Bài tập tổng hợp môn Nhập môn lập trình

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HCM

KHOA CÔNG NGHỆ THÔNG TIN

HỆ CHÍNH QUI – LỚP CỬ NHÂN TÀI NĂNG 2014

MÔN: NHẬP MÔN LẬP TRÌNH

BÀI TẬP TỔNG HỢP

ĐẶNG HOÀNG HẢI

ĐỖ NGUYÊN KHA

TP.HCM, ngày 21 tháng 12 năm 2014

{dhhai, dnkha}@fit.hcmus.edu.vn

1 Tính toán cơ bản

1. Viết hàm tính tổng ꢀ ꢀ = ꢀ + ꢀ^!+ ꢀ^!+ ⋯ + ꢀ^!

!

2. Viết hàm tính tổng ꢀ ꢀ = ꢀ + _!!!

+ _!!!!!+ ⋯ + _!!!!!!⋯!!

3. Viết hàm tính xấp xỉ ꢀ^!bằng khai triển Taylor như sau (ꢀ là số thực):

!

ꢀ^!ꢀ^!

+

ꢀ^!

ꢀ^!= 1 + ꢀ +

+ ⋯ =

2! 3!

ꢀ!

!!!

Hãy tính ꢀ^!xấp xỉ với số lũy thừa ꢀ = 5, ꢀ = 10, ꢀ = 20, ꢀ = 50 v.v. Xuất kết quả

ra ít nhất 10 chữ số thập phân để thấy độ chính xác của xấp xỉ.

4. Viết hàm tính xấp xỉ sin ꢀ bằng khai triển Taylor như sau (ꢀ là số thực tính bằng

radian):

!

ꢀ^!ꢀ^!ꢀ^!ꢀ^!

ꢀ^!!!!

!

sin ꢀ = ꢀ −

+

−

+

− ⋯ =

−1

3! 5! 7! 9!

(2ꢀ + 1)!

!!!

Hãy tính sin ꢀ xấp xỉ với số lũy thừa ꢀ = 5, ꢀ = 10, ꢀ = 20, ꢀ = 50 v.v. Xuất kết

quả ra ít nhất 10 chữ số thập phân để thấy độ chính xác của xấp xỉ.

5. Hãy xác định khai triển Taylor của cos ꢀ và tính xấp xỉ.

6. Viết hàm tính tổng tất cả các ước số nguyên dương của số nguyên dương n.

7. Viết hàm tính tích tất cả các ước số nguyên dương của số nguyên dương n.

3

{dhhai, dnkha}@fit.hcmus.edu.vn

8. Viết hàm kiểm tra số nguyên dương n có phải là số hoàn hảo (perfect number) hay

không. Số hoàn hảo là số bằng đúng tổng tất các ước số dương của nó trừ chính

nó.

Ví dụ số 6 là số hoàn hảo: 6 = 1 + 2 + 3

Ví dụ số 28 là số hoàn hảo: 28 = 1 + 2 + 4 + 7 + 14

9. Số hoàn hảo chẵn: Euclid chứng minh được rằng 2^!!!(2^!− 1) là một số hoàn hảo

chẵn khi 2^!− 1 là một số nguyên tố. Để 2^!− 1 là số nguyên tố (số nguyên tố

Mersenne), thì bản thân ꢀ cũng phải là số nguyên tố:

2^!− 1 nguyên tố ⇒ ꢀ nguyên tố

Điều ngược lại không đúng: ꢀ nguyên tố ⇏ 2^!− 1 nguyên tố.

Ví dụ:

ꢀ = 2: 2^!2^!− 1 = 6

ꢀ = 3: 2^!2^!− 1 = 28

ꢀ = 5: 2^!2^!− 1 = 496

Dựa vào kết quả của Euclid, hãy đề xuất thuật toán hiệu quả kiểm tra một số có

phải là số hoàn hảo chẵn hay không.

10.Viết hàm đếm tần số của các chữ số thập phân của số nguyên n. Ví dụ:

