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++

ơng . Hãy tính 
1 2
...
n
S
n n n
     
        
     
. 
Nhận xét thấy: có nhiều đoạn mà 
1
...
i i j
n n n
     
       
     
. Vì vậy ta sẽ tìm các 
đoạn nhƣ vậy và nhân với độ dài của đoạn với độ lớn của 
i
n
 
 
 
. 
#include 
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; 
Algorithm with C++ 
126 
 i=n/t+1; 
 } 
 cout<<s; 
} 
Algorithm with C++ 
127 
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() 
Algorithm with C++ 
128 
{ 
 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 
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 
Bài toán 
cấp n 
Bài toán 
cấp n-1 
Bài toán 
cấp n-2 
Bài toán 
cấp n-2 
Bài toán 
cấp n-1 
Bài toán 
cấp n-2 
Algorithm with C++ 
129 
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 na thì độ phức tạp của giải 
thuật sẽ là – chỉ có thể giải đƣợc cho n cỡ 6 810 10  trong thời gian giây. 
Algorithm with C++ 
130 
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;k++) cout<<x[k]; 
 cout<<endl; 
} 
void Try(ll i) 
{ 
 for(int j=0;j<=1;j++) 
 { 
 x[i]=j; 
 if(i==n) Xuat(); 
 else Try(i+1); 
 } 
} 
int main() 
{ 
 cin>>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  1,2,...,X n . 
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: 
Algorithm with C++ 
131 
#include 
#define ll long long 
#define fo(i,a,b) for(int i=a;i<=b;i++) 
using namespace std; 
ll n,x[30],d[30]; 
void Xuat() 
{ 
 fo(k,1,n) cout<<x[k]; 
 cout<<'\n'; 
} 
ll Try(ll i) 
{ 
 fo(j,1,n) 
 if(d[j]==0)// nếu j chưa được chọn 
 { 
 x[i]=j;//chọn x[i] là j 
 d[j]=1;//đánh dấu j đã được chọn 
 if(i==n) Xuat();// in ra khi chọn tới xn 
 else Try(i+1); // chưa chọn đến xn thì chọn tiếp 
 d[j]=0;// quay lại bỏ đánh dấu để chọn tiếp sau 
 } 
} 
int main() 
{ 
 cin>>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'; 
Algorithm with C++ 
132 
 } 
 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  1,2,...X n . 
Dữ liệu: Một dòng ghi số nguyên không âm 
9(0 10 )n n  . 
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 910 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 (0 20)n n  
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 (0 10)n n  . 
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 
Algorithm with C++ 
133 
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 k 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  1,2,...,X n 
Dữ liệu nhập: Một dòng một gồm  , 1 8k n k n   . 
Kết quả: Mỗi dòng in một chỉnh hợp chập k 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 n 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 k của n phần 
tử này. 
Dữ liệu nhập: 
- Dòng một gồm  , 1 8k n k n   . 
- Dòng hai là n phần tử của tập A. 
Kết quả: 
- Mỗi dòng in một chỉnh hợp chập k của n , 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 9 4 
1 4 
1 9 
Algorithm with C++ 
134 
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 k của tập  1,2,...,X n . 
Dữ liệu: Một dòng một gồm  , 1 8k n k n   . 
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 k 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  , 1 8k n k 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 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 9 4 
1 4 
1 9 
4 9 
3 
Algorithm with C++ 
135 
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  20n 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.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à n 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  20n 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  . 15S length  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 
Algorithm with C++ 
136 
Bài 11.11– (N1111D) Số mũ 1 
Yêu cầu: Cho hai số nguyên a, n. Tính  9% 10 7na  . 
Dữ liệu: Một dòng ghi hai số nguyên  9, 0 , 10a n a n  . 
Kết quả: In ra kết quả là tổng  9% 10 7na  . 
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  0 1 11.2 2.2 ... .2 %nS n K    . 
Dữ liệu: Một dòng ghi hai số nguyên  9n,K 0 , K 10n  . 
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 1 21 ... nS a a a     . Kết quả có thể rất lớn 
nên chia lấy dƣ cho 910 7 khi in ra. 
Dữ liệu: Một dòng ghi hai số nguyên  9, 0 , 10a n a n  . 
Kết quả: In ra kết quả là tổng  9% 10 7S  . 
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 
Algorithm with C++ 
137 
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<=b;i++) 
#define nmax 10000005 
using namespace std; 
ll n,k,a[30],b[30],dem=0; 
ll qlui(ll x) 
{ 
 fo(i,1,n) if(N[i]==0) 
 { 
 a[x]=i; 
 b[i]=1;// Đánh dấu i đã được chọn 
 if(x==k) 
 { 
 fo(j,1,k) cout<<t[a[j]]<<' '; 
 cout<<'\n'; 
 } 
 else qlui(x+1); 
 b[i]=0;// Bỏ đánh dấu để quay lui chọn lại 
 } 
} 
int main() 
{ 
 cin>>k>>n; 
 fo(i,1,n) cin>>t[i]; 
 sort(t+1,t+1+n); 
 qlui(1); 
 cout<<dem; 
} 
Bài 11.5 – (N1105B) Liệt kê chỉnh hợp tập A 
#include 
#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) 
{ 
Algorithm with C++ 
138 
 fo(i,1,n) if(N[i]==0) 
 { 
 a[x]=i; 
 b[i]=1; 
 if(x==k) 
 { 
 fo(j,1,k) cout<<t[a[j]]<<' '; 
 cout<<'\n'; 
 dem++; 
 } 
 else Try(x+1); 
 b[i]=0; 
 } 
} 
int main() 
{ 
 cin>>k>>n; 
 fo(i,1,n) cin>>t[i]; 
 sort(t+1,t+1+n); 
 Try (1); 
 cout<<dem; 
} 
Bài 11.6 – (N1105B) 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 k của tập  1,2,...,X n . 
#include 
#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'; 
 } 
