Bài Toán đệ Quy - .vn

Donate to VNFoundation Project name

• Trang chủ
• Tra cứu tài liệu
• Đóng góp
• Giới thiệu

• • 
• Đăng ký
• Đăng nhập

Đăng nhập

• Ghi nhớ
• Quên mật khẩu?

Đăng nhập Bạn chưa có tài khoản? Hãy đăng ký. Tên đăng nhập hoặc mật khẩu chưa đúng TÀI LIỆU Bài toán đệ quy Science and Technology 0

Để xây dựng giải thuật giải một bài toán có tính đệ quy bằng phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau :

1. Thông số hóa bài toán .
2. Tìm các trường hợp neo cùng giải thuật giải tương ứng .
3. Tìm giải thuật giải trong trường hợp tổng quát bằng phân rã bài toán theo kiểu đệ quy.

Thông số hoá bài toán.

Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quát (một họ các bài toán chứa bài toán cần giải ),tìm ra các thông số cho bài toán tổng quát đặc biệt là nhóm các thông số biểu thị kích thước của bài toán - các thông số điều khiển ( các thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán , và giảm đi qua mỗi lần gọi đệ qui ) .

n trong hàm FAC(n) ; a , b trong hàm USCLN(a,b) .

Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.

Đây là các trường hợp suy biến của bài toán tổng quát , là các trương hợp tương ứng với các gía trị biên của các biến điều khiển (trường hợp kích thước bài toán nhỏ nhất), mà giải thuật giải không đệ qui (thường rất đơn giản).

FAC(1) =1 , USCLN(a,0) = a , SM(a[x:x] ≡∅ ,TSUM(a[m:m]) = a[m]

Phân rã bài toán tổng quát theo phương thức đệ quy.

Tìm phương án (giải thuật ) giải bài toán trong trường hợp tổng quát bằng cách phân chia nó thành các thành phần mà hoặc có giải thuật không đệ quy hoặc là bài toán trên nhưng có kích thước nhỏ hơn.

FAC(n) = n * FAC(n -1) .

Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] )

Bài toán tháp Hà Nội .

Truyền thuyết kể rằng : Một nhà toán học Pháp sang thăm Đông Dương đến một ngôi chùa cổ ở Hà Nội thấy các vị sư đang chuyển một chồng đĩa qúy gồm 64 đĩa với kích

thước khác nhau từ cột A sang cột C theo cách :

- Mỗi lần chỉ chuyển 1 đĩa .

- Khi chuyển có thể dùng cột trung gian B .

- Trong suốt qúa trình chuyển các chồng đĩa ở các cột luôn được xếp đúng (đĩa có kích thước bé được đặt trên đĩa có kích thước lớn ) .

Khi được hỏi các vị sư cho biết khi chuyển xong chồng đĩa thì đến ngày tận thế !.

Như sẽ chỉ ra sau này với chồng gồm n đĩa cần 2 n - 1 lần chuyển cơ bản (chuyển 1

đĩa ).

Giả sử thời gian để chuyển 1 đỉa là t giây thì thời gian để chuyển xong chồng 64 đĩa sẽ là :

T = ( 2 64 − ) * t S = 1.84* 1019 *t S

Với t = 1/100 s thì T = 5.8*109 năm = 5.8 tỷ năm .

Ta có thể tìm thấy giải thuật (dãy các thao tác cơ bản ) cho bài toán một cách dễ dàng ứng với trường hợp chồng đĩa gồm 0, 1, 2, 3 đĩa . Với chồng 4 đĩa giải thuật bài

toán đã trở nên phức tạp . Tuy nhiên giải thuật của bài toán lại được tìm thấy rất dễ dàng nhanh chóng khi ta khái quát số đĩa là n bất kỳ và nhìn bài toán bằng quan niệm đệ quy .

Thông số hóa bài toán .

Xét bài toán ở mức tổng quát nhất : chuyển n (n>=0) đĩa từ cột X sang cột Z

lấy cột Y làm trung gian

