main frame

1.Dãy số Fibonacci

Dãy Fibonacii là dãy số mà các phần tử trong dãy có giá trị bằng tổng của 2 phần tử trước ngay nó, một số thuộc dãy Fibonacci được gọi là số Fibonacci 

Dãy số này bắt đầu từ 2 số 0 và 1, một vài số đầu tiên trong dãy Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.... 

Định nghĩa : 

20 số đầu tiên trong dãy Fibonacci : 

Dãy số Fibonacci tăng rất nhanh và khi bạn sinh ra dãy số này tới số Fibonacci thứ 92 sẽ có giá trị F92 = 7540113804746346429 (~7,5.10¹⁸). Đây là số Fibonacci lớn nhất mà kiểu dữ liệu long long trong ngôn ngữ C có thể lưu được, bạn có thể xem đầy đủ 300 số Fibonacci đầu tiên tại đây

2.Kiểm Tra Số Fibonacci

Trong các bài toán liên quan tới Fibonacci thường yêu cầu bạn kiểm tra 1 số có phải là số Fibonacci hay không.

Mình sẽ hướng dẫn các bạn 2 cách, 1 là sử dụng vòng lặp để sinh ra dãy số Fibonacci, 2 là sử dụng mảng để sinh ra dãy Fibonacci.

Nếu bạn chưa biết kiến thức về mảng thì có thể tìm tới phần bài viết về mảng 1 chiều để đọc qua trước lý thuyết.

a. Kiểm tra số Fibonacci bằng vòng lặp

Như đã đề cập ở mục 1 thì dãy số Fibonacci tăng rất nhanh và chỉ cần tính tới số thứ 92 sẽ đạt tới số Fibonacci lớn nhất mà long long có thể lưu.

Vì thế để kiểm tra 1 số có phải là số Fibonacci hay không bạn hãy sinh ra các số Fibonacci từ F0 tới F92 và kiểm tra các số mình sinh ra có giống với số cần kiểm tra hay không.

Code : 

#include "stdio.h"
#include "math.h"

int fibo(long long n){
   //2 so fibonacci f0 va f1
   if(n == 0 || n == 1){
      return 1;
   }
   long long fn1 = 1, fn2 = 0, fn;
   //sinh ra so fibonacci tu f2 toi f92
   for(int i = 2; i <= 92; i++){
      fn = fn1 + fn2;
      if(fn == n){
         return 1;
      }
      //dich fn1 fn2 sang 2 gia tri tiep theo
      fn2 = fn1;
      fn1 = fn;
   }
   return 0;
}

int main(){
   long long n = 89;
   if(fibo(n)){
      printf("YES\n");
   }
   else{
      printf("NO\n");
   }
   return 0;
}

Output :

YES

b.Kiểm tra số Fibonacci bằng mảng

Tương tự như kiểm tra số Fibonacci bằng vòng lặp, bạn cũng có thể sử dụng mảng để lưu lại các số trong dãy Fibonacci.

Mỗi lần kiểm tra số bạn chỉ cần duyệt các số Fibonacci mà bạn đã lưu trong mảng và so sánh.

Code : 

#include "stdio.h"
#include "math.h"

int fibo(long long n){
   //F[i] : So fibonacci thu i
   long long F[100];
   F[0] = 0; F[1] = 1;
   for(int i = 2; i <= 92; i++){
      F[i] = F[i - 1] + F[i - 2];
   }
   //Kiem tra
   for(int i = 0; i <= 92; i++){
      if(n == F[i]){
         return 1;
      }
   }
   return 0;
}


int main(){
   long long n = 89;
   if(fibo(n)){
      printf("YES\n");
   }
   else{
      printf("NO\n");
   }
   return 0;
}

Output :

YES

3.Bài Toán Với Dãy Fibonacci

Bài 1. In ra các số Fibonacci từ 1 đến N

#include "stdio.h"
#include "math.h"

int fibo(long long n){
   if(n == 0 || n == 1){
      return 1;
   }
   long long fn1 = 1, fn2 = 0, fn;
   for(int i = 2; i <= 92; i++){
      fn = fn1 + fn2;
      if(fn == n){
         return 1;
      }
      fn2 = fn1;
      fn1 = fn;
   }
   return 0;
}

int main(){
   int n = 1000;
   for(int i = 0; i <= n; i++){
      if(fibo(i)){
         printf("%d ", i);
      }
   }
   return 0;
}

Output : 

0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Bài 2. In ra N số Fibonacci đầu tiên (N≥1)

Chú ý : N số Fibonacci đầu tiên thì bạn cần in từ F₀ tới F_{N - 1}

Code 1 : Sử dụng vòng lặp

#include "stdio.h"
#include "math.h"

void fibo(int n){
   if(n == 1){
      printf("0\n");
   }
   else{
      printf("0 1 ");
      long long fn1 = 1, fn2 = 0, fn;
      for(int i = 2; i < n; i++){
         fn = fn1 + fn2;
         printf("%lld ",  fn);
         fn2 = fn1;
         fn1 = fn;
      }
   }
}
int main(){
   fibo(20);
   return 0;
}

Output : 

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Code 2 : Sử dụng mảng 

#include "stdio.h"
#include "math.h"

void fibo(int n){
   long long F[100];
   F[0] = 0;
   F[1] = 1;
   for(int i = 2; i < n; i++){
      F[i] = F[i - 1] + F[i - 2];
   }
   for(int i = 0; i < n; i++){
      printf("%lld ", F[i]);
   }
}

int main(){
   fibo(20);
   return 0;
}

Output :

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Xem thêm bài giảng về số Fibonacci của mình : 

0DDT_XcJ1jw