जेकेंडोर्फ प्रमेय क्या है?
जेकेंडोर्फ प्रमेय के अनुसार, प्रत्येक धनात्मक पूर्णांक को गैर-आसन्न फाइबोनैचि संख्याओं के योग के रूप में विशिष्ट रूप से दर्शाया जा सकता है। अर्थात, कोई भी दो क्रमागत फाइबोनैचि संख्याओं का उपयोग नहीं किया जाता।
उदाहरण के लिए, यदि दिया गया योग मान 10 है, तो यह 8 और 2 का योग है। 8 और 2 दोनों फाइबोनैचि पद हैं और वे आसन्न नहीं हैं।
एल्गोरिदम
nonNeighbourFibo(sum):
Begin
while sum > 0:
fibo := सबसे बड़ा फाइबोनैचि पद लेकिन sum से बड़ा नहीं
print fibo
sum := sum - fibo
done
End
उदाहरण
#include <iostream>
using namespace std;
// n से छोटा या बराबर सबसे बड़ा फाइबोनैचि नंबर लौटाता है
int fibonacci(int n) {
if (n == 0 || n == 1)
return n;
int prev = 0, curr = 1, next = 1;
while (next <= n) {
prev = curr;
curr = next;
next = prev + curr;
}
return curr;
}
void nonNeighbourFibo(int sum) {
while (sum > 0) {
int fibo = fibonacci(sum);
cout << fibo << " ";
sum = sum - fibo;
}
}
int main() {
int sum = 120;
cout << "Sum is same as Non-adjacent Fibonacci terms: ";
nonNeighbourFibo(sum);
return 0;
}आउटपुट
Sum is same as Non-adjacent Fibonacci terms: 89 21 8 2
सत्यापन
89 + 21 + 8 + 2 = 120 ✓ फाइबोनैचि अनुक्रम: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... इस्तेमाल किए गए: 89, 21, 8, 2 (कोई भी आसन्न नहीं) ✓
अधिक उदाहरण
| संख्या | जेकेंडोर्फ प्रतिनिधित्व |
|---|---|
| 10 | 8 + 2 |
| 100 | 89 + 8 + 3 |
| 50 | 34 + 13 + 3 |
| 1000 | 987 + 13 |
ग्रीडी एल्गोरिदम क्यों काम करता है
जेकेंडोर्फ प्रमेय गारंटी देता है कि सबसे बड़ा संभव फाइबोनैचि नंबर चुनने का ग्रीडी दृष्टिकोण हमेशा इष्टतम (और अद्वितीय) प्रतिनिधित्व देता है। यह फाइबोनैचि संख्याओं के गुण से आता है: F(k) = F(k-1) + F(k-2) और F(k) > F(k-1) + F(k-3) + ...
समय जटिलता
O(log n × log n) - प्रत्येक चरण में फाइबोनैचि खोज O(log n) और अधिकतम O(log n) चरण
