Le défi fibonacci minimum!

19

Défi

Dans cette tâche, vous recevrez un entier N (inférieur à 10 6 ), trouvez la façon minimale de additionner N en utilisant uniquement des nombres de Fibonacci - cette partition est appelée représentation de Zeckendorf .

Vous pouvez utiliser n'importe quel numéro de Fibonacci plus d'une fois et s'il y a plus d'une représentation en sortie.

Par exemple, si l'entrée est 67, une sortie possible pourrait être d'utiliser les nombres Fibonacci 1,3,8,55 qui est également le nombre minimum de nombres Fibonacci qui pourraient être utilisés pour obtenir la somme 67 .

L'entrée N est donnée sur une seule ligne, les entrées sont terminées par EOF.

Exemples

Donné dans le format 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

Contraintes

  • Le nombre d'entrées ne dépasserait pas 10 6 valeurs.
  • Votre programme ne doit pas fonctionner plus de 5 secondes pour toutes les entrées.
  • Vous pouvez utiliser n'importe quelle langue de votre choix.
  • La solution la plus courte gagne!
Chimérique
la source
"Tu pourrais n'importe quel numéro de Fibonacci ..." hein? "Le nombre d'entrées ne dépasserait pas 10 ^ 6 valeurs." Nous n'aurons donc jamais besoin d'ajouter plus de 10 ^ 6 nombres ensemble? Voulez-vous dire que la somme des entrées ne dépasserait pas 10 ^ 6?
mellamokb
7
Spoilers: 1) L'algorithme gourmand (soustrayez le plus grand nombre de Fibonacci jusqu'à ce que l'entrée soit nulle) produit des solutions optimales. 2) Une solution optimale n'a pas besoin d'utiliser deux fois un nombre de Fibonacci (qui découle de 1). 3) Une solution optimale, pour N <= 1000000, n'aura pas plus de 14 termes.
Joey Adams
6
@Joey: Plus généralement, l'algorithme gourmand décompose les entiers positifs en sommes de nombres de Fibonacci distincts de sorte que les nombres de Fibonacci consécutifs ne sont pas utilisés (c'est ce qu'on appelle le théorème de Zeckendorf).
Nabb
1
Spoiler 4: 29 termes de la séquence de Fibonacci commençant à 0 1 est suffisant.
Peter Taylor
@Nabb: Merci d'avoir expliqué la partie mathématique.
Quixotic

Réponses:

16

Ensemble Motorola 68000 - 34 octets

(Syntaxe de l'assembleur 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: Le générateur Fibonacci s'est arrêté au débordement plutôt qu'en comptant, et a corrigé le 0boîtier pour qu'il sorte [0]plutôt que []. Cependant, passer un négatif se Nbloque maintenant.

Le commentaire en haut est le prototype C de cette fonction, utilisant un extension de langage pour identifier quels paramètres vont où (par défaut, ils vont sur la pile).

Ma TI-89 , avec son processeur 10 MHz, prend 5 minutes pour exécuter cette fonction sur 1 - 1 000 000.

Bien que le code machine soit (actuellement) moins d'octets que la solution GolfScript, il serait probablement injuste d'accepter cela comme la solution la plus courte car:

Si vous avez une TI-89/92 / V200, vous pouvez télécharger le projet complet ici (obsolète):

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

Bonne chance pour amener RapidShare à vous donner le fichier réel. Quelqu'un connaît-il un bon hôte pour des fichiers aussi gros? 8940 représente énormément d'octets.

Joey Adams
la source
Vous pouvez ajouter un quatrième point à la liste: la solution ne donne pas la sortie au format correct: P J'utilise 7 caractères uniquement sur les littéraux de chaîne. BTW Renvoyez-vous la liste [0] pour l'entrée 0? Il me semble que vous renvoyez la liste vide. C'est un cas spécial irritant.
Peter Taylor
@Peter Taylor: Tu as raison, ça m'a manqué. J'ai mélangé les termes et le nombre de termes. Je publierai bientôt un correctif.
Joey Adams
5

Javascript (142)

Ne gère qu'une seule entrée à la fois. Parce que la saisie sur plusieurs lignes est inutile pour 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
la source
5

C, 244 caractères

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

Avec espace:

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

Ce programme lira les nombres de l'entrée standard et écrit sur la sortie standard.

ughoavgfhw
la source
5

Golfscript, 43 caractères

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

Je pense que cela peut probablement être réduit de 3 à 5 caractères avec plus d'effort. Par exemple, le déplier pour ensuite jeter le tableau semble inutile.

Peter Taylor
la source
3

F # - 282 252 241 caractères

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
la source
3

Python - 183 caractères

La majorité du code gère plusieurs entrées :(

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
la source
Pouvez-vous mettre le n=input()à la fin de la ligne précédente?
mbomb007
Je suppose. : \
st0le
Vous pouvez également enregistrer un personnage en supprimant l'espace aprèsprint
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

Exemple de sortie

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
la source
2

EXCEL: 89 caractères en code unique:

entrez la description de l'image ici

user14011
la source
1

Scala - 353 caractères (100 caractères pour gérer plusieurs entrées)

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
la source
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))pourrait être raccourci pour io.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))enregistrer 40 caractères ish.
Gareth
1

Python 3 (170 caractères)

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)

Entrée multiligne, arrêt sur ligne vide

AMK
la source
1

C, 151 caractères

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

version lisible:

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
la source
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)

Gère plusieurs entrées et cat le résultat à 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
la source
1

R (460 caractères)

Une autre version utilisant R.
Lecture du fichier «entrée», sortie vers le fichier «sortie»

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)

exemple "entrée"

0
47
3788
1646
25347
677
343
3434

exemple "sortie"

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

Version plus lisible:

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
la source
0

D (196 caractères)

Courez avec rdmd --eval=…. Cela cache commodément le passe-partout import x, y, z;et 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
la source
0

Utiliser 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
la source
Il s'agit de golf de code, alors assurez-vous de jouer au golf votre réponse.
KSFT
1
Bienvenue chez PPCG! Comme l'a dit KSFT, c'est un défi de code-golf . Veuillez montrer un certain effort pour répondre à cette question dans le moins d'octets de code possible. À tout le moins, vous pouvez supprimer les espaces inutiles et utiliser des noms de classe / méthode / variable à lettre unique. Après cela, veuillez également inclure le nombre d'octets dans votre réponse.
Martin Ender