123456789 có các tần số là: 0:0, 1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1

1996 có các tần số là: 0:0, 1:1, 2:0, 3:0, 4:0, 5:0, 6:1, 7:0, 8:0, 9:2

11.Viết hàm tính tổng bù không quá 10 của các chữ số thập phân của số nguyên n. Ví

dụ: 123456789 => 45 => 9.

4

{dhhai, dnkha}@fit.hcmus.edu.vn

12.Viết hàm tính ước chung lớn nhất của 2 số nguyên dương a, b.

13.Viết hàm tính bội chung nhỏ nhất của 2 số nguyên dương a, b.

14.Viết hàm cài đặt thuật toán hiệu quả để kiểm tra số tự nhiên n có phải là số lũy

thừa hoàn hảo (perfect power) hay không. n là số lũy thừa hoàn hảo nếu có dạng n

= a^b với a, b là số tự nhiên >1.

15.Viết hàm đếm số bit của một số nguyên n.

Phương pháp Newton

Phương pháp Newton là phương pháp tìm nghiệm thực của phương trình ꢀ ꢀ = 0,

bằng cách cải thiện các xấp xỉ của nghiệm ꢀ qua từng bước lặp. Cụ thể như sau:

Cho trước hàm ꢀ(ꢀ) xác định trên ℝ, có đạo hàm ꢀ^!, ta bắt đầu với ꢀ_!là dự đoán

(guess) nghiệm ꢀ của ꢀ ꢀ = 0. Ta cải thiện xấp xỉ nghiệm ꢀ bằng ꢀ_!, với

ꢀ ꢀ_!

ꢀ_!= ꢀ_!−

ꢀ^!ꢀ_!

Quá trình cải thiện này được lặp như sau:

ꢀ ꢀ_!

ꢀ_!!!= ꢀ_!−

ꢀ^!ꢀ_!

với n đủ lớn cho tới khi đạt được độ chính xác mong muốn.

5

{dhhai, dnkha}@fit.hcmus.edu.vn

16.Viết hàm tính căn bậc 2 (square root) dựa trên phương pháp Newton.

Hàm tính ꢀ thực chất là hàm tìm nghiệm của phương trình ꢀ ꢀ = ꢀ^!− ꢀ = 0.

Khởi động với ꢀ_!= 1, sử dụng phương pháp Newton hãy tính xấp xỉ căn bậc 2 của một

số thực dương ꢀ, với số lần lặp cải tiến xấp xỉ là ꢀ = 5, ꢀ = 10, ꢀ = 20, ꢀ = 50 v.v.

Xuất kết quả ra ít nhất 10 chữ số thập phân để thấy độ chính xác của xấp xỉ.

17.Mở rộng hàm tính căn bậc 2 với mức xấp xỉ (sai số) ꢀ. Tức là dừng vòng lặp cải

tiến xấp xỉ khi thấy sai số giữa ꢀ_!và ꢀ_!!!nhỏ hơn ꢀ: ꢀ_!− ꢀ_!!!< ꢀ. Thử

nghiệm và đếm số vòng lặp cần thực hiện với các giá trị khác nhau của ꢀ.

18.Thay đổi hàm tính căn bậc 2 với giá trị khởi tạo ban đầu ꢀ_!tốt hơn. Nếu giá trị

khởi tạo ban đầu ở khá xa so với giá trị thực, tốc độ của hàm tính căn sẽ bị giảm

thiểu. Ta cần chọn một giá trị ban đầu ꢀ_!gần với giá trị thực để tăng tốc thuật

toán. Nếu biểu diễn nhị phân của ꢀ có dạng ꢀ×2^!!, với 0.1_!≤ ꢀ < 10_!,

ꢀ = ꢀ×2^!, ta có thể xấp xỉ thô ꢀ ≈ 2^!, tức khởi động ꢀ_!= 2^!.

19.Hãy viết hàm cài đặt thuật toán tính căn bậc 3 (cube root - ∛) bằng phương pháp

