500 bài tập tin học (HSG)

500 BÀI TẬP TIN HỌC - HSG
1. Điểm và tam giác
Cho tam giác có 3 đỉnh với tọa độ (x1, y1), (x2, y2), (x3, y3). Lập thuật toán cho biết điểm (x, y) nằm trong hay ngoài tam giác.
2. Ba hình hộp
Cho 3 hình hộp với các cạnh (là số nguyên) a1>=b1>=c1, a2>=b2>=c2, a3>=b3>=c3.
Lập thuật toán cho biết 3 hình hộp trên có thể lập thành một hình lập phương được không.
3. Số hạnh phúc
Lập chương trình tính số vé hạnh phúc gồm 2n chữ số (các số vé ghi trong hệ cơ số 10), với định nghĩa vé hạnh phúc là vé có tổng n số đầu bằng tổng n số cuối.
4. Tính 100!
Lập chương trình tính 100!
5. Tính 750
Lập chương trình tính 750.
6. Bài toán "Tháp Hà nội"
Cho 3 cọc và n đĩa (lồng vào cọc) đặt ở cọc số 1 và theo thứ tự to dưới nhỏ trên (xem hình vẽ).
Hãy chuyển n đĩa đó sang cọc số 3 sao cho thứ tự vẫn được bảo toàn. Được sử dụng cọc số 2 làm trung gian và thỏa mãn yêu cầu khi chuyển thì chỉ cho phép đĩa bé đặt trên đĩa to. Mỗi lần được chuyển một đĩa. Hãy lập chương trình mô tả quá trình chuyển đổi đó.
7. Bài toán "8 Hậu"
Hãy lập chương trình xếp 8 con hậu lên bàn cờ quốc tế sao cho không có hai con hậu nào ở tình trạng đe dọa lẫn nhau.
8. Bài toán "Mã đi"
Hãy lập chương trình di chuyển con mã trên bàn cờ n x n, xuất phát từ một vị trí nào đó sao cho nó di qua mỗi ô đúng một lần và quay về ô xuất phát.
9. Tìm "giao điểm" của các hình chữ nhật
Trên mặt phẳng tọa độ cho n hình chữ nhật có các cạnh song song với các trục tọa độ. Hãy xây dựng thuật toán để tìm số lớn nhất k thỏa mãn điều kiện: Tồn tại một điểm trên mặt phẳng nằm trong k hình chữ nhật trên.
10. Dãy số gần nhau
Cặp 2 số a,b gọi là gần nhau nếu |a-b|<10. Dãy số a1, a2, ..., an gọi là gần nhau nếu tồn tại một hoán vị của dãy trên b1, b2, ..., bnsao cho các cặp số (b1, b2), (b2, b3),..., (bn-1, bn) là gần nhau.
Hãy tìm thuật toán cho phép biết được rằng một dãy số cho trước có phải là gần nhau hay không.
11. Đường đi ngắn nhất
Cho một lưới ô vuông kích thước m x n (xem hình vẽ). Lập thuật toán tính số các đường đi ngắn nhất từ A đến B và chỉ đi trên các cạnh của lưới.
12. Danh sách lớp
Lập chương trình nhập từ bàn phím danh sách học sinh (vào cả Họ, Đệm và Tên)của một lớp (<100 hs) và sau đó in ra theo thứ tự từ điển tên của các học sinh đó,nghĩa là xếp a, b, c trước, họ đệm sau.
13. Cộng - Trừ - Nhân - Chia
Lập chương trình nhập từ bàn phím hai số tự nhiên m, n nhỏ hơn 1000000 và in ra kết quả số m x n, m+n, m/n, m-n.
14. Dãy điểm gần nhau
Cho n điểm trên mặt phẳng. Hai điểm (ax