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

  • 主题发起人 千中元
  • 开始时间
千

千中元

Unregistered / Unconfirmed
GUEST, unregistred user!
求在85到165之间的4个随机数，
这四个随机数中，任意两个地差值不大于5。
先把我写的（应该是本次比赛最后一名。。555）贴出来：
var
a: integer;
Temp:integer;
i,j:integer;
exist:boolean;
N:array [0..3] of integer;
begin
randomize;
a:=random(81)+85
//165-85=80;现在先在85---160之间得到一个随机数字
for i:=1 to 4 do //当i=2时候
begin
Exist:=false;
repeat
Temp:=random(5)+a;//范围为5
特别耗费时间。如果范围扩大，则不会出现这样的情况。如random(500);

for j:=0 to i-1 do
begin
if Temp=N[j] then

begin
Exist:=true;
break;
end

end;
if (not exist) then

N[i-1]:=Temp;
until not Exist

end;
end;
上面程序存在地问题就是，
random(5)以后就差不多陷入死循环了---虽然逻辑上是可以不死循环的，
但是运行起来确实是n 分钟不动。。
谁能写出来更好的..来练练手吧。
(洗牌算法。。等)
 
procedure TForm1.Button9Click(Sender: TObject);
var
a:integer;
Temp:integer;
i,j:integer;
M:array[0..5]of Integer;
begin
randomize;
a:=random(81)+85;
for i:=0 to 5 do
M:=a+i;
for i:=0 to 3 do
begin //此算法将被选中的数放到数组头部，然后再剩下的数中进行选取
j:=random(5-i)
//每循环一次范围减1
Temp:=M
//交换M和M[j]
M:=M[j];
M[j]:=Temp;
end;
Caption:='';
for i:=0 to 3 do //输出数组头部的元素
Caption:=Caption+' '+IntToStr(M);
end;
 
哦！有点问题，再改一下：

j:=random(6-i)+i
//每循环一次范围减1

OK！
 
Temp:=random(5)+a;//范围为5
特别耗费时间。如果范围扩大，则不会出现这样的情况。如random(500);
那就变通一下，改成
temp:=random(500) mod 5 +a ,不知道这样行不行？
 
咳，俺的小学数学得再学：
》a:=random(81)+85
//165-85=80;现在先在85---160之间得到一个随机数字
改成a:=random(81)+80
to 白马小将：
嗯，不知道为何，改成random(500) mod 5也是长时间没响应，而random(500)
就很快出来结果
 
还有一个问题，不看速度，您的算法得到的随机数的分布不是绝对均匀的（当然我的算法也一样），
理由如下：

将问题简化，改为——从1..5中随机取两个数字，使它们的差不大于2，分析结果如下：
产生的选取区间：1..3, 2..4, 3..5 ——概率均为1/3
各个搜索区间中可能得到的结果及其出现概率：
1..3: 1 2, 2 3, 1 3 --各1/3
2..4: 2 3, 3 4, 2 4 --各1/3
3..5: 3 4, 4 5, 3 5 --各1/3
这样就出现了一个问题：结果“2 3”与“3 4”出现的概率明显比其它结果的概率要高。

解决此问题的办法：先计算从1..3中取任意两个数的结果，得到这两个数的最大值与最小值Max Min，
然后将这个结果加上Random(5-(Max-Min))-Min+1（使结果均匀的分布），就得到了绝对均匀的最终结果。
例如：若产生了 1 2 ，则最终结果可能为： 1 2, 2 3, 3 4, 4 5 ——各个结果概率相等
若产生了 1 3 ，则最终结果可能为： 1 3, 2 4, 3 5 ——各个结果概率相等
若产生了 2 3 ，则最终结果与 1 2 时相同

若要将此方法推广到更一般的情况，只要进行选取最大最小值的运算就可以了。 OK!
 
你这种算法跟题目都不符。
 
creation-zy兄程序的后部分好像就是类似洗牌的算法。
将
》for i:=0 to 3 do
》 begin //此算法将被选中的数放到数组头部，然后再剩下的数中进行选取
》 j:=random(6-i)＋i
//每循环一次范围减1
》 Temp:=M

改作for i:=0 to 5 do
则更容易出现两数差值正好为5的情况（for i:=0 to 3 do 运行了几次，差值最大的都是
4）
 
老千：
您的算法之所以很慢，主要是因为您用了一个循环产生0..5随机数，并且每产生一个数就检查它是否与前面
产生的随机数重叠，而四个差值小于5的数字发生重叠的概率实在是太大了（还有，您使用的Random(5)的值域
是0..4——差值不大于4!?），所以选取一个未被使用的数很耗时。至于在改为Random(500)之后变快——显然
是因为从500个数中任取四个数，这几个数发生重叠的概率很小——可是这样做显然违反了“差值不大于5”的
要求。
在我的算法中，先构造值域a..a+5，然后用一个循环从这个值域中随机选取一个数字，每选中一个数，就将
其放到数组的排头去，然后在更小的范围内搜索下一个数，这样做的好处就是绝对不会发生重复选择的现象，
因此就不用再花时间检查是否重合——这是我所知道的随机不重复取数的最有效算法。
 
>改作for i:=0 to 5 do则更容易出现两数差值正好为5的情况
完全不用。我的算法在数学上是正确的，不用增加循环次数。再说，增加循环次数并不能影响
M[0]..M[3]的值。
我只试了4次就出现了差值为5的情况—— 90-95
还有，根据排列组合的原理，出现差值为5的概率的确比较小，差值为3-4的概率就大得多。
 
老千特地把我召来，原来是帮我练手 :)

