En C++, réduire un nombre à 1 en effectuant l'opération donnée

Étant donné un entier en entrée. L'objectif est de trouver le nombre minimum d'étapes ou d'opérations nécessaires pour réduire le nombre d'entrée à 1. Les opérations pouvant être effectuées seraient - :

• Si le nombre est pair, divisez-le par 2.

• Si le nombre est impair, incrémentez-le ou décrémentez-le de 1.

Exemple

Entrée− Nombre = 28

Sortie− Étapes minimales pour réduire 28 à 1 : 6

Explication−

28 est un nombre pair - diviser par 2 = 14

14 est un nombre pair - diviser par 2 = 7

7 est un nombre impair - diviser par 1 = 8

8 est un nombre pair - diviser par 2 = 4

4 est un nombre pair - diviser par 2 = 2

2 est un nombre pair - diviser par 2 = 1

Entrée − Nombre = 9

Sortie − Étapes minimales pour réduire 9 à 1 : 4

Explication -

9 est impair - soustraire 1 = 8

8 est pair - diviser Prendre 2 = 4

4 est un nombre pair - diviser par 2 = 2

2 est un nombre pair - diviser par 2 = 1

La méthode utilisée dans le programme suivant est comme suit

2 est un nombre pair - diviser par 2 = 1 h2>

Dans cette méthode, une méthode récursive est utilisée pour vérifier les opérations minimales requises pour réduire le nombre à 1. Moyen minimal de vérifier récursivement le numéro + 1 ou le numéro-1 (selon le plus petit des deux) s'il s'agit même d'une simple division par 2.

• Traitez le nombre saisi comme un entier.

• La fonction minWays(int num) prend num comme entrée et renvoie le nombre minimum d'opérations requises pour réduire num à 1.

• Prenez les variables tmp1, tmp2 et min sous forme d'entiers.

• Si num est 0, renvoie 1.

• Si num%2==0 est un nombre pair, définissez num=num/2

• Si num est un nombre impair, définissez tmp1=minWays(num-1) et tmp2=minWays(num+1 ).

• Définissez min comme étant la valeur minimale de tmp1 et tmp2.

• Retour 1+min.

• En fin de compte, nous obtiendrons les résultats que nous souhaitons.

• Imprimez les résultats en principal.

Exemple

#include <iostream>
using namespace std;
int minWays(int num){
   int tmp1,tmp2,min;
   if (num == 1){
      return 0;
   }
   else if (num % 2 == 0){
      tmp1=minWays(num/2);
      return (1 + tmp1);
   }
   else{
      int tmp1=minWays(num - 1);
      int tmp2=minWays(num + 1);
      int min=tmp1<tmp2?tmp1:tmp2;
      return (1 + min);
   }
}
int main(){
   int Number = 21;
   cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
   return 0;
}

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Minimum steps to reduce 21 to 1: 6

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!