读书人

关于完全剩余系解决办法

发布时间: 2012-04-11 17:42:33 作者: rapoo

关于完全剩余系
有没有一个表达式可以求得一个数的随机完全剩余系?

如, {0,1,2,3,4}是5的一个完全剩余系, 现在想求一表达式, 可以随机的生成5的一个完全剩余系, 就如{2,0,4,3,1}, {28, 501, 10, 1002, 49}之类, 只要生成的完全剩余系不是像{0, 1, 2, 3, 4}这样很规律出现的就行

谢谢

[解决办法]
假设对于数A,楼主要求的就是长度为A的随机序列{List},随机序列{List}满足:随机序列{List}的元素模A取遍[0,A)之间的数。

用随机洗牌算法,构造这样的随机序列是简单的。

楼主要表达式,也就要找随机序列的生成式,比较麻烦。

若用线性同余法,设{Y(i)}为求的随机序列,其线性同余生成式为Y(i+1)=(a*Y(i)+c) mod m.
《计算机程序设计艺术》中给出了如下定理:

{Y(i)}周期长度为m,当且仅当:
1):c与m互素
2):对整除m的每个素数p,b=a-1是p的倍数
3):如果m是4的倍数,则b也是4的倍数。

有了这个定理,对给定的模m(也就是A),就可以找到一个乘数a以及增量c使{Y(i)}周期长度为m。

可以看出,a由m的素数分解决定,因此找a的复杂度不低于将m分解的复杂度。

当然,随机序列的生成方法不止线性同余法一种,但线性同余法是最简单的一种了,所以最好控制,实现起来也最为方便,若用其他生成方法,就没有这些优点。

如果要的只是满足条件的随机序列{List},就没有必要自己写一个随机数发生器,直接用洗牌算法就可以了。

读书人网 >软件架构设计

热点推荐