Ta gọi giải thuật giải bài toán ở mức tổng quát là thủ tục THN(n ,X ,Y,Z) chứa 4 thông số n,X,Y,Z ; n thuộc tập số tự nhiên N (kiểu nguyên không dấu ); X ,Y,Z thuộc tập các ký tự (kiểu ký tự ).

Bài toán cổ ở trên sẻ được thực hiện bằng lời gọi THN(64,A,B,C) .

Dễ thấy rằng : trong 4 thông số của bài toán thì thông số n là thông số quyết định độ phức tạp của bài toán ( n càng lớn thì số thao tác chuyển đỉa càng nhiều và thứ tự thực hiện chúng càng khó hình dung ) , n là thông số điều khiển .

Trường hợp suy biến và cách giải .

Với n =1 bài toán tổng quát suy biến thành bài toán đơn giản THN (1,X,Y,Z) : tìm

dãy thao tác để chuyển chồng 1 đĩa từ cột X sang cột Z lấy cột Y làm trung gian . Giải thuật giải bài toán THN (1,X,Y,Z) là thực hiện chỉ 1 thao tác cơ bản : Chuyển 1 đĩa từ

X sang Z ( ký hiệu là Move (X , Z) ) .

THN(1,X,Y,Z) ≡ { Move( X, Z ) }

Chú ý : Hoàn toàn tương tự ta cũng có thể quan niện trường hợp suy biến là trường hợp n= 0 tương ứng với bài toán THN(0,X,Y,Z) : chuyển 0 đĩa từ X sang Z lấy Y làm

trung gian mà giải thuật tương ứng là không làm gì cả ( thực hiện thao tác rỗng ) .

THN(0,X,Y,Z) ≡ { 𝜙 }

Phân rã bài toán :

Ta có thể phần rã bài toán TH N (k,X,Y,Z) : chuyển k đĩa từ cột X sang cột Z lấy cột Y làm trung gian thành dãy tuần tự 3 công việc sau :

+ Chuyển (k -1) đĩa từ cột X sang cột Y lấy cột Z làm trung gian : THN (k -1,X,Z,Y) (bài toán THN với n = k-1,X= X , Y = Z , Z = Y ) + Chuyển 1 đĩa từ cột X sang cột Z : Move ( X, Z ) (thao tác cơ bản ). + Chuyển (k - 1 ) đĩa từ cột Y sang cột Z lấy cột X làm trung gian : THN( k -1,Y,X,Z) ( bài toán THN với n = k-1 , X = Y , Y = X , Z = Z ) . Vậy giải thuật trong trường hợp tổng quát (n > 1) là :

THN(n,X,Y,Z) ≡ { THN (n -1,X,Z,Y) ;

Move ( X, Z ) ;

THN (n -1,Y,X,Z) ;

}

Với n đĩa thì cần bao nhiêu bước chuyển 1 đĩa? Thực chất trong thủ tục THN các lệnh gọi đệ qui chỉ nhằm sắp sếp trình tự các thao tác chuyển 1 đĩa Số lần chuyển 1 đĩa được thực hiện là đặc trưng cho độ phức tạp của giải thuật . Với n đĩa , gọi f(n) là số các thao tác chuyển _một_đĩa .

Ta có : f(0) = 0 .

f(1) =1 .

f(n) = 2f(n -1) + 1 với n > 0

Do đo : f(n) = 1+ 2 + 2 2 + + 2 n-1 = 2 n - 1

Để chuyển 64 đĩa cần 2 64 - 1 bước hay xấp xỉ 10 20 bước . Cần khoảng 10 triệu

năm với một máy tính nhanh nhất hiện nay để làm việc này .

Chương trình con mã hóa giải thuật THN trong NNLT Pascal :

procedure THN (n : integer ; X,Y,Z : char) begin if n > 0 then begin THN (n-1 ,X,Z,Y) ; Move( X, Z); THN (n-1 ,Y,X,Z); end ; end ; ( Lấy trường hợp chuyển n = 0 làm trường hợp neo )

Hoặc :

procedure THN (n : integer ; X,Y,Z : char) begin if (n = 1) then Move(X, Z) else begin THN (n-1 ,X,Z,Y ) ; Move(X, Z ); THN (n -1 ,Y,X,Z ); end ; end; ( Lấy trường hợp chuyển n = 1 làm trường hợp neo )

