在1000个数字里，随机挑选100个不重复的数字。求最优算法 -- 急(100分)

  • 主题发起人 主题发起人 吴剑明
  • 开始时间 开始时间
吴

吴剑明

Unregistered / Unconfirmed
GUEST, unregistred user!
我下午就要。哪个大哥有现成算法给一份。我马上要的。
 
哈哈！撞枪口了吧！

http://www.delphibbs.com/delphibbs/dispq.asp?lid=542886
 
var
a: array [1..1000] of Integer;
Len: Integer;
b: array [1..100] of Integer;
i: Integer;
Index: Integer;
begin
for i:=1 to 1000 do
a:=i;
Len:=1000;

Randomize;
for i:=1 to 100 do
begin
Index:=Random(Len)+1;
b:=a[Index];
a[Index]:=a[Len];
Dec(Len)
end
end;
 
我要求的是“不重复”
 
不知道你的原数那里来,给你思想,希望和你意
procedure TForm1.Button1Click(Sender: TObject);
var
outList:Tstringlist;
j:string;
begin
outlist:=Tstringlist.Create;
while outList.Count<100 do
begin
Randomize;
j:=inttostr(Random(1000));
if outlist.IndexOf(j)=-1 then
outlist.Add(j);
end;
outlist.SaveToFile('c:/1.txt');
end;
 
楼上的算法不是最优的。会比较慢。
我要最优算法
 
是的是的,那汇编的你要不要[:)]

你要给明条件吗,比如1000个数十分是固定的,还是随即的,等等
 
randomize;
s:=random(1000);
for i:=2 to 100 to
begin
s:=s+random(100);
end;
//s里面的就是你要的数。这个算法保证速度快，谁能和我比？？？
//大哥给分。
 
>>最优算法
请您仔细的看看我给出的帖子。在这个帖子中，已经有超过3种算法，都可以解决你的问题。

const
TotalNum=1000;
GetNum=10
//作为实验，仅取十个数
procedure TForm1.Button1Click(Sender: TObject);
var
a:integer;
Temp:integer;
i,j:integer;
M:array[0..TotalNum-1]of Integer
//在实际应用中，M可以是全局数组，只要进行一次初始化，
//就可以反复使用，因为计算过程中只会改变元素的相对顺序，而不会增加或减少元素
begin
Randomize;
for i:=0 to TotalNum-1 do
M:=i
//这个初始化过程可以摆到外面去，执行一次即可
for i:=0 to GetNum-1 do
begin //此算法将被选中的数放到数组头部，然后再剩下的数中进行选取
j:=random(TotalNum-i)+i
//每循环一次范围减1
Temp:=M
//交换M和M[j]
M:=M[j];
M[j]:=Temp;
end;
Caption:='';
for i:=0 to GetNum-1 do //输出数组头部的元素
Caption:=Caption+' '+IntToStr(M);
end;

to 楼上：
请问阁下的算法可能得到这个结果吗？？—— 1,2,3,...50,951,952,953...1000
 
to 楼上：
冒泡加随机,难怪最后[:D]

to狼牙
如果能这样的话
那就这样
for i:=1 to 1000
s[1]:=i
就得了,谁和我比?/
 
to gray:
在你的算法中，在循环的主体中用“outlist.IndexOf(j)=-1”，你可知道这样做的代价是
在数量级上增大算法的时间复杂度吗？（平均每次检索要花费(1+GetNum)/2/2的时间，总共
要检索GetNum次！）
我的复杂度: O(GetNum)
你的复杂度: O(GetNum*(1+GetNum)/4) -> O(GetNum^2)
 
to creation-zy,请问你那个M与M[j]交换有什么作用？
能不能放在另一个数组中呢？
 
同意creation-zy。
 
to creation-zy：
如你所说,献丑了[:(]
 
>>M与M[j]交换有什么作用？
0 1 2 3 4 5 6
Random(7-0)+0 -> 4+0=4
M[4]<=>M[0]
4 1 2 3 0 5 6 (注意：剩下的六个数都在数组的尾部)
Random(7-1)+1 -> 5+1=6
M[6]<=>M[1]
4 6 2 3 0 5 1 (...五个数...尾部)
Random(7-2)+2 -> ...
....

明白了吗？
 
to grays
你的是随机数吗？
我得是阿！你输了！
我的算法有那些不对呢？
最简单的未必不能用阿？
:)
 
都讨论到这里了，居然还有人只看见别人的漏洞，却不见自己的错误...

