Cetak dahulu n nombor Fibonacci menggunakan formula langsung

Dalam artikel ini, kami akan menyelesaikan masalah mencetak nombor n Fibonacci pertama menggunakan formula langsung.

Dalam matematik, nombor Fibonacci selalunya diwakili oleh Fn (untuk nombor Fibonacci ke-n), membentuk urutan di mana setiap nombor adalah sama dengan jumlah dua nombor sebelumnya. Nombor Fibonacci ke-1 boleh dinyatakan seperti berikut -

$$mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$$

Siri ini bermula dengan 0 dan 1. Beberapa nilai pertama dalam urutan Fibonacci bermula dari 0 dan 1 ialah -

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

Jadi, dalam masalah ini, kita akan diberikan nombor N dan kita perlu mencetak nombor N Fibonacci yang pertama menggunakan formula langsung.

Contoh

Masukkan : 4

Output: 0 1 1 2

Masuk : 8

Output: 0 1 1 2 3 5 8 13

Untuk soalan ini, kita perlu memahami konsep formula Binet, yang memberikan formula langsung untuk mendapatkan nombor Fibonacci ke-n, yang akan dibincangkan secara terperinci dalam bahagian algoritma.

Algoritma

Mengikut formula $mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$ kita memerlukan item (n-1) dan (n- 2) dan tambahkannya pada dapatkan item ke-n. Kerana dalam masalah ini kita harus mencetak n nombor Fibonacci pertama menggunakan formula langsung untuk mendapatkan nombor Fibonacci ke-n.

Untuk mendapatkan nombor Fibonacci ke-n dalam jujukan Fibonacci, anda boleh menggunakan formula eksplisit yang dipanggil formula Binet. Ia dicipta oleh ahli matematik Jacques Philippe Marie Binet.

Formula

Jika $mathrm{Fn}$ mewakili nombor Fibonacci ke- dalam jujukan Fibonacci, ia boleh dinyatakan sebagai

$$mathrm{F_n:=:frac{1}{sqrt5}((frac{1+{sqrt5}}{2})^n:-:(frac{ 1-{sqrt5}}{2})^n )}$$

NOTA - Formula ini memberikan urutan Fibonacci bermula dari 1 dan 1. Untuk mendapatkan jujukan Fibonacci bermula pada 0 dan 1, gunakan n-1 untuk mendapatkan nombor Fibonacci ke-.

Kita boleh memperoleh formula ini menggunakan konsep persamaan kuadratik. Kami akan menggunakan formula ini untuk mencetak setiap nombor Fibonacci sehingga ke nombor Fibonacci ke- untuk mencetak nombor Fibonacci pertama.

Kaedah

• Kami akan menggunakan gelung for untuk mencetak semua nombor N Fibonacci dari 0 hingga n lelaran kerana kami sedang mempertimbangkan urutan Fibonacci bermula dari 0 dan 1.

• Mulakan pembolehubah kepada nombor Fibonacci dan simpan nombor Fibonacci ke-i menggunakan formula di atas pada setiap lelaran sehingga i

• Teruskan mencetak nombor Fibonacci pada setiap lelaran, yang akan memberi kita nombor N Fibonacci yang pertama.

Contoh

Berikut adalah pelaksanaan kaedah di atas dalam C++ -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void fibonacci(long long int N){ //function to print first N fibonacci numbers
   long long int fibonacci; //to store ith fibonacci number
   
   for(int i=0;i<N;i++) { //using for loop to print all N fibonacci numbers
      //using direct formula to print every fibonacci number until n
      fibonacci = 1/sqrt(5)*(pow((1+sqrt(5))/2,i) - (pow((1-sqrt(5))/2,i)));
      cout<<fibonacci<<" ";
   }
   cout<<endl;
}

//Driver Code
int main(){
   long long int N=10;
   fibonacci(N);
   N=6;
   fibonacci(N);
   return 0;
}

Output

0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5

Kerumitan masa: O(n), kerana gelung for berjalan sehingga i kurang daripada n.

Kerumitan ruang: O(1), kerana ia tidak menggunakan ruang tambahan.

Kesimpulan

Dalam artikel ini, kami belajar mencetak nombor N Fibonacci pertama menggunakan formula langsung dan bukannya menggunakan rekursi. Kami juga mempelajari formula Binet, yang boleh terus mendapatkan nombor Fibonacci ke-n dalam jujukan Fibonacci.

Saya harap artikel ini membantu anda mengosongkan semua konsep tentang topik ini.

Atas ialah kandungan terperinci Cetak dahulu n nombor Fibonacci menggunakan formula langsung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!