Với thủ tục Move(X, Y) mô tả thao tác chuyển 1 đĩa từ cột X sang cột Y được viết tuỳ theo cách thể hiện thao tác chuyển .

Chương trình con mã hóa giải thuật THN trong NNLT C++ :

Trong C++ hàm con thực hiện giải thuật THN có dạng :

void THN( int n , char X,Y,Z) { if(n > 0) { THN(n -1,X,Z,Y ) ; Move ( X , Z ) ; THN(n - 1,Y,X,Z ) ; } return ; } hoặc : void THN( int n , char X,Y,Z) { if(n = = 1) Move ( X , Z ) ; else { THN(n -1,X,Z,Y ) ; Move ( X, Z ) ; THN(n - 1,Y,X,Z ) ; } return ; }

Bài toán chia thưởng.

Có 100 phần thưởng đem chia cho 12 học sinh giỏi đã được xếp hạng. Có bao nhiêu cách khác nhau để thực hiện cách chia?

Ta thấy ngay rằng việc tìm ra lời giải cho bài toàn sẻ không dễ dàng nếu ta không tìm ra cách thích hợp để tiếp cận với nó. Ta sẽ tìm giải thuật giải bài toàn bằng phương pháp đệ quy.

Thông số hóa.

Ta sẽ giải bài toán ở mức độ tổng quát : Tìm số cách chia m vật (phần thưởng ) cho n

đối tượng (học sinh ) có thứ tự .

Gọi PART là số cách chia khi đó PART là hàm của 2 biến nguyên m , n ( PART(m,n )) .

Ta mã hoá n đối tượng theo thứ tự xếp hạng 1, 2 , 3 , . . . n ; Si là số phần thưởng mà

học sinh i nhận được .

Khi đó các điều kiện ràng buộc lên cách chia là :

Si >= 0

S1 >= S2 >= >= Sn .

S1 + S2 + .… + Sn = m

Với m = 5 , n = 3 ta có 5 cách chia sau :

5 0 0

4 1 0

3 2 0

3 1 1

2 2 1

Tức là PART(5,3 ) = 5

Các trường hợp suy biến :

+ m = 0 thì sẻ có duy nhất 1 cách chia : mọi học sinh đều nhận được 0 phần thưởng .

Vậy : PART(0 , n ) = 1 với mọi n

+ n = 0 , m <> 0 thì sẽ không có cách nào để thực hiện việc chia . Vậy : PART(m , 0 ) = 0 với mọi m <> 0 .

( ta có thể thay trường hợp neo PART(m ,0) = 0 hoặc trường hợp neo PART(m , 1) = 1 )

Phân rã bài toán trong trường hợp tổng quát :

+ m < n khi số phần thương m nhỏ hơn số học sinh n thì n - m học sinh xếp cuối sẽ luôn không nhận được gì cả trong mọi cách chia .

Vậy :

khi n > m thì PART(m , n ) = PART(m , m )

+ Trong trường hợp m >= n : số vật chia (phần thưởng ) lớn hơn hoặc bằng số học sinh (đối tượng ) ta phân các cách chia làm 2 nhóm :

* Nhóm thứ nhất không dành cho học sinh xếp cuối cùng phần thưởng nào

cả

( Sn = 0 ) . Số cách chia này sẽ bằng số cách chia m phần thương cho n -1 học sinh .

Tức là : Số cách chia trong nhóm thứ nhất = PART(m , n -1 ) .

* Nhóm thứ 2 có phần cho người cuối cùng ( Sn > 0 ) . Dễ thấy rằng số

cách chia của nhóm này bằng số cách chia m - n phần thương cho n học sinh ( vì phương thức chia mà tất cả học sinh đều nhận được phần thưởng có thể thực hiện bằng cách : cho mỗi người nhận trước 1 phần thưởng rồi mới chia ).

Tức là : Số cách chia trong nhóm thứ 2 = PART(m - n , n ) .

Vậy : với m>= n PART(m , n ) = PART(m , n -1 ) + PART(m - n , n )

