Le plus petit nombre de 1 dans un nombre répété

Dans ce problème, il suffit d'imprimer le chiffre 1 dans la plus petite unité.

la réunification est un nombre positif, comme 11, 111 ou 1111 en mathématiques simples, uniquement avec le chiffre 1. La forme de réunion est $mathrm{(10*n-1)/9}$

Exemple

$mathrm{(10*10-1)/9}$ donne 11.

$mathrm{(10*100-1)/9}$ donne 111.

$mathrm{(10*1000-1)/9}$ donne 1111.

La question ci-dessus souligne que l'on nous donne tout entier positif N dont le chiffre unitaire est 3, et que nous devons déterminer la plus petite unité qui peut être divisible par le nombre N donné.

Par exemple,

Si on donne N=13.

Sortie : 6

N, c'est-à-dire que 13 est un diviseur parfait de 111111 ce qui nous donne 8547.

111111 est la plus petite unité de poids divisible par 13. Par conséquent, le nombre de 1 dans la plus petite unité de poids est 6, ce qui donne le résultat souhaité.

Algorithme

Parce que nous savons que le nombre de répétitions est 1, 11, 111, 1111, etc. La réunion ultérieure après x peut être définie comme $mathrm{(x*10+1)}$.

Cet algorithme est basé uniquement sur le concept selon lequel si un entier N laisse un reste rem, alors le reste réuni sera toujours $mathrm{(rem*10+1)%N}$.

Déterminer le nombre de réunions peut être trop fastidieux car le nombre peut être très grand, nous trouverons donc la réponse en mettant à jour le reste jusqu'à ce qu'il devienne 0 et en comptant le nombre de 1 à chaque étape de mise à jour. Le nombre d'itérations nécessaires pour amener le reste à 0 sera le nombre de 1 dans la plus petite unité de poids.

Voici une description étape par étape de l'algorithme -

• Étape 1− Déclarez le reste de la variable comme 1 pour stocker le reste de chaque N itération et itr valent 1 pour compter le nombre d'itérations.

• Étape 2− Utilisez une boucle while jusqu'à ce que le reste devienne 0. p>

• Étape 3 − À chaque étape, mettez à jour le reste et augmentez-le de 1.

• Étape 4−Une fois le reste égal à 0, renvoyez itr.

Essayons cette approche avec N=13.

Parce que nous déclarons le reste et itr comme 1 avant la boucle while.

Maintenant,

• Dans la 1ère itération, le reste sera (reste*10+1)%N, soit 11. Reste=11 et itr=2. Suivez le même algorithme jusqu'à ce que le reste devienne 0.

• À l'itération 2, reste=7 et itr=3

• À l'itération 3, reste=6 et itr=4

• À l'itération 4, reste=9 et itr=5

• À l'itération 5, reste=0 et itr=6.

Puisque le reste devient 0, nous renverrons itr, qui vaut 6, ce qui est le résultat souhaité.

Méthode

Ce qui suit est l'implémentation de la méthode ci-dessus en C++ -

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

//function to calculate no of ones in smallest repunit
int numberOfones(int N){  
   int remainder=1;
   
   int itr=1; // to store no of iterations
   
   while(remainder!=0){
      //update remainder
      remainder=(remainder*10 + 1)% N;
   
      itr++; //increase itr by 1 to get number of 1's in repunit
   }
   
   return itr;
}
int main(){
   int N=23;
   cout<<numberOfones(N);
   return 0;
}

Sortie

22

Le plus petit nombre d'unités divisible par 23 sera composé de 22 unités.

Conclusion

Dans l'article ci-dessus, nous avons essayé de résoudre le problème de trouver le nombre de plus petites unités pouvant être divisibles par n'importe quel entier positif N avec un seul chiffre de 3. J'espère que cet article pourra vous aider à clarifier le concept de ce 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!