使用C++找到Pell数-C++-PHP中文网

使用C++找到Pell数

WBOY

发布： 2023-08-30 18:09:06

转载

1061人浏览过

使用c++找到pell数

在给定的问题中，我们得到一个整数 n，我们需要找到 P_n，即该位置的咒语编号。现在，正如我们所知，拼写数是由以下公式给出的序列的一部分 -P_n = 2*P_n-1 + P_n-2

前两个起始数字 - P₀ = 0 和 P₁ = 1

查找方法解决方案

现在我们将通过两种方法来解决这个问题：递归和迭代。

递归方法

在这个公式中，我们将递归地应用公式Pell Number 并进行 n 次迭代。

立即学习“C++免费学习笔记（深入）”；

示例

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

登录后复制

输出

登录后复制

上述代码的解释

在这种方法中，我们通过调用 pell(n-1) && pell(n-2) 来使用递归，直到 n 小于或等于 2，因为我们知道直到 2 的拼写数字与给定数字相同。上述程序的总体时间复杂度为O(N)，其中N是给定的数字。

怪兽AI数字人

数字人短视频创作，数字人直播，实时驱动数字人

查看详情

迭代方法

在这种方法中，我们将使用与上面相同的公式，但使用 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;
}

登录后复制