Bài tập cơ bản Tập I
Các bài tập cơ bản
Bài 1. Viết chơng trình nhập số nguyên dơng N<=1000 và N số nguyên A[1], . . .,
A[N]. Hãy thông báo ra màn hình các số sau:
- Giá trị lớn nhất của dãy và các chỉ số của các số hạng đạt giá trị lớn nhất.
- Giá trị nhỏ nhất của dãy và các chỉ số của các số hạng đạt giá trị nhỏ nhất.
- Giá trị lớn thứ nhì của dãy và các chỉ số của các số hạng đạt giá trị lớn nhì.
- Giá trị nhỏ thứ nhì của dãy và các chỉ số của các số hạng đạt giá trị nhỏ nhì.
- Dãy con gồm nhiều nhất các số hạng liên tiếp của dãy lập thành một cấp số cộng
- Dãy con gồm nhiều nhất các số hạng liên tiếp của dãy lập thành một dãy đơn điệu
- Dãy con gồm nhiều nhất các số hạng liên tiếp trái dấu nhau của dãy
- Dãy con gồm nhiều nhất các số hạng liên tiếp cùng dấu của dãy
Bài 2. Viết chơng trình nhập từ bàn phím hai số nguyên dơng M và N 10000 và in
ra màn hình ớc chung lớn nhất của hai số đó.
Bài 3. Viết chơng trình nhập từ bàn phím số nguyên dơng N 30000 và thông báo ra
màn hình N có là số nguyên tố hay không.
Bài 4. Viết chơng trình nhập từ bàn phím số nguyên dơng N 10000 và thông báo ra
màn hình các số K<=N có bằng tổng các ớc của nó và nhỏ hơn nó? (Số K thoả mãn điều
kiện trên đợc gọi là số hoàn thiện, ví dụ 6=1+2+3 là số hoàn thiện)
Bài 5. Nhập từ bàn phím số nguyên dơng N<=10000 và N số thực A1, . ., AN. Hãy
sắp xếp dãy đó theo thứ tự không giảm. Thông báo ra màn hình dãy đợc sắp xếp lại đó và
ghi rõ từng số hạng là số hạng nào của dãy cũ.
Bài 6. Có N gói kẹo, N<=200, các gói kẹo đợc đánh số từ 1 đến N, gói kẹo thứ i có
A[i] cái kẹo, các số a[1], . ., a[N] đều nguyên dơng và không quá 200. Hãy thông báo ra
màn hình một cách chia các gói kẹo làm hai nhóm sao cho tổng số kẹo trong các nhóm
sai khác nhau ít nhất.
Dữ liệu vào đợc cho bởi file INP.BL trong đó dòng thứ nhất ghi số N và trong các
dòng tiếp theo, mỗi dòng ghi 10 số lần lợt từ A[1] đến A[N].
Kết quả ghi ra file OUT.BL nh sau: dòng thứ nhất ghi số kẹo chênh lệch giữa hai
nhóm, tiếp theo là một nhóm dòng ghi số hiệu các gói kẹo thuộc nhóm thứ nhất, mỗi
dòng ghi 20 số hiệu, cuối cùng là một nhóm dòng ghi số hiệu các gói kẹo thuộc nhóm thứ

m
(d
1
. . d
r
)
Ví dụ nếu M=2, N=3, ta phải viết ra màn hình 0,(6).
Bài 11. Hãy tìm một cách biểu diễn các số lớn hàng trăm chữ số và thực hiện các
phép toán cộng và trừ.
Bài 12. Viết chơng trình nhập từ bàn phím hai số nguyên dơng M, N. Hãy tìm cách
thay các dấu ? trong biểu thức sau bởi các phép toán +, -, * sao cho giá trị của biểu thức
nhận đợc bằng N:
((((M?M)?M)?M)?M)
Nếu không có thể đợc, hãy thông báo là không thể đợc.
Bài 13. Viết chơng trình nhập một số thực dơng R và một số nguyên dơng MAX.
Hãy tìm trong số các phân số có dạng P/Q với Q<=MAX phân số gần số R nhất.
Bài 14. Viết chơng trình nhập số nguyên dơng N<=30000 và thông báo ra màn hình
số chữ số không tận cùng của N!.
Bài 15. Viết chơng trình nhập từ bàn phím hai xâu ký tự S1 và S2.
1. Thông báo ra màn hình độ dài của S1 và S2.
2. Hãy xét xem S1 có xuất hiện bao nhiêu lần trong S2 và xuất hiện tại những vị trí
nào?
3. Hãy xét xem liệu S2 có là ghép liên tiếp của một số lần xâu S1 không?
Bài 16. Viết chơng trình nhập từ bàn phím một ký tự và một xâu ký tự. Hãy thông
báo ra màn hình ký tự đó xuất hiện bao nhiêu lần trong xâu ký tự và tại những vị trí nào?
Bài 17. Viết chơng trình nhập 5 số nguyên A
0
, A
1
, A

