Viết chương trình sử dụng kĩ thuật duyệt quay lui để kiểm tra xem một biểu thức có hợp lệ về sử dụng các dấu ngoặc đơn hay không.

Trong Nhiệm vụ 2, động tác "quay lui" nằm ở đâu? Việc hoán vị được thực hiện như thế nào?

Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi là cần in ra kết quả là các xâu kí tự chỉ bao gồm các kí tự “A”, “T”, “G”, “X”.

Theo em kĩ thuật duyệt quay lui thường được áp dụng cho những loại bài toán nào? Em có thể nêu ra một vài ví dụ không?

Viết chương trình sinh xâu nhị phân thực sự có độ dài n, tức là kết quả in ra phải là các xâu kí tự chứ không phải là danh sách (list) như trong các chương trình trên.

Viết chương trình sinh tất cả các số hex (hệ đếm 16) có 3 chỉ số.

Viết chương trình sinh tất cả các xâu (hoặc dãy) bao gồm n kí tự dạng “R”, “G” và "B".

Sửa các chương trình trên bổ sung thêm chức năng: sau khi in ra tất cả các xâu nhị phân thi thông báo tổng số nghiệm.

Giải thích ý nghĩa của lệnh A.pop() tại dòng 8 của chương trình 2. Vì sao lệnh này không có trong chương trình 1?

Trong chương trình 1, động tác “quay lui” nằm ở đâu?

Cùng thực hiện, trao đổi, thảo luận thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui.

Có cách nào đếm được tất cả các nghiệm từ thuật toán trên được không? Nếu có thì làm cách nào?

Trạng thái "quay lui" của thuật toán trên nằm ở đâu?

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui.

Nếu yêu cầu bổ sung thêm 1 lệnh “Nếu thấy <lối ra> thì thông báo và dừng chương trình” thì lệnh này sẽ đặt ở đâu trong chương trình trên?

Lệnh gọi hàm chính của chương trình trên là gì?

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không?

Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.

Viết chương trình để tìm ra hai bạn có nhiều bạn chung nhất, hai bạn có nhiều nhóm chung nhất.

Trong bài toán đề xuất danh sách kết bạn, không tìm thấy đối tượng phù hợp cho hai bạn Hà, Hùng. Hãy viết chương trình tìm nhóm gợi ý cho một bạn bất kì (được nhập vào từ bàn phím). Nhóm được gợi ý là nhóm các bạn này chưa tham gia và đang có nhiều thành viên nhất.

Viết chương trình cho phép người dùng nhập một số nguyên dương N từ bàn phím, sau đó in ra toàn bộ các số hoàn hảo nhỏ hơn N. Số hoàn hảo là số có giá trị bằng tổng số các ước số của nó, không kể chính nó.

Với bài toán trong Hoạt động 1, em hãy viết thêm các lệnh để tìm ra 3 học sinh có tổng điểm lớn nhất.

Viết chương trình cho phép người dùng nhập một số nguyên dương N từ bàn phím rồi in ra số có nhiều ước số nhất trong các số nhỏ hơn N.

Theo em, thuật toán tìm kiếm nhị phân có sử dụng duyệt vét cạn hay không?

Một mảng hai chiều kích thước m×n thi duyệt vét cạn sẽ phải duyệt qua tổng số bao nhiêu phần tử?

Tìm kiếm tuần tự trên một dãy n phần tử có phải là duyệt vét cạn hay không?

Với các bài toán sau, em hãy thảo luận với bạn để tìm kĩ thuật tìm kiếm đã học (tìm kiếm trên các mảng 1 hoặc 2 chiều) để giải.

1. Cho trước số tự nhiên n. Tìm và in ra tất cả các xâu nhị phân có độ dài n.

2. Viết chương trình tìm và liệt kê tất cả các hoán vị của tập hợp [1, 2, ..., n] với n là số tự nhiên cho trước.

Phân tích và viết chương trình để thực hiện các yêu cầu sau:

a) Tìm học sinh có điểm Toán bằng 8.9.

b) Tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5.

c) Tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhất.

So sánh số vòng lặp cần thực hiện để thực hiện các yêu cầu a, b, c trong ví dụ trên.

Cho A, B, C, D lần lượt là các danh sách tên học sinh, điểm thi môn Toán, điểm thi môn Vật lí và điểm thi môn Hoá học. Danh sách điểm Toán được sắp xếp theo thứ tự tăng dần và các danh sách tên học sinh và điểm các môn còn lại được sắp xếp theo tương ứng.

A = [“Nam”, “Sơn”, “Hương”, “Huyền”, “Hà”, “Hùng”

B = [8.3, 8.4, 8.7, 8.9, 9.1.96]

C= [ 8.3, 7.8, 8.9, 9.5, 9.3, 9.0]

D= [7.9, 9.0, 8.9, 8.2, 9.5, 9.1]

Hãy thảo luận về kĩ thuật tìm kiếm được thực hiện với mỗi yêu cầu sau:

a) Tìm một học sinh có điểm Toán lớn hơn điểm Vật lí.

b) Tìm tất cả các học sinh có điểm Vật lí lớn hơn điểm Hoá học.

c) Tìm tất cả các học sinh có cả 3 điểm đều lớn hơn hoặc bằng 9.

Để xác định một giá trị a có xuất hiện trong một dãy A cho trước hay không ta có thể áp dụng phương pháp tìm kiếm tuần tự: lần lượt so sánh a với từng phần tử trong A. Theo em, liệu có cách nào đề giải bài toán này trong trường hợp A là một dãy bất kì hay không?

Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa là tổng của một dãy con liên tục dạng$S\left(i,j\right)=A\left[i\right]+A\left[i+1\right]+\mathrm{...}+A\left[j\right]$ . Bài toán yêu cầu tìm và chỉ ra một tổng con và dãy con tương ứng có giá trị lớn nhất. Yêu cầu sử dụng kĩ thuật chia để trị.

Cho dãy số A, cần tìm phần tử mốt (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện nhiều nhất trong A. Nếu tồn tại nhiều thì chỉ yêu cầu tìm ra một phần tử mốt. Yêu cầu sử dụng kĩ thuật chia để trị.

Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sung: Cần đưa ra kết quả là số lượng các cặp nghịch đảo và toàn bộ dãy các cặp chỉ số nghịch đảo đã tìm thấy. Ví dụ với A = [4, 5, 2, 10, 4] thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (1, 4)].

Khi làm việc với các danh sách mảng, nhiều trường hợp đòi hỏi cần kiềm ra các danh sách mảng đã được sắp thứ tự để áp dụng thuật toán phù hợp. Cho một dãy số, theo em làm thế nào để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần?

Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước, cụ thể như sau.

- Thủ tục trộn sẽ có dạng sau: merge(A,left,mid,right). Thủ tục này sẽ trộn hai phân đoạn của dãy A là A[left], ...., A[mid] và A[mid + 1]..... A[right]. Hai phân đoạn này phải được sắp xếp đúng trước đó.

- Thuật toán chính có dạng mergeSoft(A, left, right) như sau:

- Lệnh gọi hàm đệ quy là: