Câu 1:DSLK đơn,các phép toán chèn thêm phần tử mới,xóa 1 pt sau 1 pt cho trước:nêu các thao tác cần thực hiện,cho VD.

Danh sách liên kết đơn, gọi tắt là danh sách liên kết (DSLK) được tạo nên từ các thành phần được liên kết với nhau bởi các con trỏ. Mỗi thành phần trong DSLK chứa một dữ liệu và một con trỏ trỏ tới thành phần tiếp theo. Chúng ta sẽ mô tả mỗi thành phần của DSLK như một hộp gồm hai ngăn: một ngăn chứa dữ liệu data và một ngăn chứa con trỏ next.

data Next

cấu trúc trong C + + :

struct Node

{

Item data ;

Node* next ;

} ;

a) Chèn một phần tử vào danh sách nối đơn

- Tạo ra phần tử mới (New Node) cần chèn

- Tìm phần tử Q là phần tử đứng trước phần tử P(trường NEXT trỏ tới phần tử P)

- Chỉnh lại các trường NEXT của các phần tử có liên quan: phần tử NewNode là phần tử kế tiếp của phần tử Q và đến lượt P lại là phần tử kế tiếp của NewNode.

- Trường hợp phần tử P là phần tử đầu thì NewNode sẽ trở thành phần tử đầu tiên của danh sách và có tên mới là Head.

b) Xóa một phần tử của danh sách nối đơn

- Tìm phần tử q đứng trước liền kề với phần tử p (phần tử q có trường NEXT trỏ tới phần tử p).

- Chỉnh lại trường NEXT của các phần tử liên quan: NEXT của q trỏ tới phần tử liền kề sau phần tử p.

- Giải phóng bộ nhớ nơi lưu trữ phần tử p.

- Trường hợp phần p là phần tử đầu (p = head) thì phần tử liền kề sau p được đặt lại tên là Head.

Thuật toán:

Câu 2: Thuật toán tìm kiếm nhị phân:bài toán,ý tưởng,thủ tục,đánh giá thuật toán,cho ví dụ mô phỏng.

-Bài toán:

Input: Dãy gồm N số nguyên k1, k2,..., kN đôi một khác nhau và là dãy tăng; số nguyên x.

Output: Chỉ số i mà ki = x hoặc thông báo không có số hạng nào của dãy có giá trị trùng với x.

-Ý tưởng: Vì dãy đã sắp xếp, ta thu hẹp phạm vi tìm kiếm Chọn số hạng "giữa dãy" để so sánh với k, Giua=[ (N+1)/2].

- Nếu k[Giua] = x thì Giua là chỉ số cần tìm.

- Nếu kGiua > k thì việc tìm kiếm tiếp theo chỉ xét trên dãy k1, ka2,..., kGiua-1

- Nếu kGiua < k thì thực hiện tìm kiếm trên dãy kGiua+1, kGiua+2,..., kN.

Lặp đi lặp lại cho đến khi tìm thấy x trong dãy hoặc khẳng định dãy không chứa giá trị bằng x.

-Thủ tục :

Bước 1. Nhập N, các giá trị k1, k2,..., kN và giá trị khóa x.

Bước 2. Dau Ü 1, Cuoi Ü N.

Bước 3. Giua Ü .

Bước 4. Nếu kGiua = x thì thông báo chỉ số Giua, rồi kết thúc

Bước 5. Nếu kGiua > x thì đặt Cuoi = Giua - 1 rồi chuyển đến bước 7.

Bước 6. Dau Ü Giua + 1

Bước 7. Nếu Dau > Cuoi thì thông báo dãy không có số hạng có giá trị trùng với x, rồi kết thúc.

Bước 8. Quay lại bước 3.

-Đánh giá:

+Trường hợp tốt nhất, độ phức tạp tính toán là O(1), trong trường hợp xấu và trung bình là O(lgN) ,

+Tuy nhiên với dãy chưa được sắp xếp thì cần có chi phí cho việc sắp xếp.

-Ví dụ:

Câu 3:Với những bài toán có tc gì có thể ứng dụng chiến lược ăn tham để thiết kế thuậttoán giải nó?Các việc chính nào cần làm khi thiết kế thuật toán?Cho Ví dụ

-Tính chất bài toán:

+Giải các bài toán tối ưu theo nghĩa tốt nhất có thể được

+ kích thước dữ liệu quá lớn.

Xây dựng cách chọn theo kiễu ăn tham.

Xây dựng cấu trúc tối ưu

-VD: Thuật toán tham ăn cho bài toán đường đi ngắn nhất

Giả sử đồ thị mà ta xét là đồ thị định hướng n đỉnh được đánh số 0,1,2,...,n-1, và là đồ thị đầy đủ, tức là với mọi 0 ≤ i , j ≤ n-1 đều có cung đi từ i đến j với độ dài là số thực không âm d(i,j). Giả sử đỉnh xuất phát là đỉnh 0, và đường đi ngắn nhất mà ta cần tìm là (0, a1, a1,... an-1, 0) trong đó ak {1,2,...,n-1}. Để nhận được nghiệm tối ưu trên, tại mỗi bước k (k = 1,..., n-1) chúng ta cần chọn một đỉnh ak để đi tới trong số các đỉnh chưa thăm (tức là ak  ai , i = 1,..., k-1). Với mong muốn đường đi nhận được là ngắn nhất, ta đưa ra tiêu chuẩn chọn đỉnh ak ở mỗi bước là đỉnh gần nhất trong số các đỉnh chưa thăm.

Ví dụ. Xét đồ thị định hướng trong hình 16.3

Hình 16.3. Một đồ thị định hướng

Giả sử ta cần tìm tua ngắn nhất xuất phát từ A. Vì d(A,B) = 7, d(A,C) = 3 và d(A,D) = 1, nên ta chọn đỉnh D để đi tới, ta có đường đi (A, D). Từ D, các đỉnh chưa thăm là B và C, ta chọn C để đi tới vì C gần D hơn là B. Ta thu được đường đi (A, D, C). Từ C ta chỉ có một khả năng là đi tới B. Do đó ta nhận được tua (A, D, C, B, A). Độ dài của nó là 1 + 2 + 9 + 5 = 17. Đây không phải là đường đi ngắn nhất, vì đường đi ngắn nhất là (A, C, D, B, A) có độ dài 3 + 2 + 6 + 5 = 16.

Câu 4: Hang doi: dinh nghia, cac phep toan khoi tao, them vao, lay ra, kiem tra rong, tran. To chuc hang doi vong tron ntn va co loi j?

-dinh nghia: Hàng đợi là một danh sách các đối tượng dữ liệu, một trong hai đầu danh sách được xem là đầu hàng, còn đầu kia là đuôi hàng. Chẳng hạn, hàng đợi có thể là danh sách các ký tự (a, b, c, d), trong đó a đứng ở đầu hàng, còn d đứng ở đuôi hàng.

- cacphép toán: Theo nguyên tắc vào trước-ra trước-FIFO ( First In First Out).

+ Mô tả Queueu bằng mảng

-Hai chỉ số Front, Rear. Khi khởi tạo đặt Front là 1 còn Rear là 0.

(i) Push: tăng Rear lên 1 và đưa giá trị của phần tử cần bổ sung vào .

(ii) Pop:lấy giá trị phần tử có chỉ số là Front và sau đó tăng Front lên 1.

(iii) Khi tăng chỉ số Rear lên hết khoảng cho phép thì Queue đã đầy (OverQueue).

(iv) Khi Front > Rear thì Queue là rỗng ( EmptyQueue) .

+Mô tả Queueu bằng danh sách vòng

Một danh sách vòng tròn- các phần tử nằm trên cung tròn từ vị trí Front đến Rear là thuộc Queue.

- Khi thêm một phần tử vào Queue: dịch chuyển chỉ số Rear theo vòng tròn 1 ví trí rồi đặt giá trị cần thêm vào đó.

- Khi lấy một phần tử ra khỏi Queue: lấy phần tử có chỉ số là Front rồi dịch chuyển chỉ số Front theo vòng tròn 1 vị trí.

Cau5. Thuat toan sap xep chen: bai toan, y tuong, thu tuc, danh gia thuat toan, cho VD mo fong.

-Bài toán: Cho dãy K gồm n giá trị khóa k1, k2,..., kn. Giữa hai khóa có quan hệ "<=". Cần xếp lại dãy khóa sao cho:

k'1 <= k'2<=... <= k'n. trong đó k'i thuộc tập { k1, k2,..., kn.}

