首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于完全剩余系解决办法

2012-04-11 
关于完全剩余系有没有一个表达式可以求得一个数的随机完全剩余系?如,{0,1,2,3,4}是5的一个完全剩余系,现在

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

如,   {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},就没有必要自己写一个随机数发生器,直接用洗牌算法就可以了。

热点排行