Objektif

Diberikan input rdan ntemukan nbilangan asli pertama xsehingga jika kita memutar digit pertama ke tempat terakhir yang kita peroleh x/r.

Anda dapat menganggap itu 2 <= r <= 9dan 1 <= n <= 65535.

Anda dapat menulis sebuah program yang mengambil input dari argumen stdin atau baris perintah; atau Anda dapat menulis fungsi yang mengambil rdan nsebagai parameter. Output, bagaimanapun, harus stdout. Output harus satu baris per nilai x, diformat sebagai x/r=y, dalam urutan meningkat x.

Solusi Anda harus dapat menangani semua kasus yang valid dalam satu menit di komputer desktop yang masuk akal.

Uji kasus

Input: 4 5
Keluaran:

102564/4=25641  
205128/4=51282  
307692/4=76923  
410256/4=102564  
512820/4=128205

Input: 5 1
Keluaran:714285/5=142857

Ini adalah kode-golf, jadi paling tidak byte menang. Jawaban yang menang akan diterima 4 minggu dari sekarang (2014-09-19).

Kredit untuk pertanyaan ini diberikan kepada kolega saya, yang mengizinkan saya untuk mengirim pertanyaan ini di sini :)

Haskell, 182 179

Versi kedua, mungkin golf lebih lanjut, tetapi dengan algoritma "tepat" kali ini. Secara khusus, ini selesai dalam beberapa menit dengan r=4dan n=65535, tapi sekali lagi komputer saya tidak masuk akal atau desktop, jadi kemungkinan ini tetap dalam satu menit pada mesin lain.

n#r=take n$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words

Ini didasarkan pada gagasan bahwa x=10^k*a + m, di mana digit pertama 0≤a≤9dipindahkan ke akhir untuk mendapatkan y=10*m+a. Sebuah matematika sedikit mengungkapkan bahwa mdapat diperoleh sebagai a*(10^k-r)/(10*r-1), jadi kami hanya memindai alebih [1..9]untuk setiap kdari 0 hingga tak terbatas, dan menjaga dan mencetak pertama nhasil yang ekspresi di atas untuk madalah integral.

Hal fromIntegralini diperlukan karena readdaftar dengan nsebagai salah satu elemen dalam main, dalam kombinasi dengan penggunaan ndalam take, akan memaksa runtuk Intkeseluruhan, yang menghasilkan luapan yang tidak menyenangkan dengan jumlah besar yang dipertanyakan. Saya bisa menggunakan genericTake, tetapi itu membutuhkan import.

Kode ini juga memiliki manfaat yang hampir sepele untuk diperluas ke basis selain 10.

Input dibaca dari stdin, dua nilai dapat dipisahkan oleh spasi putih apa pun.

Pure Bash (tidak ada utilitas eksternal), 80 byte

for((;++x,c<$2;));{
y=$[10#${x:1}${x:0:1}]
((y*$1==x))&&echo $x/$1=$y&&((c++))
}

Catatan bash hanya bilangan bulat aritmatika dan bukan floating point, jadi kami memeriksa jika x == y * rbukan x / r == y. Multiplikasi juga seharusnya lebih cepat. Namun, ini belum memenuhi persyaratan kinerja.

Keluaran:

$ ./rotdiv.sh 4 5
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
$ ./rotdiv.sh 5 1
714285/5=142857
$ 

C 468

#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}

(Beberapa baris baru yang tidak dihitung dalam jumlah byte telah ditambahkan di atas untuk menghilangkan bilah gulir. Ya, baris akhir terakhir dihitung.)

Mengharapkan argumen pada baris perintah, dan mengasumsikan output standar menerima ASCII. Runtime adalah O (jumlah byte keluaran) = O (n * n).

Tidak, saya tidak bisa menggunakan printf. Itu membutuhkan terlalu banyak waktu dan mendorong program melebihi batas menit pada desktop saya. Karena itu, beberapa kasus uji memerlukan waktu sekitar 30 detik.

Algoritma memperlakukan output sebagai string, bukan angka, karena mereka dengan cepat menjadi sangat besar, dan ada pola yang kuat dalam output.

Agak tidak terserang:

#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
    for (int i=0; i <= repeats; ++i)
        fputs(num, stdout);
    printf("/%c=", '0'+r);

    /* Assume the repeated num is a solution. Just move the first
       digit and skip any resulting leading zeros. */
    const char* num_tail = num;
    ++num_tail;
    while (*num_tail=='0')
        ++num_tail;
    fputs(num_tail, stdout);
    while (repeats--)
        fputs(num, stdout);
    printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
   decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
    r = atoi(argv[1]);
    int n = atoi(argv[2]);
    int q = 10*r-1;
    int d = 0;

    /* Populate the strings in sol[]. */
    while (d++<9) {
        int p = r*d;
        char* sol_str = sol[d];

        /* Do the long division p/q in decimal, stopping when the remainder
           is the original dividend. The integer part is always zero. */
        do {
            p *= 10;
            *sol_str++ = p/q + '0';
            p %= q;
        } while (p != r*d);
    }

    /* Output the answers. */
    d = 1;
    int repeats = 0;
    int r5x7_repeats = 0;
    while (n--) {
        if (r==5 && r5x7_repeats<6) {
            show_line(x[7], 7*repeats + r5x7_repeats);
        } else {
            if (r==5 && d==7)
                show_line(x[d], 7*repeats + 6);
            else
                show_line(x[d], repeats);
            if (++d > 9) {
                d = 1;
                ++repeats;
                r5x7_repeats = 0;
            }
        }
    }
}

