Convertissez un nombre m en n avec un minimum d'opérations. Les opérations autorisées sont :
- Multipliez par 2, c'est-à-dire faites m = 2 * m
- Soustraire 1, c'est-à-dire faire m = m - 1
Imprimez -1 s'il n'est pas possible de convertir.
Exemples :
Input : m = 3 n = 11 Output : 3 1st operation: *2 = 3*2 = 6 2nd operation: *2 = 6*2 = 12 3rd operation: -1 = 12-1 = 11 Input : m = 15 n = 20 Output : 6 1st operation: -1 '5' times = 15 + (-1*5) = 10 2nd operation: *2 = 10*2 = 20 Input : m = 0 n = 8 Output : -1 Using the given set of operations 'm' cannot be converted to 'n' Input : m = 12 n = 8 Output : 4
L'idée est basée sur les faits ci-dessous.
1) Si m est inférieur à 0 et n est supérieur à 0, alors ce n'est pas possible.
2) Si m est supérieur à n alors nous pouvons atteindre n en utilisant uniquement des soustractions.
3) Sinon (m est inférieur à n), nous devons effectuer m*2 opérations. Deux cas suivants se présentent.
......a) Si n est impair nous devons faire une opération -1 pour l'atteindre.
......b) Si n est pair il faut faire une opération *2 pour l'atteindre.
Algorithme:
int convert(mn) if (m == n) return 0; // not possible if (m <= 0 && n > 0) return -1; // m is greater than n if (m > n) return m-n; // n is odd if (n % 2 == 1) // perform '-1' return 1 + convert(m n+1); // n is even else // perform '*2' return 1 + convert(m n/2);
Note: La liste des opérations ainsi générée doit être appliquée dans l'ordre inverse.
Par exemple:
m = 3 n = 11 convert(311) | --> n is odd: operation '-1' convert(312) | --> n is even: operation '*2' convert(36) | --> n is even: operation '*2' convert(33) | --> m == n return Therefore the sequence of operations is '*2' '*2' '-1'.
// C++ implementation to convert // a number m to n using minimum // number of given operations #include
// Java implementation to convert // a number m to n using minimum // number of given operations class ConvertNum { // function to find minimum // number of given operations // to convert m to n static int convert(int m int n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver Code public static void main (String[] args) { int m = 3 n = 11; System.out.println('Minimum number of ' + 'operations : ' + convert(m n)); } }
# Python implementation to convert # a number m to n using minimum # number of given operations # Function to find minimum # number of given operations # to convert m to n def convert(m n): if(m == n): return 0 # only way is to do # -1(m - n): times if(m > n): return m - n # not possible if(m <= 0 and n > 0): return -1 # n is greater and n is odd if(n % 2 == 1): # perform '-1' on m #(or +1 on n): return 1 + convert(m n + 1) # n is even else: # perform '*2' on m #(or n/2 on n): return 1 + convert(m n / 2) # Driver code m = 3 n = 11 print('Minimum number of operations :' convert(m n)) # This code is contributed by # Sanjit_Prasad
// C# implementation to convert // a number m to n using minimum // number of given operations using System; class GFG { // function to find minimum // number of given operations // to convert m to n static int convert(int m int n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver code public static void Main () { int m = 3 n = 11; Console.Write('Minimum number of ' + 'operations : ' + convert(m n)); } } // This code is contributed by nitin mittal
// PHP implementation to convert // a number m to n using minimum // number of given operations // Function to find minimum // number of given operations // to convert m to n function convert($m $n) { if ($m == $n) return 0; // only way is to do // -1 (m - n) times if ($m > $n) return $m - $n; // not possible if ($m <= 0 && $n > 0) return -1; // n is greater and n is odd if ($n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert($m $n + 1); // n is even else // perform '*2' on m // (or n/2 on n) return 1 + convert($m $n / 2); } // Driver code { $m = 3; $n = 11; echo 'Minimum number of '. 'operations : ' convert($m $n); return 0; } // This code is contributed // by nitin mittal. ?> <script> // javascript implementation to convert // a number m to n using minimum // number of given operations // function to find minimum // number of given operations // to convert m to n function convert(m n) { if (m == n) return 0; // only way is to do // -1 (m - n) times if (m > n) return m - n; // not possible if (m <= 0 && n > 0) return -1; // n is greater and n is odd if (n % 2 == 1) // perform '-1' on m // (or +1 on n) return 1 + convert(m n + 1); // n is even else // perform '*2' on m // (or n / 2 on n) return 1 + convert(m n / 2); } // Driver Code var m = 3 n = 11; document.write('Minimum number of ' + 'operations : ' + convert(m n)); // This code is contributed by Princi Singh </script>
Sortir :
Minimum number of operations : 3
Références :
https://www.queryhome.com/tech/112705/convert-number-with-minimum-operations-operations-allowed