Quelle est la position de n dans le nombre composé de 2, 3, 5 et 7 ?

L'énoncé du problème consiste à imprimer la position de n dans un nombre composé de 2, 3, 5 et 7, où n peut être n'importe quel nombre positif donné par l'utilisateur.

Un nombre composé de 2, 3, 5 et 7 signifie qu'il s'agira d'une séquence de nombres strictement croissante contenant uniquement les nombres 2, 3, 5 ou 7, les quatre premiers nombres premiers. Les premiers nombres de la séquence où tous les nombres ne sont que 2,3,5 et 7 car leurs nombres sont 2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, etc. .

Fondamentalement, chaque nombre de la séquence est une combinaison de ces 4 nombres (c'est-à-dire 2, 3, 5 ou 7) et la séquence est classée par ordre croissant.

Dans cette question, nous recevrons un nombre N dont les chiffres ne sont que 2, 3, 5 et 7, nous devons connaître la position du nombre donné dans la séquence et l'imprimer, ce sera la sortie numérique souhaitée.

Comprenons mieux ce problème avec l'exemple ci-dessous.

INPUT : N=33</p><p>OUTPUT : 10

Explication - Le nombre donné contenant seulement 2, 3, 5 ou 7 en entrée est 33. Dans une séquence numérique comportant uniquement les chiffres 2, 3, 5 ou 7, la position 33 est la 10ème position. Notre résultat est donc 10.

INPUT : 52</p><p>OUTPUT : 13

Explication - Le nombre saisi est 52. Lorsque nous suivons le modèle de la séquence, chaque nombre a 2, 3, 5 ou 7 comme chiffre, et la séquence est strictement par ordre croissant, nous trouvons 52 en position 13. Notre résultat souhaité est donc 13.

Comprenons l'algorithme pour trouver directement la position d'un nombre donné sans créer la séquence entière.

Algorithme

Si nous regardons des séquences de nombres où les nombres ne sont que 2, 3, 5 ou 7, nous verrons que nous ne pouvons former que 4 combinaisons de nombres avec un nombre spécifique. Nous utiliserons cette logique pour déterminer la position d’un nombre N donné.

Les quatre premiers chiffres se situent comme suit :

2 : Première place

3 : Deuxième place

5 : Troisième place

7 : Quatrième place

Puisque la séquence est par ordre croissant, les quatre nombres suivants seront composés de 2 chiffres, le premier nombre étant 2 puisque nous ne pouvons former que 4 nombres avec des nombres spécifiques.

Nous pouvons trouver la position de n'importe quel nombre de chiffres en multipliant la position du premier chiffre à gauche par 4 et en ajoutant la position de ce nombre particulier.

Par exemple, N=52

La position initiale sera 0.

En partant du chiffre de gauche, la position 5 dans la séquence sera la position de position*4+5, soit 0*4+3=3. La position est désormais 3.

Le nombre suivant est 2, donc la position du nombre sera 3*4+1, puisque la position actuelle est 3 fois 4, l'ajout de la position du nombre actuel nous donne la position 13, soit 52 positions dans la séquence de Nombres.

Pour résoudre ce problème, on initialise simplement la position à 0. Continuez ensuite à vérifier chaque numéro jusqu'au dernier chiffre du numéro et mettez à jour la position en conséquence -

Pour le numéro 2, la position sera la position*4+1.

Pour le numéro 3, la position sera la position*4+2.

Pour le chiffre 5, la position sera la position*4+3.

Pour le chiffre 7, la position sera la position*4+4.

Nous mettons à jour la position en multipliant par 4 car pour chaque numéro possible nous ne pouvons faire que 4 combinaisons. Ainsi, chaque fois que nous multiplions la position par 4 et ajoutons la position du nombre actuel, nous obtenons la position du nombre N, qui n'est que 2, 3, 5 ou 7.

Nous utiliserons cet algorithme dans notre approche afin de résoudre le problème efficacement.

Méthode

Étapes à suivre lors de l'implémentation de l'algorithme dans notre méthode pour imprimer la position d'un nombre N composé uniquement de 2, 3, 5 ou 7 -

• Nous allons créer une fonction pour obtenir la position d'un nombre donné qui n'est que 2, 3, 5 ou 7.

• Nous obtiendrons le numéro d'entrée N sous la forme d'une chaîne.

• Donc, de i=0 à i

• Pour le premier cas, si le i-ième nombre est 2, on multipliera cette position par 4 et 1 puisque 1 est la position de 2. De même, nous utiliserons la formule pour calculer la position du nombre jusqu'à la position i en fonction du i-ème chiffre discuté dans la section algorithme.

• À chaque itération, la position est continuellement mise à jour en fonction du i-ième numéro actuel.

• Lorsque nous avons fini de parcourir la chaîne entière, renvoyons la valeur stockée à cet emplacement, qui est la sortie dont nous avons besoin.

Exemple

Code C++ pour cette méthode :

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

//to find the position of the number with only 2,3,5 or 7 as its digits
int position(string N){

   int p=0; //to store the position of the number

   //iterating in a for loop to calculate the position
   for(int i=0;i<N.size();i++){

      if(N[i]=='2'){ 
         //if the digit is 2
         p = p * 4 + 1; 
         //multiplying the position by 4 and adding the position of the digit
      }
      else if(N[i]=='3'){ 
         // if the digit is 3
         p = p * 4 + 2;
      }
      else if(N[i]=='5'){ 
         //if the digit is 5
         p = p * 4 + 3;
      }
      else{ // for the case when digit is 7
         p = p * 4 + 4;
      }
   }

   return p; //return the position of the number N

}
using namespace std;

int main() {
   string N;
   N = "2357";
   //calling the function
   cout<<"The position of "<<N<<" in the sequence is : "<<position(N)<<endl;

   N = "3327";
   cout<<"The position of "<<N<<" in the sequence is : "<<position(N)<<endl;

   return 0;
}

Sortie

The position of 2357 in the sequence is : 112
The position of 3327 in the sequence is : 168

Complexité temporelle - O(n) , où n est la longueur de la chaîne ou le nombre de chiffres du nombre, puisque nous itérons n fois dans la boucle for pour compter le nombre dans la séquence de positions donnée

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire pour résoudre le problème.

Conclusion

Cet article traite de l'algorithme pour trouver la position du nombre N dans une séquence de nombres avec le numéro 2, 3, 5 ou 7, nous avons implémenté cet algorithme dans notre méthode pour résoudre le problème efficacement en temps O(n) C++ sans utiliser tout espace supplémentaire.

J'espère qu'après avoir lu cet article, vous serez en mesure de comprendre ce problème et la manière de le résoudre en utilisant C++.

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!