Cari nombor Pell menggunakan C++

Dalam masalah yang diberikan, kita diberi integer n dan kita perlu mencari P_n iaitu nombor ejaan pada kedudukan tersebut. Sekarang, seperti yang kita ketahui, nombor ejaan ialah sebahagian daripada urutan yang diberikan oleh formula berikut - P_n = 2*P_n-1 + P_n-2

Dua nombor permulaan pertama - P ₀ = 0 dan P₁ = 1

Mencari Penyelesaian Kaedah

Sekarang kita akan menyelesaikan masalah ini dengan dua kaedah: rekursi dan lelaran.

Kaedah Rekursif

Dalam formula ini, kami akan menggunakan formula Pell Number secara rekursif dan melakukan n lelaran.

Contoh

#include <iostream>

using namespace std;
int pell(int n) {
   if(n <= 2)
      return n;
   return 2*pell(n-1) + pell(n-2);
}
int main() {
   int n = 6; // given n
   cout << pell(n) <<"\n"; // Pell number at that position.
   return 0;
}

Output

70

Penjelasan kod di atas

Dalam pendekatan ini kami menggunakan rekursi dengan memanggil pell(n-1) && pell(n-2) sehingga n adalah kurang daripada atau sama dengan 2 kerana Kami ketahui bahawa nombor yang dieja hingga 2 adalah sama dengan nombor yang diberikan. Kerumitan masa keseluruhan program di atas ialah O(N), dengan N ialah nombor yang diberikan.

Kaedah Iteratif

Dalam kaedah ini kita akan menggunakan formula yang sama seperti di atas tetapi menggunakan gelung for dan bukannya fungsi rekursif untuk mengira nombor.

Contoh

#include <iostream>

using namespace std;
int main() {
   int n = 6; // given n.
   int p0 = 0; // initial value of pn-2.
   int p1 = 1; // initial value of pn-1.
   int pn; // our answer.

   if(n <= 2) // if n <= 2 we print n.
      cout << n <<"\n";
   else {
      for(int i = 2; i <= n; i++) { // we are going to find from the second number till n.

         pn = 2*p1 + p0;
         p0 = p1; // pn-1 becomes pn-2 for new i.
         p1 = pn; // pn becomes pn-1 for new i.
      }

      cout << pn << "\n";
   }
   return 0;
}

Output

70

Penjelasan kod di atas

Dalam atur cara yang diberikan, kami merentasi dari 2 ke n dan hanya mengemas kini nilai pn-2 kepada pn-1, menukar nilai pn-1 Nilai dikemas kini kepada pn sehingga n dicapai.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari nombor ejaan N menggunakan rekursi dan lelaran. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain, seperti C, java, python dan bahasa lain.

Atas ialah kandungan terperinci Cari nombor Pell menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!