有如下需求的随机数算法大赛。。。求最好的程序（速度，可读性）(200分)

  • 主题发起人 主题发起人 千中元
  • 开始时间 开始时间
看完这段讨论，我认为："千中元" 根本就是罪魁祸首，帖了一段误人子弟的code
然后大家就开始讨论、改进这个算法。换一个算法不行吗？

这种东西，概率书上很多，不过惭愧的很，我都忘光了。

“这四个随机数中，任意两个地差值不大于5。”
假设 这四个数从小到大为 ： A 、B、C、D
则 D － A < 6

我们先产生一个数 A 好了： A ：＝ Random(70)


然后我们产生两个随机数m,n， 其中 m!=n
0<m,n<6;
然后：
count := 0;
for i:= 0 to 5 do
if (i<>m) and (i<>n) then
begin
R[count]:= A+i;
Inc(count);
end;

“求在85到165之间的4个随机数，” 故 最后要把R中的数调整一下

上述的具体思想就是： 先产生最小的数A 然后认为；A＋1，A＋2，A＋3，A＋4，A＋5均为候选的数
然后再随机淘汰这后面5个数中的任意两个。我写的code没有试过，可能有问题，但是这个方法绝对可以。



 
to 白马小将:
您的算法的确不用循环。但是，为了产生C(6,4)的结果表，还是要使用循环的。不过，对于多次循环，您的算法
只要计算一次结果表就可以了（不过产生C(6,4)的结果表的时间比我的算法可要多上好几倍哟 :) ）。
对于本问题，您的算法的空间复杂度是完全可以接受的。但是C(M,N)的增长速度实在太快了。
您的算法还有一个问题，与lha的一样。如要解决这个问题，就必须用P(6,4)而不是C(6,4)（或者加一个P(4,4)
的对照表也可以）。

to addie:
>代码用移位更漂亮
怎么移位？

to lha:
>随机淘汰这后面5个数中的任意两个
思路很好，可是您的算法产生的结果是按大小排序的，即： R1<R2<R3<R4
好像不是完全随机的。解决方法见上。
 
既然大家都在讨论算法问题，那我也来插几句：

//这四个随机数中，任意两个地差值不大于5
继承 lha 的方法：
从1～6之中随机淘汰两个数，剩下的 4 个数组成一链表，再循环取出链表中的
随机位置的数，可以实现不重复、排列不均匀了。
然后就可以加到 a 后面了。
 
老千，不要缩手缩脚的嘛，出来说句话啊？^_^
 
我这样想：
　　既然任意两个数之间的差不能大于5，那也就是说，如果最小的数为85，则最大的
数最大为90，如果最大的数为165，则最小的数此时最大为162。———也就是说，最小
的数的取值范围是：85-162。
　　这样，我们先随机在85-162中，取最小的数，比如n，然后再在这个最小的数的基
础上+5，即得到最大数的上限n+5（不是最大数），再在这个区间[n+1,n+5]内随机取
三个数(n已经取过了)。不就成了！
 
>再循环取出链表中的随机位置的数
对算法来说，最重要的是时空复杂度。如果使用链表的话，光是取出某个数的耗时就是O(n)，
再加上循环，耗时就是O(n^2)。类似的问题早已在《电脑爱好者》中讨论过，链表没有数组快。
如果一定要继承lha的方法，我的想法是，仿照白马小将的方法，先生成一个P(4,4)的对照表：
P[0][4]={0,1,2,3}
P[1][4]={0,1,3,2}
P[2][4]={0,2,1,3}
...
在找到一组解R[0]..R[3]之后进行如下运算：
d:=Random(24)
//4的全排列
for i:=0 to 3 do
R_:=R[P[d]];
由此得到的 R_ 就是完全随机的了。（这么复杂！——我已经尽力了）
 
呵呵，我们还没有学 算法 ，你说这些，我可就没有办法了 :-(
 
说明是随机机会应该均等．不然最快的也没有达到题意．
很明显你们的机会都不是均等的．
 
随机本身就不是均等的，只有轮流就会才均等
 
就和莫彩票一样，看是每一个人都有机会摸到，但摸到的只有几个人，而且
同样不排除摸到过的人以后就不能再摸到。或许一个人摸中了好几次，而其
他人一次也没摸中。只有轮流，每个人都有一次后才能有第二次的可能。
 
老千，拿分来。。。。。。。。。。。。

把前面我的算法求精一下
因为1字节比所求的值要大，所以字节间不会有进位，
而1个字刚好是4个字节，所以用1个字来表示4个数

问题重述：
要求4个数，他们之间相差不超过5
并且不允许重复，那么他们只有下面几种可能性
（为了表述方便简化一下
a ,a+1,a+2,a+3,a+4,a+5改为
0 ，1 ，2 ，3 ，4 ,5 ）
c(6,4)=15
const abc:array[0..14] of word =
//初始化，编译的时候进行，运算的时候不消耗时间
（编号0）$00010203
（编号1）$00010204
（编号2）$00010205
（编号3）$00010304
.....
（编号14）$02030405;

算法如下，
begin
a:=random(76);//这里得改为76，因为。。。
b:=random(15);//由b来判断取那个，如是0则选编号0的那组
temp:=a+abc;
answer[0]:=temp and $ff000000;//取第一个字节
answer[1]:=temp and $00ff0000;
answer[2]:=temp and $0000ff00;
answer[3]:=temp and $000000ff;
end
算法复杂度肯定低啦，连循环都不要，只是多消耗了15个字的空间，我想这个还是值得的。
并且如果改过程被多次调用的话，效率会更高。
 
to 白马小将:
我已经说过了：您的算法产生的结果是按大小排序的，如要解决这个问题，就必须用P(6,4)而不是C(6,4)
（或者加一个P(4,4)的对照表也可以）。不过，即使这样做，空间复杂度也是完全可以接受的(360)。
如果只是针对本问题，我无话可说。

>连循环都不要
您只是将循环变相为4个 answer[?]:=temp and $????????
如果要取的数是200个而不是4个，您还不用循环吗？
依我看，只有这样做，才能达到真正的“不用循环”的境界（仅针对本问题）：
PDWord(@answer[0])^:=temp
//一次性将4Bytes写过去。answer为Byte数组
我们的运气太好了，老千只要取4个介于0-255之间的数。

还有， answer[0]:=temp and $ff000000
得到的数难道会介于0-255之间吗？还要右移24位吧。
一个Word显然不能容纳$02030405，应该使用DWord。因此，空间复杂度应该为：360*4=1440Bytes
 
老千，怎么还不结束？
 
对，word是2字节
最近老是搞s390，昏头了。不好意思。
 
接受答案了.
 
您必须登录或注册才可回复。

Similar threads

T
关于算法的问题~~~请大家看看。 (1分)
回复
2
查看
216
tiger_520
T
G
有关Random随机数发生器(100分)
回复
4
查看
217
jomee
J
H
查询的速度太慢了，呜呜呜……(求SQL程序)(100分)
回复
7
查看
179
hawlj
H
N
有关产生随机数的问题！！！散分啦(100分)
2
回复
21
查看
377
nzfboy
N
Q
求各位大虾帮忙调试程序！(50分)
回复
4
查看
221
qifenglin
Q
后退
顶部