Vérifier si un numéro est un numéro de Munchhausen

Le nombre de Munchhausen est un nombre impair doté de propriétés uniques. Un nombre est considéré comme un nombre de Munchhausen si la somme de ses chiffres (ses puissances) est égale au nombre d'origine. Ces chiffres sont rares et beaucoup d’entre eux sont inconnus. Si la définition 00 = 0 est utilisée, alors 0 peut également être considéré comme le nombre de Munchhausen.

L'article suivant fournit un moyen de déterminer si un nombre est un nombre de Munchhausen, en gardant à l'esprit ces caractéristiques des nombres de Munchhausen.

Énoncé du problème

La tâche actuelle consiste à vérifier si un entier n donné est un nombre de Münchhausen, c'est-à-dire que lorsque chaque nombre est élevé à sa propre puissance et additionné, le résultat est égal au nombre d'origine. S'il s'agit d'un numéro de Münchhausen, le programme doit renvoyer vrai, sinon il doit renvoyer faux.

Exemple

Input: 1
Output: True

Explication - (1 à la puissance 1) = 11 = 1.

Puisque le nombre obtenu est égal au nombre d'origine, 1 est le nombre de Munchhausen.

Input: 1603
Output: False

Explication − (1 à la puissance 1) + (6 à la puissance 6) + (0 à la puissance 0) + (3 à la puissance 3) = 11 + 6⁶ + 0⁰ + 3³ ≠ 1603.

Cela équivaut à 46684. Puisque le nombre obtenu n’est pas égal au nombre d’origine, 1603 n’est pas un nombre de Munchhausen.

Input: 3435
Output: True

Explication − (3 à la puissance 3) + (4 à la puissance 4) + (3 à la puissance 3) + (5 à la puissance 5) = 33 + 4⁴ + 3³ + 5⁵ = 3435.

Puisque le nombre obtenu est égal au nombre d'origine, 3435 est le nombre de Munchhausen.

Input: 4335
Output: False

Explication − (4 à la puissance 4) + (3 à la puissance 3) + (3 à la puissance 3) + (5 à la puissance 5) = 4⁴ + 3³ + 3³ + 5⁵ ≠ 4335.

Puisque le nombre obtenu n'est pas égal au nombre d'origine, 4335 n'est pas un numéro de Munich.

Méthode de solution

Afin de savoir si le numéro fourni est un numéro de Münchhausen, nous devons savoir si le résultat de l'ajout de chaque numéro à lui-même est le même que le numéro d'origine. Vous pouvez utiliser les méthodes suivantes pour calculer la somme et déterminer si le résultat correspond au nombre d'origine.

Algorithme

La méthode comprend les étapes suivantes -

• Divisez le numéro donné en ses chiffres individuels.

• Élevez chaque numéro vers lui-même.

• Ajouter des résultats.

• Comparez la somme au nombre d'origine.

• Afficher les réponses.

pseudocode

Fonction is_munchhausen()

• Initialiser la somme = 0

• Initialiser temp = n

• simultanément (température > 0)

  Initialiser le chiffre = temp % 10

  somme = somme + pow(nombre, nombre)

  Température=Température/10

• Somme de retour ==n

Fonction principale()

• Initialiser n

• si (is_munchhausen())

  cout

• Autres

  cout

• Impression

Exemple : programme C++

Le programme détermine si un numéro est un numéro de Münchhausen en appelant la fonction is_munchhausen(). Cette fonction utilise une variable temporaire égale à n et une autre variable somme pour stocker la somme des résultats de chaque nombre additionnés sur lui-même.

À chaque itération de la boucle, utilisez l'opérateur « % » pour accéder à chaque chiffre de la température. Il renvoie le chiffre le plus à droite du nombre. Ce nombre est ensuite augmenté et ajouté au total. A la fin de chaque itération, temp est divisé par 10 pour accéder au numéro suivant. La boucle s'exécute jusqu'à ce que temp > 0.

// C++ code for Münchhausen Number
#include <iostream>
#include <cmath>

using namespace std;
// this function is used to check out whether the given number is Münchhausen Number or not
bool is_munchhausen(int n){
   int sum = 0;
   int temp = n;
   while (temp > 0){
      int digit = temp % 10; //yields the rightmost digit as remainder
      sum = sum + pow(digit, digit);
      temp = temp / 10; // yields the remaining number
   }
   return (sum == n); // returns true if sum is equal to original number
}
// Driver Code
int main(){
   int n = 3253;
   cout << "input number: " << n << endl;
   if (is_munchhausen(n)){
      cout << "Münchhausen Number" << endl;
   } else {
      cout << "Non-Münchhausen Number" << endl;
   }
   return 0;
}

Sortie

input number: 3253
Non-Münchhausen Number

Analyse de la complexité temporelle et spatiale

Time Complexity - O (log n) complexité temporelle, où n est la valeur du paramètre d'entrée. En effet, le nombre d'itérations de la boucle while dans la fonction is_munchhausen() dépend du nombre de chiffres du nombre donné, qui est proportionnel à log(n) base 10. Cette fonction n'est appelée qu'une seule fois dans la fonction principale, la complexité globale du programme est donc proportionnelle à log(n).

Complexité spatiale - O(1). Cette fonction utilise une mémoire fixe pour stocker les variables entières sum et temp, de sorte que sa complexité spatiale est constante quelle que soit la taille des arguments d'entrée.

Conclusion

Pour résumer, un nombre de Münchhausen est un nombre unique exprimé comme la somme de ses propres nombres. Ils ne sont pas courants et les trouver peut être une tâche difficile. La solution discutée dans cet article fournit un moyen de vérifier facilement si un nombre est Münchhausen en temps logarithmique sans utiliser d'espace auxiliaire. Cet article explique en profondeur le concept de nombre de Munchhausen à l'aide de divers exemples. Utilisez le code C++ inclus pour déterminer rapidement si un nombre donné est un nombre de Münchhausen.

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!