Zeckendorf定理（非相邻斐波那契表示）-yiteyi-C++库

泽肯多夫定理声明每个正整数可以唯一地写为不同的非相邻斐波那契数之和。如果两个斐波那契数在斐波那契序列（0，1，1，2，3，5，…）中一个接一个，那么它们就是邻居。例如，3和5是邻居，但2和5不是邻居。

null

给定一个数，找出一个表示为非连续斐波那契数之和的数。

例如：

Input:  n = 10Output: 8 28 and 2 are two non-consecutive Fibonacci Numbersand sum of them is 10.Input:  n = 30Output: 21 8 121, 8 and 1 are non-consecutive Fibonacci Numbersand sum of them is 30.

我们强烈建议您尽量减少浏览器，并先自己尝试。 这个想法是使用贪婪算法 .

1) Let n be input number2) While n >= 0     a) Find the greatest Fibonacci Number smaller than n.        Let this number be 'f'.  Print 'f'     b) n = n - f

C++

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

JAVA

                         // Java program for Zeckendorf's theorem. It finds                       
                         // representation of n as sum of non-neighbouring                       
                         // Fibonacci Numbers.                       
                         class                                     GFG {                       
                                                 public                                     static                                     int                                     nearestSmallerEqFib(                                     int                                     n)                       
                                                 {                       
                                                 // Corner cases                       
                                                 if                                     (n ==                                     0                                     || n ==                                     1                                     )                       
                                                 return                                     n;                       
           
                                                 // Find the greatest Fibonacci Number smaller                       
                                                 // than n.                       
                                                 int                                     f1 =                                     0                                     , f2 =                                     1                                     , f3 =                                     1                                     ;                       
                                                 while                                     (f3 <= n) {                       
                                                 f1 = f2;                       
                                                 f2 = f3;                       
                                                 f3 = f1 + f2;                       
                                                 }                       
                                                 return                                     f2;                       
                                                 }                       
           
                                                 // Prints Fibonacci Representation of n using                       
                                                 // greedy algorithm                       
                                                 public                                     static                                     void                                     printFibRepresntation(                                     int                                     n)                       
                                                 {                       
                                                 while                                     (n >                                     0                                     ) {                       
                                                 // Find the greates Fibonacci Number smaller                       
                                                 // than or equal to n                       
                                                 int                                     f = nearestSmallerEqFib(n);                       
           
                                                 // Print the found fibonacci number                       
                                                 System.out.print(f +                                     " "                                     );                       
           
                                                 // Reduce n                       
                                                 n = n - f;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method to test                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     30                                     ;                       
                                                 System.out.println(                                     "Non-neighbouring Fibonacci "                       
                                                 +                                     " Representation of "                                     + n +                                     " is"                                     );                       
           
                                                 printFibRepresntation(n);                       
                                                 }                       
                         }                       
           
                         // Code Contributed by Mohit Gupta_OMG                       

Python3

                         # Python 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.                       
                         def                                     nearestSmallerEqFib(n):                       
                                   
                                                 # Corner cases                       
                                                 if                                     (n                                     =                                     =                                     0                                     or                                     n                                     =                                     =                                     1                                     ):                       
                                                 return                                     n                       
                                   
                                                 # Finds the greatest Fibonacci Number smaller                       
                                                 # than n.                       
                                                 f1, f2, f3                                     =                                     0                                     ,                                     1                                     ,                                     1                       
                                                 while                                     (f3 <                                     =                                     n):                       
                                                 f1                                     =                                     f2;                       
                                                 f2                                     =                                     f3;                       
                                                 f3                                     =                                     f1                                     +                                     f2;                       
                                                 return                                     f2;                       
           
           
                         # Prints Fibonacci Representation of n using                       
                         # greedy algorithm                       
                         def                                     printFibRepresntation(n):                       
                                   
                                                 while                                     (n>                                     0                                     ):                       
           
                                                 # Find the greates Fibonacci Number smaller                       
                                                 # than or equal to n                       
                                                 f                                     =                                     nearestSmallerEqFib(n);                       
                                   
                                                 # Print the found fibonacci number                       
                                                 print                                     (f,end                                     =                                     " "                                     )                       
                                   
                                                 # Reduce n                       
                                                 n                                     =                                     n                                     -                                     f                       
           
                         # Driver code test above functions                       
                         n                                     =                                     30                       
                         print                                     (                                     "Non-neighbouring Fibonacci Representation of"                                     , n,                                     "is"                                     )                       
                         printFibRepresntation(n)                       

C#

                         // C# program for Zeckendorf's theorem.                       
                         // It finds the representation of n as                       
                         // sum of non-neighbouring  Fibonacci                       
                         // Numbers.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                                 public                                     static                                     int                                     nearestSmallerEqFib(                                     int                                     n)                       
                                                 {                       
                                                 // Corner cases                       
                                                 if                                     (n == 0 || n == 1)                       
                                                 return                                     n;                       
           
                                                 // Find the greatest Fibonacci                       
                                                 // Number smaller than n.                       
                                                 int                                     f1 = 0, f2 = 1, f3 = 1;                       
                                                 while                                     (f3 <= n) {                       
                                                 f1 = f2;                       
                                                 f2 = f3;                       
                                                 f3 = f1 + f2;                       
                                                 }                       
                                                 return                                     f2;                       
                                                 }                       
           
                                                 // Prints Fibonacci Representation                       
                                                 // of n using greedy algorithm                       
                                                 public                                     static                                     void                                     printFibRepresntation(                                     int                                     n)                       
                                                 {                       
                                                 while                                     (n > 0) {                       
                                                 // Find the greates Fibonacci                       
                                                 // Number smallerthan or equal                       
                                                 // to n                       
                                                 int                                     f = nearestSmallerEqFib(n);                       
           
                                                 // Print the found fibonacci number                       
                                                 Console.Write(f +                                     " "                                     );                       
           
                                                 // Reduce n                       
                                                 n = n - f;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 40;                       
                                                 Console.WriteLine(                                     "Non-neighbouring Fibonacci "                       
                                                 +                                     " Representation of "                                     + n +                                     " is"                                     );                       
           
                                                 printFibRepresntation(n);                       
                                                 }                       
                         }                       
           
                         // Code Contributed by vt_m                       

PHP

                         <?php                       
                         // PHP 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.                       
                         function                                     nearestSmallerEqFib(                                     $n                                     )                       
                         {                       
                                   
                                                 // Corner cases                       
                                                 if                                     (                                     $n                                     == 0 ||                                     $n                                     ==1)                       
                                                 return                                     $n                                     ;                       
           
                                                 // Find the greatest Fibonacci                       
                                                 // Number smaller than n.                       
                                                 $f1                                     = 0;                       
                                                 $f2                                     = 1;                       
                                                 $f3                                     = 1;                       
                                                 while                                     (                                     $f3                                     <=                                     $n                                     )                       
                                                 {                       
                                                 $f1                                     =                                     $f2                                     ;                       
                                                 $f2                                     =                                     $f3                                     ;                       
                                                 $f3                                     =                                     $f1                                     +                                     $f2                                     ;                       
                                                 }                       
                                                 return                                     $f2                                     ;                       
                         }                       
           
                         // Prints Fibonacci Representation                       
                         // of n using greedy algorithm                       
                         function                                     printFibRepresntation(                                     $n                                     )                       
                         {                       
                                                 while                                     (                                     $n                                     > 0)                       
                                                 {                       
                                   
                                                 // Find the greates Fibonacci                       
                                                 // Number smaller than or                       
                                                 // equal to n                       
                                                 $f                                     = nearestSmallerEqFib(                                     $n                                     );                       
           
                                                 // Print the found                       
                                                 // fibonacci number                       
                                                 echo                                     $f                                     ,                                     " "                                     ;                       
           
                                                 // Reduce n                       
                                                 $n                                     =                                     $n                                     -                                     $f                                     ;                       
                                                 }                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 30;                       
                                                 echo                                     "Non-neighbouring Fibonacci Representation of "                                     ,                       
                                                 $n                                     ,                                     " is "                                     ;                       
                                                 printFibRepresntation(                                     $n                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript 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.                       
                         function                                     nearestSmallerEqFib(n)                       
                         {                       
                                   
                                                 // Corner cases                       
                                                 if                                     (n == 0 || n==1)                       
                                                 return                                     n;                       
           
                                                 // Find the greatest Fibonacci                       
                                                 // Number smaller than n.                       
                                                 let f1 = 0;                       
                                                 let f2 = 1;                       
                                                 let f3 = 1;                       
                                                 while                                     (f3 <= n)                       
                                                 {                       
                                                 f1 = f2;                       
                                                 f2 = f3;                       
                                                 f3 = f1 + f2;                       
                                                 }                       
                                                 return                                     f2;                       
                         }                       
           
                         // Prints Fibonacci Representation                       
                         // of n using greedy algorithm                       
                         function                                     printFibRepresntation(n)                       
                         {                       
                                                 while                                     (n > 0)                       
                                                 {                       
                                   
                                                 // Find the greates Fibonacci                       
                                                 // Number smaller than or                       
                                                 // equal to n                       
                                                 let f = nearestSmallerEqFib(n);                       
           
                                                 // Print the found                       
                                                 // fibonacci number                       
                                                 document.write(f,                                     " "                                     );                       
           
                                                 // Reduce n                       
                                                 n = n - f;                       
                                                 }                       
                         }                       
           
                                                 // Driver Code                       
                                                 let n = 30;                       
                                                 document.write(                                     "Non-neighbouring Fibonacci Representation of "                                     +                       
                                                 n +                                     " is <br>"                                     );                       
                                                 printFibRepresntation(n);                       
           
                         // This code is contributed by _saurabh_jaiswal                       
                         </script>                       

输出

Non-neighbouring Fibonacci Representation of 30 is 21 8 1

时间复杂性： O（N*LogN）

上述贪婪算法是如何工作的？ 设小于或等于‘n’的最大斐波那契数为fib（i）【第i个斐波那契数】。然后n–fib（i）将有它自己的表示，作为非相邻Fibonacci数的和。我们只想确保附近没有问题。通过归纳，n-fib（i）不存在邻近问题，那么n可能存在邻近问题的唯一方法是，如果n-fib（i）在其表示中使用fib（i-1）。所以我们需要进一步证明的是，n-fib（i）在其表示中没有使用fib（i-1）让我们用矛盾来证明它。如果n-fib（i）=fib（i-1）+fib（i-x）+……，那么fib（i）不能是与n最近的最小斐波那契数，因为fib（i）+fib（i-1）本身就是fib（i+1）。因此，如果n-fib（i）在其表示中包含fib（i-1），那么fib（i+1）将更接近于n的较小fib数，这与我们的假设相矛盾，即fib（i）是最接近于n的较小fib数。

这种表述有用吗？ 比如二进制表示。这可以是表示正数的替代表示法。关于这种表示法的一个重要观察结果是，斐波那契表示法中的1的数量往往比二进制表示法中的1的数量少得多。因此，如果在存储1比存储0更昂贵的应用程序中，使用斐波那契表示法是有意义的。本文由 高拉夫·萨克塞纳 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章