-Ý tưởng: Với k1, coi là đã sắp xếp. Bổ sung k2, nếu k2<k1 thì chèn k2 vào trước k1. Thêm k3, dãy k1, k2 là đã sắp xếp, cần tìm cách chèn nó cho dãy 03 phần tử sẽ là dãy được sắp. Tổng quát, ta cần sắp xếp dãy k1, k2,..., ki bằng cách chèn ki vào dãy đã sắp k1, k2,..., ki-1 để dãy sau khi chèn xong là dãy đã được sắp xếp.

- So sánh ki lần lượt với các khóa của dãy đã sắp từ ki-1 cho đến khi tìm được kj > ki thì dừng lại

- Chèn ki vào ví trí rỗng của dãy.

-Thủ tục:

void InsertionSort (Item A[], int n)

{

(1) for ( int i = 1 ; i < n ; i++)

(2) for ( int k = i ; k > 0 ; k--)

(3) if (A[k].key < A[k-1].key)

swap(A[k],A[k-1]);

else break;

}

- Đánh giá:

+>Tốt nhất: O(n).

+>Dãy có thứ tự ngược: tổng số phép so sánh sẽ là: (k-1) +(k-2) +.........+2+1= k* (k-1.

+>Chuyển dịch dãy con từ vị trí thứ j đến (i-1) sang phải một ví trí.

)/2; O(k2)

Trung bình, có thể coi ở lượt thứ i thuật toán cần trung bình i/2 phép so sánh nên tổng là:(1/2) +(2/2)+(3/2) +......+(k/2) = ( k+1) * n/4

O(k2).

-Ví dụ: Giả sử ta ta có mảng số nguyên A[0..5] và đoạn đầu A[0..2] đã được sắp

0 1 2 3 4 5

1 4 5 2 9 7

Lúc này i = 3 và k = 3 vì A[3] < A[2], trao đổi A[3] và A[2], ta có

0 1 2 3 4 5

1 4 2 5 9 7

Đến đây k=2, và A[2] < A[1], lại trao đổi A[2] và A[1], ta có

0 1 2 3 4 5

1 2 4 5 9 7

Lúc này k = 1 và A[1] >= A[0] nên ta dừng lại và có đoạn đầu A[0..3] đã được sắp.

Câu 6: Voi nhung bai toan co tinh chat gi thi co the ung dung chien luoc chia de tri va de quy de thiet ke thuat giai toan giai no? Cac viec chinh nao can thuc hien khi thiet ke thuat toan chia de tri? Minh hoa bang 1 VD tuy chon

-Tính chất bài toán:đệ quy

-Ý tưởng: Chia: Chia bài toán xuất phát, phức tạp, có kích thước Input lớn thành các bài toán con tương tự nhưng có kích thước Input nhỏ hơn.

Tri:̣ Giải các bài toán con bằng đệ quy.

Kết hợp nghiệm (combaine)

Tức là: Chia vấn đề cần giải thành một số vấn đề con cùng dạng với vấn đề đã cho, chỉ khác là cỡ của chúng nhỏ hơn. Mỗi vấn đề con được giải quyết độc lập. Sau đó, ta kết hợp nghiệm của các vấn đề con để nhận được nghiệm của vấn đề đã cho. Nếu vấn đề con là đủ nhỏ có thể dễ dàng tính được nghiệm, thì ta giải quyết nó, nếu không vấn đề con được giải quyết bằng cách áp dụng đệ quy thủ tục trên (tức là lại tiếp tục chia nó thành các vấn đề con nhỏ hơn,...).

DivideConquer (A,x)

// tìm nghiệm x của bài toán A.



if (A đủ nhỏ)

Solve (A);

else 

Chia bài toán A thành các bài toán con

A1, A2,..., Am;

for (i = 1; i <= m ; i ++)

DivideConquer (Ai , xi);

Kết hợp các nghiệm xi của các bài toán con Ai (i=1, ..., m) để nhận được nghiệm x của bài toán A;



}

-Ví dụ : Tìm max và min

Cho mảng A cỡ n, chúng ta cần tìm giá trị lớn nhât (max) và nhỏ nhất (min) của mảng này. Bài toán đơn giản này có thể giải quyết bằng các thuật toán khác nhau.

Một thuật toán rất tự nhiên và đơn giản là như nhau. Đầu tiên ta lấy max, min là giá trị đầu tiên A[0] của mảng. Sau đó so sánh max, min với từng giá trị A[i], 1 ≤ i ≤ n-1, và cập nhật max, min một cách thích ứng. Thuật toán này được mô tả bởi hàm sau:

SiMaxMin (A, max, min)

{

max = min = A[0];

for ( i = 1 ; i  n , i ++)

if (A[i]  max)

max = A[i];

else if (A[i]  min)

min = A[i];

}

Câu 7: Thuật toán tìm kiếm tuần tự

Input: Dãy khóa gồm N số nguyên k1, k2,..., kN đôi một khác nhau và số nguyên x;

Output: Chỉ số i mà ki = x hoặc thông báo không có số hạng nào của dãy có giá trị trùng với khóa x.

Ý tưởng: Lần lượt so sánh x với các số hạng trong dãy cho đến khi có sự trùng nhau.

Thuật toán:

Bước 1. Nhập N, các giá trị k1, k2,..., kN và giá trị x.

Bước 2. i Ü 1.

Bước 3. Nếu ki = x thì thông báo chỉ số i, rồi kết thúc.

Bước 4. i Ü i + 1

Bước 5. Nếu i>N thì Thông báo dãy khoa không có số hạng nào có giá trị trùng với x, rồi kết thúc.

Bước 6. Quay lại bước 3.

Mô phỏng thuật toán:

Đánh giá:

- Trường hợp tốt nhất độ phức tạp là O(1)

- Trường hợp xấu nhất và trung bình độ phức tạp là O(N)

Câu 8:Sắp xếp: bài toán sắp xếp như sau:

Cho dãy K gồm n giá trị khóa k1, k2,..., kn. Giữa hai khóa có quan hệ "<=". Cần xếp lại dãy khóa sao cho:

k'1 <= k'2<=... <= k'n. trong đó k'i thuộc tập { k1, k2,..., kn.}

a) Sắp xếp bằng lựa chọn

Ý tưởng: Tìm giá trị nhỏ nhất và tráo đổi giá trị khóa đó với khóa k1 . ở lươt thứ hai chọn trong số ( K-1) khóa còn lại khóa nhỏ nhất và tráo đổi giá trị đó cho khóa k2,..

Đánh giá: (k-1) +(k-2) +.........+2+1= k* (k-1)/2

Độ phức tạp là O(k2)

b) Sắp xếp bằng tráo đổi (Bubble Sort)

Ý tưởng: Với mỗi cặp số hạng đứng liền kề không thoả mãn điều kiện cần sắp xếp ta tiến hành đổi chỗ chúng cho nhau. Lặp lại cho đến khi mọi cặp số hạng liền kề trong dãy đều đã xếp đúng thứ tự yêu cầu.

Dây A 1 5 3 6 7 8 7 10 4 12

Lượt 1 1 3 5 6 7 7 8 4 10

Lượt 2 1 3 5 6 7 7 4 8

Lượt 3 1 3 5 6 7 4 7

Lượt 4 1 3 5 6 4 7

Lượt 5 1 3 5 4 6

Lượt 6 1 3 4 5

Lượt 7 1 3 4

Lượt 8 1 3

Lượt 9 1

c) Sắp xếp trộn (MergeSort)

Ý tưởng:. Trộn (Merge) hai dãy đã sắp thành một dãy được sắp xếp là thao tác mấu chốt của thuật toán Mergesort.

Cho hai dãy đã sắp xếp B={ b1,b2,...bm] và C={ c1,c2,...,cn} cần trộn thành dãy D={d1,d2,...,dm+n+} cũng là dãy được sắp.

Lần lượt xây dựng di ( 1<=i<=n+m) bằng cách chọn phần tử nhỏ hơn trong hai phần tử bj và ck ( 1<=j<=m; 1<=k<=n); tại mỗi bước tương ứng với phần tử được chọn thì chỉ số của nó tăng lên 1.

Đánh giá:

Sắp xếp trộn là một thuật toán sắp xếp cổ điển nhất ( do J. Von Neumann đề xuât năm 1945), nhưng cho tới nay nó được coi là thuật toán sắp xếp ngoài mẫu mực nhất.

- O(k).

- Không quá [lgn] lần trộn nên O(klgk).

- Nhược điểm là phải dùng thêm không gian để lưu trữ dãy khóa d ( trong việc trộn).

d)Sắp xếp nhanh (QuickSort)

Quicksort là một thuật toán rất hiệu quả do C.A.R. Hoare xây dựng. Nó gồm 2 phần là:

Phân đoạn ( partition)

Sắp xếp (sort).

Sau đây là cài đặt của thuật toán này:

Câu 9 : CÂY

1)Định nghĩa cây một cách đệ quy:

- Mỗi nút là một cây, nút đó cũng là nút gốc của cây

- Nếu n là một nút và n1, n2,...,nk lần lượt là gốc của các cây C1,C2,...Ck; các cây này từng đôi một không có nút chung. Nếu cho n là cha của các nút n1, n2,....,nk thì ta sẽ có một cây mới kí hiệu là cây C.

2) Các khái niệm

i) Số các con của một nút gọi là cấp của nút đó

ii) Nút có cấp bằng 0 gọi là nút lá (leaf)

iii) Các nút không phải nút lá gọi là nút nhánh ( branch)

iv) Cấp cao nhất có trong các nút của một cây gọi là cấp của cây đó.

v) Gốc của cây có mức 1, nếu một nút có mức i thì các nút con của nút đó có mức i+1.

vi) Chiều cao (height) của cây là số mức cao nhất của các nút có trên cây đó

vii) Tập hợp các cây phân biệt gọi là một rừng (forest).

3) Cây nhị phân là cây mà mọi nút của nó có tối đa hai cây con. Với mỗi nút xác định cây con trái và cây con phải.

Cây nhị phân suy biến là các cây với các nút không phải là lá chỉ có một cây con : cây lệch trái, cây lệch phải, cây dích dắc.

Cây nhị phân hoàn chỉnh (complete binary tree) là cây nhị phân có chiều cao là h thì mọi nút có mức < h-1 đều có đúng 02 nút con.

Cây nhị phân đầy đủ ( full Binary tree) là cây nhị phân có chiều cao h thì mọi nút có mức <=h-1 đều có đúng 02 nút con

Một số các tính chất:

- Cây nhị phân suy biến có chiều cao lớn nhất, cây nhị phân đầy đủ có chiều cao nhỏ nhất.

- Số lượng tối đa các nút trên mức i là 2i-1 và tối thiểu là 1 ( i>=1)

- Số lượng tối đa các nút trên cây nhị phân có chiều cao h là 2h-1 và tối thiểu là h ( h>=1)

- Cây nhị phân hoàn chỉnh có n nút thì chiều cao của nó là h=[ lg(n)] +1

Biểu diễn cây nhị phân bằng mảng

Xét cây nhị phân đầy đủ, ta đánh số thứ tự các nút lần lượt từ mức m đến mức m+1, từ trái sang phải.

Với nút i :nút con trái 2i và nút con phải là 2i+1. Nút cha của nút i là i/2. Trường hợp cây nhị phân tổng quát: thêm nút giả để cây trở thành cây nhị phân đầy đủ.

Biểu diễn cây nhị phân bằng danh sách liên kết

- Một trường Data lưu giá trị của nút đó

- Một trường Left chứa liên kết trỏ tới nút con trái. Nếu không có nút con trái thì trường này chứa một giá trị đặc biệt (Null)

- Một trường Right chứa liên kết trỏ tới nút con phải. Nếu không có nút con phải thì trường này chứa một giá trị đặc biệt (Null).

Duyệt cây nhị phân

Cách 1. Duyệt theo thứ tự trước (preorder traversal)

- Nút đang xét được duyệt trước tiên,

- Tiếp theo là duyệt nút con trái

- Sau cùng là duyệt nút con phải.

Cách 2. Duyệt theo thứ tự giữa (inorder traversal)

- Với mỗi nút thì nút con trái được duyệt trước tiên,

- Tiếp theo là duyệt nút dang xét

- Sau cùng duyệt nút con phải.

Cách 3. Duyệt theo thứ tự sau (postorder traversal)

- Với mỗi nút thì nút con trái được duyệt trước tiên,

- Tiếp đến duyệt nút con phải và

- Sau cùng là duyệt nút đang xét.

4) Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là một cây nhị phân đặc biệt có các tính chất sau:

• - Giá trị của các nút của cây con trái nhỏ hơn giá trị của nút gốc của cây con đó.

• - Giá trị của các nút của cây con phải lớn hơn giá trị của nút gốc của cây con đó.

• - Cây con trái và cây con phải cũng là cây tìm kiếm nhị phân.

- Hai giá trị khóa chứa trong hai nút bất kì khác nhau là khác nhau.

a)Phép tìm kiếm:

Có nút nào chứa giá trị bằng một giá trị?

Ý tưởng:

- đối sánh giá trị nút đó với khóa.