Newton.

20.Xét công thức tính trung bình như sau:

!!!

ꢀ

!

ꢀꢁꢂꢃꢄꢅꢂ =

ꢀ_!− ꢀꢁꢂ +

ꢀ_!− ꢀꢁꢂ + ꢀꢁꢂ − ꢀꢁꢂ

2

6

{dhhai, dnkha}@fit.hcmus.edu.vn

Trong đó ꢀꢁꢂ, ꢀꢁꢂ lần lượt là giá trị lớn nhất, nhỏ nhất của ꢀ số thực

ꢀ_!, ꢀ_!, ꢀ_!, … , ꢀ_!!!. Hãy viết hàm tính ꢀꢁꢂꢃꢄꢅꢂ mà không dùng mảng để lưu trữ các

phần tử. Các phần tử sẽ được truyền vào liên tục bằng cách đọc từ nhập chuẩn/tập tin.

2 Thao tác trên mảng

21.Viết hàm tìm số âm lớn nhất trong mảng một chiều các số thực. Trả về 0 nếu

không thấy số âm.

22.Viết hàm tìm số nguyên tố lớn nhất trong mảng một chiều các số nguyên. Trả về 0

nếu không tìm thấy số nguyên tố.

23.Viết hàm tìm trong mảng một chiều các số thực số xa x nhất (x cho trước).

24.Viết hàm tìm ước chung lớn nhất của tất cả các số trong mảng một chiều các số

nguyên dương.

25.Viết hàm tìm bội chung nhỏ nhất của tất cả các số trong mảng một chiều các số

nguyên dương.

26.Viết hàm phát sinh ngẫu nhiên một mảng n số nguyên trong khoảng [a, b].

27.Viết hàm đếm tần suất xuất hiện của giá trị x trong mảng một chiều các số thực.

28.Viết hàm đếm tần suất xuất hiện của các số trong mảng một chiều các số nguyên.

Sắp kết quả tần suất theo giá trị của các số với thứ tự tăng dần.

29.Viết hàm dịch phải xoay vòng k lần các phần tử trong mảng

30.Viết hàm tính khoảng cách trung bình giữa các giá trị trong mảng một chiều các số

thực. Khoảng cách giữa 2 số tính bằng giá trị tuyệt đối.

7

{dhhai, dnkha}@fit.hcmus.edu.vn

31.Viết hàm tính vector n chiều là tổng 2 vector n chiều số thực cho trước. Mỗi vector

n chiều là 1 mảng n phần tử, với mỗi phần tử đại diện cho một chiều i. Vector

ꢀ = (ꢀ_!, ꢀ_!, … , ꢀ_!, … , ꢀ_!!!, ꢀ_!)

Phép cộng 2 vector n chiều thực hiện bằng cách cộng giá trị theo từng chiều.

32.Viết hàm tính tích vô hướng của 2 vector n chiều số thực cho trước. Tích vô

!

hướng ꢀ ∙ ꢀ^!= _!!!ꢀ_!ꢀ_!^!

!

33.Viết hàm tính độ lớn của vector n chiều số thực. Độ lớn ꢀ =

34.Viết hàm tính góc ꢀ giữa 2 vector n chiều số thực, tính theo radian.

_!!!ꢀ_!^!.

!

ꢀ∙ꢀ

Biết cos ꢀ =

và biết khai triển Taylor của hàm ngược cos^!!ꢀ với ꢀ ≤ 1 là

!

ꢀ

!

1

1 ꢀ^!1 3 ꢀ^!1 3 5 ꢀ^!

1

+ ⋯ = ꢀ −

2

(2ꢀ)! ꢀ^!!!!

4^!ꢀ! 2ꢀ + 1

cos^!!ꢀ = ꢀ − ꢀ +

+

!

2

2 3 2 4 5 2 4 6 7

!!!

35.Cho trước 2 mảng số thực một chiều sắp tăng dần có kích thước n và m. Viết hàm