老千啊，你原来那个就是死循环啊，把我的 Delphi 都搞死了，害我重启 :-(
（我还是用的单步跟踪）

问题不是出在 Random(5), 而是出在 if Temp=N[j] then
在我的 WatchList 里面，在 i 取某一个值(不一定)的时候，
j 始终显示为 InAccessable （不可访问）！
于是 if 始终不能满足，于是就一直 loop

至于creation-zy兄说的“四个差值小于5的数字发生重叠的概率实在是太大了”
我想，这的确存在，但是这不是问题，凭我们现在的机器，绝对能够对付

当然有更好的生成不重复的随机数的方法，比如用链表
每次得到一个随机数过后，从链中取出该值，下次无论如何也不会得到相同的值了
（就不用具体写出来了吧 :p）
 
老千啊，你的算法有毛病啊！
总算找到了！

repeat
Temp:=random(5)+a;//范围为5
特别耗费时间。如果范围扩大，则不会出现这样的情况。如random(500);

for j:=0 to i-1 do
begin
if Temp=N[j] then
begin
Exist:=true;
break;
end;
end;

if (not exist) then
N[i-1]:=Temp;
until not Exist;

看一下，要是有一次重复，那么就死定了！！！
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
当重复的时候，Exist 为 True，从 for 里面 break 出来，
然后回到 repeat 的第一行，看一看，你现在地 Exist 还是
True 吧！因此，即使 if Temp=N[j] then 不满足，没有给
Exist 再次赋值为 True，但是 Exist 本来就已经是 True
~~~~ ~~~~~~~~~~~~~~~~~
于是又循环………………

修改也很简单，将 Exist:=false
移到 repeat 里面去
我已经调试通过了，尽管重复的几率很大，但是还是一眨眼就
~~~~~~~~~~~~~~~~
运行完了！

解决了！
 
贴出修改后的源代码：

procedure TMainForm.ToolButton1Click(Sender: TObject);
var
a: integer;
Temp:integer;
i,j:integer;
exist:boolean;
N:array [0..3] of integer;
begin
randomize;
a:=random(81)+85
//165-85=80;现在先在85---160之间得到一个随机数字
for i:=1 to 4 do //当i=2时候
begin
repeat
Exist:=false;
~~~~~~~~~~~~~移到这里来了！！！！！！！（其他均未改）
Temp:=random(5)+a;//范围为5
特别耗费时间。如果范围扩大，则不会出现这样的情况。如random(500);

for j:=0 to i-1 do
begin
if Temp=N[j] then
begin
Exist:=true;
break;
end;
end;

if (not exist) then
N[i-1]:=Temp;
until not Exist;
end;
showmessage('搞定！');
end;

点击按钮，一眨眼，对话框就弹出来了。
没想到老千也会犯这种低级错误 :p
 
procedure TForm1.Button1Click(Sender: TObject);
var
a:integer;
Temp:integer;
i,j:integer;
N:array [0..5] of integer;
M:array [0..3] of integer;//存放结果
begin
randomize;
a:=random(81)+85;
for i:=0 to 5 do
begin
N:=a+i;
end;
for j:=0 to 3 do
begin
Temp:=random(6-j);
M[j]:=N[Temp];
for i:= Temp to 4 do
begin
N:=N[i+1];
end;
end;
edit1.text:=inttostr(M[0]);
edit2.text:=inttostr(M[1]);
edit3.text:=inttostr(M[2]);
edit4.text:=inttostr(M[3]);
end;
 
呵呵，还是beta兄行！
我也认为尽管会出现重复，也应该能够在ms级解决问题，原来是这一句写错位置了。

to feishu:
总算把您的 for i:=Temp to 4 do N:=N[i+1]
看懂了，思路很独特。（不过常量4应该
随j变化才能提高效率吧）。
您的算法也实现了不重复取数的功能，不过比俺的多了一个循环，效率嘛...
 
怎么没有贴上？？
再来一次

问题重述：
要求4个数，他们之间相差不超过5
并且不允许重复，那么他们只有下面几种可能性
（为了表述方便简化一下
a ,a+1,a+2,a+3,a+4改为
0 ，1 ，2 ，3 ，4）

c(5,1)=5
0，1，2，3 （少4）
0，1，2，4 （少3）
0，1，3，4 （少2）
0，2，3，4 （少1）
1，2，3，4 （少0）

所以算法如下，
begin
a:=random(81);
b:=random(5);//由b来判断减少那个，如是4则吧a+4去掉
......
end
算法复杂度肯定低啦，连循环都不要，呵呵

至于是否他们的概率分布就不算了，从感觉上应该是中间的相等，略高
向2边（离边界小于5）的逐渐降低
 
to 千中元
creation-zy的算法和咱们昨天讨论的一样，但代码用移位更漂亮。
 
帮 白马小将 贴的：

昨天的解答有2个问题，1是a的上限错误，2是没有考虑这4个数之差等于5

的情况
改正一下。

问题重述：
要求4个数，他们之间相差不超过5
并且不允许重复，那么他们只有下面几种可能性
（为了表述方便简化一下
a ,a+1,a+2,a+3,a+4,a+5改为
0 ，1 ，2 ，3 ，4 ,5 ）
c(6,4)=15
（编号0）0，1，2，3
（编号1）0，1，2，4
（编号2）0，1，2，5
（编号3）0，1，3，4
.....
（编号14）2，3，4，5
所以算法如下，
begin
a:=random(76);//这里得改为76，因为。。。
b:=random(15);//由b来判断取那个，如是0则选编号0的那组
......
end
算法复杂度肯定低啦，连循环都不要，呵呵
 
to creation-zy:
多谢指教，那处应为4-j，你的交换法确实很好
 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
一个关于矩阵的算法
回复
0
查看
706
import
I
I
如何求出包围任意折线多边形的最小矩形
回复
0
查看
627
import
I
I
常用算法（3）动态规划
回复
0
查看
866
import
I
顶部