Sáng kiến kinh nghiệm THPT: Sử dụng thuật toán lùa bò vào chuồng để giải các bài toán đếm

Chia sẻ: Ganuongmuoiot | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

79
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Đếm" ở đây không phải đơn thuần là đếm 1, 2, 3, ... mà còn cần ở người đếm một sự khéo léo và có thể có một chút kỹ thuật. Bên cạnh đó để giúp các em học sinh có kiến thức khoa học cơ bản, hiện đại, tiến tiến, có tính tự lập và khả năng sáng tạo, nhận thức ở mức độ cao, tư duy tốt về lập trình. Các phương pháp đếm đơn giản là một trong những vấn đề mà bất cứ người lập trình tin học đều cần phải nắm vững.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Sử dụng thuật toán lùa bò vào chuồng để giải các bài toán đếm

I. ĐẶT VẤN ĐỀ I.1. Lý do chọn đề tài Sự phát triển như vũ bão của Công nghệ Thông tin và Truyền thông đóng vai trò không nhỏ trong sự phát triển chung của nhân loại. Đảng và nhà nước đã xác định rõ ý nghĩa và tầm quan trọng của tin học, Công nghệ Thông tin và Truyền thông cũng như yêu cầu đẩy mạnh của ứng dụng Công nghệ Thông tin, đào tạo thế hệ trẻ năng động, sáng tạo, nắm vững tri thức khoa học công nghệ để làm chủ trong mọi hoàn cảnh công tác và hoạt động xã hội trong thời kỳ công nghiệp hóa và hiện đại hóa đất nước. Chính vì xác định được tầm quan trọng đó nên nhà nước đã đưa môn tin học vào trong nhà trường và ngay từ tiểu học học sinh được tiếp xúc môn tin học để làm quen dần với lĩnh vực công nghệ thông tin, tạo nền móng ban đầu để học những phần nâng cao tiếp theo. Đối với các em học sinh, có thể nói đây là một hành trang để giúp các em vững bước đi tới tương lai - tương lai của thời đại công nghệ thông tin bùng nổ! Trong chương trình Tin học THPT lớp 10 học sinh được giới thiệu các kiến thức đại cương về tin học, lớp 11 học sinh được giới thiệu về lập trình, lớp 12 học sinh được học về cơ sở dữ liệu. Đặc biệt, chương trình Tin học lớp 11 là phần được cho là khó cho Thầy Cô giáo cũng như học sinh, vì phải làm thế nào để học sinh có thể hiểu được ngôn ngữ lập trình, để từ đó có thể lựa chọn và thiết kế thuật toán. Chương trình tin học lớp 11 nhằm rèn luyện tư duy về thuật toán cho học sinh, rèn luyện kĩ năng lập trình, tính kiên trì, tỉ mỉ cẩn thận. Đối với học sinh thì phải làm quen với lối suy nghĩ logic với sự hoạt động của máy tính, mà đây lại là một lối suy nghĩ hoàn toàn khác với các môn học khác. Từ thực tiễn giảng dạy học sinh đại trà cũng như học sinh đội tuyển học sinh giỏi Tin học của trường THPT tôi thấy rằng, học sinh gặp khó khăn khi chuyển lời giải các bài toán từ toán sang ngôn ngữ lập trình. Đặc biệt là việc phân tích bài toán, nhận biết bài toán đó có thể giải quyết bằng phương pháp nào, cỏ lời giải tối ưu hay không? Để hệ thống lại các chuyên đề bồi dưỡng học sinh giỏi (HSG) Tin học mà tôi đã dạy trong nhiều năm qua, đồng thời qua quá trình nghiên cứu, giảng dạy, tham khảo ý kiến đồng nghiệp, tôi thấy rằng một số bài toán tin học có liên quan đến việc đếm. Chính vì vậy tôi chọn viết đề tài về chuyên đề “Sử dụng thuật toán “lùa bò vào chuồng” để giải các bài toán đếm”. 1
I.2. Mục tiêu nghiên cứu "Đếm" là công việc quan trọng và đơn giản mà chúng ta làm thường ngày, điều đó thì không cần phải bàn đến làm gì? Điều đáng nói ở đây là công việc có vẻ nhàm chán đó lại chứa bao điều thú vị, nhất là khi gặp những bài toán yêu cầu ta phải "đếm". "Đếm" ở đây không phải đơn thuần là đếm 1, 2, 3, ... mà còn cần ở người đếm một sự khéo léo và có thể có một chút kỹ thuật. Bên cạnh đó để giúp các em học sinh có kiến thức khoa học cơ bản, hiện đại, tiến tiến, có tính tự lập và khả năng sáng tạo, nhận thức ở mức độ cao, tư duy tốt về lập trình. Các phương pháp đếm đơn giản là một trong những vấn đề mà bất cứ người lập trình tin học đều cần phải nắm vững. I.3. Nhiệm vụ nghiên cứu Trước hết là thực hiện đổi mới phương pháp giảng dạy Tin học làm cho học sinh tìm ra những kết quả sáng tạo, lời giải hay trên một số “dạng bài toán tin có liên quan đến việc đếm”; giúp bản thân nắm vững hơn nữa về tư duy thuật toán, khả năng lập trình, đồng thời để trao đổi và học tập kinh nghiệm với các quý thầy cô giáo trong nhóm Tin học của nhà trường nói riêng và các quý thầy cô giảng dạy môn Tin học trong ngành nói chung. I.4. Đối tượng nghiên cứu Trong nghiên cứu này, các học sinh được chọn là các em học sinh học môn Tin học khối 10, khối 11, các học sinh là thành viên của đội tuyển HSG môn Tin học, và một số giáo viên đứng lớp dạy Tin học ở các trường THPT trên địa bàn. I.5. Các phương pháp nghiên cứu * Phương pháp suy luận, tổng hợp: kết hợp từ nhiều nguồn tài liệu tham khảo của các tác giả và tra cứu trên mạng internet với các đề thi HSG rút ra những kinh nghiệm, hệ thống lại kiến thức, mở ra các hướng mới. * Phương pháp trò chuyện – phỏng vấn: trao đổi tâm tình với nhiều HSG để nắm tình hình trong việc giải các bài toán tin về dãy số (mảng). * Phương pháp khảo sát: bản thân được tham gia giảng dạy các lớp, đội tuyển HSG, các kỳ tập huấn; tham khảo các thầy cô, đồng nghiệp giảng dạy đội tuyển nhiều năm nên có tìm hiểu thêm về các phương pháp làm bài của các em học sinh. * Phương pháp phân tích lý luận: phân tích giúp học sinh nắm thật rõ bản chất vấn đề, lựa chọn được phương pháp giải cho phù hợp. 2
II. NỘI DUNG ĐỀ TÀI II. 1. Lịch sử của vấn đề nghiên cứu Trong những năm liên tiếp dạy bồi dưỡng HSG môn Tin Học lớp 10, 11, 12 thi HSG cấp Tỉnh, cũng như tham khảo ý kiến các đồng nghiệp chuyên dạy bồi dưỡng đội tuyển ở trong trường, trong ngành và các Tỉnh bạn, ở các trường THPT Chuyên, tôi rút ra một điều là “công việc đếm rất quan trọng trong dạy lập trình”, vì vậy tôi mạnh dạn chọn viết đề tài: Sử dụng thuật toán “lùa bò vào chuồng” để giải các bài toán đếm. II. 2. Cơ sở lý luận của đề tài Kết hợp các bài giảng chuyên đề bồi dưỡng HSG của cá nhân tôi và các tài liệu tham khảo để phân tích, tổng hợp, hệ thống. II. 3. Thực trạng của vấn đề nghiên cứu Đa số HSG tin rất ngại, sợ khi giải các bài toán tin có liên quan đến việc đếm; rất lúng túng trong quá trình phân tích, tổ chức dữ liệu, tìm thuật toán hiệu quả để hiểu được bản chất và vận dụng kiến thức một cách thích hợp. II. 4. Nội dung nghiên cứu và kết quả nghiên cứu A. NỘI DUNG NGHIÊN CỨU Tư tưởng của thuật toán được xây dựng dựa trên suy nghĩ thực tế là để đếm số lượng bò trên một vùng xác định thì người ta phải tìm cách lùa chúng vào các chuồng (để chúng khỏi chạy rông) cho dễ đếm. Đương nhiên là những con bò cùng loại phải được lùa vào cùng một chuồng để dễ phân biệt hoặc lùa mỗi con vào một chuồng thì càng tốt. Tương tự như vậy, muốn giải bài toán đếm các đối tượng thì ta dùng một cấu trúc dữ liệu hợp lý (thường dùng kiểu mảng hoặc kiểu con trỏ) với ý nghĩa giống như các “chuồng” để lưu các đối tượng, mỗi phần tử của mảng tương ứng với một chuồng. Trên cơ sở đó ta dễ dàng thực hiện được mục đích của mình là thực hiện thao tác đếm. Để hiểu rõ hơn thuật toán ta xét ví dụ sau: “Viết chương trình nhập từ bàn phím một xâu ký tự S và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng Anh trong S (không phân biệt chữ hoa hay chữ thường)” – Bài 2. Bài tập và thực hành 5 - sách Tin học 11 - trang 73. Rõ ràng với bài toán này ta có thể duyệt toàn bộ xâu S và mỗi lần duyệt ta thực hiện thao tác đếm một chữ cái. Sau 26 lần duyệt tương ứng với 26 chữ cái thì ta thu được toàn bộ kết quả. Tuy nhiên, vì việc duyệt xâu như vậy tương 3
đối chậm và có thể xâu văn bản đã cho rất dài nên về thời gian là không chấp nhận được. Ta vận dụng thuật toán “lùa bò vào chuồng” bằng cách sử dụng một mảng tĩnh A:array[′A′..′Z′] of Longint; với ý nghĩa như sau: giá trị A[c] trong đó c thuộc [′A′..′Z′] lưu số lần xuất hiện của ký tự c trong file văn bản. Mảng A được khởi tạo với tất cả các giá trị bằng 0, khi duyệt xâu ta đọc lần lượt các ký tự trong xâu ra một biến trung gian ch nào đó, và tăng giá trị của mảng tại vị trí tương ứng có chỉ số ch lên một đơn vị qua câu lệnh: A[ch]:=A[ch] + 1. Như vậy, bài toán được giải quyết chỉ với một lần duyệt xâu duy nhất. Sau đây chúng ta cùng khảo sát một số ví dụ điển hình vận dụng thuật toán này. 1. Bài 1: Đếm bò Tên chương trình: DEMBO.* Bài toán đặt ra là giả sử trên cánh đồng rộng thả rất nhiều bò (N con), mỗi con bò đeo một thẻ có số hiệu nguyên dương (là số tháng tuổi của nó). Tất nhiên, hai con bò cùng tháng tuổi thì đeo thẻ có số hiệu như nhau. Làm thế nào để đếm được loại bò nào có nhiều nhất? Bài toán này có thể phát biểu lại như sau: + Nhập từ bàn phím số nguyên dương N (0 < N ≤ 200) và các phần tử của mảng một chiều A(N) có giá trị nguyên dương (0 < A[i] ≤ 100). + Giá trị nào xuất hiện nhiều nhất trong A và xuất hiện bao nhiêu lần? + Ví dụ: A(12) = {2, 3, 2, 4, 5, 6, 2, 6, 7, 1, 6, 2} thì A(12) có số phần tử giá trị bằng 2 là nhiều nhất. Số lượng phần tử này là 4. Thuật toán “Lùa bò vào chuồng” Để giải bài toán này người ta dùng thuật toán “lùa bò vào chuồng” gồm 3 bước: - Bước 1: Đóng dãy chuồng bò và đánh số các chuồng bằng các số tự nhiên liên tiếp từ 1 đến max (max là số tháng tuổi của con bò già nhất), ban đầu mọi chuồng đều chưa có bò ở trong. - Bước 2: Lùa bò vào chuồng có số hiệu bằng số thẻ của nó. - Bước 3: Duyệt dãy chuồng bò tìm chuồng có nhiều bò nhất. Áp dụng thuật toán vào bài tập: 4
+ Bước 1: Giả sử con bò thứ i có tháng tuổi là a[i] (1 ≤ i ≤ n). Coi mảng b(n) như dãy chuồng bò, b[x] là số lượng bò (có x tháng tuổi) trong chuồng có số hiệu x, ban đầu các phần tử của mảng b(n) đều bằng 0. + Bước 2: Con bò có tháng tuổi a[i] phải vào chuồng bò có số hiệu a[i]. Thêm 1 con bò vào chuồng a[i] tương ứng với lệnh inc(b[a[i]]) + Bước 3: Duyệt mảng b, tìm chỉ số phần tử lớn nhất. Chương trình tham khảo: Code Pascal Code C++ Const max = 200; #include Var N: integer; using namespace std; A: array[1..max] of byte; int i, j, n, a[200], b[200], maxsl; B: array[1..max] of byte; int main() maxsl, i, li: integer; { BEGIN cout >n; For i := 1 to N do for(i=1;i
Write('So ', li, ' co so luong lon nhat la ', return 0; maxsl); } Readln; END. 2. Bài 2: Nhập vào số nguyên dương N (2 ≤ N ≤ 10000) và một dãy a1, a2,….an các phần tử nguyên dương (ai ≤ 32000). Cho biết dãy trên có bao nhiêu phần tử khác nhau. Ý tưởng: Để làm bài này ta dùng thuật toán “lùa bò vào chuồng”, các phần tử bằng nhau sẽ nhốt chung một chuồng, có bao nhiêu chuồng thì có bấy nhiêu phần tử khác nhau trong dãy ban đầu. Ta đóng dãy chuồng C, đánh số chuồng lần lượt từ 1, 2….32000 ( ai là các số nguyên dương, ain; a[i]:=random(maxint)-random(100); for(i=1; i
writeln('So phan tu khac nhau cua day la cout
read(f, x); if(x
Lời giải cho bài toán này gần giống như ví dụ đã trình bày ở trên. Bạn đọc có thể xem thuật giải thông qua chương trình mẫu dưới đây: var a:array[1..256] of longint; n:integer; procedure solve; var f:text; i,j,k:integer; s:string; ss:set of byte; begin fillchar(a,sizeof(a),0); ss:=[65..90]; assign(f,′FREQ.INP′); reset(f); readln(f,n); for i:=1 to n do begin readln(f,s); for j:=1 to length(s) do begin k:=ord(s[j]); if k in ss then k:=k+32; inc(a[k]); end; end; close(f); end; procedure output; var f:text; i,m:longint; begin assign(f,′FREQ.OUT′); Rewrite(f); 9
m:=a[1]; for i:=2 to 256 do if m < a[i] then m:=a[i]; write(f,m); close(f); end; BEGIN solve; output; END. 5. Bài 5. Phủ nhỏ nhất (Đề thi chọn HSG Quốc gia lớp 12 năm 1998-1999) Cho tập hợp n đoạn thẳng (đánh số từ 1 đến n) với các đầu mút có toạ độ nguyên [Li,Ri], i=1,2, 3,…,n và một đoạn thẳng [P,Q] (P, Q là các số nguyên). Yêu cầu: Cần tìm một số ít nhất đoạn thẳng trong tập đã cho để phủ kín đoạn thẳng [P,Q] (nghĩa là mỗi điểm x thuộc [P,Q] phải thuộc vào ít nhất một trong số các đoạn thẳng được chọn). Dữ liệu vào: từ file văn bản PHU.INP: - Dòng đầu tiên ghi 3 số n, P, Q phân cách nhau bởi dấu trắng; - Dòng thứ i trong số n dòng tiếp theo chứa hai số L, R phân cách nhau bởi dấu trắng (i=1, 2,…, n); 1 ≤ n ≤ 100 000; P − Q ≤ 5000; |Li| ≤ 50000; |Ri|≤50000, i = 1, 2,…, n. Kết quả: ghi ra file văn bản PHU.OUT: - Dòng đầu tiên ghi số k là số lượng đoạn cần chọn (quy ước ghi số 0 nếu không tìm được lời giải); - Nếu k > 0 thì mỗi dòng trong số k dòng tiếp theo ghi số của một đoạn thẳng được chọn. Ví dụ: PHU.INP PHU.OUT 201 1 -1 0 2 01 10
Thuật toán: Ta phân tích bài toán để có thể áp dụng sáng tạo tư tưởng của thuật toán đã trình bày như sau: Ta thấy rằng độ dài đoạn thẳng [P,Q] không lớn hơn 5000. Còn số đoạn thẳng trong tập đã cho có thể lên tới 100000. Ta không thể lưu tất cả các đoạn thẳng này lại được. Vậy chúng ta có thể lưu các đoạn thẳng này theo cách: lưu từng đoạn một, dùng một mảng A có độ dài chính bằng độ dài đoạn thẳng [P,Q], kích thước của mảng này là 5000x2 (A: Array [ 0..5000, 1..2 ] Of LongInt;) Ta coi đoạn [P,Q] là mảng A trên. Ta lần lượt đọc các đoạn thẳng của tập n các đoạn thẳng. Với mỗi đoạn thẳng vừa đọc được, ta xét xem chúng phủ đoạn [P,Q] bắt đầu từ đâu và độ dài mà đoạn thẳng đó phủ được. Ta sẽ lưu lại trên mảng A ở phần tử mà đoạn thẳng chúng ta vừa đọc bắt đầu phủ đoạn [P,Q] chỉ số của đoạn thẳng đó và độ dài chúng phủ được. A[Phần tử bắt đầu phủ,1] = chỉ số của đoạn vừa đọc và A[Phần tử bắt đầu phủ, 2] = độ dài mà đoạn đó phủ được. Nếu có nhiều đoạn thẳng bắt đầu phủ đoạn [P,Q] tại cùng một vị trí thì chọn đoạn nào có độ dài phủ được là lớn nhất. Sau khi làm xong công việc trên ta được một mảng gồm các đoạn thẳng phủ lên đoạn [P, Q]. Bây giờ ta sẽ tiến hành tìm xem số đoạn phủ ít nhất sẽ là bao nhiêu bằng cách: ta bắt đầu đi từ vị trí 0 (nếu tại vị trí này mà không có đoạn nào phủ thì sẽ không có lời giải) ta tìm xem có đoạn nào giao với đoạn này mà tạo thành một đoạn thẳng có phủ dài nhất thì ta lưu đoạn này lại (nếu không có đoạn thẳng nào giao với đoạn thẳng này để tạo được một đoạn thẳng có độ che phủ lớn hơn độ che phủ của đoạn trên thì sẽ không có lời giải). Làm tương tự với đoạn thẳng vừa tìm được cho đến khi các đoạn thẳng được chọn sẽ phủ kín đoạn [P, Q] ta sẽ được số đoạn thẳng ít nhất để phủ đoạn [P, Q]. Như vậy, thuật toán này cho phép giải quyết bài toán cũng chỉ với một lần duyệt mảng duy nhất. Dưới đây là chương trình minh hoạ: Const Fi = ′PHU.INP′; Fo = ′PHU.OUT′; Max = 5000; Dd = 2; Var n, P, Q, Min, Id : LongInt; A : Array [ 0..Max,1..2 ] Of LongInt; 11
C: Array[0..Max] Of LongInt; F : Text; Procedure InitData; Var i, L, R : LongInt; Begin Id:=1; Assign(F, Fi); Reset(F); Readln(F, n, P, Q); FillChar(A, SizeOf(A), 0); For i := 1 To n Do Begin Readln(F, L, R); If L Q then A[0, Dd] := Q - P else A[0, Dd] := R - P; End else else If L Q then A[L-P, Dd]:= Q-L else A[L-P, Dd]:= R - L; End; End; Close(F); End; Function tt(u,v:LongInt):LongInt; Begin If A[u, Dd]+u
End; Procedure solve; Var i, j, tmp, Count, Max:LongInt; Dung:Boolean; Begin Min:=0; If A[0, id]=0 then Exit; j:=0; Dung:=False; Count:=1; C[1]:=A[0, id]; If A[0, Dd] = Q-P then Begin Min:=1; Exit; End; While Not Dung Do Begin Max:=j+A[j, Dd]; For i:=j + 1 To j + A[j, Dd] Do If (A[i, id]0) And (tt(i, j)>Max) then Begin Max:=tt(i, j); tmp:=i; End; If Max=j+A[j, Dd] then Exit else Begin Count:=Count + 1; C[Count]:=A[tmp, id]; j :=tmp; If Max = Q - P Then Dung := True; End; End; Min := Count; 13
End; Procedure ReSult; Var i : LongInt; Begin Assign(F, FO); Rewrite(F); Writeln(F, Min); If Min 0 Then For i: = 1 To Min Do Writeln(F, C[i]); Close(F); End; BEGIN InitData; solve; ReSult; END. Tham khảo thêm: Trong Sáng tạo trong thuật toán và lập trình - tập 2 (Ebook) tác giả Đỗ Xuân Huy có giới thiệu thêm thuật toán giải bài toán này như sau: Bài 1.7 trang 21 - Phương pháp: Tham (độ phức tạp N2) * Sắp các đoạn tăng theo đầu phải R. * k : = 1; { chỉ số đầu tiên }; v := P; { Đầu trái của đoạn [P,Q] } * Lặp đến khi v >= Q - Duyệt ngược từ N đến k - Tìm đoạn j [Lj, Rj] đầu tiên có đầu trái Lj
* Có thể dùng thuật toán “Lùa bò vào chuồng” để giải quyết bài toán sau: 1. Bài 1: Dự tiệc Ông An đến dự một buổi tiệc. Buổi tiệc đã có N người (0 < N < 500.000). Mỗi người dự tiệc đều được cài lên áo một bông hoa trên đó có ghi một con số nguyên dương X bất kì ( X
2. Bài 2: Chuỗi kiểm tra Cho một file văn bản có n dòng (3 < n ≤ 30000), mỗi dòng là một chuỗi S có tối đa 255 kí tự, các kí tự S[i] ∈ [‘a’..’z’] với 1 ≤ i ≤ length(S). Trong đó, chỉ có một chuỗi S có số lần xuất hiện là một số lẻ, các chuỗi khác có số lần xuất hiện là số chẳn. Yêu cầu: Tìm chuỗi S (có số lần xuất hiện lẻ) đó. Dữ liệu vào: từ file ‘CHUOIKT.inp’ +Dòng đầu là một số nguyên n. + Dòng thứ i + 1 trong n dòng sau, mỗi dòng là một chuỗi kí tự (1 ≤ i ≤ n). Kết quả: ghi vào file ‘CHUOIKT.out’ chứa chuỗi kí tự tìm được. Ví dụ: CHUOIKT.INP CHUOIKT.OUT 7 lop10tin abcdef bbcc lop10tin abcdef bbcc abcdef abcdef 3. Bài 3: Tuyển nhân viên Công ty phần mềm máy tính A có số lượng nhân viên rất lớn. Để tiện việc quản lý, công ty đã cấp cho mỗi nhân viên một mã số, mã số của mỗi nhân viên là một số nguyên dương, hai nhân viên bất kỳ thì có mã số khác nhau. Tuy nhiên, sau một thời gian thì một số nhân viên đã nghỉ hưu hoặc chuyển công tác, nên công ty phải tiến hành tuyển thêm k nhân viên mới. Các nhân viên mới này sau khi được tuyển vào cũng sẽ được cấp mã số, mỗi nhân viên một mã số và mã số này cũng phải là một số nguyên dương. Yêu cầu: Với n nhân viên hiện có (còn lại) của công ty tương ứng với các mã số a1, a2, …, an. Hãy tìm k mã số nhỏ nhất để cấp cho k nhân viên mới tuyển vào sao cho vẫn thỏa mãn hai nhân viên bất kỳ (cả nhân viên cũ và nhân viên mới) có mã số khác nhau. 16
Dữ liệu vào: từ file ‘Recruit.inp’ có nội dung như sau: + Dòng đầu chứ hai số nguyên dương lần lượt là n và k (k ≤ n ≤ 106). + n dòng tiếp theo, dòng thứ i là số nguyên dương ai (i = 1, 2, …, n; ai≤ 2*109). Kết quả: ghi vào file ‘Recruit.out’ k mã số theo thứ tự từ nhỏ đến lớn (mỗi mã số trên một dòng). Ví dụ: RECRUIT.INP RECRUIT.OUT 53 2 3 4 1 5 6 9 8 Hướng dẫn: + Cách 1: Thuật toán O(NlogN) dùng quicksort đủ chấp nhận. + Cách 2: Dùng Sắp xếp phân phối (Distribution sort). Trong bài toán này, dãy chuồng chỉ cần đóng số hiệu từ 1 đến số hiệu 2*nmax (nmax = 106) và mỗi chuồng chỉ chứa 1 trong 2 trạng thái đã có hoặc chưa có (true, false). Bằng cách chạy từ 1 đến n, nếu số nào < n+k thì đánh dấu chuồng đó bằng true. Sau đó chạy từ 1 đến n+k, nếu số nào bằng false thì in số đó ra file (chỉ in đủ k số). 4. Bài 4: Xâu fibonacci. Định nghĩa: Dãy xâu fibo được xây dựng theo nguyên tắc sau: + F1 =’B’; F2 =’A’; + Fk = Fk-1 + Fk-2. Yêu cầu: Tính số lần xuất hiện của SR trong Fn (tức là số xâu con các kí tự liên tiếp nhau bằng SR). Hai xâu con được gọi là khác nhau nếu khác nhau ít nhất một ký tự.(N
Hướng dẫn Thuật toán: Với phương pháp này chỉ giải quyết với dữ liệu không lớn lắm (N
đề này nữa, các em đã hiểu và vận dụng khá tốt những phần liên quan đến việc đếm ứng dụng vào Tin học; một số em đã bước đầu sáng tạo được những cách giải hay, các giải mới (tuy là những bài toán còn “đơn giản”). Riêng bản thân tôi sẽ tiếp tục nghiên cứu sâu hơn nữa về chuyên đề này hy vọng sẽ “làm rõ hơn nữa” để các học sinh trong đội tuyển HSG Tin học thích học và đạt nhiều thành tích hơn nữa. Nếu biết vận dụng tốt những suy luận sẽ làm cho những bài toán tin có những giải thuật đơn giản và đạt được kết quả tốt hơn. Đặc biệt là trong công việc đếm, đòi hỏi phải lựa chọn cách giải quyết phù hợp cho các bài toán có đầu vào lớn. 19