Heim > Backend-Entwicklung > C++ > Die kleinste Anzahl von Einsen in einer wiederholten Zahl

Die kleinste Anzahl von Einsen in einer wiederholten Zahl

PHPz
Freigeben: 2023-09-06 17:21:09
nach vorne
1251 Leute haben es durchsucht

Die kleinste Anzahl von Einsen in einer wiederholten Zahl

Bei diesem Problem müssen wir nur die Zahl 1 in der kleinsten Einheit drucken.

reunit ist eine positive Zahl, wie 11, 111 oder 1111 in der Alltagsmathematik, nur mit der Zahl 1. Die Form der Wiedervereinigung ist $mathrm{(10*n-1)/9}$

Beispiel

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

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

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

Die obige Frage weist darauf hin, dass wir eine beliebige positive ganze Zahl N erhalten, deren Einheitsziffer 3 ist, und wir die kleinste Einheit bestimmen müssen, die durch die gegebene Zahl N teilbar ist.

Zum Beispiel

Wenn wir N=13 geben.

Ausgabe: 6

N, das heißt, 13 ist ein perfekter Teiler von 111111, was uns 8547 ergibt.

111111 ist die kleinste Gewichtseinheit, die durch 13 teilbar ist. Daher beträgt die Anzahl der Einsen in der kleinsten Gewichtseinheit 6, was die gewünschte Ausgabe ergibt.

Algorithmus

Weil wir wissen, dass die Anzahl der Wiederholungen 1, 11, 111, 1111 usw. beträgt. Die anschließende Wiedervereinigung nach x kann als $mathrm{(x*10+1)}$ definiert werden.

Dieser Algorithmus basiert ausschließlich auf dem Konzept, dass, wenn eine ganze Zahl N einen Rest rem hinterlässt, der wiedervereinigte Rest immer $mathrm{(rem*10+1)%N}$ sein wird.

Die Bestimmung der Anzahl der Wiedereinheiten könnte zu mühsam sein, da die Zahl sehr groß sein kann. Daher finden wir die Antwort, indem wir den Rest aktualisieren, bis er 0 wird, und die Anzahl der Einsen bei jedem Aktualisierungsschritt zählen. Die Anzahl der Iterationen, die erforderlich sind, um den Rest auf 0 zu bringen, entspricht der Anzahl der Einsen in der kleinsten Gewichtseinheit.

Hier finden Sie eine Schritt-für-Schritt-Beschreibung des Algorithmus -

  • Schritt 1Deklarieren Sie den Variablenrest als 1, um den Rest jedes N zu speichern iteration und itr sind 1, um die Anzahl der Iterationen zu zählen.

  • Schritt 2Verwenden Sie eine While-Schleife, bis der Rest 0 wird. p>

  • Schritt 3 Aktualisieren Sie bei jedem Schritt den Rest und erhöhen Sie ihn um 1.

  • Schritt 4Sobald der Rest gleich 0 ist, geben Sie itr zurück.

Versuchen wir diesen Ansatz mit N=13.

Weil wir den Rest und den Itr vor der While-Schleife als 1 deklarieren.

Jetzt,

  • In der ersten Iteration beträgt der Rest (Rest*10+1)%N, also 11. Rest=11 und itr=2. Befolgen Sie denselben Algorithmus, bis der Rest 0 wird.

  • Bei Iteration 2 ist Rest=7 und itr=3

  • Bei Iteration 3 ist Rest=6 und itr=4

  • Bei Iteration 4 ist Rest=9 und itr=5

  • Bei Iteration 5 ist Rest=0 und itr=6.

Da der Rest 0 wird, geben wir itr zurück, was 6 ist, was der gewünschten Ausgabe entspricht.

Methode

Das Folgende ist die Implementierung der obigen Methode in 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;
}
Nach dem Login kopieren

Ausgabe

22
Nach dem Login kopieren

Die kleinste durch 23 teilbare Anzahl von Einheiten besteht aus 22 Einsen.

Fazit

Im obigen Artikel haben wir versucht, das Problem zu lösen, die Anzahl der kleinsten Einheiten zu ermitteln, die durch jede positive ganze Zahl N mit einer einzelnen Ziffer von 3 teilbar sind. Ich hoffe, dieser Artikel kann Ihnen helfen, das Konzept dieses Problems zu klären.

Das obige ist der detaillierte Inhalt vonDie kleinste Anzahl von Einsen in einer wiederholten Zahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage