CTDLGT Giải thuật và đệ quy

Giải thuật đệ quy là

• Trong giải thuật của nó có lời gọi của chính nó

• Trong giải thuật của nó có lời gọi của chính nó nhưng với qui mô nhỏ hơn

• Trong giải thuật của nó có lời gọi của chính nó nhưng với qui mô lớn hơn

• Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả

Có Hàm đệ qui sau:

Public long Factorial(int n)

{ if (n=0) Factorial=1;

else Factorial = n*Factorial(n-1); }

Dòng lệnh " if (n=0) Factorial=1" là:

•  Điều kiện dừng đệ qui

• Lặp 1 lần

• Lặp vô hạn

•  Điều kiện không thực hiện đệ qui

Có Hàm đệ qui sau: Public long Factorial(int n)

{if (n=0) Factorial=1;

else Factorial = n*Factorial(n-1); }

Kết quả bằng bao nhiêu khi n=3

• 6

• 8

• 3

• 2

• 11001

• 10011

• 11111

• 00000

Một giải thuật đệ quy xảy ra trường hợp suy biến khi nào:

• Khi kết quả của giải thuật bằng giá trị 0

• Khi không giải quyết được giải thuật

• Sau một số lần có lời gọi đệ qui và bài toán khi đó sẽ được giải quyết để dừng bài toán.

• Sau vô số lần gọi đệ qui

• 14

• 15

• 16

• 17

• 14
• 15

• 16

• 17

• 20

• 17

• 18

• 19

Hàm đệ quy nào dưới đây tìm số Fibonacci thứ n?

• public int Fibonacci(int n) { if n<=2 return 1 ; else return Fibonacci(n - 1) + Fibonacci(n - 2); }

• public int Fibonacci(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return Fibonacci(n - 1) + Fibonacci(n - 2); }

• public int Fibonacci(int n) { if (n == 1) return 1; else if (n == 2) return 2; else return Fibonacci(n - 1) + Fibonacci(n - 2); }

Hàm đệ quy nào dưới đây tìm ước số chung lớn nhất (GCD) của hai số a và b? (với a luôn là số lớn)

• public int GCD(int a, int b) { if (b == 0) return a; else return GCD(b, a % b); }

• public int GCD(int a, int b) { if (a == 0) return b; else return GCD(a % b, b); }

• public int GCD(int a, int b) { if (b == 0) return a; else return GCD(b, a-b); }

• public int GCD(int a, int b) { if (b == 0) return b; else return GCD(a % b, b); }