Напишите число в виде суммы Фибоначчи

9

Давайте определим последовательность Фибоначчи как 

F(1) = 1

F(2) = 2

F(n) = F(n - 2) + F(n - 1)

Итак, мы имеем бесконечную последовательность 1,2,3,5,8,13,... Хорошо известно, что любое положительное целое число может быть записано как сумма некоторых чисел Фибоначчи. Единственное предостережение в том, что это суммирование может быть не уникальным. Всегда есть хотя бы один способ записать число в виде суммы чисел Фибоначчи, но их может быть намного больше.

Ваша задача - написать полную программу, которая с использованием stdin принимает положительное целое число от одного до миллиона включительно, а затем выводит с использованием stdout все возможные суммы сумм Фибоначчи, которые суммируют до входных данных. Суммируя, числа Фибоначчи не должны повторяться, и это включает число 1. При любом суммировании, если 1оно присутствует, оно должно присутствовать только один раз, поскольку в моем определении приведенная выше последовательность 1встречается только один раз. Суммы с единственным термином действительны, поэтому, если входное число является самим числом Фибоначчи, то само число является действительным суммированием и должно быть напечатано. Если несколько сумм, то между любыми двумя суммами должна быть пустая строка, чтобы их можно было легко различить.

Вот несколько примеров.

./myfib 1
1

Существует только одна такая сумма, и у нее есть только термин, так что это все, что напечатано.

./myfib 2
2

Обратите внимание, что 1+1это неверная сумма, потому что 1повторяется.

./myfib 3
1+2

3

Две суммы, и они оба напечатаны с пустой строкой между ними.

./myfib 10
2+8

2+3+5

./myfib 100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55

Настоящий код-гольф. Самый короткий код на любом языке выигрывает. Пожалуйста, опубликуйте свой код с некоторыми тестовыми примерами (кроме того, который я дал выше). В случае галстуков, я выбираю ту, которая получила наибольшее количество голосов после ожидания, по крайней мере, в течение двух недель и, возможно, дольше. Поэтому сообщество, пожалуйста, не стесняйтесь высказать любые решения, которые вам нравятся. Хитрость / красота кода важнее, чем то, кто публикуется первым.

Удачного кодирования!

code-golf fibonacci Фиксированная точка
источник
1
... Я просто соблазню это: P Если я
отправлю
Ну, это код-гольф, а не быстрый код. :-D
Фиксированная точка
1
Я написал это, и это на самом деле работает быстро: P
дверная ручка
Не совсем дубликат, но тесно связанный с codegolf.stackexchange.com/q/2677/194
Питер Тейлор
1
@shiona Так как я не уточнил, выберите свой любимый. :-)
Фиксированная точка

Ответы:

9

GolfScript, 54 символа

~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/

Протестируйте его онлайн или посмотрите на примеры:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55
Говард
источник
4

Ruby, 118 114 (вывод массива) или 138 134 (корректный вывод)

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}

Образец прогона:

c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]

Измените getsна, $*[0]если вы хотите аргументы командной строки ( >fibadd 100), хотя +1 символ.

С правильным выводом:

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'

'

Образцы прогонов:

c:\a\ruby>fibadd
100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946

2+5+8+13+233+1597+10946

2+5+21+89+144+1597+10946

2+5+21+233+610+987+10946

2+5+21+233+1597+4181+6765

2+5+8+13+89+144+1597+10946

2+5+8+13+233+610+987+10946

2+5+8+13+233+1597+4181+6765

2+5+21+34+55+144+1597+10946

2+5+21+89+144+610+987+10946

2+5+21+89+144+1597+4181+6765

2+5+21+233+610+987+4181+6765

2+5+8+13+34+55+144+1597+10946

2+5+8+13+89+144+610+987+10946

2+5+8+13+89+144+1597+4181+6765

2+5+8+13+233+610+987+4181+6765

2+5+21+34+55+144+610+987+10946

2+5+21+34+55+144+1597+4181+6765

2+5+21+89+144+233+377+987+10946

