Sáng kiến kinh nghiệm Hệ thống giải bài trực tuyến nhập môn Lập trình với C++

Nội dung tóm tắt: Sáng kiến kinh nghiệm Hệ thống giải bài trực tuyến nhập môn Lập trình với C++

1. Algorithm with C++ } a/=10; } cout sing namespace std; #include #define ll long long #define fo(i,a,b) for(int i=a;i >n; cout<<f[n]; } Bài 10.11 – (N1011E) Định đề Bertrand Yêu cầu: Định đề Bertrand phát biểu rằng với bất kỳ số nguyên , luôn tồn tại ít nhất một số nguyên tố sao cho . Cho , đếm số lƣợng số nguyên tố thuộc đoạn . 123
2. Algorithm with C++ #include #define ll long long #define maxx 2000010 using namespace std; ll n,a[maxx],t; bool NT[maxx]; void SNT() { for (ll i=1;i >t; while(t ) { cin>>n; cout #define fo(i,a,b) for(int i=a;i<=b;i++) #define ll long long using namespace std; ll nt(ll n) { fo(i,2,sqrt(n)) if(n%i==0) return false; 124
3. Algorithm with C++ return true; } ll n,a[105],b[105],c[105],t=4,k=0; int main() { cin>>n; a[1]=2,a[2]=3,a[3]=5,a[4]=7; b[1]=1,b[2]=3,b[3]=7,b[4]=9; n ; while(n ) { fo(i,1,t) fo(j,1,4) if(nt(a[i]*10+b[j])) c[++k]=a[i]*10+b[j]; fo(i,1,k) a[i]=c[i]; t=k;k=0; } cout using namespace std; long long n,s=0,i=1; int main() { cin>>n; while(i<=n) { long long t=n/i; s+=(n/t-i+1)*t; 125
4. Algorithm with C++ i=n/t+1; } cout<<s; } 126
5. Algorithm with C++ CHƢƠNG 11 – ĐỆ QUY A. KIẾN THỨC GHI NHỚ 1. Khái niệm đệ quy Chƣơng trình con đệ quy là các chƣơng trình con có lời gọi nó trong chính chƣơng trình của nó. Điều này có thể hơi khác lạ với phƣơng thức lập trình logic tuần tự nhƣng đây lại là một điểm mạnh của các ngôn ngữ lập trình với việc quản lý ngăn xếp chƣơng trình con để cất ngữ cảnh hiện tại và tiếp tục giải bài toán ở mức nhỏ hơn cho đến khi gặp trƣờng hợp nhỏ nhất. Chƣơng trình con đệ quy có ƣu thế khi giải quyết các bài toán có dạng công thức truy hồi, các bài toán về chia để trị, các bài toán quay lui vét cạn. Một chƣơng trình đệ quy thƣờng có cấu trúc nhƣ sau: (danh sách tham số) { if(trường hợp dừng đệ quy) return ; else return (tham số cấp nhỏ hơn); } Ta chú ý rằng chƣơng trình con đệ quy phải có hai phần rõ rệt. Một là phần trƣờng hợp dừng – trƣờng hợp nhỏ nhất của bài toán, không có phần trƣờng hợp dừng này hoàn toàn chƣơng trình sẽ lặp tới mức tràn ngăn xếp chƣơng trình con. Hai là trƣờng hợp gọi đệ quy, trƣờng hợp này sẽ đƣa bài toán đang giải về bài toán cùng dạng với cấp độ nhỏ hơn. Khi có lời gọi đệ quy, trình biên dịch sẽ liên tục cất ngữ cảnh vào bộ nhớ ngăn xếp chƣơng trình con cho tới trƣờng hợp dừng sẽ lại quay trở lại lấy giá trị các biến trong ngăn xếp chƣơng trình con để tính ngƣợc lên lời gọi đầu tiên. Vì vậy khi gọi đệ quy chúng ta lƣu ý không để lời gọi quá sâu để dẫn tới việc tràn bộ nhớ ngăn xếp chƣơng trình con. 2. Ví dụ minh họa Ta xét một ví dụ mở đầu về đệ quy nhƣ sau: Tính #include using namespace std; long long gt(long long n){ if(n==0) return 1;// Trường hợp dừng else return n*gt(n-1);//Lời gọi đệ quy cấp thấp hơn } int main() 127
6. Algorithm with C++ { long long n; cin>>n; cout<<gt(n); } Với chƣơng trình trên khi nhập bằng ta có một sơ đồ đệ quy nhƣ sau: Chú ý rằng trong chƣơng trình con đệ quy dứt khoát phải có trƣờng hợp dừng, khi đó mới thoát ra khỏi vòng lặp đệ quy. Câu lệnh đệ quy thƣờng ngắn gọn, súc tích, gần với bản chất toán học của bài toán. Tuy nhiên việc gọi đệ quy quá sâu sẽ phải cất ngữ cảnh quá nhiều dẫn tới tràn ngăn xếp chƣơng trình con. Mỗi trình biên dịch ngôn ngữ thƣờng đƣợc cấp một dung lƣợng nhất định cho ngăn xếp chƣơng trình con, ta cũng có thể mở rộng trong phạm vi cho phép, tuy nhiên nó sẽ phụ thuộc nhiều vào bộ nhớ trên máy tính. Thực tế, với việc tính n! theo cách viết đệ quy không đem lại ƣu thế. Vì vậy đây chỉ là một ví dụ mô tả cho đệ quy mà thôi, chúng ta ít sử dụng nó trực tiếp trong tính toán nhƣ trên. 3. Một số ứng dụng của đệ quy Đệ quy có nhiều ứng dụng trong lập trình. Một trong những ứng dụng thƣờng gặp là chia để trị và liệt kê tổ hợp. Cấu trúc của các giải thuật chia để trị đƣa việc giải quyết bài toán về giải nhiều bài toán cùng dạng nhƣng có cấp thấp hơn theo mô hình cây và sử dụng đƣợc lời giải ở cấp thấp hơn để độ phức tạp bài Bài toán cấp n Bài toán Bài toán cấp n-1 cấp n-1 Bài toán Bài toán Bài toán cấp n-2 cấp n-2 cấp n-2 toán giảm xuống: Điển hình cho dạng toán này đƣợc mô tả trong Ví dụ 11.1 128
7. Algorithm with C++ Ngoài ra để liệt kê các cấu hình tổ hợp thì cấu trúc đệ quy quay lui rất thuận tiện cho việc liệt kê này. Ta có mô hình liệt kê tổ hợp nhƣ sau: void Try (int i)//Xây dựng thành phần thứ i { ; for(xi thuộc Si) { if (tìm thấy nghiệm) ; else Try(i+1); ; } } Trong đó Si là tập hợp các giá trị mà xi có thể nhận đƣợc với xi là thành phần thứ i của cấu hình ta cần xây dựng. Ta xem xét ví dụ minh họa cho dạng toán này trong Ví dụ 11.2 B. CÁC VÍ DỤ MẪU Ví dụ 11.1: Xét chƣơng trình tính bằng chia để trị với độ phức tạp . #include #define mod 1000000007 #define ll long long using namespace std; ll mu(ll a, ll n) // tính a^n%mod bằng đệ quy chia để trị { if(n==0) return 1; ll tam = mu(a,n/2); tam = (tam*tam)%mod; if(n%2==1) tam = (tam*a)%mod; return tam; } int main() { long long a,n; cin>>a>>n; cout<<mu(a,n); // độ phức tạp thuật toán là O(logn) } Chú ý rằng nếu chúng ta sử dụng vòng lặp for để tính a n thì độ phức tạp của giải thuật sẽ là – chỉ có thể giải đƣợc cho n cỡ 1068 10 trong thời gian giây. 129
8. Algorithm with C++ Ví dụ 11.2: Ta xét ví dụ liệt kê dãy nhị phân có độ dài n nhƣ sau: #include #define ll long long using namespace std; int x[30],n; void Xuat() { for(int k=1;k >n; Try(1); } Lời gọi đệ quy vét cạn thƣờng bắt đầu với nghĩa là xây dựng thành phần thứ nhất của i. Ví dụ 11.3: Chƣơng trình sau sẽ liệt kê ra các hoán vị của tập Xn 1,2, , . Ta biết khi xây dựng hoán vị thì các thành phần xây dựng không đƣợc phép lặp lại. Vì vậy ta phải sử dụng một mảng đánh dấu d[] để đánh dấu cho các giá trị đã đƣợc chọn để không chọn lại. Đoạn chƣơng trình liệt kê hoán vị nhƣ sau: 130
9. Algorithm with C++ #include #define ll long long #define fo(i,a,b) for(int i=a;i >n; Try(1); } Bên cạnh phƣơng pháp này kể từ phiên bản C14, ta có hàm next_permutation() để sinh hoán vị kế tiếp, đây là một cách code khá gọn gàng nhƣ sau: #include using namespace std; long long n,a[30]; int main() { cin>>n; for(int i=1;i<=n;i++) a[i]=i; do { for(int i=1;i<=n;i++) cout<<a[i]; cout<<'\n'; 131
10. Algorithm with C++ } while(next_permutation(a+1,a+n+1)); } C. BÀI TẬP ÁP DỤNG Bài 11.1 – (N1101A) Số tập con Yêu cầu: Hãy đếm số tập hợp con của tập Xn 1,2, . Dữ liệu: Một dòng ghi số nguyên không âm nn(0 109 ). Kết quả: In ra số các tập con của tập X . Kết quả có thể rất lớn nên ta sẽ chia lấy dƣ cho 109 7 khi in ra. Ví dụ: input output 3 8 Bài 11.2 – (N1102A) Liệt kê nhị phân Yêu cầu: Hãy in ra các dãy nhị phân độ dài n Input: Một dòng ghi số nguyên nn(0 20) Output: In ra các dãy nhị phân theo thứ tự từ điển. Ví dụ: input output 2 00 01 10 11 Bài 11.3 – (N1103A) Liệt kê tam phân Yêu cầu: Dãy tam phân là dãy chỉ gồm các ký tự 0, 1, 2 dùng để biển diễn các số trong hệ cơ số 3. Ví dụ ta có các dãy tam phân độ dài 2 là: 00, 01, 02, 10, 11, 12, 20, 21, 22. Hãy liệt kê theo thứ tự từ điển các dãy tam phân độ dài n . Dữ liệu: Một dòng ghi số nguyên không âm nn(0 10) . Kết quả: In ra các dãy tam phân theo thứ tự từ điển. Ví dụ: input output 2 00 01 02 10 11 132
11. Algorithm with C++ 12 20 21 22 Bài 11.4 – (N1104B) Liệt kê chỉnh hợp Yêu cầu: Trong toán học, chỉnh hợp là cách chọn những phần tử từ một nhóm lớn hơn và có phân biệt thứ tự, trái với tổ hợp là không phân biệt thứ tự. Theo định nghĩa, chỉnh hợp chập k của n phần tử là bộ sắp thứ tự gồm phần tử của tập hợp gồm n phần tử. Hãy liệt kê các chỉnh hợp chập k của n phần tử của Xn 1,2, ,  Dữ liệu nhập: Một dòng một gồm k, n 1 k n 8 . Kết quả: Mỗi dòng in một chỉnh hợp chập của n , các chỉnh hợp in theo thứ tự từ điển. Ví dụ: input output 2 3 1 2 1 3 2 1 2 3 3 1 3 2 Bài 11.5 – (N1105C) Liệt kê chỉnh hợp tập A Yêu cầu: Trong bài tập này bạn đƣợc cho một tập hợp A gồm phần tử số nguyên khác nhau. Bạn hãy liệt kê các chỉnh hợp không lặp chập của phần tử này. Dữ liệu nhập: - Dòng một gồm . - Dòng hai là phần tử của tập A. Kết quả: - Mỗi dòng in một chỉnh hợp chập của , các chỉnh hợp in theo thứ tự từ điển. - Dòng cuối cùng in số lƣợng chỉnh hợp liệt kê đƣợc. Ví dụ: input output 2 3 1 4 1 9 4 1 9 133
12. Algorithm with C++ 4 1 4 9 9 1 9 4 6 Bài 11.6 – (N1106B) Liệt kê tổ hợp Yêu cầu: Trong toán học, tổ hợp chập k của n là cách chọn tập con gồm k phần tử trong tập có n phần tử. Ở đây, bạn đƣợc yêu cầu in ra tất cả các tổ hợp chập của tập Xn 1,2, , . Dữ liệu: Một dòng một gồm k, n 1 k n 8 . Kết quả: - Mỗi dòng in một tổ hợp chập k của theo thứ tự từ điển. - Dòng cuối cùng in số lƣợng tổ hợp liệt kê đƣợc. Ví dụ: input output 2 3 1 2 1 3 2 3 3 Bài 11.7 – (N1107C) Liệt kê tổ hợp tập A Yêu cầu: Hãy in ra các tổ hợp chập của tập số nguyên A gồm n phần tử. Dữ liệu: - Dòng đầu tiên một gồm hai số nguyên . - Dòng tiếp theo gồm n số nguyên trong tập A. Kết quả: - Mỗi dòng in một tổ hợp chập của theo thứ tự từ điển. - Dòng cuối cùng in số lƣợng tổ hợp liệt kê đƣợc. Ví dụ: input output 2 3 1 4 1 9 4 1 9 4 9 3 134
13. Algorithm with C++ Bài 11.8 – (N1108B) Liệt kê xâu ký tự AB Yêu cầu: Hãy liệt kê các xâu độ dài n chỉ gồm hai kí tự ′A′ hoặc ′B′ mà không có hai kí tự ′B′ nào đứng cạnh nhau. Dữ liệu: Một dòng ghi số nguyên nn 20 . Kết quả: In ra các xâu ký tự theo thứ tự từ điển. Ví dụ: input output 3 AAA AAB ABA BAA BAB Bài 11.9 – (N1109D) Liệt kê xâu hợp lệ Yêu cầu: Hãy liệt kê các cách đặt n dấu mở ngoặc và dấu đóng ngoặc sao cho biểu thức đó hợp lệ. Dữ liệu: Một dòng ghi số nguyên . Kết quả: In ra các xâu ký tự theo thứ tự từ điển. Ví dụ: input output 3 AAA AAB ABA BAA BAB Bài 11.10 – (N1110E) Liệt kê xâu con Yêu cầu: Hãy liệt kê tất cả các xâu con khác nhau của xâu S. Dữ liệu: Một dòng ghi xâu S S. length 15 gồm các ký tự từ a đến z. Kết quả: In ra các xâu con khác nhau của S theo thứ tự từ điển. Ví dụ: input output abc a ab abc ac b bc c 135
14. Algorithm with C++ Bài 11.11– (N1111D) Số mũ 1 Yêu cầu: Cho hai số nguyên a, n. Tính an % 109 7 . Dữ liệu: Một dòng ghi hai số nguyên a, n 0 a , n 109 . Kết quả: In ra kết quả là tổng . Ví dụ: input output 2 3 8 Bài 11.12 – (N1112E) Số mũ 2 Yêu cầu: Cho số nguyên n, K tính S 1.20 2.2 1 n .2n 1 % K . Dữ liệu: Một dòng ghi hai số nguyên n,K 0 n , K 109 . Kết quả: In ra kết quả là tổng S . Ví dụ: input output 1 10 1 Bài 11.13 – (N1113E) Số mũ 3 Yêu cầu: Cho số nguyên n, tính S 1 a12 a an . Kết quả có thể rất lớn nên chia lấy dƣ cho 109 7 khi in ra. Dữ liệu: Một dòng ghi hai số nguyên a, n 0 a , n 109 . Kết quả: In ra kết quả là tổng S% 109 7 . Ví dụ: input output 2 9 1023 Bài 11.14 – (N1114E) Quân hậu Yêu cầu: Cho bàn cờ vua có kích cỡ . Hãy tìm cách xếp quân hậu trên bàn cờ sao cho các quân hậu không ăn đƣợc nhau. Dữ liệu: Một dòng ghi một số nguyên dƣơng Kết quả: In ra kết quả là số cách sắp xếp quân hậu trên bàn cờ. Ví dụ: input output 8 92 136
15. Algorithm with C++ D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP Bài 11.4 – (N1104B) Liệt kê chỉnh hợp #include #define ll long long #define fo(i,a,b) for(int i=a;i >k>>n; fo(i,1,n) cin>>t[i]; sort(t+1,t+1+n); qlui(1); cout #define ll long long #define fo(i,a,b) for(int i=a;i<=b;i++) #define nmax 10000005 using namespace std; ll n,k,a[30],b[30],t[30],dem=0; ll Try(ll x) { 137
16. Algorithm with C++ fo(i,1,n) if(N[i]==0) { a[x]=i; b[i]=1; if(x==k) { fo(j,1,k) cout >k>>n; fo(i,1,n) cin>>t[i]; sort(t+1,t+1+n); Try (1); cout #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; long long n,k,a[20],t=1,m=1; void Try(int i) { fo(j,a[i-1]+1,n-k+i) { a[i]=j; if(i==k) { fo(N,1,i) cout<<a[b]<<' '; cout<<'\n'; } 138
17. Algorithm with C++ else Try(i+1); } } int main() { cin>>n>>k; fo(i,1,n) { t*=i; if(i using namespace std; #define ll long long ll n,k,x[25]; bool check(ll x[]){ for(int i = 1;i<=k;i++){ if(x[i]=='B'and x[i+1]=='B'){ return false; } } return true; } void Xuat(ll x[]) { for(int i = 1;i<=k;i++){ cout<<char(x[i]); } cout<<endl; } void Try(ll i){ for(int j = 'A';j<='B';j++){ 139
18. Algorithm with C++ x[i]=j; if(i==k){ if(check(x)) Xuat(x); } else Try(i+1); } } int main() { cin>>k; Try(1); } Bài 11.9 – (N1109D) Liệt kê xâu hợp lệ Yêu cầu: Hãy liệt kê các cách đặt n dấu mở ngoặc và dấu đóng ngoặc sao cho biểu thức đó hợp lệ. #include using namespace std; #define ll long long ll n,k,x[25]; bool check(ll x[]){ for(int i = 1;i<=k;i++){ if(x[i]=='B'and x[i+1]=='B') return false; } return true; } void Xuat(ll x[]) { for(int i = 1;i<=k;i++){ cout<<char(x[i]); } cout<<endl; } void Try(ll i){ for(int j = 'A';j<='B';j++){ x[i]=j; if(i==k){ if(check(x)) Xuat(x); } else Try(i+1); } 140
19. Algorithm with C++ } int main() { cin>>k; Try(1); } Bài 11.10 – (N1110E) Liệt kê xâu con Yêu cầu: Hãy liệt kê các cách đặt n dấu mở ngoặc và dấu đóng ngoặc sao cho biểu thức đó hợp lệ. #include using namespace std; string s, t; int n; set res; void Try(int x) { if(x > n) { if(t.size() != 0) res.insert(t); return; } for(int i = 0; i > s; n = s.size() - 1; Try(0); for(auto s : res) cout #define ll long long #define mod 1000000007 141
20. Algorithm with C++ using namespace std; ll power(ll a, ll n) { if(n == 0) return 1; ll tam = power(a,n/2); tam= (tam*tam)%mod; if(n % 2 == 1) tam=(tam*a)%mod; return tam; } int main() { ll a,n; cin>>a>>n; cout using namespace std; //Nhân chống tràn long long nhan(long long a,long long b,long long mod) { a%=mod; b%=mod; lo q=(long double) a*b/mod; return ((a*b-q*mod)%mod+mod)%mod; }// Đây là một trick khá hay trong C++ long long mu(long long x,long long y,long long z) { if(y==0) return 1; if(y==1) return x%z; long long r=mu(x,y/2,z); r=nhan(r,r,z); if(y%2==1) r=nhan(r,x,z); return r; } int main() 142
21. Algorithm with C++ { long long n,k; while(cin>>n>>k) cout using namespace std; const int mod=1e9+7; long long mu(long long a, long long b) { if (N==0) return 1; long long tmp=mu(a,b/2); tmp=(tmp*tmp)%mod; if (N%2==1) tmp=(tmp*a)%mod; return tmp; } long long a,n; int main() { cin>>a>>n; if (a==1) {cout<<n+1<<'\n';return 0;} cout<<((mu(a,n+1)-1)*mu(a-1,mod-2))%mod;//Fermat nhỏ } Bài 11.14 – (N1114E) Quân hậu Yêu cầu: Cho bàn cờ vua có kích cỡ . Hãy tìm cách xếp quân hậu trên bàn cờ sao cho các quân hậu không ăn đƣợc nhau. Ở đây ta sử dụng kỹ thuật đệ quy quay lui và đánh dấu các hàng, cột, chéo chính, chéo phụ. 143
22. Algorithm with C++ #include #define fo(i,a,b) for(int i=a;i >n; Try(1); cout<<dem; } 144
23. Algorithm with C++ KẾT LUẬN Đề tài đã tạo đƣợc một hệ thống các ví dụ, bài tập nhập môn lập trình thuật toán với ngôn ngữ C++ phong phú đa dạng, phân hóa mức độ từ thấp đến cao theo thang đo Bloom (2001); hệ thống ví dụ và bài tập này sẽ góp phần giúp giáo viên, học sinh sử dụng trong thực tế học tập và giảng dạy lập trình thuật toán một cách dễ dàng hơn. Đề tài đã cài đặt thành công website JUDGE có tên - một dạng elearning trong giảng dạy lập trình là một công cụ rất hữu hiệu đang đƣợc nhiều quốc gia phát triển trên thế giới áp dụng. Đề tài góp phần tạo ra một sân chơi học tập và giảng dạy cho môn Tin học lập trình trong xu thế của thời đại 4.0. Hƣớng phát triển kế tiếp của đề tài là trên cơ sở cài đặt công cụ - trang web có khả năng biên dịch, thông dịch các mã nguồn của nhiều loại ngôn ngữ; chúng tôi sẽ biên tập tiếp tục cuốn tài liệu nhập môn với Python và cuốn tài liệu nâng cao lập trình thuật toán với C++, đồng thời hoàn thiện các tính năng nâng cao khác cho website 145
24. Algorithm with C++ TÀI LIỆU THAM KHẢO 1. Bộ Giáo dục và Đào tạo, Chƣơng trình giáo dục phổ thông môn Tin học 2018. Thông tƣ số 32/2018/TT-BGDĐT, Hà Nội. 2. Hồ Sỹ Đàm, Sách giáo khoa Tin học 10 (2011). Nhà xuất bản giáo dục, Hà Nội. 3. Hồ Sỹ Đàm, Sách giáo khoa Tin học 11 (2011). Nhà xuất bản giáo dục, Hà Nội. 4. Hồ Sỹ Đàm, Sách bài tập Tin học 11 (2011). Nhà xuất bản giáo dục, Hà Nội. 5. Stephen Prata, C Prime Plus (2014). Adison Wesley, NewYork. 6. Thomas H. Cormen, Introduce to Algorithm (2001). The MIT Press. 146