Bài tập Kỹ thuật lập trình - Nguyễn Duy Phương

Nội dung text: Bài tập Kỹ thuật lập trình - Nguyễn Duy Phương

1. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 2 1 23 199 15 2345 6789 BÀI 1.1.12: SỐ CÓ TỔNG CHỮ SỐ CHIA HẾT CHO 10 Viết chương trình kiểm tra một số có thỏa mãn tính chất tổng chữ số của nó chia hết cho 10 hay không. Dữ liệu vào: Dòng đầu tiên ghi số bộ test. Mỗi bộ test viết trên một dòng một số nguyên dương, ít nhất 2 chữ số nhưng không quá 9 chữ số. Kết quả: Mỗi bộ test viết ra YES hoặc NO tùy thuộc kết quả kiểm tra. Ví dụ: Input Output 3 NO 3333 YES 555555 PTITYES 123455 BÀI 1.1.13: SỐ ĐẸP 3 Một số được coi là đẹp nếu nó là số thuận nghịch, tổng chữ số là số nguyên tố và tất cả các chữ số đều lẻ. Bài toán đặt ra là đếm xem trong một đoạn giữa hai số nguyên cho trước có bao nhiêu số đẹp như vậy. Dữ liệu vào: Dòng đầu tiên ghi số bộ test. Mỗi bộ test viết trên một dòng hai số nguyên dương tương ứng, cách nhau một khoảng trống. Các số đều không vượt quá 9 chữ số. Kết quả: 11
2. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Với mỗi bộ test viết ra số lượng các số thuần nguyên tố tương ứng. Ví dụ Input Output 3 4 23 199 0 2345 6789 311 222222 99999999 BÀI 1.1.14: Hãy viết chương trình tìm số các số tự nhiên N thỏa mãn đồng thời những điều kiện dưới đây (N 231): N là số có K chữ số (K 15). N là số nguyên tố. Đảo ngược các chữ số của N cũng là một số nguyên tố. Tổng các chữ số của N cũng là một số nguyên tố. Mỗi chữ số của N cũng là các số nguyên tố ; Thời gian thực hiện chương trình không quá 1sec. Dữ liệu vào (Input) cho bởi file data.in theo khuôn dạng: Dòng đầu tiên ghi lại số tự nhiên M là số lượng các test (M 100). M dòng kế tiếp ghi lại mỗi dòng một test. Mỗi test bao gồm một số K. Hai số được viết cách nhau mộtPTIT vài khoảng trống. Kết quả ra (Output): ghi lại M dòng trong file ketqua.out, mỗi dòng ghi lại bộ hai số số N, X. Trong đó X là số các số có N chữ số thỏa mãn yêu cầu của bài toán. Ví dự dưới đây minh họa cho file input và output của bài toán. Input.in Output.out 5 2 0 2 3 8 3 4 15 4 5 46 5 7 359 7 12
3. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.1.15: Trong ngày đầu tiên phát hành các số điện thoại di động, công ty viễn thông dự định khuyến mại cho N khách hàng đăng ký trước nhất các số điện thoại loại 1, M khách hàng kế tiếp số điện thoại loại 2 và K khách hàng cuối cùng các số điện thoại loại 3. Các số điện thoại loại 1, loại 2 và loại 3 có tính chất sau: Số loại 3 (Loại 3): là các số điện thoại mà sáu số cuối cùng của nó tạo thành một số thuận nghịch có sáu chữ số. Ví dụ số : 0913.104401. Số loại 2 (Loại 2): là các số điện thoại Loại 3 có tổng sáu số cuối cùng của nó là một số chia hết cho 10. Ví dụ số : 0913.104401. Số loại 1 (Loại 1): là các số điện thoại Loại 2 có tổng sáu số cuối cùng của nó không chứa bất kỳ số 0 nào. Ví dụ số : 0913.686686. Bài toán được đặt ra là cho trước một phương án N, M, K, hãy trả lời “YES” nếu công ty thực hiện được, trả lời “NO” nếu công ty không thực hiện được. Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test là một bộ 3 số N, M, K được ghi trên một dòng. Các số được ghi cách nhau một vài khoảng trống. Output: Với mỗi bộ test, viết ra trên một dòng giá trị “YES” hoặc “NO” tương ứng với phương án thực hiện được, hoặc phương án không thực hiện được. Ví dụ cho Input và Output: INPUT OUTPUT 5 NO 100 100 200 NO 50 150 200PTIT YES 100 50 300 120 YES 50 500 NO 140 50 700 BÀI 1.1.16: Số N nguyên hệ cơ số ACM là những số nguyên thông thường sử dụng các ký hiệu từ 0, 1, ,9 làm ký hiệu của hệ đếm (Ví dụ số 719ACM). Nguyên tắc chung để đổi một số A =(a1, a2, ,aN) ở hệ cơ số ACM sang số ở hệ cơ số 10 được thực hiện như sau: N K10 ai *(i!), trong đó ai chữ số tại vị trí thứ i của ở hệ cơ số ACM . i 1 Ví dụ: 13
4. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 A = 719ACM = 9.(1!) + 1.(2!) + 7.(3!) = 5310 . Nhiệm vụ của bạn là viết một chương trình đọc một số nguyên ở hệ cơ số ACM rồi đổi số đó thành số hệ cơ số 10 . Dữ liệu vào: Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên không lớn hơn 100 là số lượng các bộ dữ liệu. Những dòng tiếp theo chứa các bộ dữ liệu. Mỗi bộ dữ liệu được viết trên một dòng. Mỗi dòng viết một số nhỏ hơn 232 là số ở hệ cơ số ACM . Dữ liệu ra: Với mỗi bộ dữ liệu, ghi ra trên một dòng một số được chuyển đổi. Ví dụ dữ liệu vào Ví dụ dữ liệu ra 6 53 719 1 1 7 15 8 110 8 102 0 8 PTIT 14
5. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 1.2. Các bài tập về mảng và ma trận BÀI 1.2.1: SỐ CẶP BẰNG NHAU TRONG DÃY Viết chương trình đếm các cặp số bằng nhau liên tiếp trong dãy số nguyên. Dữ liệu vào: Dòng đầu tiên ghi số bộ test. Mỗi bộ test có hai dòng: Dòng đầu ghi số phần tử của dãy, không quá 30 Dòng tiếp theo ghi các phần tử của dãy, mỗi phần tử cách nhau một khoảng trống. Các phần tử không quá 100. Kết quả: Ghi ra màn hình Mỗi bộ test viết ra trên một dòng giá trị tổng chữ số tương ứng Ví dụ: Input Output 2 1 4 6 1 3 3 4 PTIT 12 1 2 3 3 3 3 4 4 5 5 5 1 BÀI 1.2.2: ĐẾM CÁC SỐ LỚN HƠN SỐ ĐỨNG TRƯỚC TRONG DÃY Cho một dãy số nguyên dương có n phần tử (2<=n<=50). Hãy liệt kê số các phần tử trong dãy không nhỏ hơn các số đứng trước nó (tính cả phần tử đầu tiên). Dữ liệu vào: Dòng 1 ghi số bộ test 15
6. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Với mỗi bộ test: dòng đầu tiên ghi số n. Dòng tiếp theo ghi n số nguyên dương của dãy (các số không vượt quá 1000). Kết quả: Ghi ra màn hình trên một dòng số các phần tử thỏa mãn. Ví dụ: Input Output 2 5 7 3 3 5 6 8 4 2 9 15 9 8 123 7 11 14 18 21 399 10 5 4 1 2 3 BÀI 1.2.3: ĐOÁN SỐ TIẾP THEO An và Bình chơi trò chơi số học đơn giản. Dãy số mà An đưa ra là A = {1,1,3,4,5,9,7,16,9, }và đố Bình tìm ra số tiếp theo trong dãy đó. Rất nhanh chóng, Bình tìm được số tiếp theo là số 25. Bình đố lại An, nếu cho trước một số k không quá 100, hãy tính số đứng vị trí đó trong dãy đã choPTIT (thứ tự trên dãy tính từ 1). Bạn hãy giúp An tính ra kết quả trên. Dữ liệu vào: Dòng đầu là số bộ test, không quá 20. Mỗi bộ test ghi trên một dòng số nguyên dương k. Kết quả: Với mỗi bộ test, đưa ra trên một dòng giá trị ở vị trí k của dãy. Ví dụ: C.IN Kết quả 3 1 1 4 4 25 10 16
7. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.2.4: TỔNG HAI ĐA THỨC Cho hai đa thức P(x) -bậc n và Q(x) -bậc m có các hệ số nguyên, n và m không quá 100. Hãy viết chương trình tính tổng hai đa thức trên. Dữ liệu vào: Dòng đầu tiên chứa số nguyên N là số bộ dữ liệu ( 1 ≤ N ≤ 10 ). Mỗi bộ dữ liệu gồm 4 dòng: Dòng 1 ghi số n là bậc của P. Dòng 2 ghi n+1 số nguyên tương ứng là hệ số của P từ P0 đến Pn Dòng 3 ghi số m là bậc của Q. Dòng 4 ghi m+ 1 số nguyên tưng ứng là hệ số của Q, từ Q0 đến Qm Kết quả: Ghi ra màn hình Với mỗi bộ dữ liệu vào, in ra kết quả trên hai dòng: Dòng 1 ghi bậc của đa thức tổng. Dòng 2 ghi lần lượt các hệ số của đa thức tổng, tính từ 0. Ví dụ: D.IN Kết quả 1 5 3 2 3 5 2 3 3 1 2 3 4 5 PTIT 1 1 2 -2 3 3 BÀI 1.2.5: TÌM CÁC VỊ TRÍ BẰNG NHAU CỦA HAI MA TRẬN Cho hai ma trận vuông A và B chỉ gồm số nguyên dương cấp n . Hãy viết chương trình tìm ra các vị trí bằng nhau trong hai ma trận (vị trí [i,j] được coi là bằng nhau nếu A[i,j]=B[i,j]). Dữ liệu vào: Dòng đầu tiên ghi số bộ test. Với mỗi bộ test: Dòng đầu tiên ghi số n; n dòng tiếp theo ghi ma trận A; n dòng tiếp theo ghi ma trận B Kết quả (ghi ra màn hình): 17
8. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Với mỗi bộ test ghi ra một số nguyên dương m là số vị trí bằng nhau. m dòng tiếp theo ghi hai giá trị chỉ số của từng cặp (cách nhau một khoảng trống). (Chú ý: các chỉ số đều tính từ 0 đến n-1). Ví dụ: Input Output 1 2 2 0 1 1 1 1 1 1 2 9 1 4 2 BÀI 1.2.6: SỐ FIBONACI THỨ N Dãy Fibonaci được định nghĩa như sau: F(0) = 0, F(1)=1, , F(n)=F(n-1)+F(n-2). Cho trước số nguyên dương n (không quá 45), hãy tính số Fibonaci thứ n. Dữ liệu vào: Dòng 1 ghi số bộ test. Mỗi bPTITộ test ghi trên một dòng số nguyên dương n. Kết quả (ghi ra màn hình): Với mỗi bộ test ghi ra giá trị số Fibonaci thứ n. Ví dụ: Input Output 3 1 1 13 7 55 10 18
9. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.2.7: TÍCH MA TRẬN VỚI CHUYỂN VỊ CỦA NÓ Cho ma trận A chỉ gồm các số nguyên dương cấp n*m . Hãy viết chương trình tính tích của A với ma trận chuyển vị của A. Dữ liệu vào: Dòng đầu tiên ghi số bộ test. Với mỗi bộ test: Dòng đầu tiên ghi hai số n và m là bậc của ma trân a; n dòng tiếp theo, mỗi dòng ghi m số của một dòng trong ma trận A. Kết quả (ghi ra màn hình): Với mỗi bộ test ghi ra ma trận tích tương ứng, mỗi số cách nhau đúng ộm t khoảng trống. Ví dụ: Input Output 1 5 11 2 2 11 25 1 2 3 4 BÀI 1.2.8: SỐ XUẤT HIỆN NHIỀU LẦN NHẤT TRONG DÃY Cho một dãy số nguyên dương khôngPTIT quá 100 phần tử, các giá trị trong dãy không quá 30000. Hãy xác định xem số nào là số xuất hiện nhiều lần nhất trong dãy. Chú ý: trong trường hợp nhiều số khác nhau cùng xuất hiện số lần bằng nhau và là lớn nhất thì in ra tất cả các số đó theo thứ tự xuất hiện trong dãy ban đầu. Dữ liệu vào: Dòng đầu là số bộ test, không quá 20. Mỗi bộ test gồm hai dòng. Dòng đầu ghi số phần tử của dãy, dòng tiếp theo ghi các phần tử của dãy. Kết quả: Ghi ra màn hình Với mỗi bộ test, đưa ra số xuất hiện nhiều lần nhất trong dãy đã cho. Ví dụ: 19
10. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Input Output 2 1 10 1 2 3 4 5 6 7 8 9 0 1 2 3 1 2 3 1 2 3 1 10 1 2 3 4 5 6 7 8 9 0 BÀI 1.2.9: MA TRẬN ĐƠN VỊ Một ma trận vuông A cấp n chỉ gồm các số nguyên dương. A được gọi là ma trận đơn vị nếu tất cả các phần tử trong A đều là 0 hoặc 1. Viết chương trình kiểm tra xem một ma trận có đối xứng hay không. Dữ liệu vào: Dòng đầu tiên ghi số bộ test (không quá 10). Với mỗi bộ test: Dòng đầu tiên ghi số n là bậc của ma trân A; n dòng tiếp theo, mỗi dòng ghi n số của một dòng trong ma trận A. Các giá trị đều không quá 100. Kết quả (ghi ra màn hình): Với mỗi bộ test ghi ra màn hìnhPTIT chữ YES nếu đó đúng là ma trận đơn vị, NO nếu ngược lại. Ví dụ: Input Output 2 NO 2 YES 1 1 1 2 4 1 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 20
11. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.2.10: TỔNG TAM GIÁC Số tam giác thứ n là tổng của n số tự nhiên đầu tiên, T(n) = 1 + + n. Nó cũng chính là số lượng điểm trong một mảng tam giác có cạnh là n, ví dụ như với T(4) thì: X X X X X X X X X X Hãy viết chương trình tính tổng có trọng số của số tam giác: n W(n) k.T(k 1) k 1 Dữ liệu vào: Dòng đầu tiên chứa số nguyên N là số bộ dữ liệu ( 1 ≤ N ≤ 1000 ). Mỗi bộ dữ liệu gồm 1 dòng chứa duy nhất 1 số nguyên n ( 1 ≤ n ≤ 300 ) là số điểm trên cạnh của tam giác. Kết quả: Ghi ra màn hình Với mỗi bộ dữ liệu vào, in ra trên một dòng số thứ tự của bộ dữ liệu (1 đến N), một dấu cách, giá trị của n trong bộ dữ liệu, một dấu cách và tổng có trọng số W(n) của những số tam giác tương ứng với n. Ví dụ: PTIT D.IN Kết quả 4 1 3 45 3 2 4 105 4 3 5 210 5 4 10 2145 10 21
12. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.2.11: ĐỖ XE TỐI ƯU Khi mua sắm trên khu Long Street, Michael thường đỗ xe của mình ở một số vị trí ngẫu nhiên và đi bộ vào cửa hàng. Bạn hãy giúp Michael chọn một chỗ đỗ xe để khoảng cách phải đi bộ khi mua hàng là nhỏ nhất. Long Street có thể coi như là một đường thẳng mà tất cả những điểm mua hàng là các điểm có tọa độ nguyên. Dữ liệu vào: Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 100 là số lượng bộ test. Mỗi bộ test gồm 2 dòng, dòng đầu tiên ghi số cửa hàng n mà Michael muốn qua mua hàng, 1 ≤ n ≤ 20 và dòng thứ hai ghi n số nguyên là tọa độ các điểm này trên phố Long Street, 0 ≤ xi ≤ 99. Kết quả: Với mỗi bộ test, in ra màn hình trên một dòng khoảng cách nhỏ nhất phải đi bộ với chỗ đỗ xe tối ưu. Ví dụ cho Input và Output: Input Ouput 2 152 4 70 24 13 89 37 6 7 30 41 14 39 42 PTIT BÀI 1.2.12: Ta định nghĩa một từ là dãy các kí tự không chứa khoảng trống (space), dấu tab, dấu xuống dòng (‘\n’), dấu về đầu dòng (‘\r’) và dấu kết thúc dòng (‘\0’). Tần xuất xuất hiện của từ W trong tập văn bản D1 và D2, ký hiệu là P(W) được tính theo công thức: N1 (W ) N 2 (W ) P(W ) ; trong đó Ni(W) là số lần xuất hiện từ W trong Di, N(Di) là tổng N(D1 ) N(D2 ) số từ của tập văn bản Di (i=1, 2). 22
13. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Cho hai file văn bản data1.in và data2.in. Sử dụng CTDL Mảng, hãy tìm tập các từ và tần xuất xuất hiện của mỗi từ hoặc xuất hiện trong data1.in hoặc xuất hiện trong data2.in. Tập các từ tìm được ghi lại trong file Ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại số tự nhiên K là số từ W tìm được theo yêu cầu của bài toán. K dòng kế tiếp, mỗi dòng ghi lại một từ W và tần xuất xuất hiện P(W) thỏa mãn yêu cầu của bài toán. W và P(W) được viết cách nhau bởi một vài khoảng trống. Ví dụ với file data1.in và data2.in dưới đây sẽ cho ta file Ketqua.out của bài toán. data1.in data2.in Ketqua.out AB AC AD AE AF AB AC AD AH AK 3 AB AC AD AE AF AB AC AD AH AK AB 0.2 AC 0.2 AD 0.2 BÀI 1.2.13: Ta định nghĩa một từ là dãy các kí tự không chứa khoảng trống (space), dấu tab, dấu xuống dòng (‘\n’), dấu về đầu dòng (‘\r’) và dấu kết thúc dòng (‘\0’). Tần xuất xuất hiện của từ W trong tập văn bản D1 và D2, ký hiệu là P(W) được tính theo công thức: N1 (W ) N 2 (W ) P(W ) ; trong đóPTIT Ni(W) là số lần xuất hiện từ W trong Di, N(Di) là tổng N(D1 ) N(D2 ) số từ của tập văn bản Di (i=1, 2). Cho hai file văn bản data1.in và data2.in. Sử dụng CTDL Mảng, hãy tìm tập các từ và tần xuất xuất hiện của các từ xuất hiện trong file data1.in nhưng không xuất hiện trong file data2.in. Tập các từ tìm được ghi lại trong file Ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại số tự nhiên K là số từ W tìm được theo yêu cầu của bài toán. K dòng kế tiếp, mỗi dòng ghi lại một từ W và tần xuất xuất hiện P(W) thỏa mãn yêu cầu của bài toán. W và P(W) được viết cách nhau bởi một vài khoảng trống. Ví dụ với file data1.in và data2.in dưới đây sẽ cho ta file Ketqua.out của bài toán. 23
14. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 data1.in data2.in Ketqua.out AB AC AD AE AF AB AC AD AH AK 7 AB AC AD AE AF AB AC AD AH AK AB 0.2 AC 0.2 AD 0.2 AE 0.1 AF 0.1 AH 0.1 AK 0.1 BÀI 1.2.14: Ta định nghĩa một từ là dãy các kí tự không chứa khoảng trống (space), dấu tab, dấu xuống dòng (‘\n’), dấu về đầu dòng (‘\r’) và dấu kết thúc dòng (‘\0’). Tần xuất xuất hiện của từ W trong tập văn bản D1 và D2, ký hiệu là P(W) được tính theo công thức: N1 (W ) N 2 (W ) P(W ) ; trong đó Ni(W) là số lần xuất hiện từ W trong Di, N(Di) là tổng N(D1 ) N(D2 ) số từ của tập văn bản Di (i=1, 2). Cho hai file văn bản data1.in và data2.in. Sử dụng CTDL Mảng, hãy tìm tập các từ và tần xuất xuất hiện của mỗi từ đồng thPTITời trong cả hai tập data1.in và data2.in. Tập các từ tìm được ghi lại trong file Ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại số tự nhiên K là số từ W tìm được theo yêu cầu của bài toán. K dòng kế tiếp, mỗi dòng ghi lại một từ W và tần xuất xuất hiện P(W) thỏa mãn yêu cầu của bài toán. W và P(W) được viết cách nhau bởi một vài khoảng trống. Ví dụ với file data1.in và data2.in dưới đây sẽ cho ta file Ketqua.out của bài toán. data1.in data2.in Ketqua.out AB AC AD AE AF AB AC AD AH AK 2 AB AC AD AE AF AB AC AD AH AK AE 0.1 AF 0.1 24
15. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.2.15: Cho tập các số tự nhiên ghi lại trong file data.in theo từng dòng; mỗi dòng ghi lại nhiều nhất 10 số; hai số được viết cách nhau một vài khoảng trống; mỗi số tự nhiên có thể xuất hiện nhiều lần ở những vị trí khác nhau trong file. Ta gọi tần xuất xuất hiện số tự nhiên X N(X ) trong file data.in là P(X ) ; trong đó N(X) là số lần xuất hiện số tự nhiên X trong K file data.in, K là số các số tự nhiên trong file data.in. Sử dụng CTDL mảng, hãy viết chương trình tìm số vừa nguyên tố vừa thuận nghịch X có P(X) lớn nhất đầu tiên tìm được trong file data.in. Ví dụ với file data.in được cho dưới đây, ta tìm được số X = 131 vừa là số nguyên tố, vừa là số thuận nghịch với tần xuất xuất hiện lớn nhất là P(X) = 3/30 = 0.1. data.in 10 131 171 13 37 27 30 23 77 444 10 131 171 20 23 77 23 27 77 444 10 131 171 20 23 77 23 27 77 444 BÀI 1.2.16: Cho tập các số tự nhiên trong file data.in được ghi theo từng dòng, mỗi dòng ghi nhiều nhất 5 số, hai số được viết cách nhau một vài khoảng trống. Biết rằng, mỗi số tự nhiên trong file data.in hoặc là số nguyên tố, hoặc làPTIT số thuận nghịch và có thể xuất hiện nhiều lần ở những vị trí khác nhau trong file. Sử dụng cấu trúc dữ liệu mảng, hãy viết chương trình tách tập các số và đếm số lần xuất hiện của mỗi số trong file data.in thành 3 file ketqua1.out, ketqua2.out, ketqua3.out thỏa mãn những yêu cầu dưới đây. a) File ketqua1.out ghi lại các số nguyên tố nhưng không là số thuận nghịch cùng với số lần xuất hiện của nó trong file data.in; b) File ketqua2.out ghi lại các số thuận nghịch nhưng không là nguyên tố cùng với số lần xuất hiện của nó trong file data.in; c) File ketqua3.out ghi lại các số vừa là số nguyên tố vừa là số thuận nghịch cùng với số lần xuất hiện của nó trong file data.in; d) Khuôn dạng của các file kết quả được qui định như sau: Dòng đầu tiên của mỗi file ghi lại số các số của mỗi file kết quả; 25
16. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Những dòng kế tiếp mỗi dòng ghi lại một số cùng với số lần xuất hiện của nó trong file data.in. Hai số được viết cách nhau một vài khoảng trống. Ví dụ dưới đây minh họa cho các file data.in, ketqua1.out, ketqua2.out và ketqua3.out. Data.in Ketqua1.out Ketqua2.out Ketqua3.out 10007 10009 10801 10901 13831 2 2 2 10007 10009 10801 10901 34543 10007 4 10801 4 13831 2 10007 10009 10801 10901 13831 10009 4 10901 4 34543 2 10007 10009 10801 10901 34543 BÀI 1.2.17: Cho một hình vuông gồm 5 x 5 hình vuông đơn vị như hình vẽ sau: 3 5 1 1 1 5 0 0 3 3 1 0 3 4 3 1 3 4 2 1 1 3 3 1 3 Hãy điền các chữ số từ 0 đến 9 vào mỗi hình vuông đơn vị sao cho những điều kiện sau được thỏa mãn: (i) Đọc từ trái sang phải theo hàng ta nhận được năm số nguyên tố có năm chữ số; (ii) Đọc từ trên xuống dướiPTIT theo cột ta nhận được năm số nguyên tố có năm chữ số; (iii) Đọc theo hai đường chéo chính từ trái sang phải ta nhận được hai số nguyên tố có năm chữ số; (iv) Tổng các chữ số trong mỗi số nguyên tố đều bằng S cho trước (trong ví dụ trên S=11). Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test viết trên một dòng một bộ đôi hai số S, T tương ứng với tổng các chữ số trong mỗi số nguyên tố và giá trị ô vuông trên cùng góc trái. Output: Với mỗi bộ test, output đưa ra một số duy nhất là số các lời giải của bài toán. Mỗi lời giải của bài toán là một hình vuông gồm 5 5 hình vuông đơn vị. Hai lời giải được xem là khác nhau nếu tồn tại một ô vuông đơn vị ở cùng một vị trí có giá trị khác nhau. 26
17. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Ví dụ cho Input và Output của bài toán: INPUT OUTPUT 3 5 11 3 0 11 9 0 11 8 BÀI 1.2.18: Trò chơi Rubik trên mặt phẳng có thể được mô tả bằng dãy các số từ 1 đến 8 và được chia thành hai hàng. Ta qui ước trạng thái khởi đầu S của Rubik là trạng thái trong hình 1. Người ta đã chứng minh được rằng, từ trạng thái khởi đầu S ta có thể dịch chuyển thành trạng thái T bất kỳ trên các thao tác A, B, C dưới đây: A : Đổi hàng trên cho hàng dưới (Hình 2). B : Tạo nên một hoán vị vòng trên mỗi hàng (Hình 3). C : Quay 90 độ 4 ô ở giữa (Hình 4) Hình 1. Trạng thái khởi đầu S 1 2 3 4 8 7 6 5 PTIT Hình 2. Thao tác A Hình 3. Thao tác B Hình 4. Thao tác C 8 7 6 5 4 1 2 3 1 7 2 4 1 2 3 4 5 8 7 6 8 6 3 5 Yêu cầu: Cho trước một trạng thái kết thúc T. Hãy chuyển S thành T sao cho số các phép A, B, C thực hiện là ít nhất. Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được tổ chức trên một dòng là giá trị trạng thái kết thúc T. Output: Với mỗi bộ test, viết ra trên một dòng số các bước A, B, C ít nhất. 27
18. BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 INPUT OUTPUT 2 7 2 6 8 4 5 7 3 1 0 1 2 3 4 5 6 7 8 1.3. Các bài tập về xâu ký tự BÀI 1.3.1: PHÉP CỘNG SỐ NGUYÊN Viết chương trình cộng hai số nguyên dương bất kỳ (không quá 256 chữ số). Dữ liệu vào: Dòng 1 ghi số bộ test. Mỗi bộ test gồm 2 dòng, mỗi dòng ghi một số nguyên dương Kết quả (ghi ra màn hình): Với mỗi bộ test ghi ra một số nguyên dương là tổng hai số đã cho (số này cũng không quá 256 chữ số). Ví dụ: PTIT Input Output 3 112 12 10100 100 121212121257800190 1212 8888 121212121212121212 45678978 28