2+5+21+89+144+610+987+4181+6765

2+5+21+233+610+987+1597+2584+6765

2+5+8+13+34+55+144+610+987+10946

2+5+8+13+34+55+144+1597+4181+6765

2+5+8+13+89+144+233+377+987+10946

2+5+8+13+89+144+610+987+4181+6765

2+5+8+13+233+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+10946

2+5+21+34+55+144+610+987+4181+6765

2+5+21+89+144+233+377+987+4181+6765

2+5+21+89+144+610+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+10946

2+5+8+13+34+55+144+610+987+4181+6765

2+5+8+13+89+144+233+377+987+4181+6765

2+5+8+13+89+144+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+4181+6765

2+5+21+34+55+144+610+987+1597+2584+6765

2+5+21+89+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+4181+6765

2+5+8+13+34+55+144+610+987+1597+2584+6765

2+5+8+13+89+144+233+377+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+1597+2584+6765

Этот последний (12804) занял всего около 3 секунд!

Дверная ручка
источник
4

Mathematica, 89 85 символов

Сокращено до 85 символов благодаря Дэвиду Каррахеру.

i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column

Mathematica имеет встроенную функцию Fibonacci, но я не хочу ее использовать.

alephalpha
источник
Очень компактный Ницца.
Доктор Велизарий
1
76 символов, если вы не против печатать в виде списка сумм:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]
DavidC
1
84 i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &] // Column
символа
2

питон 206 181 персонажа

import itertools as a
i,j,v,y=1,2,[],input()
while i<1000000:v,i,j=v+[i],j,i+j
for t in range(len(v)+1):
 for s in a.combinations(v,t):
  if sum(s)==y:print "+".join(map(str,s))+"\n"

Пробный прогон:

25
1+3+21

1+3+8+13

1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
Бэтмен
источник
Избавьтесь от всех этих лишних пробелов. Вы можете использовать одну табуляцию или пробел для отступа кода. Кроме того, запись кодов циклов в одну строку, когда это возможно, короче, т. while i<1000000:v+=[i];i,j=j,i+j
Е.
Некоторые предложения (я не хотел просто заниматься плагиатом вашего ответа и опубликовать свою сокращенную версию): import itertools as zудалите символы новой строки после двоеточий, вставьте их y=input()в x,y,vстроку и удалите лишний пробел после заключительного ifутверждения.
SimonT
Я включил ваши предложения в коде. Спасибо :)
Бэтмен
2

Скала, 171

def f(h:Int,n:Int):Stream[Int]=h#::f(n,h+n)
val x=readInt;(1 to x).flatMap(y=>f(1,2).takeWhile(_<=x).combinations(y).filter(_.sum==x)).foreach(z=>println(z.mkString("+")))
Дэн Г
источник
2

C #, 376 байт

class A{IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}static void Main(){new A().C(int.Parse(Console.ReadLine()));}}

Ungolfed:

class A
{
    IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}
    void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}
    static void Main(){new A().C(int.Parse(Console.ReadLine()));}
}

Метод Bвозвращает значение IEnumerable, представляющее весь (бесконечный) набор Фибоначчи. Второй метод, учитывая число n, просматривает первые nчисла Фибоначчи (здесь огромный перебор), находит все возможные подмножества (набор мощностей), а затем фильтрует до подмножеств, чья сумма точно n, и затем печатает.

Бен Райх
источник
1

APL (75)

I←⎕⋄{⎕←⎕TC[2],1↓,'+',⍪⍵}¨S/⍨I=+/¨S←/∘F¨↓⍉(N⍴2)⊤⍳2*N←⍴F←{⍵,+/¯2↑⍵}⍣{I<⊃⌽⍺}⍳2

Менее конкурентоспособен, чем хотелось бы, в основном из-за формата вывода.

Вывод:

⎕:
      100

 3 + 8 + 89 

 3 + 8 + 34 + 55 

 3 + 8 + 13 + 21 + 55 

 1 + 2 + 8 + 89 

 1 + 2 + 8 + 34 + 55 

 1 + 2 + 8 + 13 + 21 + 55 

 1 + 2 + 3 + 5 + 89 

 1 + 2 + 3 + 5 + 34 + 55 

 1 + 2 + 3 + 5 + 13 + 21 + 55

Объяснение:

  • I←⎕: читать ввод, хранить в I.
  • ⍳2: начиная со списка 1 2,
  • {⍵,+/¯2↑⍵}: добавить сумму двух последних элементов в список,
  • ⍣{I<⊃⌽⍺}: before Iменьше, чем последний элемент списка.
  • F←: сохранить в F(это числа Фибоначчи от 1до I).
  • N←⍴F: сохранить количество чисел Фибоначчи в N.
  • ↓⍉(N⍴2)⊤⍳2*N: получить числа от 1до 2^N, как биты.
  • S←/∘F¨: использовать каждый из них как битовую маску F, хранить в S.
  • I=+/¨S: для каждого подсписка в S, посмотрите, равна ли его сумма I.
  • S/⍨: выберите их из S. (Теперь у нас есть все списки чисел Фибоначчи, которые суммируются с I.)
  • {... }¨: для каждого из них:
    • ,'+',⍪⍵: добавьте +перед каждым номером,
    • 1↓: убери первый +,
    • ⎕TC[2]: добавить дополнительный перевод строки,
    • ⎕←и вывод.
Мэринус
источник
1

Haskell - 127

После многих итераций я получил следующий код:

f=1:scanl(+)2f
main=getLine>>=putStr.a f "".read
a(f:g)s n|n==f=s++show f++"\n\n"|n<f=""|n>f=a g(s++show f++"+")(n-f)++a g s n

Я мог бы сохранить, может быть, один символ, обманув и добавив дополнительный «0+» перед каждой выходной строкой.

Я хочу поделиться другой версией (длина 143), которую я придумал, пытаясь сыграть в гольф предыдущее решение. Я никогда раньше не злоупотреблял операторами и кортежами так сильно:

f=1:scanl(+)2f
main=getLine>>=(\x->putStr$f€("",read x))
o%p=o++show p;(f:g)€t@(s,n)|n==f=s%f++"\n\n"|n<f=""|n>f=g€(s%f++"+",n-f)++g€t

Тестовые случаи, 256:

256
2+3+5+13+34+55+144

2+3+5+13+89+144

2+3+5+13+233

2+8+13+34+55+144

2+8+13+89+144

2+8+13+233

2+21+34+55+144

2+21+89+144

2+21+233

и 1000:

1000
2+3+8+21+34+89+233+610

2+3+8+55+89+233+610

2+3+8+144+233+610

2+3+8+377+610

2+3+8+987

5+8+21+34+89+233+610

5+8+55+89+233+610

5+8+144+233+610

5+8+377+610

5+8+987

13+21+34+89+233+610

13+55+89+233+610

13+144+233+610

13+377+610

13+987

Некоторые данные об эффективности, так как кто-то имел этот материал:

% echo "12804" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  0.09s user 0.00s system 96% cpu 0.100 total
% echo "128040" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  2.60s user 0.01s system 99% cpu 2.609 total
shiona
источник
0

05AB1E , 19 байт (не конкурирует)

ÅFævy©O¹Qi®'+ý}})ê»

Попробуйте онлайн!

Рассчитывает все возможные суммы для любой данной n. Пример вывода на 1000:

1+1+3+8+144+233+610
1+1+3+8+21+34+89+233+610
1+1+3+8+377+610
1+1+3+8+55+89+233+610
1+1+3+8+987
13+144+233+610
13+21+34+89+233+610
13+377+610
13+55+89+233+610
13+987
2+3+8+144+233+610
2+3+8+21+34+89+233+610
2+3+8+377+610
2+3+8+55+89+233+610
2+3+8+987
5+8+144+233+610
5+8+21+34+89+233+610
5+8+377+610
5+8+55+89+233+610
5+8+987
Урна волшебного осьминога
источник