Bài tập minh họa Nhập môn lập trình (Phần 1)

ủa một ngƣời từ bàn phím. Hãy chuẩn hóa chuỗi họ tên này. (Xóa các khoảng trắng 
thừa và ký tự đầu tiên của họ, chữ lót và tên phải viết hoa, các ký tự còn lại viết thƣờng). 
Ví du: 
Nhập: “ NgUyen VaN A “ 
Xuất: “Nguyen Van A” 
2. Không sử dụng các hàm có sẵn. Viết chƣơng trình xóa N ký tự tại vị trí i trong chuỗi S. 
Ví dụ: 
Nhập: S = “Nguyen Van A” i = 2 N = 3 (Xóa 3 ký tự tại ký tự 2 trong chuỗi S) 
Xuất: S = “Nen Van A” 
3. Viết chƣơng trình nhập một số nguyên, xuất lại số đó ở dạng chuỗi nhƣng có dấu “,” ngăn cách 
hàng triệu, ngàn. 
Ví dụ: 
Nhập: N = 123456789 
Xuất: S = “123,456,789” 
4. Nhập một chuỗi S từ bàn phím. Kiểm tra xem chuỗi có phải là chuỗi đối xứng. 
Ví dụ: 
Nhập: S = “aBCdCBa” 
Xuất: Đối xứng 
Nhập: S = “aBCdBCa” 
Xuất: Không dối xứng 
5. Nhập một chuỗi S từ bàn phím. Tìm ký tự xuất hiện nhiều nhất trong chuỗi đó và số lần xuất hiện. 
Ví dụ: 
Nhập: S = “Nguyen Thi B” 
Xuất: n 2 lần 
6. Nhập một chuỗi S từ bàn phím và một ký tự C. Đếm xem ký tự C xuất hiện bao nhiêu lần trong 
chuỗi S đó. 
Nhập: “Nguyen Van A” C = „u‟ 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 47 
Xuất: 1 lần 
7. Lập trình nhập vào từ bàn phím danh sách học sinh một lớp, sắp xếp lại danh sách theo thứ tự abc 
của Tên, nếu trùng Tên thì sắp xếp theo thứ tự abc của Họ. 
8. Viết chƣơng trình nhập từ bàn phím 2 xâu ký tự S1 và S2. Hãy xét xem S1 có xuất hiện bao nhiêu 
lần trong S2 (hoặc ngƣợc lại S2 xuất hiện bao nhiêu lần trong S1) và tại những vị trí nào? 
9. Viết chƣơng trình nhập một xâu S chỉ gồm các chữ cái thƣờng. Hãy lập xâu S1 nhận đƣợc từ xâu 
S bằng cách sắp xếp lại các ký tự theo thứ tự abc. 
10. Cho xâu S chỉ gồm các dấu “(“ và “)”. Hãy kiểm tra xem S có là một biểu thức ( ) hợp lệ hay 
không. 
Lập trình tính giá trị của một số viết dƣới dạng LA MÃ. 
11. Ví dụ: MDCLXVI = 1666. M:1000 ; D:500 ; C:100; L:50; X :10 ; V:5 ; I :1 
CÁC BÀI TẬP THÊM CÓ ĐỘ KHÓ CAO 
12. Không sử dụng các hàm có sẵn. Viết chƣơng trình chèn chuỗi S2 vào chuỗi S1 tại vị trí i trong 
chuỗi S1. 
Ví dụ: 
Nhập: S1 = “Nguyen Van A” 
S2 = “Le ” 
i = 8 (Chèn chuỗi S2 vào chuỗi S1 tại vị trí 8) 
Xuất: S1 = “Nguyen LeVan A” 
13. Nhập 2 chuỗi S1 và S2 chỉ gồm các ký số từ bàn phím. Xuất ra tổng của 2 số đó. 
Ví dụ: 
Nhập: S1 = “2912” S2 = “176” 
Xuất: S = “3088” 
14. Không sử dụng các hàm có sẵn. Kiểm tra xem chuỗi S2 có nằm trong chuỗi S1 hay không và tại vị 
trí nào. 
Ví dụ: 
Nhập: S1 = “Nguyen Van A” S2 = “Van” 
Xuất: S2 nằm trong S1 tại vị trí 8. 
15. Nhập một chuỗi S từ bàn phím. Đếm xem có bao nhiêu từ có nhiều hơn n ký tự có trong chuỗi S. 
Nhập: “Nguyen Van A” n = 2 
Xuất: 2 từ 
16. Cho xâu ký tự S. Xét xem có hay không một xâu X sao cho S là ghép của một số lần liên tiếp của 
X. Ví du S = abcabc thì X là abc, còn nếu S = abcab thì không có xâu X. 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 48 
17. Nhập từ bàn phím một số nguyên dƣơng N<=1000 và in ra màn hình xâu ký tự S độ dài N chỉ 
gồm các ký tự 0 và 1 sao cho S không có xâu con nào xuất hiện 3 lần liên tiếp trong nó. 
Nhập từ bàn phím hai số nhị phân X và Y. Hãy in ra màn hình số nhị phân Z có giá trị lớn nhất có 
thể đƣợc mà Z nhận đƣợc từ X bằng cách gạch đi một số chữ số nhị phân nào đó và Z cũng nhận 
đƣợc từ Y bằng cách gạch đi một số chữ số nhị phân nào đó. 
18. Cho một số N rất lớn (không thể biểu diễn dƣới dạng thập phân một các thông thƣờng) đƣợc biểu 
diễn dƣới dạng chuỗi nhị phân. Hãy tìm phần dƣ của phép chia N cho 15 trong hệ thập phân. 
19. Cho N xâu ký tự A1, A2, …, AN, N<=100, độ dài của xâu Ai không quá 10, và một xâu ký tự S. 
Hãy tìm mọi cách biểu diễn S dƣới dạng ghép của các xâu ký tự Ai, mỗi xâu Si có thể xuất hiện 
trong biểu diễn dó nhiều lần. 
20. Xâu M gọi là xâu con của S nếu ta có thể nhận đƣợc M từ S bằng cách xóa đi một số ký tự của S. 
Cho hai xâu S1, S2, hãy tìm xâu con M dài nhất vừa là xâu con của S1, vừa là xâu con của S2. 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 49 
Tuần 13. ĐỆ QUY 
CÁC BÀI TẬP CƠ BẢN 
1. Nhập một số nguyên n. Sử dụng đệ quy tính n! (n! = 1*2*…*n) 
Ví dụ: 
Nhập: n = 0 
Xuất: 0! = 1 
Nhập: n = 4 
Xuất: 4! = 24 
#include 
#include 
// Nên đặt prototype ở đây để biết hàm nhận vào cái gì và trả về cái gì 
// Đầu vào: n 
// Đầu ra: n! 
int GiaiThua(int); 
void main() 
{ 
 int n; 
 printf("Nhap n: "); 
 scanf("%d", &n); 
 int kq = GiaiThua(n); 
 printf("%d! = %d", n, kq); 
 getch(); 
} 
int GiaiThua(int n) 
{ 
 if (n==0) // Rất quan trọng. Đây là điểm thoát của hàm đệ quy. 
 return 1; 
 else // Có thể bỏ else vì nếu rơi vào trường hợp n=0 thì đã return. 
 return n*GiaiThua(n-1); 
} 
Cần chú ý sức chứa của biến khi khai báo. Hàm GiaiThua trả về kết quả kiểu int có sức chứa không đủ 
trong các trƣờng hợp n lớn. Lúc này sẽ xảy ra hiện tƣợng tràn số và dẫn đến cho ra kết quả sai. Có thể 
thay kiểu trả về int bằng kiểu khác có sức chứa lớn hơn nhƣ float hoặc double.
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 50 
2. Nhập một số nguyên n. Sử dụng đệ quy in dãy Fibonacy có độ dài n. 
Ví dụ: 
Nhập: n = 2 
Xuất: 1 1 
Nhập: n = 5 
Xuất: 1 1 2 3 5 
#include 
#include 
// Nên đặt prototype ở đây để biết hàm nhận vào cái gì và trả về cái gì 
// Đầu vào: n 
// Đầu ra: phần tử thứ n của dãy Fibonacy 
int Fibonacy(int); 
void main() 
{ 
 int n; 
 printf("Nhap n: "); 
 scanf("%d", &n); 
 for (int i=0; i<n; i++) 
 printf("%4d", Fibonacy(i)); 
 getch(); 
} 
int Fibonacy(int n) 
{ 
 if (n==0 || n==1) // Rất quan trọng. Đây là điểm thoát của hàm đệ quy. 
 return 1; 
 else // Có thể bỏ else vì nếu rơi vào trường hợp n=0 hoặc n = 1 thì đã return 
 return Fibonacy(n-1) + Fibonacy(n-2); 
} 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 51 
3. Nhập một mảng n số nguyên. Sử dụng đệ quy tính tổng giá trị các phần tử có trong mảng. 
Ví dụ: 
Nhập: n = 1 và mảng a = 4 
Xuất: Tổng = 4 
Nhập: n = 5 và mảng a = -1 4 6 3 0 
Xuất: Tổng = 12 
#include 
#include 
#define MAX 100 
// Đầu vào: biến chứa mảng các số nguyên và số phần tử 
// Đầu ra: tổng các phần tử của mảng 
int TongMang(int [], int); 
void main() 
{ 
 int a[MAX]; 
 for (i=0; i<n; i++) 
 { 
 printf("Nhap phan tu a[%d]: ", i); 
 scanf("%d", &a[i]); 
 } 
 if (n>0) 
 { 
 printf("Mang a vua nhap la: "); 
 for (i=0; i<n; i++) 
 printf("%4d", a[i]); 
 } 
 int kq = TongMang(a, n); 
 printf("Tong cac phan tu cua mang bang %d", kq); 
 getch(); 
} 
int TongMang(int a[], int n) 
{ 
 if (n==0) // Đây là điểm thoát của hàm đệ quy khi mảng rỗng. 
 return 0; 
 else // Mảng không rỗng thì lấy phần tử cuối + tổng phần đầu 
 return a[n-1] + TongMang(a, n-1); 
} 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 52 
4. Nhập 2 số nguyên dương a và b. Sử dụng đệ quy tính ước số chung lớn nhất của 2 số đó. 
Nhập: a = 3 b = 4 
Xuất: USCLN = 12 
#include 
#include 
// Đầu vào: 2 số nguyên dương 
// Đầu ra: ước số chung lớn nhất của 2 số nguyên dương đó 
int USCLN(int, int); 
void main() 
{ 
 int a, b; 
 printf("Nhap 2 so nguyen a va b: "); 
 scanf("%d%d", &a, &b); 
 int c = USCLN(a,b); 
 printf("Uoc so chung lon nhat cua %d va %d la: %d", a, b, c); 
 getch(); 
} 
int USCLN(int a, int b) 
{ 
 if (a==b) // Đây là điểm thoát của hàm đệ quy a=b 
 return a; 
 if (a>b) 
 return USCLN(a-b, b); 
 return USCLN(a, b-a); 
} 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 53 
5. Nhập số nguyên dương N. Sử dụng đệ quy tính in dãy nhị phân của số N đó. 
Nhập: N = 5 
Xuất: 101 
#include 
#include 
// Đầu vào: số nguyên n 
// Đầu ra: dãy biểu diện nhị phân của số nguyên dương n 
void InNhiPhan(int); 
void main() 
{ 
 int n; 
 printf("Nhap n: "); 
 scanf("%d", &n); 
 InNhiPhan(n); 
 getch(); 
} 
void InNhiPhan(int n) 
{ 
 if (n/2==0) // Đây là điểm thoát của hàm đệ quy khi không thể chia n tiếp 
 printf("%d", n%2); 
 else // Muốn bỏ else ở đây thì phải them return; ở điều kiện n/2==0 
 { 
 InNhiPhan(n/2); // Chú ý thứ tự in: in phần còn lại trước 
 printf("%d", n%2); // … rồi in số dư vừa tìm được 
 } 
} 
CÁC BÀI TẬP THÊM CÓ ĐỘ KHÓ TRUNG BÌNH 
1. Nhập một số nguyên N. Tính N! 
Nhập: N = 4 
Xuất: N! = 24 
2. Nhập 2 số nguyên a và b. Sử dụng đệ quy tính ƣớc số chung lớn nhất của 2 số đó. 
Nhập: a = 3 b = 4 
Xuất: USCLN = 12 
3. Nhập một mảng gồm N số nguyên. Sử dụng đệ quy tính tổng N số nguyên đó. 
Nhập: [1, 5, 0, 6] 
Xuất: S = 12 
4. Nhập một mảng gồm số N số nguyên. Sử dụng đệ quy kiểm tra xem có phải là mảng tăng dần. 
Nhập: [0, 1, 5, 6] 
Xuất: Tăng dần 
5. Nhập một mảng gồm số N số nguyên. Sử dụng đệ quy kiểm tra xem có phải là mảng đối xứng. 
Nhập: [0, 1, 5, 1, 0] 
Xuất: Mảng đối xứng 
BÀI TẬP MINH HỌA MÔN TIN HỌC CƠ SỞ A1 
Trang 54 
6. Nhập một số N từ bàn phím. In ra số đó theo thứ tự ngƣợc lại. 
Nhập: N = 1234 
Xuất: N = 4321 
7. Nhập một số nguyên N từ bàn phím. Tính giá trị biểu thức: 
S = 24...)1(*2*2  NN 
Nhập: N = 4 
Xuất: S = 3,299 (S = 2468  ) 
8. Nhập n. 
Tính 
)!12(
)1...(
!5!3
1253



n
xxx
xS
n
n . 
Kiểm tra kết quả tìm đƣợc khi n lớn với sinx 
9. Nhập n. Tính 
)!2(
)1...(
!4!2
1
242
n
xxx
S
n
n . 
Kiểm tra kết quả tìm đƣợc khi n lớn với cosx 
10. QuickSort 
11. Xây dựng một dãy gồm N ký tự từ 3 ký tự 1, 2, 3 sao cho không có hai dãy con liên tiếp nào giống 
nhau. Ví dụ N = 5: 12321 (đúng). Các dãy 12323, 12123 là không đúng. 
CÁC BÀI TẬP THÊM CÓ ĐỘ KHÓ CAO 
1. Cho n số tự nhiên x1, x2,…, xn. Hãy tìm UCLN (x1, x2,…,xn) bằng cách sử dụng: 
UCLN(x1,x2,…,xn)= UCLN(UCLN(x1,x2,…,x(n-1)),xn) 
2. Bài toán mã đi tuần 
3. Bài toán 8 quân hậu 
4. Tìm tất cả các hoán vị của một mảng có n phần tử 
5. Dãy Fibonacci 
6. Cho n quả cân có trọng lƣợng m1, m2,…,mn. Hãy tìm cách đặt một số quả cân sao cho cân đƣợc 
cân bằng. 
7. Cho 1 va li có thể tích V và có n đồ vật có các giá trị a1, a2,…, an và thể tích tƣơng ứng là V1, 
V2,…,Vn. Hãy tìm cách xếp các đồ vật vào vali sao cho giá trị của các hàng hóa là cao nhất