Bài tập bồi dưỡng học sinh giỏi môn tin học

BÀI TẬP BỒI DƯỠNG HSG MÔN TIN HỌC 
I/ Câu lệnh điều kiện If:
Bài 1: Viết chương trình nhập vào 3 số nguyên dương từ bàn phím. Xét xem 3 số đó có phải là độ dài ba cạnh của tam giác không ?
	Nếu phải thì kiểm tra xem thuộc dạng tam giác gì (vuông cân, vuông, đều, cân hay tam giác thường)
Bài 2: Viết chương trình giải bất phương trình bậc nhất một ẩn ax + b >0 với a, b được nhập từ bàn phím.
Bài 3: Hằng tháng các hộ dân trong thành phố đều nhận được hóa đơn tiền điện. Tiền điện tiêu dùng của mỗi hộ gia đình được tính như sau:
100 số đầu tiên: mỗi số phải trả 1000 đồng;
Từ 101 đến 150 số mỗi số phải trả 2000 đồng;
Từ 151 đến 200 mỗi số phải trả 2500 đồng;
Từ số 200 trở lên mỗi số phải trả 3000 đồng;
Số tiền phải trả là tổng số tiền tính được cộng thêm 10% thuế VAT. 
Biết rằng lượng điện tiêu thụ trong một tháng là a (KW), a được nhập từ bàn phím.
Hãy tính số tiền điện phải trả cho một tháng của một gia đình.
Bài 4: Hãy viết chương trình đổi tiền có mệnh giá n đồng ra các tiền 200000, 100000, 50000 đồng sao cho số tờ tiền là ít nhất. n được nhập vào từ bàn phím.
II/ Câu lệnh case:
	Bài tập tính tiền điện.
Bài 1: Theo dương lịch, năm được biểu diễn bằng một số nguyên. Theo âm lich, năm được gọi theo can và chi. Ví dụ: năm dương lịch 2006 được gọi theo âm lịch là Bính Tuất, trong đó Bính là can và Tuất là chi.
Có tất cả 10 can: Giáp, Ất, Bính, Đinh, Mậu, Kỉ, Canh, Tân, Nhâm, Quý.
Có 12 chi: Tí, Sửu, Dần, Mão, Thìn, Tỵ, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi.
Hãy lập trình:
Nhập vào từ bàn phím một năm dương lịch.
Đưa ra màn hình tên gọi năm âm lịch tương ứng (tiếng việt không dấu). Chương trình cho phép lần lượt nhập các năm và đưa ra kết quả tương ứng cho đến khi năm nhập vào là số nhỏ hơn hoặc bằng 0 thì kết thúc.
Chú ý: Bài này có thể dùng hai mảng can và chi.
Program	Canchi;
Const
	Can	: array[0..9] of string = (‘Canh’, ‘Tân’, ‘Nhâm’, ‘Quý’, ‘Giáp’, ‘Ất’, ‘Bính’, ‘Đinh’, ‘Mậu’, ‘Kỉ) ;
	Chi	: array[0..11] of string =(‘Thân’, ‘Dậu’, ‘Tuất’, ‘Hợi’, ‘Tí’, ‘Sửu’, ‘Dần’, ‘Mão’, ‘Thìn’, ‘Tỵ’, ‘Ngọ’, ‘Mùi’) ;
Var year: integer;	i,j : byte;
BEGIN
	year:=1;
While year>0 do
	Begin
	Write(‘Nam duong lich: ’);	readln(year);
	If year > 0 then
Begin
	i:= year mod 10;
	j:=year mod 12;
	Writeln(‘Nam am lich la: ’, can[i], ‘	‘, chi[j]);	
	End;
	End;
