Luận văn - Báo cáo
Kỹ thuật
Giao thông - Vận tải
Viễn thông
Điện - Điện tử
Cơ khí - Vật liệu
Kiến trúc - Xây dựng
Lý luận chính trị
Tư tưởng Hồ Chí Minh
Chủ nghĩa xã hội khoa học
Triết học Mác - Lênin
Đường lối cách mạng
Kinh tế chính trị
Kinh tế - Quản lý
Bảo hiểm
Định giá - Đấu thầu
Marketing
Tài chính thuế
Chứng khoán
Xuất nhập khẩu
Kiểm toán
Kế toán
Quản trị kinh doanh
Tài chính - Ngân hàng
Bất động sản
Dịch vụ - Du lịch
Tiến sĩ
Thạc sĩ - Cao học
Kinh tế
Khoa học xã hội
Y dược - Sinh học
Sư phạm
Luật
Kiến trúc - Xây dựng
Nông - Lâm - Ngư
Kỹ thuật
Công nghệ thông tin
Khoa học tự nhiên
Báo cáo khoa học
Nông - Lâm - Ngư
Lâm nghiệp
Nông học
Chăn nuôi
Thú y
Thủy sản
Công nghệ thực phẩm
Cao su - Cà phê - Hồ tiêu
Khoa học tự nhiên
Toán học
Vật lý
Hóa học
Sinh học
Địa lý - Địa chất
Khoa học xã hội
Đông phương học
Việt Nam học
Văn hóa - Lịch sử
Xã hội học
Báo chí
Văn học - Ngôn ngữ học
Giáo dục học
Tâm lý học
Quan hệ quốc tế
Y khoa - Dược
Công nghệ - Môi trường
Công nghệ thông tin
Quản trị mạng
Lập trình
Đồ họa
Web
Hệ thống thông tin
Thương mại điện tử
Lập trình di động
Kinh tế thương mại
Tài chính - Ngân hàng
Quỹ đầu tư
Bảo hiểm
Đầu tư Bất động sản
Đầu tư chứng khoán
Tài chính doanh nghiệp
Kế toán - Kiểm toán
Ngân hàng - Tín dụng
Công nghệ thông tin
Thủ thuật máy tính
Chứng chỉ quốc tế
Phần cứng
An ninh bảo mật
Tin học văn phòng
Quản trị web
Cơ sở dữ liệu
Hệ điều hành
Thiết kế - Đồ họa
Quản trị mạng
Kỹ thuật lập trình
Giáo dục - Đào tạo
Luyện thi - Đề thi
Thi THPT Quốc Gia
Địa ly
Sinh học
Hóa học
Vật lý
Môn tiếng Anh
Môn văn
Môn toán
Lịch sử
Công chức - Viên chức
Đề thi lớp 1
Đề thi lớp 2
Đề thi lớp 3
Đề thi lớp 4
Đề thi lớp 5
Đề thi lớp 6
Đề thi lớp 7
Đề thi lớp 8
Đề thi lớp 9
Đề thi lớp 10
Đề thi lớp 11
Đề thi lớp 12
Tuyển sinh lớp 10
Môn tiếng Anh
Môn văn
Môn toán
Luyện thi Đại học - Cao đẳng
Quy chế tuyển sinh
Quy chế tuyển sinh 2015
Khối D
Môn tiếng Anh
Môn văn
Môn toán
Khối C
Môn địa lý
Môn lịch sử
Môn văn
Khối B
Môn sinh
Môn hóa
Môn toán
Khối A
Môn lý
Môn hóa
Môn tiếng Anh A1
Môn toán
Mầm non - Mẫu giáo
Mẫu giáo lớn
Mẫu giáo nhỡ
Mẫu giáo bé
Tiểu học
Lớp 1
Lớp 5
Lớp 4
Lớp 3
Lớp 2
Trung học cơ sở
Lớp 9
Lớp 8
Lớp 7
Lớp 6
Trung học phổ thông
Lớp 10
Lớp 11
Lớp 12
Cao đẳng - Đại học
Kỹ thuật công nghệ
Kiến trúc xây dựng
Sư phạm
Công nghệ thông tin
Luật
Khoa học xã hội
Chuyên ngành kinh tế
Y dược
Đại cương
Giáo dục hướng nghiệp
Tiếng Anh
Tin học
Công nghệ
Thể dục
Mỹ thuật
Âm nhạc
GDCD-GDNGLL
Địa lý
Lịch sử
Sinh học
Toán học
Vật lý
Luật
Văn học
Hóa học
Giáo án - Bài giảng
Mầm non
Tiểu học
Trung học cơ sở
Sáng kiến kinh nghiệm
Bài giảng điện tử
Giáo án điện tử
Trung học phổ thông
Ngoại ngữ
Tiếng Nga - Trung - Pháp
Tiếng Nhật - Hàn
Kỹ năng nói tiếng Anh
Kiến thức tổng hợp
Chứng chỉ A,B,C
Kỹ năng viết tiếng Anh
Kỹ năng đọc tiếng Anh
Kỹ năng nghe tiếng Anh
Anh ngữ cho trẻ em
Anh văn thương mại
Anh ngữ phổ thông
Ngữ pháp tiếng Anh
TOEFL - IELTS - TOEIC
Kế toán - Kiểm toán
Kế toán
Kiểm toán
Kinh tế - Quản lý
Quy hoạch đô thị
Quản lý dự án
Tiêu chuẩn - Qui chuẩn
Quản lý nhà nước
Sách - Truyện đọc
Sách-Ebook
Y học
Giáo dục học tập
Văn hóa giải trí
Công nghệ
Ngoại ngữ
Kinh tế
Ngôn tình
Truyện dài
Tự truyện
Tiểu thuyết
Truyện ngắn
Truyện Ma - Kinh dị
Truyện cười
Truyện kiếm hiệp
Truyện thiếu nhi
Truyện văn học
Kinh doanh - Tiếp thị
Tổ chức sự kiện
Kỹ năng bán hàng
PR - Truyền thông
Tiếp thị - Bán hàng
Thương mại điện tử
Kế hoạch kinh danh
Internet Marketing
Quản trị kinh doanh
Văn hóa - Nghệ thuật
Du lịch
Sân khấu điện ảnh
Thời trang - Làm đẹp
Điêu khắc - Hội họa
Mỹ thuật
Chụp ảnh - Quay phim
Khéo tay hay làm
Ẩm thực
Âm nhạc
Báo chí - Truyền thông
Tôn giáo
Kỹ thuật - Công nghệ
Kỹ thuật viễn thông
Điện - Điện tử
Cơ khí chế tạo máy
Tự động hóa
Năng lượng
Hóa học - Dầu khi
Kiến trúc xây dựng
Nông - Lâm - Ngư
Ngư nghiệp
Lâm nghiệp
Nông nghiệp
Biểu mẫu - Văn bản
Thủ tục hành chánh
Văn bản
Biểu mẫu
Hợp đồng
Khoa học xã hội
Triết học
Văn học
Địa lý
Lịch sử
Khoa học tự nhiên
Toán học
Môi trường
Sinh học
Hóa học - Dầu khi
Vật lý
Y tế - Sức khỏe
Y học
Sức khỏe - dinh dưỡng
Sức khỏe giới tính
Sức khỏe người lớn tuổi
Sức khỏe phụ nữ
Sức khỏe trẻ em
Kỹ năng mềm
Tâm lý - Nghệ thuật sống
Kỹ năng quản lý
Kỹ năng làm việc nhóm
Kỹ năng tổ chức
Kỹ năng đàm phán
Kỹ năng tư duy
Kỹ năng giao tiếp
Kỹ năng thuyết trình
Kỹ năng lãnh đạo
Kỹ năng phỏng vấn
Thể loại khác
Chưa phân loại
Phật
Văn khấn cổ truyền
Phong Thủy
Đăng ký
Đăng nhập
Luận văn - Báo cáo
Kỹ thuật
Giao thông - Vận tải
Viễn thông
Điện - Điện tử
Cơ khí - Vật liệu
Kiến trúc - Xây dựng
Lý luận chính trị
Tư tưởng Hồ Chí Minh
Chủ nghĩa xã hội khoa học
Triết học Mác - Lênin
Đường lối cách mạng
Kinh tế chính trị
Kinh tế - Quản lý
Bảo hiểm
Định giá - Đấu thầu
Marketing
Tài chính thuế
Chứng khoán
Xuất nhập khẩu
Kiểm toán
Kế toán
Quản trị kinh doanh
Tài chính - Ngân hàng
Bất động sản
Dịch vụ - Du lịch
Tiến sĩ
Thạc sĩ - Cao học
Kinh tế
Khoa học xã hội
Y dược - Sinh học
Sư phạm
Luật
Kiến trúc - Xây dựng
Nông - Lâm - Ngư
Kỹ thuật
Công nghệ thông tin
Khoa học tự nhiên
Báo cáo khoa học
Nông - Lâm - Ngư
Lâm nghiệp
Nông học
Chăn nuôi
Thú y
Thủy sản
Công nghệ thực phẩm
Cao su - Cà phê - Hồ tiêu
Khoa học tự nhiên
Toán học
Vật lý
Hóa học
Sinh học
Địa lý - Địa chất
Khoa học xã hội
Đông phương học
Việt Nam học
Văn hóa - Lịch sử
Xã hội học
Báo chí
Văn học - Ngôn ngữ học
Giáo dục học
Tâm lý học
Quan hệ quốc tế
Y khoa - Dược
Công nghệ - Môi trường
Công nghệ thông tin
Quản trị mạng
Lập trình
Đồ họa
Web
Hệ thống thông tin
Thương mại điện tử
Lập trình di động
Kinh tế thương mại
Tài chính - Ngân hàng
Quỹ đầu tư
Bảo hiểm
Đầu tư Bất động sản
Đầu tư chứng khoán
Tài chính doanh nghiệp
Kế toán - Kiểm toán
Ngân hàng - Tín dụng
Công nghệ thông tin
Thủ thuật máy tính
Chứng chỉ quốc tế
Phần cứng
An ninh bảo mật
Tin học văn phòng
Quản trị web
Cơ sở dữ liệu
Hệ điều hành
Thiết kế - Đồ họa
Quản trị mạng
Kỹ thuật lập trình
Giáo dục - Đào tạo
Luyện thi - Đề thi
Thi THPT Quốc Gia
Địa ly
Sinh học
Hóa học
Vật lý
Môn tiếng Anh
Môn văn
Môn toán
Lịch sử
Công chức - Viên chức
Đề thi lớp 1
Đề thi lớp 2
Đề thi lớp 3
Đề thi lớp 4
Đề thi lớp 5
Đề thi lớp 6
Đề thi lớp 7
Đề thi lớp 8
Đề thi lớp 9
Đề thi lớp 10
Đề thi lớp 11
Đề thi lớp 12
Tuyển sinh lớp 10
Môn tiếng Anh
Môn văn
Môn toán
Luyện thi Đại học - Cao đẳng
Quy chế tuyển sinh
Quy chế tuyển sinh 2015
Khối D
Môn tiếng Anh
Môn văn
Môn toán
Khối C
Môn địa lý
Môn lịch sử
Môn văn
Khối B
Môn sinh
Môn hóa
Môn toán
Khối A
Môn lý
Môn hóa
Môn tiếng Anh A1
Môn toán
Mầm non - Mẫu giáo
Mẫu giáo lớn
Mẫu giáo nhỡ
Mẫu giáo bé
Tiểu học
Lớp 1
Lớp 5
Lớp 4
Lớp 3
Lớp 2
Trung học cơ sở
Lớp 9
Lớp 8
Lớp 7
Lớp 6
Trung học phổ thông
Lớp 10
Lớp 11
Lớp 12
Cao đẳng - Đại học
Kỹ thuật công nghệ
Kiến trúc xây dựng
Sư phạm
Công nghệ thông tin
Luật
Khoa học xã hội
Chuyên ngành kinh tế
Y dược
Đại cương
Giáo dục hướng nghiệp
Tiếng Anh
Tin học
Công nghệ
Thể dục
Mỹ thuật
Âm nhạc
GDCD-GDNGLL
Địa lý
Lịch sử
Sinh học
Toán học
Vật lý
Luật
Văn học
Hóa học
Giáo án - Bài giảng
Mầm non
Tiểu học
Trung học cơ sở
Sáng kiến kinh nghiệm
Bài giảng điện tử
Giáo án điện tử
Trung học phổ thông
Ngoại ngữ
Tiếng Nga - Trung - Pháp
Tiếng Nhật - Hàn
Kỹ năng nói tiếng Anh
Kiến thức tổng hợp
Chứng chỉ A,B,C
Kỹ năng viết tiếng Anh
Kỹ năng đọc tiếng Anh
Kỹ năng nghe tiếng Anh
Anh ngữ cho trẻ em
Anh văn thương mại
Anh ngữ phổ thông
Ngữ pháp tiếng Anh
TOEFL - IELTS - TOEIC
Kế toán - Kiểm toán
Kế toán
Kiểm toán
Kinh tế - Quản lý
Quy hoạch đô thị
Quản lý dự án
Tiêu chuẩn - Qui chuẩn
Quản lý nhà nước
Sách - Truyện đọc
Sách-Ebook
Y học
Giáo dục học tập
Văn hóa giải trí
Công nghệ
Ngoại ngữ
Kinh tế
Ngôn tình
Truyện dài
Tự truyện
Tiểu thuyết
Truyện ngắn
Truyện Ma - Kinh dị
Truyện cười
Truyện kiếm hiệp
Truyện thiếu nhi
Truyện văn học
Kinh doanh - Tiếp thị
Tổ chức sự kiện
Kỹ năng bán hàng
PR - Truyền thông
Tiếp thị - Bán hàng
Thương mại điện tử
Kế hoạch kinh danh
Internet Marketing
Quản trị kinh doanh
Văn hóa - Nghệ thuật
Du lịch
Sân khấu điện ảnh
Thời trang - Làm đẹp
Điêu khắc - Hội họa
Mỹ thuật
Chụp ảnh - Quay phim
Khéo tay hay làm
Ẩm thực
Âm nhạc
Báo chí - Truyền thông
Tôn giáo
Kỹ thuật - Công nghệ
Kỹ thuật viễn thông
Điện - Điện tử
Cơ khí chế tạo máy
Tự động hóa
Năng lượng
Hóa học - Dầu khi
Kiến trúc xây dựng
Nông - Lâm - Ngư
Ngư nghiệp
Lâm nghiệp
Nông nghiệp
Biểu mẫu - Văn bản
Thủ tục hành chánh
Văn bản
Biểu mẫu
Hợp đồng
Khoa học xã hội
Triết học
Văn học
Địa lý
Lịch sử
Khoa học tự nhiên
Toán học
Môi trường
Sinh học
Hóa học - Dầu khi
Vật lý
Y tế - Sức khỏe
Y học
Sức khỏe - dinh dưỡng
Sức khỏe giới tính
Sức khỏe người lớn tuổi
Sức khỏe phụ nữ
Sức khỏe trẻ em
Kỹ năng mềm
Tâm lý - Nghệ thuật sống
Kỹ năng quản lý
Kỹ năng làm việc nhóm
Kỹ năng tổ chức
Kỹ năng đàm phán
Kỹ năng tư duy
Kỹ năng giao tiếp
Kỹ năng thuyết trình
Kỹ năng lãnh đạo
Kỹ năng phỏng vấn
Thể loại khác
Chưa phân loại
Phật
Văn khấn cổ truyền
Phong Thủy
Trang chủ
Giáo dục - Đào tạo
Tin học
Bồi dưỡng học sinh giỏi môn tin học chuyên đề vận dụng thuật toán tìm kiếm nhị p...
Tài liệu Bồi dưỡng học sinh giỏi môn tin học chuyên đề vận dụng thuật toán tìm kiếm nhị phân giải quyết một số bài toán
.PDF
44
2835
155
dangvantuan
Báo vi phạm
Tải xuống
155
Đang tải nội dung...
Xem thêm (5 trang)
Tải về
Mô tả:
Chuyên đề: VẬN DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN GIẢI QUYẾT MỘT SỐ BÀI TOÁN Trường THPT chuyên Lê Hồng Phong NĐ 1 I. ĐẶT VẤN ĐỀ Tìm kiếm là một việc thường xảy ra trong cuộc sống. Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Thuật toán tìm kiếm nhị phân là một trong những thuật toán tìm kiếm quan trọng nhất của tin học. Thuật toán này còn được gọi là thuật toán chặt nhị phân hay thuật toán chia đôi được áp dụng rất nhiều trong giải toán, nó làm giảm được nhiều thời gian tìm kiếm, giúp chương trình chạy nhanh hơn. IV. NỘI DUNG 1.Phương pháp tìm kiếm: Thuật toán tìm kiếm nhị phân liên quan đến bài toán sau: “ Cho mảng n phần tử đã được sắp tăng dần và một phần tử x. Tìm xem x có trong mảng hay không” Yêu cầu: Thuật toán này chỉ có thể được dùng khi dãy số được sắp xếp đơn điệu theo thứ tự tăng hoặc giảm dần. Tư tưởng của thuật toán: chọn phần tử ở vị trí giữa làm chốt, chia dãy thành 2 phần có kích thước nhỏ hơn. Sau đó so sánh phần tử cần tìm x với chốt, nếu x lớn hơn chốt tìm ở nửa sau của dãy, nếu x nhỏ hơn chốt tìm ở nửa trước của dãy (áp dụng với dãy tăng), quá trình trên tiếp tục cho tới khi tìm được x hoặc dãy chia không còn phần tử nào. Ví dụ: Cho dãy số: A={-6,1,3,5,8,10,14,16,19,21 }; x=5; dãy gồm 10 phần tử Gọi phần tử chốt là k, ban đầu k=8 Bước 1: k=8, so sánh x với k, x
k ta tìm kiếm x ở nửa sau {3,5,8} Bước 3: k=5, so sánh x với k, x=k ta tìm được x kết thúc. Procedure TKNP (x: Item, a1,a2,...,an: Item); Begin Trường THPT chuyên Lê Hồng Phong NĐ 2 d := 1; {d là điểm đầu của đoạn tìm kiếm} c := n; {c là điểm cuối của đoạn tìm kiếm} tim_thay:=false; while (d <=c) and not tim_thay do begin g:= (d+c) div 2 if x = a[g] then tim_thay :=true else if x
2*g+4*(36-g) thì c:=g 2.4Nếu x<2*g+4*(36-g) thì d:=g 3.Quay lại bước 2 4.Kết thúc. Bài 3. SỐ 0 CUỐI CÙNG Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong dãy. Thuật toán: Ta tiến hành tìm kiếm nhị phân trên xâu kí tự để tìm ra vị trí số 0 cuối cùng như sau: - Tìm phần tử giữa xâu đang xét - So sánh kí tự ở vị trí giữa xâu với kí tự 0. - Nếu kí tự giữa xâu là kí tự 0 thì ta tìm ở nửa sau của xâu, nếu không phải kí tự 0 (mà là 1) thì ta tìm ở nửa trước của xâu. 1.d:=1; c:=length(s); 2. trong khi d
8 thì C52.8 =C516 = (12.13.14.15.16)/(1.2.3.4.5)= 13.7.3.16=4368 > 2048 Thuật toán: 1. d=0;c= 8; x=2048; 2. trong khi d
tong(g)) thì l:=g 2.4.Nếu (x
M thì cuối =h - Tiếp tục kiểm tra h cho đến khi chênh lệch của M,S lặp lại. writeln('Chieu cao cua cac cay la:'); for i:=1 to n do begin write('cay ',i,'=');readln(a[i]); if a[i]>c then c:=a[i]; end; d:=0;kt:=true; while kt and (d<=c) do begin s:=0; g:=(d+c) div 2; Trường THPT chuyên Lê Hồng Phong NĐ 7 for i:=1 to n do begin t:=a[i]-g; if t>=0 then s:=s+t; end; t:=s-m; if (t=0 )or (cl=t)then kt:=false else begin cl:=t; if t<0 then c:=g else d:=g; end; end; if t>=0 then write('h=',g) else write('ko tim dc'); B. PHẦN NÂNG CAO Trong thực tế, ta thường gặp dạng bài toán tìm thời điểm kết thúc sớm nhất (hay muộn nhất) của một công việc, tìm chi phí bé nhất (hay lớn nhất),… với các yêu cầu ràng buộc trong đề bài. Khi đó ta nghĩ đến một thuật toán rất hiệu quả - thuật toán tìm kiếm nhị phân. Sau đây là một số bài tập trong các đề thi học sinh giỏi Bài 6. CHỈNH DÃY SỐ Cho một dãy N (N≤2x105) số nguyên dương không quá 109. Có thể giữ nguyên hoặc bỏ không quá một đoạn liên tiếp các số trong dãy. Hãy thực hiện một trong hai cách trên sao cho dãy số thu được có độ dài đoạn liên tiếp tăng dần là lớn nhất. Ví dụ : với dãy 1 2 3 1 4 5 sẽ chỉ có cách bỏ số 1 thứ 2 trong dãy đi để thu được dãy mới có độ dài đoạn con liên tiếp tăng dần là 5 Với dãy 1 3 4 6 ta không cần bỏ số nào đi Dữ liệu vào từ file DEFENSE.INP - Dòng 1 : số nguyên T≤25 là số bộ test Trường THPT chuyên Lê Hồng Phong NĐ 8 - T nhóm dòng sau: mỗi nhóm gồm 2 dòng. Dòng đầu ghi số nguyên N, dòng sau ghi N số nguyên là các số trong dãy theo thứ tự từ trái qua phải Kết quả ghi ra flie DEFENSE.OUT chứa độ dài đoạn con liên tiếp tăng dần lớn nhất có thể thu được. Ví dụ : DEFENSE.INP DEFENSE.OUT 2 4 9 6 534928671 7 1 2 3 10 4 5 6 Thuật toán : Gọi L[i] là độ dài dãy dài nhất các số liên tiếp tăng dần kết thúc tại A[i] R[i] là độ dài dãy dài nhất các số liên tiếp tăng dần bắt đầu tại A[i] R và L tính được nhờ thuật toán quy hoạch động. Ta phải tìm giá trị cực đại của tổng L[i]+R[j] sao cho i ≤ j và A[i]
=i f[y]:=r[c[y]] ; for i:=y- 1 downto m+1 do f[i]:= max(r[c[i]], f[i+1]) ; // voi moi i ta se tim v nho nhat sao cho a[c[v]]>a[c[i]] v:= m+1 ; for i:=x to m do Begin While (v
a[c[i]] then res:=max(res, l[c[i]]+f[v]) ; End ; //tron 2 doan da sap xep u:=x ; v:=m+1 ; for i :=x to y do Trường THPT chuyên Lê Hồng Phong NĐ 10 if (v>y) or ((v<=y) and (u<=m) and (a[c[u]])< a[c[v]])) then begin d[i] :=c[u] ; inc(u) ; end else begin d[i] :=c[v] ; inc(v) ; end ; for i := x to y do c[i] :=d[i] ; end ; procedure solve ; var i:longint ; begin //tinh l,r L[1]:=1; For i :=2 to n do begin L[i] :=1 If (a[i]>a[i-1]) then l[i] :=l[i-1]+1 ; End ; R[n] :=1 ; For i :=n-1 downto 1 do begin R[i] :=1 ; If (a[i]
0 do begin Dec(ntest);enter ;solve ; Writeln(fo, res); end ; Close(fo) ; close(fi); End. Bài 7. CĂN N Biết rằng căn bậc N của một số S là một sốnguyên <106. Tìm căn bậc N của S Dữ liệu vào: file CANN.INP Dòng 1 là số N (N ≤ 100) CANN.INP CANN.OUT Dòng 2 là số S(0 ≤ S ≤ 10100 ) 4 Kết quả ra: file CANN.OUT 81 3 Gồm 1 dòng duy nhất là căn bậc N của số S. Thuật toán: - Cmin =0; Cmax = 106.Kết quả sẽ nằm trong đoạn [C min ,Cmax ]. - Đặt Ctg =(Cmin +Cmax )div 2. Tính A= C TG N. Để tính A ta dùng thuật toán nhân sốlớn. Nếu A > S thì tìm kiếm trong đoạn [C tg+1 ,Cmax ] Nếu A < S thì tìm kiếm trong đoạn [ Cmin , C tg -1 ] Nếu A=S thì căn bậc N của S chính là C tg - Tiếp tục tìm kiếm cho tới khi C min >Cmax Cài đặt: type ds=array[1..1000] of 0..9; Trường THPT chuyên Lê Hồng Phong NĐ 12 var x,y,kqc:ds; a,b,s,skq,stg:string; ctg,n,m,j,k,p,spt,l,i,cmin,cmax:longint; f,g:text; procedure htkq(x:ds;n:longint); var i:byte; begin for i:=1 to n do write(x[i]); end; procedure nhan(x,y:ds;vt:byte); {Nhan mot chu so o vi tri vt cua so y voi so x} var kq:ds; nho,i,t,tg:byte; begin for k:=1 to m-vt do kq[k]:=0; k:=m-vt; nho:=0; for i:=l downto 1 do begin k:=k+1; tg:=(nho+x[i]*y[vt]) div 10; kq[k]:=(nho + x[i]*y[vt]) mod 10; nho:=tg; end; if nho>0 then begin k:=k+1; kq[k]:=nho; end; Trường THPT chuyên Lê Hồng Phong NĐ 13 {cong ket qua tinh duoc (kq) vao voi ket qua cuoi cung (kqc)} nho:=0; for t:=1 to k do begin tg:=(nho+kq[t]+kqc[t]) div 10; kqc[t]:=(kq[t]+kqc[t]+nho) mod 10; nho:=tg; end; t:=k; while nho>0 do begin t:=t+1; tg:=(nho+kqc[t]) div 10; kqc[t]:=(nho+kqc[t])mod 10; nho:=tg; end; kqc[t]:=nho+kqc[t]; spt:=t; end; procedure xlkq; var i,j,tg:byte; begin i:=1; j:=spt; while i<=j do begin tg:=kqc[i];kqc[i]:=kqc[j];kqc[j]:=tg; i:=i+1; j:=j-1; end; Trường THPT chuyên Lê Hồng Phong NĐ 14 end; function ss(s1,s2:string):boolean; var u,v,q:longint; kt:boolean; begin u:=length(s1); v:=length(s2); if u>v then kt:=true else if u
s do Trường THPT chuyên Lê Hồng Phong NĐ 15 begin ctg:=(cmin+cmax) div 2; skq:=''; str(ctg,a); str(ctg,b); {tinh ctg mu n} for p:=2 to n do begin l:=length(a); m:=length(b); for i:=1 to l do x[i]:=ord(a[i])-48; for i:=1 to m do y[i]:=ord(b[i])-48; for k:=1 to l+m+1 do kqc[k]:=0; for j:=m downto 1 do nhan(x,y,j); xlkq; a:=''; for i:=1 to spt do begin str(kqc[i],stg); a:=a+stg; end; end; skq:=a; if ss(skq,s) then cmax:=ctg-1 else cmin:=ctg+1; end; writeln(g,ctg); close(f); close(g); end. Trường THPT chuyên Lê Hồng Phong NĐ 16 Bài 8. Dãy con tăng dài nhất (LIS (http://vn.spoj.pl/problems/LIS/)) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint. Input: File Lis.Inp Dòng đầu tiên gồm số nguyên N. Dòng thứ hai gồm N số mô tả dãy. Output: file Lis.Out Gồm một số nguyên duy nhất là đáp số của bài toán Ví dụ: Lis.Inp Lis.Out 5 3 2 1 4 3 5 Thuật toán: Gọi k là độ dài cực đại của dãy con tăng và ký hiệu H[1..k] là dãy có ý nghĩa sau: H[i] là số hạng nhỏ nhất trong các số hạng cuối cùng của các dãy con tăng có độ dài i. Đuơng nhiên h[1] < h[2] <.. < h[k]. Mỗi khi xét thêm một giá trị mới trong dãy A thì các giá trị trong dãy H và giá trị k cũng tương ứng thay đổi. Res:=1; H[1]:=1; For i:=2 to n do Begin If A[i] < a[h[1]] then h[1]:=i else if a[i] > a[h[res]] then Begin Inc(Res); H[res]:=i; End else Begin d:=1; c:=Res; While d<>c do Trường THPT chuyên Lê Hồng Phong NĐ 17 begin mid:=(d+c+1) div 2; If A[i] > a[h[mid]] then d:=mid else c:=mid-1; End; Mid:=(d+c) div 2; If (A[h[mid]] < a[i]) and (a[i]
Maxv then Maxv:=a[i,j]; End; Readln(Fi); End; End; Function Ktra(Maxc:Integer):Boolean;{ktra xem co the chia thanh k phan voi do giam suc manh va hay khong} Var i,j,dem,u,v,s,Nhom,d,c:integer; kt:boolean; dd:array[1..Max]Of Boolean; q:array[1..Max] Of Integer; Begin Nhom:=0;dem:=0; Fillchar(dd,sizeof(dd),True); While (dem
0 then Begin Trường THPT chuyên Lê Hồng Phong NĐ 20
- Xem thêm -
Tài liệu liên quan
Trắc nghiệm tin học 11 có đáp án (6 chương)...
43
103201
129
Skkn tin học-một số bài tập thực hành về cách làm vi...
18
19401
151
Ngân hàng câu hỏi trắc nghiệm lý thuyết ứng dụng chứ...
133
15112
148
Skkn tích hợp hoạt động trải nghiệm sáng tạo trong d...
54
12083
100
Cách sử dụng hàng đợi ưu tiên (priority queue) khi k...
14
10986
136
Skkn-hướng dẫn học sinh thực hành môn tin học phù hợ...
14
9836
133
Skkn-kinh nghiệm bồi dưỡng học sinh giỏi môn tin học...
35
8470
78
Giáo án liên môn tích hợp tin học 8 Bài 5. Từ bài to...
12
7868
150
455 câu hỏi trắc nghiệm tin học nâng cao theo từng m...
59
6407
103
Giáo án tin học lớp 11. (đúng chuẩn kiến thức kĩ năn...
48
5415
77
Bồi dưỡng học sinh giỏi tin học lớp 11...
245
5236
143
Bồi dưỡng học sinh giỏi môn tin học thpt chuyên đề m...
12
5107
120
Chuyên đề xâu bồi dưỡng hsg tin học...
52
4170
89
Skkn hướng dẫn khắc phục một số sự cố khi đăng ký và...
19
4061
81
Skkn giúp dạy tốt và học tốt bài “bài toán và thuật ...
17
3804
109
Phương pháp giải các dạng bài tập tin học 11-đậu mạn...
249
3571
130
Skkn tích hợp kiến thức liên môn địa lý, gdcd với vi...
25
3422
124
Skkn xây dựng trò chơi trên phần mềm activinspire tạ...
22
3307
110
Skkn mô phỏng thuật toán sắp xếp bằng tráo đổi (exch...
10
3260
96
Bồi dưỡng học sinh giỏi môn tin học thpt chuyên đề ứ...
29
3248
114
×
Tải tài liệu
Chi phí hỗ trợ lưu trữ và tải về cho tài liệu này là
đ
. Bạn có muốn hỗ trợ không?
Tài liệu vừa đăng
Skkn lồng ghép trò chơi trong dạy học nghề tin học
13
125
55
Giai phap nccl môn tin.pptx
1
61
Sử dụng trò chơi đầu tiết học nhằm nâng cao kết quả học bài 6 câu lệnh điều kiện cho nhóm học sinh lớp 8a3 trường thcs an bình, huyện phú giáo.
40
261
70
Sử dụng phần mềm fscapture để dạy bài thực hành 6 tin học 7 nhằm nâng cao kết quả học tập của học sinh lớp 7
18
203
69
Skkn đổi mới kiểm tra, đánh giá môn tin học lớp 11
20
269
88
234 câu trắc nghiệm tin học ôn thi công chức có đáp án (office 2010)
32
366
131
Đột phá bằng casio fx570vn plus môn toán (phần 2)
1
124
Đề cương ôn thi tin học trẻ (toán tin - có đáp án)
21
303
80
100 đề thi toán tin học (có bài giải)
159
413
93
Skkn ứng dụng e learning trong dạy tin học tại trường thpt
21
525
57
Tài liệu xem nhiều nhất
Trắc nghiệm tin học 11 có đáp án (6 chương)
43
103201
129
Skkn tin học-một số bài tập thực hành về cách làm việc với tệp – tiết 39; 40
18
19401
151
Ngân hàng câu hỏi trắc nghiệm lý thuyết ứng dụng chứng chỉ CNTT cơ bản
133
15112
148
Skkn tích hợp hoạt động trải nghiệm sáng tạo trong dạy học tin học ở trường trung học phổ thông
54
12083
100
Cách sử dụng hàng đợi ưu tiên (priority queue) khi khai thác stl trong c++
14
10986
136
Skkn-hướng dẫn học sinh thực hành môn tin học phù hợp lực học, khả năng của mỗi học sinh nhằm nâng cao kết quả học tập môn tin học của học sinh
14
9836
133
Skkn-kinh nghiệm bồi dưỡng học sinh giỏi môn tin học 9
35
8470
78
Giáo án liên môn tích hợp tin học 8 Bài 5. Từ bài toán đến chương trình.
12
7868
150
455 câu hỏi trắc nghiệm tin học nâng cao theo từng module ôn thi ic3 có đáp án
59
6407
103
Giáo án tin học lớp 11. (đúng chuẩn kiến thức kĩ năng từ tiết 1 đến tiết 12)
48
5415
77