Viết chương trình tìm số fibonaci trong java

Lập trinh java tutorial sẽ giới thiệu cho các bạn về một bài toàn tìm số fibonaci trong java, với tiêu bài toàn này các bạn hãy phân tích theo những yêu cầu như sau:

Đầu vào
Nhập vào một số nguyên dương n
Đầu ra :
số fibonaci của thứ n

Trước tiên các bạn hãy hiểu như thế nào về fibonaci.

Fibonaci là một Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là:

Thực hiện bài toán và viết chương trình tìm số fibonaci thứ n trong java như sau:

Thuật toán tìm số fibonaci bằng thuật toán đệ quy
Giải thuật :
Đệ quy là một phương pháp dùng trong các chương trình máy tính nó dùng để thực hiện một hàm và tự gọi chính nó
1. Hiểu đơn giản đệ quy là gì?
Trước tiên ta cần hiểu phương thức trước, trong lập trình, phương thức là tập hợp các lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết các phương thức tự gọi (hoạc định nghĩa lại) chính nó.
Xem ví dụ đơn giản sau nhé. Đề bài: Tính lũy tiến từ 0 đến n.

public int sum(int n) {
  if (n >= 1) {
      return sum(n - 1) + n;
  }
  return n;
}

Thuật toán đệ quy trong java sử dụng tìm số fibonaci

// dung de quy de tinh so fibonaci thu n
int fibonaci(int n){
if(n == 1 || n ==2)return 1;
return fibonaci(n-1) + fibonaci(n-2);
}

Giải thích:

•    Quy luật, ta nhận thấy số n sẽ là tổng của 2 chữ số đứng sau nó là (n-2) + (n-1).
•    Và ta biết chắc chắn rằng n1 = 0 và n2= 1 là điều kiện dừng của dãy số. 

 
Thuật toán tìm số fibonaci bằng vòng lặp
 Code chương trình:

// khong dung de quy de tim fibonaci
int fibonaciN(int n){
if(n == 1 || n == 2) return 1;
int i =3,a=0,a1 =1,a2 =1;
while(i<=n){
a = a1+a2;
a1 =a2;
a2 =a;
i++;
}
return a;
}

Giải thích:

•    Thực hiện kiểm tra điêu kiện nế n =1 hoặc n =2 thì nó trả về giá trị là 1.
•    Ngoài trường hợp trên ta thực hiện phép gắn giá trị a,a1,a2 sau đó thực hiện vòng lặp whilte cho đến khi i<=n thì kết thúc.
•    Trong vòng lặp white ta thực hiện phép tình tổng và hoán đổi các giá trị như trên và tăng i thêm một ở mỗi lượt.

Toàn bộ code chương trình tìm số fibonaci N trong java 

public class Timsofibonaci {
// dung de quy de tinh so fibonaci thu n
int fibonaci(int n){
if(n == 1 || n ==2)return 1;
return fibonaci(n-1) + fibonaci(n-2);
}
// khong dung de quy de tim fibonaci
int fibonaciN(int n){
if(n == 1 || n == 2) return 1;
int i =3,a=0,a1 =1,a2 =1;
while(i<=n){
a = a1+a2;
a1 =a2;
a2 =a;
i++;
}
return a;
}
public static void main(String args[]){
int n =40;
Timsofibonaci fb = new Timsofibonaci();
System.out.println("so fibonaci thu n: " + n +" la : " +fb.fibonaci(n));
System.out.println("so fibonaci thu n: " + n +" la : " +fb.fibonaciN(n));
}
}

Xin cảm ơn các bạn đã theo dõi bài viết của tôi, nếu có vấn đề gì mọi người cứ comment ở bên dưới, mình sẽ trả lời.