问一算法题 - V2EX

This topic created in 4209 days ago, the information mentioned may be changed or developed.

输入：
5个整数
A, B, X1, K, M

有一个random算法
Xn = (A * Xn-1 + B) % M

要输出第K到K+4的X结果

老老实实写了如下python代码，问如何优化？
~~~
A, B, X1, K, M = map(int, raw_input().split())

def myRand(seed):
return (A * seed + B) % M

seed = X1
for i in xrange(1, K+5):
if i > K-1:
print seed
seed = myRand(seed)
~~~

seed

myrand

k+5

15 replies • 2014-12-15 18:50:36 +08:00

jiang42

Dec 14, 2014

不知道你想怎么优化？我能想到的就是map换成list comprehension。或者数学好的话把递归表达式直接写成直接求值的表达式。一般来说，O（n）的算法在实际生活中已经足够好了

czheo

Dec 14, 2014

我把代码提交上去，系统说运行超时，我只能想出O(n)的算法。不知道考点在哪里。
hint: 比如M极小的时候除余会不会变慢？

@jiang42 把递归表达式直接写成直接求值要怎么写？

iloahz

Dec 14, 2014 via iPhone

可以写出来通项公式的样子，要是嫌麻烦用矩阵也行噻

czheo

Dec 14, 2014

一软件公司出题让我求通项公式也太....

@iloahz 怎么个矩阵法？

akagi

Dec 14, 2014

同余吧循环节是M 打个表出来直接到里面取 —— 简单想了下不一定对

akagi

Dec 14, 2014

好像不太对…… 再想想去

iloahz

Dec 14, 2014 via iPhone

@akagi 对的呀，线性递推取模肯定是有循环节的，当M比较小的时候妥妥可以

@czheo 求通项又不是很麻烦啊，矩阵就是
[1, X1] * [1, B \n 0, A] ^ (n -1) = [1, Xn]嘛，如果你这么鄙视软件公司…那没准就是递推优化优化吧

jiang42

Dec 14, 2014

@czheo 可以提供提交的地址么？我去试试

组合数学，用母函数应该可以

akagi

Dec 15, 2014

@iloahz 不过考虑到随机数发生器的场景，M通常比较大就是了。

计算时还是通项比较靠谱，
x_2 = a * x_1 + b;
x_3 = a^2 * x_1 + b * a + b;
...
x_k = [ a^k-1 * x_1 + b * (1+a+a^2+...) ];
最后取个余得到结果，前面没影响。另外计算 (a^k-1)%M 和右侧等比数列可以用点小技巧，差不多这样。

whalegia

Dec 15, 2014

是这样吗？……
https://gist.github.com/whaleee/4a2ae06b6e5ef348c06c

这个输入数字大小有限制吗？感觉这么写没法处理很大的输入……

czheo

Dec 15, 2014

@akagi 通项不对吧，怎么证明最后求余和每步求余结果一样？

whalegia

Dec 15, 2014

其实我也觉得同项不太对

whalegia

Dec 15, 2014

但是我觉得答案里是有循环的，搞个 list 记录一下循环吧？

我去试试

akagi

Dec 15, 2014

@czheo

设
y_n = k * M + c;
y_(n+1) = A * (k * M + c) + B;
y_(n+2) = A^2 * (k * M + c) + A * B + B;
=>
x_n = c;
x_(n+1) = (A * x_n + B) % M;
x_(n+2) = (A * [(A * x_n + B) % M] + B) % M = ...

核心在于求余满足分配率。

czheo

Dec 15, 2014 via iPhone

akagi 百度说求余不符合分配律