Giải bài tập Cấu trúc dữ liệu và giải thuật(C++)(Phần 2)

Phần 2. SINH KẾ TIẾP – QUAY LUI – NHÁNH CẬN

BÀI 1. XÂU NHỊ PHÂN CÓ K BIT 1

Hãy in ra tất cả các xâu nhị phân độ dài N, có K bit 1 theo thứ tự từ điển tăng dần.

Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm 2 số nguyên N, K (1 ≤ K ≤ N

≤ 16).

Output: Với mỗi test, in ra đáp án tìm được, mỗi xâu in ra trên một dòng.

👁️Source code: Xem

BÀI 2. XÂU AB

Một xâu kí tự S = (s1, s2, .., sn) được gọi là xâu AB độ dài n nếu với mọi siS thì si hoặc là kí tự

A hoặc si là kí tự B . Ví dụ xâu S = “ABABABAB” là một xâu AB độ dài 8. Cho số tự nhiên N

và số tự nhiên K (1<=K<N<=15 được nhập từ bàn phím), hãy viết chương trình liệt kê tất cả các

xâu AB có độ dài N chứa duy nhất một dãy K kí tự A liên tiếp.

Dữ liệu vào chỉ có một dòng ghi hai số N và K.

Kết quả ghi ra màn hình theo khuôn dạng:

- Dòng đầu tiên ghi lại số các xâu AB thỏa mãn yêu cầu bài toán;

- Những dòng kế tiếp, mỗi dòng ghi lại một xâu AB thỏa mãn. Các xâu được ghi ra theo

thứ tự từ điển.

👁️Source code: Xem

BÀI 3. TỔ HỢP TIẾP THEO

Cho số nguyên dương (1<N<40) và số nguyên dương K<N. Với 1 tổ hợp chập K phần tử của N,

hãy cho biết tổ hợp tiếp theo sẽ có bao nhiêu phần tử mới. Nếu tổ hợp đã cho là cuối cùng thì kết

quả là K.

Dữ liệu vào: Dòng đầu ghi số bộ test, không quá 20. Mỗi bộ test viết trên hai dòng

- Dòng 1: hai số nguyên dương N và K (K<N)

- Dòng 2 ghi K số của tổ hợp ban đầu. Theo đúng thứ tự tăng dần, không có số nào trùng

nhau.

Kết quả: Với mỗi bộ dữ liệu in ra số lượng phần tử mới.

👁️Source code: Xem

BÀI 4. HOÁN VỊ KẾ TIẾP

Hãy viết chương trình nhận vào một chuỗi (có thể khá dài) các ký tự số và đưa ra màn hình hoán

vị kế tiếp của các ký tự số đó (với ý nghĩa là hoán vị có giá trị lớn hơn tiếp theo nếu ta coi chuỗi

đó là một giá trị số nguyên). Chú ý: Các ký tự số trong dãy có thể trùng nhau.

Ví dụ:

123 -> 132

279134399742 -> 279134423799

Cũng có trường hợp sẽ không thể có hoán vị kế tiếp. Ví dụ như khi đầu vào là chuỗi 987.

Dữ liệu vào: Dòng đầu tiên ghi số nguyên t là số bộ test (1 ≤ t ≤ 1000). Mỗi bộ test có một

dòng, đầu tiên là số thứ tự bộ test, một dấu cách, sau đó là chuỗi các ký tự số, tối đa 80 phần tử.

Kết quả: Với mỗi bộ test hãy đưa ra một dòng gồm thứ tự bộ test, một dấu cách, tiếp theo đó là

hoán vị kế tiếp hoặc chuỗi “BIGGEST” nếu không có hoán vị kế tiếp.

👁️Source code: Xem

BÀI 5. CHỌN SỐ TỪ MA TRẬN VUÔNG CẤP N

Cho ma trận vuông C[i][j] cấp N (1<= i, j <= N<=10) gồm N^2 số tự nhiên và số tự nhiên K (các số trong ma trận không nhất thiết phải khác nhau và đều không quá 100, K không quá 104). Hãy viết

chương trình lấy mỗi hàng, mỗi cột duy nhất một phần tử sao cho tổng các phần tử này đúng bằng K.

Dữ liệu vào: Dòng 1 ghi hai số N và K. N dòng tiếp theo ghi ma trận C.

Kết quả: dòng đầu ghi số cách tìm được. Mỗi dòng tiếp theo ghi một cách theo vị trí của số đó

trong lần lượt từng hàng của ma trận. Xem ví dụ để hiểu rõ hơn.

👁️Source code: Xem

BÀI 6. SẮP XẾP QUÂN HẬU 1

Cho một bàn cờ vua có kích thước n * n, ta biết ràng quân hậu có thể di chuyển theo chiều ngang, dọc, chéo. Vấn đề đặt ra rằng, có n quân hậu, bạn cần đếm số cách đặt n quân hậu này lên bàn cờ sao cho với 2 quân hậu bất kì, chúng không “ăn” nhau.

Input: Một số nguyên dương n duy nhất (không quá 10)

Output: Số cách đặt quân hậu.

Ví dụ:

Input              Output

4                     2

👁️Source code: Xem

BÀI 7. SẮP XẾP QUÂN HẬU 2

Cho một bàn cờ 8 x 8, mỗi ô có một giá trị A[i][j] nhất định (0 ≤ A[i][j] ≤ 100), tương ứng với

