Подсчет фонтанов

17

Фонтан является расположение монет в строках , так что каждая монета касается двух монет в строке ниже ее, или находится в нижнем ряду, а нижний ряд соединен. Вот фонтан из 21 монеты:

От http://mathworld.wolfram.com/Fountain.html

Ваша задача состоит в том, чтобы подсчитать, сколько разных фонтанов можно сделать с заданным количеством монет.

В качестве входных данных вы получите положительное целое число n. Вы должны вывести количество различных nфонтанов-монет, которые существуют.

Стандартные правила ввода / вывода, стандартные лазейки запрещены. Решения должны быть в состоянии рассчитать n = 10в течение минуты.

Желаемый вывод для n = 1 ... 10:

1, 1, 2, 3, 5, 9, 15, 26, 45, 78

Эта последовательность OEIS A005169 .

Это код гольф. Побеждает несколько байтов.

code-golf sequence combinatorics isaacg
источник
Есть ли nдля чего программа должна быть гарантированно работать? (то есть после чего он может сломаться)
квинтопия
@quintopia Это должно работать для всех n, вплоть до ограничений типа данных, аппаратного обеспечения и т. д.
isaacg

Ответы:

3

Python, 57 байт

f=lambda n,i=0:sum(f(n-j,j)for j in range(1,i+2)[:n])or 1

Как отмечалось в OEIS , если вы сдвигаете каждую строку на полшага относительно строки под ней, размеры столбцов образуют последовательность натуральных чисел с максимальным шагом вверх 1.

Функция f(n,i)считает последовательности с суммой nи последним числом i. Они могут быть рекурсивно суммированы для каждого выбора следующего размера столбца от 1до i+1, то есть range(1,i+2). Усечение до range(1,i+2)[:n]препятствует тому, чтобы столбцы использовали больше монет, чем осталось, избегая необходимости говорить, что отрицательный nдает 0. Более того, он избегает явного базового случая, поскольку пустая сумма 0рекурсивна, а не рекурсивна, но вместо этого ее f(0)необходимо установить 1, для чего or 1достаточно (как было бы +0**n).

XNOR
источник
17 байтов в M|sgL-Gd<ShHG1gQ0
Pyth
5

Mathematica, 59 байт

SeriesCoefficient[1-Fold[1-x^#2/#&,Range[#,0,-1]],{x,0,#}]&

Основано на программе Mathematica по OEIS Жана-Франсуа Альковера.

alephalpha
источник
Можете ли вы переписать это как формулу (я просто хочу сравнить с формулой, которую я нашел)? Я просто не могу прочитать Mathematica =)
flawr
@flawr Производящая функция последовательности 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))).
alephalpha 26.12.15
Спасибо за объяснение, это действительно хороший подход, если у вас есть такой мощный CAS =)
flawr
3

Haskell, 60 48 байтов

Спасибо @nimi за более короткое решение!

n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1
(#1)

Старая версия.

t n p|p>n=0|p==n=1|p<n=sum[t (n-q) q|q<-[1..p+1]]
s n=t n 1

Функция вычисления значения: sреализация рекурсивной формулы, найденная здесь: https://oeis.org/A005169

flawr
источник
Баг: рекурсивный вызов есть t (n-p) q. Игра в гольф советы: используйте оператор инфиксную для tсмените охранников и использовать mapвместо списка понимания: n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1. sстановится s=(#1), но вам не нужно вообще давать имя главной функции, так (#1)что этого достаточно. 48 байтов.
Ними
Спасибо большое за подсказки! Я только начал изучать основы Haskell. Я собираюсь узнать о том, как использование #и $здесь, во-первых =)
flawr
Немного объяснений: #это определенный пользователь функция инфикса так же , как +, *и т.д. функции инфиксных предопределена. $это другой способ настроить приоритет (кроме скобок) f (g (h x))-> f$g$h xили в нашем случае sum(map(...)[...])-> sum$map(...)[...].
nimi
Спасибо, это очень полезно знать, я ценю ваше объяснение!
flawr
3

Haskell, 43 байта

n%i=sum[(n-j)%j|j<-take n[1..i+1]]+0^n
(%0)

Смотрите Python ответ для объяснения.

Та же самая длина с minчем take:

n%i=sum[(n-j)%j|j<-[1..min(i+1)n]]+0^n
(%0)
XNOR
источник
1

Matlab, 115 105 байт

function F=t(n,varargin);p=1;if nargin>1;p=varargin{1};end;F=p==n;if p<n;for q=1:p+1;F=F+t(n-p,q);end;end

Реализация рекурсивной формулы найдена здесь: https://oeis.org/A005169

function F=t(n,varargin);
p=1;
if nargin>1
    p=varargin{1};
end;
F=p==n;
if p<n;
    for q=1:p+1;
        F=F+t(n-p,q);
    end;
end;
flawr
источник
1

Юлия, 44 43 байта

f(a,b=1)=a>b?sum(i->f(a-b,i),1:b+1):1(a==b)

Это использует рекурсивную формулу на OEIS.

объяснение

function f(a, b=1)
    if a > b
        # Sum of recursing
        sum(i -> f(a-b, i), 1:b+1)
    else
        # Convert bool to integer
        1 * (a == b)
    end
end

Кто-нибудь еще заметил, что удар через 44 - это обычный 44 ??

Факс
источник
0

Python 3, 88 байт

f=lambda n,p:sum([f(n-p,q)for q in range(1,p+2)])if p<n else int(p==n)
t=lambda n:f(n,1)
монопольный
источник
0

JavaScript (ES6), 63

Реализация рекурсивной формулы на странице OEIS

F=(n,p=1,t=0,q=0)=>p<n?eval("for(;q++<=p;)t+=F(n-p,q)"):p>n?0:1
edc65
источник