Nombor terkecil 1 dalam nombor berulang

Dalam masalah ini, kita hanya perlu mencetak nombor 1 dalam unit terkecil.

reunit ialah nombor positif, seperti 11, 111 atau 1111 dalam matematik kasual, hanya dengan nombor 1. Bentuk penyatuan semula ialah $mathrm{(10*n-1)/9}$

Contoh

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

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

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

Soalan di atas menunjukkan bahawa kita diberi sebarang integer positif N yang digit unitnya ialah 3, dan kita perlu menentukan unit terkecil yang boleh dibahagi dengan nombor N yang diberikan.

Sebagai contoh,

Jika kita berikan N=13.

Output: 6

N, iaitu 13 ialah pembahagi sempurna bagi 111111 yang memberi kita 8547.

111111 ialah unit berat terkecil yang boleh dibahagi dengan 13. Oleh itu, bilangan 1 dalam unit berat terkecil ialah 6, memberikan output yang diingini.

Algoritma

Sebab kita tahu bilangan ulangan ialah 1, 11, 111, 1111, dll. Penyatuan semula seterusnya selepas x boleh ditakrifkan sebagai $mathrm{(x*10+1)}$.

Algoritma ini hanya berdasarkan konsep bahawa jika integer N meninggalkan baki rem, maka baki yang disatukan semula akan sentiasa $mathrm{(rem*10+1)%N}$.

Menentukan bilangan unit semula mungkin terlalu membosankan kerana bilangannya boleh menjadi sangat besar, jadi kami akan mencari jawapannya dengan mengemas kini baki sehingga ia menjadi 0 dan mengira nombor 1 dengan setiap langkah kemas kini. Bilangan lelaran yang diperlukan untuk mendapatkan baki 0 ​​akan menjadi bilangan 1 dalam unit berat terkecil.

Berikut ialah penerangan langkah demi langkah algoritma -

• Langkah 1− Isytihar baki pembolehubah sebagai 1 untuk menyimpan baki setiap N lelaran dan itr ialah 1 untuk mengira bilangan lelaran.

• Langkah 2− Gunakan gelung sementara sehingga bakinya menjadi 0. p>

• Langkah 3 − Setiap langkah, kemas kini baki dan tingkatkan itr 1.

• Langkah 4−Setelah bakinya bersamaan dengan 0, kembalikan itr.

Mari cuba pendekatan ini dengan N=13.

Kerana kami mengisytiharkan baki dan itr sebagai 1 sebelum gelung while.

Sekarang,

• Dalam lelaran pertama, bakinya ialah (baki*10+1)%N, iaitu 11. Baki=11 dan itr=2. Ikuti algoritma yang sama sehingga bakinya menjadi 0.

• Pada lelaran 2, baki=7 dan itr=3

• Pada lelaran 3, baki=6 dan itr=4

• Pada lelaran 4, baki=9 dan itr=5

• Pada lelaran 5, baki=0 dan itr=6.

Oleh kerana bakinya menjadi 0, kami akan mengembalikan itr, iaitu 6, iaitu output yang diingini.

Kaedah

Berikut adalah pelaksanaan kaedah di atas dalam 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;
}

Output

22

Bilangan terkecil unit yang boleh dibahagi dengan 23 akan terdiri daripada 22 unit.

Kesimpulan

Dalam artikel di atas, kami cuba menyelesaikan masalah mencari bilangan unit terkecil yang boleh dibahagi dengan mana-mana integer positif N dengan satu digit 3. Harap artikel ini dapat membantu anda menjelaskan konsep masalah ini.

Atas ialah kandungan terperinci Nombor terkecil 1 dalam nombor berulang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!