trộn 2 mảng ban đầu thành một mảng một chiều mới có kích thước n+m, có phần

tử là các phần tử của 2 mảng ban đầu và vẫn sắp tăng dần (Merge sort).

36.Tìm phần tử lớn thứ k trong mảng. Cho một mảng một chiều n số thực, hãy viết

hàm tìm phần tử lớn thứ k trong mảng, tức là phần tử lớn hơn hoặc bằng k-1 số

trong mảng, và nhỏ hơn hoặc bằng n-k số còn lại.

37.Phân hoạch mảng một chiều (Quicksort partition). Cho một mảng một chiều n số

thực, hãy phân hoạch lại mảng (sắp lại các phần tử trong mảng) để đồng thời thỏa

tất cả các điều kiện sau:

8

{dhhai, dnkha}@fit.hcmus.edu.vn

• Phần tử lớn thứ n/2 nằm ở vị trí n/2 trong mảng (vị trí đếm từ 1)

• Các phần tử nhỏ hơn hoặc bằng phần tử lớn thứ n/2 nằm trước phần tử

n/2 trong mảng (bên trái mảng) . Thứ tự của các phần tử này không quan

trọng.

• Các phần tử lớn hơn hoặc bằng phần tử lớn thứ n/2 nằm sau phần tử n/2

trong mảng (bên phải mảng). Thứ tự của các phần tử này không quan

trọng.

38.Một ma trận nxm (n dòng, m cột) có thể được biểu diễn bằng mảng 2 chiều nxm.

Hãy viết hàm tính ma trận tổng C của 2 ma trận nxm A và B: C = A + B. Ma trận

tổng C cũng là một ma trận nxm với mỗi phần tử C(i,j) = A(i,j) + B(i,j)

39.Hãy viết hàm tính ma trận hiệu C = A – B: C(i,j) = A(i,j) – B(i,j).

40.Viết hàm tính tích hai ma trận. Hai ma trận chỉ có thể nhân được với nhau nếu số

cột của ma trận trước bằng số dòng của ma trận sau. Tích của ma trận A nxp với

ma trận B pxm là ma trận C nxm, với

C(i,j) = tích vô hướng của dòng i của A với cột j của B

41.Viết hàm tìm điểm yên ngựa trên ma trận. Điểm yên ngựa là điểm có giá trị nhỏ

nhất trên hàng nhưng lớn nhất trên cột, hoặc là điểm có giá trị lớn nhất trên hàng

nhưng nhỏ nhất trên cột.

9

{dhhai, dnkha}@fit.hcmus.edu.vn

3 Cấu trúc

42.Viết cấu trúc Phân số, trong đó tử là một số nguyên, mẫu là một số nguyên dương.

Viết các hàm tính tổng, hiệu, tích, thương của 2 phân số. Viết hàm rút gọn phân

số. Viết hàm in phân số, có thể in ra dạng hỗn số.

43.Viết cấu trúc Số phức, với số phức c có dạng c = a + bi, với a, b là số thực, a là

phần thực, b là phần ảo. Viết các hàm tính tổng, hiệu, tích, thương của 2 số phức,

biết i^2 = -1. Viết hàm tính lũy thừa bậc n của một số phức.

44.Viết hàm tính khoảng cách trung bình giữa các phần tử trong mảng một chiều các

điểm 2D (2 chiều tọa độ x, y) theo khoảng cách Euclid.

45.Viết hàm tính khoảng cách trung bình giữa các phần tử trong mảng một chiều các

điểm 2D (2 chiều tọa độ x, y) theo khoảng cách Manhattan.

46.(Closest pair) Viết hàm tìm 2 điểm gần nhau nhất trong một mảng các điểm 2D.

Khoảng cách tính theo khoảng cách Euclid.

47.Viết hàm tính khoảng cách trung bình giữa các phần tử trong mảng một chiều các

điểm 3D (3 chiều tọa độ x, y, z) theo khoảng cách Euclid.

