Sáng kiến kinh nghiệm Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

Nội dung tóm tắt: Sáng kiến kinh nghiệm Rèn kĩ năng lập trình cho học sinh giỏi thông qua khai thác tư duy một số thuật toán

1. 20 sức mạnh không thể giập vùi, tình yêu ấy đã giúp bao anh lính bộ đội cụ Hồ đã chắc tay súng để bảo vệ tổ quốc và có niền tin vào một ngày mai đất nước độc lập thống nhất, tình yêu bị kìm nén ấy sẽ lại bùng cháy và thăng hoa cùng dân tộc. Những con người đấy phần đông là thanh niên, khi đó tại các trường đại học khi có lệnh tổng động viên nhiều sinh viên cả nam nữ gác bút nghiên đi theo tiếng gọi của lịch sử. Trường đại học hồi đó quản lý sinh viên bằng mã sinh viên, hai sinh viên khác nhau sẽ có 2 mã khác nhau. Trong khi học tập các cặp nam nữ sinh viên đã nảy sinh những tình cảm đẹp giành cho nhau. Các cặp nam nữ sinh viên nói trên ghi lại mã sinh viên của nhau trước khi lên đường nhập ngũ để ngày giải phóng họ dễ tìm lại nhau trong trường đại học. Năm 1975, khi chiến tranh kết thúc, đất nước hoàn toàn giải phóng, những sinh viên năm nào người đã ngã xuống trên mặt trận, một số may mắn còn lại và có điều kiện quay về trường tiếp tục học tập. Biết rằng có n sinh viên nam và m sinh viên nữ đã trở về trường. n sinh viên nam, trong hoàn cảnh chiến tranh khốc liệt, họ đã để thất lạc mã số của những người sinh viên nữ và chỉ nhớ được mã sinh viên của chính họ: b1, b2, b3, bn; m sinh viên nữ vẫn giữ lại được mã sinh viên của mình: g1, g2, g3, .,gm và của các sinh viên nam mà họ đã dành tình cảm thời sinh viên trước đó: y1, y2, y3, .,ym (gi giữ yi). Cặp sinh viên bi và gj sẽ tìm được nhau nếu yj = bi. Yêu cầu: Em hãy thống kê xem có bao nhiêu cặp sinh viên nam nữ trong số trên có thể tìm được nhau và chỉ ra các cặp sinh viên đó. Dữ liệu vào: tệp LIW.INP gồm: - Dòng 1: n m - Dòng 2: mã sinh viên nam b1, b2, b3, bn - Dòng 3: mã sinh viên nữ g1, g2, g3, .,gm - Dòng 4: mã các sinh viên nam mà sinh viên nữ đã dành tình cảm thời sinh viên trước đó: y1, y2, y3, .,ym (gi giữ yi). Dữ liệu ra: tệp LIW.OUT gồm:
2. 21 - Dòng 1: Số cặp sinh viên nam nữ tìm được nhau. - Các dòng tiếp theo là các cặp mã sinh viên nam nữ tìm được nhau, mã sinh viên nữ được sắp tăng dần (gj1 < gj2 < LIW.INP LIW.OUT <gjk). 4 5 3 4 Giới hạn: 1 <= n, m <= 10 . 1 <= 8 6 2 4 4 1 16 bi, gi, yi <= 10 1 7 5 3 11 2 7 4 2 10 12 6 6 11 Bài 4: Trung điểm – Đề thi HSG tỉnh Bắc Giang năm 2018 - 2019 Trên trục tọa độ Ox, cho N điểm khác nhau P1, P2, ., PN. Điểm Pi được gọi là trung điểm của đoạn PjPk nếu 2Pi = Pj + Pk Yêu cầu: Cho biết tọa độ của N điểm P1, P2, ., PN. Hỏi có bao nhiêu điểm là điểm trung bình của các đoạn thẳng tạo ra từ các điểm đã cho? Dữ liệu: vào từ tệp văn bản TDD.INP gồm: - Dòng 1: Ghi số nguyên dương N 5 - Dòng 2: Ghi lần lượt các số x1, , xN (|xi| ≤ 10 ) tương ứng là tọa độ của các điểm P1, P2, ., PN Kết quả: Ghi ra tệp văn bản TDD.OUT gồm một số duy nhất là kết quả tìm được của bài toán. Ví dụ: TDD.INP TDD.OUT Giải thích 5 3 Đoạn 1: 5 -1, trung điểm 2 3 -1 2 5 4 Đoạn 2: 2 4, trung điểm 3 Đoạn 3: 3 5, trung điểm 4
3. 22 2. Sắp xếp nhanh (QUICKSORT) 2.1. Ý tưởng: Sắp xếp dãy khoá k[1 n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới chỉ số n trong dãy khoá đó. Để sắp xếp một đoạn trong dãy khoá, nếu đoạn đó có ít hơn 2 khoá thì không cần phải làm gì cả, còn nếu đoạn đó có ít nhất 2 khoá, ta chọn một khoá ngẫu nhiên nào đó của đoạn làm "chốt" (Pivot). Mọi khoá nhỏ hơn khoá chốt được xếp vào vị trí đứng trước chốt, mọi khoá lớn hơn khoá chốt được xếp vào vị trí đứng sau chốt. Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm hai đoạn khác rỗng mà mọi khoá trong đoạn đầu đều ≤ chốt và mọi khoá trong đoạn sau đều ≥ chốt. Hay nói cách khác: Mỗi khoá trong đoạn đầu đều ≤ mọi khoá trong đoạn sau. Và vấn đề trở thành sắp xếp hai đoạn mới tạo ra (có độ dài ngắn hơn đoạn ban đầu) bằng phương pháp tương tự. 2.2. Cài đặt: procedure QuickSort; procedure Partition(L, H: Integer); {Sắp xếp dãy khoá k[L H]} var i, j: Integer; Pivot: TKey; {Biến lưu giá trị khoá chốt} begin if L ≥ H then Exit; {Nếu đoạn chỉ có ≤ 1 khoá thì không phải làm gì cả} Pivot := k[Random(H - L + 1) + L]; {Chọn một khoá ngẫu nhiên trong đoạn làm khoá chốt} i := L; j := H; {i := vị trí đầu đoạn; j := vị trí cuối đoạn} repeat while k[i] Pivot do j := j - 1; {Tìm từ cuối đoạn khoá ≤ khoá chốt} + 1; {Tìm từ đầu đoạn khoá ≥ khoá chốt} {Đến đây ta tìm được hai khoá k[i] và k[j] mà k[i] ≥ key ≥ k[j]}
4. 23 if i ≤ j then begin if i j; end; Partition(L, j); Partition(i, H); {Sắp xếp hai đoạn con mới tạo ra} begin Partition(1, n); end; 3. Quay lui: (BACKTRACKING). 3.1. Quay lui dùng để giải bài toán liệt kê các phương án. Mỗi phương án được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Giả sử phương án cần liệt kê có dạng x[1 n], khi đó thuật toán quay lui thực hiện qua các bước: Bước 1: Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[1] ta sẽ: Bước 2: Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] cứ tiếp tục như vậy đến bước: Bước n: Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báo phương án tìm được .
5. 24 Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các phương án n phần tử dạng x[1 n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp phương án n - 1 phần tử x[2 n]. 3.2. Mô hình của thuật toán quay lui: procedure Try(i: Integer); begin for do begin ; if then else begin ; Try(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]} ; end; end; end; Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)
6. 25 3.3. Ví dụ: Ví dụ 1: Liệt kê các dãy nhị phân độ dài N Biểu diễn dãy nhị phân độ dài N dưới dạng x[1 n]. Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị {0, 1} gán cho x[i]. Với mỗi giá trị thử gán cho x[i] lại thử các giá trị có thể gán cho x[i+1].Chương trình liệt kê bằng thuật toán quay lui có thể viết: program BinaryStrings; const InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 30; var x: array[1 max] of Integer; n: Integer; f: Text; procedure PrintResult; {In phương án tìm được} var i: Integer; begin for i := 1 to n do Write(f, x[i]); WriteLn(f); end; procedure Try(i: Integer); {Thử các cách chọn x[i]} var j: Integer; begin for j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó} begin
7. 26 x[i] := j; {Thử đặt x[i]} if i = n then PrintResult {Nếu i = n thì in kết quả} else Try(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x[i+1]} end; end; BEGIN Assign(f, InputFile); Reset(f); ReadLn(f, n); {Nhập dữ liệu} Close(f); Assign(f, OutputFile); Rewrite(f); Try(1); {Thử các cách chọn giá trị x[1]} Close(f); END. Vẽ cây ví dụ
8. 27 3.4. Bài tập vận dụng: Bài 1:Bài toán cái túi (Câu 3 đề thi cấp tỉnh V1 năm 2011-2012) Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có n đồ vật cần đem theo. Đồ vật thứ j có trọng lượng là aj và giá trị sử dụng là cj (j = 1, 2, 3, ,n). Hỏi rằng nhà thám hiểm cần đem theo các đồ vật nào để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất? Input: Vào từ file văn bản CAITUI.INP: • Dòng đầu ghi 2 số nguyên dương n và b (n < 100). • Dòng thứ hai ghi các số nguyên không âm a1, a2, ,an. • Dòng thứ ba ghi các số nguyên không âm c1, c2, ,cn. Output: Ghi ra file CAITUI.OUT: • Dòng đầu ghi tổng giá trị các đồ vật đem theo ứng với phương án tìm được. • Ghi chỉ số của các đồ vật đem theo CAITUI.INP CAITUI.OUT 4 8 15 5 3 2 4 1 2 10 5 3 6 4. Quy hoạch động. (DYNAMIC PROGRAMMING) 4.1. Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. 4.2. Các bước cài đặt một chương trình sử dụng quy hoạch động: + Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng phương án.
9. 28 + Dùng công thức truy hồi phối hợp những lời giải của những bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải. + Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu. 4.3. Ví dụ Ví dụ 1: Bài toán Tính N! GT.PAS 1 n = 0 Ta có định nghĩa như sau: n! = nếu nn*( 1 )!− n 0 Cho một số nguyên dương n (0 n 13). Yêu cầu: Hãy tính n! bằng phương pháp quy hoạch động (lập bảng phương án). Dữ liệu vào: Ghi trong file văn bản GT.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương n. Dữ liệu ra: Ghi ra file văn bản GT.OUT theo cấu trúc như sau: - Dòng 1: Ghi giá trị tính được của n! Ví dụ: GT.INP GT.OUT 3 6 Thuật toán: Gọi GT[i] là giá trị của i! (0 i 13) Ta có công thức quy hoạch động như sau: GT[i] := GT[i-1]*i; Như vậy, việc tính n! sẽ được thực hiện bằng vòng lặp: GT[0] :=1; For i:=1 to n do
10. 29 GT[i] := GT[i-1]*i; Kết quả: giá trị của n! nằm trong phần tử GT[n]. Ví dụ 2: Dãy con đơn điệu: Bài toán: Cho dãy số nguyên A = a1, a2, , an. (n ≤ 1000, -10000 ≤ ai ≤ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. Đặc trưng: Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử A[i] trong dãy, các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị. Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Công thức quy hoạch động: Hàm mục tiêu: f : độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là mảng một chiều. Gọi Li là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ A1 đến Ai và phần tử cuối cùng là Ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính Li như sau: L[n+1] = 1. (Hiển nhiên) Li = L[jmax] + 1 với mọi phần tử j thỏa mãn: 0 < j < i và Aj ≤ Ai Tính Li: phần tử đang được xét là Ai. Ta tìm đến phần tử Aj < Ai có Lj lớn nhất. Khi đó nếu bổ sung Ai vào đầu dãy con Aj ta sẽ được dãy con tăng dần dài nhất xét từ A1 Ai.
11. 30 Truy vết: Tại bước xây dựng dãy L, mỗi khi tính L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại Ai sẽ có phần tử thứ hai kế tiếp là Ajmax. Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0. T[0] là phần tử đầu tiên được chọn, T[T[0]] là phần tử thứ hai được chọn, T[T[T[0]]] là phần tử thứ ba được chọn Quá trình truy vết có thể diễn tả như sau: i := T[0]; while i i := T[i]; end; Cài đặt : Ví dụ: với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8). Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ Li và mảng giá trị T sử dụng để lưu trữ vị trí của các phần tử trong dãy con.
12. 31 i 0 1 2 3 4 5 6 7 8 9 10 11 ai -∞ 5 2 3 4 9 10 5 6 7 8 +∞ L[i] 9 5 8 7 6 3 2 5 4 3 2 1 T[i] 2 8 3 4 7 6 11 8 9 10 11 Truy vết Cài đặt: Const max:=1000; Var a, L, T: array [1 max+1] of longint; N: longint; Procedure nhapdl; { Nhap du lieu cho mang A} Procedure QHD_daycondondieu; Var I, j, jmax: longint; Begin A[0] := -32768; A[n+1] := 32767; L[n+1] := 1; For i:= n downto 0 do Begin Jmax:= n+1; For j:= i+1 to n+1 do If (A[j]>A[i]) and (L[j]> L[jmax]) then jmax:= j; L[i] := L[jmax] + 1; T[i] := jmax; End;
13. 32 Writeln(‘Chieu dai cua day con la: ’, L[0] - 2); {Truy vet tim va hien thi day con} i:= T[0]; while i <> n+1 do begin write (A[i]); i:= T[i]; end; End; BEGIN Nhapdl; QHD_daycondondieu; END. Như vậy độ phức tạp bộ nhớ của bài toán là O(n), độ phức tạp thời gian là O(n2). Có một số phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn), một trong những cách đó là dùng cây nhị phân. 4.4. Bài tập vận dụng: Bài 1: Cho hai số nguyên dương M, N (0 ≤ M, N ≤ 100) và hai dãy số nguyên: A1, A2, , AM và B1, B2, , B N. Tìm một dãy dài nhất C là dãy con chung dài nhất của hai dãy A và B, nhận được từ A bằng cách xoá đi một số số hạng và cũng nhận được từ B bằng cách xoá đi một số số hạng. Dữ liệu vào trong file LCS.INP có dạng: + Dòng thứ nhất chứa M số A1, A2, , AM + Dòng thứ hai chứa N số B1, B2, , B N. Dữ liệu ra trong file LCS.OUT có dạng: + Dòng thứ nhất ghi số k là số số hạng của dãy C.
14. 33 + Dòng thứ hai chứa k số là các số hạng của dãy C. Hướng dẫn: Công thức QHĐ Cần xây dựng mảng L[0 M, 0 N] với ý nghĩa: L[i, j] là độ dài của dãy chung dài nhất của hai dãy A[0 i] và B[0 j]. Đương nhiên nếu một dãy là rỗng (số phần tử là 0) thì dãy con chung cũng là rỗng vì vậy L[0, j] = 0 với j = 1 N, L[i, 0] = 0 với i = 1 M. Với M ≥ i > 0 và N ≥ j > 0 thì L[i, j] được tính theo công thức truy hồi sau: L[i,j] = Max{L[i, j-1], L[i-1, j], L[i-1, j-1] + x} (với x = 0 nếu A[i] ≠ B[j] , x=1 nếu A[i]=B[j]) Bài 2: Biến đổi xâu: Cho xâu ký tự X, xét 3 phép biến đổi: a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X. b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C. c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X. Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y. Input: file văn bản STR.INP - Dòng 1: Chứa xâu X (độ dài ≤ 100) - Dòng 2: Chứa xâu Y (độ dài ≤ 100) Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.
15. 34 STR.INP STR.OUT PBBCEFATZ 7 QABCDABEFA PBBCEFATZ -> Delete(9) -> PBBCEFAT PBBCEFAT -> Delete(8) -> PBBCEFA PBBCEFA -> Insert(4, B) -> PBBCBEFA PBBCBEFA -> Insert(4, A) -> PBBCABEFA PBBCABEFA -> Insert(4, D) -> PBBCDABEFA PBBCDABEFA -> Replace(2, A) -> PABCDABEFA PABCDABEFA -> Replace(1, Q) -> QABCDABEFA Hướng dẫn: Công thức QHĐ: Hàm mục tiêu: f: số phép biến đổi. Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét của xâu F. Do vậy để cài đặt cho bảng phương án ta sẽ dùng mảng 2 chiều. Gọi L[i,j] là số phép biến đổi ít nhất để biến xâu Xi gồm i kí tự phần đầu của X (Xi=X[1 i]) thành xâu Fj gồm j kí tự phần đầu của F (Fj=F[1 j]). Công thức QHĐ: L[0,j]=j L[i,0]=i L[i,j] =L[i−1,j−1] nếu Xi=Yj. L[i,j] = min(L[i−1,j], L[i,j−1], L[i-1,j-1]) +1 nếu Xi≠Fj.
16. 35 Bài 3: Xâu con chung dài nhất: Cho 2 xâu X, Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất. Biết xâu con của một xâu thu được khi xóa một số kí tự thuộc xâu đó (hoặc không xóa kí tự nào). Hướng dẫn: Công thức QHĐ: Gọi L[i,j] là độ dài xâu con chung dài nhất của xâu Xi gồm i kí tự phần đầu của X(Xi=X[1 i]) và xâu Yj gồm j kí tự phần đầu của Y (Yj=Y[1 j]). Ta có công thức quy hoạch động như sau: L[0,j] = L[i,0] = 0 L[i,j] = L[i−1,j−1] + 1 nếu Xi=Yj L[i,j] = max(L[i−1,j], L[i,j−1]) nếu Xi≠Yj. Bài 4: Xâu đối xứng (Palindome): Bài toán: Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Hướng dẫn: Công thức QHĐ: Gọi L[i,j] là số kí tự ít nhất cần thêm vào xâu con S[i j] của S để xâu đó trở thành đối xứng. Đáp số của bài toán sẽ là L[1,n] với n là số kí tự của S. Ta có công thức sau để tính L[i,j]: L[i,i]=0. L[i,j]=L[i+1,j−1] nếu Si=Sj L[i,j]=max(L[i+1,j],L[i,j−1]) nếu Si≠Sj
17. 36 PHỤ LỤC II THIẾT KẾ BÀI GIẢNG ÔN LUYỆN ĐỘI TUYỂN CHỦ ĐỀ / BÀI HỌC: THUẬT TOÁN TÌM GIÁ TRỊ LỚN NHẤT CỦA DÃY SỐ. Chủ đề gồm nội dung: - Nội dung 1: Thuật toán tìm Max. - Nội dung 2: Bài tập vận dụng. I. MỤC TIÊU BÀI HỌC Sau khi học chủ đề, học sinh cần: - Biết cách viết thuật toán tìm giá trị lớn nhất của một dãy số. - Biết đánh giá độ phức tạp thuật toán từ đó lựa chọn ra thuật toán tối ưu tương ứng với từng bài toán. - Biết vận dụng thuật toán vào giải quyết các bài toán trong thực tế và ở một số các môn học: Toán, Lý, - Phát triển tư duy logic và bước đầu hình thành kĩ năng giải quyết vấn đề cho học sinh. - Bước đầu có cảm hứng và đam mê lập trình. II. ĐỒ DÙNG DẠY HỌC - Máy tính. - Tài liệu: Sách giáo khoa tin học 10, cấu trúc dữ liệu và giải thuật. - Phiếu học tập. III. CÁC HOẠT ĐỘNG DẠY HỌC 1. Khởi động - Mục đích: Tạo hứng thú cho học sinh trong việc tìm hiểu kiến thức.
18. 37 - Phương pháp tiến hành: Giáo viên giao nhiệm vụ cho học sinh về nhà đọc và tìm hiểu thuật toán tìm giá trị lớn nhất của dãy số với các nội dung: + Xác định bài toán. + Ý tưởng giải quyết bài toán. + Viết thuật toán. + Đánh giá độ phức tạp thuật toán. - Định hướng kết quả: Học sinh hệ thống và nắm được thuật toán cơ bản tìm giá trị lớn nhất trong chương trình lớp 10. b. Hoạt động ôn tập - Mục đích: Kiểm tra việc thực hiện nhiệm vụ của học sinh trong phần khởi động. - Phương thức tiến hành: Yêu cầu học sinh hoàn thành phiếu học tập. - Định hướng sản phẩm: Nội dung Tìm giá trị lớn nhất của dãy số Xác định - Input: Số nguyên dương N và dãy N số nguyên a1, , aN. bài toán - Output: Giá trị lớn nhất Max của dãy số. Ý tưởng - Khởi tạo Max = a1 giải quyết - Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với Max, nếu bài toán ai > Max thì Max nhận giá trị mới là ai. Thuật toán Liệt kê : Bước 1. Nhập N và dãy a1, , aN; Bước 2. Max := a1, i := 2; Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4. Bước 4.1. Nếu ai > Max thì Max := ai;
19. 38 Bước 4.2. i := i + 1 rồi quay lại bước 3; Sơ đồ khối Độ phức - Độ phức tạp thuật toán là O(N) tạp thuật toán.
20. 39 c. Luyện tập vận dụng và cũng cố - Mục đích: + Giúp học sinh củng cố kiến thức về thuật toán tìm giá trị lớn nhất và vận dung thuật toán đó giải quyết các bài toán khác. + Giúp học sinh đưa ra được ý tưởng tối ưu ( Sử dụng thuật toán sắp xếp). - Phương thúc tiến hành: Giáo viên tổ chức cho học sinh làm bài tập vận dung: Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên. Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị nhỏ nhất của dãy. Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị nhỏ nhất của dãy là 1 Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên. Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị lớn thứ nhì của dãy. Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 thì giá trị lớn thứ nhì của dãy là 8 Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên. Dãy A gồm N số nguyên a1, a2, , aN (N<= 100). Viết thuật toán đưa ra giá trị lớn thứ k của dãy (k nguyên dương có giá trị được nhập vào từ bàn phím) Ví dụ: Dãy A: 1, 5, 8,10, 7, 4, 2 với k = 2 thì giá trị lớn thứ 2 của dãy là 8
21. 40 MỘT SỐ HÌNH ẢNH SẢN PHẨM CỦA HỌC SINH Thuật toán tìm Max và đếm số lượng số có giá trị bằng Max
22. 41 Bài 1: Tìm giá trị nhỏ nhất của một dãy số nguyên. Bài 3: Tìm giá trị lớn thứ k của một dãy số nguyên.
23. 42 Bài 2: Tìm giá trị lớn thứ nhì của một dãy số nguyên.
24. 43 MỘT SỐ PHIẾU HỌC TẬP ÁP DỤNG TRONG QUÁ TRÌNH GIẢNG DẠY
25. 45 TÀI LIỆU THAM KHẢO 1. Giải thuật và lập trình - Lê Minh Hoàng - ĐHSP Hà Nội. 2. Tài liệu chuyên Tin Học quyển 1 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục. 3. Sách giáo khoa Tin Học 10 - Hồ Sĩ Đàm (Chủ biên ) - NXB Giáo Dục. 4. Trang 5. Chuyên đề “Quy hoạch động” - Nguyễn Thanh Tùng - ĐHSP Hà Nội. 6. Quy hoạch động - Nhóm tác giả Trường THPT chuyên Bắc Giang. 7. Đề thi học sinh giỏi văn hóa cấp tỉnh Tin Học 11 từ năm 2018 đến 2021.
26. 46 MỤC LỤC Trang 1. Tên sáng kiến 2 2. Ngày sáng kiến được áp dụng 2 3. Các thông tin bảo mật 2 4. Mô tả giải pháp cũ thường làm 2 5. Sự cần thiết phải áp dụng giải pháp sáng kiến 3 6. Mục đích của giải pháp 4 7. Nội dung 4 7.1 Thuyết minh giải pháp mới hoặc cải tiến 4 - Tên giải pháp 4 - Nội dung 4 7.1.1 Thuật toán 4 7.1.2 Áp dụng thuật toán vào giải quyết các bài toán 8 - Các bước tiến hành thực hiện giải pháp 8 - Kết quả khi thực hiện giải pháp 8 + Sản phẩm được tạo ra từ giải pháp 8 + Các bảng số liệu, biểu đồ so sánh 8 7.2 Thuyết minh về phạm vi áp dụng sáng kiến 10 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến 10 Phụ lục I 11 Phụ lục II 36