Programme C++ pour calculer le nombre minimum d'opérations nécessaires pour changer un nombre n en 1

Supposons que nous ayons un numéro n. Nous effectuons arbitrairement l'une de ces opérations -

• Lorsque n est divisible par 2, remplacez n par n/2

• Lorsque n est divisible par 3, remplacez n par 2n/3

• Lorsque n est divisible par 5, remplacez n par 4n/5

  li>

Il faut calculer le nombre minimum de coups requis pour le chiffre 1. Si ce n'est pas possible, -1 est renvoyé.

Donc, si l'entrée est quelque chose comme n = 10, la sortie sera 4 car l'utilisation de n/2 obtient 5, puis 4n/5 obtient 4, puis n/2 obtient à nouveau 2, et n/2 obtient à nouveau 1.

Étapes

Étapes h2>

Pour résoudre ce problème, nous suivrons les étapes suivantes -

m := 0
while n is not equal to 1, do:
   if n mod 2 is same as 0, then:
      n := n / 2
      (increase m by 1)
   otherwise when n mod 3 is same as 0, then:
      n := n / 3
      m := m + 2
   otherwise when n mod 5 is same as 0, then:
      n := n / 5
      m := m + 3
   Otherwise
      m := -1
      Come out from the loop
return m

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
   int m = 0;
   while (n != 1) {
      if (n % 2 == 0) {
         n = n / 2;
         m++;
      }
      else if (n % 3 == 0) {
         n = n / 3;
         m += 2;
      }
      else if (n % 5 == 0) {
         n = n / 5;
         m += 3;
      }
      else {
         m = -1;
         break;
      }
   }

   return m;
}
int main() {
   int n = 10;
   cout << solve(n) << endl;
}

Input

10

Output

4

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!