Giải sách bài tập Tin học 11 định hướng Khoa học máy tính Cánh diều bài 8: Lập trình một số thuật toán sắp xếp

Fcs31. Em hãy xác định số lượng nghịch thế tối đa của một dãy A gồm n số nguyên phân biệt.

Hướng dẫn trả lời:

Số lượng nghịch thế đạt giá trị lớn nhất khi dãy A đã được sắp sẵn theo thứ tự giảm dần. Khi đó, số lượng nghịch thế của A là $C^{2}_{2}=\frac{n(n-2)}{2}$

Fcs32. Phân loại hoá chất

Trong phòng thí nghiệm Hóa học, có n lọ mất nhãn. Lần này, em không cần dùng các chất thử để phân biệt, vì tình huống hiện tại khá đặc biệt: Nhận thấy tất cả dung dịch trong phòng đều là các hợp chất quen thuộc nằm trong chương trình Hoá học 11 và mỗi chất này đều có khối lượng riêng khác nhau. Hơn nữa, trùng hợp là thể tích của các lọ này đều như nhau (số mol bằng nhau), theo thông tin từ giáo viên. Vì thế, chỉ cần biết khối lượng của các lọ là có thể biết được lọ nào chứa chất nào.

Bằng một chiếc cân chính xác, em đã lấy ra được khối lượng của n lọ đó, là dãy số a₀,a₁,a₂,…,a_n-1

Yêu cầu: Em hãy lập trình để kiểm tra trong n lọ này chứa bao nhiêu chất khác nhau.

Dữ liệu: Nhập từ thiết bị vào chuẩn: 

• Dòng đầu tiên chứa một số nguyên dương n. 

• Dòng thứ hai chứa n số nguyên theo thứ tự a₀,a₁,a₂,…,a_n-1

Kết quả: Hiển thị ở thiết bị ra chuẩn số nguyên là số chất khác nhau:

Ví dụ:

Hướng dẫn trả lời:

Fcs33. Số lần đổi chỗ

Cho dãy A gồm n số nguyên phân biệt A₀,A₁,A₂,…,A_n-1.

Em có thể dùng thao tác sau: Chọn hai vị trí kề nhau i và i + 1 bất kì 0≤i<n-1, nếu A_i>A_i+1 thì đổi chỗ A_i với A_i+1 cho nhau

Em hãy thao tác trên mảng A, sao cho sau khi thực hiện tuần tự các thao tác, mảng A được sắp xếp tăng dần.

Yêu cầu: Hãy in ra số lần đổi giá trị và vị trí i và j của lần đổi chỗ đó.

Dữ liệu: Nhập từ thiết bị vào chuẩn: 

• Dòng đầu tiên chứa một số nguyên dương n

• Dòng thứ hai chứa n số nguyên theo thứ tự A₀,A₁,A₂,…,A_n-1.

Kết quả: Hiển thị ở thiết bị ra chuẩn:

• Dòng đầu tiên chứa số nguyên dương K là số thao tác bạn làm.

• K dòng sau, dòng thứ i in ra hai số u_i,v_i (0≤u_i<v_i<n) cho biết bạn sẽ đổi giá trị của hai vị trí u_i, v_i cho nhau.

Ví dụ:

Hướng dẫn trả lời:

Fcs34. Sắp xếp tên sách tiếng Anh

Một thư viện vừa nhập về một kho sách mới về ngoại ngữ gồm n quyền, nhưng các quyển sách được sắp xếp rất lộn xộn. Em hãy giúp thủ thư sắp xếp lại những quyển sách này theo thứ tự từ điển, để việc xếp lên giá sách được thuận tiện hơn. Danh sách các sách được lưu trong tệp danhsach.txt.

Gợi ý: Một xâu A độ dài lA được gọi là đứng trước xâu B độ dài lB, theo thứ tự từ điển, nếu sau khi loại bỏ toàn bộ khoảng trắng, tồn tại vị trí i đầu tiên sao cho khi so sánh thứ tự trong bảng chữ cái, A_iB_i và A_i đứng trước B_i, hoặc l_Al_B và A_i=B_i với mọi i≤l_A

Dữ liệu: Nhập từ tệp danhsach.txt:

• Dòng đầu tiên chứa số nguyên n

