Bài tập Kỹ thuật lập trình

172 trang phuongnguyen 4010

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài tập Kỹ thuật lập trình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_tap_ky_thuat_lap_trinh.pdf

Nội dung text: Bài tập Kỹ thuật lập trình

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA CÔNG NGHỆ THÔNG TIN 1 BÀI TẬP KỸ THUẬT LẬP TRÌNH PTIT CHỦ BIÊN: TS. NGUYỄN DUY PHƯƠNG Hà Nội, 2013
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 MỤC LỤC I. Lập trình với các cấu trúc dữ liệu cơ bản 4 1.1. Các bài tập với dữ liệu kiểu số nguyên 4 1.2. Các bài tập về mảng và ma trận 15 1.3. Các bài tập về xâu ký tự 28 1.4. Các bài tập về file và cấu trúc 30 II. Lập trình dựa vào kỹ thuật duyệt và đệ qui 36 1.5. Kỹ thuật vét cạn 36 1.6. Kỹ thuật sinh kế tiếp 46 1.7. Kỹ thuật quay lui 54 1.8. Kỹ thuật nhánh cận 65 1.9. Kỹ thuật qui hoạch động 67 III. Lập trình dựa vào ngăn xếp, hàng đợi 72 1.10. Kỹ thuật xử lý trên ngăn xếp 72 1.11. Kỹ thuật xử lý trên hàng đợi 81 1.12. Kỹ thuật xử lý trên danh sách liên kết 86 1.13. Khử đệ qui dựa vào ngăn xếp và danh sách liên kết 94 IV. Lập trình trên cây nhị phânPTIT 98 4.1. Cây nhị phân 98 4.2. Cây nhị phân tìm kiếm 100 4.3. B-Cây (thuộc tìm kiếm bộ nhớ ngoài) 106 4.4. Cây cân bằng 106 4.5. Cây đỏ đen 107 4.6. Cây quyết định 108 4.7. Cây mã tiền tố 108 V. Lập trình trên Đồ thị 109 5.1. Biểu diễn đồ thị 109 5.2. Kỹ thuật DFS 111 2
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 5.3. Kỹ thuật BFS 115 5.4. Đồ thị Euler 128 5.5. Đồ thị Hamilton 137 5.6. Cây khung đồ thị 137 5.7. Bài toán tìm đường đi ngắn nhất 147 5.8. Bài toán luồng cực đại trên mạng 150 5.9. Đồ thị hai phía 153 VI. Các kỹ thuật sắp xếp và tìm kiếm 155 6.1. Các phương pháp sắp xếp cơ bản 155 6.2. Quicksort 161 6.3. Heapsort 163 6.4. Mergesort 164 6.5. Sắp xếp bằng cơ số 165 6.6. Các phương pháp tìm kiếm cơ bản 166 6.7. Phép băm 169 6.8. Tìm kiếm dựa vào cơ số 170 TÀI LIỆU THAM KHẢO 172 PTIT 3
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 I. Lập trình với các cấu trúc dữ liệu cơ bản 1.1. Các bài tập với dữ liệu kiểu số nguyên BÀI 1.1.1: TỔNG CHỮ SỐ Viết chương trình tính tổng chữ số của một số không quá 9 chữ số. 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 số nguyên tương ứng 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 10 1234 2 1000001 BÀI 1.1.2: BẮT ĐẦU VÀ KẾT THÚCPTIT Viết chương trình kiểm tra một số nguyên dương bất kỳ (2 chữ số trở lên, không quá 9 chữ số) có chữ số bắt đầu và kết thúc bằng nhau 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 số nguyên dương tương ứng cần kiểm tra Kết quả: Ghi ra màn hình Mỗi bộ test viết ra YES hoặc NO, tương ứng với bộ dữ liệu vào Ví dụ: 4
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Input Output 2 YES 12451 NO 1000012 BÀI 1.1.3: BỘI SỐ CHUNG NHỎ NHẤT Viết chương trình tính bội số chung nhỏ nhất của hai số nguyên dương không quá 7 chữ số. 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 Kết quả: Ghi ra màn hình Mỗi bộ test viết ra trên một dòng giá trị bội số chung nhỏ nhất của hai số đó Ví dụ Input PTITOutput 2 60 30 20 98754568 222222 8888888 BÀI 1.1.4: 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 quá 9 chữ số. 5
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 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 YES 123455 BÀI 1.1.5: SỐ ĐẸP 1 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 toá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ả: 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 PTITOutput 3 4 23 199 0 2345 6789 311 222222 99999999 BÀI 1.1.6: SỐ ĐẸP 2 Một số được coi là đẹp nếu nếu nó có tính chất thuận nghịch và tổng chữ số chia hết cho 10. Bài toán đặt ra là cho trước số chữ số. Hãy đếm xem có bao nhiêu số đẹp với số chữ số như vậy. Dữ liệu vào: Dòng đầu tiên ghi số bộ test. 6
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Mỗi bộ test viết trên một dòng số chữ số tương ứng cần kiểm tra (lớn hơn 1 và nhỏ hơn 10) Kết quả: Ghi ra màn hình Mỗi bộ test viết ra số lượng số đẹp tương ứng Ví dụ Input Output 2 1 2 90 5 BÀI 1.1.7: TRÒ CHƠI ĐOÁN SỐ Trong lúc rảnh rỗi, hai bạn sinh viên quyết định chơi trò đoán số giống học sinh cấp 1. Mỗi bạn nghĩ ra hai con số nguyên không âm sau đó viết ra tổng và hiệu của chúng (cũng là các số nguyên không âm). Công việc của bạn kia là xác định hai con số ban đầu. Ở một số lượt chơi, một bạn có thể cố tình đưa ra một cặp giá trị không thể là tổng và hiệu của hai số nguyên nào cả. PTIT Viết chương trình giúp tính toán nhanh ra kết quả cho bài toán trên. Dữ liệu vào: Dòng đầu là số bộ test, không quá 200. Mỗi dòng sau chứa hai số nguyên không âm s và d lần lượt là giá trị tổng và hiệu hai số. Cả hai số s và d đều không quá 104. Kết quả: Ghi ra màn hình Với mỗi bộ dữ liệu, đưa ra hai số ban đầu, số lớn viết trước, cách nhau một khoảng trống. Nếu không thể có cặp số như vậy thì in ra “impossible” Ví dụ 7
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Input Output 2 30 10 40 20 impossible 20 40 BÀI 1.1.8: MÁY BÁN HÀNG TỰ ĐỘNG Khi mua hàng bằng máy bán hàng tự động, người mua sẽ trả bằng một số tiền chẵn lớn hơn hoặc bằng giá của sản phẩm. Máy sẽ tính toán để trả lại số tiền thừa cho người mua. Giả sử trong máy chỉ có ba mệnh giá tiền là 1 dollar, 5 dollar và 10 dollar với quy ước mỗi lần trả chỉ được phép dùng ít hơn 5 tờ 1 dollar và ít hơn 2 tờ 5 dollar. Hãy viết chương trình tính số tiền mỗi loại mà máy bán hàng tự động phải trả lại cho người mua. Dữ liệu vào: Dòng đầu tiên là số bộ test, mỗi bộ test ghi trên một dòng hai số nguyên không âm là giá của sản phẩm và tổng số tiền người mua đưa vào. Cả hai giá trị này đều không vượt quá 105. Kết quả: Với mỗi bộ test, viết ra biểu diPTITễn số tiền cần trả của máy bán hàng tự động theo mẫu trong bộ test ví dụ dưới đây. (Chú ý: giữa các số và các dấu luôn có đúng một khoảng trống, cả với dấu =, dấu * hoặc dấu +) Ví dụ cho Input và Output: Input Output 3 28 = 2 * 10 + 1 * 5 + 3 * 1 72 100 163 = 16 * 10 + 0 * 5 + 3 * 1 37 200 45 = 4 * 10 + 1 * 5 + 0 * 1 5 50 8
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.1.9: (*) BIỂU DIỄN SỐ BẰNG QUE DIÊM Một trong những cách biểu diễn số khá phổ biến trong các đồng hồ điện tử là sử dụng que diêm. Các ký tự số sẽ được biểu diễn như sau: Với một số lượng que diêm cho trước, hãy các định số nhỏ nhất và số lớn nhất mà bạn có thể biểu diễn được. Chú ý: Bạn không được phép để thừa que diêm nào khi xếp. Các số biểu diễn không được bắt đầu bằng số 0 Dữ liệu vào: 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 số nguyên duy nhất không lớn hơn 100 là số que diêm bạn có. Kết quả: Với mỗi bộ test, output đưa ra hai số nguyên theo thứ tự là số nhỏ nhất và số lớn nhất có thể biểu diễn bởi số que diêm cho bởi input (mỗi số cách nhau một khoảng trống). Ví dụ cho Input và Output: PTIT Input Output 4 7 7 3 6 111 6 8 711 7 108 7111111 15 9
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.1.10: ĐẾM SỐ CHÍNH PHƯƠNG TRONG ĐOẠN Viết chương trình đếm trong một đoạn giữa hai số nguyên có bao nhiêu số chính phươ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 hai số nguyên dương tương ứng, cách nhau một khoảng trống. Các số đều không quá 9 chữ số. Kết quả: Ghi ra màn hình Mỗi bộ test viết ra trên một dòng giá trị số các số chính phương đếm được. Ví dụ: Input Output 2 10 23 199 34 2345 6789 BÀI 1.1.11: SỐ THUẦN NGUYÊN TỐ Một số được coi là thuần nguyên tố nếu nó là số nguyên tố, tất cả các chữ số là nguyên tố và tổng chữ số của nó cũng là mộtPTIT số nguyên tố. Bài toá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ố thuần nguyên tố. 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ả: Ghi ra màn hình Mỗi bộ test viết ra số lượng các số thuần nguyên tố tương ứng. Ví dụ Input Ouput 10
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 2 1 23 199 15 2345 6789 BÀ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 quá 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 BÀ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 toá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
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 BÀ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à các số nguyên tố ; Thời gian thực hiện chương trình không quá 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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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 khá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 toán được đặt ra là cho trước một phương á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 án thực hiện được, hoặc phương á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 BÀ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
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
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 BÀ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 BÀ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 cá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
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 BÀ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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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 BÀ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
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 BÀ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 quá 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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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ố cách nhau đúng ộm t khoảng trống. Ví dụ: Input Output 1 5 11 2 2 11 25 1 2 3 4 BÀ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 quá 100 phần tử, các giá trị trong dãy không quá 30000. Hãy xá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
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 BÀ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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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 giá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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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à cá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 độ cá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 BÀ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
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 BÀ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
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 BÀ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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀ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 BÀ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 tá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
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 BÀ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
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 BÀ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 thá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 tá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ố các bước A, B, C ít nhất. 27
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ự BÀ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
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.3.2: DANH SÁCH ĐIỆN THOẠI NHẤT QUÁN Cho một danh sách các số điện thoại, hãy xác định danh sách này có số điện thoại nào là phần trước của số khác hay không? Nếu không thì danh sách này được gọi là nhất quán. Giả sử một danh sách có chứa các số điện thoại sau: - Số khẩn cấp: 911 - Số của alice: 97 625 999 - Số của Bob: 91 12 54 26 Trong trường hợp này, ta không thể gọi cho Bob vì tổng đài sẽ kết nối bạn với đường dây khẩn cấp ngay khi bạn quay 3 số đầu trong số của Bob, vì vậy danh sách này là không nhất quán. Dữ liệu vào: Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 40 là số lượng bộ test. Mỗi bộ test sẽ bắt đầu với số lượng số điện thoại n được ghi trên một dòng, 1 ≤ n ≤ 10000. Sau đó là n dòng, mỗi dòng ghi duy nhất 1 số điện thoại. Một số điện thoại là một dãy không quá 10 chữ số. Kết quả: Với mỗi bộ dữ liệu vào, in ra “YES” nếu danh sách nhất quán và “NO” trong trường hợp ngược lại. Ví dụ cho Input và Output: Input PTITOutput 2 NO 3 YES 911 97625999 91125426 5 113 12340 123440 12345 98346 29
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.3.3: CHUẨN HÓA XÂU HỌ TÊN Một xâu họ tên được coi là viết chuẩn nếu chữ cái đầu tiên mỗi từ được viết hoa, các chữ cái khác viết thường. Các từ cách nhau đúng ộm t dấu cách và không có khoảng trống thừa ở đầu và cuối xâu. Hãy viết chương trình đưa các xâu họ tên về dạng chuẩn. Dữ liệu vào: Dòng 1 ghi số bộ test. Mỗi bộ test ghi trên một dòng xâu ký tự họ tên, không quá 80 ký tự. Kết quả (ghi ra màn hình): Với mỗi bộ test ghi ra xâu ký tự họ tên đã chuẩn hóa. Ví dụ: Input Output 3 Nguyen Van Nam nGuYEN vAN naM Tran Trung Hieu tRan TRUNG hiEU Vo Le Hoa Binh vO le hOA bINh 1.4. Các bài tập về file và cấu trúc BÀI 1.4.1: ĐẾM TỪ KHÁC NHAU Viết chương trình đếm số từ khác nhauPTIT của một file văn bản. Dữ liệu vào: File: A.IN Gồm nhiều dòng, chỉ bao gồm các chữ cái. Kết quả: Ghi ra màn hình Viết ra số từ khác nhau trong file. Ví dụ: A.IN Kết quả Xin chao cac ban 8 Xin moi cac ban tap trung hoc tap 30
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 1.4.2: ĐẾM SỐ NGUYÊN TỐ KHÁC NHAU Cho một file văn bản chỉ bao gồm các số nguyên không quá 9 chữ số. Viết chương trình đếm xem trong file đó có bao nhiêu số nguyên tố khác nhau. Dữ liệu vào: File: B.IN Gồm nhiều dòng, chỉ bao gồm các số nguyên, cách nhau một hoặc một vài khoảng trống. Kết quả: Ghi ra màn hình Viết ra số các số nguyên tố khác nhau. Ví dụ: B.IN Kết quả 11 13 14 16 18 21 13 23 99 88 77 66 4 13 13 13 13 23 23 23 13 24 25 26 27 28 97 BÀI 1.4.3: TÌM TỪ THUẬN NGHỊCH DÀI NHẤT TRONG FILE VĂN BẢN Cho một file văn bản bất kỳ. Hãy tìm ra từ thỏa mãn tính chất thuận nghịch có độ dài lớn nhất trong file đó và cho biết từ đóPTIT xuất hiện bao nhiêu lần. Nếu có nhiều từ cùng có độ dài lớn nhất thì in ra tất cả các từ đó theo thứ tự xuất hiện trong file ban đầu. Dữ liệu vào: File C.IN Gồm một đoạn văn bản bất kỳ. Không quá 1000 từ. Kết quả (ghi ra màn hình): Ghi ra trên một dòng từ thuận nghịch có độ dài lớn nhất và số lần xuất hiện của nó. Nếu có nhiều từ cùng có độ dài lớn nhất thì các từ được liệt kê theo thứ tự xuất hiện ban đầu. Ví dụ: C.IN KẾT QUẢ 31
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 AAA BAABA HDHDH ACBSD SRGTDH DDDDS HDHDH 3 DUAHD AAA AD DA HDHDH AAA AAA AAA AAA DDDAS HDHDH HDH AAA AAA AAA AAA AAA AAA AAA AAA DHKFKH DHDHDD HDHDHD DDDHHH HHHDDD TDTD BÀI 1.4.4: TÌM TỪ DÀI NHẤT TRONG FILE Cho một file văn bản bất kỳ. Hãy tìm ra từ có độ dài lớn nhất trong file. Nếu có nhiều từ khác nhau có độ dài bằng nhau và bằng giá trị lớn nhất thì in ra tất cả các từ đó theo thứ tự xuất hiện trong file dữ liệu vào (nhưng một từ dù xuất hiện nhiều lần cũng chỉ được liệt kê một lần). Dữ liệu vào: File D.IN Gồm một đoạn văn bản bất kỳ. Không quá 1000 từ. Kết quả: Ghi ra màn hình từ dài nhất và độ dài của nó, cách nhau một khoảng trống. Nếu có nhiều từ như vậy thì liệt kê lần lượt các từ theo thứ tự xuất hiện trong file ban đầu. Ví dụ: D.IN KẾT QUẢ Tiet hoc cuoi cung da ket thuc. MonPTIT hoc Tin hoc co so 2 thuc. 5 da ket thuc. Cac ban co gang on tap tot de thi dat ket qua nhieu 5 cao. Chuc cac ban ngay cang gat hai duoc nhieu thanh thanh 5 cong tren con duong da chon duong 5 BÀI 1.4.5: TÌM TỪ THUẬN NGHỊCH DÀI NHẤT TRONG FILE VĂN BẢN Cho một file văn bản bất kỳ. Hãy tìm ra từ thỏa mãn tính chất thuận nghịch có độ dài lớn nhất trong file đó và cho biết từ đó xuất hiện bao nhiêu lần. Nếu có nhiều từ cùng có độ dài lớn nhất thì in ra tất cả các từ đó theo thứ tự xuất hiện trong file ban đầu. Dữ liệu vào: File E.IN 32
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Gồm một đoạn văn bản bất kỳ. Không quá 1000 từ. Kết quả (ghi ra màn hình): Ghi ra trên một dòng từ thuận nghịch có độ dài lớn nhất và số lần xuất hiện của nó. Nếu có nhiều từ cùng có độ dài lớn nhất thì các từ được liệt kê theo thứ tự xuất hiện ban đầu. Ví dụ: E.IN KẾT QUẢ AAA BAABA HDHDH ACBSD SRGTDH DDDDS HDHDH 3 DUAHD AAA AD DA HDHDH AAA AAA AAA AAA DDDAS HDHDH HDH AAA AAA AAA AAA AAA AAA AAA AAA DHKFKH DHDHDD HDHDHD DDDHHH HHHDDD TDTD BÀI 1.4.6: SẮP XẾP THÍ SINH Hãy sắp xếp danh sách thí sinh đã có trong file theo tổng điểm giảm dần. Mỗi thí sinh gồm các thông tin: Mã thí sinh: là một số nguyên, tự động tăng. Tính từ 1. Tên thí sinh, ngày sinh Điểm môn 1, điểm môn 2, điPTITểm môn 3 Dữ liệu vào: File: F.IN Dòng đầu chứa số thí sinh. Mỗi thí sinh viết trên 3 dòng: Dòng 1: Tên thí sinh Dòng 2: Ngày sinh Dòng 3,4,5: 3 điểm thi tương ứng. Các điểm thi đều đảm bảo hợp lệ (từ 0 đến 10). Kết quả: Ghi ra màn hình In ra danh sách thí sinh đã sắp xếp theo tổng điểm giảm dần. Nếu 2 thí sinh bằng điểm nhau thì thí sinh nào xuất hiện trước trong file sẽ viết trước. Mỗi thí sinh viết trên một dòng gồm: mã, tên, ngày sinh và tổng điểm. Các thông tin cách nhau đúng 1 khoảng trống. Điểm tổng được làm tròn đến 1 số sau dấu phẩy. 33
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Ví dụ F.IN Kết quả 3 2 Nguyen Van B 1/9/1994 26.5 Nguyen Van A 1 Nguyen Van A 12/12/1994 16.0 12/12/1994 3 Nguyen Van C 6/7/1994 14.0 3.5 7.0 5.5 Nguyen Van B 1/9/1994 7.5 9.5 9.5 Nguyen Van C 6/7/1994 4.5 4.5 5.0 BÀI 1.4.7: SẮP XẾP MẶT HÀNGPTIT Hãy sắp xếp danh sách các mặt hàng đã có trong file theo lợi nhuận giảm dần. Mỗi mặt hàng gồm các thông tin: Mã mặt hàng: là một số nguyên, tự động tăng. Tính từ 1. Tên mặt hàng, nhóm hàng: là các xâu ký tự Giá mua, giá bán: là các số thực (không quá 9 chữ số) Dữ liệu vào: File: H.IN Dòng đầu chứa số mặt hàng. Mỗi mặt hàng viết trên 4 dòng: Dòng 1: Tên mặt hàng Dòng 2: Nhóm hàng Dòng 3: Giá mua. Dòng 4: Giá bán Kết quả: Ghi ra màn hình 34
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 In ra danh sách mặt hàng đã sắp xếp theo lợi nhuận giảm dần (lợi nhuận tính bằng giá bán trừ đi giá mua). Nếu 2 mặt hàng lợi nhuận bằng nhau thì mặt hàng nào xuất hiện trước trong file sẽ viết trước. Mỗi mặt hàng viết trên một dòng gồm: mã, tên, nhóm hàng và lợi nhuận. Các thông tin cách nhau đúng 1 khoảng trống. Ví dụ D.IN Kết quả 3 2 Tu lanh Side by Side Dien lanh 7699 May tinh SONY VAIO 1 May tinh SONY VAIO Dien tu 1299 Dien tu 3 Banh Chocopie Tieu dung 10.5 16400 17699 Tu lanh Side by Side Dien lanh 18300 25999 Banh Chocopie Tieu dung 27.5 37 PTIT 35
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 II. Lập trình dựa vào kỹ thuật duyệt và đệ qui 1.5. Kỹ thuật vét cạn BÀI 2.1.1: BÀI TOÁN CỔ: VỪA GÀ VỪA CHÓ Vừa gà vừa chó, bó lại cho tròn 36 con, một trăm chân chẵn. Hỏi số con mỗi loại. Hãy sử dụng phương pháp vét cạn để giải bài toán. Dữ liệu vào: Số con 36. Số chân 100. Kết quả: Ghi ra màn hình số con gà, số con chó. Mỗi loại một dòng. BÀI 2.1.2: TÌM CỰC ĐẠI CHO HÀM SỐ Viết chương trình tìm X = (x1, x2, ,xn ) và giá trị f(X) của hàm 푛 ( 1, 2, , 푛) = ∑푖=1 푖 푖 đạt giá trị lớn nhất. Trong đó, 푛 = ( 1, 2, , 푛) ∈ = {∑푖=1 푖 푖 ≤ ; 푖 ∈ {0,1}} , ci, ai, b là các số nguyên dương, n £ 100. Dữ liệu vào: PTIT Dữ liệu vào n, cj, aj, b được cho trong file data.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên n và b. Hai số được ghi cách nhau bởi một vài ký tự trống; Dòng kế tiếp ghi lại n số c i (i=1, 2, , n ). Hai số được ghi cách nhau bởi một vài ký tự trống; Dòng cuối cùng ghi lại n số a i ( i = 1, 2, ,n). Hai số được ghi cách nhau bởi một vài ký tự trống. Kết quả: Giá trị tối ưu f(x1,x2, ,xn) và phương án tối ưu X = (x1 , x2, ,xn) tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: 36
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Dòng đầu tiên ghi lại giá trị tối ưu f(x1,x2, ,xn ); Dòng kế tiếp ghi lại phương án tối ưu X = (x1, x2, ,xn ). Hai phần tử khác nhau của X được ghi cách nhau bởi một vài khoảng trống. Ví dụ: Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán: Data.in Ketqua.out 4 10 12 5 1 9 3 0 0 1 1 5 3 6 4 BÀI 2.1.3: LIỆT KÊ DÃY CON Cho dãy A[] gồm N số tự nhiên khác nhau và số tự nhiên K. Hãy viế t chương trình liệt kê tất cả các dãy con của dãy số A[] sao cho tổng các phần tử trong dãy con đó đúng bằng K. Dữ liệu vào: Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các số của dãy số A[] và số tự nhiên K, hai số được viết cách nhau bởiPTIT một vài khoảng trống; Dòng kế tiếp ghi lại N số của dãy số A[], hai số được viết cách nhau một vài khoảng trống. Kết quả: Các dãy con thoả mãn điều kiện tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số các dãy con có tổng các phần tử đúng bằng K tìm được; Những dòng kế tiếp mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Ví dụ: 37
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Ví dụ dưới đây sẽ minh hoạ cho file dayso.in và ketqua.out của bài toán. Dayso.in ketqua.out 7 50 7 5 10 15 20 25 30 35 20 30 15 35 5 20 25 5 15 30 5 10 35 5 10 15 20 5 10 15 20 BÀI 2.1.4: TỔ HỢP Một tổ hợp chập k của n là một tập con k phần tử của tập n phần tử. Chẳng hạn tập {1,2,3,4} có các tổ hợp chập 2 là: {1,2}, {1,3, {1,4, {2,3}, {2,4}, {3,4}. Vì trong tập hợp các phần tử không phân biệt thứ tự nên tập {1,2} cũng là tập {2,1} và do đó, ta coi chúng chỉ là một tổ hợp. Bài toán đặt ra cho chúng ta là hãy xác định tất cả các tổ hợp chập k của tập n phần tử. Để đơn giản ta chỉ xét bài toán tìm cácPTIT tổ hợp của tập các số nguyên từ 1 đến n. Đối với một tập hữu hạn bất kì, bằng cách đánh số thứ tự của các phần tử,ta cũng đưa được về bài toán đối với tập các số nguyên từ 1 đến n. Dữ liệu vào: File input gồm: dòng đầu ghi 2 số nguyên dương n, k cách nhau bởi dấu cách. Kết quả: File output ghi mỗi dòng một tổ hợp k của n phần tử. 38
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.1.5: CHỈNH HỢP LẶP Chỉnh hợp lặp chập k của n là một dãy k thành phần, mỗi thành phần là một phần tử của tập n phần tử, có xét đến thứ tự và không yêu cầu các thành phần khác nhau. Một ví dụ dễ thấy nhất của chỉnh hợp lặp là các dãy nhị phân. Một dãy nhị phân độ dài m là một chỉnh hợp lặp chập m của tập 2 phần tử {0,1}. Chẳng hạn 101 là một dãy nhị phân độ dài 3. Ngoài ra ta còn có 7 dãy nhị phân độ dài 3 nữa là 000, 001, 010, 011, 100, 110, 111. Vì có xét thứ tự nên dãy 101 và dãy 011 là 2 dãy khác nhau. Dữ liệu vào: File input gồm: dòng đầu ghi 2 số nguyên dương n, k cách nhau bởi dấu cách. Kết quả: File output ghi mỗi dòng một chỉnh hợp lặp chập k của n phần tử. BÀI 2.1.6: CHỈNH HỢP KHÔNG LẶP Khác với chỉnh hợp lặp là các thành phần được phép lặp lại,tức là có thể giống nhau, chỉnh hợp không lặp chập k của tập n phần tử cũng là một dãy k thành phần lấy từ tập n phần tử có xét thứ tự nhưng các thành phần không được phép giống nhau. Chẳng hạn có n người, một cách chọn ra k người để xếp thành một hàng là một chỉnh hợp không lặp chập k của n. Một trường hợp đặc biệt của chỉnh PTIThợp không lặp là hoán vị. Hoán vị của một tập n phần tử là một chỉnh hợp không lặp chập n. Nói một cách trực quan thì hoán vị của tập n phần tử là phép thay đổi vị trí của các phần tử (do đó mới gọi là hoán vị). Dữ liệu vào: File input gồm: dòng đầu ghi 2 số nguyên dương n, k cách nhau bởi dấu cách. Kết quả: File output ghi mỗi dòng một chỉnh hợp không lặp chập k của n phần tử. BÀI 2.1.7: TÌM 2 SỐ NGUYÊN TỐ Tìm 2 số nguyên tố thỏa mãn khi biết n: n = p*q. 39
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Dữ liệu vào (nhập từ bàn phím): n là số nguyên dương. Kết quả: In ra màn hình 2 số p, q cách nhau bởi dấu cách. BÀI 2.1.8: TÌM NGHIỆM PHƯƠNG TRÌNH Tìm nghiệm nguyên của phương trình: ax+by = c, với a,b,c là các số nguyên. Dữ liệu vào (nhập từ bàn phím): Các số nguyên a,b,c. Kết quả: In ra màn hình các nghiệm thỏa mãn, mỗi dòng 2 số x,y cách nhau bởi dấu cách. BÀI 2.1.9: TÌM SỐ LỚN NHẤT TRONG DÃY SỐ CHO TRƯỚC Cho một dãy số nguyên bất kỳ, hãy tìm ra số lớn nhất. Dữ liệu vào (nhập từ bàn phím): Dãy số nguyên, các số cách nhau bởi dấu cách, kết thúc nhập bởi Enter. Kết quả: In ra màn hình số lớn nhất. PTIT BÀI 2.1.10: BÀI TOÁN CÁI TÚI Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được. Dữ liệu vào: 40
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 File input: dòng đầu ghi n, M là số nguyên dương, dòng thứ hai ghi trọng lượng của n mặt hàng wi , cách nhau bởi dấu cách, dòng thứ 3 ghi giá trị của n mặt hàng ci . Kết quả: File output ghi phương án tối ưu nhất thứ tự các mặt hàng mang đi được. BÀI 2.1.11: ĐẶT DẤU NGOẶC Cho số nguyên dương n (n có 5 cách: 1. ((( ))) 2. (( ) ( )) 3. (( ))() 4. ()(( )) 5. ()()() BÀI 2.1.12: TÌM SỐ NGUYÊN DƯƠNG NHỎ NHẤT Cho n (n<=10) số nguyên dương a1,a2, ,an (ai<=10^9). Tìm số nguyên dương m nhỏ nhất sao cho m không phân tích được dưới dạng tổng của một số các số (mỗi số sử dụng không quá 1 lần) thuộc n số trên. VD: n=4, A= (1,2,3,4) kết quả ra sẽ là 13. PTIT BÀI 2.1.13: BÀI TOÁN 36 SĨ QUAN Bài toán 36 sĩ quan là bài toán tổ hợp nổi tiếng do nhà toán học Thụy Sĩ Ơle đưa ra vào thế kỷ XVIII. Nội dung bài toán như sau: Có 36 sĩ quan thuộc 6 loại quân hàm, từ 6 đơn vị khác nhau. Hãy tìm cách xếp thành đội hình 6 hàng ngang, 6 hàng dọc thế nào cho trên mỗi hàng ngang, hàng dọc chỉ có các sĩ quan không cùng quân hàm và cùng đơn vị. BÀI 2.1.14: ĐẢO CHỮ CÁI Bạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái. Ví dụ: Cho từ “abc”, chương tr ình của bạn phải đưa ra được các từ "abc", "acb", "bac", 41
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 "bca", "cab" và "cba" (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho). Dữ liệu vào: Dữ liệu vào được cho trong tệp input.txt chứa một số từ. Dòng đầu tiên là một số tự nhiên cho biết số từ được cho ở dưới. Mỗi dòng tiếp theo chứa một từ. Trong đó, một từ có thể chứa cả chữ cái thường hoặc hoa từ A đ ến Z. Các chữ thường và hoa được coi như là khác nhau. Một chữ cái nào đó có thể xuất hiện nhiều hơn một lần. Kết quả: Với mỗi từ đã cho trong file Input.txt, kết quả nhận được ra file Output.txt phải chứa tất cả các từ khác nhau được sinh từ các chữ cái của từ đó. Các từ được sinh ra từ một từ đã cho phải được đưa ra theo thứ tự tăng dần của bảng chữ cái. Ví dụ: Input.txt Output.txt 2 abc abc acb acba bac bca cab cba PTITaabc aacb abac abca acab acba baac baca bcaa caab caba cbaa 42
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.1.15: TẠO MA TRẬN SỐ Cho trước số nguyên dương N bất kỳ. H ãy viết thuật toán và chương trình để tạo lập bảng NxN phần tử nguyên dương theo quy luật được cho trong ví dụ sau: 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 2 4 4 8 12 2 4 6 5 10 2 4 6 8 6 12 4 6 8 10 Thực hiện chương trình đó trên máy với N=12, đưa ra màn hình ma trận kết quả (có dạng như trong ví dụ). BÀI 2.1.16: DÃY SỐ NGUYÊN Dãy cá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? Bạn hãy viết chương trình để tính toán.PTIT Tổng quát bài toá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. BÀI 2.1.17: MÃ NHỊ PHÂN GRAY Trong giờ học môn Điện tử số về mã Gray, MĐ chợt nảy sinh ra một bài toán để code. Bài toán rất đơn giản như sau: In ra lần lượt bảng mã gray n-bit. Mã Gray là mã nhị phân mà hai mã liền kề trong bảng mã chỉ khác nhau một bit. Các giá trị ở nửa sau của bảng mã có sự đối xứng với nửa đầu của bảng mã theo thứ tự ngược lại, ngoại trừ bit cao nhất bị đảo giá trị (bit cao nhất là bit ngoài cùng bên trái). Tính chất đối xứng này vẫn đúng cho các bit thấp hơn trong mỗi nửa, mỗi phần tư, của bảng mã. 43
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Dữ liệu vào: Một số nguyên duy nhất n (1 n. Dữ liệu vào: Dòng duy nhất chứa số n (1<=n<=8) Kết quả: Các hoán vị sắp xếp theo thứ tự từ điển tăng dần. Ví dụ: Input.txt Output.txt 44
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 3 123 132 213 231 312 321 BÀI 2.1.19: Cho một chuỗi gồm n bít X = (x1, x2, , xn). Ta gọi K là tổng các bít liền kề của chuỗi X ( ký hiệu là AdjBC(X)) được tính toán như sau: n 1 K  xi xi 1 ; i 1 Ví dụ : AdjBC(011101101) = 3 AdjBC(111101101) = 4 AdjBC(010101010) = 0 Viết chương trình tìm số các chuỗi bít có độ dài N có tổng các bít liền kề đúng bằng K. Ví dụ với N = 5, ta có 6 chuỗi có tổng các bít liền kề là 2 như sau: 11100, 01110, 00111, 10111, 11101, 11011. Input: PTIT Dòng đầu tiên ghi lại số tự nhiên T là số test của bài toán; T dòng kế tiếp, mỗi dòng ghi lại một test. Mỗi test ghi lại cặp ba số i, N, K. Trong đó, i là số thứ tự của test, N là độ dài chuỗi bít, K là tổng các bít liền kề. Các số được ghi cách nhau một vài khoảng trống. Output: Ghi lại số hiệu test và số các bít liền kề thỏa mãn yêu cầu bài toán trên một dòng. Hai số được viết cách nhau một vào khoảng trống. InputB: OutputB: 10 1 6 1 5 2 2 63426 2 20 8 3 1861225 3 30 17 4 1682122501 4 40 24 5 44874764 5 50 37 6 160916 45
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 6 60 52 7 22937308 7 70 59 8 99167 8 80 73 9 15476 9 90 84 10 23076518 10 100 90 1.6. Kỹ thuật sinh kế tiếp BÀI 2.2.1: LIỆT KÊ DÃY NHỊ PHÂN CÓ ĐỘ DÀI CHO TRƯỚC Sinh các dãy nhị phân có độ dài n. Dữ liệu vào: Số nguyên duy nhất n (1 dãy kế tiếp 000+1=001. Xây dựng thuật toán sinh kế tiếp: - Khởi tạo dãy nhị phân ban đầu là 000 0 46
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 - Duyệt dãy nhị phân từ cuối, nếu phần tử cuối là bit 0 thì thay nó bằng bit 1.Còn các bit khác được duyệt qua được gán =1. (sinh kế tiếp) while (chưa về đầu dãy nhị phân) do i=n; while(s[i]==1) do begin s[i]=0; i– end s[i]=1; end; BÀI 2.2.2: LIỆT KÊ CHỈNH HỢP LẶP CHẬP K CỦA N PHẦN TỬ Cho n phần tử từ 1, ,n. Hãy liệt kê các chỉnh hợp lặp chập k của n phần tử trên. Dữ liệu vào: Số nguyên k, n (1<=k, n<=9) Kết quả: Mỗi dòng một dãy các chỉnh hợp lặp chập k của n phần tử 1, ,n. PTIT BÀI 2.2.3: HOÁN VỊ CỦA N PHẦN TỬ Xem bài 2.1.18. BÀI 2.2.4: TỔ HỢP CHẬP K CỦA N PHẦN TỬ Xem bài 2.1.4. BÀI 2.2.5: LIỆT KÊ DÃY NHỊ PHÂN KHÔNG CÓ HAI SỐ 0 LIÊN TIẾP Hãy liệt kê các dãy nhị phân có độ dài n sao cho dãy tạo ra không có 2 số 0 liên tiếp nhau. Dữ liệu vào: Số nguyên duy nhất n (1<=n<=9) 47
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Kết quả: Mỗi dòng một dãy nhị phân. Các dãy nhị phân phải được liệt kê theo thứ tự từ điển. Ví dụ: Input.txt Output.txt 2 01 10 11 BÀI 2.2.6: SINH TỔNG CON KẾ TIẾP Cho n là số nguyên dương. Một cách phân chia số n là biểu diễn n thành tổng các số tự nhiên không lớn hơn n. Liệt kê tất cả các tổng con có thể có của n, thứ tự đơn giản nhất là thứ tự từ điển (sử dụng phương pháp sinh tổ hợp để sinh ra cấu hình tiếp theo không dùng quay lui). Dữ liệu vào: Số nguyên duy nhất n (1<=n<=9) Kết quả: Mỗi dòng một dãy thỏa mãnPTIT yêu cầu. Các dãy nhị phân phải được liệt kê theo thứ tự từ điển. Ví dụ: Input.txt Output.txt 7 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 48
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 BÀI 2.2.7: Cho dãy A[] gồm N số tự nhiên khác nhau và số tự nhiên K. Hãy sử dụng thuật toán sinh viết chương trình liệt kê tất cả các dãy con của dãy số A[] sao cho tổng các phần tử trong dãy con đó đúng bằng K. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các số của dãy số A[] và số tự nhiên K, hai số được viết cách nhau bởi một vài khoảng trống; Dòng kế tiếp ghi lại N số của dãy số A[], hai số được viết cách nhau một vài khoảng trống. Các dãy con thoả mãn điều kiện tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số các dãy con có tổng các phần tử đúng bằng K tìm được; Những dòng kế tiếp mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Ví dụ dưới đây sẽ minh hoạ cho file dayso.in và ketqua.out của bài toán. Dayso.in PTITKetqua.out 5 50 3 10 15 25 5 10 15 20 25 5 20 25 5 10 15 20 BÀI 2.2.8: Cho dãy gồm N số nguyên phân biệt A[] = {a1, a2, , aN } và số tự nhiên K ( K N 100). Hãy sử dụng thuật toán sinh viết chương trình liệt kê tất cả các dãy con K phần tử tăng dần tự nhiên của dãy số A[]. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: 49
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Dòng đầu tiên ghi lại hai số tự nhiên N, K. Hai số được viết cách nhau một vài khoảng trống; Những dòng kế tiếp ghi lại N số nguyên của dãy số A[], hai số khác nhau được viết cách nhau một vài khoảng trống. Các dãy con K phần tử tăng dần của dãy số A[] 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 M là số các dãy con K phần tử tăng dần của dãy số A[] tìm được; M dòng kế tiếp, mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Ví dụ với file dayso.in dưới đây sẽ cho ta file ketqua.out tương ứng. dayso.in ketqua.out 5 3 7 2 5 15 10 20 2 5 15 2 5 10 2 5 20 2 15 20 2 10 20 5 15 20 5 10 20 BÀI 2.2.9: Cho dãy gồm N số nguyên phân biPTITệt A[] = {a1, a2, , aN } và số tự nhiên K ( K N 100). Hãy sử dụng thuật toán sinh viết chương trình liệt kê tất cả các dãy con K phần tử tăng dần tự nhiên của dãy số A[]. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại hai số tự nhiên N, K. Hai số được viết cách nhau một vài khoảng trống; Những dòng kế tiếp ghi lại N số nguyên của dãy số A[], hai số khác nhau được viết cách nhau một vài khoảng trống. Các dãy con K phần tử tăng dần của dãy số A[] 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 M là số các dãy con K phần tử tăng dần của dãy số A[] tìm được; M dòng kế tiếp, mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Ví dụ với file dayso.in dưới đây sẽ cho ta file ketqua.out tương ứng. 50
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 dayso.in ketqua.out 5 3 7 2 5 15 10 20 2 5 15 2 5 10 2 5 20 2 15 20 2 10 20 5 15 20 5 10 20 BÀI 2.2.10: 2 Cho ma trận vuông C = (cij) cấp N (1 i, j N 100) gồm N số tự nhiên (các số không nhất thiết phải khác nhau) ghi lại trong file matran.in theo khuôn dạng sau : Dòng đầu tiên ghi lại số tự nhiên N là cấp của ma trận vuông C; N dòng kế tiếp ghi lại ma trận vuông C = (cij). Hai phần tử khác nhau của ma trận được ghi cách nhau bởi một vài khoảng trống. Hãy sử dụng thuật toán sinh thích hợp viết chương trình lấy trên mỗi hàng, mỗi cột duy nhất một phần tử của ma trận C sao cho tổng các phần tử này là nhỏ nhất. Kết quả tìm được ghi lại trong file ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại tổng giá trị nhỏ nhất của N phần tử tìm được; N dòng kế tiếp, mỗi dòng ghi lại ba số i, j, cij tương ứng với chỉ số hàng, chỉ số cột và giá trị phần tử tương ứng của ma trận. Ba số được viết cách nhau một vài khoảng trống. Ví dụ về file matran.in và ketqua.outPTIT: matran.in ketqua.out 6 82 10 64 57 29 18 15 1 1 10 34 20 19 30 16 12 2 6 12 57 49 40 16 11 19 3 4 16 29 21 46 26 21 18 4 5 21 28 16 11 21 21 37 5 3 11 15 12 15 48 37 30 6 2 12 51
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.2.11: Cho dãy gồm N số nguyên phân biệt A[] = {a1, a2, , aN } và số tự nhiên K ( K N 100). Hãy sử dụng thuật toán sinh viết chương trình liệt kê tất cả các dãy con K phần tử giảm dần tự nhiên của dãy số A[]. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại hai số tự nhiên N, K. Hai số được viết cách nhau một vài khoảng trống; Những dòng kế tiếp ghi lại N số nguyên của dãy số A[], hai số khác nhau được viết cách nhau một vài khoảng trống. Các dãy con K phần tử tăng dần của dãy số A[] 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 M là số các dãy con K phần tử tăng dần của dãy số A[] tìm được; M dòng kế tiếp, mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Ví dụ với file dayso.in dưới đây sẽ cho ta file ketqua.out tương ứng. dayso.in ketqua.out 5 3 7 2 5 15 10 20 2 5 15 2 5 10 2 5 20 2 15 20 2 10 20 5 15 20 5 10 20 PTIT BÀI 2.2.12: Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) viết chương trình Viết n chương trình tìm X = (x1, x2, ,xn) và giá trị f (x1 , x2 , , xn ) ci xi đạt giá trị lớn nhất. Trong i 1 n  đó, X x1 , x2 , , xn D ai xi b; xi 0,1 , ci, ai, b là các số nguyên dương, n 100 i 1  Dữ liệu vào n, cj, aj, b được cho trong file data.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên n và b. Hai số được ghi cách nhau bởi một vài ký tự trống; n dòng kế tiếp ghi lại trên mỗi dòng một cặp số ci , ai (i=1, 2, , n). Hai số được ghi cách nhau bởi một vài ký tự trống; 52
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Giá trị tối ưu f(x1,x2, ,xn) và phương án tối ưu X = (x1, x2, ,xn) tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại giá trị tối ưu f(x1,x2, ,xn); Dòng kế tiếp ghi lại phương án tối ưu X = (x1, x2, ,xn). Hai phần tử khác nhau của X được ghi cách nhau bởi một vài khoảng trống. Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán: Data.in Ketqua.out 4 10 12 5 5 0 0 1 1 1 3 9 6 3 4 BÀI 2.2.13: Cho dãy gồm n số tự nhiên phân biệt a1, a2, , an và số tự nhiên B. Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) liệt kê tất cả các phần tử của tập n  D x1 , x2 ,, xn : ai xi B, xi 0,1,i 1,2, ,n ; i 1  Dữ liệu vào cho bởi file data.in theo khuôn dạng như sau: Dòng đầu tiên ghi lại hai số tự nhiên n và B. Hai số được viết cách nhau bởi một vài khoảng trống. Dòng kế tiếp ghi lại n số nguyênPTIT dương a1, a2, ,an. Hai số khác nhau được viết cách nhau bởi một vài kí tự trống. Kết quả ra ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên k là số phần tử của tập D. k dòng tiếp theo mỗi dòng ghi lại một vector nhị phân x = (x1, x2 , , xn) là phần tử của D. Hai thành phần khác nhau của vector x được viết cách nhau bởi một vài khoảng trống. Ví dụ với n =7, B = 25, { a1, a2, a3, a4, a5, a6, a7} = {5, 10, 15, 20, 25, 30, 35} trong file data.in sẽ cho ta 3 phần tử của tập D tương ứng với 3 vector nhị phân độ dài n trong file ketqua.out dưới đây: Data.in Ketqua.Out 7 25 3 5 10 15 20 25 0 0 0 0 1 0 0 30 35 1 0 0 1 0 0 0 0 1 1 0 0 0 0 53
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.2.14: Một người quản lý có n công việc cần thực hiện cùng một lúc. Biết rằng có n công nhân, mỗi công nhân đều có thể thực hiện được tất cả các công việc nhưng với thời gian khác nhau. Thời gian để công nhân thứ i thực hiện công việc j là Ci,j (tính theo giờ). Hãy sử dụng thuật toán sinh (quay lui, nhánh cận, qui hoạch động) viết chương trình tìm cách bố trí n công việc cho n công nhân sao cho tổng thời gian thực hiện là nhỏ nhất. Dữ liệu vào được cho bởi file: VIEC.INP trong đó: - Dòng thứ nhất ghi số N ; - N dòng tiếp theo ghi các giá trị của ma trận thời gian C. Hai phần tử khác nhau được viết cách nhau một vài khoảng trống. Kết quả tìm được lưu vào file KETQUA.OUT trong đó: - Dòng thứ nhất ghi giá trị tổng thơi gian nhỏ nhất có thể đạt được - Dòng thứ hai ghi cách bố trí việc cho từng ông thợ. Ví dụ: File VIEC.INP và KETQUA.OUT VIEC.INP KETQUA.OUT 6 82 10 64 57 29 18 15 1 6 5 3 4 2 34 20 19 71 16 12 57 49 40 16 11 19 PTIT 29 21 46 26 21 18 28 16 11 21 21 37 15 12 15 48 37 30 1.7. Kỹ thuật quay lui 54
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.3.1: BÀI TOÁN XẾP HẬU (THAM KHẢO) Có một bàn cờ kích thước n x n (n ≥ 4). Yêu cầu: tìm tất cả các cách để đặt n con hậu trên bàn cờ sao cho không có con nào khống chế lẫn nhau. Biết rằng, một con hậu có thể khống chế tất cả các quân cờ trên hàng ngay, cột dọc và hai đường chéo đi qua vị trí của nó. Chẳng hạn ta có một cách đặt sau đối với các con hậu: Dữ liệu vào: File input gồm: số nguyên dương n. Kết quả: File output: dòng đầu tiên ghi số phương án thỏa mãn m. Các dòng tiếp theo ghi m ma trận nxn gồm các số 0 hoặc 1 với 1 là vị trí đặt của quân hậu, các ma trận liền nhau cách nhau một dòng trống.PTIT Gợi ý: Ta có có nhận xét: mỗi con hậu phải ở trên một hàng và một cột. Do đó ta coi con hậu thứ i ở hàng i và nếu biết x[i] là cột đặt con hậu thứ i thì ta suy ra được lời giải. Vậy nghiệm của bài toán có thể coi là một vector x gồm n thành phần với ý nghĩa: 1. Con hậu thứ i được đặt ở hàng i và cột x[i]. 2. x[i] lấy giá trị trong tập {1,2 n} 3. Ràng buộc: các giá trị x[i] khác nhau từng đôi một và không có 2 con hậu ở trên cùng một đường chéo. 55
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.3.2: BÀI TOÁN MÃ ĐI TUẦN (THAM KHẢO) Cho bàn cờ vua có n x n ô . Một con mã được phép đi theo luật cờ vua, đầu tiên được đặt vào ô có tọa độ (x0,y0). Yêu cầu : Hãy chỉ ra các hành trình nếu có của con mã sao cho con mã đi qua tất cả cá ô của bàn cờ,mỗi ô đi qua đúng 1 lần. Dữ liệu vào: File input gồm: số nguyên dương n. Kết quả: File output: các cặp tọa độ (x,y) cách nhau bởi dấu cách chỉ ra hành trình của con mã, bắt đầu với (x0,y0). BÀI 2.3.3: TÌM ĐƯỜNG ĐI TRONG MÊ CUNG Mê cung là một khu vực hình chữ nhật được chia là M*N phòng. Tại mỗi phòng có thể nhốt một quái vật. Từ một phòng ta có thể đi đến 4 phòng xung quang nếu chúng không có quái vật. Giả sử bạn đang lạc trong mê cung tại ô (x0,y0). Hãy tìm đường đi thoát khỏi mê cung ra một phòng trên cạnh của mê cung một cách nhanh nhất (đi qua ít đỉnh nhất). Dữ liệu vào: Dòng đầu là 2 số M,N.M dòng tiếp theo mô tả ma trận A trong đó A[x,y]=1 nếu tại phòng (x,y) có quái vật, ngược lại thì A[x,y]=0. Hạn chế: 4<=M,N<=100. PTIT Kết quả: Dòng đầu tiên là số K mô tả số các phòng đã đi qua. Nếu không tìm được đường ra thì K=0. Các dòng tiếp theo là toạ độ các phòng đã đi qua. BÀI 2.3.4: BÀI TOÁN NGƯỜI BÁN HÀNG Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. 56
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Gợi ý: Bài toán người bán hàng có thể được mô hình hoá như một đồ thị vô hướng có trọng số, trong đó mỗi thành phố là một đỉnh của đồ thị còn đường đi giữa các thành phố là mỗi cách. Khoảng cách giữa hai thành phố là độ dài cạnh. Đây là vấn đề cực tiểu hoá với điểm đầu và điểm cuối là cùng một đỉnh sau khi thăm hết các đỉnh còn lại đúng một lần. Mô hình này thường là một đồ thị đầy đủ (giữa mỗi cặp đỉnh đều có cạnh). Nếu không có đường giữa hai thành phố thì có thể thêm một cạnh với độ dài đủ lớn vào đồ thị mà không ảnh hưởng đến kết quả tối ưu sau cùng. BÀI 2.3.5: LIỆT KÊ DÃY NHỊ PHÂN KHÔNG CÓ HAI SỐ 0 LIÊN TIẾP Xem bài 2.2.4. BÀI 2.3.6: TAM GIÁC SỐ Hình sau mô tả một tam giác số có số hàng N=5: 7 3 8 8 1 0PTIT 2 7 4 4 4 5 2 6 5 Đi từ đỉnh (số 7) đến đáy tam giác bằng một đường gấp khúc, mỗi bước chỉ được đi từ số ở hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới, và cộng các số trên đường đi lại ta được một tổng. Ví dụ: đường đi 7 8 1 4 6 có tổng là S=26, đường đi 7 3 1 7 5 có tổng là S=23 Trong hình trên, tổng Smax=30 theo đường đi 7 3 8 7 5 là tổng lớn nhất trong tất cả các tổng. 57
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Nhiệm vụ của bạn và viết chương trình nhận dữ liệu vào là một tam giác số chứa trong text file INPUT.TXT và đưa ra kết quả là giá trị của tổng Smax trên màn hình. File INPUT.TXT có dạng như sau: Dòng thứ 1: có duy nhất 1 số N là số hàng của tam giác số (0<N<100). N dòng tiếp theo, từ dòng thứ 2 đến dòng thứ N+1: dòng thứ i có (i-1) số cách nhau bởi dấu trống (space). Ví dụ: với nội dung của file INPUT.TXT là 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 thì kết quả chạy chương trình sẽ là: Smax=30. BÀI 2.3.7: Ô CHỮ Trò chơi ô chữ thông dụng 30 năm trước của trẻ em gồm một khung ô chữ kích thước 5x5 chứa 24 hình vương nhỏ kích thướcPTIT như nhau. Trên mặt mỗi hình vuông nhỏ có in một chữ cái trong bảng chữ cái. Vì chỉ có 24 hình vuông trong ô chữ nên trong ô chữ còn thừa ra một ô trống, có kích thước đúng bằng kích thước các hình vuông. Một hình vuông có thể đẩy trượt vào ô trống đó nếu nó nằm ngay sát bên trái, bên phải, bên trên hay bên dưới ô trống. Mục tiêu của trò chơi là trượt các h ình vuông vào ô trống sao cho cuối cùng các chữ cái trong ô chữ được xếp theo đúng thứ tự của chúng trong bảng chữ cái. Hình sau đây minh hoạ một ô chữ với cấu hình ban đầu và cấu hình của nó sau 6 nước đi sau: 1.Trượt hình vuông phía trên ô trống. 2.Trượt hình vuông bên phải ô trống. 3.Trượt hình vuông bên phải ô trống. 4.Trượt hình vuông phía dưới ô trống. 58
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 5.Trượt hình vuông phía dưới ô trống. 6.Trượt hình vuông bên trái ô trống. TT RR GG SS JJ XX OO KK LL II MM DD VV BB NN WW PP AA EE UU QQ HH CC FF Cấu hình của ô chữ sau 6 nước. T R G S J X D O K I PTIT M V L N W P A B E U Q H C F Cấu hình ban đầu của ô chữ Bạn hãy viết một chương trình của bạn chứa cấu hình ban đầu của ô chữ cùng các nước đi để vẽ ra ô chữ kết quả. 59
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Input Đầu vào của chương trình của bạn chứa cấu hình ban đầu của một ô chữ và một dẫy các nước đi trong ô chữ đó . Năm dòng đầu tiên mô tả cấu hình ban đầu của ô chữ, mỗi dòng tương ứng với một hàng của ô chữ và chứa đú ng 5 ký tự tương ứng với 5 hình vuông của ô chữ trên hàng đó. Ô trống đ ược diễn tả bằng một dấu cách. Các dòng tiếp theo sau là dẫy các nước đi. Dãy các nước đi được ghi bằng dãy các chữ A,B,R và L để thể hiện hình vuông nào được trượt vào ô trống. A thể hiện hình vuông phía trên ô trống được trượt vào ô trống, tương ứng: B-phía dưới, R-bên phải, L-bên trái. Có thể có những nước đi không hợp cách, ngay cả khi nó được biểu thị bằng những chữ cái trên. Nếu xuất hiện một nước đi không hợp cách thì ô chữ coi như không có cấu hình kết quả. Dãy các nước đi có thể chiếm một số dòng, nhưng nó sẽ được xem là kết thúc ngay khi gặp một số 0. Out put Nếu ô chữ không có cấu hình kết quả thì thông báo 'This puzzle has no final configuration.'; ngược lại thì hiển thị cấu hình ô chữ kết quả. Định dạng mỗi dòng kết quả bằng cách đặt một dấu cách vào giữa hai kí tự kế tiếp nhau. Ô trống cũng được xử lý như vậy. Ví dụ nếu ô trống nằm bên trong hàng thì nó được xuất hiện dưới dạng 3 dấu cách: một để ngăn cách nó với kí tự bên trái, một để thể hiện chính ô trống đó , còn một để ngăn cách nó với kí tự bênPTIT phải. Chú ý: Input mẫu đầu tiên tương ứng với ô chữ được minh hoạ trong ví dụ trên. Sample Input 1 TRGSJ XDOKI M VLN WPABE UQHCF ARRBBL0 Sample Output 1 T R G S J 60
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 X O K L I M D V B N W P A E U Q H C F Sample Input 2 AB C DE F G H I J KLMNO PQRS TUVWX AAA LLLL0 Sample Output 2 A B C D F G H I E K L M N J P Q R S O PTIT T U V W X Sample Input 3 ABCDE FGHIJ KLMNO PQRS TUVWX AAAAABBRRRLL0 Sample Output 3 61
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 This puzzle has no final configuration. BÀI 2.3.8: DI CHUYỂN TRÁI PHẢI Một robot chỉ có thể di chuyển sang phải hoặc sang trái. Dãy di chuyển của nó được kí hiệu là một chuỗi, nhưng do sơ suất của người ghi chép, nên một số bước đi không ghi lại được. Nhiệm vụ của bạn là xác định xem robot có thể đi cách xa nhất vị trí ban đầu là ban nhiêu? Input Một dòng duy nhất chứa chuỗi di chuyển, mỗi kí tự có thể là: - ‘L’ nếu di chuyển sang trái - ‘R’ nếu di chuyển sang phải - ‘ ?’ nếu không xác định. Output Khoảng cách xa nhất đến vị trí ban đầu. Ví dụ: Input: LLLRLRRR Output: 3 PTIT Input: R???L Output: 4 BÀI 2.3.9: LIỆT KÊ DÃY NHỊ PHÂN CÓ ĐỘ DÀI CHO TRƯỚC Tham khảo bài 2.3.1 62
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.3.10: Cho dãy A[] gồm N số tự nhiên khác nhau và số tự nhiên K. Hãy sử dụng thuật toán quay lui viết chương trình liệt kê tất cả các dãy con của dãy số A[] sao cho tổng các phần tử trong dãy con đó đúng bằng K. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các số của dãy số A[] và số tự nhiên K, hai số được viết cách nhau bởi một vài khoảng trống; Dòng kế tiếp ghi lại N số của dãy số A[], hai số được viết cách nhau một vài khoảng trống. Các dãy con thoả mãn điều kiện tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số các dãy con có tổng các phần tử đúng bằng K tìm được; Những dòng kế tiếp mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Dayso.in Ketqua.out 5 50 3 10 15 25 5 10 15 20 25 5 20 25 5 10 15 20 BÀI 2.3.11: PTIT 2 Cho ma trận vuông C = (cij) cấp N (1 i, j N 100) gồm N số tự nhiên (các số không nhất thiết phải khác nhau) ghi lại trong file matran.in theo khuôn dạng sau : Dòng đầu tiên ghi lại số tự nhiên N là cấp của ma trận vuông C; N dòng kế tiếp ghi lại ma trận vuông C = (cij). Hai phần tử khác nhau của ma trận được ghi cách nhau bởi một vài khoảng trống. Hãy sử dụng thuật toán quay lui viết chương trình lấy trên mỗi hàng, mỗi cột duy nhất một phần tử của ma trận C sao cho tổng các phần tử này là nhỏ nhất. Kết quả tìm được ghi lại trong file ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại tổng giá trị nhỏ nhất của N phần tử tìm được; N dòng kế tiếp, mỗi dòng ghi lại ba số i, j, cij tương ứng với chỉ số hàng, chỉ số cột và giá trị phần tử tương ứng của ma trận. Ba số được viết cách nhau một vài khoảng trống. 63
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Ví dụ về file matran.in và ketqua.out: matran.in ketqua.out 6 82 10 64 57 29 18 15 1 1 10 34 20 19 30 16 12 2 6 12 57 49 40 16 11 19 3 4 16 29 21 46 26 21 18 4 5 21 28 16 11 21 21 37 5 3 11 15 12 15 48 37 30 6 2 12 BÀI 2.3.12: Cho dãy gồm N số nguyên phân biệt A[] = {a1, a2, , aN } và số tự nhiên K ( K N 100). Hãy sử dụng thuật toán quay lui viết chương trình liệt kê tất cả các dãy con K phần tử giảm dần tự nhiên của dãy số A[]. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại hai số tự nhiên N, K. Hai số được viết cách nhau một vài khoảng trống; Những dòng kế tiếp ghi lại N số nguyên của dãy số A[], hai số khác nhau được viết cách nhau một vài khoảng trống. Các dãy con K phần tử tăng dần của dãy số A[] 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 M là số các dãy con K phần tử tăng dần của dãy số A[] tìm được; M dòng kế tiếp, mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi mộtPTIT vài khoảng trống. Ví dụ với file dayso.in dưới đây sẽ cho ta file ketqua.out tương ứng. dayso.in ketqua.out 5 3 7 2 5 15 10 20 2 5 15 2 5 10 2 5 20 2 15 20 2 10 20 5 15 20 5 10 20 64
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 1.8. Kỹ thuật nhánh cận BÀI 2.4.1: DÃY ABC Cho trước một số nguyên dương N (N ≤ 100), hãy tìm một xâu chỉ gồm các ký tự A, B, C thoả mãn 3 điều kiện: - Có độ dài N - Hai đoạn con bất kỳ liền nhau đều khác nhau (đoạn con là một dãy ký tự liên tiếp của xâu) - Có ít ký tự C nhất. Cách giải: Nếu dãy X[1 n] thoả mãn 2 đoạn con bất kỳ liền nhau đều khác nhau, thì trong 4 ký tự liên tiếp bất kỳ bao giờ cũng phải có 1 ký tự “C”. Như vậy với một dãy con gồm k ký tự liên tiếp của dãy X thì số ký tự C trong dãy con đó bắt buộc phải ≥ k div 4. Tại bước thử chọn X[i], nếu ta đã có T[i] ký tự “C” trong đoạn đã chọn từ X[1] đến X[i], thì cho dù các bước đệ quy tiếp sau làm tốt như thế nào chăng nữa, số ký tự “C” sẽ phải chọn thêm bao giờ cũng ≥ (n - i) div 4. Tức là nếu theo phương án chọn X[i] như thế này thì số ký tự “C” trong dãy kết quả (khi chọn đến X[n]) cho dù có làm tốt đến đâu cũng ≥ T[i] + (n - i) div 4. Ta dùng con số này để đánh giá nhánh cận, nếu nó nhiều hơn số ký tự “C” trong BestConfig thì chắc chắn có làm tiếp cũng chỉ được một cấu hình tồi tệ hơn, ta bỏ qua ngay cách chọn nàyPTIT và thử phương án khác. Input: file văn bản ABC.INP chứa số nguyên dương n ≤ 100 Output: file văn bản ABC.OUT ghi xâu tìm được Ví dụ: ABC.INP ABC.OUT 10 ABACABCBAB “C” Letter Count : 2 65
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.4.2: BÀI TOÁN NGƯỜI BÁN HÀNG Xem bài 2.3.4. BÀI 2.4.3: BÀI TOÁN TÌM ĐƯỜNG TRONG MÊ CUNG Xem bài 2.3.3. BÀI 2.4.4: BÀI TOÁN CÁI TÚI Xem bài 2.1.10. BÀI 2.4.5: BÀI TOÁN MÃ ĐI TUẦN Xem bài 2.3.2. BÀI 2.4.6: BÀI TOÁN XẾP HẬU Xem bài 2.3.1. BÀI 2.4.7: Cho dãy A[] gồm N số tự nhiên khác nhau và số tự nhiên K. Hãy sử dụng thuật toán quay lui nhánh cận viết chương trình liệt kê tất cả các dãy con của dãy số A[] sao cho tổng các phần tử trong dãy con đó đúng bằngPTIT K. Dữ liệu vào cho bởi file dayso.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các số của dãy số A[] và số tự nhiên K, hai số được viết cách nhau bởi một vài khoảng trống; Dòng kế tiếp ghi lại N số của dãy số A[], hai số được viết cách nhau một vài khoảng trống. Các dãy con thoả mãn điều kiện tìm được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số các dãy con có tổng các phần tử đúng bằng K tìm được; Những dòng kế tiếp mỗi dòng ghi lại một dãy con. Hai phần tử khác nhau của dãy con được viết cách nhau bởi một vài khoảng trống. Dayso.in Ketqua.out 66
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 5 50 3 10 15 25 5 10 15 20 25 5 20 25 5 10 15 20 BÀI 2.4.8: 2 Cho ma trận vuông C = (cij) cấp N (1 i, j N 100) gồm N số tự nhiên (các số không nhất thiết phải khác nhau) ghi lại trong file matran.in theo khuôn dạng sau : Dòng đầu tiên ghi lại số tự nhiên N là cấp của ma trận vuông C; N dòng kế tiếp ghi lại ma trận vuông C = (cij). Hai phần tử khác nhau của ma trận được ghi cách nhau bởi một vài khoảng trống. Hãy sử dụng thuật toán quay lui nhánh cận viết chương trình lấy trên mỗi hàng, mỗi cột duy nhất một phần tử của ma trận C sao cho tổng các phần tử này là nhỏ nhất. Kết quả tìm được ghi lại trong file ketqua.out theo khuôn dạng: Dòng đầu tiên ghi lại tổng giá trị nhỏ nhất của N phần tử tìm được; N dòng kế tiếp, mỗi dòng ghi lại ba số i, j, cij tương ứng với chỉ số hàng, chỉ số cột và giá trị phần tử tương ứng của ma trận. Ba số được viết cách nhau một vài khoảng trống. Ví dụ về file matran.in và ketqua.out: matran.in PTITketqua.out 6 82 10 64 57 29 18 15 1 1 10 34 20 19 30 16 12 2 6 12 57 49 40 16 11 19 3 4 16 29 21 46 26 21 18 4 5 21 28 16 11 21 21 37 5 3 11 15 12 15 48 37 30 6 2 12 1.9. Kỹ thuật qui hoạch động 67
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.5.1: XẾP HÀNG Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao. Bác John đã chuẩn bị một danh sách gồm Q (1 ≤ Q ≤ 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1, 1000000]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này. Dữ liệu Dòng đầu tiên chứa 2 số nguyên N và Q. Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i. Dòng thứ i trong số Q trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤ N), cho biết đoạn các con bò từ A đến B. Kết quả Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng. Ví dụ: PTIT Input.txt Output.txt 6 3 6 1 3 7 0 3 4 2 5 1 5 4 6 2 2 68
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 2.5.2: ĐOẠN TĂNG Cho dãy số nguyên A = (a1, a2, , an). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy A có thứ tự không giảm. Quy ước: Đoạn chỉ gồm đúng 1 phần tử trong A cũng được coi là có thứ tự không giảm. Dữ liệu: Dòng 1 chứa số nguyên dương n ≤ 105 9 Dòng 2 chứa n số nguyên a1, a2, , an ("i: |ai| ≤ 10 ) cách nhau ít nhất một dấu cách Kết quả:một số nguyên duy nhất là số phần tử trong đoạn tìm được Ví dụ: INPUT OUTPUT 11 4 88 99 11 22 22 33 11 66 33 44 77 BÀI 2.5.3: ĐỘ ĐO Hai xâu ký tự được gọi là đảo của nhau nếu ta có thể hoán vị các ký tự của một xâu để được xâu còn lại. Ví dụ: xâu “occurs” là đảo của xâu “succor”, tuy nhiên xâu “dear” không phải là đảo của xâu “dared” (vì chữPTIT ‘d’ xuất hiện 2 lần trong “dared” nhưng chỉ xuất hiện “dear” trong 1 lần). Độ đo giữa hai xâu ký tự là số ký tự ít nhất cần phải xóa (trên cả hai xâu) để hai xâu còn lại đảo của nhau. Ví dụ độ đo giữa hai xâu “sleep” và “leap” là 3, độ đo giữa hai xâu “dog” và “cat” là 6. Yêu cầu: Hãy tính độ đo giữa hai xâu cho trước. Dữ liệu: Gồm hai dòng, mỗi dòng chứa một xâu ký tự chỉ gồm các chữ cái tiếng Anh thường, mỗi dòng có không quá 1 triệu ký tự. Kết quả: một số nguyên duy nhất là độ đo giữa hai xâu trong file dữ liệu. 69
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Ví dụ INPUT OUTPUT Begin 4 end BÀI 2.5.4: DÃY CON TĂNG DẦN TỰ NHIÊN BẬC K Cho dãy gồm N số phân biệt AN = {a1, a2, , aN } và số tự nhiên K (K<=N<=100). Ta gọi một dãy con tăng dần bậc K của dãy số AN là một dãy các số gồm K phần tử trong dãy đó thỏa mãn tính chất tăng dần. Bài toán được đặt ra là hãy tìm số các dãy con tăng dần bậc K của dãy số AN. Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được xây dựng theo khuôn dạng sau: Dòng đầu tiên ghi lại hai số N và K tương ứng với số phần tử của dãy số và bậc của dãy con. Dòng kế tiếp ghi lại N số của dãy số AN, các số trong dãy không lớn hơn 100. Output: PTIT Với mỗi bộ test, in ra màn hình số các dãy con tăng dần tự nhiên bậc K của dãy số AN. Ví dụ: Input: Output: 2 7 5 3 1 2 5 15 10 20 5 3 2 20 10 15 5 70
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 PTIT 71
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 III. Lập trình dựa vào ngăn xếp, hàng đợi 1.10. Kỹ thuật xử lý trên ngăn xếp BÀI 3.1.1: THÁP HÀ NỘI (THAM KHẢO) Bài toán Tháp HàNội được mô tả như sau: cho 3 cột được đánh số lần lượt là 1, 2 và 3. Có n đĩa được sắp theo thứ tự đĩa nhỏ ở bên trên đĩa lớn. Hãy liệt kê các bước thực hiện để chuyển tất cả các đĩa từ cột 1 sang cột 2. Quy luật di chuyển như sau: 1. Mỗi bước chỉ di chuyển 1 đĩa từ cột này sang cột khác. 2. Đĩa có bán kính nhỏ luôn sắp trên đĩa có bán kính lớn. 1 2 3 1 2 3 Yêu cầu: Viết chương trình nhập vào số đĩa n, thực hiện các bước di chuyển các đĩa, mỗi bước di chuyển cho biết cột nguồn (cột lấy đĩa) và cột đích (cột đặt đĩa). Giải thuật di chuyển không đệ quy, dùng stack để chứa thông tin tạm thời trong quá trình di chuyển. Sinh viên cài đặt stack dùng danh sách liên kết, mỗi node phần info chứa 3 thông tin {số đĩa di chuyển, cột nguồn, cột đích}. Hướng dẫn: Như chúng ta biết bài toán tháp PTITHanoi thường được giải bằng phương pháp đệ quy. Tuy nhiên có thể giải bằng cách dùng stack để khử đệ quy. Để thực hiện việc lưu trữ tạm trong quá trình di chuyển chúngta dùng một stack. Trong đó mỗi phần tử của stack này chứa các thông tin gồm: số đĩa di chuyển (N), cột nguồn bắt đầu di chuyển (Nguon) và cột đích là nơi cần di chuyển đến (Dich). Ở đây không cần lưu cột trung gian vì có 3 cột đánh số là 1, 2 và 3 thì cột trung gian để di chuyển là: 6 – (Nguon+Dich). Đầu tiên đưa vào stack thông tin di chuyển {n, 1, 2}, tức là di chuyển n đĩa từ cột 1 sang cột thứ 2 qua cột trung gian là 6-(1+2) = 3. Tại mỗi bước khi lấy trong stack ra một phần tử. chúng ta thực hiện như sau: Nếu N = 1: ⇒ di chuyển đĩa từ cột Nguon -> cột Dich. Ngược lại (nếu N > 1): 72
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 • Xác định cột trung gian TrungGian = 6 – (Nguon+Dich) • Push ⇒ stack thông tin di chuyển {N-1, TrungGian, Dich} • Push ⇒ stack thông tin di chuyển {1, Nguon, Dich} • Push ⇒ stack thông tin di chuyển {N-1, Nguon, TrungGian} Quá trình còn thực hiện khi stack khác rỗng. Nhận xét: Lưu ý thứ tự khi đưa vào thông tin di chuyển vào stack. Trong phần trên thông tin {N-1, Nguon, TrungGian} được đưa vào stack sau cùng nên chúng sẽ được lấy ra trước tiên, kế đến là thông tin di chuyển {1, Nguon, Dich} và cuối cùng là thông tin di chuyển {N-1, TrungGian, Dich}. BÀI 3.1.2: SỬ DỤNG CẤU TRÚC STACK ĐỂ CHUYỂN MỘT BIỂU THỨC TRUNG TỐ SANG HẬU TỐ ? (THAM KHẢO) 1. Nhập biểu thức trung tố: toán hạng, toán tử và dấu ngoặc VD: (20+5)/5+(7-3)*100 2. Chuyển biểu thức trung tố thành hậu tố (xuất ra màn hình) VD: 20 5 + 5 / 7 3 – 100 * + 3. Tính giá trị của biểu thức hậu tố VD: (20+5)/5+(7-3)*100 = 405 Yêu cầu: Sinh viên cài đặt stack dùng PTITdanh sách liên kết: Cài đặt các thao tác: IsEmpty, NewNode, FreeNode, Pop, Push trên Stack. Hướng dẫn: 1. Chuyển biểu thức trung tố thành hậu tố: Duyệt biểu thức trung tố từ trái sang phải - Nếu gặp toán hạng thì ghi vào chuỗi kết quả - Nếu gặp dấu mở ngoặc thì push ⇒ stack - Nếu gặp toán tử gọi là O1 thực hiện các bước sau: - Chừng nào còn một toán tử O2 ở đỉnh stack và độ ưu tiên của O1 ≤ độ ưu tiên O2 thì lấy O2 ra khỏi stack và ghi vào chuỗi kết quả. - Push O1 ⇒ stack - Nếu gặp dấu đóng ngoặc: thì lấy toán tử trong stack ra cho đến khi lấy được 73
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 dấu mở ngoặc (lưu ý: pop dấu mở ngoặc ra, nhưng ko xuất ra chuỗi kết quả) Khi đã duyệt hết biểu thức trung tố, lấy tất cả toán tử trong stack và ghi vào chuỗi kết quả. 2. Tính giá trị biểu thức hậu tố: Đọc biểu thức từ trái sang phải, Nếu là toán hạng: Push ⇒ stack. Nếu gặp toán tử: - Lấy 2 toán hạng trong stack ra - Tính giá trị của 2 toán hạng đó theo toán tử - Push kết quả ⇒ stack Khi quá trình kết thúc thì con số cuối cùng còn lại trong stack chính là giá trị của biểu thức đó. BÀI 3.1.3: BÀI TOÁN ĐỐI SÁNH THẺ HTML Trong một văn bản HTML thì mỗi thẻ mở phả i đi kèm với 1 thẻ đóng, ví dụ: Tìm kiếm: PTIT Hãy viết chương trình đọc vào 1 file .html và kiểm tra xem trong file đó có thẻ nào bị lỗi hay không? BÀI 3.1.4: SỬ DỤNG CẤU TRÚC STACK ĐỂ ĐẢO XÂU KÍ TỰ ? BÀI 3.1.5: SỬ DỤNG CẤU TRÚC STACK ĐỂ CHUYỂN MỘT SỐ THẬP PHÂN SANG DẠNG NHỊ PHÂN ? 74
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.1.6: DẤU NGOẶC ĐÚNG Cho các đoạn văn chứa các dấu ngoặc, có thể là ngoặc đơn đơn ( “()” ) hoặc ngoặc vuông ( “[]” ). Một đoạn văn đúng là đoạn mà với mỗi dấu mở ngoặc thì sẽ có dấu đóng ngoặc tương ứng và đúng thứ tự. Nhiệm vụ của bạn kiểm tra xem đoạn văn có đúng hay không. Input Gồm nhiều bộ test, mỗi bộ test trên một dòng chứa đoạn văn cần kiểm tra có thể bao gồm: các kí tự trong bảng chữ cái tiếng Anh, dấu cách, và dấu ngoặc (ngoặc đơn hoặc ngoặc vuông). Kết thúc mỗi bộ test là một dấu chấm. Mỗi dòng có không quá 100 kí tự. Dữ liệu kết thúc bởi dòng chứa duy nhất một dấu chấm. Output Với mỗi bộ test, xuất ra trên một dòng “yes” nếu đoạn văn đúng, ngược lại in ra “no”. Ví dụ: Input: So when I die (the [first] I will see in (heaven) is a score list). [ first in ] ( first out ). Half Moon tonight (At least itPTIT is better than no Moon at all]. A rope may form )( a trail in a maze. Help( I[m being held prisoner in a fortune cookie factory)]. ([ (([( [ ] ) ( ) (( ))] )) ]) Output: yes yes no no no yes yes 75
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.1.7: CỘNG, TRỪ HAI ĐA THỨC Cho hai đa thức A bậc n và đa thức B bậc m được ghi lại tương ứng trong file dathuc1.in và dathuc2.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên K là số các số hạng của đa thức; K dòng kế tiếp, mỗi dòng ghi lại hệ số và số mũ của số hạng hạng đa thức. Hãy viết chương trình tính hiệ u hai đa thức A và B và ghi lại đa thức kết quả vào file ketqua.out theo khuôn dạng như trên. Ví dụ với đa thức: sẽ được biểu diễn và tính toán cho ra file kết quả sau dathuc1.in dathuc2.in ketqua.out 4 5 10 30000 10 30000 8 20000 -8 20000 5 1000 PTIT3 1000 2 1000 3 2 3 500 -3 500 3 0 7 100 -7 100 6 1 3 2 -6 1 3 0 BÀI 3.1.8: LẬP TRÌNH LỚP STACK Viết một lớp với các hàm trong stack như sau: 76
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 class stack { int data[10]; int top; public : stack(){top=-1;} void push(); void pop(); } BÀI 3.1.9: Sử dụng stack để tính biểu thức hậu tố sau và chỉ ra nội dung của stack sau khi chạy mỗi lệnh. Không cần viết code. Giả sử rằng bạn đang sử dụng hàm push và pop của lớp stack. AB-CD+E*+ (với A=5, B=3, C=5, D =4, và E=2) BÀI 3.1.10: Tính biểu thức hậu tố sau đây sử dụng stack và chỉ ra nội dung stack sau mỗi lệnh: 50,40,+,18, 14,-, *,+ BÀI 3.1.11: PTIT Tính biểu thức hậu tố sau đây sử dụng stack và chỉ ra nội dung stack sau mỗi lệnh: TRUE, FALSE, TRUE, FALSE, NOT, OR, TRUE, OR, OR, AND BÀI 3.1.12: Sử dụng cấu trúc dữ liệu mảng (ngăn xếp), hãy viết chương trình chuyển đổi số tự nhiên n thành số ở hệ cơ số b (2 b 32). 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 K là số lượng các test (k 100). K dòng kế tiếp ghi lại mỗi dòng một test. Mỗi test bao gồm một cặp số n, b. Hai số được viết cách nhau một vài khoảng trống. 77
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Kết quả ra (Output): ghi lại K dòng trong file ketqua.out, mỗi dòng ghi lại bộ ba số n, k, x. Trong đó x là số ở hệ cơ số b được chuyển đổi từ 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 8 2 1000 8 2 32 16 20 32 16 255 16 FF 255 16 100 10 100 100 10 64 32 20 64 32 BÀI 3.1.13: Sử dụng cấu trúc dữ liệu ngăn xếp, 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ố thuận nghịch (số đối xứng). Chuyển đổi N thành số hệ cơ số B cũng là một số thuận nghịch (2 N 512). Thời gian thực hiện chươngPTIT 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 cặp số N, B. Hai số được viết cách nhau một 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ộ ba số N, B, X. Trong đó X là số các số có N chữ số ở hệ cơ số B 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 3 8 2 1000 8 2 32 16 20 78
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 32 16 255 16 FF 255 16 BÀI 3.1.14: Sử dụng cấu trúc dữ liệu ngăn xếp, 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ố thuận nghịch (số đối xứng). Chuyển đổi N thành số hệ cơ số B cũng là một số thuận nghịch (2 N 512). Thời gian thực hiện chương trình không quá 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 cặp số N, B. Hai số được viết cách nhau một 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ộ ba số N, B, X. Trong đó X là số các số có N chữ số ở hệ cơ số B 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 3 PTIT2 2 2 2 2 2 3 0 2 3 5 16 6 5 16 BÀI 3.1.15: Cho file dữ liệu trungto.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các biểu thức số học được biểu diễn dưới dạng trung tố; N dòng kế tiếp, mỗi dòng ghi lại một biểu thức trung tố. 79
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Hãy sử dụng cấu trúc dữ liệu kiểu ngăn xếp viết chương trình dịch chuyển các biểu thức trung tố trong file trungto.in thành file hauto.out. Các biểu thức hậu tố dịch chuyển được ghi lại trong file hauto.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các biểu thức hậu tố dịch chuyển được; N dòng kế tiếp, mỗi dòng ghi lại một biểu thức hậu tố. Ví dụ dưới đây sẽ minh họa cho file trungto.in và hauto.out. trungto.in hauto.out 4 4 ( a + b ) a b + ( a - b ) a b – ( a / b ) a b / ( a * b ) a b * (a + b) * ( a – b) a b + a b - * BÀI 3.1.16: Cho file dữ liệu hauto.in theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các biểu thức số học được biểu diễn dưới dạng hậu tố; N dòng kế tiếp, mỗi dòng ghi lại một biểu thức hậu tố. Hãy sử dụng cấu trúc dữ liệu kiểu ngăn xếp viết chương trình tính toán giá trị của các biểu thức hậu tố trong file hauto.in.PTIT Các biểu thức hậu tố dịch chuyển được ghi lại trong file ketqua.out theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N là số các biểu thức hậu tố; N dòng kế tiếp, mỗi dòng ghi lại giá trị của một biểu thức hậu tố trong file. Ví dụ dưới đây sẽ minh họa cho file hauto.in và ketqua.out. hauto.out ketqua.out 4 4 3 2 + 5 3 2 – 1 3 2 / 1 3 2 * 6 3 2 + 3 2 5 - * 80
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 1.11. Kỹ thuật xử lý trên hàng đợi BÀI 3.2.1: LẬP TRÌNH LỚP VỚI CÁC HÀM CHO HÀNG ĐỢI VÒNG Hoàn thành lớp với các hàm cho hàng đợi vòng như sau: class queue { int data[10]; int front, rear; public : queue(){front=-1;rear=-1} void add(); void remove(); } BÀI 3.2.2: VIẾT CHƯƠNG TRÌNH QUẢN LÝ KHO Viết chương trình quản lý kho đơn giản thực hiện các chức năng sau: 1. Cho phép thêm một mặt hàng vào kho 2. Xuất một mặt hàng raPTIT khỏi kho 3. Xem tất cả hàng hoá trong kho 4. Xem mặt hàng nào kế tiếp sẽ được xuất kho Yêu cầu: 1. Cài đặt cấu trúc dữ liệu HàngHoá: có các dữ liệu nào liệt kê ra 2. Cài đặt một Queue chứa các hàng hoá trong kho 3. Cài đặt các thao tác trên Queue 4. Cài đặt các chức n ăng theo mô tả của bài tập. 81
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.2.3: Nhập vào queue 1 mảng các nhân viên bao gồm các thông tin sau : mã nhân viên, họ tên nhân viên, hệ số lương và in thông tin các nhân viên này ra màn hình. BÀI 3.2.4: HÀNG ĐỢI Cho một hàng đợi đã có một số phần tử. Một thao tác di chuyển trong hàng đợi được định nghĩa như sau: vị trí xuất phát to vị trí đến tức là di chuyển phần tử ở vị trí xuất phát đến vị trí đến. Ví dụ, hàng đợi ban đầu là: Item1 Item2 Item3 Item4 Item5 Thì thao tác 5 to 2 sẽ đưa hàng đợi về dạng: Item1 Item5 Item2 Item3 Item4 Ta có áp dụng nhiều thao tác di chuyển cùng một lúc. Ví dụ nếu hàng đợi là: Item1 Item2 Item3 Item4 Item5 Item6 Item7 Item8 Và chuỗi thao tác là 2 to 6; 6 to 3; 4 to 5; 5 to 2; 7 to 4; 8 to 1 Thì ta có hàng đợi mới sẽ là: PTIT Item8 Item5 Item6 Item7 Item4 Item2 Item1 Item3 Chú ý: trong chuỗi thao tác thì không được có hai thao tác nào trùng nhau. Các thao tác thực hiện đồng thời và phần tử nào được di chuyển đến vị trí mới thì bắt buộc phải ở vị trí đó sau khi hoàn thành, các phần tử khác không liên quan được đẩy sang các vị trí còn lại nhưng vẫn giữ thứ tự trước sau như lúc đầu. Như trong ví dụ trên, vị trí 7,8 không được phần tử nào di chuyển đến nên hai item còn lại là 1 và 3 (là các vị trí không bị di chuyển đi) sẽ ở vị trí đó. Bài toán đặt ra là cho trước hàng đợi và chuỗi thao tác di chuyển, hãy xác định hàng đợi kết quả. Input: Dòng đầu ghi số bộ test không quá 100. Mỗi bộ test gồm: 82
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Dòng đầu ghi hai số m và n (1<=n,m<=20). Trong đó m là số phần tử trong hàng đợi, n là số thao tác di chuyển. Dòng tiếp theo ghi các phần tử trong hàng đợi ban đầu, mỗi phần tử là một chuỗi ký tự ngắn (1 đến 8 ký tự), các phần tử cách nhau một khoảng trống. Không có hai phần tử nào trung nhau. n dòng tiếp theo, mỗi dòng ghi một thao tác di chuyển dưới dạng 2 số nguyên dương theo thứ tự là vị trí xuất phát và vị trí đến. Output Với mỗi bộ test, in ra màn hình trạng thái hàng đợi sau khi áp dụng các thao tác di chuyển. Ví dụ: Input: 3 5 1 alpha beta gamma delta epsilon 5 2 8 6 a b c d e f g h 2 6 6 3 PTIT 4 5 5 2 7 4 8 1 3 2 foo bar baz 3 11 3 Output: alpha epsilon beta gamma delta h e f g d b a cbaz bar foo 83
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.2.5: Viết chương trình con thêm một phần tử trong danh sách đã có thứ tự sao cho ta vẫn có một danh sách có thứ tự bằng cách vận dụng các phép toán cơ bản trên danh sách. BÀI 3.2.6: Viết chương trình con tìm kiếm và xóa một phần tử trong danh sách có thứ tự. BÀI 3.2.7: Viết chương trình con nhận vào từ bàn phím một dãy số nguyên, lưu trữ nó trong một danh sách có thứ tự không giảm, theo cách sau: với mỗi phần tử được nhập vào chương trình con phải tìm vị trí thích hợp để xen nó vào danh sách cho đúng thứ tự. Viết chương trình con trên cho trường hợp danh sách được cài đặt bằng mảng và cài đặt bằng con trỏ và trong trường hợp tổng quát (dùng các phép toán cơ bản trên danh sách). BÀI 3.2.8: Viết chương trình con loại bỏ các phần tử trùng nhau (giữ lại duy nhất 1 phần tử) trong một danh sách có thứ tự không giãm, trong hai trường hợp: cài đặt bằng mảng và cài đặt bằng con trỏ. PTIT BÀI 3.2.9: Viết chương trình con nhận vào từ bàn phím một dãy số nguyên, lưu trữ nó trong một danh sách có thứ tự tăng không có hai phần tử trùng nhau, theo cách sau: với mỗi phần tử được nhập vào chương trình con phải tìm kiếm xem nó có trong danh sách chưa, nếu chưa có thì xen nó vào danh sách cho đúng thứ tự. Viết chương trình con trên cho trường hợp danh sách được cài đặt bằng mảng và cài đặt bằng con trỏ. BÀI 3.2.10: Viết chương trình con trộn hai danh sách liên kết chứa các số nguyên theo thứ tự tăng để được một danh sách cũng có thứ tự tăng. 84
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.2.11: Viết chương trình con xoá khỏi danh sách lưu trữ các số nguyên các phần tử là số nguyên lẻ, cũng trong hai trường hợp: cài đặt bằng mảng và bằng con trỏ. BÀI 3.2.12: Viết chương trình con tách một danh sách chứa các số nguyên thành hai danh sách: một danh sách gồm các số chẵn còn cái kia chứa các số lẻ. BÀI 3.2.13: Hình dưới đây biểu diễn cho mảng SPACE có 10 phần tử dùng để biểu diễn danh sách bằng con nháy (cursor) và hai danh sách L1 ; L2 đang có trong mảng PTIT a. Hãy liệt kê các phần tử trong mỗi danh sách L1, L2. b. Vẽ lại hình đã cho lần lượt sau các lời gọi INSERT_LIST('o',1,L1), INSERT_LIST('m',6,L1), INSERT_LIST('k',9,L1). c. Vẽ lại hình ở câu b. sau khi xoá : x,y. 85
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.2.14: Cho cặp số S và T là các số nguyên tố có 4 chữ số (Ví dụ S = 1033, T = 8197 là các số nguyên tố có 4 chữ số). Sử dụng hàng đợi, hãy viết chương trình tìm cách dịch chuyển S thành T thỏa mãn đồng thời những điều kiện dưới đây: • Mỗi phép dịch chuyển chỉ được phép thay đổi một chữ số của số ở bước trước đó (ví dụ nếu S=1033 thì phép dịch chuyển S thành 1733 là hợp lệ); • Số nhận được cũng là một số nguyên tố có 4 chữ số (ví dụ nếu S=1033 thì phép dịch chuyển S thành 1833 là không hợp lệ, và S dịch chuyển thành 1733 là hợp lệ); • Số các bước dịch chuyển là ít nhất. Ví dụ với S = 1033, T = 8179 sẽ có ít nhất 6 phép dịch chuyển như sau: 1033 1733 3733 3739 3779 8779 81779 . 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 hai số nguyên tố có 4 chữ số. Output: Với mỗi bộ test, viết ra trên một dòng số bước của đường nguyên tố ngắn nhất. Ví dụ cho Input và Output: INPUT OUTPUT 3 6 1033 8179 7 1373 8017PTIT 0 1033 1033 1.12. Kỹ thuật xử lý trên danh sách liên kết BÀI 3.3.1: Đa thức P(x)= anxn+ an-1xn-1+ + a1x + a0 được lưu trữ trong máy tính dưới dạng một danh sách liên kết mà mỗi phần tử của danh sách là một struct có ba trường lưu giữ hệ số, số mũ, 86
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 và trưòng NEXT trỏ đến phần tử kế tiếp. Chú ý cách lưu trữ đảm bảo thứ tự giảm dần theo số mũ của từng hạng tử của đa thức. Ví dụ: đa thức 5x4 - x + 3 được lưu trữ trong danh sách có 3 phần tử như sau: a. Hãy viết chương trình thực hiện được sự lưu trữ này. b. Dựa vào sự cài đặt ở trên, viết chương trình con thực hiện việc cộng hai đa thức. c. Viết chương trình con lấy đạo hàm của đa thức. BÀI 3.3.2: Để lưu trữ một số nguyên lớn, ta có thể dùng danh sách liên kết chứa các chữ số của nó. Hãy tìm cách lưu trữ các chữ số của một số nguyên lớn theo ý tưởng trên sao cho việc cộng hai số nguyên lớn là dễ dàng thực hiện. Viết chương trình con cộng hai số nguyên lớn. BÀI 3.3.3: Để tiện cho việc truy nhập vào danh sách, người ta tổ chức danh sách liên kết có dạng sau, gọi là danh sách nối vòng: PTIT Hãy viết khai báo và các chương trình con cơ bản để cài đặt một danh sách nối vòng. BÀI 3.3.4: Hãy cài đặt một ngăn xếp bằng cách dùng con trỏ. a. Dùng ngăn xếp để viết chương trình con đổi một số thập phân sang số nhị phân. b. Viết chương trình con/hàm kiểm tra một chuỗi dấu ngoặc đúng (chuỗi dấu ngoặc đúng là chuỗi dấu mở đóng khớp nhau như trong biểu thức toán học). 87
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.3.5: Ta có thể cài đặt 2 ngăn xếp vào trong một mảng, gọi là ngăn xếp hai đầu hoạt động của hai ngăn xếp này như sơ đồ sau: Hình vẽ mảng chứa 2 ngăn xếp Hãy viết các chương trình con cần thiết để cài đặt ngăn xếp hai đầu. BÀI 3.3.6: PTIT Mô phỏng việc tạo buffer in một file ra máy in. Buffer xem như là một hàng, khi ra lệnh in file máy tính sẽ thực hiện một cách lặp quá trình sau cho đến hết file: 1. Đưa nội dung của tập tin vào buffer cho đến khi buffer đầy hoặc hết file. 2. In nội dung trong buffer ra máy in cho tới khi hàng rỗng. 3. Hãy mô phỏng quá trình trên để in một file văn bản lên từng trang màn hình. 88
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.3.7: Cài đặt danh sách liên kết kép với các phép toán khởi tạo danh sách rỗng, thêm xoá một phần tử. BÀI 3.3.8: Danh sách liên kết kép nối vòng có dạng sau: Hãy cài đặt danh sách liên kết kép dạng nối vòng như trên. BÀI 3.3.9: GIẤY KHAI SINH Một buổi họp mặt đại gia đình nhân dịp cụ già Ted tròn 100 tuổi, người ta muốn sắp xếp con cháu của cụ theo thứ tự từ tuổi cao xuống thấp. Giả sử ta có thông tin vềgiấy khai sinh của từng người đó. Mỗi giấy khai sinh chỉ viết ba thông tin đơn giản gồm: Tên người cha, Tên người con, Tuổi của người chaPTIT lúc sinh con. Hãy giúp đại gia đình trên tính ra tuổi của từng người con cháu cụ Ted và viết ra danh sách theo thứ tự từ tuổi cao xuống thấp. Input Dòng đầu ghi số bộ test (không quá 100). Với mỗi bộ test: Dòng đầu tiên ghi số X (0<X<100) là số người con cháu cần sắp xếp. Tiếp theo là X dòng, mỗi dòng ghi thông tin về một giấy khai sinh của từng người (thứ tự ngẫu nhiên) gồm 3 thành phần, mỗi thành phần cách nhau một khoảng trống: o Tên người cha: không quá 20 ký tự và không chứa khoảng trống o Tên người con: không quá 20 ký tự và không chứa khoảng trống o Tuổi của người cha khi sinh con: 1 số nguyên dương, không quá 100. 89
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 Output Với mỗi bộ test, in ra màn hình thứ tự bộ test (xem thêm trong bộ test ví dụ), sau đó lần lượt là từng người trong danh sách tuổi từ cao xuống thấp (không tính cụ Ted). Mỗi người viết ra hai thông tin: tên, một khoảng trống rồi đến tuổi của người đó. Nếu hai người có cùng tuổi thì xếp theo thứ tự từ điển. Ví dụ: Input: 2 1 Ted Bill 25 4 Ray James 40 James Beelzebub 17 Ray Mark 75 Ted Ray 20 Output: DATASET 1 PTIT Bill 75 DATASET 2 Ray 80 James 40 Beelzebub 23 Mark 5 90
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 BÀI 3.3.10: 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 danh sách liên kết đơn (kép), hãy tìm tập các từ và tần xuất xuất hiện của mỗi từ 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 3 AB AC AD AE AF AB AC AD AH AK AB 0.2 PTITAC 0.2 AD 0.2 BÀI 3.3.11: 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à 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 danh sách liên kết đơn (kép), hãy viết chương trình tá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; 91