N-th Tribonacci Number Leetcode الحل


مستوى الصعوبة سهل
كثيرا ما يطلب في Facebook
البرمجة الديناميكية

بيان المشكلة

في المشكلة "N-th Tribonacci Number" حصلنا على رقم n. مهمتنا هي معرفة ال N تريبوناتشي عدد.

رقم تريبوناتشي صفر. رقم تريبوناتشي الأول هو 0. رقم تريبوناتشي الثاني هو 1.

رقم تريبوناتشي N هو مجموع (N-1 th Tribonacci number) ، (N-2 th tribonacci number) ، و (N-3 th tribonacci number).

N-th Tribonacci Number Leetcode الحل

مثال

n = 4
4

التفسير: كأصفار ، فإن أرقام تريبوناتشي الأولى والثانية هي 0,1,1،0،1 على التوالي. لذا فإن رقم تريبوناتشي الثالث هو (1 + 2 + 1) 1. وبالمثل ، فإن تريبوناتشي الرابع هو (2 + 4 + XNUMX) XNUMX.

نهج N-th Tribonacci Number Leetcode Solution

حيث يتم تعريف رقم تريبوناتشي N-th على أنه مجموع (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 آخر ثلاثة أرقام تريبوناتشي. باستخدام هذه الأرقام الثلاثة الأخيرة من تريبوناتشي ، سنحسب رقم تريبوناتشي التالي ثم نحدّث قيم أ وب وج.
  3. سنكرر الخطوة 2 حتى نجد قيمة رقم تريبوناتشي N ثم نعيدها.

تطبيق

كود C ++ لرقم N-th Tribonacci

#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-th Tribonacci Number

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-th Tribonacci Number Leetcode Solution

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نكرر حتى رقم N-th tribonacci. هنا n هو الرقم المعطى الذي نحتاج إلى حساب N-th tribonacci number.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

المراجع