Н-то Трибонаццијево решење са шифром кода


Ниво тешкоће Лако
Често питани у фацебоок
Динамичко програмирање

Изјава о проблему

У задатку „Н-ти Трибоначијев број“ добијамо број н. Наш задатак је да откријемо Н-ту трибонацци број.

Нулти број трибоначијевог броја је 0. Први трибоначијев број је 1. Други трибоначијев број је 1.

Н-ти трибоначијев број је сумирање (Н-1-ти трибоначијев број), (Н-2-и трибоначијев број) и (Н-3-ти трибоначијев број).

Н-то Трибонаццијево решење са шифром кода

Пример

n = 4
4

objašnjenje: Као нулти, први и други трибоначијеви бројеви су 0,1,1 респективно. Дакле, трећи трибоначијев број је (0 + 1 + 1) 2. Исто тако, четврти трибоначијев број је (1 + 1 + 2) 4.

Приступ решењу Н-тог Трибоначијевог броја са Леетцоде-ом

Како је Н-ти трибоначијев број дефинисан као збир (Н-1), (Н-2) и (Н-3) трибоначијевог броја. Дакле, прво нам је потребан (Н-3) -ти трибоначијев број који ће се користити за израчунавање (Н-2), (Н-1) и (Н) -ти трибоначијев број. Дакле, наш нови проблем је израчунати (Н-3) -ти трибоначијев број. Овде можемо закључити једну ствар да је израчунавање Н-тог трибоначијевог броја потребно да израчунамо један до Н-тог трибоначијевог броја, јер је свака следећа вредност зависна од претходне три вредности. Пратићемо ове кораке:

  1. Вредности нултог, првог и другог трибоначијевог броја чуваћемо у три променљиве, наиме а, б и ц.
  2. Овде ће а, б и ц сачувати последња три трибоначијева броја. Користећи ова последња три трибоначијева броја израчунаћемо следећи трибоначијев број, а затим ћемо ажурирати вредности а, б и ц.
  3. Понављаћемо корак-2 док не пронађемо вредност Н-тог трибоначијевог броја, а затим ћемо га вратити.

Имплементација

Ц ++ код за Н-ти Трибоначијев број

#include <bits/stdc++.h> 
using namespace std; 
    int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d = a + b + c;
        while (n-- > 2) {
            d = a + b + c, a = b, b = c, c = d;
        }
        return c;
    }

int main() 
{ 
int n=4;
int ans=tribonacci(n); 
 cout<<ans<<endl;
 return 0;
}
4

Јава код за Н-ти Трибоначијев број

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d;
        while (n-- > 2) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
  public static void main(String[] args) {
        int n=4; 
        int ans=tribonacci(n); 
        System.out.println(ans);
  }
}
4

Анализа сложености Н-тог Трибонаццијевог решења Леетцоде решења

Временска сложеност

Временска сложеност горњег кода је Он) јер понављамо до Н-тог трибоначијевог броја. Овде је н дати број за који треба израчунати Н-ти трибоначијев број.

Свемирска сложеност

Сложеност простора горњег кода је О (1) јер користимо само променљиву за чување одговора.

Референце