48.Viết cấu trúc Đơn thức biểu diễn đơn thức dạng ꢀ(ꢀ) = ꢀꢀ^!, với a là hệ số và n là

số mũ. Viết các hàm tính giá trị của ꢀ(ꢀ) với giá trị cụ thể của ꢀ, hàm tính tích,

thương của các đơn thức.

49.Viết cấu trúc Đa thức biểu diễn đa thức dạng ꢀ ꢀ = ꢀ_!ꢀ^!+ ꢀ_!!!ꢀ^!!!+ ⋯ +

ꢀ_!ꢀ_!+ ꢀ_!. Viết các hàm tính giá trị đa thức với giá trị cụ thể của biến ꢀ, hàm tính

tổng, hiệu, tích, thương, phần dư các đa thức.

10

{dhhai, dnkha}@fit.hcmus.edu.vn

50.Viết cấu trúc Ngày giờ (datetime) biểu diễn thời gian, gồm thông tin

ngày/tháng/năm giờ/phút/giây. Viết các hàm nhận vào datetime và:

• Kiểm tra năm nhuận

• Xác định ngày thứ mấy trong năm

• Xác định ngày thứ mấy trong tuần

• Xác định giây thứ mấy trong năm

• Xác định khoảng cách giữa 2 thời điểm datetime tính bằng

giây/phút/giờ/ngày/tháng/năm

51.Viết cấu trúc Tam giác trong không gian 2 chiều gồm tọa độ 3 đỉnh của tam giác.

Viết hàm:

• Kiểm tra 3 đỉnh có tạo thành tam giác không

• Tính chu vi, diện tích tam giác

• Tính tọa độ trọng tâm tam giác

• Phân loại tam giác: đều, vuông, vuông cân, cân, thường

52.Đường tròn trong không gian 2D được biểu diễn bằng tọa độ tâm và bán kính. Cho

một mảng các đường tròn 2D, hãy viết hàm tìm xem có đường tròn nào bao hết tất

cả các đường tròn khác trong mảng hay không.

53.Xây dựng cấu trúc vé xem phim dựa trên một vé xem phim thực tế như sau:

11

{dhhai, dnkha}@fit.hcmus.edu.vn

4 Chuỗi kí tự và tập tin

54.Viết hàm đếm số kí tự của một chuỗi kí tự kết thúc bằng kí tự rỗng ‘\0’.

55.Viết hàm đếm số dòng của một tập tin văn bản.

56.Viết hàm đếm số kí tự không khoảng trắng (không phải kí tự khoảng trắng, tab \t,

xuống dòng \n) của một tập tin văn bản.

57.Viết hàm đếm số từ (từ phân tách bởi khoảng trắng) của một chuỗi kí tự.

58.Viết hàm đếm số từ của một tập tin văn bản.

59.Viết hàm tách từ của một chuỗi kí tự.

60.Viết hàm chuyển một chuỗi kí tự số thành giá trị số nguyên.

61.Viết hàm chuyển một chuỗi kí tự số thành giá trị số thực.

12

{dhhai, dnkha}@fit.hcmus.edu.vn

62.Viết hàm sao chép một tập tin văn bản ra một tập tin văn bản khác.

63.Viết hàm thống kê tần suất xuất hiện của các từ trong một tập tin văn bản.

64.Viết hàm xử lý cắt dòng cho một tập tin văn bản sao cho mỗi dòng có không quá n

kí tự.

65.Viết hàm đảo ngược chuỗi.

5 Bài tập tổng hợp

66.THỜI KHÓA BIỂU

struct Activity {

Cấu trúc hoạt động: mô tả thông tin

char info[MAXSIZE]; // Mô tả hoạt động

của một hoạt động, bao gồm một

Time start; // Thời gian bắt đầu

đoạn văn bản mô tả, thời gian bắt

Time end;

// Thời gian kết thúc

đầu, thời gian kết thúc.

};

• Viết hàm tính thời lượng của một hoạt động (Activity)