Bukti

bahwa program menyelesaikan masalah:

(Dalam buktinya, anggap semua operator dan fungsi sebagai fungsi matematika yang sebenarnya, bukan operasi komputer yang memperkirakannya. ^Menunjukkan eksponensial, bukan bitwise xor.)

Untuk lebih jelasnya, saya akan menggunakan fungsi ToDecuntuk menggambarkan proses biasa menulis angka sebagai urutan angka desimal. Kisarannya adalah himpunan tupel yang dipesan {0...9}. Sebagai contoh,

ToDec(2014) = (2, 0, 1, 4).

Untuk bilangan bulat positif n, tentukan L(n)menjadi jumlah digit dalam representasi desimal n; atau,

L(n) = 1+floor(log10(n)).

Untuk bilangan bulat positif kdan integer non-negatif ndengan L(n)<k, menentukan Rep_k(n)untuk menjadi nomor nyata diperoleh dengan menambahkan angka nol di depan angka desimal n, jika perlu untuk mendapatkan kangka total, dan kemudian jauh mengulangi mereka kdigit setelah titik desimal. Misalnya

Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...

Mengalikan Rep_k(n) * 10^kmemberi angka nsebelum titik desimal, dan (nol-empuk) angka ndiulang tak terbatas setelah titik desimal. Begitu

Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)

Diberikan bilangan bulat positif r, anggaplah xsolusi untuk masalah, dan

ToDec(x) = ( x_1, x_2, ..., x_k )

dimana x_1 != 0dan k = L(x).

Untuk menjadi solusi, xadalah kelipatan dari r, dan

ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).

Menerapkan Rep_kfungsi memberikan persamaan yang bagus:

10*Rep_k(x) = x_1 + Rep_k(x/r)

Menggunakan formulir tertutup dari atas,

10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)

x_1harus di set {1 ... 9}. rditentukan berada di set {2 ... 9}. Sekarang satu-satunya pertanyaan adalah, untuk nilai apa krumus di atas untuk xmemberikan bilangan bulat positif? Kami akan mempertimbangkan setiap nilai yang mungkin secara rindividual.

Ketika r= 2, 3, 6, 8, atau 9, masing-masing 10r-1adalah 19, 29, 59, 79, atau 89. Dalam semua kasus, penyebutnya p = 10r-1prima. Dalam pembilang, hanya 10^k-1bisa kelipatan p, yang terjadi saat

10^k = 1 (mod p)

Himpunan solusi ditutup dengan penambahan dan pengurangan yang tidak menghasilkan angka negatif. Jadi himpunan terdiri dari semua kelipatan dari beberapa faktor umum, yang juga merupakan solusi paling positif untuk k.

Kapan r = 4dan 10r-1 = 39; atau kapan r = 7dan 10r-1 = 69, penyebutnya 3 kali prima yang berbeda p=(10r-1)/3. 10^k-1selalu merupakan kelipatan 3, dan sekali lagi tidak ada faktor lain dalam pembilang yang bisa kelipatan p, jadi sekali lagi masalahnya berkurang menjadi

10^k = 1 (mod p)

dan sekali lagi solusinya adalah kelipatan dari solusi paling tidak positif untuk k.

[Belum selesai...]

Python - 91 90

Ini foto pertama:

r,n=input();i=1
while n:
 if int(`i`[1:]+`i`[0])*r==i:print'%d/%d=%d'%(i,r,i/r);n-=1
 i+=1

Sunting: Oke, ini mungkin cara lambat untuk memenuhi batas waktu 1 menit yang diperlukan untuk angka 65 ribu.

JavaScript - 145

function f(a,b){for(d=0;d<b;d++)for(i=1;;i++){c=i/a;if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))console.log(i+'/'+a+'='+c)}}

tidak golf:

function f(a,b){
    for(d=0;d<b;d++) //loop for the right amount
        for(i=1;;i++){ //iterating loop
            c=i/a; //actual result of the division
            if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))
                console.log(i+'/'+a+'='+c)
        }
}

Python 3 - 223 179 byte

Implementasi Python dari solusi TheSpanishInquisition:

r,n=map(int,input().split());k=0
while 1:
 for a in range(1,10):
  D,M=divmod(a*(10**k-r),10*r-1)
  if M==0:
   print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
   if n==0:exit()
 k+=1

Lari:

• python3 <whatever you named it>.py
• Mengambil input pada stdin
• Ruang input dipisahkan

Keluaran:

$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128

Temuan:

https://oeis.org/A092697 adalah nilai pertama untuk setiap r.

Tampaknya hanya nilai-nilai k tertentu yang menghasilkan jawaban, dan intervalnya teratur. Misalnya untuk r = 4:

Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]

Intervalnya adalah:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 tampaknya anomali, karena untuk sebagian besar nilai r, ada rumpun 9, 5 membentuk rumpun 9 dan 1 (dengan hanya a = 7 yang bekerja), lihat di bawah)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Formulir ini https://oeis.org/A094224 .

Menggunakan nilai-nilai ini, versi yang lebih efisien dapat dibangun:

import math

def A094224(n):
    return [18,28,6,6,58,22,13,44][n-2]


r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
    for a in range(1,10):
        D,M=divmod(a*10**k-a*r,10*r-1)
        if M==0:
            print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
            if n==0:exit()
    k+=A094224(r)

Namun, saya tidak dapat (belum) membuktikan bahwa ini berlanjut secara matematis.

Hasil untuk r = 5:

0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]