Algorithm with C++ 
139 
 else Try(i+1); 
 } 
} 
int main() 
{ 
 cin>>n>>k; 
 fo(i,1,n) 
 { 
 t*=i; 
 if(i<=min((n-k),k)) m=m*i*i; 
 else if(i<=max((n-k),k)) m*=i; 
 } 
 cout<<t/m<<'\n'; 
 a[0]=0; 
 Try(1); 
} 
Bài 11.8 – (N1108C) 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. 
#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++){ 
Algorithm with C++ 
140 
 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à n 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); 
 } 
Algorithm with C++ 
141 
} 
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à n 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 <= 1; i++) 
 { 
 if(i) t += s[x]; 
 Try(x + 1); 
 if(i) t.erase(t.size() - 1, 1); 
 } 
} 
int main() 
{ 
 cin >> s; 
 n = s.size() - 1; 
 Try(0); 
 for(auto s : res) cout << s << '\n'; 
} 
Bài 11.11 – (N1111D) Số mũ 1 
#include 
#define ll long long 
#define mod 1000000007 
Algorithm with C++ 
142 
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<<power(a,n); 
} 
Bài 11.12 – (N1112E) Số mũ 2 
Yêu cầu: Cho số nguyên n, K tính  0 1 11.2 2.2 ... .2 %nS n K    . 
Trong bài này, ta sử dụng hàm tính nhanh mũ và phép nhân chia lấy dƣ chống 
tràn nhƣ sau: 
#include 
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() 
Algorithm with C++ 
143 
{ 
 long long n,k; 
 while(cin>>n>>k) 
 cout<<nhan(mu(2,n,k),(n-1),k)+1<<'\n'; 
} 
Bài 11.13 – (N1113E) Số mũ 3 
Yêu cầu: Cho số nguyên , tính 1 21 ... nS a a a     . Kết quả có thể rất lớn 
nên chia lấy dƣ cho 910 7 khi in ra. 
Ta có 
1
1 2 11 ...
1
n
n aS a a a
a
 
     

. Từ đó ta sử dụng phép mũ chia để trị và 
định lý Fermat nhỏ để chia lấy dƣ cho một số nguyên tố để có đƣợc kết quả. 
Nội dung định lý Fermat nhỏ nhƣ sau: “Với p là số nguyên tố và 2a  thì 
 1 1 modpa p  ”. Từ đó suy ra đẳng thức     2% % % %pa p a p b p p
b
  . 
#include 
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ụ. 
Algorithm with C++ 
144 
#include 
#define fo(i,a,b) for(int i=a;i<=b;i++) 
#define ll long long 
using namespace std; 
ll n,q[20],s=1,t,dem=0; 
bool ok; 
void Try(ll r) //Quay lui vét cạn 
{ 
 fo(j,1,n) 
 { 
 ok=true; 
 fo(i,1,r-1) //Đánh dấu hàng, cột, chéo chính phụ 
 if(q[i]==j||q[i]==j+r-i||q[i]==j-r+i) ok=false; 
 if(ok) 
 { 
 q[r]=j; 
 if(r==n) dem++; 
 else Try(r+1); 
 } 
 } 
} 
int main() 
{ 
 cin>>n; 
 Try(1); 
 cout<<dem; 
} 
Algorithm with C++ 
145 
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 
Algorithm with C++ 
146 
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.