回 帖 发 新 帖 刷新版面

主题:有人能帮我降低这个程序的时间复杂度吗?

program test;{程序的功能是产生一个1-80的随机数列,数列中的数在1-80之间,没有重复}
type a=array[1..80] of integer;
var
   i,temp:integer;
   data:a;{一个用于存放生成数列的数组}
   check:a;{一个用于标识该数是否出现过的数组,程序设想是}
            {比如8已经出现过,则check[8]将被置为1,所以程序运行中只有当随机产生的数对应在check数组中的标识不为1时,才能赋给数组data}
begin
   for i:=1 to 80 do
   check[i]:=0;
   for i:=1 to 80 do
   begin
   repeat
   randomize;
   temp:=random(81);
   if temp=0 then temp:=1;
   until check[temp]=0;

   data[i]:=temp;
   check[temp]:=1;
   end;
   for i:=1 to 80 do
   begin
   write(data[i]:4);
   if i mod 4=0 then writeln;
   end;
end.
程序可正常运行,问题是运行时间需要将近一分钟,太久了,各位有无办法帮忙改善一下

回复列表 (共4个回复)

沙发

呵呵!彩票抽奖?其实就是随意找出一组1-80的排列。你先把数列按顺序排,然后作n次(比如1000次)随意两个数交换。最终有序数列被打乱了,而且速度会快好多。

板凳

谢谢呀,这不失为一个好的办法,但是如果一定用RANDOM来随机产生的,有无办法改善呢

3 楼

硬要用RANDOM随机产生,你的程序对了。对于1-80,你的程序应该不慢。假如是1-1000,我不敢保证你的程序运行多长时间。

很遗憾的是,我写的东西,很少有人注意去看。我对你写过这样一句话:

===============================
不必要插在每个RANDOM(X)之前,我测试过如果那样的话,获得的随机数列效果会更差。开始用random前调用一下即可。
===============================

这就是你程序慢的原因。我只调你的一个语句randomize,可能很快出结果。原则上跟复杂度没关系,事实去对比,你就知道了。



program test;
type a=array[1..80] of integer;
var
   i,temp:integer;
   data:a;
   check:a;

begin
   randomize;
   for i:=1 to 80 do
   check[i]:=0;
   for i:=1 to 80 do
   begin
   repeat
   temp:=random(81);
   if temp=0 then temp:=1;
   until check[temp]=0;

   data[i]:=temp;
   check[temp]:=1;
   end;
   for i:=1 to 80 do
   begin
   write(data[i]:4);
   if i mod 4=0 then writeln;
   end;
end.

我的机上,运行后是一秒不到出结果。这就是我写那句话的原因。经验之谈,可惜很少人去注意它。

4 楼

谢谢啦,我之前理解错误了,我以为每调用RANDOM(X)之前使用RANDOMIZE一次,产生的数就会跟之前的不同,呵呵,不好意思,我初学这个东西,了解不多

我来回复

您尚未登录,请登录后再回复。点此登录或注册