Dạng mã giả của hàm PART(m , n )

PART(m , n ) = if(m = 0 ) then return 1 ; else if( n = 1 ) then return 1 ; else if(m < n ) then return PART(m , m) ; else return ( PART(m , n -1) + PART(m - n , n ))

Dạng hàm PART trong NNLT Pascal

Function PART(m , n : integer ) : integer ; Begin if ( (m = 0) or ( n = 1) ) then PART := 1 else if(m < n) then PART := PART(m , m ) else PART := PART(m , n -1 ) + PART(m - n , n) ; End ; Dạng hàm PART trong NN LT C++ int PART( int m , int n ) { if ((m == 0 ) || (n == 0) ) return 1 ; else if(m < n ) retrun ( PART(m , m )) ; else return ( PART(m , n -1 ) + PART( m -n , n ) ) ; }

Bài toán tìm tất cả các hoán vị của một dãy phần tử.

Bài toán : Xuất tất cả các hoán vị của dãy A

Với dãy A gồm N = 3 phần tử A[1] = a , A[2] = b , A[3] = c thì bài toán bắt phải xuất 6 hoán vị có thể của A :

a b c a c b c b a

b a c c a b b c a

Với dãy A gồm N = 4 phần tử A[1] = 1 , A[2] = 2 , A[3] = 3 , A[4] =4 thì bài toán

bắt phải xuất 24 hoán vị có thể của A :

1 2 3 4 1 2 4 3 1 4 3 2 4 2 3

2 1 3 4 2 1 4 3 4 1 3 2 2 4 3 1

1 3 2 4 1 4 2 3 1 3 4 2 4 3 2 1

3 1 2 4 4 1 2 3 3 1 4 2 3 4 2 1

3 2 1 4 4 2 1 3 3 4 1 2 3 2 4 1

2 3 1 4 2 4 1 3 4 3 1 2 2 3 4 1

Thông số hóa bài toán .

Gọi HV(v, m ) ( với v : array[1 . . N ] of T , m :integer ; m ≤ N ; T là một kiểu dữ liệu đã biết trước ) là thủ tục xuất tất cả các dạng khác nhau của v có được bằng cách hoán vị m thành phần đầu của dãy v

N = 4 , A[1] = 1 , A[2] = 2 , A[3] = 3 , A[4] = 4 thì lời gọi HV(A ,3 ) xuất tất cả hoán vị của A có được bằng cách hoán vị 3 phần tử đầu ( có 6 h vị ) :

1 2 3 4 1 3 2 4 3 2 1 4

2 1 3 4 3 1 2 4 2 3 1 4

Để giải bài toán đặt ra ban đầu ta gọi HV(A,N) ).

Trường hợp neo.

Vơi m = 1 : HV(v,1) là thủ tục giải bài toán xuất tất cả các dạng của v có được bằng cách hoán vị 1 phần tủ đầu . Vậy HV(v,1) là thủ tục xuất v. HV(v,1) ≡ print(v) ≡ for k:= 1 to N do write(v[k])

Phân rã bài toán.

Ta có thể tìm hết tất cả các hoán vị m phần tử đầu của vector V theo cách sau : - Giữ nguyên các phần tử cuối V[m] , . . ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) .

- Đổi chổ V[m] cho V[m-1] ,giữ nguyên các phần tử cuối V[m],... ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) .

- Đổi chổ V[m] cho V[m-2] ,giữ nguyên các phần tử cuối V[m],…. ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) .

- Đổi chổ V[m] cho V[2] ,giữ nguyên các phần tử cuối V[m], . .. ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) .

- Đổi chổ V[m] cho V[1] ,giữ nguyên các phần tử cuối V[m], . . . ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) .

Vậy :

HV(V,m) ≡ { SWAP( V[m],V[m] ) ; HV(V,m - 1) ;

SWAP( V[m],v[m-1] ) ; HV(V,m - 1) ;

SWAP( V[m],v[m-2 ] ) ; HV(V,m - 1) ;

SWAP (V[m],v[2] ) ; HV(V,m - 1) ;

SWAP( V[m],v[1] ) ; HV(V,m - 1) ;

}

( SWAP(x , y ) là thủ tục hoán đổi giá trị của 2 đối tượng dữ liệu x ,y ) Vậy :

HV(V , m ) ≡ for k := m downto 1 do begin

SWAP( V[m], V[k] ) ;

HV(V,m - 1) ; end ;

Thủ tục hoán vị trên NNLT Pascal.

const size = Val ; (* Val là hằng gía trị *) type vector = array[1.. size] of typebase; (* typebase là một kiểu dữ liệu có thứ tự *) procedure Swap( var x , y : typebase ) ; var t : typebase ; begin t := x ; x := y ; y := t ; end ; procedure print( A : vector ) ; var i : integer ; begin for i:= 1 to size do write( A[i] : 3 ); writeln ; end ; Procedure HV( V : vec tor ; m :integer ) ; var k : integer ; begin if (m = 1 ) then print(V) else for k := m downto 1 do begin Swap(V[m] , V[k]); HV(V , m - 1) ; end ; end ;

Thủ tục hoán vị trên NNLT C++ .

const size = Val ; // Val là hằng gía trị typedef typebase vector[size] ; // typebase là một kiểu dữ liệu có thứ tự void Swap( typebase & x , typebase& y) { typebase t ; t = x ; x = y ; y = t ; } void print( const vector &A) { for(int j= 0 ; j <size ; j++ ) cout<< A[j] ; cout << endl ; } void HV( const vector &V , int m) { if (m == 1 ) print( V ); else for(int k = m-1 ; k > = 0 ; k-- ) { swap(V[m-1] ,V[k] ) ; HV(V,m-1) ; } }

Bài toán sắp xếp mảng bằng phương pháp trộn (Sort-Merge).

Ý tưởng : Để sắp xếp 1 danh sách gồm n phần tử bằng phương pháp trộn người ta chia danh sách thành 2 phần (tổng quát là nhiều phần ) , sắp xếp từng phần, rồi trộn chúng .

Bài toán : sắp theo thứ tự không giảm mảng a : VectorT bằng phương pháp trộn.

( VectorT = array[1 . . size] of T).

Thông số hoá:

Bài toán được khái quát thành sắp xếp một dãy con của dãy V : VectorT từ chỉ số m đến chỉ số n với 1 <= m <= n <= size . Ta đặt tên cho bài toán ở dạng tổng quát là : SM(V,m,n).

Bài toán ban đầu : sắp dãy A sẻ được thực hiện bằng lời gọi : SM(A ,1,size).

Trường hợp tầm thường:

Đó là khi n = m (dãy sắp chỉ có 1 phần tử ), khi đó không cần làm gì cả (thao tác rỗng)

Phân rã trường hợp tổng quát :

Khi n > m ta thực hiện các công việc sau :

+ Chia dãy : a[m] ,a[m+1], . . . , a[n] thành 2 dãy con a[m] , . . , a[l] và a[l+1] , . . . , a[n]

+ Sắp xếp từng dãy con thành các dãy có thứ tự theo giải thuật SM .

+ Trộn 2 dãy con có thứ tự lại thành dãy a[m] ,. . . , a[n] mới có thứ tự .

Để thực hiện việc trộn hai dãy có thứ tự thành một dãy có thứ tự ta sẽ dùng một thủ tục không đệ quy Merge(m , l , n) . Ta cần chọn l để được 2 dãy con giảm hẵn kích thước so với dãy ban đầu , tức là chọn l : m < l < l+1 < n .

Thương chọn l là phần tử “giữa “ : l = ( m + n ) div 2 .

Thủ tục Sort_Merge(m,n) trên mảng V : VectorT viết trên ngôn ngữ PASCAL có dạng :

procedure SM (var d: VectorT ; m,n: index); var l : index ;

begin

if n>m then begin

l := (m+n) div 2; SM (d,m,l) ;

SM (d,l+1,n) ;

Merge (d,m,l,n) ; end ;

end ;

Trong đó SM là thủ tục trộn 2 dãy tăng để được một dãy tăng. Để sắp mảng A (dãy A[1:size]) ta gọi SM(A ,1,size)

