Minimalne wyzwanie fibonacciego!

19

Wyzwanie

W tym zadaniu otrzymasz liczbę całkowitą N (mniejszą niż 10 6 ), znajdź minimalny sposób, w jaki możesz sumować do N, używając tylko liczb Fibonacciego - ta partycja nazywa się reprezentacją Zeckendorfa .

Możesz użyć dowolnej liczby Fibonacciego więcej niż jeden raz i jeśli istnieje więcej niż jeden wynik reprezentacji.

Na przykład, jeśli dane wejściowe to 67, wówczas jednym z możliwych wyników może być użycie liczb Fibonacciego 1,3,8,55, co jest również minimalną liczbą liczb Fibonacciego, które można wykorzystać do uzyskania sumy 67 .

Wejście N jest podawane w jednym wierszu, wejścia są zakończone przez EOF.

Przykłady

Podany w formacie input: output

0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2

Ograniczenia

  • Liczba wejść nie przekroczy 10 10 wartości.
  • Twój program nie powinien działać dłużej niż 5 sekund dla wszystkich danych wejściowych.
  • Możesz użyć dowolnego wybranego języka.
  • Najkrótsze rozwiązanie wygrywa!
Donkiszotowski
źródło
„Mógłbyś mieć dowolny numer Fibonacciego…”, co? „Liczba wejść nie przekroczy 10 10 wartości”. Więc nigdy nie będziemy musieli dodawać więcej niż 10 ^ 6 liczb razem? Czy masz na myśli, że suma nakładów nie przekroczy 10 ^ 6?
mellamokb
7
Spoilery: 1) Chciwy algorytm (odejmuj największą liczbę Fibonacciego, aż wartość wejściowa wyniesie zero) daje optymalne rozwiązania. 2) Optymalne rozwiązanie nie musi używać liczby Fibonacciego dwukrotnie (co wynika z 1). 3) Optymalne rozwiązanie dla N <= 1000000 będzie mieć nie więcej niż 14 warunków.
Joey Adams
6
@Joey: Bardziej ogólnie, zachłanny algorytm rozkłada dodatnie liczby całkowite na sumy różnych liczb Fibonacciego, tak że kolejne liczby Fibonacciego nie są używane (nazywa się to twierdzeniem Zeckendorfa).
Nabb
1
Spoiler 4: 29 terminów sekwencji Fibonacciego rozpoczynających się od 0 1 jest wystarczający.
Peter Taylor
@Nabb: Dziękujemy za wyjaśnienie części matematycznej.
Quixotic

Odpowiedzi:

16

Motorola 68000 - 34 bajty

(Składnia asemblera GNU)

| short min_fib_partition(long N asm("%d2"), long *out asm("%a0"))
min_fib_partition:
    | Generate Fibonacci numbers on the stack (-1, 1, 0, 1, 1, 2, 3, ..., 1134903170).
    moveq #-1, %d0          | A = -1
    moveq #1, %d1           | B = 1
generate_loop:
    move.l %d0, -(%sp)      | Push A to the stack.
    exg.l %d0, %d1          | A' = B
    add.l %d0, %d1          | B' = A + B
    bvc.s generate_loop     | Stop when signed long overflows.

    | Go back up the stack, partitioning N using the greedy algorithm.
    moveq #0, %d0           | Initialize return value (number of terms).
subtract_loop:
    move.l (%sp)+, %d1      | Pop a Fibonacci number F off the stack.
    cmp.l %d1, %d2          | If N < F, continue to smaller Fibonacci number.
    blt.s subtract_loop
    addq.w #1, %d0          | Increment the term count.
    move.l %d1, (%a0)+      | Append F to the output array.
    sub.l %d1, %d2          | N -= F
    bne.s subtract_loop     | Continue if N has not yet reached zero.

    | Clear the stack by searching for that -1.
clear_stack_loop:
    tst.l (%sp)+
    bge clear_stack_loop

done:
    rts

