Đề thi chọn HSG môn Tin học 8

Nội dung text: Đề thi chọn HSG môn Tin học 8

1. Đề số 1 Bài 1. Lập trình tìm các số có ba chữ số với điều kiện giá trị của số đó bằng tổng lập phương các chữ số của nó. Bài 2. Tính tổng sau (với x thực nhập từ bàn phím): x 3 x 5 x 7 T x 3 5 7 Chương trình dừng khi x 2n 1 ( 1) n . 0,0001 (2n 1) Bài 3. Cho dãy số thực bất kỳ, hãy kiểm tra xem dãy số đã sắp xếp chưa? Nếu sắp xếp rồi thì theo chiều nào? Nếu chưa thì sắp xếp theo chiều tăng dần. Bài 4. Nhập vào một xâu ký tự. Hãy chuẩn hoá xâu bằng cách chỉ giữ lại một dấu cách giữa các từ. 1
2. Đề số 2 Bài 1 Nhập vào một số tự nhiên n. Lập trình trả lời các câu hỏi sau: - n có bao nhiêu chữ số? - Tổng các chữ số của n bằng bao nhiêu? - Tìm chữ số đầu tiên của n. - Giả sử trong cách biểu diễn thập phân của n có dạng sau: akak-1 a2a1a0. Hãy tính tổng S = ak – ak-1 + ak-2 - a0 - Nhập vào số m (m số chữ số của n). Hãy tính tổng m chữ số cuối cùng của n. Bài 2. Nhập vào một dãy các số nguyên bất kỳ, in ra màn hình các số khác nhau trong dãy số đó. Bài 3. Viết chương trình nhập vào một ma trận vuông k hàng, k cột. Sau đó sắp xếp lại sao cho phần tử có trị tuyệt đối lớn nhất trong mỗi hàng sẽ nằm trên đường chéo chính. Bài 4. Vẽ bàn cờ vua 8 x 8 ô lên màn hình. 2
3. Đề số 3 Bài 1. Viết chương trình nhập vào một dãy n số nguyên và in ra màn hình các thông tin sau (Nếu không có số nào thoả mãn thì đưa ra thông báo không có): - Số hạng âm lớn nhất của dãy và chỉ số của nó; - Số hạng dương nhỏ nhất của dãy và chỉ số của nó; - Số lượng số hạng dương liên tiếp nhiều nhất; - Số lượng số hạng âm liên tiếp có tổng lớn nhất; - Số lượng số hạng liên tiếp đan dấu nhiều nhất. Bài 2. Điền các số từ 1 đến n*n theo chiều kim đồng hồ vào mảng hai chiều. In mảng kết quả ra màn hình theo dạng n dòng và n cột. Bài 3. Nhập vào một xâu ký tự bất kỳ. Hãy chuẩn hoá xâu đó bằng cách chỉ giữ lại một dấu trống (dấu cách) giữa các từ (từ được hiểu là một dãy các ký tự liên tiếp không chứa dấu cách). Bài 4. Với giá trị x nhập từ bàn phím, hãy tính tổng sau: (x 1) (x 1)3 (x 1)5 (x 1) 2n 1 (x 1) 3.(x 1)3 5.(x 1)5 (2n 1).(x 1) 2n 1 (x 1) 2n 1 cho đến khi 0,0001 (2n 1).(x 1) 2n 1 3
4. Đề số 4 Bài 1. Lệnh Format đĩa mềm với các tham số, nêu các ý nghĩa của các tham số này. Bài 2. Lập trình tính tổng sau: 1 1 1 S : 1 2 3 n Bài 3. Lập trình đưa ra màn hình các số nguyên tố từ 1 đến 100. Bài 4. Lập trình đưa ra màn hình bảng cửu chương có dạng: 1 2 3 9 2 18 . . . . . 9 18 81 bằng hai cách. 4
5. Đề số 5 Bài 1. Tính biểu thức sau với x là số thực cho trước (x 0), yêu cầu kiểm tra điều kiện x nhập vào từ bàn phím: 2 T x2 4 x2 8 x2 16 x2 . . . . 256 x2 x2 Bài 2. Nhập vào hai số tự nhiên n và m. Hãy in ra chu kỳ của phân số n/m Ví dụ: 1/7 có chu kỳ là (142857). Còn các phân số hữu hạn thì chu kỳ = 0. Bài 3. Cho số tự nhiên n và dãy các số thực a1, a2, an, trong đó hãy xác định số lượng các phần tử kề nhau mà: a. Cả hai số đều dương. b. Cả hai số đều cùng dấu đồng thời số đứng trước có giá trị tuyệt đối lớn hơn số đứng sau. c. Cả hai số trái dấu nhau. Bài 4. Cho một tệp văn bản có tên VANBAN.PAS gồm 3 dòng chứa 3 xâu ký tự S1, S2, S3 có độ dài tuỳ ý. Xâu S1 cần biến đổi như sau: lần lượt xét từng ký tự của S1. Nếu ký tự i của S1 trùng với ký tự thứ j gặp đầu tiên tính từ bên trái của S2 thì ký tự thứ i đó của S1 được thay bằng ký tự thứ j của S3 nếu có. Trong các trường hợp khác thì bỏ qua yêu cầu biến đổi S1. Mỗi bước, nếu có sự thay thế cần hiển thị lên màn hình dạng thông báo: -(a, i, j, c) nghĩa là ký tự thứ i của S1 là a được thay bằng ký tự thứ j của S3 là c. -Hiển thị lên màn hình lần lượt S1, S2, S3 ban đầu và S1 sau khi biến đổi. 5
6. Đề số 6 Bài 1. Tần số xuất hiện chữ cái Cho tệp văn bản mang tên VANBAN.PAS. Hãy đưa ra một tệp văn bản mang tên KQVANBAN.PAS các chữ cái khác nhau trong tệp trên và số lần xuất hiện mỗi chữ cái đó. Bài 2. Tam giác Pascal Hãy in ra màn hình tam giác Pascal có n dòng và tính xem ở hàng thứ i có bao nhiêu số j (với n, i, j nhập từ bàn phím). Tam giác Pascal có dạng như sau: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 6    Bài 3. Xâu nghịch đảo d. Hãy sử dụng kỹ thuật đệ quy trong lập trình để tìm xâu nghịch đảo của một xâu nhị phân cho trước (xâu nhị phân là xâu chỉ gồm hai kí tự ‘0’ và ‘1’). Bài 4. Số hoàn hảo Nhập từ bàn phím một số tự nhiên N. Lập chương trình tìm tất cả các số hoàn hảo có giá trị từ 1 đến N (nếu có). Nếu không có hãy đưa ra thông báo “Không có”. (Số hoàn hảo là một số tự nhiên thoả mãn điều kiện: giá trị số đó bằng tổng các ước số thực sự của nó mà không kể chính số đó). 6
7. Đề số 7 Bài 1. Bài toán 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ụ như 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 M và N. 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 không? Bài 2. Số siêu nguyên tố Số siêu nguyên tố là số nguyên tố mà khi bó đi 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ụ: 7333 là số siêu nguyên tố có 4 chữ số vì 733; 73; 7 đều là các số nguyên tố. Hãy lập 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à các số siêu nguyên tố có N chữ số cùng số lượng của chúng. Bài 3. Tìm điểm yên ngựa Cho bảng số A kích thước M hàng x N cột. Phần tử Aij (nằm ở hàng i, cột j ) được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng i đồng thời là phần tử lớn nhất trong cột j (hoặc là phần tử lớn nhất trong hàng i đồng thời là phần tử nhỏ nhất trong cột j). Ví dụ trong 2 bảng số sau: Bảng 1: 15 3 9 55 4 6 76 1 2 Bảng 2: 15 55 9 3 4 1 7 6 2 Thì phần tử A22 = 4 là phần tử yên ngựa. Hãy lập chương trình nhập từ bàn phím một bảng số kích thước M x N và in ra các phần tử yên ngựa (nếu có). Bài 4. Bài toán thay thế từ Hai file DLIEU1.TXT và DLIEU2.TXT được cho như sau: File DLIEU1.TXT chứa một đoạn văn bản bất kỳ. File DLIEU2.TXT chứa không quá 50 dòng. Mỗi dòng gồm 2 từ: Từ đầu là từ đích và từ sau là từ nguồn. Hãy lập chương trình tìm trong file DLIEU1.TXT tất cả các từ là từ đích và thay thế chúng bằng các từ nguồn tương ứng. Kết quả được ghi vào file KETQUA.TXT (Đó là đoạn văn bản 7
8. tương tự như trong file DLIEU1.TXT nhưng được thay thế từ đích bởi từ nguồn). Ví dụ: File DLIEU1.TXT chứa đoạn văn bản: Nam hoc sap ket thuc roi, ban co zui khong? Chuc cac ban don mot ky nghi he that zui ze va hanh phuc. File DLIEU2.TXT chứa các dòng sau: ban em zui vui ze ve File KETQUA sẽ chứa đoạn văn bản sau: Nam hoc sap ket thuc roi, ban co vui khong? Chuc cac ban don mot ky nghi he that vui ve va hanh phuc. 8
9. Đề số 8 Bài 1. Trò chơi Trò chơi bốc kẹo là trò chơi cho 2 đối thủ. Người ta xếp N túi kẹo vòng quanh một chiếc bàn tròn và đánh số liên tiếp theo chiều kim đồng hồ từ 1 đến N bắt đầu từ một túi kẹo bất kỳ. Túi thứ i có ai cái kẹo. Hai đối thủ luân phiên thực hiện nước đi, mỗi nước đi phải lấy 1 túi kẹo. Đối thủ thứ nhất, là người thực hiện nước đi đầu tiên, được chọn và lấy 1 trong N túi kẹo. Tiếp theo, đối thủ đến lượt thực hiện nước đi phải chọn túi kẹo ở sát cạnh vị trí túi kẹo mà đối thủ thực hiện nước đi ngay trước đó vừa lấy. Trò chơi kết thúc khi trên mặt bàn không còn túi kẹo nào cả. Yêu cầu: Cho biết chỉ số của túi kẹo mà đối thủ nhất lấy đi trong nước đi đầu tiên. Hãy tính tổng số kẹo lớn nhất mà đối thủ thứ hai có thể lấy được khi tham gia trò chơi này. Dữ liệu: Vào từ file văn bản GAME.INP - Dòng đầu tiên chứa số lượng túi kẹo N ( 1 N 1000). - Dòng thứ hai chứa số nguyên dương k là chỉ số của túi kẹo mà đối thủ thứ nhất chọn và lấy trong nước đi đầu tiên. - Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương ai (ai 32767), i = 1, 2, N. Kết quả: Ghi ra file văn bản GAME.OUT tổng số kẹo lớn nhất tìm được. Ví dụ: GAME.INP GAME.OUT 5 11 1 2 2 3 9 5 Bài 2. Xếp khách Một khách dạn có N phòng đôi (phòng cho 2 người) được đánh số từ 1 đến N. Khi có một đoàn khách đến thuê phòng, tiếp tân của khách sạn sẽ xếp khách vào phòng theo quy tắc sau: Mỗi cặp khách sẽ được xếp vào phòng có chỉ số nhỏ nhất trong số các phòng trống. Nếu số lượng khách của đoàn là số lẻ thì người cuối cùng của đoàn khách sẽ được xếp vào phòng có chỉ số nhỏ nhất trong số các phòng trống. Nếu không còn phòng trống, thì số khách chưa 9
10. có phòng sẽ được xếp tuần tự từng người một vào phòng có chỉ số nhỏ nhất trong số các phòng mới có một khách ở (của đoàn khách đến trước). Đầu tiên tất cả các phòng của khách sạn là trống. Yêu cầu: Cho trước trình tự đến của các đoàn khách và số lượng khách của mỗi đoàn. Hãy xác định số lượng khách trong mỗi phòng của khách sạn. Dữ liệu: Vào từ file văn bản ROOM.INP: - Dòng đầu tiên chứa 2 số nguyên dương N ( 1 N 100) và G được ghi cách nhau bởi dấu cách. N là số phòng của khách sạn, G là số lượng đoàn khách. - Dòng thứ i trong số G dòng tiếp theo chứa số lượng khách của đoàn khách thứ i (các đoàn khách được đánh số theo thứ tự đến khách sạn bắt đầu từ 1). Giả thiết rằng không có 2 đoàn khách nào đến khách sạn vào cùng một thời điểm và tổng số khách của tất cả các đoàn không vượt quá sức chứa của khách sạn ( 2N). Kết quả: Ghi ra file văn bản ROOMS.OUT N dòng: Dòng thứ i chứa số lượng khách của phòng i (1 i N). Ví dụ: ROOMS.INP ROOMS.OUT 7 3 2 3 1 1 1 4 2 2 0 0 Bài 3. Hình vuông Cho một lưới K x N điểm gồm K dòng và N cột (2 K, N 9) là các điểm nút của một lưới ô vuông (các dòng được đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải bắt đầu từ 1). Trên lưới điểm đó cho một số đoạn thẳng, mỗi đoạn nối một cặp điểm cạnh nhau trên cùng một dòng (đoạn ngang) hoặc trên cùng một cột (đoạn dọc). Cần phải đếm số các hình vuông với kích thước nhất định được tạo thành bởi các đoạn thẳng đã cho của lưới nêu trên. Chẳng hạn ở hình 1 dưới đây có 3 hình vuông; 2 hình kích thước 1 và 1 hình kích thước 2 (kích thước của hình vuông là số các đoạn thẳng tạo thành 1 cạnh của hình vuông). 10
11. Hình 1 Yêu cầu: Hãy xác định số lượng các loại hình vuông và số hình vuông mỗi loại trong lưới điểm đã cho (hình vuông có cùng kích thước được xếp vào cùng một loại). Dữ liệu: Vào từ file văn bản SQUARE.INP có khuôn dạng như sau: • Dòng 1 chứa số nguyên N là số cột của lưới. • Dòng 2 chứa số nguyên M là số các đoạn thẳng được cho trên lưới. • Mỗi dòng trong M dòng tiếp theo có 1 trong 2 dạng sau: ➢ H i j chỉ một đoạn ngang trên dòng thứ i nối hai điểm ở cột j và cột j +1. ➢ Hoặc: V j i chỉ một đoạn dọc trên cột thứ j nối hai điểm ở dòng i và dòng i +1. Số liệu được ghi từ vị trí đầu tiên của mỗi dòng, giữa ký tự và số và giữa hai số liên tiếp trên một dòng có đúng một dấu cách. Kết quả: Ghi ra file văn bản SQUARE.OUT •Dòng đầu tiên ghi số nguyên P là số loại hình vuông có trên lưới. •Mỗi dòng trong P dòng tiếp theo ghi thông tin mô tả về một loại hình vuông và số lượng hình vuông đó bao gồm hai số nguyên a, b cho biết có a hình vuông có cạnh độ dài b. Các thông tin về các loại hình vuông phải được đưa ra theo thứ tự tăng dần của độ dài cạnh. •Trong trường hợp không tìm được bất cứ một hình vuông nào file SQUARE.OUT gồm một dòng duy nhất chứa thông báo “NO SQUARES”. Ví dụ: File dữ liệu mô tả lưới cho trong hình 1 và file kết quả tương ứng có dạng: 11
12. SQUARE.INP SQUARE.OUT 4 2 16 2 1 H 1 1 1 2 H 1 3 H 2 1 H 2 2 H 2 3 H 3 2 H 4 2 H 4 3 V 1 1 V 2 1 V 2 2 V 2 3 V 3 2 V 4 1 V 4 2 V 4 3 12
13. Đề số 9 Bài 1. Tính số ngày giữa 2 mốc thời gian bất kỳ: Yêu cầu nhập vào 6 số: nd, td, yd, nc, tc, yc là ngày tháng năm bắt đầu và ngày tháng năm cuối (2000 < yd <yc). Hãy tính xem giữa hai mốc thời gian đó có bao nhiêu ngày. Biết rằng: Tháng 4, 6, 9, 11 có 30 ngày. Tháng 1, 3, 5, 7, 8, 10, 12 có 31 ngày. Tháng 2 nếu năm nhuận có 29 ngày còn nếu không nhuận thì có 28 ngày. Bốn năm có một năm nhuận, biết rằng năm 2000 thì năm nhuận. Bài 2. Trên một bàn cơ có n x n ô, hãy lập trình xếp 2n quân cờ lên bàn cờ sao cho không có quá 2 quân cờ trên 1 hàng và trên 1 cột. Chỉ cần in ra một cách xếp lên màn hình (dùng dấu ‘ *’ làm ký hiệu quân cờ). Bài 3. Cho một dãy số bất kỳ. Hãy kiểm tra xem dãy đó được sắp xếp hay chưa? Nếu sắp xếp rồi thì: - Trả lời dãy đó được sắp xếp theo chiều tăng hay giảm? - Chèn một phần tử vào dãy đã sắp xếp đó sao cho thứ tự sắp xếp không thay đổi (phải chèn trực tiếp, không được sắp xếp lại). Nếu dãy chưa sắp xếp, hãy sắp xếp chúng theo chiều tăng dần. Bài 4. Hai xâu ký tự được gọi là ANAGRAM của nhau nếu xâu này có thể tạo được bằng cách hoán vị các ký tự của xâu kia, từ đơn được hiểu là xâu ký tự viết liền nhau không chứa dấu cách. Cho một tệp văn bản bất kỳ có tên VANBAN.TXT, hãy lập trình để hiện lên màn hình những nhóm từ là ANAGRAM của nhau bằng cách xét các từ trong tệp văn bản đã cho. 13
14. Đề số 10 Bài 1. Tìm các số hạng Max của các đường chéo thuộc tam giác bên trái dưới của ma trận An x n. Bài 2. Cho ma trận nguyên An x n và 2 số a, b. Hãy xây dựng ma trận mới cấp An – 1 x n–1 từ ma trận trên bằng cách loại bỏ dòng a và cột b (không dùng ma trận trung gian) Bài 3. Mã số sách Để đánh mã số cho từng quyển sách, một cán bộ thư viện dự định dùng một từ có 5 kí hiệu liên tiếp nhau gồm : 2 kí tự (A Z) tiếp theo là 3 kí số (001 999). Em hãy lập trình tạo tất cả từ có thể dùng làm mã số. Yêu cầu kĩ thuật Xuất : File text MASO.INP Mỗi dòng có 8 từ, mỗi từ cách nhau một khoảng trống. Ghi chú: Mã số sách không có 3 kí hiệu cuối là 000. 14
15. Đề số 11 Bài 1. Cho dãy số nguyên a1, a2, an. Hãy tìm độ dài đoạn dài nhất các phần tử liên tiếp của dãy trên sao cho ai =ai +1. Bài 2. Nhận dạng hằng số thực (real con-stant) Người ta định nghĩa, một hằng số được coi là số thực nếu ngoài các số chữ số ra nó còn có dấu chấm (.) hoặc một số mũ (bắt đầu bởi e hay E thường được gọi là số luỹ thừa) hoặc cả hai. Nếu có dấu chấm (.) thì mỗi bên của dấu chấm phải có ít nhất một chữ số. Ngoài ra, ở trước số và trong số mũ còn có thể có một dấu cộng (+) hoặc trừ (-). Phần số luỹ thừa phải là số nguyên. Số thực có thể có các khoảng trông (BLANK) ở trước hoặc sau nhưng bên trong thì không. Hằng số thực không có giới hạn về giá trị. Viết chương trình kiểm tra xem các chuỗi kí tự cho trước có phải là những số thực theo định nghĩa trên đây hay không. Dữ liệu vào: Dữ liệu vào cho trong tập tin văn bản SOTHUC.INP gồm nhiều dòng cho nhiều trường hợp cần kiểm tra. Mỗi dòng chứa một chuỗi kí thự S i là chuỗi cần kiểm tra. Dòng cuối cùng chứa kí tự '*', dòng này không được xét trong chương trình. Mỗi dòng tối đa 255 kí tự. Dữ liệu ra Kết quả ghi trong tập tin văn bản SOTHUC.OUT gồm nhiều dòng. Mỗi dòng chứa câu trả lời là "DUNG" hoặc "SAI" tương ứng với một dòng trong tập tin SOTHUC.INP. Ví dụ: Dữ liệu vào Dữ liệu ra 1,2 DUNG 5,300 DUNG 1 SAI 1.0e55 DUNG +1e-12 DUNG 6 SAI e-12 SAI *. 15
16. Bài 3. Chuỗi đối xứng Mỗi chuỗi kí tự được gọi là đối xứng nếu nó có không ít hơn 1 kí tự và nếu ta đọc từ phải sang trái hay từ trái sang phải đều giống nhau. Ví dụ 'Z' , 'TOT' , 'NAN' là các chuỗi đối xứng còn 'NAM' không phải. Yêu cầu: Viết chương trình nhận vào chuỗi kí tự cho trước S và hãy cho biết có bao nhiêu chuỗi con khác nhau của S là chuỗi đối xứng. Chuỗi con của S là chuỗi gồm một số kí tự nằm liên tiếp nhau trong S. Dữ liệu vào: Dữ liệu vào cho trong tập tin văn bản CHUOI.INP gồm nhiều dòng, mỗi dòng là một chuỗi kí tự cần xem xét (các chuỗi có độ dài không quá 80 kí tự). Dữ liệu ra: Kết quả ghi trong tập tin văn bản CHUOI.OUT có số dòng bằng với số dòng của CHUOI.INP. Mỗi dòng chứa một số nguyên là con số cho biết số chuỗi con đối xứng của chuỗi ở dòng tương ứng trong CHUOI.INP. Ví dụ: Dữ liệu vào: Dữ liệu ra: Z 1 TOT 3 NANG 4 16