使用C++找到Pell數

在給定的問題中，我們得到一個整數 n，我們需要找到 P_n，也就是該位置的咒語編號。現在，如我們所知，拼字數是由以下公式給出的序列的一部分-P_n = 2*P_n-1 P_n-2

前兩個起始數字- P₀ = 0 和P₁# = 1

#找出方法解決方案

#現在我們將透過兩種方法來解決這個問題：遞歸和迭代。

遞歸方法

在這個公式中，我們將遞歸地應用公式Pell Number 並進行 n 次迭代。

範例

#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;
}

輸出

70

上述程式碼的解釋

在這種方法中，我們透過呼叫pell(n-1) && pell( n-2) 來使用遞歸，直到n 小於或等於2，因為我們知道直到2 的拼字數字與給定數字相同。上述程序的總體時間複雜度為O(N)，其中N是給定的數字。

迭代方法

在這個方法中，我們將使用與上面相同的公式，但使用 for 迴圈而不是遞歸函數來計算數字。

範例

#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;
}

輸出

70

上述程式碼的解釋

在給定的程式中，我們從2 遍歷到n，並簡單地將pn-2 的值更新為pn-1，將pn-1 的值更新為pn，直到達到n .

結論

#在本文中，我們使用遞歸和迭代解決了查找第N 個咒語編號的問題。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言寫相同的程序，例如C、java、python等語言。

以上是使用C++找到Pell數的詳細內容。更多資訊請關注PHP中文網其他相關文章！