给定一个正整数 N .任务是找出将N表示为1和2之和的方法的数量。 例如：
null
Input : N = 3Output : 33 can be represented as (1+1+1), (2+1), (1+2).Input : N = 5Output : 8
对于N=1，答案是1。 对于N=2。（1+1），（2），答案是2。 对于N=3。（1+1+1），（2+1），（1+2），答案是3。 对于N=4。（1+1+1+1），（2+1+1），（1+2+1），（1+1+2），（2+2）答案是5。 等等 可以观察到它的形成 斐波那契级数 .因此，将N表示为1和2之和的方法的数量是（N+1） th 斐波那契数。 怎样 我们可以很容易地看到递归函数与斐波那契数完全相同。为了得到N的和，我们可以把1加到N–1中。此外，我们可以在N–2中添加2。只允许1和2来求和N。所以，要用1和2来求和N，总的方法是：求和的方法数（N-1）+求和的方法数（N-2）。 我们可以在O（logn）时间内找到第N个斐波那契数。请参考第5种方法 这 邮递 以下是该方法的实施情况：
C++
// C++ program to find number of ways to representing // a number as a sum of 1's and 2's #include <bits/stdc++.h> using namespace std; // Function to multiply matrix. void multiply( int F[2][2], int M[2][2]) { int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Power function in log n void power( int F[2][2], int n) { if ( n == 0 || n == 1) return ; int M[2][2] = {{1,1},{1,0}}; power(F, n/2); multiply(F, F); if (n%2 != 0) multiply(F, M); } /* function that returns (n+1)th Fibonacci number Or number of ways to represent n as sum of 1's 2's */ int countWays( int n) { int F[2][2] = {{1,1},{1,0}}; if (n == 0) return 0; power(F, n); return F[0][0]; } // Driver program int main() { int n = 5; cout << countWays(n) << endl; return 0; } |
JAVA
// Java program to find number of // ways to representing a number // as a sum of 1's and 2's class GFG { // Function to multiply matrix. static void multiply( int F[][], int M[][]) { int x = F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ]; int y = F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ]; int z = F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ]; int w = F[ 1 ][ 0 ] * M[ 0 ][ 1 ] + F[ 1 ][ 1 ] * M[ 1 ][ 1 ]; F[ 0 ][ 0 ] = x; F[ 0 ][ 1 ] = y; F[ 1 ][ 0 ] = z; F[ 1 ][ 1 ] = w; } // Power function in log n static void power( int F[][], int n) { if (n == 0 || n == 1 ) { return ; } int M[][] = {{ 1 , 1 }, { 1 , 0 }}; power(F, n / 2 ); multiply(F, F); if (n % 2 != 0 ) { multiply(F, M); } } /* function that returns (n+1)th Fibonacci number Or number of ways to represent n as sum of 1's 2's */ static int countWays( int n) { int F[][] = {{ 1 , 1 }, { 1 , 0 }}; if (n == 0 ) { return 0 ; } power(F, n); return F[ 0 ][ 0 ]; } // Driver program public static void main(String[] args) { int n = 5 ; System.out.println(countWays(n)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to find number of ways to # representing a number as a sum of 1's and 2's # Function to multiply matrix. def multiply(F, M): x = F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ] y = F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ] z = F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ] w = F[ 1 ][ 0 ] * M[ 0 ][ 1 ] + F[ 1 ][ 1 ] * M[ 1 ][ 1 ] F[ 0 ][ 0 ] = x F[ 0 ][ 1 ] = y F[ 1 ][ 0 ] = z F[ 1 ][ 1 ] = w # Power function in log n def power(F, n): if ( n = = 0 or n = = 1 ): return M = [[ 1 , 1 ],[ 1 , 0 ]] power(F, n / / 2 ) multiply(F, F) if (n % 2 ! = 0 ): multiply(F, M) #/* function that returns (n+1)th Fibonacci number # Or number of ways to represent n as sum of 1's # 2's */ def countWays(n): F = [[ 1 , 1 ], [ 1 , 0 ]] if (n = = 0 ): return 0 power(F, n) return F[ 0 ][ 0 ] # Driver Code n = 5 print (countWays(n)) # This code is contributed by mohit kumar |
C#
// C# program to find number of // ways to representing a number // as a sum of 1's and 2's class GFG { // Function to multiply matrix. static void multiply( int [,]F, int [,]M) { int x = F[0,0] * M[0,0] + F[0,1] * M[1,0]; int y = F[0,0] * M[0,1] + F[0,1] * M[1,1]; int z = F[1,0] * M[0,0] + F[1,1] * M[1,0]; int w = F[1,0] * M[0,1] + F[1,1] * M[1,1]; F[0,0] = x; F[0,1] = y; F[1,0] = z; F[1,1] = w; } // Power function in log n static void power( int [,]F, int n) { if (n == 0 || n == 1) { return ; } int [,]M = {{1, 1}, {1, 0}}; power(F, n / 2); multiply(F, F); if (n % 2 != 0) { multiply(F, M); } } /* function that returns (n+1)th Fibonacci number Or number of ways to represent n as sum of 1's 2's */ static int countWays( int n) { int [,]F = {{1, 1}, {1, 0}}; if (n == 0) { return 0; } power(F, n); return F[0,0]; } // Driver program public static void Main() { int n = 5; System.Console.WriteLine(countWays(n)); } } // This code contributed by mits |
Javascript
<script> // Javascript program to find number of // ways to representing a number // as a sum of 1's and 2's // Function to multiply matrix. function multiply(F , M) { var x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; var y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; var z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; var w = F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Power function in log n function power(F , n) { if (n == 0 || n == 1) { return ; } var M = [[1, 1], [1, 0]]; power(F, parseInt(n / 2)); multiply(F, F); if (n % 2 != 0) { multiply(F, M); } } /* function that returns (n+1)th Fibonacci number Or number of ways to represent n as sum of 1's 2's */ function countWays(n) { var F = [[1, 1], [1, 0]]; if (n == 0) { return 0; } power(F, n); return F[0][0]; } // Driver program var n = 5; document.write(countWays(n)); // This code is contributed by 29AjayKumar </script> |
输出：
8
时间复杂性： O（logn）。 本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