1. Ba điểm A, B, C có lập thành một tam giác không?
- 2
Lê Ngọc Thắng
Bài tập cơ bản Tập I
2. Nếu ABC là một tam giác, hãy xét xem điểm D có nằm bên trong tam giác này
không?
Bài 20. Viết chơng trình nhập số nguyên dơng N<=1000 và dãy A gồm N số nguyên
dơng khác nhau từng đôi A[1], . ., A[N]. Hãy tìm một dãy B gồm nhiều số hạng nhất
(không nhất thiết là liên tiếp) của A sao cho với bất kỳ ba số hạng khác nhau X, Y, Z của
B, ta luôn có tổng X + Y + Z không lớn hơn tổng các số hạng còn lại của B.
Bài 21. Giả sử trong một phiên làm việc từ thời điểm 0 đến thời điểm T = 8640000,
một trung tâm tính toán phải thực hiện N chơng trình, chơng trình i thực hiện từ thời
điểm A[i] đến thời điểm B[i], 0<=A[i]<=B[i]<T.
1. Cho trớc một khoảng thời gian [P1,Q1]. Hãy xét xem liệu tại mọi thời điểm của
đoạn đó luôn có chơng trình chạy hay không?
2. Cho trớc một khoảng thời gian [R1,S1]. Hãy xét xem liệu tại mọi thời điểm của
đoạn đó luôn không có chơng trình chạy hay không?
3. Hãy tìm khoảng thời gian [P,Q] dài nhất sao cho tại mọi thời điểm của nó luôn có
chơng trình chạy.
4. Hãy tìm khoảng thời gian [R,S] dài nhất sao cho tại mọi thời điểm của nó đều
không có chơng trình chạy.
Dữ liệu vào đợc cho bởi file INP.BL trong đó dòng thứ nhất ghi số nguyên dơng N
<=200. Với 1<=i<=N, dòng thứ i+1 ghi hai số nguyên không âm A[i] và B[i]. Dòng thứ
N+2 ghi hai số nguyên không âm P1, Q1, P1<=Q1. Dòng thứ N+3 ghi hai số nguyên
không âm R1, S1, R1<=S1.
Kết quả ghi ra file OUT.BL: dòng thứ nhất ghi CO/KHONG tuỳ theo kết quả cụ thể;
dòng thứ hai ghi CO/KHONG tuỳ theo kết quả cụ thể; dòng thứ ba ghi hai số P,Q; dòng
thứ t ghi hai số R, S.
Bài 22. Viết chơng trình làm các việc sau:
1. Nhập một số nguyên dơng N<=1000 và dãy A gồm N số tự nhiên A[1], . ., A[N].

trong đó dòng thứ nhất ghi hai số nguyên dơng M, N <=100, trong M dòng sau, dòng thứ
i ghi N số lần lợt là MIN2[i,1], . ., MIN2[i,N]. Ghi ra file MIN2-1.TXT mảng MIN1 thể
hiện tình trạng mìn theo cách thứ hai, mỗi dòng của mảng MIN1 ghi thành một dòng của
file.
Bài 24.Viết chơng trình làm các việc sau:
1. Nhập từ bàn phím hai xâu ký tự S1 và S2.
2. Ta có thể dùng một trong ba loại phép biến đổi sau:
BD1: xoá một ký tự nào đó trong xâu,
BD2: thêm một ký tự nào đó vào một vị trí nào đó của xâu,
BD3: thay một ký tự nào đó trong xâu bằng một ký tự khác.
Hãy thông báo ra file OUT.TXT liệu có thể dùng một số phép biến đổi thuộc ba loại
trên để biến đổi S1 thành S2 không, quy cách thông báo nh sau: ví dụ S1 = ptsddf, S2 =
tsgldds, thì ta phải thông báo nh sau:
Biến đổi đợc
ptslddf - xoá p/1 => tslddf
tslddf - thêm g/3 => tsgdldf
tsgdldf - thay f/7/s => tsgldds
3. Trong trờng hợp biến đổi đợc, hãy tìm một cách biến đổi dùng ít phép biến đổi
nhất và thông báo tiếp vào file OUT.TXT theo quy cách nh trên.
Bài 25. Cho một bảng vuông cạnh dài N đơn vị, N nguyên dơng, 3<=N<=25. Bảng
đợc chia thành NxN ô vuông bằng nhau bằng các đờng song song với các cạnh.Trên một
số ô không nằm trên cạnh của bảng có đặt vật cản nhng bảng có mái che nên không biết
đợc vật cản nằm ở những ô nào. Ta có thể dùng một quả bóng lăn từ ngoài vào bảng theo
các dòng/cột của bảng. Khi đó diễn biến chuyển động của quả bóng nh sau:
TH1. Nếu quả bóng gặp ô có vật cản, nó quay lại ngợc chiều.
TH2. Nếu quả bóng đi tiếp súc với một ô có vật cản, nó đổi hớng 90
o
theo hớng
vuông góc với cạnh tiếp súc ngay tại ô kề đỉnh với ô chứa vật cản. TH1 sẽ xẩy ra khi
đồng thời có cả TH1 và TH2.

