Биномиальный коэффициент с использованием хвостовой рекурсии / аккумулятора в Прологе - PullRequest
Новая
       84

Биномиальный коэффициент с использованием хвостовой рекурсии / аккумулятора в Прологе

0 голосов
/ 18 июня 2020

Есть ли способ запрограммировать вычисление C (n, k) с использованием хвостовой рекурсии / аккумулятора в Prolog? Я не могу понять, как «перевернуть» classi c рекурсивную формулу C (n, k) = C (n-1, k-1) + C (n-1, k). Может, есть еще способы?

1 Ответ

0 голосов
/ 18 июня 2020

Вы можете сделать это с помощью обычной рекурсии, я нашел этот ответ благодаря ответу Омри Барела на треугольнике Pascal, который тесно связан с биномиальным коэффициентом. 

c(N,K,Out):-calc(N,K,1,0,Out),!.

calc(_,K,Out,K,Out).
calc(N,K,Prev,Count,Out):-
    C2 is Count+1,
    NewPrev is Prev*(N-Count)/C2,
    calc(N,K,NewPrev,C2,Out).

Когда вы генерируете треугольник pascal и рассматриваете его как 2-мерную матрицу PT с нулевым индексом. C (n, k) равно PT (n, k).

Итак, чтобы найти C (n, k), вы можете сгенерировать n-ю строку треугольника и найти th k -й индекс. На самом деле вам не нужна хвостовая рекурсия, поскольку для вычисления (k + 1) -го индекса строки Pascal вам нужно знать только значение k-го индекса. (Который помечен как Prev)

Изменить: чтобы завершить домашнее задание sh OP, эта версия явно использует аккумулятор и хвостовую рекурсию. 

c(N,K,Out):-calc(N,[1],List),
    elemAt(K,List,Out).

calc(N,[H|T],Out):-length(T, N),
    Out = [H|T],!.
calc(N,[H|T],Out):-
    length(T, Length),
    X is H*((N-Length)/(1+Length)),
    RX is round(X),
    calc(N,[RX|[H|T]],Out).

elemAt(0,[H|_],H).
elemAt(K,[_|T],Out):-
    K2 is K-1,
    elemAt(K2, T, Out).
...