Prolog-使用累加器查找第N个斐波那契数
我有这个代码以相反的顺序生成斐波那契数列的列表。
fib2(0, [0]).
fib2(1, [1,0]).
fib2(N, [R,X,Y|Zs]) :-
N > 1,
N1 is N - 1,
fib2(N1, [X,Y|Zs]),
R is X + Y.
我只需要第一个元素。问题是这段代码false.在列表之后也给出了一个，所以我尝试获取第一个元素的所有尝试都失败了。有什么方法可以获取列表中的第一个元素，或者使用累加器计算第 N 个斐波那契数的任何其他方法。
提前致谢。
回答
我得到了这个对数步长O(log n) 的解决方案，甚至尾递归。
只是为了好玩，它还可以计算第 n 个卢卡斯数：
<pre>
fib(N, X) :-
powmat(N, [[0,1],[1,1]], [[1,0],[0,1]],
[[_,X],[_,_]]).
luc(N, Z) :-
powmat(N, [[0,1],[1,1]], [[1,0],[0,1]],
[[X,Y],[_,_]]), Z is 2*X+Y.
powmat(0, _, R, R) :- !.
powmat(N, A, R, S) :- N rem 2 == 0, !,
mulmat(A, R, H), M is N//2, mulmat(A, A, B), powmat(M, B, H, S).
powmat(N, A, R, S) :-
M is N//2, mulmat(A, A, B), powmat(M, B, R, S).
mulmat([[A11,A12],[A21,A22]],
[[B11,B12],[B21,B22]],
[[C11,C12],[C21,C22]]) :-
C11 is A11*B11+A12*B21,
C12 is A11*B12+A12*B22,
C21 is A21*B11+A22*B21,
C22 is A21*B12+A22*B22.
?- fib(100,X).
?- luc(100,X).
</pre>
<script src="http://www.dogelog.ch/lib/exchange.js"></script>你可以比较：
https://www.wolframalpha.com/input/?i=Fibonacci[100]
https://www.wolframalpha.com/input/?i=LucasN[100]
2021 年 6 月 28 日编辑：
这是一个非常快速的解释为什么矩阵算法有效。我们只需要证明斐波那契的一步是线性的。即这种递推关系导致线性矩阵：
F_{n+2} = F_{n}+F_{n+1}
要查看矩阵，我们必须假设矩阵 M 将向量b=[Fn,Fn+1]转换为向量b'=[F_{n+1}, F_{n+2}]：
b' = M*b
这个矩阵可能是什么？只需解决它：
|F_{n+1}| |0*F_{n}+1*F_{n+1}| |0 1| |F_{n} |
| | = | | = | | * | |
|F_{n+2}| |1*F_{n}+1*F_{n+1}| |1 1| |F_{n+1}|