• Viết hàm in ra thông tin một hoạt động

• Viết cấu trúc thời khóa biểu TimeTable (danh sách các hoạt động trong 1 tuần)

• Viết hàm in toàn bộ thời khóa biểu ra màn hình, phân theo ngày, sắp thứ tự tăng

dần theo thời gian bắt đầu

• Viết hàm tìm trên thời khóa biểu in ra các hoạt động bắt đầu và kết thúc trong buổi

sáng (từ 6h đến 12h)

• Viết hàm tìm trên thời khóa biểu thời gian rảnh (thời gian bắt đầu – thời gian kết

thúc) vào các buổi sáng trong tuần (từ 6h đến 12h)

13

{dhhai, dnkha}@fit.hcmus.edu.vn

• Viết chương trình chính:

- Đọc thời khóa biểu của 2 học sinh A và B từ 2 tập tin văn bản

- Tìm thời gian rảnh vào các buổi sáng của từng học sinh A và B

- Tìm thời gian rảnh vào các buổi sáng của cả A và B (cả 2 cùng rảnh)

- Gán hoạt động "Hoc nhom" vào một khoảng thời gian rảnh chung của cả A và B

vào thời khóa biểu của A và B

- Lưu thời khóa biểu mới của A và B ra 2 tập tin văn bản mới

67.MÃ HÓA VÀ GIẢI MÃ

Bạn cần viết một chương trình giải mã một chuỗi các kí tự thành một văn bản hợp lệ.

Chương trình của bạn sẽ đọc một chuỗi các kí tự đã mã hóa và in ra chuỗi kí tự thực sự

ẩn chứa bên dưới.

Cơ chế mã hóa dựa theo mã hóa Caesar: văn bản mã được tạo ra bằng cách thay thế

mỗi chữ cái trong văn bản bằng một chữ cái cách nó một đoạn cho trước. Đoạn cho trước

này được gọi là khóa của hệ mã. Chương trình của bạn sẽ luôn giả sử khóa là 7.

INPUT Dữ liệu nhập gồm nhiều dòng, kết thúc bằng EOF. Mỗi dòng chứa một chuỗi đã

mã hóa có chiều dài tối đa là 255 kí tự. Các kí tự sau khi mã hóa thuộc phần hiển thị được

của bảng mã ASCII (có mã thập phân từ 32 đến 126).

OUTPUT Chương trình cần in ra chuỗi giải mã tương ứng, mỗi chuỗi một dòng, với

khóa là 7.

14

{dhhai, dnkha}@fit.hcmus.edu.vn

INPUT MẪU

OUTPUT MẪU

