Fibonacci ቁጥር LeetCode መፍትሔ

የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ብሉምበርግ eBay ፌስቡክ ጎልድማን ሳክስ google ኢንፎሲስ JPMorgan የሂሳብ ስራዎች የ Microsoft NVIDIA በ Oracle SAP በ Uber VMware Zillow
አጉላዕይታዎች 215

የችግሩ መግለጫ

Fibonacci ቁጥር LeetCode መፍትሔ - "Fibonacci ቁጥር" ይላል የፊቦናቺ ቁጥሮች፣ በተለምዶ ይገለጻል። 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

ውጤት

 1

ማብራሪያ:

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

ምሳሌ 2:

ግቤት

 n = 3

ውጤት

 2

ማብራሪያ:

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

ምሳሌ 3:

ግቤት

 n = 4

ውጤት

 3

ማብራሪያ:

 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) ተያይloል ጋር a ክብ ተግባር፣ የ Nth ቃል እሴትን እናስገባለን። ኦ(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;
        
    }
};

JAVA የ Fibonacci ቁጥር ፕሮግራም

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 መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን)

የቦታ ውስብስብነት

ኦ (1)

Translate »