4 6
Bài 26. Cho một dãy N viên bi gồm 3 mầu xanh, trắng, đỏ xếp lẫn lộn. Bằng cách đổi
chỗ từng cặp viên bi cho nhau, hãy xếp lại dãy bi trên theo trình tự xanh trớc, trắng giữa,
đỏ sau. Yêu cầu cần dùng một số ít nhất phép đổi chỗ.
Dữ liệu vào đợc cho bởi file INP1.TXT. Dòng thứ nhất ghi số nguyên dơng
N<=1000. Trong N dòng tiếp theo, mỗi dòng ghi ở vị trí đầu tiên một ký tự thuộc ba loại:
X, T, D thể hiện dãy bi ban đầu.
Dữ liệu ra ghi vào file OUT1.TXT trong đó dòng thứ nhất ghi số lợng phép đổi chỗ
cần dùng. Trong những dòng tiếp theo, mỗi dòng ghi một phép đổi chỗ dới dạng hai số
p q
có nghĩa là đổi chỗ các viên bi ở hai vị trí p và q cho nhau. Trình tự viết các dòng là trình
tự các phép đổi chỗ đợc tiến hành.
Thời gian chạy chơng trình: 20 giây.
Ví dụ
INP1.TXT OUT1.TXT
9 4
T 1 3
T 4 7
- 5
Lê Ngọc Thắng
Bài tập cơ bản Tập I
X 9 2
D 5 9
D
D
T
D
X
Bài 27. Tổng giám đốc một công ty muốn tổ chức một buổi liên hoan cho các đồng
nghiệp trong công ty. Mỗi cán bộ của công ty ngoại trừ tổng giám đốc đều có đúng một

Trong các dòng tiếp theo ghi mỗi dòng 10 số (cho tới khi hết N số) lần lợt là các số ghi
trong các lá Bài từ lá Bài 1 đến lá Bài N.
Dữ liệu ra ghi ra file OUT.BL2 trong đó dòng thứ nhất ghi số lợng lá bài. Trong các
dòng tiếp theo, mỗi dòng ghi 10 số hiệu của các lá Bài đợc chọn, các số hiệu ghi theo thứ
tự tăng dần cho tới hết.
Ví dụ
INP.BL2
14
6 5 1 3 4 2 8 10 7 9
3 2 1 9
OUT.BL2
- 6
Lê Ngọc Thắng
Bài tập cơ bản Tập I
10
1 2 3 4 5 6 7 8 9 10
Bài 30. Bắt đầu từ thời điểm 0, một ngời làm N việc với số hiệu từ 1 đến N, N<=200.
Với 1<=i<=N, việc i cần làm trong T[i] đơn vị thời gian và mỗi đơn vị thời gian từ thời
điểm 0 đến lúc bắt đầu làm nó, ngời đó bị phạt một lợng tiền C[i]. Khi đã làm một việc
nào thì phải làm xong mới chuyển sang làm việc khác. Hãy thu xếp trình tự các việc làm
sao cho tổng số tiền bị phạt là ít nhất.
Dữ liệu vào đợc cho bới file INP.BL trong đó dòng thứ nhất ghi số nguyên dơng N.
Với 1<=i<=N, dòng thứ i+1 ghi hai số thực T[i] và C[i].
Dữ liệu ra ghi trong file OUT.BL. Dòng thứ nhất ghi tổng số tiền bị phạt. Từ dòng
thứ hai ghi mỗi dòng 1 cặp số: số thứ nhất là số hiệu việc, số thứ hai là thời điểm bắt đầu
việc. Trình tự từ trên xuống dới là trình tự lần lợt làm các việc.
Bài 31. Cho xâu S chỉ gồm các dấu mở và đóng ngoặc tròn (, ). Hãy xét xem liệu có
thể viết thêm một số toán hạng và dấu phép toán giữa các dấu đó để nhận đợc một biểu
thức số học đúng không.
Dữ liệu vào đợc cho bởi file INP.BL trong đó mỗi dòng ghi một xâu ký tự. Với mỗi

Kết quả ghi ra file OUT.BL nh sau:
- 7
Lê Ngọc Thắng