Rovh'Jveun'Unole5'[oveun'[pu'KO'RO[U Khoa Co^ng Nghe^. Tho^ng Tin DH KHTN

_pu'johgv'jh.j'ih5u

Jo|.j'ih5u'th`'th/.u

Xin cha`o ca'c ba.n

Chu'c ba.n maY ma('n

68.3N+1

Các bài toán trong Khoa học máy tính thường được phân loại vào một nhóm bài toán cụ

thể, như nhóm bài toán NP, Không giải được hay Đệ quy. Trong bài toán dưới đây, bạn

sẽ khảo sát một thuật toán không thể phân nhóm được.

BÀI TOÁN

Xem mã giả sau đây:

1.nhập số nguyên ꢀ

2.in ra ꢀ

3.nếu ꢀ == 1 thì dừng

4.

5.

nếu n là số lẻ thì gán ꢀ = 3ꢀ + 1

ngược lại gán ꢀ = ꢀ/2

6.quay lại bước 2

Với ꢀ = 30, thuật toán sẽ in ra chuỗi sau

30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

15

{dhhai, dnkha}@fit.hcmus.edu.vn

Các nhà khoa học dự đoán rằng thuật toán trên sẽ dừng (khi gặp ꢀ = 1) với mọi số

nguyên ꢀ. Mặc dù thuật toán khá đơn giản, nhưng hiện vẫn chưa biết được dự đoán đó có

đúng hay không. Tuy nhiên, thuật toán đã được kiểm chứng là sẽ dừng với mọi số nguyên

ꢀ thỏa 0 < ꢀ < 1 000 000.

Với mỗi số nguyên ꢀ, ta gọi số con số được in ra bởi thuật toán là chiều dài chu kỳ của

ꢀ. Trong ví dụ trên, chiều dài chu kỳ của ꢀ = 30 là 19.

YÊU CẦU Bạn cần xác định chiều dài chu kỳ lớn nhất của các số nguyên trong khoảng

giữa ꢀ và ꢀ, với ꢀ, ꢀ cho trước.

INPUT Input bao gồm nhiều cặp các số nguyên ꢀ và ꢀ, mỗi cặp trên một dòng. Các số

nguyên nằm trong khoảng [0, 1 000 000]. Bạn cần xử lý tất cả các cặp số nguyên, và tìm

chiều dài chu kỳ lớn nhất của các số nguyên trong khoảng giữa ꢀ và ꢀ.

OUTPUT Với mỗi cặp số nguyên ꢀ và ꢀ, in ra ꢀ, ꢀ và chiều dài chu kỳ lớn nhất của các số

nguyên trong khoảng từ ꢀ đến ꢀ, mỗi số cách nhau bằng một khoảng trắng và viết trên

cùng một dòng.

INPUT MẪU

OUTPUT MẪU

1 50

1 50 112

10 20

10 20 21

305 399

305 399 144

1089 2012

2012 10012

999999 999990

1089 2012 182

2012 10012 262

999999 999990 259

16

{dhhai, dnkha}@fit.hcmus.edu.vn

69.THƯ VIỆN

Thành phố Y mới mở 2 thư viện lớn, có rất nhiều sách để cho mượn. Thành phố muốn

bạn xây dựng một hệ thống phần mềm quản lý cho mượn sách mới, vì phần mềm cũ

không còn chạy được trên hệ thống máy tính mới. Hệ thống phần mềm cần giúp người

đọc của thư viện in ra danh sách những cuốn sách có thể mượn, cho người đọc mượn và

trả sách. Chương trình cần quản lý 2 đối tượng thông tin, đó là thư viện và sách.

INPUT và OUTPUT

Dữ liệu nhập gồm nhiều dòng là một chuỗi lệnh. Mỗi lệnh là một kí tự in hoa ở đầu dòng.

Mỗi lệnh có thể có tham số, và có thể gồm nhiều dòng. Tên thư viện và tên sách là chuỗi

kí tự có chiều dài không quá 50. Có tối đa 10 thư viện, mỗi thư viện có tối đa 50 cuốn

sách. Chương trình hỗ trợ các lệnh sau:

N LibraryName

Tạo một thư viện mới có tên là LibraryName.

Nếu thành công, báo

LibraryName created

Nếu trong danh sách thư viện hiện tại đã có thư viện trùng tên,

không tạo mới và báo lỗi:

LibraryName already exists

Nếu vượt quá số thư viện có thể quản lý (10 thư viện) báo lỗi

Library list is full

L

Liệt kê danh sách tên các thư viện hiện có, mỗi thư viện một dòng,

17

{dhhai, dnkha}@fit.hcmus.edu.vn

có đánh số

Available Libraries:

1. LibraryName1

2. LibraryName2

Nếu không có thư viện nào, in ra

No libraries available

L LibraryName

Liệt kê toàn bộ danh sách sách có trong thư viện có tên

LibraryName, mỗi sách trên một dòng, có đánh số thứ tự (không

cần sắp xếp), cho biết trạng thái của sách. Có 2 trạng thái: đã cho

mượn (R), hoặc có thể mượn (A).

Books in LibraryName catalog

1. [A]BookName1

2. [R]BookName2

Nếu thư viện LibraryName không tồn tại, báo lỗi

LibraryName does not exist

Nếu thư viện không có sách nào, in ra

No books in LibraryName

A LibraryName

B Book1

Thêm sách vào thư viện có tên LibraryName. Tên của các cuốn

sách được nhập trên từng dòng trong các dòng tiếp theo, bắt đầu

bằng chữ B.

B Book2

Nếu thêm sách thành công, báo

Book1 added

Nếu thư viện LibraryName không tồn tại, bỏ qua các dòng nhập

18

{dhhai, dnkha}@fit.hcmus.edu.vn

sách tiếp theo, báo lỗi

LibraryName does not exist

Nếu có sách trùng tên sẵn trong thư viện, bỏ qua và báo

Book1 already exists, skip

Nếu vượt quá số sách thư viện có thể quản lý (50 sách) báo lỗi, và

bỏ qua các sách còn lại

LibraryName is full, skip all remaining book(s)

Sau khi thêm sách, báo kết quả, cho biết số sách đã thêm và số sách

đã bỏ qua.

5 book(s) added, 0 book(s) skipped

Mượn sách từ thư viện có tên LibraryName. Tên của các cuốn sách

R LibraryName

B Book1

được nhập trên từng dòng trong các dòng tiếp theo, bắt đầu bằng

chữ B.

B Book2

Nếu mượn sách thành công, báo

Book1 rented

Nếu thư viện LibraryName không tồn tại, bỏ qua các dòng tiếp

theo, báo lỗi

LibraryName does not exist

Nếu sách đã được mượn trước bởi người khác, bỏ qua và báo

Book1 already rented, skip

Nếu sách không tồn tại trong thư viện, bỏ qua và báo

Book1 does not exist, skip

19

{dhhai, dnkha}@fit.hcmus.edu.vn

Sau khi thực hiện, báo kết quả, cho biết số sách mượn và số sách đã

bỏ qua.

5 book(s) rented, 0 book(s) skipped

S LibraryName

B Book1

Trả sách lại cho thư viện có tên LibraryName. Tên của các cuốn

sách được nhập trên từng dòng trong các dòng tiếp theo, bắt đầu

bằng chữ B.

B Book2

Nếu trả sách thành công, báo

Book1 returned

Nếu thư viện LibraryName không tồn tại, bỏ qua các dòng tiếp

theo, báo lỗi

LibraryName does not exist

Nếu sách không tồn tại trong thư viện, bỏ qua và báo

Book1 does not exist, skip

Sau khi thực hiện, báo kết quả, cho biết số sách đã trả và số sách đã

bỏ qua.

5 book(s) returned, 0 book(s) skipped

Kết thúc chuỗi lệnh. Chương trình kết thúc xử lý.

X

INPUT MẪU

OUTPUT MẪU

L

No libraries available

N Kitty

A Kitty

Kitty created

20

{dhhai, dnkha}@fit.hcmus.edu.vn

B A Memory of Light

B Spice and Wolf

A Memory of Light added

Spice and Wolf added

2 book(s) added, 0 book(s) skipped

Available Libraries:

L

1. Kitty

A Snoopy

Snoopy does not exist

0 book(s) added, 1 book(s) skipped

B Spider Man

R Kitty

B A Memory of Light

B Spiderman

A Memory of Light rented

A Memory of Light already rented, skip

Spiderman does not exist, Skip

1 book(s) rented, 2 book(s) skipped

Books in Kitty catalog

L Kitty

1. [R]A Memory of Light

2. [A]Spice and Wolf

S Kitty

B A Memory of Light

B Spiderman

A Memory of Light returned

Spiderman does not exist, skip

1 book(s) returned, 1 book(s) skipped

X

HƯỚNG DẪN

Bạn được cung cấp sẵn các tập tin mã nguồn khung để viết chương trình này:

thuvien.cpp

data.h

lib.cpp

lib.h

inout.cpp

inout.h

21

Bài tập tổng hợp môn Nhập môn lập trình - Đặng Hoàng Hải