END.
Bài 2:	Viết chương trình nhập từ bàn phím một số tự nhiên có 4 chữ số. Hãy in ra màn hình cách đọc tiếng việt (không dấu) của số đó.
Bài 3*: Ngày 01/01/2013 là ngày thứ ba trong tuần. Hội đồng giáo viên họp vào thứ năm đầu tiên hàng tháng trong năm trừ ra các tháng nghỉ hè là tháng 6 và 7.
Hãy in ra tất cả các ngày trong năm 2013 mà Hội đồng giáo viên của trường họp.
III/ Câu lệnh lặp For ( dạng tiến và dạng lùi):
Bài 1:	Ba số tự nhiên a, b và c được gọi là bộ số Py-ta-go nếu a2 + b2 = c2. Viết chương trình tìm tất cả các số Py-ta-go trong khoảng từ 1 đến n, với n là số nguyên dương được nhập vào từ bàn phím.
Bài 2:	Một người gửi tiết kiệm tại một ngân hàng với số tiền ban đầu là a (triệu đồng) có chu kì tính lãi là c (tháng) với lãi suất là k%, biết rằng khi chưa đủ chu kì tính lãi thì không được tính lãi.
Hãy cho biết số tiền người đó rút được sau khoảng thời gian t (tháng). Cho biết phương thức tính lãi lũy kế, nghĩa là lãi suất sau mỗi tháng sẽ được cộng vào số tiền gốc.
Bài 3: Dãy số Fibonacci là dãy các số sao cho mỗi số sẽ bằng tổng của hai số đứng trước nó:	Fi = Fi-1 + Fi-2
Trong đó Fi là số thứ i của dãy. Hai số đầu tiên của dãy được đặt là F1=F2=1.
Hãy viết chương trình nhập từ bàn phím số nguyên n và tính giá trị của số hạng thứ n của dãy Fibonacci.
Bài 4: Số bạn bè
Hai số nguyên được gọi là bạn bè nếu tổng các ước số thực sự (kể cả 1) của số này bằng số kia và ngược lại.
Vd: Số 220 có các ước số thực sự là:
	1	2	4	5	10	11	20	22	44	55	110
	Tổng các ước số trên là 284.
Số 284 có các ước số thực sự là:
1	2	4	71	142
Tổng các ước số trên là 220
Vậy 220 và 284 là hai số bạn bè.
Viết chương trình tìm tất cả các số bạn bè trong một miền cho trước (1≤ l ≤ h ≤ 900000)
IV/ Câu lệnh lặp While:
Bài toán gửi tiền tiết kiệm: Viết chương trình cho biết người đó phải gửi bao nhiêu tháng để thu được tổng số tiền cả gốc và lãi không ít hơn b (triệu đồng).
Bài toán tìm UCLN(a,b) bằng thuật toán trừ liên tiếp hoặc bằng thuật toán chia liên tiếp.
Bài 1: Viết chương trình con thực hiện các công việc sau:
Nhập từ bàn phím giá trị của hai phân số a/b và c/d.
Nhấn phím ‘S’ hoặc ‘s’ cho kết quả là tổng của hai phân số. Hiển thị ra màn hình dạng phân số tối giản.
Nhấn ‘P’ hoặc ‘p’ cho kết quả là tích của hai phân số. Hiển thị ra màn hình dạng phân số tối giản. 
Lặp lại công việc trên cho đến khi nhấn phím ‘K’ hoặc ‘k’ để thoát khỏi chương trình.
Bài 2: Số nguyên tố tương đương 
Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không. 
Bài 3: Số siêu nguyên tố 
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố.
Nhiệm vụ của bạn là viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là một số siêu nguyên tố có N chữ số cùng số lượng của chúng.
Ví dụ khi chạy chương trình:
Nhap so N:	4¿
Cac so sieu nguyen to có 4 chu so la:	2333 	2339	2393	2399	2939	3119	3137	3733	3739	3793	3797	5939	7193	7331	7333	7393	
Tat ca co 16 so_
V/ Câu lệnh lặp Repeat:
Bài 1: Nhập vào từ bàn phím số nguyên dương N (0 < N ≤ 2*109). Tính và đưa ra màn hình tổng bình phương các chữ số của N.
Bài 2: Cho trước một số tự nhiên N. Tìm và in ra màn hình tất cả các số nguyên tố từ 2 đến N.
Bài 3: Viết chương trình đổi một số từ hệ thập phân sang hệ nhị phân.
VI/ Bài tập tổng hợp vòng lặp:
Bài 1: Cho một bảng hình vuông có kích thước nxn . Hãy viết chương trình để đưa ra màn hình bảng được điền các số từ 1 đến n2 theo hình xoắn ốc.
Ví dụ: n=4	
	1	2	3	4
	12	13	14	5
	11	16	15	6
	10	9	8	7