- Nếu giá trị nút đang xét nhỏ hơn thì tìm kiếm trên cây con trái theo cách đệ quy

- Nếu giá trị nút đang xét lớn hơn thì tìm kiếm trên cây con phải theo cách đệ quy.

b)Phép chèn:

- sau khi thêm cây mới tạo thành cũng là cây tìm kiếm nhị phân.

Ý tưởng:

• Xin cấp bộ nhớ cho một nút mới, gán giá trị mới vào trường Data của nút mới. Trường Left và trường Right của nút mới đều được gán Null.

• Duyệt cây

• Khi gặp nút x không có nút con trái/phải

Tiến hành chỉnh sữa các trường liên kết.

c)Phép xóa:

- nút lá- "cắt bỏ" x - thay giá trị liên kết của nút cha của x bằng null và giải phóng bộ nhớ của x.

- x có một trong hai cây con là cây rỗng thì thì chỉ cần điều chỉnh lại con trỏ của nút cha của x

- x có hai cây con ( x1 và x2) và chẳng hạn x1 không có con- thay nút x1 làm nút cha của cây con có gốc là x2.

- Trường hợp tổng quát: trong một cây tìm kiếm nhị phân khác rỗng, nút lá bên trái cùng có giá trị nhỏ nhất và nút lá bên phải cùng có giá trị lớn nhất.

d)Đánh giá

Giả sử mức thấp nhất là k ta có:

1+ 2+ 22 +.....+2k-1 < n

1+ 2+ 22 +.....2k >=n

Hay 2k -1 <n và 2k+1-1 >=n, do vậy log(n+1) -1 <=k < log(n+1) - xấp xỉ logn- O(logn). Cây suy biến sẽ có O(n)

Câu 10 : Khái niệm danh sách

a) Định nghĩa

- Danh sách - tập sắp thứ tự các phần tử cùng kiểu.

- Theo thứ tự "trước- sau"

- Danh sách con: từ ai đến aj .

Nếu i=1 -phần đầu (prefix)

Nếu j=n -phần cuối (postfix).

- Dãy con: loại từ danh sách một số phần tử. Ví dụ, DS = (a,b,c,d,e,f). Khi đó:

(c,d,e) là một danh sách con của DS

(a, b) là một phần đầu của DS

(c,d,e,f) là một phần cuối của DS

(a,c,f) là một dãy con của DS

b) Các phép toán trên danh sách

- Phép khởi tạo tạo DS rỗng.

- Xác định độ dài DS

- Loại bỏ một phần tử

- Chèn thêm một phần tử

- Tìm kiếm một phần tử

- Kiểm tra tính trạng thái rỗng

- Kiểm tra trạng thái tràn

- Duyệt .

- Sắp xếp lại các phần tử trong danh sách

c) Cài đặt bằng mảng một chiều

Ví dụ,

DS = ( A, B, C, D, E, F, G, H, I, J, K)

Dùng mảng M, một chiều, gồm 11 phần tử để lưu trữ DS.

+Chèn một phần tử V vào vị trí

- Dồn tất cả các phần tử từ vị trí P đến cuối sang phải một vị trí:

+ Xoa phần tử P khỏi mảng

- Mảng ban đầu

+ Nhận xét

-Truy cập trực tiếp đến mọi phần tử của mảng.

- Với các phép toán chèn và xóa đều phải dịch chuyển một số các phần tử để cho vị trí phù hợp.

Câu 11: Đệ quy (recursion)

+là một kĩ thuật định nghĩa một khái niệm trực tiếp hoặc gián tiếp theo chính nó.

+Thuật toán đệ quy

a.Định nghĩa

Nếu lời giải P được thực hiện bằng lời giải P' giống như P thì ta nói đó là lời giải đệ quy. Thuật toán tương ứng là thuật toán đệ quy.

Hai phần:

• (i) Phần neo (anchor)

• (ii) Phần đệ quy

Như vậy, phần đệ quy thể hiện tính "quy nạp" của lời giải. Phần neo đảm bảo cho tính dừng của thuật toán.

Một số ví dụ

Tính giai thừa: N!= N(N-1)!

Int fact ( int n) {

If ( n <= 1 )

Return 1; /* cơ sở*/

Else

Return n*fact (n-1) /* quy nạp*/

}

Bài toán tháp HN:

Quy tắc chuyển:

- Chuyển một đĩa phải đặt vào 1 trong 3 cọc.