36 → 34: Sprawiono, że generator Fibonacciego zatrzymał się przy przepełnieniu zamiast zliczania, i naprawił 0obudowę, aby wyświetlała [0]zamiast []. Jednak przekazanie negatywnej Nawarii powoduje teraz.

Komentarz u góry to prototyp C tej funkcji, wykorzystujący rozszerzenie języka do identyfikacji, które parametry idą gdzie (domyślnie idą na stos).

Mój TI-89 z procesorem 10 MHz zajmuje 5 minut na uruchomienie tej funkcji na 1 - 1 000 000.

Chociaż kod maszynowy ma (obecnie) mniej bajtów niż rozwiązanie GolfScript, prawdopodobnie niesprawiedliwe byłoby zaakceptowanie tego jako najkrótszego rozwiązania, ponieważ:

Jeśli masz TI-89/92 / V200, możesz pobrać cały projekt tutaj (nieaktualny):

https://rapidshare.com/files/154945328/minfib.zip

Powodzenia namawianie RapidShare do uzyskania rzeczywistego pliku. Czy ktoś zna dobrego hosta dla tak dużych plików? 8940 to strasznie dużo bajtów.

Joey Adams
źródło
Możesz dodać czwarty punkt do listy: rozwiązanie nie daje danych wyjściowych we właściwym formacie: P Używam 7 znaków na samych literałach łańcuchowych. BTW Czy zwracasz listę [0] dla wejścia 0? Wydaje mi się, że zwracasz pustą listę. To irytujący przypadek specjalny.
Peter Taylor
@Peter Taylor: Masz rację, tęskniłem. Mam pomieszane terminy i liczby terminów. Wkrótce opublikuję poprawkę.
Joey Adams
5

JavaScript (142)

Obsługuje tylko pojedyncze wejście na raz. Ponieważ wprowadzanie wielu wierszy jest bezużyteczne w JavaScript.

k=n=prompt(f=[a=b=1])|0;while((b=a+(a=b))<n)f.push(b);for(i=f.length,g=[];i--;)if(f[i]<=k)g.push(f[i]),k-=f[i];alert(n+': '+(n?g.join('+'):0))

http://jsfiddle.net/EqMXQ/

mellamokb
źródło
5

C, 244 znaki

#define P printf
int f[30];int main(){f[28]=f[29]=1;int i=28;for(;i>0;--i)f[i-1]=f[i+1]+f[i];int x;while(scanf("%i",&x)!=-1){P(x?"%i: ":"0: 0\n",x);if(x>0){int i=0,a=0;while(x>0){while(f[i]>x)++i;if(a++)P("+");P("%i",f[i]);x-=f[i];}P("\n");}}}

Z białymi znakami:

#define P printf
int f[30];
int main(){
    f[28] = f[29] = 1;
    int i = 28;
    for(; i > 0; --i) f[i-1] = f[i+1] + f[i];
    int x;
    while(scanf("%i",&x) != -1) {
        P(x ? "%i: " : "0: 0\n",x);
        if(x > 0) {
            int i = 0, a = 0;
            while(x > 0) {
                while(f[i] > x) ++i;
                if(a++) P("+");
                P("%i",f[i]);
                x -= f[i];
            }
            P("\n");
        }
    }
}

Ten program odczytuje liczby ze standardowego wejścia i zapisuje na standardowe wyjście.

ughoavgfhw
źródło
5

Golfscript, 43 znaki

~]{:|': '[{0 1{|>!}{.@+}/;|1$-:|}do]'+'*n}%

Myślę, że można to z większym wysiłkiem zmniejszyć o 3 do 5 znaków. Np. Rozwinięcie, a następnie wyrzucenie tablicy, jest marnotrawstwem.

Peter Taylor
źródło
3

F # - 282 252 241 znaków

let mutable d=int(stdin.ReadLine())
let q=d
let rec f x=if x<2 then 1 else f(x-2)+f(x-1)
let s x=
 d<-d-x
 x