• n dòng sau, mỗi dòng là một xâu biểu thị tên của một quyển sách.

Dữ liệu đảm bảo tên chỉ gồm các chữ cái Latinh in hoa hoặc in thường cùng với dấu cách, giữa hai từ liên tiếp nhau chỉ chứa đúng một dấu cách và không có hai quyển sách nào trùng tên nếu không tính in hoa hoặc in thường.

Kết quả: Hiển thị ở thiết bị ra chuẩn: 

• n dòng, dòng thứ i in ra quyển sách thứ i theo thứ tự từ điển.

Ví dụ:

Hướng dẫn trả lời:

Fcs35. Sắp xếp tiếng Việt

Có một tập tiếng Việt chứa n từ (cụm từ) xếp lộn xộn. Em hãy viết chương trình sắp xếp lại n từ (cụm từ) đó theo thứ tự từ điển tiếng Việt để dễ tra cứu. 

Dữ liệu: Nhập từ tập danhsach.txt

• Dòng đầu tiên chứa số nguyên dương n

• n dòng sau, mỗi dòng là một xâu biểu thị từ hoặc cụm từ tiếng Việt

Kết quả: Đưa ra tệp Tudien.out:

• Gồm n dòng, dòng thứ i in ra từ hoặc cụm từ thứ i theo thứ tự từ điển

Ví dụ:

Hướng dẫn trả lời:

Fcs36. Phân bố phòng thi

Một trường học có n lớp, mỗi lớp có x bạn học sinh. Giả sử tên khai sinh của các bạn chỉ gồm hai tiếng: họ (một tiếng) và tên (một tiếng).

Sắp diễn ra kiểm tra cuối kì II, nhà trường yêu cầu phòng Công nghệ thông tin tạo danh sách phòng thi. Đầu tiên, nhà trường sẽ sắp xếp danh sách phần tên trong họ tên các bạn theo thứ tự từ điển, nếu trùng tên sẽ sắp xếp theo họ. Sau đó, các bạn sẽ lần lượt được phân vào phòng thi theo thứ tự này, mỗi phòng thi có đúng m bạn, riêng phòng cuối có thể ít hơn m bạn. 

Ví dụ, phòng thi có bốn bạn. Có hai lớp, lớp 11A có ba bạn là: “Đỗ Nhỏ”, “Lê Hiếu” và “Lê Đức". Lớp 11B có ba bạn là: “Đặng Hiếu”, “Lê Quý" và “Lê Hân”. Khi đó, danh sách các bạn trong hai lớp này theo thứ tự sắp xếp là: [Lê Đức, Lê Hân, Đặng Hiếu, Lê Hiếu, Đỗ Nhỏ, Lê Quý]. Ta có thể phân thành hai phòng và xếp bốn bạn đầu danh sách đã sắp xếp vào phòng 1, hai bạn còn lại vào phòng 2

Em được cho danh sách học sinh của mỗi lớp. Em hãy tạo danh sách phòng thi.

Dữ liệu: Nhập từ tệp danhsach.txt

• Dòng đầu tiên gồm hai số nguyên dương n, m là số lượng lớp trong trường và số học sinh trong phòng thi 

• n cụm dòng tiếp theo, mỗi cụm dòng thứ i có dạng như sau:

• Dòng đầu tiên chứa số x là số lượng học sinh trong lớp thứ i.

• x dòng tiếp theo, mỗi dòng gồm hai xâu cách nhau một khoảng trắng, mỗi xấu không chứa khoảng trắng và chỉ chứa ký tự trong bảng chữ cái tiếng Việt. Hai xâu này lần lượt là họ và tên của một bạn học sinh trong lớp.

Kết quả: Đưa ra tên phongthi.txt: 

• Dòng đầu tiên in ra c là số lượng phòng thi.

• c cụm dòng tiếp theo tương ứng với c phòng thi, mỗi phòng thi in ra những dòng sau:

• Dòng đầu tiên chứa số nguyên k là số lượng thí sinh trong phòng.

• k dòng theo thứ tự từ điển, mỗi dòng chứa họ và tên của các bạn học sinh trong phòng thi

• Cần đảm bảo thứ tự xuất hiện của các dòng họ và tên phải theo thứ tự từ điển.

Ví dụ: 

Hướng dẫn trả lời: