N- րդ տրիբոնաչիի համարի կոդերի լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են facebook
Դինամիկ ծրագրավորում

Խնդրի հայտարարություն

«N- րդ տրիբոնաչիի համարը» խնդրում մեզ տրված է n թիվ: Մեր խնդիրն է պարզել N- րդը տրիբոնաչի թիվ.

Erրոտ տրիբոնաչիի համարը 0. Առաջին տրիբոնաչիի թիվն է 1. Երկրորդ տրիբոնաչի համարը 1 է:

N- րդ տրիբոնաչիի համարը (N-1- րդ տրիբոնաչիի թիվ), (N-2- րդ տրիբոնաչիի թիվ) և (N-3- րդ տրիբոնաչիի համար) գումարումն է:

N- րդ տրիբոնաչիի համարի կոդերի լուծում

Օրինակ

n = 4
4

Բացատրությունը. Որպես զրոթ, առաջին և երկրորդ տրիբոնաչի համարները համապատասխանաբար 0,1,1 են: Այսպիսով, երրորդ տրիբոնաչի համարն է (0 + 1 + 1) 2. Նմանապես, չորրորդ տրիբոնաչին է (1 + 1 + 2) 4:

N-th Tribonacci Number Leetcode լուծման մոտեցում

Քանի որ N- րդ տրիբոնաչիի համարը սահմանվում է որպես (N-1), (N-2) և (N-3) տրիբոնաչչի համարների ամփոփում: Այսպիսով, մեզ նախ անհրաժեշտ է (N-3) -th տրիբոնաչչի համարը, որը կօգտագործվի (N-2), (N-1) և (N) -th տրիբոնաչի համարները հաշվարկելիս: Այսպիսով, հիմա մեր նոր խնդիրն է (N-3) -th տրիբոնաչիի համարը հաշվարկելը: Այստեղ մենք կարող ենք եզրակացնել մեկ բան, այն է `հաշվարկել N- րդ տրիբոնաչիի համարը, որը մենք պետք է հաշվարկենք մեկը N- րդ տրիբոնաչի համարից, քանի որ յուրաքանչյուր հաջորդ արժեք կախված է նախորդ երեք արժեքներից: Մենք հետևելու ենք այս քայլերին.

  1. Մենք կպահենք զրոթի, առաջին և երկրորդ տրիբոնաչչի թվերի արժեքները համապատասխանաբար երեք փոփոխականներում, մասնավորապես `a, b և c:
  2. Այստեղ a, b և c կպահպանեն տրիբոնաչիի վերջին երեք համարները: Օգտագործելով տրիբոնաչիի այս երեք վերջին թվերը, մենք հաշվարկելու ենք տրիբոնաչիի հաջորդ թիվը և ապա թարմացնելու ենք a, b և c արժեքները:
  3. Մենք կկրկնենք 2-րդ քայլը, մինչև գտնենք N- րդ տրիբոնաչիի համարի արժեքը, ապա այն կվերադարձնենք:

Իրականացման

C ++ կոդ N- րդ Տրիբոնաչիի համարի համար

#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

Java- ի կոդը N- րդ Tribonacci համարի համար

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

N- րդ տրիբոնաչիի համարի լետոկոդ լուծույթի բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք կրկնվում ենք մինչև N- րդ տրիբոնաչի թիվը: Այստեղ n- ը տրված թիվն է, որի համար մենք պետք է հաշվարկենք N- րդ տրիբոնաչի թիվը:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