Sáng kiến kinh nghiệm THPT: Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi

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

Thêm vào BST

Báo xấu

24
lượt xem 7
download

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

Mục đích chính của sáng kiến "Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi" là giới thiệu đến giáo viên và học sinh một số kỹ thuật cơ bản dành cho đối tượng HSG khối THPT: 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.

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: Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT DIỄN CHÂU 5 SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI MỘT SỐ KỸ THUẬT LẬP TRÌNH CƠ BẢN GIÚP ĐẠT HIỆU QUẢ CAO TRONG BỒI DƯỠNG HỌC SINH GIỎI Lĩnh vực: Tin học Nhóm người thực hiện: Nguyễn Thị Luận – Trường THPT Diễn Châu 5 Số điện thoại : 0989868255 Email: nguyenluan.dc5@gmail.com Trần Thị Thủy – Trường THPT Nghi Lộc 4 Số điện thoại : 0848919111 Email: tttpdl@gmail.com Năm thực hiện : 2022 NGHỆ AN, NĂM 2022
1. MỞ ĐẦU 1.1. Lý do cho ̣n đề tài Chúng ta biết rằng để có kết quả cao trong kì thi tuyển chọn học sinh giỏi môn Tin học nói chung thì phải có vốn kiến thức tốt về thuật toán để giải được các bài toán khó, sau đó học sinh lựa chọn NNLT để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo yêu cầu. Điều này lại chỉ được hình thành sau khi người học được tiếp xúc với một hệ thống các bài toán được tổ chức cẩn thận, chặt chẽ. Hệ thống này giúp xây dựng được các thói quen tư duy cơ bản cũng như các kỹ thuật cơ bản trong lập trình. Với mong muốn giúp các em giải các bài toán trong Tin học theo hướng tối ưu nhất, qua quá trình bồi dưỡng học sinh giỏi, chúng tôi đã phát hiện, rút ra được một số kỹ thuật cơ bản, rất quan trọng giúp đạt hiệu quả cao trong bồi dưỡng kiến thức, kỹ năng lập trình cho học sinh. Mặt khác, theo chương trình mới của Bộ giáo dục khuyến khích giáo viên dạy NNLT mới thay Pascal nên chúng tôi viết chương trình bằng NNLT C++ và Python để làm tài liệu tham khảo mới cho giáo viên và học sinh. Từ những lý do trên chúng tôi đã mạnh dạn trình bày sáng kiến kinh nghiê ̣m: “Một số kỹ thuật lập trình cơ bản giúp đạt hiệu quả cao trong bồi dưỡng học sinh giỏi”. 1.2. Mu ̣c đí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ố kỹ thuật cơ bản dành cho đối tượng HSG khối THPT: - 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 - Sử dụng NNLT C++ và Python trong chương trình giáo dục phổ thông 2018 sắp tới. 1.3. Đố i tươ ̣ng nghiên cứu - Giáo viên và học sinh tham gia bồi dưỡng HSG Tin học. - Tổng hợp lại một số kỹ thuật giúp học sinh phát triển tư duy lập trình thông qua hệ thống các bài tập được phân loại kỹ lưỡng. 1.4. Phương phá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. 1.5. Phạm vi nghiên cứu Phạm vi nghiên cứu: Một số kỹ thuật cơ bản để tăng tốc chương trình giúp đạt hiệu quả cao trong bồi dưỡng HSG môn Tin học. 1
2. NỘI DUNG NGHIÊN CỨU 2.1. Cơ sở lý luâ ̣n Trong quá trình ôn luyện đội tuyển, học sinh được dạy khá nhiều về các phương pháp tối ưu thuật toán như: phương pháp tham lam, chia để trị (sắp xếp nhanh, chặt nhị phân…), quay lui, quy hoạch động, Z Algorithm, KMP… Nhưng nếu không biết kết hợp với những kỹ thuật khác, không biết cách tổ chức dữ liệu, những phương pháp này xét về phương diện độc lập sẽ không đạt được sự tối ưu cao nhất và không có ý nghĩa. Các kỹ thuật được giới thiệu trong sáng kiến đều là những kỹ thuật rất cơ bản, đơn giản và rất dễ tiếp cận đồng thời đem lại một hiệu quả rất đáng kể trong việc giảm độ phức tạp thuật toán, tiến tới một thuật toán tối ưu nhất. Học sinh dần được làm quen với NNLT C++ hoặc Python. 2.2. Thực trạng Trên thực tế đã có một số tài liệu đề cập đến những kỹ thuật để tăng tốc chương trình, tuy nhiên chưa đi sâu vào phân tích cách tư duy, cách lựa chọn và cài đặt chương trình tối ưu, đặc biệt việc tổng hợp lại các kỹ thuật giúp học sinh có thể so sánh các cách giải, các kết quả, độ phức tạp còn rất ít, hệ thống bài tập cũng không nhiều. 2.3. Các kĩ thuật lập trình cơ bản 2.3.1. Kỹ thuật lính canh (Sentinel) - Là kĩ thuật sử dụng 1 biến (mang giá trị đặc biệt) làm “chốt chặn”. - Mục đích chính: tạo điều kiện dừng cho các vòng lặp không xác định số lần lặp. - Xét một số bài toán cụ thể sau: 2.3.1.1. Bài toán 1 – Tìm max / min Cho dãy gồm N số nguyên a1, a2,…,aN. Hãy tìm giá trị lớn nhất của dãy số. a. Ý tưởng của thuật toán - Xét bài toán tìm kiếm giá trị lớn nhất trong một mảng số, đặt biến kết quả max bằng giá trị đầu tiên trong mảng (biến này gọi là biến lính canh), xét lần lượt phần tử thứ 2 đến n, nếu có một phần tử nào lớn hơn “lính canh” ban đầu thì thực hiện đổi “lính canh”: + Khởi tạo max=a1; + Lần lượt với i=2 đến n, so sánh số ai với max, nếu ai > max thì gán max=ai. 2
b. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật: Bước 1: Nhập N và dãy a1, a2, ..., aN. Bước 2: Max ← a1, csmax←1, i ←2; Bước 3: Nếu i > N thì đưa ra giá trị Max và csmax rồi kết thúc; Bước 4: Nếu ai > Max thì Max ←ai, csmax ←i; Bước 5: i ← i + 1 rồi quay lại Bước 3; Cài đặt chương trình: C++ Python #include import sys #include fi=open("max.inp",encoding="utf-8") using namespace std; fo=open("max.out","w",encoding="utf- long long n,max,csmax; 8") long long a[10000]; sys.stdin=fi void doctep() sys.stdout=fo {ifstream fi ("max.inp"); # đọc dữ liệu từ tệp fi>>n; n=int(input()) for (int i=0;i>a[i]; # Đổi các phần tử sang kiểu số nguyên fi.close(); for i in range(n): } ds[i]=int(ds[i]) void maxday() fi.close() { # tìm phần tử lớn nhất long long max=a[0];//dat linh canh lonnhat=ds[0] # khai báo lính canh, gán giá trị ban đầu cho biến csmax=0; csmax=0 for(int i=1;i
fo
a[n] = k; // gán lính canh vào cuối mảng for (i=0; ; i++) { if (a[i] == k) { Cs=i+1; break; } } Như vậy, mỗi vòng lặp for đã giảm được 1 câu lệnh kiểm tra i
fi>>n>>k; //dữ liệu vào: k = int(a[1]) dòng đầu lưu hai số nguyên n và k ds = str.split((input())) for (i=0;i>a[i]; # đổi các phần tử sang kiểu số nguyên fi.close(); n = len(ds) } for i in range (n): int main() ds[i] = int (ds[i]) { fi.close() doctep(); # tìm kiếm phần tử có giá trị = k ofstream fo ("tk.out"); for i in range(n): a[n]=k;//đặt lính canh vào cuối mảng if ds[i]==k: for (i=0;;i++) cs = i { break if (a[i]==k) if i==n-1: { print(-1) cs=i; else: Break; print (cs) } fo.close() } if (i==n) fo
2.3.2. Kỹ thuật đặt cờ hiệu (Flag) - Là kĩ thuật sử dụng 1 biến (mang giá trị đúng/ sai) làm “dấu hiệu” đánh dấu trạng thái. - Mục đích chính: Kiểm tra một tính chất nào đó. - Xét một số bài toán cụ thể như sau: 2.3.2.1. Bài toán 1 - Kiểm tra tính chất một số Cho số nguyên dương N. Hãy cho biết N có phải là số nguyên tố hay không? a. Ý tưởng của thuật toán - Ta dùng biến kt có kiểu logic (true, false) để đặt cờ hiệu, ban đầu ta đặt cho lá cờ này một giá trị mặc định là true. - Kiểm tra, nếu N 1 thì ta sẽ kiểm tra xem N có ước nào thuộc đoạn [2; N/2] hay không? Trong lúc kiểm tra nếu thấy có ước thì cập nhật lại giá trị cờ hiệu (kt=false) rồi dừng kiểm tra. - Cuối cùng, kiểm tra: nếu kt=true thì thông báo N là số nguyên tố, ngược lại thì N không phải nguyên tố. b. Nội dung và cài đặt chương trình Các bước thực hiện giải thuật: B1. Nhập số nguyên dương N; B2. kt ← true; B3. Nếu N = 1 thì kt ← false rồi chuyển đến bước 8; B3. i ←2; B4. Nếu i > [N/2] thì chuyển đến bước 8; B6. Nếu N chia hết cho i thì kt ← false rồi chuyển đến bước 8;; B7. i ← i + 1 rồi quay lại bước 4; B8. Nếu kt= true thì thông báo N là số nguyên tố rồi kết thúc; B9. Nếu kt=false thì thông báo N không nguyên tố rồi kết thúc. Cài đặt chương trình: C++ Python #include import sys #include fi=open("snt.inp",encoding="utf-8") using namespace std; fo=open("snt.out","w",encoding="utf- long long n; 8") 7
bool kt; sys.stdin=fi void doctep() sys.stdout=fo { #đọc dữ liệu từ tệp ifstream fi ("snt.inp"); n=int(input()) fi>>n; kt=True # Đánh dấu cờ hiệu fi.close(); if n
2.3.2.2. Bài toán 2 - Kiểm tra tính chất mảng Cho dãy gồm N số nguyên a1, a2,…, aN. Hãy cho biết dãy trên có phải là dãy tăng dần/giảm dần hay không? Lưu ý: Dãy tăng dần là dãy có phần tử đứng sau phải lớn hơn mọi phần tử đúng trước nó. a. Ý tưởng của thuật toán - Ta dùng biến kt có kiểu logic (true, false) để đặt cờ hiệu, ban đầu ta đặt cho lá cờ này một giá trị mặc định là true. - Lần lượt so sánh 2 phần tử liền kề nhau trong dãy: + Nếu thấy có 2 phần tử liền kề nhau mà số hạng trước không nhỏ hơn số hạng sau (tức ai >=ai+1) thì cập nhật lại giá trị cờ hiệu (tức kt=false) rồi kết thúc công việc so sánh. - Cuối cùng, chỉ cần kiểm tra giá trị cờ hiệu: + Nếu kt=true thì dãy có tính chất tăng dần + Nếu kt=false thì dãy không có tính chất tăng dần. b. Cài đặt chương trình: C++ Python #include import sys #include fi = open("td.inp",encoding="utf-8") using namespace std; fo=open("td.out","w",encoding="utf- const long long maxn=50000; 8") long long n,a[maxn]; sys.stdin = fi bool kt; sys.stdout = fo void doctep() # Đọc dữ liệu từ tệp { n = int(input()) ifstream fi ("td.inp"); ds = str.split((input())) fi>>n; # Đổi các phần tử sang kiểu số nguyên for(int i=0;i++;i>a[i]; ds[i] = int(ds[i]) fi.close(); # Hàm kiểm tra mảng tăng dần } def kttd(ds): bool kiemtra() kt = True for i in range(n-2): 9
{ if ds[i]>=ds[i+1]: kt=true;//danh dau co hieu kt = False for(int i=0;i=a[i+1]) return kt { if kttd(ds): print("yes") kt=false;//thay doi co hieu else: print("no") break; fi.close() } fo.close() return kt; } void ghitep() { ofstream fo ("td.out"); if (kiemtra()) fo
2.3.3.1. Bài toán 1 - Tìm dãy Fibonaci Dãy số Fibonaci được định nghĩa như sau: F(0)= 1, F(1) = 1, F(n) = F(n-1) + F(n-2) với n>= 2. Cho N, viết chương trình tìm N phần tử Finonaci đầu tiên a. Ý tưởng thuật toán: Ta dùng một mảng (hoặc danh sách) để lưu các giá trị đã tính F(i) với 0≤ i ≤ n. b. Cài đặt chương trình C++ Python #include import sys #include # Đọc dữ liệu vào và ghi kết quả using namespace std; fi=open("fibonaci.inp","r",encoding="utf- const long long maxn=50000; 8") long long n,i,a[maxn]; fo=open("fibonaci.out","w",encoding="utf- 8") void doctep() sys.stdin = fi { sys.stdout = fo ifstream fi ("fibonaci.inp"); n = int(input()) fi>>n; # dùng danh sách a để ghi nhớ dãy fi.close(); fibonaci } a=[1,1] void xuli() for i in range(2,n): { a.append(a[i-1]+a[i-2]) a[0]=1;a[1]=1; # ghi kết quả vào tệp for (i=2;i
int main() { doctep(); xuli(); ghitep(); return 0; } 2.3.3.2. Bài toán 2 -Tính tổng Cho số nguyên dương N. Tính tổng S=1!+2!+3!+4!+…+N! với N≥1. a. Ý tưởng của thuật toán: Ta nhận thấy: a1 = 1! = 1 a2 = 2! = 1! * 2 = a1 * 2 a3 = 3! = 2! * 3 = a2 * 3 ………………………… aN = N!= (N-1)! * N= aN-1 * N Ta có công thức truy hồi: ai = i! = (i-1)! * i = ai-1 * i với 0
fi>>n; n vào danh sách mảng fi.close(); a = [] } a.append(1) void xuli() for i in range (1,n): { x = a[i-1]*(i+1) a[0]=1;tong=0; a.append (x) for (i=1;i
2.3.4. Kỹ thuật đệ quy - Trong lập trình, một hàm được gọi là đệ quy nếu bên trong thân hàm có một lời gọi đến chính nó. Hàm đệ quy luôn có điều kiện dừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa. - Cú pháp: Kiểu_trả_về Tên_hàm (Các_tham_số) { Điều_kiện_dừng; return Tên_hàm (Các_tham_số_mới) ; // hoặc một biểu thức có chứa lời gọi hàm. } - Xét một số bài toán cụ thể như sau: 2.3.4.1. Bài toán 1 - Giai thừa Cho n là một số tự nhiên (n>=0). Hãy tính giai thừa của n (n!) biết rằng 0! = 1 và n! = (n-1)! * n. a. Ý tưởng thuật toán Theo giả thiết, ta có : n! = (n-1)! * n. Như vậy : Để tính n! ta cần phải tính (n-1)! Để tính (n-1)! ta phải tính (n-2)! … Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác. b. Cài đặt chương trình: C++ Python #include import sys int n; def GiaiThua(n): using namespace std; if n==0: return 1 long GiaiThua(int n) return n*GiaiThua(n-1) { fi=open("giaithua.inp","r",encoding if (n == 0) = "utf-8") { fo=open("giaithua.out","w",encoding = "utf-8") return 1; // điều kiện dừng sys.stdin=fi 14
} sys.stdout=fo return n * GiaiThua(n - 1); // gọi đệ quy n = int(input()) } print(GiaiThua(n)) int main() fi.close() { fo.close() cout >n; cout
if (n == 0) if n==1: return 1 return 0; // điều kiện dừng return fibonaci(n-1)+fibonaci(n- if (n == 1) 2) return 1; // điều kiện dừng # Đọc dữ liệu vào và ghi kết quả return fibonacci(n - 1)+ fibonacci(n- 2); fi= open("fibonaci.inp","r",encoding = "utf-8") } fo=open("fibonaci.out","w", int main() encoding = "utf-8") { sys.stdin=fi for (int count =0; count < 15; ++count) sys.stdout=fo cout
int BSCNN(int a, int b) a = int (input ("Nhập a =")) { b = int (input ("Nhập b =")) return (a * b) / USCLN(a, b); print ("UCLN =",USCLN (a,b)) } print ("BCNN =", BSCLN (a,b)) int main() { coutx; couty; cout
Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho danh sách đã có thứ tự hay đã được sắp xếp. a. Ý tưởng thuật toán Các bước thực hiện giải thuật: B1: Gán Left←0; Right ← n-1. B2: Gán mid ← (Left+Right)/2 Nếu a[mid]==x thì dừng lại và trả về giá trị của mid (chính là vị trí của x trong mảng a. Nếu a[mid]>x thì Right ← mid-1 Nếu a[mid]x: return { BinarySearch(a,l,mid-1,x) if (r>=l) return BinarySearch(a,mid+1,r,x) { return -1 int mid=l+(r-l)/2; fi=open("NPSearch.inp",encoding="utf if (arr[mid]==x) -8") return mid; fo=open("NPSearch.out","w",encoding ="utf-8") if (arr[mid]>x) sys.stdin=fi return BinarySearch(arr,l,mid-1,x); return BinarySearch(arr,mid+1,r,x); sys.stdout=fo 18
} n=int(input()) return -1; a=str.split((input())) } for i in range(n): int main() a[i]=int(a[i]) { x=int(input()) clock_t begin=clock(); result=BinarySearch(a,0,n-1,x) ifstream fi("NPSearch.inp"); if result==-1: print("khong co") ofstream fo("NPSearch.out"); else: print(result) fi>>n; end_time = datetime.now() for (int i=0;i>arr[i]; start_time),"s") fi>>x; fi.close() int result=BinarySearch(arr,0,n- fo.close() 1,x); if (result==-1) fo