to 狼牙:
如果我没有理解错，您的算法应该是：（如果我理解错了，请您指正！）
randomize;
s[1]:=random(1000)+1
//请注意： random(1000)=0..999
for i:=2 to 100 to
s:=s[i-1]+random(100)+1
//Random(100)可能为0的，必须保证 s<>s[i-1]

请您回答以下问题：
1: 您的算法导致从 S[1] 到 S[100] 依次增大，您凭什么保证S[1]之后的元素也在1000之内？
2: 请问理论上 S[N+1] 和 S[N] 的差值的可能范围是多少（假定已知S[1]到S[100]依次增大）？
而您的算法得到的结果相应的差值范围又是多少？（是1..100吧？还没发现问题所在吗？？）

我可以帮你解决问题1，办法如下，非常简单：
s:=(s[i-1]+random(100)+1) mod 1000+1
//虽然用了除法（很慢的），但解决了这个问题

问题2则是致命的，任何灵丹妙药都救不了你！ 哈哈哈哈！
 
这倒是。不过，我们可以小心修改一下，比如：
randomize;
s[1]:=random(10)+1
// random(10)=0..9
for i:=2 to 100 to
s:=s[i-1]+random(10)+1;//保证数据不重复
//如何？s[N]+10<=s[N+1]，这样10*100<=1000,即使每次取最大，都在1000之内，对吧？：）
更何况每次取最大的几率比较小噢。呵呵。两数之间的差距在1..10，然而，随机数并没有
需要差距忽大忽小吧：），而且，递增之间也是随机的嘛，是不？
当然。我的算法只是最简单的算法，但，效率好像是最高噢。呵呵。
 
赫赫，几天前我也刚写过一个。用的是链表。
为了示意起见，用的是java script.
代码: 
function random(maxstep)
{
	return Math.round(Math.random()*maxstep);
}

// init chain array

var chain= new Array(500);
for (i=0;i<chain.length;i++)
{
	chain[i] = i+1;
}
chain[chain.length-1]=0;

var pointer = 0;

var output= new Array();
var s='';

// select 200 random.

for (i=0;i<200;i++)
{
	step = random(20);
	for (j=0;j<step;j++)
	{
		// walk through the chain
		pointer = chain[pointer];
	}
	
	// got it!
	output[output.length]=chain[pointer];
	s+=chain[pointer]+",";
	chain[pointer]=chain[chain[pointer]];
}
 
to 狼牙:
我无话可说——什么叫做随机？？比如现在有1000个小方块，这些方块分为10种颜色，
每种颜色的方块各有100个，现在将它们相同颜色的放在一起（第1..100个是红色的，
第101..200个是黄色的，...）。要求从这1000个方块中随机取出100个方块来。
请问：如果采用阁下的算法，有可能得到这种组合吗？？？？？？？？？
40个1..100之间的，20个501..600之间的，40个901..1000之间的。

连可能出现的组合都不能取全，还有资格谈“随机”？？？（如果有一种洗牌算法，
非常高效，唯一的缺点是——用这个算法，你不可能让任何人拿到同花顺或者绝门——
你会采用它吗？？？） （说心里话，你的思路我以前还没有想到过，要是没有这个
缺陷，我真要自愧不如了... 但是，既然存在不足，就应该改进，消除不足，而不是
马马虎虎就过去了！）

还有，你谈到了“高效”，请问，阁下的算法除了在长度上比我的短了几行以外，可曾
在数量级上有所突破？（O(LogN)或者更高？） 你看看我给出的帖子，同志们都在数量级
上下功夫，上百个数里面取4个数字，一次Random搞定！他们好像要比较厉害耶。

曹兄的“pointer = chain[pointer];”确保了不会发生溢出，不过这双重循环的时间
复杂度嘛...
 
您必须登录或注册才可回复。

Similar threads

Z
算法，请问如何获取n个数中重复最多的那个数？100(100分)
回复
15
查看
389
stuwe
S
B
★★★关于随机数：求randomize random的用法及注意事项及原理及其它的随机方法？我给分。谢谢(20分)
回复
5
查看
187
bcfans
B
X
快速复数矩阵求逆的算法(300分)
回复
3
查看
186
x3000
X
快
100分继续挑战算法高手（50分求购算法的续集）up有分 (100分)
回复
13
查看
512
快刀不快
快
Y
求一个 矩形最优化切割的 算法,200分(200分)
2
回复
21
查看
1K
LeeChange
L
后退
顶部