Tài liệu Skkn rèn luyện kĩ năng, vận dụng và phát triển tư duy lập trình bằng cách phân tích, mở rộng các bài toán đơn giản

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NGHI LỘC 4 SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI “RÈN LUYỆN KĨ NĂNG, VÂN DỤNG VÀ PHÁT TRIỂN TƯ DUY LẬP TRÌNH BẰNG CÁCH PHÂN TÍCH VÀ MỞ RỘNG CÁC BÀI TOÁN ĐƠN GIẢN” Lĩnh vực: Tin Học Thực hiện:Trần Thị Thủy Chức vụ: Giáo viên Số điện thoại: 0848919111 Emai: [email protected] Nghệ An năm 2022 SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI “RÈN LUYỆN KĨ NĂNG, VÂN DỤNG VÀ PHÁT TRIỂN TƯ DUY LẬP TRÌNH BẰNG CÁCH PHÂN TÍCH VÀ MỞ RỘNG CÁC BÀI TOÁN ĐƠN GIẢN” Lĩnh vực: Tin Học Năm học: 2021 - 2022 2 MỤC LỤC PHẦN 1. MỞ ĐẦU ............................................................................................... 1 1. Lý do chọn đề tài ........................................................................................... 1 2. Mục đích nghiên cứu ..................................................................................... 1 3. Nhiệm vụ ....................................................................................................... 1 4. Đối tượng nghiên cứu .................................................................................... 2 5. Phương pháp nghiên cứu ............................................................................... 2 6. Phạm vi nghiên cứu ....................................................................................... 2 7. Những đóng góp mới của đề tài .................................................................... 2 PHẦN 2. NỘI DUNG NGHIÊN CỨU ................................................................ 3 1. Cơ sở lý luận .................................................................................................. 3 2. Cơ sở thực tiễn ............................................................................................... 3 3. Các biện pháp sử dụng để giải quyết vấn đề ................................................. 3 3.1. Chủ đề về số nguyên tố ........................................................................... 3 3.1.1. Khái niệm ......................................................................................... 3 3.1.2. Bài toán cơ bản................................................................................. 4 3.1.3. Bài toán nâng cao cấp độ 1 .............................................................. 4 3.1.4. Bài toán nâng cao cấp độ 2 .............................................................. 6 3.1.5. Đánh giá thuật toán .......................................................................... 7 3.1.6. Các bài toán giao về nhà .................................................................. 8 3.2. Chủ đề về dãy số ................................................................................... 12 3.2.1. Dãy Fibonaci .................................................................................. 12 3.2.2. Mảng một chiều ............................................................................. 14 3.2.3. Đánh giá các thuật toán .................................................................. 24 3.2.4. Bài tập về nhà ................................................................................. 26 3.3. Chủ đề về xâu ....................................................................................... 28 3.3.1. Bài toán cơ bản............................................................................... 28 3.3.2. Bài toán nâng cao cấp độ 1 ............................................................ 30 3.3.3. Bài toán nâng cao cấp độ 2 ............................................................ 35 3.3.4. Bài tập giao về nhà ......................................................................... 39 3.4. Đánh giá ................................................................................................ 41 4. Bài toán áp dụng .......................................................................................... 42 4.1. ƯỚC NGUYÊN TỐ ............................................................................. 42 4.2. SUBARR .............................................................................................. 42 4.3. QUÀ TẶNG .......................................................................................... 43 4.4. TỔ TÌNH NGUYỆN ............................................................................. 44 4.5. XÂU TƯƠNG ĐƯƠNG ....................................................................... 45 5. Kết quả đạt được .......................................................................................... 45 PHẦN 3. KẾT LUẬN VÀ KIẾN NGHỊ .......................................................... 48 1. Kết luận........................................................................................................ 48 2. Kiến nghị ..................................................................................................... 48 TÀI LIỆU THAM KHẢO ................................................................................. 50 DANH MỤC TỪ VIẾT TẮT VIẾT TẮT VIẾT ĐẦY ĐỦ THPT Trung học phổ thông HSG Học sinh giỏi SGK Sách giáo khoa NNLT Ngôn ngữ lập trình SKKN Sáng kiến kinh nghiệm PHẦN 1. MỞ ĐẦU 1. Lý do chọn đề tài Theo chương trình giáo dục phổ thông 2018 được Bộ Giáo dục và Đào tạo ban hành kèm Thông tư số 32/2018/TT-BGDĐT ngày 26/12/2018, môn tin học có triết lí cốt lõi tạo ra một thế hệ mới có tư duy áp dụng công nghệ trong giải quyết các vấn đề thực tế. Vì vậy, những kiến thức về phần giải thuật và lập trình đóng vai trò quan trọng trong chương trình tin học ở bậc Trung học phổ thông. Để rèn luyện kỹ năng lập trình cho học sinh khá, giỏi trước khi chọn đội tuyển đi thi HSG môn Tin học có rất nhiều cách mà giáo viên có thể áp dụng đối với các đối tượng học sinh khác nhau. Tuy nhiên trong cùng một trường với các đối tượng học sinh khác nhau giáo viên có thể áp dụng nhiều biện pháp khác nhau để rèn luyện kỹ năng lập trình cho học sinh với hiệu quả khác nhau. Trong quá trình dạy để chọn đội tuyển, bồi dưỡng học sinh giỏi Tỉnh nhiều năm liền tôi đã chọn lựa ra một số dạng bài toán từ SGK cơ bản và phát triển thêm thành các bài toán nâng cao để mở rộng phạm vi kiến thức giúp học sinh dần dần hình thành các kiến thức nâng cao. Trên cơ sở đó tôi đã mạnh dạn nghiên cứu và lựa chọn đề tài “Rèn luyện kĩ năng, vận dụng và phát triển tư duy lập trình bằng cách phân tích, mở rộng các bài toán đơn giản”. 2. Mục đích nghiên cứu Mục đích chính của sáng kiến là giới thiệu đến giáo viên và học sinh một số bài toán cơ bản, phân tích và mở rộng các bài toán đó để học sinh dần hình thành các kiến thức nâng cao: - Phát triển tư duy lập trình, giúp các em học giỏi môn Tin Học đạt kết quả cao. - Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT. mới. - Sử dụng NNLT C++ và Python trong chương trình giáo dục phổ thông 3. Nhiệm vụ Đề tài có nhiệm vụ giải đáp các câu hỏi khoa học sau đây: - Học sinh có giải quyết được các bài toán đơn giản. - Giáo viên mở rộng các bài toán đó như thế nào cho phù hợp với năng lực học sinh. - Những tình huống nào thường gặp trong quá trình dạy học theo phương pháp này. - Học sinh gặp những khó khăn nào trong quá trình dạy học theo phương 1 pháp này. - Các kỹ năng học sinh đạt được nhờ phương pháp dạy học này. - Kết quả thực nghiệm như thế nào. 4. Đối tượng nghiên cứu - Học sinh tham gia bồi dưỡng học sinh giỏi Tin học. - Hệ thống các bài tập từ cơ bản đến nâng cao theo từng chủ đề. 5. Phương pháp nghiên cứu - Phương pháp điều tra, nghiên cứu tài liệu. Phương pháp phân tích, tổng hợp. Phương pháp khảo sát thực tiễn. Phương pháp tổng kết kinh nghiệm. 6. Phạm vi nghiên cứu Hệ thống lại các bài tập từ đơn giản đến mức độ tăng dần bằng việc mở rộng các bài toán đó giúp đạt hiệu quả cao trong quá trình chọn đội tuyển và bồi dưỡng học sinh giỏi môn Tin học. 7. Những đóng góp mới của đề tài - Qua một số năm làm công tác dạy học và bồi dưỡng học sinh giỏi môn tin học tôi thấy dạy học theo phương pháp này học sinh hứng thú học hơn, chất lượng học sinh được tăng lên đáng kể, nhiều học sinh sau khi học theo phương pháp này đã tự giải quyết được các bài toán khó trong các đề thi cấp tỉnh, tin học không chuyên... - Đề tài sẽ làm phong phú hơn các phương pháp day học môn tin học tại các trường trung học phổ thông hiện nay. 2 PHẦN 2. NỘI DUNG NGHIÊN CỨU 1. Cơ sở lý luận Xây dựng hệ thống các bài tập theo các chủ để chính, mỗi chủ đề có thể chia thành một hoặc nhiều buổi dạy tuỳ vào từng đối tượng học sinh của mình. Hệ thống các bài tập của mỗi chủ đề theo các mức độ từ cơ bản đến mức độ khó tăng dần tuy nhiên hệ thống bài tập phải liên quan và phải vận dụng được các bài tập cơ bản để giải quyết các bài toán khó hơn. Cụ thể mỗi chủ đề được thực hiện theo các bước: Bước 1: Giới thiệu lí thuyết cơ bản của chủ đề Bước 2: Chọn bài toán cơ bản hoặc bài toán quen thuộc với học sinh để học sinh lập trình (thường là các bài toán trong sách giáo khoa). Bước 3: Mở rộng bài toán nâng cao ở cấp độ 1 (chỉ cần học sinh lập trình được mà chưa cần quan tâm đến các yếu tố như: quan tâm đến các yếu tố đặc biệt của dữ liệu vào, thời gian, phạm vi giá trị của biến…) Bước 4: Mở rộng bài toán nâng cao ở cấp độ 2 (quan tâm đến các yếu tố như: các trường hợp đặc biệt của dữ liệu vào, phạm vi giá trị của các biến, thời gian…) Bước 5: Thực hiện chấm các chương trình bằng phần mềm Themis với cùng một bộ test để so sánh thời gian thực hiện của các thuật toán với cùng một bài toán. Bước 6: Phân tích và nhận xét sự tối ưu của thuật toán Bước 7: Mở rộng bài toán để học sinh rèn luyện kỹ năng lập trình và vận dụng các bài tập ở nhà. Thường là những bài toán tương đương đề học sinh giỏi cấp Tỉnh. 2. Cơ sở thực tiễn Nhiều học sinh có suy nghĩ môn lập trình rất khó và không phải là môn thi tốt nghiệp, đại học nên các em ít lựa chọn tham gia đội tuyển chọn HSG Tỉnh Qua công tác dạy học nhiều năm tại trường tôi thấy đa số học sinh đều gặp không ít khó khăn trong việc xác định thuật toán để giải một bài toán. Việc giải các bài toán cơ bản trong sách giáo khoa các em có thể giải quyết được tuy nhiên vận dụng để giải các bài toán khó hơn lại gặp rất nhiều khó khăn. Nhiều giáo viên đang lúng túng trong việc chọn học sinh có kĩ năng và tư duy lập trình để bồi dưỡng thêm. 3. Các biện pháp sử dụng để giải quyết vấn đề 3.1. Chủ đề về số nguyên tố 3.1.1. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. 3 3.1.2. Bài toán cơ bản Bài toán: Viết chương trình nhập vào từ bàn phím số nguyên N, Kiểm tra và thông báo ra màn hình N là số nguyên tố hoặc N không là số nguyên tố. Nhận xét: Đây là bái toán cơ bản mà học sinh đã được làm quen ở bài 4: Bài toán và thuật toán lớp 10. Học sinh có thể vận dụng khái niệm của số nguyên tố để đưa ra các thuật toán. Tuy nhiên cách được giới thiệu trong SGK Tin học 10 là tối ưu nhất. Chương trình cụ thể như sau: C++ Python #include import math #include def check_prime_number(n): using namespace std; flag = 1; bool check(int n) { if (n<2): if (n <= 1) return false; for (int i = 2; i <= round(sqrt(n)); i++) if (n % i == 0) return false; return true; } flag = 0 return flag for p in range(2,round(math.sqrt(n))): if n % p == 0: flag = 0 break int main() { return flag int n; n = int(input(">>nhap n: ")) cout<<"nhap n="; if check_prime_number(n) == 1: cin>>n; print(n," la so nt") if (check (n)) cout< import math #include def ktnt(n): #include if (n<2): using namespace std; return False; bool KT(int n) x=int(math.sqrt(n)) { for i in range(2,x+1): bool kt=true; for (int i=2;i<=round(sqrt(n));i++) if (n%i==0) kt=false; return (kt); } if n % i == 0: return False return True n = int(input(">>nhap n: ")) dem=0; if (n>=2): int main() { dem=1; for i in range(3,n+1): ifstream fi("demnt.inp"); int n;int dem=0; fi>>n; ofstream fo("demnt.out"); if (ktnt(i)): dem=dem+1; i=i+2; print(dem) for (int i=2;i<=n;i++) if (KT(i)) dem++; fo< Python def sieve(n): #include prime = [True for i in range(n+1)] #include p=2 using namespace std; while (p*p<=n): int main() { if (prime[p] == True): for i in range(p **2, n + 1, p): ifstream fi("demnt.inp"); ofstream fo("demnt.out"); prime[i] = False p += 1 int n; prime[0] = False fi>>n; prime[1] = False bool check[n+1] = {}; for p in range(n+1): for(int i=2;i <= round(sqrt(n));i ++ ) { if prime[p]: print(p) if(check[i]==0) { n = int(input(">>nhap n = ")) print(sieve(n)) for(int j = 2*i;j <= n; j += i) { 6 check[j] = 1; } } } int dem=0; for(int i=2;i<=n;i ++) { if(check[i]==0) dem++; } fo< using namespace std; int main(){ Python n = int(input("Nhập số cần phân tích: ")) a=n int n; i=2 cout << "\nNhap n = "; while a != 1: cin >> n; int dem; for(int i = 2; i <= n; i++){ dem = 0; while(n % i == 0){ ++dem; if a % i == 0: print("%5d chr(9474), i)) %c %2d" % (a, a = a/i else: i = i+1 print("%5d %c" % (1, chr(9474))) n /= i; } if(dem){ cout << i; if(dem > 1) cout << "^" << dem; if(n > i){ cout << " * "; } } } } 8 3.1.6.2. Số nguyên tố tương đương Bài toán: Hai số gọi là nguyên tố tương đương nếu chúng có cùng các ước số nguyên tố. Ví dụ 15 và 75 là các số nguyên tố tương đương. Bởi vì 15=3*5 trong khi 75=3*5^2, có cùng ước số nguyên tố là 3 và 5. Tương tự 12=2^2*3 và 18=2*3^2 là hai số nguyên tố tương dương vì có cùng hai ước số nguyên tố là 2 và 3. Tuy nhiên 12 và 60 ko nguyên tố tương đương vì 12=2^2*3 và 60=2^2*3*5, 60 có ước số nguyên tố 5 trong khi 12 không có. Cho trước hai số tự nhiên M và N. Hãy viết chương trình kiểm tra các số này có là nguyên tố tương đương với nhau không? Cài đặt thuật toán: C++ Python #include import sys #include def SNT(n): using namespace std; kt=True typedef int Mang[1001]; if n<=1: kt=True int m,n,dem,d; else: Mang a,b; t=int(n/2) bool SNT(int n) for i in range(2,t+1): { if n%i==0: bool kt=true; kt=False if (n<=1) kt=false; break else return kt for (inti=2;i<=round(sqrt(n));i++) def NTTD (m,n): if (n % i==0) d=[] { for j in range(2,n+1): kt=false; if SNT(j) and (n%j==0): break; } return kt; } d.append(j) dem=[] for k in range(2,m+1): if SNT(k) and (m%k==0): bool NTTD (int m,int n) { dem.append(k) s=0 bool kttd; d=0; if len(d)==len(dem): for i in range(0,len(d)): 9 for (int j=2;j<=n;j++) if d[i]==dem[i]: s=s+1 if (SNT(j) && (n % j==0)) if s==len(d): kttd=True else: kttd=False { return kttd d++; m=int(input("< Python def isPrime(n): #include if n<2: return False #include for i in range(2,n//2+1): using namespace std; bool isPrime(int n){ if n % i == 0: return False return True if (n<2) return false; n=int(input("Nhập n=")) for (int i=2; i<=sqrt(n); i++) q=[] if (n%i==0) return false; for i in range(2,10): return true; } if isPrime(i): q.append(i) while len(q)!=0: int main(){ queue q; int n; cout<<"Nhap n="; for i in range(1,10): k=q[0]*10+i if (k<=n) q.append(k) cin >> n; print(q[0]," ") for (int i = 2;i<10; i++){ q.pop(0) and (isPrime(k)): if (isPrime(i)){ q.push(i); } } while (!q.empty()){ for (int i = 1; i <= 9; i++){ 11 int k = q.front()*10 + i; if ( k <= n && isPrime(k)){ q.push(q.front()*10 + i); } } cout << q.front() << "\n"; q.pop(); } return 0; } 3.2. Chủ đề về dãy số 3.2.1. Dãy Fibonaci 3.2.1.1. Khái niệm dãy Fibonaci Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là: Nếu n=1 hoặc n=2 thì F(n)=1 Nếu n>2 thì F(n) = F(n-1) + F(n-2) 3.2.1.2. Bài toán cơ bản Bài toán: Dãy F là dãy Fi-bô-na-xi nếu: F1 =1;F2 =1;Fn=Fn-1 +Fn-2 với n>=2 Viết chương trình nhập từ bàn phím số nguyên dương n và đưa ra màn hình số hạng thứ n của dãy Fi-bô-na-ci. Nhận xét: Bài toán này học sinh sẽ thực hiện được sau khi học nội dung mảng 1 chiều và thường sử dụng kĩ thuật đệ quy. Cài đặt chương trình: C++ #include #include using namespace std; int fibo(int n) { Python def Fibo(n): if n == 1 or n == 2: return 1 return Fibo(n-1)+Fibo(n-2) n=int(input(">>nhap n= ")) 12 if ((n==1 || n==2)) print(Fibo(n)) return 1; return (fibo(n-1)+fibo(n-2)); } int main() { int n; cout<<"n="; cin>>n; cout<=2 Viết chương trình nhập từ bàn phím số nguyên dương n và đưa ra màn hình số hạng thứ n của dãy Fi-bô-na-ci. Nhận xét: Khi sử dụng bộ test lớn thì thuật toán sử dụng đệ quy không đảm bảo thời gian cho phép (1s/test). Vì vậy, giáo viên hướng dẫn học sinh sử dụng phương pháp quy hoạch động. Cài đặt thuật toán: C++ #include #include using namespace std; int fibo(int n) { Python def Fibo(n,memo): if n==1 or n==2: return 1 if not memo[n]==None: return memo[n] int a[100]; a[0]=a[1]=1; for (int i=2;i<=n;i++) a[i]=a[i-1]+a[i-2]; return a[n]; result = Fibo(n-1,memo)+ Fibo(n2,memo) memo[n]=result return result def F(n): 13 } memo=[None]*(n+1) return Fibo(n,memo) int main() { n=int(input("<>n; gt=int(input()) ds.append(gt) for (int i=0;i a=[6,5,3,1,8,7,2,4] using namespace std; lap=range(len(a)-1,-1,-1) int a[100001]; for i in lap: int n,tg; int main() for j in range(0,i,1): if a[j]>a[j+1]: { tg=a[j] cout<<"Nhap phan tu mang n="; cin>>n; a[j]=a[j+1] for (int i=0;i<=n-1;i++) a[j+1]=tg print(a) { cout<<"a["< - Xem thêm -