Dãy Fibonacci là gì ?

Dãy Fibonacci tạo dãy các số bằng cách cộng hai số đằng trước. Dãy Fibonacci bắt đầu từ hai số: F0 & F1. Giá trị ban đầu của F0 & F1 có thể tương ứng là 0, 1 hoặc 1, 1.

Điều kiện của dãy Fibonacci là:

Fn = Fn-1 + Fn-2

Ví dụ một dãy Fibonacci:

F8 = 0 1 1 2 3 5 8 13

Ví dụ một dãy Fibonacci khác:

F8 = 1 1 2 3 5 8 13 21

Dưới đây là phần minh họa cho dãy Fibonacci trên:

Dãy Fibonacci trong cấu trúc dữ liệu và giải thuật

Giải thuật sử dụng vòng lặp cho dãy Fibonacci

Đầu tiên, giải thuật của chúng ta sẽ sử dụng vòng lặp để tạo dãy Fibonacci:

Bt đầu gii thut Fibonacci(n)
   khai báo f0, f1, fib, loop 

   Thiết lp f0 là 0
   Thiết lp f1 là 1

   hin th f0, f1

   for loop  1 ti n

      fib  f0 + f1   
      f0  f1
      f1  fib

      hin th dãy fib
   kết thúc for

Kết thúc gii thut

Giải thuật sử dụng đệ qui cho dãy Fibonacci

Tiếp theo, dựa vào đệ qui chúng ta sẽ thiết kế giải thuật cho dãy Fibonacci như sau:

Bt đầu gii thut Fibonacci(n)
   khai báo f0, f1, fib, loop 

   Thiết lp f0 là 0
   Thiết lp f1 là 1

   hin th f0, f1

   for loop  1 ti n

      fib  f0 + f1   
      f0  f1
      f1  fib

      hin th dãy fib
   kết thúc for

Kết thúc gii thut

Dãy Fibonacci sử dụng đệ qui trong C

#include<stdio.h>  
#include<conio.h>  

// khai bao ham indayFibonacci
void indayFibonacci(int n){  
    static int n1=0,n2=1,n3;  
    if(n>0){  
         n3 = n1 + n2;  
         n1 = n2;  
         n2 = n3;  
         printf("%d ",n3);  
         indayFibonacci(n-1);  
    }  
}  

// ham main de in day Fibonacci
int main(){  
    int n;  

    printf("Ban hay nhap so phan tu trong day Fibonacci: ");  
    scanf("%d",&n);  

    printf("Hien thi day Fibonacci tren man hinh\n\n");  
    printf("%d %d ",0,1);  
    indayFibonacci(n-2);  //n-2 boi vi 2 phan tu dau tien da duoc in 

    printf("\n\n===========================\n");
    getch();  
}  

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Dãy Fibonacci trong Cấu trúc dữ liệu và giải thuật

Viết câu trả lời

Drop Images

0 Bình luận