C++의 N번째 트리보나치 수

값 n이 있다고 가정하면 n번째 트리보나치 수를 생성해야 합니다. 트리보나치 수는 피보나치 수와 유사하지만 여기서는 이전 항 3개를 추가하여 항을 생성합니다. T(n)을 생성한다고 가정하면 공식은 다음과 같습니다. -

T(n) = T(n - 1) + T(n - 2) + T(n - 3)

시작하는 처음 몇 개의 숫자는 {0, 1, 1}입니다.

이 알고리즘을 따르면 해결할 수 있습니다 -

알고리즘

• first := 0, second := 1, third := 1
• for i in range n – 3, do
   o next := first + second + third
   o first := second, second := third, third := next
• return third

예시(C++)

#include<iostream>
using namespace std;
long tribonacci_gen(int n){
   //function to generate n tetranacci numbers
   int first = 0, second = 1, third = 1;
   for(int i = 0; i < n - 3; i++){
      int next = first + second + third;
      first = second;
      second = third;
      third = next;
   }
   return third;
}
main(){
   cout << "15th Tribonacci Term: " << tribonacci_gen(15);
}

입력

15

출력

15th Tribonacci Term: 1705