Reduzieren Sie in C++ eine Zahl auf 1, indem Sie die angegebene Operation ausführen

Gegeben ist eine ganze Zahl als Eingabe. Das Ziel besteht darin, die Mindestanzahl an Schritten oder Operationen zu finden, die erforderlich sind, um die Eingabezahl auf 1 zu reduzieren. Die ausführbaren Operationen wären:

• Wenn die Zahl gerade ist, dividiere sie durch 2.

• Wenn die Zahl ungerade ist, erhöhen oder verringern Sie sie um 1.

  ?

14 ist eine gerade Zahl – dividiere durch 2 = 7

7 ist eine ungerade Zahl – dividiere durch 1 = 8

8 ist eine gerade Zahl – dividiere durch 2 = 4

4 ist eine gerade Zahl – dividiere durch 2 = 2

2 ist eine gerade Zahl – dividiere durch 2 = 1

Eingabe − Zahl = 9

Ausgabe

− Mindestschritte, um 9 auf 1 zu reduzieren: 4

Erklärung

-

9 ist ungerade – subtrahiere 1 = 8

8 ist gerade – dividiere Nimm 2 = 4

4 ist eine gerade Zahl – dividiere durch 2 = 2

2 ist eine gerade Zahl – dividiere durch 2 = 1

Die im folgenden Programm verwendete Methode ist wie folgt:

2 ist eine gerade Zahl – dividiere durch 2 = 1 h2> Bei dieser Methode wird eine rekursive Methode verwendet, um die Mindestoperationen zu überprüfen, die erforderlich sind, um die Zahl auf 1 zu reduzieren. Minimale Möglichkeit, rekursiv nach Zahl+1 oder Zahl-1 (je nachdem, welcher Wert kleiner ist) zu suchen, auch wenn es sich nur um eine einfache Division durch 2 handelt.

Behandeln Sie die eingegebene Zahl als Ganzzahl.

Funktion minWays(int num) verwendet num als Eingabe und gibt die minimale Anzahl von Operationen zurück, die erforderlich sind, um num auf 1 zu reduzieren.

Nehmen Sie die Variablen tmp1, tmp2 und min als ganze Zahlen.

Wenn num 0 ist, wird 1 zurückgegeben.

• Wenn num%2==0 eine gerade Zahl ist, setzen Sie num=num/2

• Wenn num eine ungerade Zahl ist, setzen Sie tmp1=minWays(num-1) und tmp2=minWays(num+1 ).

• Setzen Sie min auf den Mindestwert von tmp1 und tmp2.

• Rückfahrt 1+Min.
• Am Ende werden wir die Ergebnisse bekommen, die wir wollen.

• Drucken Sie die Ergebnisse im Hauptteil aus.

• Beispiel

  #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;
  }

  Ausgabe
• Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

  Minimum steps to reduce 21 to 1: 6

Das obige ist der detaillierte Inhalt vonReduzieren Sie in C++ eine Zahl auf 1, indem Sie die angegebene Operation ausführen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!