फाइबोनैकी श्रृंखला

Question

के लिए एल्गोरिदम फ़ंक्शन मैं एक उत्तर के लिए जरूरी नहीं देख रहा हूं, लेकिन मैं यह पूछ रहा हूं कि यह प्रश्न क्या पूछ रहा है। इस सवाल को एक साक्षात्कार के लिए पढ़ा गया लेकिन यह सुनिश्चित नहीं है कि वे क्या पूछ रहे हैं?

फ़िबोनैकी अनुक्रम के माध्यम से चलने वाला फ़ंक्शन लिखें और पैरामीटर के रूप में पारित होने वाली अनुक्रमणिका लौटाएं।

Answer 1

सबसे पहले, आप विकी से link के साथ फिबोनासी के बारे में अपनी मूल गणित जानकारी अपडेट कर सकते हैं। और तेजी से गणना के लिए this formula पर देखें। और आप इसे this link में इसके बारे में सब कुछ पढ़ सकते हैं।

यह वें फिबोनैकी संख्या की गणना करने के पुनरावर्ती क्रिया है और हे की है (2^n) समय:

int Fibonacci(int n) { 
     if (n == 0 || n == 1) return n; 
     else 
     return Fibonacci(n - 1) + Fibonacci(n - 2); } 

अनुक्रम कम्प्यूटिंग

आप तर्क दे सकते हैं कि वास्तव में कंप्यूटिंग के मामले में कंप्यूटर पर फाइबोनैकी अनुक्रम के मान, आप मूल पुनरावृत्ति संबंध, f [n] = f [n-1] + f [n-2] का उपयोग करके बेहतर हैं। मैं सहमत होने के इच्छुक हूं। बड़ी संख्या के लिए प्रत्यक्ष बंद-फॉर्म समाधान का उपयोग करने के लिए, आपको बहुत सटीकता बनाए रखने की आवश्यकता है। यहां तक ​​कि 9 दशमलव स्थानों के साथ, fn≈round (0.723606798⋅ (1.618033989) n), उदाहरण के लिए, के लिए केवल n = 38 तक 0 (here बनाम here देखें) के लिए मान्य है। इसके अलावा, पूर्णांकों में जोड़ने से कम computationally महंगा है और एक प्रतीकात्मक अंश या चल बिन्दु मूल्य

इस वें फिबोनैकी संख्या की गणना करने के बेहतर विचार है और हे की है exponentiating तुलना में अधिक सटीक (एन) समय है:

int Fibonacci(int n) { 
if(n <= 0) return 0; 
if(n > 0 && n < 3) return 1; 

int result = 0; 
int preOldResult = 1; 
int oldResult = 1; 

for (int i=2;i<n;i++) { 
    result = preOldResult + oldResult; 
    preOldResult = oldResult; 
    oldResult = result; 
} 

return result;} 

और इस का सबसे अच्छा तरीका वें फिबोनैकी संख्या की गणना करने के लिए है और (लॉग (एन)) समय हे की है:

this link:

जैसा कि आप पहले से ही संदेह कर रहे हैं, यह बहुत समान काम करेगा। यदि आप वेक्टर

f(n-1), f(n-2), ... , f(n-x+1), f(n-x) 

जो

f(n), f(n-1), ... , f(n-x+1) 

मैट्रिक्स घातांक में जो परिणाम के साथ इस मैट्रिक्स गुणा समझने के लिए x * x मैट्रिक्स

|1 0 0 0 .... 1 1| 
|1 
| 1 
| 1 
|  1 
|  1 
................... 
................... 
|   ... 1 0| 

यह आसान है के एन-वें शक्ति का उपयोग कर सकते ओ (लॉग (एन)) समय में किया जाना चाहिए (जब एक्स स्थिर होना माना जाता है)।

फिबोनासी पुनरावृत्ति के लिए, एक बंद फॉर्मूला समाधान भी है, यहां देखें http://en.wikipedia.org/wiki/Fibonacci_number, बिनेट या मोइवर के फॉर्मूला को देखें।

और देखो: मैं सवाल अलग तरह से व्याख्या 1- nth fibonacci number in sublinear time

Answer 2

public static int fibonacci(int i){ 
if(i==0) 
    return 0; 

if(i==1) 
    return 1; 
return fib(--i,0,1); 
} 


public static int fib(int num,int pre,int prepre){ 
    if(num==0){ 
    return prepre+pre; 
    } 
    return fib(--num,pre+prepre,pre); 
} 

Answer 3

.... एक इनपुट के रूप में एक number को देखते हुए श्रृंखला में उस नंबर के index क्या है? जैसे input=5, तो सूचकांक 5 (अनुक्रम 0 1 1 2 3 5 दिया जहां सूचकांक 0 साथ शुरू होता है) है

इस कोड को इस प्रकार हैं (जो सूचकांक रिटर्न) है [अस्वीकरण: http://talkbinary.com/programming/c/fibonacci-in-c/ में दिए गए कोड से अनुकूलित]

int Fibonacci(int n) 
{ 
    if (n == 0) 
    return 0; 
    if (n== 1) 
    return 1; 

    int fib1 = 0; 
    int fib2 = 1; 
    int fib = 0; 
    int i = 0; 

for (i = 2; ; i++) 
{ 

    fib = fib1 + fib2; 
    if (n == fib) 
     break; 
    fib1 = fib2; 
    fib2 = fib; 
} 


    return i; 
} 

Answer 4

मुझे ऐसा लगता है कि आपको nth fibonacci no वापस करने के लिए कहा जाता है, जहां n पास पैरामीटर है। आप इस प्रश्न का उत्तर देने के लिए विभिन्न विधियों को नियोजित कर सकते हैं, जबकि ये सभी समय जटिलता और कोड जटिलता में भिन्न होते हैं।

विधि 1 (रिकर्सन का उपयोग करें) एक सरल विधि जो ऊपर दिए गए प्रत्यक्ष पुनरावृत्ति कार्यान्वयन गणितीय पुनर्वास संबंध है।

int fib(int n) 
{ 
    if (n <= 1) 
    return n; 
    return fib(n-1) + fib(n-2); 
} 

समय जटिलता: टी (एन) = टी (n-1) + T (n-2) घातीय है। हम देख सकते हैं कि यह कार्यान्वयन बहुत बार बार-बार काम करता है (निम्नलिखित रिकर्सन पेड़ देखें)। तो यह nth फिबोनाची संख्या के लिए एक बुरा कार्यान्वयन है।

     fib(5) 
       /   \  
      fib(4)    fib(3) 
     / \    / \ 
    fib(3)  fib(2)   fib(2) fib(1) 
    / \  / \  / \ 

मिथ्या (2) मिथ्या (1) मिथ्या (1) मिथ्या (0) मिथ्या (1) मिथ्या (0) /\ मिथ्या (1) मिथ्या (0) अतिरिक्त अंतरिक्ष: O (n) अगर हम फ़्यूशन कॉल स्टैक आकार पर विचार करते हैं, अन्यथा ओ (1)।

विधि 2 (गतिशील प्रोग्रामिंग का उपयोग करें) हम दोबारा किए गए काम से बच सकते हैं, अब तक की गणना की गई फिबोनाची संख्याओं को संग्रहीत करके विधि 1 है।

int fib(int n) 
{ 
    /* Declare an array to store fibonacci numbers. */ 
     int f[n+1]; 
     int i; 

    /* 0th and 1st number of the series are 0 and 1*/ 
    f[0] = 0; 
    f[1] = 1; 

    for (i = 2; i <= n; i++) 
    { 
     /* Add the previous 2 numbers in the series 
     and store it */ 
     f[i] = f[i-1] + f[i-2]; 
    } 

    return f[n]; 
} 

समय जटिलता: हे (एन) अतिरिक्त अंतरिक्ष: हे (एन)

विधि 3 (अंतरिक्ष Otimized विधि 2) हम कर सकते हैं पिछले दो नंबर भंडारण के द्वारा विधि 2 में उपयोग अंतरिक्ष का अनुकूलन केवल इसलिए कि हमें श्रृंखला में अगली फिबांकी संख्या प्राप्त करने की आवश्यकता है।

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

समय जटिलता: हे (एन) अतिरिक्त अंतरिक्ष: हे (1)

विधि 4 (matrx का उपयोग करते हुए बिजली {{1,1}, {0,1}}) यह एक अन्य ओ (एन) जो इस तथ्य पर निर्भर करता है कि यदि हम बार मैट्रिक्स एम = {{1,1}, {0,1}} को गुणा करते हैं (दूसरे शब्दों में बिजली की गणना (एम, एन)), तो हम परिणामस्वरूप मैट्रिक्स में पंक्ति और कॉलम (0, 0) पर तत्व के रूप में (एन + 1) वें फाइबोनैकी संख्या प्राप्त करें।

मैट्रिक्स प्रतिनिधित्व फाइबोनैचि संख्या के लिए निम्नलिखित बंद अभिव्यक्ति देता है:

/* Helper function that multiplies 2 matricies F and M of size 2*2, and 
    puts the multiplication result back to F[][] */ 
    void multiply(int F[2][2], int M[2][2]); 

    /* Helper function that calculates F[][] raise to the power n and puts the 
    result in F[][] 
    Note that this function is desinged only for fib() and won't work as general 
    power function */ 
    void power(int F[2][2], int n); 

    int fib(int n) 
    { 
    int F[2][2] = {{1,1},{1,0}}; 
    if(n == 0) 
     return 0; 
    power(F, n-1); 

    return F[0][0]; 
    } 

    void multiply(int F[2][2], int M[2][2]) 
    { 
    int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
    int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
    int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
    int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

    F[0][0] = x; 
    F[0][1] = y; 
    F[1][0] = z; 
    F[1][1] = w; 
    } 

    void power(int F[2][2], int n) 
    { 
    int i; 
    int M[2][2] = {{1,1},{1,0}}; 

    // n - 1 times multiply the matrix to {{1,0},{0,1}} 
    for (i = 2; i <= n; i++) 
     multiply(F, M); 
    } 

समय जटिलता: हे (एन) अतिरिक्त अंतरिक्ष: हे (1)

विधि 5 (अनुकूलित विधि 4) विधि 4 को ओ (लॉगन) समय जटिलता में काम करने के लिए अनुकूलित किया जा सकता है। हम prevous विधि में बिजली (एम, एन) (अनुकूलन इस पोस्ट में किया के समान) प्राप्त करने के लिए पुनरावर्ती गुणा कर सकते हैं

void multiply(int F[2][2], int M[2][2]); 

    void power(int F[2][2], int n); 

    /* function that returns nth Fibonacci number */ 
    int fib(int n) 
    { 
    int F[2][2] = {{1,1},{1,0}}; 
    if(n == 0) 
     return 0; 
    power(F, n-1); 
    return F[0][0]; 
    } 

    /* Optimized version of power() in method 4 */ 
    void power(int F[2][2], int n) 
    { 
    if(n == 0 || n == 1) 
     return; 
    int M[2][2] = {{1,1},{1,0}}; 

    power(F, n/2); 
    multiply(F, F); 

    if(n%2 != 0) 
     multiply(F, M); 
    } 

    void multiply(int F[2][2], int M[2][2]) 
    { 
    int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
    int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
    int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
    int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

    F[0][0] = x; 
    F[0][1] = y; 
    F[1][0] = z; 
    F[1][1] = w; 
    } 

समय जटिलता: ओ (logn) अतिरिक्त अंतरिक्ष: ओ (logn) अगर हम फंक्शन कॉल स्टैक आकार पर विचार करते हैं, अन्यथा ओ (1)।

चालक कार्यक्रम: int मुख्य() { int n = 9; printf ("% d", fib (9)); getchar(); वापसी 0; }

संदर्भ: http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html

Answer 5

यह एक बहुत ही खराब शब्दों में सवाल है, लेकिन आप वे n ^वें Fibonnaci संख्या जहां n पैरामीटर के रूप में प्रदान की जाती है के लिए पूछ रहे हैं ग्रहण करने के लिए किया है।

सभी दूसरों द्वारा सूचीबद्ध तकनीक, n > 1 के लिए आप भी golden ratio method, जो किसी भी पुनरावृत्ति विधि से ज़्यादा तेज़ है उपयोग कर सकते हैं के अलावा

। लेकिन जैसा कि सवाल कहता है 'फाइबोनैकी अनुक्रम के माध्यम से चलाएं' यह योग्य नहीं हो सकता है। आप शायद उन्हें मौत के लिए भी डराएंगे।