printf"%d: %s"q (Core.string.Join("+",[for i in List.filter(fun x->x<d)[for i in 28..-1..0->f i]do if d-i>=0 then yield s i]))
Nharren
źródło
3

Python - 183 znaków

Większość kodu obsługuje wiele danych wejściowych :(

f=lambda a,b,n:b>n and a or f(b,a+b,n)
g=lambda n:n>0and"%d+%s"%(f(0,1,n),g(n-f(0,1,n)))or""
try:
 while 1:
  n=input()
  print "%d: %s"%(n,n<1and"0"or g(n).strip("+"))
except:0
st0le
źródło
Czy umieścisz n=input()na końcu poprzedniej linii?
mbomb007
Tak przypuszczam. : \
st0le
Możesz także uratować postać, usuwając spację poprint
mbomb007
2

Mathematica 88

n = RandomInteger[10000, 10];

Print[k=#,For[i=99;l={},k>0,If[#<=k,k-=#;l~AppendTo~#]&@Fibonacci@i--];":"l~Row~"+"]&/@n

Przykład wyniku

3999: 2584+987+377+34+13+3+1
9226: 6765+1597+610+233+21
7225: 6765+377+55+21+5+2
9641: 6765+2584+233+55+3+1
6306: 4181+1597+377+144+5+2
4507: 4181+233+89+3+1
8848: 6765+1597+377+89+13+5+2
6263: 4181+1597+377+89+13+5+1
2034: 1597+377+55+5
6937: 6765+144+21+5+2
Ybeltukov
źródło
2

EXCEL: 89 znaków w unikalnym kodzie:

wprowadź opis zdjęcia tutaj

użytkownik14011
źródło
1

Scala - 353 znaków (100 znaków do obsługi wielu danych wejściowych)

def h(m:Int){lazy val f={def g(a:Int,b:Int):Stream[Int]=a #:: g(b,a+b);g(0,1);};if(m==0)println(m+": "+m)else{var s=0;var t= f.takeWhile(_ <= m);var w="";while(s!= m){s+=t.last;w+=t.last+"+";t=t.takeWhile(_<=m-s);};println(m+": "+w.take(w.length-1))}}
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
Lalith
źródło
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))można skrócić, aby io.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))zapisać 40-znakowe postacie.
Gareth
1

Python 3 (170 znaków)

while 1:
 s=input()
 if not s:break
 s=n=int(s);f=[1];t=[]
 while f[-1]<n:f+=[sum(f[-2:])]
 for i in f[::-1]:
  if s>=i:s-=i;t+=[i]
 print(n,'=','+'.join(map(str,t))or 0)

Wejście wielowierszowe, zatrzymaj się na pustej linii

AMK
źródło
1

C, 151 znaków

main() {int i=1,n,f[30]={1,1};for(;i++<30;)f[i]=f[i-1]+f[i-2];while(scanf("%d",&n))for(i=30;;--i)if(f[i]<=n){printf("%d\n",f[i]);if(!(n-=f[i]))break;}}

czytelna wersja:

main() {
    int i=1,n,f[30]={1,1};
    for(;i++<30;)f[i]=f[i-1]+f[i-2];
    while(scanf("%d",&n))
        for(i=30;;--i)
            if(f[i]<=n) {
                printf("%d\n",f[i]);
                if (!(n-=f[i])) break;
            }
}
vmrob
źródło
1

R 170

x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)

Obsługuje wiele wejść i wyniki kota do STDOUT

> x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)
1: 100
2: 200
3: 300
4: 
Read 3 items
89+8+3
144+55+1
233+55+8+3+1
numeric(0)
>
MickyT
źródło
1

R (460 znaków)

Inna wersja używająca R.
Czytanie z pliku „wejście”, wyjście do pliku „wyjście”

