Fibonacci produkte

13

Sie können eine Zahl größer als 0 als eindeutige Summe positiver Fibonacci-Zahlen zerlegen. In dieser Frage subtrahieren wir wiederholt die größtmögliche positive Fibonacci-Zahl. Z.B:

1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3

Nun nenne ich ein Fibonacci-Produkt die gleichen Listen wie oben, aber mit dem Zusatz, der durch Multiplikation ersetzt wird. Zum Beispiel f(100) = 89 * 8 * 3 = 2136.

Schreiben Sie ein Programm oder eine Funktion, die bei einer positiven Ganzzahl n das Fibonacci-Produkt dieser Zahl zurückgibt.


Testfälle:

1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236
orlp
quelle
6
Die Aussage ist nicht ganz richtig. ZB 2kann zerlegt werden als -1 + 3. Die korrekte Aussage des Satzes von Zeckendorf lautet, dass eine positive Fibonacci-Zahl eindeutig als Summe nicht aufeinanderfolgender Fibonacci-Zahlen mit positivem Index zerlegt werden kann.
Peter Taylor
1
@PeterTaylor Ich betrachte negative Fibonacci-Zahlen für diese Frage nicht als Teil der Serie. Aufeinanderfolgend oder nicht nur dann, wenn Sie die Indizes möchten, kümmern wir uns nicht um die Indizes für diese Frage.
Orlp
1
Ich sage nicht, dass Sie die Frage ändern sollten, um negative Fibonacci-Zahlen zu unterstützen: Ich sage, dass Sie sie so bearbeiten sollten, dass sie explizit die Annahmen widerspiegeln, die Sie treffen.
Peter Taylor
1
@orlp aufeinanderfolgend oder nicht wichtig, da zwei verschiedene Formen zwei verschiedene Produkte ergeben würden. Sie haben das Problem bereits in einer Weise angegeben, die konsekutive Fibonacci-Begriffe implizit ausschließt, sodass es dort keinen Grund zur Sorge gibt.
Hobbs
2
(Insbesondere: F (n) und F (n + 1) können nicht beide in der Ausgabe erscheinen, da der Algorithmus garantiert, dass der Rest, bevor er berücksichtigt wird, bereits kleiner als F (n + 2) = F (n) + ist F (n + 1))
hobbs

Antworten:

5

Jelly , 16 15 Bytes

Rf1+С¤ṪạµÐĿIAP

Nicht besonders schnell oder speicherfreundlich, aber effizient genug für alle Testfälle. Probieren Sie es online!

Wie es funktioniert

Rf1+С¤ṪạµÐĿIAP  Main link. Argument: n (integer)

         µ       Combine the chain to the left into a link.
          ÐĿ     Apply that link until the results are no longer unique.
                 Return the list of unique results.
      ¤            Combine the two links to the left into a niladic chain.
  1                  Set the left (and right) argument to 1.
   +D¡               Apply + to the left and right argument, updating the left
                     argument with the sum, and the right argument with the
                     previous value of the left one. Return the list of results.
                     Repeat this process n times.
                   This yields n + 1 Fibonacci numbers, starting with 1, 2.
R                  Range; map k to [1, ..., k].
 f                 Filter; keep the items in the range that are Fibonacci numbers.
       Ṫ           Tail; yield the last one or 0 if the list is empty.
        ạ          Absolute difference with k.
                   This is the argument of the next iteration.
            I    Compute the increments of the arguments to the loop, yielding
                 the selected Fibonacci numbers (with changed sign).
             A   Apply absolute value to each.
              P  Compute their product.  
Dennis
quelle
6
Das scheint groß zu sein, Dennis.
Orlp
9

Python, 54 Bytes

f=lambda n,a=1,b=1:n<1or b>n and a*f(n-a)or f(n,b,a+b)

Nur eine gute alte Rekursion.

Sp3000
quelle
5

Perl, 69 63 + 4 ( -pl61Flag) = 67 Bytes

