펠 번호 - DSA

GfG Practice에서 사용해 보세요. ' title=

#practiceLinkDiv { 표시: 없음 !중요; }

펠 수(Pell Number)는 피보나치 수와 유사한 숫자이며 다음과 같이 아래 공식에 의해 생성됩니다.

P_n = 2*P_n-1 + P_n-2 with seeds P₀ = 0 and P₁ = 1

처음 몇 개의 Pell 숫자는 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... P를 반환하는 int pell(int n) 함수를 작성하세요._N.

예:

Input : n = 4 Output :12

Input : n = 7 Output : 169

Recommended Practice 펠 번호 시도해 보세요!

방법 1(재귀 사용)

C++

// Pell Number Series using Recursion in C++ #include    using namespace std; // calculate nth pell number int pell(int n) {  if (n <= 2)  return n;  return 2 * pell(n - 1) + pell(n - 2); } // Driver Code int main() {  int n = 4;  cout << ' ' << pell(n);  return 0; } // This code is contributed by shivanisinghss2110

// Pell Number Series using Recursion in C #include  // calculate nth pell number int pell(int n) {  if (n <= 2)  return n;  return 2 * pell(n - 1) + pell(n - 2); } // driver function int main() {  int n = 4;  printf('%d' pell(n));  return 0; }

Java

// Pell Number Series using Recursion in JAVA class PellNumber {  // calculate n-th Pell number  public static int pell(int n)  {  if (n <= 2)  return n;  return 2 * pell(n - 1) + pell(n - 2);  }  // driver function  public static void main(String args[])  {  int n = 4;  System.out.println(pell(n));  } }

Python3

# Pell Number Series using  # Recursion in Python3 # Calculate nth pell number def pell(n) : if (n <= 2) : return n return (2 * pell(n - 1) + pell(n - 2)) # Driver function n = 4; print(pell(n)) # This code is contributed by Nikita Tiwari.

// Pell Number Series using Recursion in C# using System; class PellNumber {  // calculate n-th Pell number  public static int pell(int n)  {  if (n <= 2)  return n;  return 2 * pell(n - 1) + pell(n - 2);  }  // Driver function  public static void Main()  {  int n = 4;  Console.Write(pell(n));  } } // This code is contributed by vt_m.

PHP

 // Pell Number Series using // Recursion in PHP // calculate nth pell number function pell($n) { if ($n <= 2) return $n; return 2 * pell($n - 1) + pell($n - 2); } // Driver Code $n = 4; echo(pell($n)); // This code is contributed by Ajit. ?>

JavaScript

<script> // Pell Number Series using // Recursion in Javascript // calculate nth pell number function pell(n) {  if (n <= 2)  return n;  return 2 * pell(n - 1) +  pell(n - 2); } // Driver Code let n = 4; document.write(pell(n)); // This code is contributed by _saurabh_jaiswal. </script>

산출

시간 복잡도: 오(2^N) 즉, 기하급수적으로 시간이 복잡해집니다.

보조 공간: 에)

방법 2(반복)

자바스크립트 코멘트

C++

// Iterative Pell Number Series in C++ #include    using namespace std; // Calculate nth pell number int pell(int n) {  if (n <= 2)  return n;  int a = 1;  int b = 2;  int c i;  for (i = 3; i <= n; i++) {  c = 2 * b + a;  a = b;  b = c;  }  return b; } // Driver Code int main() {  int n = 4;  cout << pell(n);  return 0; } // This code is contributed by nidhi_biet

// Iterative Pell Number Series in C #include  // calculate nth pell number int pell(int n) {  if (n <= 2)  return n;  int a = 1;  int b = 2;  int c i;  for (i = 3; i <= n; i++) {  c = 2 * b + a;  a = b;  b = c;  }  return b; } // driver function int main() {  int n = 4;  printf('%d' pell(n));  return 0; }

Java

// Iterative Pell Number Series in Java class PellNumber {  // calculate nth pell number  public static int pell(int n)  {  if (n <= 2)  return n;  int a = 1;  int b = 2;  int c;  for (int i = 3; i <= n; i++) {  c = 2 * b + a;  a = b;  b = c;  }  return b;  }    // driver function  public static void main(String args[])  {  int n = 4;  System.out.println(pell(n));  } }

Python

# Iterative Pell Number  # Series in Python 3 # calculate nth pell number def pell(n) : if (n <= 2) : return n a = 1 b = 2 for i in range(3 n+1) : c = 2 * b + a a = b b = c return b # driver function n = 4 print(pell(n)) # This code is contributed by Nikita Tiwari.

// Iterative Pell Number Series in C# using System; class PellNumber {  // calculate nth pell number  public static int pell(int n)  {  if (n <= 2)  return n;  int a = 1;  int b = 2;  int c;  for (int i = 3; i <= n; i++) {  c = 2 * b + a;  a = b;  b = c;  }  return b;  }    // Driver function  public static void Main()  {  int n = 4;  Console.Write(pell(n));  } } // This code is contributed by vt_m.

PHP

 // Iterative Pell Number Series in PHP // calculate nth pell number function pell($n) { if ($n <= 2) return $n; $a = 1; $b = 2; $c; $i; for ($i = 3; $i <= $n; $i++) { $c = 2 * $b + $a; $a = $b; $b = $c; } return $b; } // Driver Code $n = 4; echo(pell($n)); // This code is contributed by Ajit. ?>

JavaScript

<script>  // Iterative Pell Number Series in Javascript    // calculate nth pell number  function pell(n)  {  if (n <= 2)  return n;  let a = 1;  let b = 2;  let c;  for (let i = 3; i <= n; i++) {  c = 2 * b + a;  a = b;  b = c;  }  return b;  }    let n = 4;  document.write(pell(n));   </script>

산출:

시간 복잡도: O(n)

보조 공간: O(1)

행렬 계산 사용 :

이는 행렬 M = {{2 1} {1 0}}을 자신에게 n번 곱하면(즉, 거듭제곱(M n)을 계산) 결과 행렬의 행과 열(0 0)에 있는 요소로 (n+1)번째 Pell 수를 얻는다는 사실에 의존하는 또 다른 O(n)입니다.

M^n=시작{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} 끝{bmatrix}

여기서 M=begin{bmatrix} 2 &1 \ 1 &0 end{bmatrix}

시간 복잡도: O(log n) 2 × 2 행렬의 n제곱을 O(log n)번에 계산할 수 있으므로

퀴즈 만들기