Zeckendorf 's Theorem (Non | C ++ program for Zeckendorf 's theorem. It finds representation of n as sum of non-neighbouring Fibonacci Numbers. ; Returns the greatest Fibonacci Number smaller than or equal to n . ; Corner cases ; Find the greatest Fibonacci Number smaller than n . ; Prints Fibonacci Representation of n using greedy algorithm ; Find the greates Fibonacci Number smaller than or equal to n ; Print the found fibonacci number ; Reduce n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int nearestSmallerEqFib ( int n ) { if ( n == 0 n == 1 ) return n ; int f1 = 0 , f2 = 1 , f3 = 1 ; while ( f3 <= n ) { f1 = f2 ; f2 = f3 ; f3 = f1 + f2 ; } return f2 ; } void printFibRepresntation ( int n ) { while ( n > 0 ) { int f = nearestSmallerEqFib ( n ) ; cout << f << " ▁ " ; n = n - f ; } } int main ( ) { int n = 30 ; cout << " Non - neighbouring ▁ Fibonacci ▁ Representation ▁ of ▁ " << n << " ▁ is ▁ STRNEWLINE " ; printFibRepresntation ( n ) ; return 0 ; }