एक और फाइबोनैचि संख्या संगणना एल्गोरिथम

लेख पढ़ने से पहले, मैंने ओ (लॉग एन) के स्पर्शोन्मुखी व्यवहार के साथ अपने स्वयं के एल्गोरिदम के साथ आने का प्रयास करने का फैसला किया। इसमें ज्यादा समय नहीं लगा। नीचे विचार का वर्णन और C ++ में एक उदाहरण है।

बस यह सूत्र प्राप्त करें:
जहाँ

सूत्र आसानी से प्रेरण द्वारा सिद्ध किया जाता है। जब m = 0, सूत्र सत्य है:

मान लीजिए कि सूत्र m = p के लिए सत्य है

आइए हम सिद्ध करें कि सूत्र m = p + 1 के लिए मान्य है:

- केस एम = पी के लिए एक ही अभिव्यक्ति प्राप्त की, अर्थात्। m = p + 1 के लिए, सूत्र सत्य रहता है
प्राप्त करना आसान है एक ही संख्या के माध्यम से:

विषम एन के लिए, मी, हम चुन सकते हैं ताकि समानताएं और । यह संख्या बराबर है
सरलीकरण के बाद, हम निम्नलिखित सूत्र प्राप्त करते हैं:




नवीनतम सूत्रों का उपयोग करके, आप एक सरल पुनरावर्ती एल्गोरिदम प्राप्त कर सकते हैं।

#include <iostream> using namespace std; void fibonachi_recursive(int n, int& fn, int& fn1) { int gn, gn1; if (n < 2) { fn = n; fn1 = 1; return; } fibonachi_recursive(n / 2, gn, gn1); if (n % 2) { fn = gn1 * gn1 + gn * gn; fn1 = gn1 * gn1 + 2 * gn * gn1; } else { fn = 2 * gn * gn1 - gn * gn; fn1 = gn1 * gn1 + gn * gn; } } int fibonachi(int n) { int fn, fn1; fibonachi_recursive(n, fn, fn1); return fn; } int main() { for (int i = 0; i < 20; i++) cout << fibonachi(i) << " "; return 0; } 

पुनरावृत्ति से दूर होना काफी आसान है:

 #include <iostream> using namespace std; unsigned fibonachi(unsigned n) { if (n < 2) return n; unsigned mask = 1, m = n; while (m > 1) { m >>= 1; mask <<= 1; } unsigned fn = 1, fn1 = 1, gn, gn1; while (mask > 1) { mask >>= 1; gn = fn; gn1 = fn1; if (n & mask) { fn = gn1 * gn1 + gn * gn; fn1 = gn1 * gn1 + 2 * gn * gn1; } else { fn = 2 * gn * gn1 - gn * gn; fn1 = gn1 * gn1 + gn * gn; } } return fn; } int main() { for (int i = 0; i < 20; i++) cout << fibonachi(i) << " "; return 0; } 

UPD ने "लंबे" अंकगणित को ध्यान में रखते हुए एसिम्पोटिक्स का एक अनुमान जोड़ा