Fibonacci саны LeetCode чечими

Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Окшош Facebook Goldman Sachs Гугл Infosys JPMorgan Математика иштери Microsoft Съездбек Oracle SAP Uber VMware Zillow
ZoomViews 215

Маселени билдирүү

Fibonacci саны LeetCode Solution - "Фибоначчи саны" деп айтылат The Фибоначчи сандары, көбүнчө белгиленет F(n) деп аталган ырааттуулукту түзөт Фибоначчи ырааттуулугу, ар бир сан мурунку эки сандын суммасы болуп, баштап 0 жана 1. Ушул,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

эске n, эсептөө F(n).

Fibonacci саны LeetCode чечими

Мисал 1:

киргизүү:

 n = 2

Output:

 1

Explanation:

 F(2) = F(1) + F(0) = 1 + 0 = 1.

Мисал 2:

киргизүү:

 n = 3

Output:

 2

Explanation:

 F(3) = F(2) + F(1) = 1 + 1 = 2.

Мисал 3:

киргизүү:

 n = 4

Output:

 3

Explanation:

 F(4) = F(3) + F(2) = 2 + 1 = 3.

жакындоо

Идея:

Негизги байкоо: ар бир F(i) F(i-1) жана F(i-2) суммасына көз каранды. Ошентип, биз баштапкы маанини сактай турган эки өзгөрмөлөрдү алсак болот, андан кийин натыйжаны алуу үчүн N чейин кайталайбыз.

түшүндүрүү

  • N==0: 0 кайтаруу
  • N==1: 1 кайтаруу
  • демейки: кайтаруу fib(N-1) + fib(N-2)

жөнүндө сүйлөшөлү экинчи ыкма:

[34,55,89] ырааттуулугун эске алсак, а узор башкача айтканда, эгерде биз эки ырааттуу мүчөнү бөлсөк, анда бөлүм га жакын бирдей санга алып келет 1.618 деп аталат алтын катышы. Чынында бизде муну жасоонун формуласы бар! чакырды Бинет формуласы.

Болуптур? бул алтын нерсени кантип колдонсок болот! 34 болуп саналат 9th термин, Эгерде биз табабыз pow(golden,Nth term)/sqrt(5) тиркелген менен a тегерек функциясы, биз N-термин маанисин алабыз O(1) убакыт жана мейкиндик!

коду

Fibonacci номеринин C++ коду

class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c;
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
};

Fibonacci саны JAVA программасы

class Solution {
    public int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c=0;
        
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
}

Fibonacci саны LeetCode Solution үчүн татаалдыгы талдоо

Убакыт татаалдыгы

O (N)

Космостун татаалдыгы

O (1)

Translate »