Loading...

ĐỆ QUI

Giải thuật đệ quy:

Giải thuật đệ quy là giải thuật có chứa thao tác gọi đến chính nó. Giải thuật đệ quy cho phép mô tả một dãy lớn các thao tác bằng một số ít các thao tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệ quy).

Giải thuật giải bài toán bằng đệ quy thường rất đẹp, gọn gàng, dễ hiểu, dễ sửa đổi. Tuy nhiên, việc xử lý giải thuật đệ quy lại thường gây khó khăn cho máy tính (tốn không gian nhớ và thời gian xử lý), hơn nữa không phải mọi ngôn ngữ lập trình đều cho phép mã hóa giải thuật đệ quy (ví dụ: FORTRAN) .

Chương trình con đệ quy:

Chương trình con đệ quy là một chương trình con mà trong thân của nó có ít nhất một câu lệnh là lời gọi đến chính nó.

Chương trình con đệ quy phải có hai thành phần:

-        Thành phần không chứa đệ qui, đó là điều kiện để kết thúc quá trình đệ qui.

-        Thành phần có chứa đệ quy, sau mỗi bước, phạm vi của thành phần này phải thay đổi cho đến khi gặp điều kiện kết thúc.

@Lưu ý: Muốn giải một bài toán bằng giải thuật đệ qui việc đầu tiên ta phải đưa bài toán về một dạng tổng quát. Từ đây ta phải đi xác định cho được điều kiện suy biến của bài toán (tức điều kiện để kết thúc giải thuật đệ qui) và điều kiện gọi đệ qui.

Ví dụ bài toán tính n!
Ta có
n=0, 0!=1,
n=1, 1!=1x1 <=>0!x1
n=2, 2!=1x1x2<=>1!x2
n=3, 3!=1x1x2x3 <=>2!x3
=>n!=1x1x2x3x...x n<=>(n-1)! x n
Như vậy:
- Điều kiện suy biến  khi n=0, 0!=1
- Điều kiện gọi đệ qui n>0, n!=n x (n-1)!
Vậy, khi có được 0! =>1! =>2!=>3! ...=>n! 
Giải thuật tính n!
 
#include <stdio.h>

long int gthua(int n);

void main(void)

{

int n;

scanf(“%d”,&n);

printf(“Giai thừa của%d là: %d”,n,gthua(n));

}

int long gthua(int n)

{

if(n==0)

          return 1;

      elsse

         return(n*gthua(n-1));

}

-      Khi thực hiện lời gọi gthua(3) sẽ phát sinh lời gọi gthua(2), đồng thời phải lưu giữ thông tin về trạng thái xử lý chưa hoàn thành (return(3 * gthua(2))) vào Stack.

-      Gặp lời gọi gthua(2), tiếp tục làm phát sinh lời gọi gthua(1), đồng thời vẩn phải lưu trử thông tin về trạng thái xử lý còn dang dở (return( 2*gthua(1)))vào Stack.

-      Cứ như vậy cho tới khi gặp lời gọi của trường hợp suy biến (return(1))).

-      Khi gặp trường hợp suy biến, những thông tin được lưu tạm trong Stack sẽ được lấy ra xử lý (thông tin lấy ra theo kiểu lưu trữ của Stack, thông tin vào sau sẽ được lấy ra trước). Và như vậy, dùng kết quả của gthua(0) để tính gthua(1), dùng kết quả của gthua(1) để tính gthua(2), dùng kết quả của gthua(2) để tính gthua(3). Cuối cùng được kết quả của phép tính giai thừa.

Cụ thể thực hiện lấy và tính toán trong Stack như sau:

-      Lấy return(1*gthua(0)) để thực hiện gthua(1)=1*gthua(0)=1*1=1

-      Lấy return(2*gthua(1)) để thực hiện gthua(2)=2*gthua(1)=2*1=3

-      Lấy return(3*gthua(2)) để thực hiện gthua(3)=3*gthua(2)=3*2=6

 Bài tập thực hành

1. Sử dụng đệ qui để viết hàm tìm ước số chung lớn nhất của 2 số

2. Sử dụng đệ qui để viết hàm tính tổng S = 1+2+….+n.

Vyht

Ý kiến của bạn

Mã bảo vệ
Làm mới

Hãy đăng quảng cáo trên TuHocAnNinhMang.com

Bài xem nhiều nhất

Tự học lập trình C - Bài 1: Một số khái niệm cơ bản

Khái niệm tên rất quan trọng trong quá trình lập trình, ...

MySQL – Bài 8: Khóa chính (primary key) và khóa ngoại (foreign key) của table

Với ràng buộc này thì, việc người sử dụng vô tình hay cố ...

Tự học lập trình JAVA – Bài 1: Bước đầu với Java

Một chương trình java có thể được định nghĩa như là một ...

Tự học lập trình C - Bài 10: Mảng một chiều

Mảng 1 chiều là tập hợp các phần tử có cùng kiểu dữ ...

Tự học lập trình C - Bài 2: Cấu trúc chương trình C

Một chương trình bao gồm một hoặc nhiều hàm, mỗi hàm ...

Hướng dẫn in ấn trong Word 2007/2010 – Step by Step

[Tự học] - Tiêu đề đầu trang (Header)/tiêu đề cuối ...

Tự học lập trình Assembly - Bài 1: Bước đầu với lập trình Assembly trên vi xử lý Intel 8086/8088

Như đã biết, lệnh ngôn ngữ máy là một dãy các con số 0, ...

Hãy đăng quảng cáo trên TuHocAnNinhMang.com

Về đầu trang Hỏi - Đáp