时间戳

首页 > 解决方案 > Prolog - 制作清单

list - Prolog - 制作清单

问题描述

给定参数makelist(A,N,K,M,L) :-，应该展开，并且如果A,N,K,M,L>0Integer numbers with M>=2and Llist 应该返回 true：

[A^N mod M , A^(N+1) mod M , A^(N+2) mod M , ... , A*(N+K) mod M]

预期成绩 ：

| ?- makelist(10,2,1,10000,L).
L = [100,1000]
| ?- makelist(2,6,10,100,L).
L = [64,28,56,12,24,48,96,92,84,68,36]
| ?- makelist(12345678,3,8,100,L).
L = [52,56,68,4,12,36,8,24,72]
| ?- makelist(2,3000,5,7,L).
L = [1,2,4,1,2,4]
| ?- makelist(2,555000,5,17,L).
L = [1,2,4,8,16,15]
| ?- makelist(2,3000000,5,21,L).
L = [1,2,4,8,16,11]
| ?- makelist(142857,98765432,9,100,L).
L = [1,57,49,93,1,57,49,93,1,57]

我认为首先是通过将数字从到来实现K指数元素(N+K)0K

bet(N, M, K) :- N =< M, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).


makelist(A,N,K,M,L) :- bet(0,K,(N+K)),

标签： listprolog

解决方案

小指数的解决方案

模幂运算的一个众所周知的特性是：

x ^ n mod m = ( x mod m )^ n mod m

因此，对于具有小指数的大底，您可以使用以下代码：

makelist(A, N, K, M, L) :-
    A>0, N>0, K>0, M>0,
    K1 is N + K,
    findall(X, (between(N,K1,E), X is (A mod M)^I mod M), L).

以下是使用此代码找到的一些解决方案：

?- makelist(10,2,1,10000,L).
L = [100, 1000].

?- makelist(2,6,10,100,L).
L = [64, 28, 56, 12, 24, 48, 96, 92, 84|...].

?- makelist(12345678,3,8,100,L).
L = [52, 56, 68, 4, 12, 36, 8, 24, 72].

?- makelist(2,3000,5,7,L).
L = [1, 2, 4, 1, 2, 4].

?- makelist(2,555000,5,17,L).
L = [1, 2, 4, 8, 16, 15].

?- makelist(2,3000000,5,21,L).
L = [1, 2, 4, 8, 16, 11].

请注意，如果不使用此类属性，我们无法计算具有大指数的大底的答案：

?- X is 142857^98765432 mod 100.
ERROR: Stack limit (0.5Gb) exceeded

?- X is (142857 mod 100)^98765432 mod 100.
X = 1.

大指数的解决方案

但是，对于大指数，此代码效率非常低。例如：

?- time(makelist(142857,98765432,9,100,L)).
% 47 inferences, 115.328 CPU in -544348879559065600.000 seconds (?% CPU, 0 Lips)
L = [1, 57, 49, 93, 1, 57, 49, 93, 1|...].

因此，对于大指数n ，最好的方法是使用以下定义：

  • 如果n = 0，则x ^ n = 1
  • 否则，如果n = 1，则x ^ n = x
  • 否则，如果n是偶数，则x ^ n = ( x ^2)^( n /2)
  • 否则，如果n是奇数，则x ^ n = x*( x ^2)^floor( n /2)

有了这个定义，我们可以只使用 O(lg n ) 乘法来计算x ^ n 。基于它，我们可以定义以下谓词：

fast_pow(X, N, M, P) :-
    (   N < 32
    ->  P is (X mod M)^N mod M
    ;   (   X1 is (X mod M)^2 mod M,
            N1 is N//2,
            fast_pow(X1, N1, M, P1),
            (   N mod 2 =:= 0
            ->  P is P1
            ;   P is (X mod M)*P1  mod M ) ) ).

fast_makelist(A, N, K, M, L) :-
    A>0, N>0, K>0, M>0,
    K1 is N + K,
    findall(P, (between(N,K1,E), fast_pow(A,E,M,P)), L).

现在，我们有：

?- time(fast_makelist(142857,98765432,9,100,L)).
% 1,704 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [1, 57, 49, 93, 1, 57, 49, 93, 1|...].

推荐阅读