Numéros PGCD et Fibonacci
Essayez-le sur GfG Practice 
#practiceLinkDiv { display : aucun !important; }
#practiceLinkDiv { display : aucun !important; } plus grand diviseur commun du M et du N Numéros de Fibonacci .
Les premiers nombres de Fibonacci sont 0 1 1 2 3 5 8 13 21 34 55 89 144 ....
Notez que 0 est considéré comme le 0ème nombre de Fibonacci.
Exemples :
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
UN Solution simple est de suivre les étapes ci-dessous.
1) Trouvez le M'ème numéro de Fibonacci.
2) Trouvez le Nième numéro de Fibonacci.
3) Renvoie le GCD de deux nombres.
UN Meilleure solution est basé sur l'identité ci-dessous
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
Les étapes sont les suivantes :
1) Trouvez le PGCD de M et N. Soit GCD égal à g.
2) Renvoyez Fib(g).
Vous trouverez ci-dessous les implémentations de l'idée ci-dessus.
// 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>
Sortir:
2
