פתרון ה- Leetcode למספר הטריבונאי התשיעי  


רמת קושי קַל
נשאל לעתים קרובות פייסבוק
אלגוריתמים קידוד תכנות דינמי ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions

הצהרת בעיה  

בבעיה "מספר טריבונאית N" ניתן לנו מספר n. המשימה שלנו היא לגלות את התשיעי טריבונאצ'י מספר.

מספר הטריבונאזי האפסני הוא 0. מספר הטריבונאצי הראשון הוא 1. מספר הטריבונאצי השני הוא 1.

מספר הטריבונאית ה- N הוא סיכום של (מספר הטריבונזי N-1), (מספר הטריבונזי N-2) ו- (מספר הטריבונזי N-3).

פתרון ה- Leetcode למספר הטריבונאי התשיעי

דוגמה

n = 4
4

הסבר: כמספרי אפס, מספר ראשון וטריבונאצ'י שני הם 0,1,1 בהתאמה. אז מספר הטריבונא השלישי הוא (0 + 1 + 1) 2. כמו כן, הטריבונא הרביעי הוא (1 + 1 + 2) 4.

גישה לפיתרון ה- Leetcode מספר טריבונאית מספר N  

כמספר הטריבונאית ה- N מוגדר כסיכום של (N-1), (N-2) ו- (N-3) מספר טריבונזי. אז ראשית אנו זקוקים למספר הטריבונצי (N-3) -th זה ישמש בחישוב (N-2), (N-1), ומספר הטריבונצי (N). אז עכשיו הבעיה החדשה שלנו היא לחשב את מספר הטריבונצי (N-3). כאן אנו יכולים להסיק דבר אחד שהוא לחשב את מספר הטריבונאית ה- N שעלינו לחשב אחד למספר הטריבונאית ה- N כי כל ערך הבא תלוי בשלושת הערכים הקודמים. אנו נבצע את השלבים הבאים:

  1. נאחסן את הערכים של מספרים אפסיים, ראשונים ושניים של טריבונזי בשלושה משתנים, כלומר a, b ו- c בהתאמה.
  2. כאן a, b ו- c יאחסנו את שלושת המספרים האחרונים של הטריבונאצ'י. בעזרת שלושת המספרים האחרונים של הטריבונאטי נחשב את מספר הטריבונאצ'י הבא ונעדכן את הערכים של a, b ו- c.
  3. נחזור על שלב 2 עד שנמצא את הערך של מספר הטריבונאית ה- N ואז נחזיר אותו.
ראה גם
מצא את המיקום הראשון והאחרון של האלמנט בפתרון מיון של Array Leetcode

יישום

קוד 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

קוד ג'אווה למספר הטריבונאית התשיעי

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

ניתוח המורכבות של פתרון ה- Leetcode מספר הטריבונאי התשיעי  

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) מכיוון שאנחנו חוזרים עד מספר הטריבונאית התשיעי. כאן n הוא המספר הנתון שעבורו עלינו לחשב את מספר הטריבונאית ה- N.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) מכיוון שאנחנו משתמשים רק במשתנה לאחסון התשובה.

הפניות