#!perl -pl61
while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{

Verwenden von:

> echo 42 | perl -pl61e 'while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{'

Ungolfed:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ = 1 by -l61
    while ($_ != 0) {
        my $n = 1;
        my $m = 1;
        while ($m <= $_) {
            ($n, $m) = ($m, $n + $m);
        }
        $_ -= $n;
        $\ *= $n;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Ideone .

Denis Ibaev
quelle
Die Erklärung sollte erwähnen, dass Oktal 061die ASCII-Codierung für das Zeichen ist '1'. Nizza Hack zu verwenden $\, um es fast kostenlos gedruckt zu bekommen.
Peter Cordes
2

JavaScript (ES6), 78 42 Byte

f=(n,a=1,b=1)=>n?b>n?a*f(n-a):f(n,b,a+b):1

Port von @ Sp3000's Antwort. Ursprüngliche 78-Byte-Version:

f=(n,a=[2,1])=>n>a[0]?f(n,[a[0]+a[1],...a]):a.map(e=>e>n?0:(r*=e,n-=e),r=1)&&r
Neil
quelle
2

> <> 57 Bytes

111\ ;n{/
:@+>:{:})?\$:@@
~{*}:0=?\}>:0${:})?$~:{$-$:1@?$

Erwartet, dass die Eingabenummer beim Programmstart auf dem Stack vorhanden ist.

Baut die Fibonacci-Sequenz ( f0, f1, f2, ..., fn) auf dem Stapel auf, bis eine Zahl erreicht ist, die größer als die Eingabe ( i) ist. Dann wird mit einem Produkt ( p) initialisiert, um 1...

while (i != 0)
   if (fn <= i)
      i = i - fn
      p = p * fn
   else
      i = i - 0
      p = p * 1
   discard fn
output p

Probieren Sie es online aus!

Sok
quelle
Nett! Ich schlage vor, Sie posten einen Link mit einem Online-Compiler
Luis Mendo
1

Pyth, 28 Bytes

K1WQJ0 .WgQH+Z~JZ1=*KJ=-QJ;K

Ich denke, es kann viel weiter golfen werden ...

Probieren Sie es online!

Undichte Nonne
quelle
1

Pyth, 24 Bytes

W=-QeaYh.WgQeH,eZsZ1;*FY

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

Q wird mit der Eingangsnummer belegt.

Das Teil h.WgQeH,eZsZ1berechnet die größte Fibonacci-Zahl, die kleiner oder gleich istQ

h.WgQeH,eZsZ1
            1   start with H=Z=1
 .WgQeH         while Q >= end(H):
       ,eZsZ       H=Z=(end(Z), sum(Z))
h               first

Also, wenn Q = 10es die Zahlen / Paare erzeugt:

1 -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8) -> (8,13) -> 8

Der Rest des Codes berechnet die Partition und multipliziert die Zahlen miteinander:

W=-QeaY...;*FY    implicit: Y = empty list
     aY...        add the calculated Fibonacci number to the empty list
    e             take the last element of Y (yes the number we just added)
 =-Q              and update Q with the difference of Q and ^
W         ;       continue until Q == 0
           *FY    multiply all number in Y and print

Es gibt offensichtlich viele kürzere Lösungen (mit wirklich schlechten Laufzeiten), wie z *FhfqQsTyeM.u,eNsNQ1.

Jakube
quelle
1

Haskell, 44 Bytes

Yay für die gegenseitige Rekursion:

