Bài giảng Cấu trúc dữ liệu và giải thuật - Chia để trị - FOTECH

Chia để trịÝ tưởngPhương phápLược đồ tổng quátBài toán tìm kiếm phần tử x trong phạm vi 1..nBài toán tìm kiếm phần tử x trong dãy đã sắp thứ tựTìm giá trị max và min trong dãy 1CTDL & GT, NVA - FOTECH1. Ý tưởngĐể giải bài toán có kích thước n, ta chia bài toán đã cho thành một số bài toán con có kích thước nhỏ hơn Các bài toán con lại được tiếp tục chia thành các bài toán con nhỏ hơn nữa Quá trình này tiếp tục cho tới khi ta được các bài toán mà chúng đã có lời giải hoặc dễ dàng giải được – bài toán cơ sở2CTDL & GT, NVA - FOTECH1.Ý tưởng ( tiếp)3CTDL & GT, NVA - FOTECH2.Phương phápGồm 2 quá trình :Phân tích bài toán đã cho thành các bài toán cơ sởTổng hợp kết quả từ các bài toán cơ sở để có lời giải của bài toán ban đầu4CTDL & GT, NVA - FOTECH3.Lược đồ tổng quátChia để trị (A,x) {tìm nghiệm x của bài toán A}Bước 1: Nếu A đủ nhỏ thì GiảiBàiToán(A)	 ngược lại thì thực hiện: 	Bước 2: Phân tích A thành các bài toán 	 con A1, A2, , Am Bước 3: Giải các bài toán A1,A2, , Am 	 để được các nghiệm x1,x2, ,xm 	 tương ứng 5CTDL & GT, NVA - FOTECH3.Lược đồ tổng quát (tiếp )Bước 4: Kết hợp các nghiệm xi (i=1,2m) 	của các bài toán con Ai (i =1,2..m) để 	được nghiệm của bài toán A 6CTDL & GT, NVA - FOTECHBài toán 1: Tìm kiếm nhị phân phần tử x trong khoảng 1..nCho dãy số gồm các số [1 ..n]VD: Dãy A={a1 =3; a2 =15;a3=67; a4 = 28; a5=50; a6=45;a7=69;a8=32;a9=93; a10=71}Hỏi phần tử x = 32 có trong dãy trên không? 7CTDL & GT, NVA - FOTECHBài toán 1 (tiếp)3 15 67 28 50 45 69 32 93 711 2 3 4 5 6 7 8 9 103 15 67 28 5045 69 32 93 713 15 6745 69 3228 5093 71 3 15 45 69 67 28 50 32 93 71 3 15 45 698CTDL & GT, NVA - FOTECHBài toán 1 (tiếp)Sau 9 bước chia, bài toán trở thành bài toán cơ sở : Kiểm tra 2 phần tử có bằng nhau không ?Kiemtra(a,x): Nếu x = a thì trả lời đúng, ngược lại trả lời sai9CTDL & GT, NVA - FOTECHBài toán 1 (tiếp )Kiemtra(a,x):Nếu (a=x) thì Kiemtra = Đúng, ngược lại Kiemtra = Sai10CTDL & GT, NVA - FOTECHBài toán 1(tiếp ) 67 28 50 32 93 71 3 15 45 69Kiemtra(3,32) : Sai ; Kiemtra(15,32): Sai ; Kiemtra(67,32): Sai; Kiemtra(28,32): Sai; Kiemtra(50,32): Sai; Kiemtra(45,32): Sai; Kiemtra(69,32): Sai; Kiemtra(32,32): Đúng; Kiemtra(93,32): Sai; Kiemtra(71,32): Sai; Hợp nghiệm: Sai  Sai  Đúng  Sai = ĐúngTrả lời : Có phần tử x=32 trong dãy số trên11CTDL & GT, NVA - FOTECHBài toán 1(tiếp )Xây dựng thủ tụcTìmKiếm(A,i,j,x) A dãy các số a1 ..an ; Tìm từ vị trí i đến vị trí j; x: số cần tìm12CTDL & GT, NVA - FOTECHBài toán 1 (tiếp)TìmKiếm(A,i,j,x)B1: Nếu (i=j) thì Kiemtra(ai,x), ngược lại thực hiện B2,B3,B4B2: l=i,r=j; DiểmChia = [l+r] /2;B3: TìmKiếm(A,l,DiểmChia,x)B4: TìmKiếm(A,DiểmChia+1,r,x);13CTDL & GT, NVA - FOTECHBài toán 1 (tiếp)Dãy A={a1 =3; a2 =15;a3=67; a4 = 28; a5=50; a6=45;a7=69;a8=32;a9=93; a10=71}Tìmkiếm(A,1,10,32)l=1;r=10;DiểmChia =(1+10)/2;Tìmkiếm(A,1,5,32)Tìmkiếm(A,6,10,32);Tìmkiếm(A,1,5,32)	l=1;r=5;	Diểmchia =(1+5)/2;	Tìmkiếm(A,1,3,32);	Tìmkiếm(A,4,5,32);Tìmkiếm(A,1,3,32)	l=1;r=3;	DiểmChia =(1+3)/2;	Tìmkiếm(A,1,2,32);	Tìmkiếm(A,3,3,32);Tìmkiếm(A,3,3,32)	Kiemtra(a3,32); //(Kiemtra(67,32)) 14CTDL & GT, NVA - FOTECHBài toán 2: Tìm kiếm nhị phân phần tử x trong dãy đã được sắp xếpVD: Cho dãy số A={a1 =3; a2 =15;a3=28; a4 = 32; a5=45; a6=50;a7=67;a8=69;a9=71; a10=93} đã được sắp theo thứ tự tăng dần.Hỏi phần tử x = 32 có trong dãy trên không? 15CTDL & GT, NVA - FOTECHBài toán 2 (tiếp)Phương pháp:Chia dãy A[1..n] thành 3 dãy con : A[1..k-1], A[k], A[k+1..n]Nếu x = A[k] thì dãy A chứa phần tử xNếu x A[k] ta tìm trên dãy con A[k+1 ..n]Để tìm x trên dãy con A[1..k-1] hoặc A[k+1..n] ta lại áp dụng cách phân chia như đã làm với A[1..n]16CTDL & GT, NVA - FOTECHBài toán 2 (tiếp)3 15 28 32 45 50 67 69 71	 931 2 3 4 5 6 7 8 9 1045 3 15 28 32 50 67 69 71 93So sánh 45 với x cần tìm. Nếu x45 Ta chỉ tìm kiếm trong dãy con bên phải	Nếu x=45, thì trả lời có x trong dãy17CTDL & GT, NVA - FOTECHBài toán 2 (tiếp) 3 15 28 32 1 2 3 4 28 32 3 15 28 32 28 32Vì x =32 >15 ta tìm trong dãy con bên phảiVì x =32 >28 ta tìm trong dãy con bên phải 3218CTDL & GT, NVA - FOTECHBài toán 2 (tiếp)TìmKiếm(A,i,j,x)B1:l=i,r=j; B2: Nếu (l > r) thì Trả lời Không tìm thấy, ngược lại làm các bước sau:DiểmChia = [l+r] /2;Nếu x ADiểmChia thì TìmKiếm(A,DiểmChia +1,j,x)Ngược lại Trả lời Tìm thấy 19CTDL & GT, NVA - FOTECHBài toán 2 (tiếp)A={a1 =3; a2 =15;a3=28; a4 = 32; a5=45; a6=50;a7=67;a8=69;a9=71; a10=93}TìmKiếm(A,1,10,32)l =1; r=10;Diểmchia = (1+10)/2;Vì a5 = 45 > 32 nên TìmKiếm(A,1,4,32);TìmKiếm(A,1,4,32)	DiemChia = (1+4)/2;	Vì a2 = 15 < 32 nên TìmKiếm(A,3,4,32);20CTDL & GT, NVA - FOTECHBài toán 3: Tìm giá trị max và min trong dãy A Chia dãy A[1..n] thành 2 dãy con A[1..k] và A[k+1..n] (k=n/2)Ta tìm max và min của dãy A[1..n] thông qua việc tìm max và min của dãy A[1..k] và A[k+1..n]Để tìm được max và min trên các mảng con ta lại tiếp tục chia đôi chúng21CTDL & GT, NVA - FOTECHBài toán 3 (tiếp)Dãy A={a1 =3; a2 =15;a3=67; a4 = 28; a5=50; a6=45;a7=69;a8=32;a9=93; a10=71}Tìm giá trị max và min22CTDL & GT, NVA - FOTECHBài toán 3 (tiếp)3 15 67 28 50 45 69 32 93 711 2 3 4 5 6 7 8 9 103 15 67 28 5045 69 32 93 713 15 6745 69 3228 5093 71 3 15 45 69 67 3223CTDL & GT, NVA - FOTECHBài toán 3 (tiếp) 67 28 50 32 93 71 3 15 45 69 67 3 15 28 50 32 45 69 93 71 67 3 15 28 50 32 45 69 93 71 67 3 15 28 50 32 45 69 93 7124CTDL & GT, NVA - FOTECHBài toán 3 (tiếp)MaxMin(A,i,j,max,min) (A: dãy số ai..aj, max, min lưu giá trị max, min của dãy A )B1: Nếu (i=j) thì thực hiện các bước B1.1 và B1.2, ngược lại thực hiện B2B1.1: max = ai; B1.2: min = aj;B2: Nếu (j=i+1) thì thực hiện B3, ngược lại thực hiện B425CTDL & GT, NVA - FOTECHBài toán 3 (tiếp)B3: Nếu (ai <aj) thìmax = aj;min = ai;ngược lại max = ai;min = aj;26CTDL & GT, NVA - FOTECHBài toán 3 (tiếp)B4: DiểmChia = (i+j) / 2;MaxMin(A,i,DiểmChia,maxLeft,minLeft);MaxMin(A,DiểmChia+1,j,maxRight,minRight);Nếu (maxLeft <maxRight) thì max = maxRight; ngược lại max =maxLeft;Nếu (minLeft < minRight) thì min = minLeft; ngược lại min = minRight; 27CTDL & GT, NVA - FOTECH