Минимальный вызов Фибоначчи!

19

Вызов

В этой задаче вам дадут целое число N (меньше 10 6 ), найдите минимальный способ суммирования в N, используя только числа Фибоначчи - это разбиение называется представлением Цекендорфа .

Вы можете использовать любое число Фибоначчи более одного раза, и если есть более одного представления, выведите любое.

Например, если входное значение равно 67, то одним из возможных выходных данных может быть использование чисел Фибоначчи 1,3,8,55, которое также является минимальным числом чисел Фибоначчи, которое можно использовать для получения суммы 67 .

Вход N указан в одной строке, входы заканчиваются EOF.

Примеры

Дано в формате 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

Ограничения

  • Количество входов не должно превышать 10 6 значений.
  • Ваша программа не должна запускаться более 5 секунд для всех входов.
  • Вы можете использовать любой язык по вашему выбору.
  • Самое короткое решение побеждает!
донкихотский
источник
"Вы могли бы любое число Фибоначчи ...", а? «Количество входов не должно превышать 10 ^ 6 значений». Таким образом, нам никогда не нужно будет добавлять более 10 ^ 6 чисел вместе? Вы имеете в виду, что сумма входов не будет превышать 10 ^ 6?
mellamokb
7
Спойлеры: 1) Жадный алгоритм (вычитает наибольшее число Фибоначчи до тех пор, пока ввод не равен нулю) дает оптимальные решения. 2) Оптимальное решение не должно использовать число Фибоначчи дважды (что следует из 1). 3) Оптимальное решение для N <= 1000000 будет иметь не более 14 слагаемых.
Джои Адамс
6
@Joey: В более общем смысле, жадный алгоритм разбивает положительные целые числа на суммы различных чисел Фибоначчи, так что последовательные числа Фибоначчи не используются (это называется теорема Цекендорфа).
Набб
1
Спойлер 4: 29 членов последовательности Фибоначчи, начиная с 0 1, достаточно.
Питер Тейлор
@Nabb: Спасибо за объяснение части математики.
Quixotic

Ответы:

16

Сборка Motorola 68000 - 34 байта

(Синтаксис ассемблера 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: заставил генератор Фибоначчи останавливаться при переполнении, а не путем подсчета, и зафиксировал 0случай, чтобы он выводил, [0]а не []. Однако прохождение негатива Nсейчас вылетает.

Комментарий вверху - это прототип C этой функции, использующий расширение языка для определения, куда и куда идут параметры (по умолчанию они идут в стек).

Мой TI-89 с процессором 10 МГц занимает 5 минут, чтобы запустить эту функцию на 1 - 1 000 000.

Хотя машинный код (в настоящее время) меньше байтов, чем решение GolfScript, вероятно, было бы несправедливо принять это как самое короткое решение, потому что:

Если у вас TI-89/92 / V200, вы можете скачать полный проект здесь (устаревший):

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

Удачи в RapidShare, чтобы получить актуальный файл. Кто-нибудь знает хороший хост для таких больших файлов? 8940 - это очень много байтов.

Джои Адамс
источник
Вы можете добавить четвертый пункт в список: решение не дает вывод в правильном формате: P Я использую 7 символов только для строковых литералов. Кстати, вы возвращаете список [0] для ввода 0? Мне кажется, что вы возвращаете пустой список. Это раздражающий особый случай.
Питер Тейлор
@ Питер Тейлор: Вы правы, я пропустил это. Я перепутал сроки и сроки. Я скоро выложу исправление.
Джои Адамс
5

Javascript (142)

Только обрабатывает один вход за один раз. Потому что многострочный ввод бесполезен для 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
источник
5

C, 244 символа

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

С пробелами:

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

Эта программа будет читать числа из стандартного ввода и записывать в стандартный вывод.

ughoavgfhw
источник
5

Golfscript, 43 символа

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

Я думаю, что это может быть уменьшено на 3–5 символов с большим усилием. Например, разворачивание, чтобы затем выбросить массив, кажется расточительным.

Питер Тейлор
источник
3

F # - 282 252 241 символов

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
источник
3

Питон - 183 символа

Большая часть кода обрабатывает несколько входов :(

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
источник
Можете ли вы поставить n=input()в конце предыдущей строки?
mbomb007
Я так полагаю. : \
st0le
Вы также можете сохранить персонажа, убрав пробел послеprint
mbomb007 27.02.15
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

Пример вывода

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
источник
2

EXCEL: 89 символов в уникальном коде:

введите описание изображения здесь

user14011
источник
1

Scala - 353 символа (100 символов для обработки нескольких входов)

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)))
Лалитх
источник
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))можно сократить до io.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))40 символов.
Гарет
1

Python 3 (170 символов)

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)

Многострочный ввод, остановка на пустой строке

АМК
источник
1

C, 151 символов

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

читаемая версия:

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
источник
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)

Обрабатывает несколько входов и выводит результат в 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
источник
1

R (460 символов)

Другая версия, использующая R.
Чтение из файла «input», вывод в файл «output»

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)

пример ввода

0
47
3788
1646
25347
677
343
3434

пример вывода

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

Более читаемая версия:

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
источник
0

D (196 символов)

Беги с rdmd --eval=…. Это удобно скрывает шаблон import x, y, z;и 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
источник
0

Используя 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);
    }
}
}
Манодж Гупта
источник
Это код гольф, так что обязательно ответьте на ваш ответ.
KSFT
1
Добро пожаловать в PPCG! Как сказал KSFT, это вызов для игры в гольф . Пожалуйста, приложите некоторые усилия, чтобы ответить на этот вопрос, используя как можно меньше байт кода. По крайней мере, вы можете удалить ненужные пробелы и использовать однобуквенные имена классов / методов / переменных. После этого, пожалуйста, включите количество байтов в вашем ответе.
Мартин Эндер