Écrivez un programme en C++ pour trouver le Nième nombre composé de chiffres impairs

C++ a une énorme liste de fonctions pour résoudre des problèmes mathématiques. L'une des fonctions mathématiques consiste à trouver le Nième nombre impair de chiffres à l'aide d'un code. Cet article décrira la méthode complète pour trouver un nombre impair de chiffres et comprendra ce qu'est un nombre impair et en quoi un nombre est constitué d'un nombre impair de chiffres.

Trouvez le Nième nombre composé de chiffres impairs

Les nombres impairs auront un reste lorsqu'ils sont divisés par 2, donc les premiers nombres impairs sont 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. ..

Pour trouver le nombre recherché, nous avons deux méthodes :

Méthode 1 - Vérifiez chaque nombre naturel pour voir s'il est impair et comptez chaque nombre impair jusqu'à ce que le nombre soit égal à n, s'il est trouvé Si le nombre est pair , alors ne comptez pas, c'est-à-dire sautez les nombres pairs, comptez les nombres impairs et donnez le Nième nombre trouvé.

Cette méthode pour trouver le Nième nombre composé d'un nombre impair de chiffres peut être simple car il suffit de vérifier chaque nombre et de compter les nombres impairs, mais en termes de programmation informatique, cette méthode prend beaucoup de temps pour accomplir cette tâche.

Méthode 2 - Le dernier chiffre de chaque nombre composé de chiffres impairs peut être 1, 3, 5, 7, 9, ce sont donc des nombres impairs. On vérifie donc d'abord si le Nième nombre est 1, 3, 5, 7, 9 et si c'est le cas on obtient la réponse ; sinon on passe à d'autres nombres possibles c'est-à-dire 11, 13, 15, 17, 19 puis 21, 23, 25. , 27, 29. Cela forme un modèle : 1 * 10 + {dernier numéro possible}.

Exemple

Last possible numbers are 1,3,5,7,9
Next possible numbers can be found by
1 * 10 + 1 =11
1 * 10 + 3 = 13
1 * 10 + 5 = 15
1 * 10 + 7 = 17
1* 10 + 9 = 19
i.e 11,13,15,17,19

Exemple de code

Tout d'abord, voyons à quoi ressemble le code -

#include<bits/stdc++.h>
using namespace std;
int main(){
    queue<int> q;
    int cnt = 0, ans = 0;
    int n;
    cin >> n;
    int a[5]={1,3,5,7,9};
    for(int i = 0; i < 5;i++){
        cnt++;
        if(cnt == n)
            ans = a[i];
        q.push(a[i]);
    }
    if(ans)
        cout << ans << "\n";
    else{
        while(true){
            int x = q.front();
            q.pop();
            for(int j = 0; j < 5; j++) {
                int temp = x * 10 + a[j];
                q.push(temp);
                cnt++;
                if(cnt == n)
                    ans = temp;
            }
            if(ans)
                break;
        }
        cout << ans << "\n";
    }
    return 0;
}

Output

9

(Lorsque nous fournissons 5 en entrée, nous obtenons 9 en sortie)

Le code ci-dessus est du code C++ pour trouver le Nième nombre composé uniquement de chiffres impairs. Pour comprendre ce code, décomposons-le et comprenons chaque partie pour comprendre le code complet.

Explication du code

Étape 1 - Obtenez n de l'utilisateur et initialisez les variables requises.

int main() {
   queue<int> q;
   int cnt = 0, ans = 0;
   int n;
   cin >> n;
   int a[5]={1,3,5,7,9};

Ici, nous créons une file d'attente et initialisons les variables cnt pour compter et ans pour stocker les réponses. En même temps, nous utilisons cin pour obtenir les entrées de l'utilisateur et initialiser un tableau avec le premier nombre possible.

Étape 2 - Vérifiez si le Nième numéro fait partie des numéros initiaux possibles et stockez ces numéros dans la file d'attente.

for(int i = 0; i < 5;i++){
   cnt++;
   if(cnt == n)
      ans = a[i];
      q.push(a[i]);
   }
   if(ans)
      cout << ans << "\n";

Dans le code ci-dessus nous vérifions si le Nième numéro est disponible dans le premier numéro possible, le stockons dans le tableau et poussons le numéro présent dans le tableau vers la file d'attente s'il est disponible dans le premier numéro possible Si le Nième numéro est trouvé dans le numéro, alors le résultat est donné

Étape 3 - Trouvez le Nième numéro dans le prochain numéro possible, si le Nième numéro n'est pas trouvé, changez le numéro dans la file d'attente.

while(true) {
   int x = q.front();
   q.pop();
   for(int j = 0; j < 5; j++) {
      int temp = x * 10 + a[j];
      q.push(temp);
      cnt++;
      if(cnt == n)
         ans = temp;
      }
      if(ans)
         break;
   }
   cout << ans << "\n";
}

Enfin, nous retirons chaque numéro de la file d'attente et générons le prochain nombre possible en utilisant la formule { x * 10 + dernier nombre impair } et vérifions si la valeur de cnt est égale à n.

Conclusion

Dans cet article, nous avons eu un problème : comment trouver le Nième nombre impair composé de chiffres impairs, et avons trouvé deux méthodes pour le résoudre. La première méthode est simple, il suffit de vérifier chaque nombre et d’ignorer les nombres pairs, mais le calcul prend plus de temps.

La deuxième méthode consiste à utiliser une file d'attente pour y stocker les nombres impairs et à utiliser la formule ci-dessus pour trouver le prochain nombre possible. La complexité de cette approche est O(n).

Nous avons écrit un programme en C++ pour trouver le Nième nombre composé uniquement de chiffres impairs ; nous pouvons écrire ce programme dans n'importe quel autre langage comme C, Python, Java ou d'autres langages de programmation. J'espère que vous avez trouvé cet article utile pour résoudre votre problème.

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!