Prolog中使用尾递归/累加器的二项式系数
Prolog中使用尾递归/累加器的二项式系数
提问于 2020-06-18 19:44:44
有没有办法在Prolog中用尾递归/累加器编程计算C(n，k)？我不知道如何“逆”出经典的递归公式C(n，k) = C(n-1，k-1) + C(n-1，k)。也许，还有其他方法可以做到这一点呢？
回答 1
Stack Overflow用户
发布于 2020-06-18 22:16:31
你可以用正常的递归来做，我找到了这个答案，这要归功于帕斯卡三角形上的Omri Barel's answer，它与二项式系数密切相关。
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三角形并将其视为具有零索引的二维矩阵PT时。C(n，k)等于PT(n，k)。
因此，要找到C(n，k)，您可以生成三角形的第n行，并找到第k个索引。您实际上不需要尾递归，因为要计算Pascal行的(k+1)-th索引，您只需要知道第k个索引的值(被标记为Prev)。
编辑:为了完成运算作业，这个版本显式地使用了累加器和尾递归。
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).页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62449254
复制相关文章
相似问题
腾讯云开发者
