Finden Sie das Polynom

20

Wir wissen, dass f ein Polynom mit nicht negativen ganzzahligen Koeffizienten ist.

Gegeben f (1) und f (1 + f (1)) geben f zurück . Sie können f als eine Liste von Koeffizienten, ein ASCII-formatiertes Polynom oder ähnliches ausgeben .

Beispiele:

f(1)  f(1+f(1))  f
0     0          0
1     1          1
5     75         2x^2 + 3
30    3904800    4x^4 + 7x^3 + 2x^2 + 8x + 9
1     1073741824 x^30
orlp
quelle
1
Zufällige Frage: Ich bin zu müde, um dies jetzt zu beweisen / zu widerlegen, aber ist garantiert, dass wir immer eine Antwort von f(1)und erhalten können f(1+f(1))?
HyperNeutrino
4
@HyperNeutrino Ich hätte diese Herausforderung sonst nicht gemacht.
Orlp
Richtig, das ist ein guter Punkt. Hm. Interessant, ich werde versuchen, das morgen zu beweisen, denn das ist sehr interessant. Danke für die interessante Herausforderung!
HyperNeutrino
1
Das Base-Conversion- Tag soll ein Hinweis sein?
Thunda
9
So sehr dies ein niedliches Puzzle ist, denke ich, dass der Code im Grunde eine Basisumwandlung ist. Möglicherweise betrogen?
30.

Antworten:

27

Gelee , 3 Bytes

‘b@

Probieren Sie es online!

Gibt das Polynom als Liste von Koeffizienten zurück.

Da wir wissen, dass das Polynom nicht negative ganzzahlige Koeffizienten hat, kann f (b) durch die Definition einer Basis als "die Koeffizienten des Polynoms, die als Stellen der Basis b genommen werden" interpretiert werden . Dies unterliegt der Bedingung, dass keiner der Koeffizienten b überschreitet oder gleich ist , aber wir wissen, dass b um eins größer ist als die Summe der Koeffizienten (die f (1) ist ).

Das Programm inkrementiert einfach das erste Argument ( ), um 1 + f (1) zu erhalten , und ruft dann das Basisumwandlungsatom ( b) mit dem ersten Argument als Basis und dem zweiten Argument als Zahl auf (wobei @die Reihenfolge der Argumente vertauscht wird). da in der bRegel die Nummer zuerst und die Basis Sekunde nimmt).

Dies war eine ziemlich clevere Herausforderung. danke orlp!

Türknauf
quelle
13
Wie um
alles
Ich muss Gelee lernen ...
sagiksp
Dennis muss das unbedingt sehen.
Erik der Outgolfer
6

Mathematica, 29 28 Bytes

Vielen Dank an JungHwan Min für das Speichern von 1 Byte! (ironischerweise mit a Max)

#2~IntegerDigits~Max[#+1,2]&

Reine Funktion, die zwei nichtnegative Ganzzahlen verwendet und eine Liste von (nichtnegativen Ganzzahl-) Koeffizienten zurückgibt. #2~IntegerDigits~(#+1)wäre der gleiche Algorithmus wie in Doorknobs Gelee-Antwort ; Leider IntegerDigitsdrosselt Mathematica, wenn die Basis gleich 1 ist, weshalb zusätzliche Bytes erforderlich sind Max[...,2].

Greg Martin
quelle
2
Haha, schön.
JungHwan Min
4

Python 2 , 38 Bytes

a,b=input()
while b:print b%-~a;b/=a+1

Probieren Sie es online!


gibt durch Zeilenumbruch getrennte Koeffizienten aus

Beispielausgabe für 30, 3904800:

9
8
2
7
4

=> 9*x^0 + 8*x^1 + 2*x^2 + 7*x^3 + 4*x^4

ovs
quelle
3

VBA, 75 Bytes

Sub f(b,n)
b=b+1
Do While n>0
s=n Mod b &" " &s
n=n\b
Loop
Debug.?s
End Sub

Wenn es automatisch formatiert wird, sieht es so aus:

Sub f(b, n)
    b = b + 1
    Do While n > 0
        s = n Mod b & " " & s
        n = n \ b
    Loop
    Debug.Print s
End Sub

Der \Betreiber ist eine Bodenteilung

Ingenieur Toast
quelle
1

AHK , 63 Bytes

a=%1%
b=%2%
a+=1
While b>0
{s:=Mod(b,a) " "s
b:=b//a
}
Send,%s%

AutoHotkey weist den eingehenden Parametern die Nummern 1-n als Variablennamen zu. Es verursacht einige Probleme, wenn Sie versuchen, diese in Funktionen zu verwenden, da es denkt, dass Sie die Literalzahl 1 anstelle der Variablen mit dem Namen 1 bedeuten . Die beste Lösung, die ich finden kann, besteht darin, sie verschiedenen Variablen zuzuweisen.

Ingenieur Toast
quelle
1

Java, 53 Bytes

a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}

Gibt eine Liste von Koeffizienten aus. Vielen Dank an Ovs für die Mathematik.

Der Ausdruck muss a zugewiesen Function<Integer, IntConsumer>und aufgerufen werden, indem zuerst applydie Funktion und dann acceptdie int. Für Java 9 sind keine Importe erforderlich jshell:

C:\Users\daico>jshell
|  Welcome to JShell -- Version 9-ea
|  For an introduction type: /help intro

jshell> Function<Integer, IntConsumer> golf =
        a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}
golf ==> $Lambda$14/13326370@4b9e13df

jshell> golf.apply(30).accept(3904800)
9
8
2
7
4
David Conrad
quelle
1

Common Lisp, 87 Bytes

(defun p(x y)(multiple-value-bind(q m)(floor y (1+ x))(if(= 0 q)`(,m)`(,m ,@(p x q)))))

Ungolfed:

(defun find-polynomial (f<1> f<1+f<1>>)
  (multiple-value-bind (q m)
      (floor f<1+f<1>> (1+ f<1>))
    (if (zerop q) `(,m)
      (cons m (find-polynomial f<1> q)))))
zelcon
quelle
0

C #, 62 Bytes

(a,b)=>{var r="";a++;while(b>0){r+=(b%a)+" ";b/=a;}return r;};
CHENGLIANG YE
quelle