给定两个数N和K，找出将N表示为K个斐波那契数之和的方法的数目。 例子 :
null
Input : n = 12, k = 1 Output : 0Input : n = 13, k = 3Output : 2Explanation : 2 + 3 + 8, 3 + 5 + 5.
方法： 斐波那契级数是f（0）=1，f（1）=2，当i>1时，f（i）=f（i-1）+f（i-2）。假设F（x，k，n）是使用F（0），F（1），…F（n-1）中的k个数来形成和x的方法数。要找到F（x，k，n）的重复，请注意有两种情况：F（n-1）是否在和中。
- 如果f（n-1）不在和中， 然后用f（0），f（1），…，f（n-2）中的k个数将x表示为一个和。
- 如果f（n-1）在和中， 然后，剩余的x-f（n-1）是使用f（0）、f（1）、…、f（n-1）中的k-1数字精确地形成的。（请注意，f（n-1）仍然包括在内，因为允许使用重复的数字。）。
因此，递归关系为：
F（x，k，n）=F（x，k，n-1）+F（x-F（n-1），k-1，n）
基本情况：
- 如果k=0，那么级数中有零个数，所以和只能是0。因此，F（0，0，n）=1。
- F（x，0，n）=0，如果x不等于0。
此外，还有其他情况使F（x，k，n）=0，如下所示：
- 如果k>0且x=0，因为至少有一个正数必须导致正和。
- 如果k>0，n=0，因为没有可能的数字选择。
- 如果x<0，因为无法使用有限个非负数形成负数和。
以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // to store fibonacci numbers // 42 second number in fibonacci series // largest possible integer int fib[43] = { 0 }; // Function to generate fibonacci series void fibonacci() { fib[0] = 1; fib[1] = 2; for ( int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } // Recursive function to return the // number of ways int rec( int x, int y, int last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } int sum = 0; // for recursive function call for ( int i = last; i >= 0 and fib[i] * y >= x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } // Driver code int main() { fibonacci(); int n = 13, k = 3; cout << "Possible ways are: " << rec(n, k, 42); return 0; } |
JAVA
//Java implementation of above approach public class AQW { //to store fibonacci numbers //42 second number in fibonacci series //largest possible integer static int fib[] = new int [ 43 ]; //Function to generate fibonacci series static void fibonacci() { fib[ 0 ] = 1 ; fib[ 1 ] = 2 ; for ( int i = 2 ; i < 43 ; i++) fib[i] = fib[i - 1 ] + fib[i - 2 ]; } //Recursive function to return the //number of ways static int rec( int x, int y, int last) { // base condition if (y == 0 ) { if (x == 0 ) return 1 ; return 0 ; } int sum = 0 ; // for recursive function call for ( int i = last; i >= 0 && fib[i] * y >= x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1 , i); } return sum; } //Driver code public static void main(String[] args) { fibonacci(); int n = 13 , k = 3 ; System.out.println( "Possible ways are: " + rec(n, k, 42 )); } } |
Python3
# Python3 implementation of the above approach # To store fibonacci numbers 42 second # number in fibonacci series largest # possible integer fib = [ 0 ] * 43 # Function to generate fibonacci # series def fibonacci(): fib[ 0 ] = 1 fib[ 1 ] = 2 for i in range ( 2 , 43 ): fib[i] = fib[i - 1 ] + fib[i - 2 ] # Recursive function to return the # number of ways def rec(x, y, last): # base condition if y = = 0 : if x = = 0 : return 1 return 0 Sum , i = 0 , last # for recursive function call while i > = 0 and fib[i] * y > = x: if fib[i] > x: i - = 1 continue Sum + = rec(x - fib[i], y - 1 , i) i - = 1 return Sum # Driver code if __name__ = = "__main__" : fibonacci() n, k = 13 , 3 print ( "Possible ways are:" , rec(n, k, 42 )) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of above approach using System; class GFG { // to store fibonacci numbers // 42 second number in fibonacci series // largest possible integer static int [] fib = new int [43]; // Function to generate fibonacci series public static void fibonacci() { fib[0] = 1; fib[1] = 2; for ( int i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } // Recursive function to return the // number of ways public static int rec( int x, int y, int last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } int sum = 0; // for recursive function call for ( int i = last; i >= 0 && fib[i] * y >= x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } // Driver code static void Main() { for ( int i = 0; i < 43; i++) fib[i] = 0; fibonacci(); int n = 13, k = 3; Console.Write( "Possible ways are: " + rec(n, k, 42)); } //This code is contributed by DrRoot_ } |
PHP
<?php // PHP implementation of above approach // To store fibonacci numbers // 42 second number in fibonacci series // largest possible integer $fib = array_fill (0, 43, 0); // Function to generate // fibonacci series function fibonacci() { global $fib ; $fib [0] = 1; $fib [1] = 2; for ( $i = 2; $i < 43; $i ++) $fib [ $i ] = $fib [ $i - 1] + $fib [ $i - 2]; } // Recursive function to return // the number of ways function rec( $x , $y , $last ) { global $fib ; // base condition if ( $y == 0) { if ( $x == 0) return 1; return 0; } $sum = 0; // for recursive function call for ( $i = $last ; $i >= 0 and $fib [ $i ] * $y >= $x ; $i --) { if ( $fib [ $i ] > $x ) continue ; $sum += rec( $x - $fib [ $i ], $y - 1, $i ); } return $sum ; } // Driver code fibonacci(); $n = 13; $k = 3; echo "Possible ways are: " . rec( $n , $k , 42); // This code is contributed by mits ?> |
Javascript
<script> //Javascript implementation of above approach //to store fibonacci numbers //42 second number in fibonacci series //largest possible integer let fib= new Array(43); //Function to generate fibonacci series function fibonacci() { fib[0] = 1; fib[1] = 2; for (let i = 2; i < 43; i++) fib[i] = fib[i - 1] + fib[i - 2]; } //Recursive function to return the //number of ways function rec(x,y,last) { // base condition if (y == 0) { if (x == 0) return 1; return 0; } let sum = 0; // for recursive function call for (let i = last; i >= 0 && fib[i] * y >= x; i--) { if (fib[i] > x) continue ; sum += rec(x - fib[i], y - 1, i); } return sum; } //Driver code fibonacci(); let n = 13, k = 3; document.write( "Possible ways are: " + rec(n, k, 42)); // This code is contributed by rag2127 </script> |
输出：
Possible ways are: 2
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
