GCD 및 피보나치 수열
GfG Practice에서 사용해 보세요. 
#practiceLinkDiv { 표시: 없음 !중요; }
#practiceLinkDiv { 표시: 없음 !중요; } 두 개의 양수 M과 N이 주어졌습니다. 작업은 인쇄하는 것입니다. 최대공약수 M번째와 N번째 피보나치 수열 .
처음 몇 개의 피보나치 수는 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
0은 0번째 피보나치 수로 간주됩니다.
예:
Input : M = 3 N = 6 Output : 2 Fib(3) = 2 Fib(6) = 8 GCD of above two numbers is 2 Input : M = 8 N = 12 Output : 3 Fib(8) = 21 Fib(12) = 144 GCD of above two numbers is 3
에이 간단한 솔루션 아래 단계를 따르는 것입니다.
1) M번째 피보나치 수를 찾아보세요.
2) N번째 피보나치 수를 찾아보세요.
3) 두 숫자의 GCD를 반환합니다.
에이 더 나은 솔루션 아래의 아이덴티티를 기반으로 합니다.
GCD(Fib(M) Fib(N)) = Fib(GCD(M N)) The above property holds because Fibonacci Numbers follow Divisibility Sequence i.e. if M divides N then Fib(M) also divides N. For example Fib(3) = 2 and every third third Fibonacci Number is even. Source : Wiki
단계는 다음과 같습니다.
1) M과 N의 GCD를 구합니다. GCD를 g라고 합니다.
2) Fib(g)를 반환합니다.
다음은 위의 아이디어를 구현한 것입니다.
// C++ Program to find GCD of Fib(M) and Fib(N) #include using namespace std ; const int MAX = 1000 ; // Create an array for memoization int f [ MAX ] = { 0 }; // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ int fib ( int n ) { // Base cases if ( n == 0 ) return 0 ; if ( n == 1 || n == 2 ) return ( f [ n ] = 1 ); // If fib(n) is already computed if ( f [ n ]) return f [ n ]; int k = ( n & 1 ) ? ( n + 1 ) / 2 : n / 2 ; // Applying recursive formula [Note value n&1 is 1 // if n is odd else 0. f [ n ] = ( n & 1 ) ? ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 )) : ( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k ); return f [ n ]; } // Function to return gcd of a and b int gcd ( int M int N ) { if ( M == 0 ) return N ; return gcd ( N % M M ); } // Returns GCD of Fib(M) and Fib(N) int findGCDofFibMFibN ( int M int N ) { return fib ( gcd ( M N )); } // Driver code int main () { int M = 3 N = 12 ; cout < < findGCDofFibMFibN ( M N ); return 0 ; }
C // C Program to find GCD of Fib(M) and Fib(N) #include const int MAX = 1000 ; // Returns n'th Fibonacci number using table arr[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ int fib ( int n ) { // Create an array for memoization int arr [ MAX ]; for ( int i = 0 ; i < MAX ; i ++ ) arr [ i ] = 0 ; // Base cases if ( n == 0 ) return 0 ; if ( n == 1 || n == 2 ) return ( arr [ n ] = 1 ); // If fib(n) is already computed if ( arr [ n ]) return arr [ n ]; int k = ( n & 1 ) ? ( n + 1 ) / 2 : n / 2 ; // Applying recursive formula [Note value n&1 is 1 // if n is odd else 0. arr [ n ] = ( n & 1 ) ? ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 )) : ( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k ); return arr [ n ]; } // Function to return gcd of a and b int gcd ( int M int N ) { if ( M == 0 ) return N ; return gcd ( N % M M ); } // Returns GCD of Fib(M) and Fib(N) int findGCDofFibMFibN ( int M int N ) { return fib ( gcd ( M N )); } // Driver code int main () { int M = 3 N = 12 ; printf ( '%d' findGCDofFibMFibN ( M N )); return 0 ; } // This code is contributed by Aditya Kumar (adityakumar129)
Java // Java Program to find GCD of Fib(M) and Fib(N) class gcdOfFibonacci { static final int MAX = 1000 ; static int [] f ; gcdOfFibonacci () // Constructor { // Create an array for memoization f = new int [ MAX ] ; } // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ private static int fib ( int n ) { // Base cases if ( n == 0 ) return 0 ; if ( n == 1 || n == 2 ) return ( f [ n ] = 1 ); // If fib(n) is already computed if ( f [ n ]!= 0 ) return f [ n ] ; int k = (( n & 1 ) == 1 ) ? ( n + 1 ) / 2 : n / 2 ; // Applying recursive formula [Note value n&1 is 1 // if n is odd else 0. f [ n ] = (( n & 1 ) == 1 ) ? ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 )) : ( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k ); return f [ n ] ; } // Function to return gcd of a and b private static int gcd ( int M int N ) { if ( M == 0 ) return N ; return gcd ( N % M M ); } // This method returns GCD of Fib(M) and Fib(N) static int findGCDofFibMFibN ( int M int N ) { return fib ( gcd ( M N )); } // Driver method public static void main ( String [] args ) { // Returns GCD of Fib(M) and Fib(N) gcdOfFibonacci obj = new gcdOfFibonacci (); int M = 3 N = 12 ; System . out . println ( findGCDofFibMFibN ( M N )); } } // This code is contributed by Pankaj Kumar
Python3 # Python Program to find # GCD of Fib(M) and Fib(N) MAX = 1000 # Create an array for memoization f = [ 0 for i in range ( MAX )] # Returns n'th Fibonacci # number using table f[]. # Refer method 6 of below # post for details. # https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ def fib ( n ): # Base cases if ( n == 0 ): return 0 if ( n == 1 or n == 2 ): f [ n ] = 1 # If fib(n) is already computed if ( f [ n ]): return f [ n ] k = ( n + 1 ) // 2 if ( n & 1 ) else n // 2 # Applying recursive # formula [Note value n&1 is 1 # if n is odd else 0. f [ n ] = ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 )) if ( n & 1 ) else (( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k )) return f [ n ] # Function to return # gcd of a and b def gcd ( M N ): if ( M == 0 ): return N return gcd ( N % M M ) # Returns GCD of # Fib(M) and Fib(N) def findGCDofFibMFibN ( M N ): return fib ( gcd ( M N )) # Driver code M = 3 N = 12 print ( findGCDofFibMFibN ( M N )) # This code is contributed # by Anant Agarwal.
C# // C# Program to find GCD of // Fib(M) and Fib(N) using System ; class gcdOfFibonacci { static int MAX = 1000 ; static int [] f ; // Constructor gcdOfFibonacci () { // Create an array // for memoization f = new int [ MAX ]; } // Returns n'th Fibonacci number // using table f[]. Refer method // 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ private static int fib ( int n ) { // Base cases if ( n == 0 ) return 0 ; if ( n == 1 || n == 2 ) return ( f [ n ] = 1 ); // If fib(n) is // already computed if ( f [ n ] != 0 ) return f [ n ]; int k = (( n & 1 ) == 1 ) ? ( n + 1 ) / 2 : n / 2 ; // Applying recursive formula // [Note value n&1 is 1 // if n is odd else 0. f [ n ] = (( n & 1 ) == 1 ) ? ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 )) : ( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k ); return f [ n ]; } // Function to return gcd of a and b private static int gcd ( int M int N ) { if ( M == 0 ) return N ; return gcd ( N % M M ); } // This method returns GCD of // Fib(M) and Fib(N) static int findGCDofFibMFibN ( int M int N ) { return fib ( gcd ( M N )); } // Driver method public static void Main () { // Returns GCD of Fib(M) and Fib(N) new gcdOfFibonacci (); int M = 3 N = 12 ; Console . Write ( findGCDofFibMFibN ( M N )); } } // This code is contributed by nitin mittal.
PHP // PHP Program to find // GCD of Fib(M) and Fib(N) $MAX = 1000 ; // Create an array for memoization $f = array_fill ( 0 $MAX 0 ); // Returns n'th Fibonacci number // using table f[]. Refer method // 6 of below post for details. function fib ( $n ) { global $f ; // Base cases if ( $n == 0 ) return 0 ; if ( $n == 1 or $n == 2 ) $f [ $n ] = 1 ; // If fib(n) is already computed if ( $f [ $n ]) return $f [ $n ]; $k = ( $n & 1 ) ? ( $n + 1 ) / 2 : $n / 2 ; // Applying recursive formula [Note // value n&1 is 1 if n is odd else 0. $f [ $n ] = ( $n & 1 ) ? ( fib ( $k ) * fib ( $k ) + fib ( $k - 1 ) * fib ( $k - 1 )) : (( 2 * fib ( $k - 1 ) + fib ( $k )) * fib ( $k )); return $f [ $n ]; } // Function to return gcd of a and b function gcd ( $M $N ) { if ( $M == 0 ) return $N ; return gcd ( $N % $M $M ); } // Returns GCD of Fib(M) and Fib(N) function findGCDofFibMFibN ( $M $N ) { return fib ( gcd ( $M $N )); } // Driver code $M = 3 ; $N = 12 ; print ( findGCDofFibMFibN ( $M $N )) // This code is contributed // by mits ?>
JavaScript < script > // JavaScript Program to find GCD of Fib(M) and Fib(N) const MAX = 1000 ; // Create an array for memoization var f = [... Array ( MAX )]; f . fill ( 0 ); // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. // https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/ function fib ( n ) { // Base cases if ( n == 0 ) return 0 ; if ( n == 1 || n == 2 ) return ( f [ n ] = 1 ); // If fib(n) is already computed if ( f [ n ]) return f [ n ]; var k = n & 1 ? ( n + 1 ) / 2 : n / 2 ; // Applying recursive formula [Note value n&1 is 1 // if n is odd else 0. f [ n ] = n & 1 ? fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 ) : ( 2 * fib ( k - 1 ) + fib ( k )) * fib ( k ); return f [ n ]; } // Function to return gcd of a and b function gcd ( M N ) { if ( M == 0 ) return N ; return gcd ( N % M M ); } // Returns GCD of Fib(M) and Fib(N) function findGCDofFibMFibN ( M N ) { return fib ( gcd ( M N )); } // Driver code var M = 3 N = 12 ; document . write ( findGCDofFibMFibN ( M N )); // This code is contributed by rdtank. < /script>
산출:
2
