Zielsetzung

Geben Sie die Eingabe ein rund nfinden Sie die ersten nnatürlichen Zahlen xso, dass wir erhalten, wenn wir die erste Ziffer an die letzte Stelle drehen x/r.

Sie können davon ausgehen, dass 2 <= r <= 9und 1 <= n <= 65535.

Sie können ein Programm schreiben, das Eingaben von stdin- oder Befehlszeilenargumenten entgegennimmt. oder Sie können eine Funktion schreiben, die rund nals Parameter verwendet. Die Ausgabe sollte jedoch zu stdout sein. Die Ausgabe sollte eine Zeile pro Wert von sein x, formatiert als x/r=y, in der Reihenfolge der Erhöhung x.

Ihre Lösung muss in der Lage sein, alle gültigen Fälle innerhalb einer Minute auf einem vernünftigen Desktop-Computer zu bearbeiten.

Testfälle

Eingabe: 4 5
Ausgabe:

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

Eingabe: 5 1
Ausgabe:714285/5=142857

Dies ist Code-Golf, also gewinnen die wenigsten Bytes. Die Gewinnerantwort wird in 4 Wochen (19.09.2014) angenommen.

Credits für diese Frage gehen an meinen Kollegen, der mir erlaubt hat, diese Frage hier zu posten :)

Haskell, 182 179

Zweite Version, wahrscheinlich weiter golfbar, aber diesmal mit "richtigem" Algorithmus. Insbesondere endet es innerhalb weniger Minuten mit r=4und n=65535, aber andererseits ist mein Computer weder vernünftig noch ein Desktop, so dass die Wahrscheinlichkeit besteht, dass dies auf anderen Computern innerhalb einer Minute bleibt.

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

Es basiert auf der Idee, dass x=10^k*a + m, wo seine erste Ziffer 0≤a≤9zum Ende verschoben wird, um zu erhalten y=10*m+a. Eine wenig Mathematik zeigt , dass mkann , wie sie erhalten werden a*(10^k-r)/(10*r-1), so dass wir einfach scannen aüber [1..9]für alle kvon 0 bis unendlich, und halten und die ersten nDruckergebnisse , für die der obige Ausdruck für mintegral ist.

Das fromIntegralist erforderlich , weil reading eine Liste mit nals eines ihrer Elementen in main, in Kombination mit der Verwendung von nin take, zwingen würde , rzu Intganzen, was zu bösen überläuft mit den großen Zahlen in Frage. Ich hätte verwenden können genericTake, aber das erfordert eine import.

Dieser Code hat auch den Vorteil, dass er fast trivial ist, um auf andere Basen als 10 erweitert zu werden.

Die Eingabe wird gelesen stdin, die beiden Werte können durch ein beliebiges Leerzeichen getrennt werden.

Pure Bash (keine externen Dienstprogramme), 80 Byte

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

Beachten Sie, dass bash nur Ganzzahlarithmetik und kein Gleitkomma ausführt. Wir prüfen daher, ob x == y * ranstelle von x / r == y. Auch die Multiplikation sollte im Allgemeinen schneller sein. Dies entspricht jedoch bei weitem nicht den Leistungsanforderungen.

Ausgabe:

$ ./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);}}

(Einige Zeilenumbrüche, die nicht in der Byteanzahl gezählt wurden, wurden oben hinzugefügt, um Bildlaufleisten zu entfernen. Ja, die letzte Zeilenumbruch wird gezählt.)

Erwartet Argumente in der Befehlszeile und geht davon aus, dass die Standardausgabe ASCII akzeptiert. Die Laufzeit ist O (Anzahl der ausgegebenen Bytes) = O (n * n).

Nein, ich kann nicht verwenden printf. Das dauert zu lange und schiebt das Programm über das Minutenlimit auf meinem Desktop. Einige Testfälle dauern ungefähr 30 Sekunden.

Der Algorithmus behandelt die Ausgabe als Zeichenfolgen und nicht als Zahlen, da sie schnell enorm werden und die Ausgabe starke Muster enthält.

Etwas ungolf:

#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;
            }
        }
    }
}

Beweis

dass das Programm das Problem löst:

(Nehmen Sie im Beweis, dass alle Operatoren und Funktionen die realen mathematischen Funktionen sind, nicht die Computeroperationen, die sie approximieren. ^Bezeichnet Exponentiation, nicht bitweises xor.)

Aus Gründen der Klarheit werde ich eine Funktion verwenden ToDec, um den normalen Vorgang des Schreibens einer Zahl als Folge von Dezimalstellen zu beschreiben. Seine Reichweite ist die Menge der bestellten Tupel auf {0...9}. Beispielsweise,

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

nDefinieren Sie für eine positive Ganzzahl L(n)die Anzahl der Stellen in der Dezimaldarstellung von n; oder,

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

Definieren Sie für eine positive Ganzzahl kund eine nicht negative Ganzzahl nmit die reelle Zahl, die durch Hinzufügen von Nullen vor den Dezimalstellen von , falls erforderlich, um die Gesamtzahl der Stellen zu erhalten , und anschließende unendliche Wiederholung dieser Stellen nach dem Dezimalpunkt erhalten wird. Z.BL(n)<kRep_k(n)nkk

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

Beim Multiplizieren werden Rep_k(n) * 10^kdie Ziffern nvor dem Dezimalpunkt und die (mit Nullen aufgefüllten) Ziffern nnach dem Dezimalpunkt unendlich wiederholt. So

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

rAngenommen, eine positive ganze Zahl xist eine Lösung für das Problem, und

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

wo x_1 != 0und k = L(x).

Eine Lösung zu sein, xist ein Vielfaches von rund

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

Das Anwenden der Rep_kFunktion ergibt eine schöne Gleichung:

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

Mit seiner geschlossenen Form von oben,

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

x_1muss im Set sein {1 ... 9}. rwurde angegeben, um im Satz zu sein {2 ... 9}. Die Frage ist nun nur, für welche Werte kdie obige Formel xeine positive ganze Zahl ergibt. Wir werden jeden möglichen Wert reinzeln betrachten.

Wenn r= 2, 3, 6, 8 oder 9 ist, 10r-1ist 19, 29, 59, 79 bzw. 89. In allen Fällen ist der Nenner p = 10r-1Primzahl. Im Zähler 10^k-1kann nur ein Vielfaches von sein p, was passiert, wenn

10^k = 1 (mod p)

Der Satz von Lösungen wird unter Addition und unter Subtraktion geschlossen, was nicht zu einer negativen Zahl führt. Die Menge umfasst also alle Vielfachen eines gemeinsamen Faktors, was auch die am wenigsten positive Lösung für ist k.

Wann r = 4und 10r-1 = 39; oder wann r = 7und 10r-1 = 69, der Nenner ist dreimal eine andere Primzahl p=(10r-1)/3. 10^k-1ist immer ein Vielfaches von 3, und wieder kann kein anderer Faktor im Zähler ein Vielfaches von sein p, so dass sich das Problem wieder auf reduziert

10^k = 1 (mod p)

und wieder sind die Lösungen alle Vielfachen der am wenigsten positiven Lösung für k.

[Nicht beendet...]

Python - 91 90

Hier ist ein erster Schuss:

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

Bearbeiten: Ok, es ist wahrscheinlich viel zu langsam, um das erforderliche 1-Minuten-Zeitlimit für 65K-Nummern einzuhalten.

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)}}

nicht golfen:

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 Bytes

Python-Implementierung der Lösung von 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

Lauf:

• python3 <whatever you named it>.py
• Nimmt Eingaben auf stdin vor
• Eingaberaum getrennt

Ausgabe:

$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

Ergebnisse:

https://oeis.org/A092697 ist der erste Wert für jedes r.

Es scheint, dass nur bestimmte Werte von k Antworten liefern und dass das Intervall regelmäßig ist. ZB für 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]

Die Intervalle sind:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 scheint eine Anomalie zu sein, da es für die meisten Werte von r Klumpen von 9 gibt, 5 Klumpen von 9 und 1 bilden (wobei nur a = 7 funktioniert), siehe unten)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Dies bildet https://oeis.org/A094224 .

Mit diesen Werten kann eine effizientere Version erstellt werden:

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)

Ich kann jedoch (noch) nicht beweisen, dass dies mathematisch weitergeht.

Ergebnisse für 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]