Xem mẫu
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 2: Đệ qui và giải thuật đệ qui
Khái niệm đệ qui
Giải thuật đệ qui và chương trình đệ qui
Các bài toán đệ qui căn bản
Khái niệm đệ qui
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa
qua chính nó hoặc một đối tượng khác cùng dạng với
chính nó bằng quy nạp
Ví dụ: Đặt hai chiếc gương cầu đối diện nhau.
Trong chiếc gương 1 chứa hình chiếc gương 2. Chiếc gương 2
lại chứa hình chiếc gương 1 nên tất nhiên nó chứa lại hình ảnh
của chính nó trong chiếc gương 1… Ở một góc nhìn hợp lý, ta
có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương
Ví dụ:
Định nghĩa số tự nhiên
0 là số tự nhiên bé nhất.
Nếu k là số tự nhiên thì k + 1 cũng là số tự nhiên
Như vậy, số tự nhiên bắt đầu từ 0, ta có các số tự nhiên
là: 0 + 1 = 1, 1 + 1 = 2,…
Chuỗi ký tự
Chuỗi rỗng là một chuỗi ký tự.
Một chuỗi ký tự ghép với một ký tự bất kỳ là một chuỗi
ký tự.
Quá trình đệ qui
Quá trình đệ qui gồm 2 phần:
Trường hợp cơ sở (base case)
Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở
Ví dụ:
Hàm giai thừa: n!
a) 0!=1
b) Nếu n>0 thì n! = n*(n -1)!
nguon tai.lieu . vn
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 2: Đệ qui và giải thuật đệ qui
Khái niệm đệ qui
Giải thuật đệ qui và chương trình đệ qui
Các bài toán đệ qui căn bản
Khái niệm đệ qui
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa
qua chính nó hoặc một đối tượng khác cùng dạng với
chính nó bằng quy nạp
Ví dụ: Đặt hai chiếc gương cầu đối diện nhau.
Trong chiếc gương 1 chứa hình chiếc gương 2. Chiếc gương 2
lại chứa hình chiếc gương 1 nên tất nhiên nó chứa lại hình ảnh
của chính nó trong chiếc gương 1… Ở một góc nhìn hợp lý, ta
có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương
Ví dụ:
Định nghĩa số tự nhiên
0 là số tự nhiên bé nhất.
Nếu k là số tự nhiên thì k + 1 cũng là số tự nhiên
Như vậy, số tự nhiên bắt đầu từ 0, ta có các số tự nhiên
là: 0 + 1 = 1, 1 + 1 = 2,…
Chuỗi ký tự
Chuỗi rỗng là một chuỗi ký tự.
Một chuỗi ký tự ghép với một ký tự bất kỳ là một chuỗi
ký tự.
Quá trình đệ qui
Quá trình đệ qui gồm 2 phần:
Trường hợp cơ sở (base case)
Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở
Ví dụ:
Hàm giai thừa: n!
a) 0!=1
b) Nếu n>0 thì n! = n*(n -1)!