d=as.list(as.integer(scan("input","",sep="\n")));n=36;f=rep(1,n);for(i in 3:n){f[i]=f[i-2]+f[i-1]};d2=lapply(d,function(x){a=vector("integer");i=1;while(x>0){id=which(f>=x)[1];if(x==f[id]){x=x-f[id];a[i]=f[id]}else{x=x-f[id-1];a[i]=f[id-1]}i=i+1}a});d=mapply(c,d,d2,SIMPLIFY=0);for(i in 1:length(d)){t=d[[i]];l=length(t);if(l==1){d[[i]]=paste(t[1],t[1],sep=": ")}else{d[[i]]=paste(t[1],": ",paste(t[2:l],collapse="+"),sep="")}}lapply(d,write,"output",append=1)

przykład „wprowadzania”

0
47
3788
1646
25347
677
343
3434

przykład „wynikowy”

0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2

Bardziej czytelna wersja:

dt <- as.list(as.integer(scan(file = "input", what = "", sep = "\n")))
n <- 36
fib <- rep(1, n)
for(i in 3:n){fib[i] <- fib[i-2] + fib[i-1]}
dt2 <- lapply(dt, function(x){answ <- vector(mode = "integer")
                               i <- 1
                               while(x > 0){
                                   idx <- which(fib>=x)[1]
                                   if(x == fib[idx]){
                                       x <- x - fib[idx]
                                       answ[i] <- fib[idx]
                                   } 
                                   else {
                                       x <- x - fib[idx-1]
                                       answ[i] <- fib[idx-1]
                                   }
                                   i <- i + 1
                               }
                               answ})
dt <- mapply(FUN = c, dt, dt2, SIMPLIFY = FALSE)
for(i in 1:length(dt)){
    t1 <- dt[[i]]
    t1.len <- length(t1)
    if(t1.len == 1){
        dt[[i]] <- paste(t1[1], t1[1], sep=": ")
    } else {
        dt[[i]] <- paste(t1[1], ": ", paste(t1[2:t1.len], collapse = "+"), sep="")
    }
}
lapply(dt, write, "output", append=TRUE)
AndriusZ
źródło
0

D (196 znaków)

Uruchom z rdmd --eval=…. To wygodnie ukrywa płytę kotła import x, y, z;i void main() {…}:

int f(int i){return i-->1?f(i--)+f(i):i+2;}int n;foreach(x;std.stdio.stdin.byLine.map!(to!int))writeln(x,": ",x?n=x,reduce!((r,i)=>f(i)<=n?n-=f(i),r~="+"~f(i).text:r)("",29.iota.retro)[1..$]:"0")
mleise
źródło
0

Korzystanie z Java

package org.mindcraft;

import java.util.Scanner;

public class Fibbo {
    public static void main(String[] args) {
    String number = null;
    int tmp, sum;
    int i = 1, j = 1;
    Scanner in = new Scanner(System.in);
    number = in.nextLine();
    String[] arr = number.split(" ");
    for (int it = 0; it < arr.length; it++) {
        tmp = Integer.parseInt(arr[it]);
        String value = tmp+" : ";
        while (tmp > 0) {
            i = 1;
            j = 1;
            for (int k = 0; k < 10000; k++) {
                sum = i + j;
                if (sum > tmp) {
                    //if (value == null) {
                    char ch=value.charAt(value.length()-2);
                    if(ch==':')
                    {
                        value = value+" "+ j + "";
                    } else {
                        value = value + " + " + j;
                    }

                    tmp = tmp - j;
                    break;
                }
                i = j;
                j = sum;
            }
        }
        System.out.println(value);
    }
}
}
Manoj Gupta
źródło
To jest golf golfowy, więc upewnij się, że grasz w golfa.
KSFT
1
Witamy w PPCG! Jak powiedział KSFT, jest to wyzwanie związane z golfem . Pokaż trochę wysiłku, aby odpowiedzieć na to pytanie w jak najmniejszej liczbie bajtów kodu. Przynajmniej możesz usunąć niepotrzebne białe znaki i użyć jednoliterowych nazw klas / metod / zmiennych. Po wykonaniu tej czynności podaj również liczbę bajtów w swojej odpowiedzi.
Martin Ender