Kĩ thuật lập trình - Bài thực hành số 1

ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 1 2ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Phân tích bài tốn mảng nhiều chiều, • Liệt kê các thơng tin cần lưu ý khi áp dụng việc khai báo – truy xuất mảng nhiều chiều, • Xây dựng chương trình sử dụng mảng nhiều chiều. 3ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: nhập điểm của các sinh viên trong 1 lớp học cĩ m dãy bàn, mỗi dãy cĩ n chỗ ngồi và tính điểm trung bình, cho biết thơng tin về sv cĩ điểm cao nhất và thấp nhất. • Bước 1: phân tích các thành phần của mảng nhiều chiều, • Bước 2: vẽ lưu đồ, • Bước 3: viết chương trình. 4ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: tính và in ra màn hình tam giác Pascal bậc n (0 < n ≤ 10) • Bước 1: phân tích các thành phần của mảng nhiều chiều, – Lưu ý về cấu tạo của tam giác Pascal, • Bước 2: vẽ lưu đồ, • Bước 3: viết chương trình: – Lưu ý khơng xuất số 0. 5ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: nhập vào ma trận A cĩ kích thước m x n và ma trận B cĩ kích thước p x q. Hãy kiểm tra xem cĩ thể cộng 2 ma trận này hay khơng, nếu cĩ thì xuất ra kết quả, • Bước 1: phân tích các thành phần của mảng nhiều chiều, • Bước 2: vẽ lưu đồ, – ðiều kiện thực hiện phép cộng ma trận, – Cách thực hiện phép cộng ma trận, • Bước 3: viết chương trình. ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 2 2ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Áp dụng mảng 2 chiều cho các bài tốn ma trận, • Kiểm tra tính chất của ma trận, • Thực hiện các phép tính trên ma trận. 3ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: nhập ma trận A cĩ kích thước mxn. Hãy kiểm tra xem ma trận A cĩ phải là ma trận vuơng, ma trận đối xứng, ma trận chéo hay khơng? • Bước 1: phân tích các thành phần của mảng 2 chiều, • Bước 2: vẽ lưu đồ và lưu ý các tính chất: – Ma trận vuơng: m = n, – Ma trận đối xứng: A[i][j] = A[j][i] với mọi i,j – Ma trận chéo: A[i][i] != 0 với mọi i và A[i][j] = 0 với mọi i!=j • Bước 3: viết chương trình. 4ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: nhập ma trận A cĩ kích thước mxn và ma trận B cĩ kích thước pxq. Hãy kiểm tra xem cĩ thể thực hiện AxB hay khơng, nếu được hãy tính C=AxB? • Bước 1: phân tích các thành phần của các mảng 2 chiều, • Bước 2: vẽ lưu đồ và lưu ý các tính chất: – Phép tính AxB chỉ xảy ra khi: n=p – Kết quả C[i][j] = ΣA[i][k]xB[k][j] với k=0..(n-1) • Bước 3: viết chương trình. 5ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: nhập ma trận A cĩ kích thước mxn. Trên mỗi hàng của ma trận A, tính tổng các phần tử ở các vị trí ứng với giá trị trong dãy Fibonacci. Vd: tính tổng của các vị trí số 1 + vị trí số 1 + vị trí số 2 + vị trí số 3 + vị trí số 5 • Bước 1: phân tích các thành phần của các mảng 2 chiều, • Bước 2: Xác định các giá trị trong dãy Fibonacci và các vị trí trong mỗi hàng cần được tính tổng: – Gọi F là dãy Fibonacci: F[0] = 1, F[1] = 1, F[2] = 2, F[3] = 3, F[4] = 5 – Tính tổng A[i][F[0]] + A[i][F[1]] + A[i][F[2]] + • Bước 3: viết chương trình. ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 3 2ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Áp dụng mảng 2 chiều cho bài tốn ma trận nâng cao, • Áp dụng con trỏ thay thế cho ma trận 1 chiều trong các bài tốn. 3ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: Nhập vào từ bàn phím hai số nguyên dương m và n (0 < m, n < = 20). Hãy tạo một ma trận xoắn ốc cĩ kích thước m x n, xuất phát từ điểm gĩc dưới phải và theo hướng đi lên. Ví dụ cho trường hợp m = 4, n = 5 như sau: • Bước 1: phân tích các thành phần của mảng 2 chiều, • Bước 2: vẽ lưu đồ và lưu ý các tính chất: – ðộ thay đổi theo chiều dọc và ngang sau mỗi bước, – Quy luật của độ thay đổi theo chiều dọc và chiều ngang, – Lưu ý: điều kiện vượt ra ngồi giới hạn của 4 gĩc, • Bước 3: viết chương trình. 114131211 215201910 31617189 45678 4ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: Nhập vào điểm của n sinh viên và cho biết thơng tin về điểm cao nhất và điểm trung bình của n sinh viên (sử dụng con trỏ), • Bước 1: phân tích bài tốn với trường hợp mảng 1 chiều, • Bước 2: thay thế mảng 1 chiều bằng con trỏ: – Khai báo con trỏ, – Khởi tạo con trỏ, – Truy xuất giá trị con trỏ, • Bước 3: viết chương trình. 5ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: Nhập vào điểm của n sinh viên và sắp xếp lại theo thứ tự từ nhỏ đến lớn (sử dụng con trỏ), • Bước 1: phân tích bài tốn với trường hợp mảng 1 chiều, • Bước 2: thay thế mảng 1 chiều bằng con trỏ: – Khai báo con trỏ, – Khởi tạo con trỏ, – Truy xuất giá trị con trỏ, • Bước 3: viết chương trình. Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 4 2Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH MỤC TIÊU • Sử dụng mảng và con trỏ để xuất nhập chuỗi ký tự, • Thực hiện các xử lý chuỗi ký tự. 3Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI 1 • Yêu cầu: nhập, lưu trữ và xuất ra màn hình chuỗi ký tự và sử dụng mảng để lưu trữ chuỗi, • Lưu ý: – Khai báo mảng, – Sự khác biệt Nhập mảng ký tự và Chuỗi ký tự, – Truy xuất Chuỗi ký tự. 4Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI 2 • Yêu cầu: xây dựng hàm để xĩa các khoảng trắng ở đầu và cuối chuỗi (được nhập trong bài 1), xĩa các khoảng trắng thừa ở giữa các từ trong chuỗi, • Lưu ý: – Vị trí bắt đầu và vị trí cuối cùng của mảng, – Sự thay đổi độ dài của chuỗi ký tự sau mỗi lần xĩa 1 ký tự. 5Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI 3 • Yêu cầu: xây dựng hàm để để đếm số lần xuất hiện của một chuỗi s2 trong chuỗi đã được nhập trước đĩ (trong bài 1), • Lưu ý: – Tìm vị trí đầu tiên của chuỗi s2 trong chuỗi chính, – Tìm vị trí đầu tiên của chuỗi s2 trong phần cịn lại của chuỗi chính sau khi đã tìm thấy lần trước 6Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI 4 • Yêu cầu: xây dựng hàm để viết hoa các ký tự đầu mỗi từ trong chuỗi đã được nhập trước đĩ (trong bài 1), • Lưu ý: – Kiểm tra ký tự là chữ cái, – Nhận diện ký tự đầu của mỗi từ. 7Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI 5 • Yêu cầu: thực hiện lại các bài từ 1-4 bằng cách sử dụng con trỏ. ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 5 2ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Sử dụng các đối tượng xuất và nhập từ tập tin, • Thực hiện việc xuất nhập dữ liệu từ tập tin. 3ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: Nhập vào từ tập tin “input.txt” một chuỗi s và in chuỗi s ra tập tin “output.txt” • Bước 1: lưu ý các đối tượng dùng để nhập – xuất từ tập tin, • Bước 2: Lưu ý các thao tác để nhập – xuất từ tập tin, • Bước 3: viết chương trình. 4ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: Nhập vào từ tập tin “input.txt” một chuỗi s và xuất chuỗi s ra tập tin “output.txt” với quy tắc “ký tự hoa thành ký tự thường và ngược lại” • Bước 1: phân tích các bước xuất nhập dữ liệu từ tập tin, • Bước 2: phân tích các bước xử lý chuỗi, • Bước 3: viết chương trình. 5ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: Nhập vào từ tập tin “input.txt” một chuỗi s và xuất chuỗi s sau khi đã được xử lý ra tập tin “output.txt” • Lưu ý: – ðầu/cuối chuỗi khơng được là khoảng trắng, – Giữa hai từ chỉ tồn tại duy nhất 1 khoảng trắng. 6ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 4 • Bài tốn: Nhập vào từ tập tin “input.txt” một văn bản và xuất văn bản đĩ ra tập tin “output.txt” • Lưu ý: – Nhập từng dịng của văn bản và xuất kết quả của ngay dịng đĩ, – Kiểm tra điều kiện để tiếp tục nhập các dịng của văn bản với eof(). 7ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 5 • Bài tốn: Nhập vào từ tập tin “input.txt” một văn bản và xuất văn bản đĩ sau khi đã được xử lý ra tập tin “output.txt” • Lưu ý: xử lý giống như Bài 3. Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 6 2Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Nhận diện bài tốn đệ quy, • Miêu tả các thành phần của một hàm đệ quy, • Xây dựng chương trình giải các bài tốn đệ quy. 3Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: Nhập vào số nguyên dương n, hãy in ra các số từ 1 đến n bằng đệ quy, • Bước 1: Phân tích mối liên quan của trường hợp xử lý số n và số n-1, từ đĩ suy ra cơng thức truy hồi và điểm hội tụ, • Bước 2: Xây dựng hàm đệ quy với các thành phần “gọi chính nĩ” và thành phần dừng, • Bước 3: viết chương trình. 4Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: Nhập vào số nguyên dương n, hãy in ra các số từ n đến 1 bằng đệ quy, • Bước 1: Phân tích mối liên quan của trường hợp xử lý số n và số n-1, từ đĩ suy ra cơng thức truy hồi và điểm hội tụ, • Bước 2: Xây dựng hàm đệ quy với các thành phần “gọi chính nĩ” và thành phần dừng, • Bước 3: viết chương trình. 5Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: Nhập vào số nguyên dương n, hãy đếm số chữ số của n bằng đệ quy, • Bước 1: Phân tích mối liên quan của trường hợp xử lý số n và số n/10 (hơn nhau 1 chữ số), từ đĩ suy ra cơng thức truy hồi và điểm hội tụ (lưu ý khi xử lý các số cĩ 1 chữ số), • Bước 2: Xây dựng hàm đệ quy với các thành phần “gọi chính nĩ” và thành phần dừng, • Bước 3: viết chương trình. 6Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 4 • Bài tốn: Nhập vào số nguyên dương n, hãy in ra số cĩ thứ tự ngược lại của số n (vd: n=123 sẽ in ra 321), • Bước 1: Phân tích mối liên quan của việc đảo 1 chữ số cuối lên phía trước và thực hiện việc xử lý phần cịn lại và điều kiện để hồn tất cơng việc, • Bước 2: Xây dựng hàm đệ quy với các thành phần “gọi chính nĩ” và thành phần dừng, • Bước 3: viết chương trình. 7Đại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 5 • Bài tốn: Nhập vào số nguyên dương n, hãy in ra các hốn vị của bộ số từ 1 đến n, • Bước 1: Mỗi một hốn vị là một sự thay đổi vị trí của 1 phần tử. Lấy 1 phần tử làm chuẩn cho sự thay đổi vị trí và mong muốn được nối kết với hốn vị của các phần tử cịn lại, • Bước 2: Xây dựng hàm đệ quy với các thành phần “gọi chính nĩ” và thành phần dừng, • Bước 3: viết chương trình. ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin KỸ THUẬT LẬP TRÌNH BÀI THỰC HÀNH SỐ 7 2ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Mục tiêu • Ơn tập: – Các bài tốn mảng 2 chiều, ma trận, – Các bài tốn xử lý chuỗi bằng con trỏ, – Các bài tốn xuất nhập dữ liệu qua tập tin, – Các bài tốn đệ quy. 3ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 1 • Bài tốn: Bài tốn ma trận, • Xuất nhập dữ liệu của ma trận, • Kiểm tra tính chất của ma trận: vuơng, đối xứng, chéo, • Thực hiện các phép tốn ma trận: cộng, trừ, nhân. 4ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 2 • Bài tốn: Thực hiện lại bài 1 với việc xuất nhập dữ liệu thơng qua tập tin. 5ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 3 • Bài tốn: Bài tốn xử lý chuỗi, • Xuất nhập dữ liệu của chuỗi (sử dụng mảng), • Tìm kiếm ký tự, chuỗi con, • Thay thế các ký tự, xĩa các khoảng trắng, • Xử lý văn bản gồm nhiều dịng. 6ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 4 • Bài tốn: Thực hiện bài tốn 3 với việc xuất nhập dữ liệu qua tập tin. 7ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 5 • Bài tốn: Thực hiện bài tốn 4 với việc sử dụng con trỏ. 8ðại học Mở TP.Hồ Chí Minh Khoa Cơng Nghệ Thơng Tin ThS VÕ NHẬT VINH Bài 6 • Bài tốn: Thực hiện bài tốn đệ quy • ðếm số, in số, • Tính giai thừa, lũy thừa, Fibonacci, tam giác Pascal, • Hốn vị, tháp Hà Nội. Page 1 of 2 TRƯỜNG ðẠI HỌC MỞ TP.HCM KHOA CƠNG NGHỆ THƠNG TIN ðỀ THI MƠN: Kỹ thuật lập trình (Lần 1) HỌC KỲ: 2 NĂM HỌC: 2007 - 2008 LỚP: T7B2 HỆ: Chính quy Thời gian làm bài: 120 phút Sinh viên được sử dụng tài liệu trên giấy. Bài 1: Bài làm phải được lưu lại trong tập tin Bai1.cpp (3đ): Nhập vào từ bàn phím hai số nguyên dương m và n (0 < m, n < = 20). Hãy tạo một ma trận xoắn ốc cĩ kích thước m x n, xuất phát từ điểm gĩc dưới phải và theo hướng đi lên. Kết quả được lưu trong tập tin output.txt. Ví dụ cho trường hợp m = 4, n = 5 như sau: 8 7 6 5 4 9 18 17 16 3 10 19 20 15 2 11 12 13 14 1 Bài 2: Bài làm phải được lưu lại trong tập tin Bai2.cpp (2đ): Hãy đọc vào một văn bản từ tập tin input1.txt. Hãy cho biết số ký tự trên mỗi dịng của văn bản và cho biết giá trị lớn nhất, nhỏ nhất và giá trị trung bình. In kết quả ra tập tin output1.txt. Hãy in tồn bộ nội dung của văn bản gốc ban đầu bằng tất cả các ký tự in hoa sang tập tin output2.txt. Hãy in tồn bộ nội dung của văn bản gốc ban đầu bằng tất cả các ký tự thường sang tập tin output3.txt. Yêu cầu: sử dụng con trỏ để lưu trữ chuỗi ký tự. Bài 3: a/ Bài làm phải được lưu lại trong tập tin Bai3A.cpp (1đ): Viết chương trình tìm Ước số chung lớn nhất của 2 số nguyên dương bằng phương pháp đệ quy. b/ Bài làm phải được lưu lại trong tập tin Bai3B.cpp (1đ): Viết chương trình in ra theo thứ tự ngược lại của một số nguyên dương bằng phương pháp đệ quy. Bài 4: Bài làm phải được lưu lại trong tập tin Bai4.cpp (3đ): Xây dựng lớp HINH_CHU_NHAT để biểu diễn một hình chữ nhật và cĩ các thuộc tính DAI, RONG, TAM tương ứng với chiều dài, chiều rộng và tâm của hình chữ nhật (giao điểm 2 đường Page 2 of 2 chéo). Lớp HINH_CHU_NHAT cĩ phương thức getCorner( ) để lấy tọa độ của đỉnh trên trái của hình chữ nhật. Xây dựng tiếp tốn tử so sánh bằng giữa hai đối tượng thuộc lớp HINH_CHU_NHAT. TAM là một đối tượng thuộc lớp TOA_DO (biểu diễn cho tọa độ một điểm). Lớp TOA_DO cĩ các thuộc tính X, Y biểu diễn hồnh độ và tung độ của 1 điểm. Lớp TOA_DO cĩ các phương thức getX( ), getY( ), setX( ), setY( ) để lấy giá trị hoặc gán giá trị cho X, Y. Ghi chú: các giá trị tọa độ, độ dài cạnh đều là số nguyên dương. Xác nhận của lãnh đạo khoa Ngày 26 tháng 05 năm 2008 Giảng viên ra đề ThS Võ Nhật Vinh