Desafio
Nesta tarefa, você receberia um número inteiro N (menor que 10 6 ), encontre a maneira mínima pela qual você poderia somar N usando apenas números de Fibonacci - essa partição é chamada representação Zeckendorf .
Você pode usar qualquer número de Fibonacci mais de uma vez e, se houver mais de uma representação, qualquer saída.
Por exemplo, se a entrada for 67 , uma saída possível poderia ser usar os números de Fibonacci 1,3,8,55, que também é o número mínimo de números de Fibonacci que poderiam ser usados para obter a soma 67 .
A entrada N é fornecida em uma única linha, as entradas são terminadas por EOF.
Exemplos
Dado no formato 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
Restrições
- O número de entradas não excederia 10 6 valores.
- Seu programa não deve executar mais de 5 segundos para todas as entradas.
- Você pode usar qualquer idioma de sua escolha.
- A solução mais curta vence!
code-golf
fibonacci
integer-partitions
Quixotesco
fonte
fonte
Respostas:
Montagem do Motorola 68000 - 34 bytes
(Sintaxe do montador GNU)
36 → 34: O gerador de Fibonacci parou o estouro em vez de contar e corrigiu o
0
gabinete para que ele produzisse[0]
vez de[]
. No entanto, passando umaN
falha negativa agora.O comentário no topo é o protótipo C dessa função, usando um extensão de idioma para identificar quais parâmetros vão para onde (por padrão, eles ficam na pilha).
Minhas TI-89 , com seu processador de 10 MHz, leva 5 minutos para executar esta função em 1 a 1.000.000.
Embora o código da máquina (atualmente) seja menos bytes que a solução GolfScript, provavelmente seria injusto aceitar isso como a solução mais curta, porque:
Se você possui uma TI-89/92 / V200, pode fazer o download do projeto completo aqui (desatualizado):
https://rapidshare.com/files/154945328/minfib.zip
Boa sorte persuadindo o RapidShare a fornecer o arquivo real. Alguém sabe de um bom host para arquivos deste tamanho? 8940 é uma quantidade enorme de bytes.
fonte
Javascript (142)
Lida apenas com entrada única por vez. Como a entrada de várias linhas é inútil para JavaScript.
http://jsfiddle.net/EqMXQ/
fonte
C, 244 caracteres
Com espaço em branco:
Este programa lê números fora da entrada padrão e grava na saída padrão.
fonte
Golfscript, 43 caracteres
Eu acho que isso provavelmente pode ser reduzido em 3 a 5 caracteres com mais esforço. Por exemplo, o desenrolar para depois jogar fora a matriz parece um desperdício.
fonte
F # -
282252241caracteresfonte
Python - 183 caracteres
A maioria do código está lidando com várias entradas :(
fonte
n=input()
no final da linha anterior?print
Mathematica 88
Exemplo de saída
fonte
EXCEL: 89 caracteres em código único:
fonte
Scala - 353 caracteres (100 caracteres para manipular várias entradas)
fonte
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
pode ser reduzido paraio.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))
salvar 40 caracteres ish.Python 3 (170 caracteres)
Entrada multilinha, pare na linha vazia
fonte
C, 151 caracteres
versão legível:
fonte
R, 170
Lida com várias entradas e o resultado é STDOUT
fonte
R (460 caracteres)
Outra versão usando R.
Lendo do arquivo "input", saída para o arquivo "output"
exemplo "input"
exemplo "output"
Versão mais legível:
fonte
D (196 caracteres)
Corra com
rdmd --eval=…
. Isso oculta convenientemente o clichê deimport x, y, z;
evoid main() {…}
:fonte
Usando Java
fonte