N-ші Трибоначчи нөмірінің шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Facebook
Динамикалық бағдарламалау

Проблеманы шешу

«N-ші Трибоначчи нөмірі» мәселесінде бізге n саны беріледі. Біздің міндетіміз N-ші анықтау трибаччи саны.

Нөлдік tribonacci саны - 0. Бірінші tribonacci саны - 1. Екінші tribonacci саны - 1.

N-ші трибаччи саны - бұл (N-1-ші трибоначчи нөмірі), (N-2-ші трибоначчи саны) және (N-3- ші трибоначчи саны).

N-ші Трибоначчи нөмірінің шешімі

мысал

n = 4
4

Түсіндіру: Нөлдік, бірінші және екінші трибаччи сандары сәйкесінше 0,1,1 құрайды. Сонымен, үшінші трибаччи саны (0 + 1 + 1) 2. Сол сияқты, төртінші трибаччи (1 + 1 + 2) 4 болады.

N-ші Tribonacci санының Leitcode шешіміне тәсіл

N-ші трионаччи саны (N-1), (N-2) және (N-3) трибоначчи санының қосындысы ретінде анықталады. Сонымен, бізге алдымен (N-3) -ші трибоначчи нөмірі керек, бұл есептеу кезінде қолданылады (N-2), (N-1) және (N) -тритоначчи нөмірі. Сонымен, енді біздің жаңа мәселеміз (N-3) - трибоначчи санын есептеу. Мұнда біз N-ші трибаччи санын есептеу үшін бір нәрсені қорытындылай аламыз, бұл үшін N-ші трибоначчи нөмірін есептеу керек, өйткені әрбір келесі мән алдыңғы үш мәнге тәуелді. Біз келесі қадамдарды орындаймыз:

  1. Нөлдік, бірінші және екінші трибаччи сандарының мәндерін үш айнымалыға, атап айтқанда a, b және c сәйкесінше сақтаймыз.
  2. Мұнда a, b және c соңғы үш трионаччи сандарын сақтайды. Осы соңғы үш трибаччи сандарын пайдаланып, келесі трибаччи нөмірін есептеп шығарамыз, содан кейін a, b және c мәндерін жаңартамыз.
  3. Біз N-ші трибоначчи санының мәнін тапқанша, 2-қадамды қайталаймыз, содан кейін оны қайтарамыз.

Іске асыру

N-ші Tribonacci нөміріне арналған C ++ коды

#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

N-ші Tribonacci нөміріне арналған Java коды

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-ші Tribonacci санының Leitcode шешімінің күрделілігін талдау

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (N) өйткені біз N-ші tribonacci санына дейін қайталаймыз. Мұнда n - трибоначчи санын есептеу керек берілген сан.

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (1) өйткені біз жауап сақтау үшін тек айнымалыны қолданамыз.

Әдебиеттер тізімі