- Mỗi lần chỉ chuyển một đĩa trên cùng tại một cọc và đặt vào trên cùng ở cọc chuyển đến.

- Đĩa lớn hơn không được đặt lên đĩa nhỏ hơn.

Dùng phương pháp quy nạp toán học để giải:

- Nếu n=1 thì chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2. Kết thúc.

- Giả thiết ta có cách chuyển (n-1) đĩa từ cọc 1 sang cọc 2 thì cách chuyển (n-1) đĩa từ cọc 2 sang cọc 3 cũng làm tương tự. Tiếp đến ta chuyển đĩa lớn nhất đang ở cọc 1 sang cọc 2 và tiếp theo là chuyển (n-1) đĩa từ cọc 3 sang cọc 2. Kết thúc.

b.Đánh giá về đệ quy

Ưu điểm:

- Công cụ mạnh, diễn đạt tư duy rất rõ ràng, chặt chẽ

- Việc thiết kế thuật toán đệ quy là đơn giản

- Nhược điểm:

- Lời gọi hàm hay thủ tục tốn rất nhiều thời gian.

Câu 12: Kỹ thuật quay lui để giải bài toán tối ưu

Giả sử nghiệm của bài toán có thể biểu diễn dưới dạng (a1,..,an), trong đó mỗi thành phần ai (i = 1,...,n) được chọn ra từ tập Si các ứng viên. Mỗi nghiệm (a1,..,an) của bài toán có một giá cost(a1,..,an) >= 0, và ta cần tìm nghiệm có giá thấp nhất (nghiệm tối ưu).

Giả sử rằng, giá của các nghiệm một phần là không giảm, tức là nếu (a1,..,ak-1) là nghiệm một phần và (a1,..,ak-1,ak) là nghiệm mở rộng của nó thì

cost(a1,..,ak-1) <= cost(a1,..,ak-1,ak)

Trong quá trình mở rộng nghiệm một phần (bằng kỹ thuật quay lui), khi tìm được nghiệm một phần (a1,..,ak), nếu biết rằng tất cả các nghiệm mở rộng của nó (a1,..,ak,ak+1,...) đều có giá lớn hơn giá của nghiệm tốt nhất đã biết ở thời điểm đó, thì ta không cần mở rộng nghiệm một phần (a1,..,ak) đó.Giả sử cost*(a1,..,ak) là cận dưới của giá của tất cả các nghiệm (a1,..,ak,ak+1,...) mà nó là mở rộng của nghiệm một phần (a1,..,ak). Giả sử giá của nghiệm tốt nhất mà ta đã tìm ra trong quá trình tìm kiếm là lowcost. (Ban đầu lowcost được khởi tạo là + và giá trị của nó được cập nhật trong quá trình tìm kiếm). Khi ta đạt tới nghiệm một phần (a1,..,ak) mà cost*(a1,..,ak) > lowcost thì ta không cần mở rộng nghiệm một phần (a1,..,ak) nữa; điều đó có nghĩa là, trong cây tìm kiếm hình 16.1 ta cắt bỏ đi tất cả các nhánh từ đỉnh ak.

Cây tìm kiếm được xây dựng như sau

• Các đỉnh con của gốc là các trạng thái của S1

• Giả sử ai-1 là một đỉnh ở mức thứ i-1 của cây. Khi đó các đỉnh con của ai-1¬ sẽ là các trạng thái thuộc tập ứng cử viên Si. Cây tìm kiếm được thể hiện trong hình 16.1.

Hình 16.1. Cây tìm kiếm vectơ nghiệm

Trong cây tìm kiếm, mỗi đường đi từ gốc tới một đỉnh tương ứng với một nghiệm một phần.Khi áp dụng kỹ thuật quay lui để giải quyết một vấn đề, thuật toán được thiết kế có thể là đệ quy hoặc lặp. Sau đây ta sẽ đưa ra lược đồ tổng quát của thuật toán quay lui.

Lược đồ thuật toán quay lui đệ quy. Giả sử vector là nghiệm một phần (a1,a2,...,ai-1). Hàm đệ quy chọn thành phần thứ i của vector nghiệm là như sau:

Backtrack(vector , i)

// Chọn thành phần thứ i của vector.

{

if (vector là nghiệm)

viết ra nghiệm;

Tính Si;

for (mỗi aiSi)

Backtrack(vector + (ai) , i+1);

}