(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1
  • a ist die vorherige Fibonacci-Zahl
  • b ist die aktuelle Fibonacci-Nummer
  • c ist der Eingang
  • f ist die gewünschte Funktion

Weniger golfen:

(a & b) c | c == 0    = 1
          | c <  b    = a * f (c-a)
          | otherwise = b & (a + b) $ c
f x = (0 & 1) x
Michael Klein
quelle
1

Eigentlich 22 Bytes

W;╗uR♂F;`╜≥`M░M;╜-WXkπ

Probieren Sie es online!

Erläuterung:

W;╗uR♂F;`╜≥`M░M;╜-WXkπ
                        (implicit input)
W                 W     while top of stack is truthy:
 ;╗                       push a copy of n to reg0
   uR♂F;                  push 2 copies of [Fib(a) for a in range(1, n+2)]
        `╜≥`M░            filter: take values where n <= Fib(a)
              M;          two copies of maximum (call it m)
                ╜-        subtract from n (this leaves n-m on top of the stack to be the new n next iteration, with a copy of m below it)
                   X    discard the 0 left over after the loop ends
                    kπ  product of all stack values
Mego
quelle
Hat Actually eine eigene Codierung? Ich zähle 35 Bytes in 22 Zeichen. mothereff.in/…
cat
1
@cat Genau wie bei Seriously wird CP437 verwendet.
Mego
1

Javascript (ES6) 134 106 92 Bytes

Vielen Dank für @cat, dass Sie ein Leerzeichen entdeckt haben.

n=>{for(c=[a=b=s=1,1];a+b<=n;)a+=b,c.unshift(b+=a,a);c.map(i=>i<=n&&(n-=i)&(s*=i));alert(s)}

Nur eine nicht optimierte Version, die auf meinem Handy erstellt wurde. Sobald ich nach Hause komme, spiele ich Golf. Ideen sind willkommen.

Bálint
quelle
Es gibt ein überflüssiges Leerzeichen. : P
Katze
1

RETURN , 44 Bytes

[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]

Try it here.

Erstaunlicherweise ineffizientes anonymes Lambda, das auf Stack2 resultiert. Verwendung:

12345[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]!

HINWEIS: ␌ und ␁ sind Platzhalter für die jeweiligen nicht druckbaren Zeichen: Form Feed und Start of Heading .

Erläuterung

[                                           ]  lambda
 a:                                            store input to a
   [  ][                         ]#            while loop
    a;                                           check if a is truthy
        1$[¤¤+$a;->~][]#%                        if so, generate all fibonacci numbers less than a 
                         $␌                      push copy of TOS to stack2
                           a;\-a:                a-=TOS
                                   ␁[¤][×]#   get product of stack2
Mama Fun Roll
quelle
Ich zähle 46 Bytes auf 42 Zeichen. Wenn RETURN eine spezielle Codierung verwendet, sollte es 42 Byte in 42 Zeichen sein, aber es scheint ein Unicode zu sein, also ist es 46.
cat
Eigentlich habe ich gerade gemerkt, dass ich vergessen habe, ein paar Unprintables einzulegen.
Mama Fun Roll
Ich brauchte ein Mikroskop, um zu sagen, was sie sind, also habe ich sie für Sie verlinkt. : D (Ich konnte nicht sagen, ob es SOH oder BOM war)
Katze
0

PHP, 119 Bytes

Der Code (zur besseren Lesbarkeit in zwei Zeilen eingeschlossen):

for($o=$c=1;$c<=$n=$argv[1];$f[++$k]=$c,$a=$b,$b=$c,$c+=$a);
for($i=$k;$i;$i--)for(;$n>=$d=$f[$i];$n-=$d,$o*=$d);echo$o;

Die erste Zeile berechnet $fdie Fibonacci-Zahlen kleiner als $n(das in der Befehlszeile angegebene Argument). Die zweite Zeile berechnet die Fibonacci-Faktoren (durch Subtraktion) und multipliziert sie, um das Produkt in zu berechnen$o .

Stellen Sie den Code voran <?php(technisch nicht Teil des Programms), legen Sie ihn in eine Datei ( fibonacci-factors.php) und führen Sie ihn aus als:

$ php -d error_reporting=0 fibonacci-factors.php 100
# The output:
2136

Oder starten Sie es mit php -d error_reporting=0 -r '... code here ...' 100 .

Der ungolfed Code und die Testsuite sind auf Github zu finden .

Axiac
quelle
0

Q, 47 Bytes

m:{*/1_-':|(0<){y-x x bin y}[*+60(|+\)\1 0]\x}

Prüfung

+(i;m'i:1 2 3 4 5 6 7 8 9 42 1000 12345)

Lies es als Paare (i, map (m, i)), wobei m die Rechenfunktion ist und i die verschiedenen Argumente

schreibt

1     1
2     2
3     3
4     3
5     5
6     5
7     10
8     8
9     8
42    272
1000  12831
12345 138481852236

Erläuterung

n funtion\arg Wendet die Funktion (function (function (... function (args))) n-mal an (verwendet intern die tal-Rekursion) und gibt die Folge der Ergebnisse zurück. Wir berechnen die 60 ersten Elemente der fibonnaci-Reihe als *+60(|+\)\1 0. In diesem Fall lautet die Funktion ( | +): + \, das über eine Sequenz angewendet wird, berechnet Teilsummen (ex + \ 1 2 3 ist 1 3 6) und kehrt die Sequenz um. Bei jeder 'Iteration' berechnen wir Teilsummen der beiden vorherigen Fibonacci-Zahlen und geben die Teilsummen zurück sums reverse 60(|+\)\1 0generiert Sequenzen 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ..., *+die über dieses Ergebnis angewendet werden, kippen (traspose) und nehmen das erste. Ergebnis ist Sequenz 1 1 2 3 5 8 13 21 34 55 ..

(cond)function\args Wendet function (function (.. function (args))) an, während cond true ist, und gibt die Folge der Teilergebnisse zurück

function[arg] angewendet über eine Funktion von mehr als einem Argument erzeugt eine Projektion (Teilanwendung)

Wir können den Argumenten Namen geben, aber die impliziten Namen sind x, y, z

{y-x x bin y}[*+60(|+\)\1 0]deklariert ein Lambda mit args x, y mit partieller Projektion (arg x ist eine Fibonacci-Reihe, berechnet als * + 60 (| +) \ 1 0). x steht für Fibonacci-Werte und y für die zu verarbeitende Zahl. Die binäre Suche (bin) wird verwendet, um den Index der größeren Fibonacci-Zahl <= y ( x bin y) zu lokalisieren und den entsprechenden Wert von x zu subtrahieren.

Um das Produkt aus Teilergebnissen zu berechnen, kehren wir diese um und berechnen die Differenz jedes Paares ( -':|). Lassen Sie das erste ( 1_weil 0) fallen und multiplizieren Sie es mit ( */).

Wenn wir an akkumulierter Summe interessiert sind, ist der Code derselbe, aber mit +/statt */. Anstelle von + oder * können wir auch jeden anderen diadischen Operator verwenden.

Über die Effizienz der Ausführung

Ich weiß, dass Effizienz in diesem Wettbewerb kein Thema ist. Aber in diesem Problem können wir von linearen Kosten bis zu exponentiellen Kosten reichen, also bin ich neugierig.

Ich entwickelte eine zweite Version (Länge 48 Bytes ohne Kommentar) und wiederholte 1000-mal Testfälle Batterie auf beiden Versionen.

f:*+60(|+\)\1 0;m:{*/1_-':|(0<){x-f f bin x}\x}    /new version

Ausführungszeit ist: Originalversion 0'212 seg, neue Version 0'037 seg

Die Originalversion berechnet die Fibbonaci-Serie einmal pro Funktionsanwendung. Neue Version berechnet Fibonacci nur eine.

In beiden Fällen verwendet die Berechnung der Fibonacci-Reihe die Schwanzrekursion

J. Sendra
quelle