Bài 2: Tổng các số tự nhiên liên tiếp 
Cho trước số tự nhiên n. Lập thuật toán cho biết n có thể biểu diễn thành tổng của hai hoặc nhiều số tự nhiên liên tiếp hay không? 
Trong trường hợp có, hãy thể hiện tất cả các cách có thể có.
VII/ Kiểu mảng:
Bài 1: Viết chương trình tính giá trị của đa thức P(x)
P(x) = anxn + an-1xn-1 +  + a1x + a0 
Biết rằng số thực x, số nguyên dương n và các hệ số an, an-1 ,  , a1, a0 được nhập từ bàn phím.
Bài 2:
Sắp đến dịp tết Nguyên Đán, nhằm đáp ứng nhu cầu của khách hàng hãng hàng không Airline sẽ tăng cường chuyến bay từ TP HCM đến Huế. Vé có quyền lựa chọn số ghế. Giả sử V là tập hợp chứa ghế, các ghế được đánh số từ 1,2,3,  , n ( n ≤ 250 ), mỗi ghế sau khi được chọn sẽ loại ra khỏi V và các ghế còn lại sẽ được hiển thị để khách hàng chọn.
Hãy lập trình mô phỏng quá trình bán vé máy bay cho khách hàng.
Bài 3 : Phần tử yên ngựa 
Cho bảng A kích thước MxN. Phần tử Aij được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng của nó đồng thời là phần tử lớn nhất trong cột của nó. Ví dụ trong bảng số sau đây:
15	3	9
55	4	6
76	1	2
thì phần tử A22 chính là phần tử yên ngựa.
Bạn hãy lập chương trình nhập từ bàn phím một bảng số kích thước MxN và kiểm tra xem nó có phần tử yên ngựa hay không?
Bài 4: Xoá số trên vòng tròn 
Các số từ 1 đến 2000 được xếp theo thứ tự tăng dần trên một đường tròn theo chiều kim đồng hồ. Bắt đầu từ số 1, chuyển động theo chiều kim đồng hồ, cứ bước qua một số lại xoá đi một số. Công việc đó tiếp diễn cho đến khi trên vòng tròn còn lại đúng một số. Lập chương trình tính và in ra số đó.
Bài 5: Biểu diễn tổng các số Fibonaci
Cho số tự nhiên N và dãy số Fibonaci: 1, 1, 2, 3, 5, 8, ....
Bạn hãy viết chương trình kiểm tra xem N có thể biểu diễn thành tổng của của các số Fibonaci khác nhau hay không? 
Bài 6: Về các phép biến đổi "Nhân 2 trừ 1" 
Cho ma trận A kích thước M x N, Aij - là các số tự nhiên. Các phép biến đổi có thể là: 
- Nhân tất cả các số của một hàng với 2. 
- Trừ tất cả các số của một cột cho 1. 
Tìm thuật toán sao cho sau một số phép biến đổi trên ma trận A trở thành toàn số 0. 
Bài 7: Hai hàng số kỳ ảo 
Hãy xếp 2N số tự nhiên 1, 2, ..., 2N thành 2 hàng số: 
A1, A2 ... An 
B1, B2 ... Bn 
Thỏa mãn điều kiện: tổng các số theo n cột bằng nhau, tổng các số theo các hàng bằng nhau. 
VIII/ Kiểu xâu:
Bài 1: Viết chương trình nhập vào một xâu và đếm số lần xuất hiện của các chữ cái trong xâu đó. Hiển thị ra màn hình kí tự nào có số lần xuất hiện lớn nhất, bé nhất.
Bài 2:	 Mã hoá văn bản 
Bài toán sau mô tả một thuật toán mã hoá đơn giản (để tiện ta lấy ví dụ tiếng Anh, các bạn có thể mở rộng cho tiếng Việt):
Tập hợp các chữ cái tiếng Anh bao gồm 26 chữ cái được đánh sô thứ tự từ 0 đến 25 như sau:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
Z
Quy tắc mã hoá một ký tự như sau (lấy ví dụ ký tự X):
- Tìm số thứ tự tương ứng của ký tự ta được 23
- Tăng giá trị số này lên 5 ta được 28
- Tìm số dư trong phép chia số này cho 26 ta được 2
- Tra ngược bảng chữ cái ta thu được C.
a. Sử dụng quy tắc trên để mã hoá các dòng chữ sau:
PEACE
HEAL THE WORLD
I LOVE SPRING
b. Hãy tìm ra quy tắc giải mã các dòng chữ sau:
N FR F XYZIJSY
NSKTVRFYNHX
MFSTN SFYNTSFQ ZSNBJVXNYD
Bài 3:	Mã hóa bức thư.
Để mã hóa một bức thư người ta đưa ra qui tắc như sau:
Mộ mã được phép sử dụng trong thư là ASCII hoặc Unicode, chỉ dùng chữ thường bắt đầu là a (#97) đến z (#122)
Mỗi kí tự sẽ được tăng thêm 3, riêng ba kí tự x, y, z thì được thay bằng a, b, c.
Dãy kí tự được viết liền nhau dài không quá 200 kí tự.
Hãy lập chương trình tạo ra dãy mã hóa và giải mã theo quy luật đã cho. 
Dữ liệu vào cho bằng file văn bản Mahoa.inp có 2 dòng, trong đó dòng 1 chứa nội dung cần mã hóa, dòng 2 là ãy mã cần dịch.
Dữ liệu ra cho bởi file Mahoa.out gồm 2 dòng tương ứng kết quả từng câu.
Bài 4: Mã hoá và giải mã 
Theo quy tắc mã hoá ở bài trên (33/2000), hãy viết chương trình cho phép:
- Nhập một xâu ký tự và in ra xâu ký tự đã được mã hóa
- Nhập một xâu ký tự đã được mã hoá và in ra xâu ký tự đã được giải mã.
Ví dụ khi chạy chương trình:
Nhap xau ky tu:
PEACE ¿
Xau ky tu tren duoc ma hoa la:
UJFHJ
Nhap xau ky tu can giai ma:
FR ¿
Xau ky tu tren duoc giai ma la:
AM_
Bài 5: Mã hoá theo khoá 
Cho trước khoá là một hoán vị của n số (1, 2, ..., n). Khi đó để mã hoá một xâu kí tự ta có thể chia xâu thànhtừng nhóm n kí tự (riêng nếu nhóm cuối cùng không đủ n kí tự thì ta coa thể thêm các dấu cách vào sau cho đủ) rồi hoán vị các kí tự trong từng nhóm. Sau đó, ghép lại theo thứ tự các nhóm ta được một xâu đã mã hoá.
Chẳng hạn: với khoá 3241 (n=4) thì ta có thể mã hoá xâu 'english' thành 'gnlehs i'.
Hãy viết chương trình mã hoá một xâu kí tự cho trước.
Bài 6: Dãy số nguyên 
(Dành cho học sinh THCS)
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314..... (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Em hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.
Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng nhanh càng tốt.
IX/ Kiểu Record:
Bài 1:	Để quản lý các thuê bao điện thoại người ta sử dụng các thông tin: Họ đệm, tên, số điện thoại, địa chỉ.
Hãy nhập dữ liệu cho thuê bao và in ra màn hình:
Danh sách các thuê bao được sắp xếp theo chiều tăng dần của tên ( nếu trùng thì họ đệm ).
Tìm thuê bao theo số điện thoại.
Xóa một thuê bao.
Bài 2: Viết chương trình nhập dữ liệu cho một phòng thi không quá 30 học sinh gồm các thông tin sau: SBD, Họ tên, ĐTB môn toán, ĐTB môn Văn, ĐTB môn Lý. Sau đó in ra màn hình thông tin của học sinh có tổng điểm của ba môn ≥ 15 theo thứ tự giảm dần.
X/ Kiểu file:
Bài 1:	Số k có n chữ số, số này được gọi là đối xứng khi chữ số thứ nhất và chữ số thứ n bằng nhau, số thứ hai và số thứ n-1 bằng nhau, 
Vd: 30403, 8448 được gọi là các số đối xứng.
Khi cho hai số nguyên dương i và j, thử tìm xem trong khoảng từ i đến j có bao nhiêu số k như thế {100< i, j< 100 000}
Hãy viết chương trình liệt kê tất cả các số k và tổng số của chúng có mặt từ I đến j.
Dữ liệu vào cho bởi file văn bản có tên doixung.txt chứa hai số nguyên dương i, j có chứa cách nhau ít nhất một khoảng trắng. 
Dữ liệu ra cho file văn bản doixung.out . Liệt kê toàn bộ số k có trong khoảng i, j . Mỗi số trên một dòng. 
Bài 2: Số phản nguyên tố
Một số n gọi là số phản nguyên tố nếu số ước số của nó là nhiều nhất trong n số tự nhiên đầu tiên. Cho số K (K <= 2 tỷ). Hãy ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.
Dữ liệu vào trong file PNT.INP nội dung gồm:
- Dòng đầu tiên là số M (1 < M <= 100) - số các số cần tìm số phản nguyên tố lớn nhất của nó;
- M dòng tiếp theo lần lượt là các số K1, K2, K3, ..., KM;
Dữ liệu ra trong file PNT.OUT gồm M dòng: dòng thứ i là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.
Ví dụ:
PNT.INP
1
1000
PNT.OUT
840
Bài 3:	 Tổ chức tham quan 
Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản P2.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, M (N£M£200);
- Dòng thứ hai chứa các số nguyên dương d1, d2, ..., dN;
- Dòng thứ ba chứa các số nguyên dương v1, v2, ..., vM.
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản P2.OUT:
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).
Ví dụ:
P2.INP
P2.OUT
3 4
7 5 9
17 13 15 10
256
2
3
4