điểm số đạt được nếu như bạn đặt một quân cờ vào đó.

Nhiệm vụ của bạn là đặt 8 quân hậu lên bàn cờ, sao cho không có 2 quân nào ăn nhau, và số

điểm đạt được là lớn nhất.

Input: Dòng đầu tiên là số lượng bộ test T (T ≤ 20).

Mỗi test gồm 8 dòng, mỗi dòng 8 số nguyên mô tả bàn cờ.

Output: Với mỗi test, in ra đáp án trên một dòng.

Ví dụ:

Input                                                Output

1                                                       260

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48

48 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64

👁️Source code: Xem

BÀI 8. SỐ NHỎ NHẤT CÓ N ƯỚC SỐ

Cho số nguyên dương N. Nhiệm vụ của bạn là tìm số K nhỏ nhất, sao cho K có đúng N ước.

Input đảm bảo rằng đáp án không vượt quá 10^18

Input:

Dòng đầu tiên là số lượng bộ test T (T ≤ 10).

Mỗi test gồm 1 số nguyên N ( 1 ≤ N ≤ 1000).

Output: Với mỗi test, in ra đáp án trên một dòng.

Ví dụ:

Input                                            Output

2                                                   6

4                                                   12

6

👁️Source code: Xem

BÀI 9. TÌM BỘI SỐ

Cho số nguyên N. Nhiệm vụ của bạn cần tìm số nguyên X nhỏ nhất là bội của N, và X chỉ chứa

hai chữ số 0 và 9.

Input:Dòng đầu tiên là số lượng bộ test T (T ≤ 10000).Mỗi bộ test chứa số nguyên N trên một dòng (1 ≤ N ≤ 500).

Output: Với mỗi test in ra đáp án tìm được trên một dòng.

👁️Source code: Xem

BÀI 10. MÁY ATM

Một máy ATM hiện có n (n ≤ 30) tờ tiền có giá trị t[1], t[2], ..., t[n]. Hãy tìm cách trả ít tờ nhất

với số tiền đúng bằng S (các tờ tiền có giá trị bất kỳ và có thể bằng nhau).

Input: Dòng đầu tiên gồm 2 số nguyên n và S (S ≤ 109). 

           Dòng thứ hai chứa n số nguyên t[1], t[2], ..., t[n] (t[i] ≤ 109)

Output: Số tờ tiền ít nhất phải trả.

Ví dụ

Input                                    Output

3 5                                       1

1 4 5

👁️Source code: Xem

BÀI 11. XEM PHIM

Nông dân John đang đưa các con bò của anh ta đi xem phim. Xe tải của anh ta thì có sức chứa

tối đa là C (100 ≤ C ≤ 7000) kg, anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối

lượng của những con bò này là lớn nhất, đồng thời xe tải của anh ta vẫn còn có thể chở được.

Cho N (1 ≤ N ≤ 25) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất

mà John có thể đưa đi xem phim là bao nhiêu.

Dữ liệu vào:

Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N

Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên: W_i

Kết quả

Một số nguyên là tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim.

👁️Source code: Xem

BÀI 12. NGƯỜI DU LỊCH

Cho n thành phố đánh số từ 1 đến n và các tuyến đường giao thông hai chiều giữa chúng, mạng

lưới giao thông này được cho bởi mảng C[1...n, 1...n] ở đây C[i][j] = C[j][i] là chi phí đi đoạn

đường trực tiếp từ thành phố i đến thành phố j.

Một người du lịch xuất phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành

phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra chi phí ít nhất mà người đó phải bỏ

ra.

Dữ liệu vào: Dòng đầu tiên là số nguyên n – số thành phố (n ≤ 15); n dòng sau, mỗi dòng chứa n

số nguyên thể hiện cho mảng 2 chiều C.

Kết quả: Chi phí mà người đó phải bỏ ra.

👁️Source code: Xem

BÀI 13. KÝ TỰ LẶP TRONG HAI XÂU LIÊN TIẾP

Cho một dãy các xâu ký tự chỉ bao gồm các chữ cái in hoa từ A đến Z, trong đó các ký tự trong

mỗi xâu đều đã được sắp xếp theo thứ tự từ điển và mỗi chữ cái chỉ xuất hiện nhiều nhất một lần

(tức là độ dài xâu tối đa là 26). Nếu một ký tự xuất hiện trong hai xâu liên tiếp thì được coi là

một lần lặp. Hãy tìm cách sắp xếp lại thứ tự các xâu sao cho số lần lặp là nhỏ nhất có thể. Ví dụ

dưới đây là cùng một dãy xâu nhưng với cách sắp xếp lại thì số lần lặp chỉ còn 2.

ABC

ABEF

DEF                         => Số lần lặp là 6

ABCDE

FGH

ABEF

DEF

ABC                        => Số lần lặp là 2.

FGH

ABCDE

Input: Dòng đầu tiên ghi số N (2≤N≤10) là số xâu ký tự. N dòng tiếp theo, mỗi dòng ghi một

xâu.

Output: In ra trên một dòng số lần lặp nhỏ nhất có thể.

👁️Source code: Xem

Series Bài tập Cấu trúc dữ liệu & giải thuật: Xem thêm.

Ngoài ra bạn đọc có thể tham khảo các bài viết về thuật toán và lập trình tại VietAlgo's Blog.