Bài toán tìm nghiệm xấp xỉ của phương trình f(x)=0 .

Bài toán : Hàm f(x) liên tục trên đoạn [ao,bo] , tìm một nghiệm xấp xỉ với độ chính xác trên [ao,bo] của phương trình f(x) = 0.

Ý tưởng của giải thuật :

- Trường hợp neo : bo - ao < ε

+ Nếu f(ao).f(bo) ≤ 0 thì hàm f có nghiệm trên [ao,bo] .Và vì ta đang tìm

nghiệm xấp xỉ với độ chính xác nên ao là nghiệm xấp xỉ cần tìm .

+ Nếu f(ao).f(bo) > 0 thì ta xem như không có nghiệm xấp xỉ trên đoạn xét.

- Trương hợp bo - ao ≥ ε thì chia đôi đoạn [ao,bo] rồi tìm lần lượt nghiệm trên

từng đoạn con : đoạn con trái, đoạn con phải

Ta sẽ xây dựng một hàm đệ qui trả về giá trị là nghiệm xấp xỉ của f (nếu có),hay một hằng E ( đủ lớn) nếu f không có nghiệm xấp xỉ trên [ao,bo] .

Thông số hoá:

Xét hàm ROOT với 3 thông số là g , a,b ,(ROOT(g,a,b)) trả về giá trị nghiệm xấp xỉ của phương trình g(x) =0 trên đoạn [a,b] hoặc giá trị C nếu phương trình xét không

có nghiệm xấp xỉ . Để giải bài toán ban đấu ta gọi hàm ROOT(f,ao,bo) .

Trường hợp tầm thường:

đó là khi b - a < epsilon . Khi đó :

if ( g(a).g(b) ) <= 0 then ROOT(g,a,b) = a ; // a là nghiệm xấp xỉ

else ROOT(g,a,b) = E ; // không có nghiệm xấp xỉ

Phân rã trường hợp tổng quát:

khi b - a >= ta phân [a,b] làm 2 đoạn [a,c] và [c,b] với c = (a + b) / 2.

- Nếu ROOT(g , a ,c) < E thì ROOT(g , a , b ) = ROOT(g ,a ,c) (bài toán tìm nghiệm trên đoạn [a,c] ) .

- còn không thì ROOT(g , a , b ) = ROOT(g ,c ,b) (bài toán tìm nghiệm trên

đoạn [c ,b] ) .

Hàm tìm nghiệm xấp xỉ trên NN Pascal có dạng:

const epsilon =; E =; Function ROOT(a,b :real ) :real ; var c , R : real ; begin if ((b-a) < epsilon ) then if ( f(a)*f(b) <= 0 ) then ROOT := a else ROOT := L else begin c := (a + b)/2 ; if( ROOT(a ,c ) < E ) then ROOT := ROOT(a,c) else ROOT := ROOT(c,b) end;

Chương trình con tìm nghiệm xấp xỉ trong NN LT C++

const double epsilon =; const doubleE =; double ROOT(double a , double b ) { if((b - a) < epsilon ) if(f(a)*f(b) <= epsilon return (a ) ; else return ( L ) ; else { double c = (a + b ) / 2 ; double R = ROOT(a,c) ; if( R< E ) return R ; else return ( ROOT(c , b) ) ; } } 0 TẢI VỀ TÁI SỬ DỤNG

• Tài liệu PDF
• Tài liệu EPUB

• Trần Hoàng Thọ
• 0 GIÁO TRÌNH | 7 TÀI LIỆU

NỘI DUNG CÙNG TÁC GIẢ

• Kiểm chứng tính đúng có điều kiện
• Khử đệ quy
• Kiểm chứng tính đúng đầy đủ
• Bài toán đệ quy
• Các khái niệm
• Một số kiến thức về logic
• Khái niệm đệ quy

×

VOER message

×

VOER message

Thư viện Học liệu Mở Việt Nam (VOER) được tài trợ bởi Vietnam Foundation và vận hành trên nền tảng Hanoi Spring. Các tài liệu đều tuân thủ giấy phép Creative Commons Attribution 3.0 trừ khi ghi chú rõ ngoại lệ.

•