【作者】geniustom

【內文】http://delphi.ktop.com.tw/topic.asp?topic_id=59601



一般人看到【取亂數不重複】..很直接的想法就是一直取,每次取完之後再跟之前的比較..

其實這樣的效率極差!取N個不重複的亂數需要做N階乘次比對..

有學過資料結構的應該都知道.在複雜度裡面..N階乘算是【極差】

取亂數可以使用洗牌法..

意思就是說..

1..假設剛買來的牌..有52張..分別照順序排好...

2..你只需要把52張牌全部攤開..隨便選2張交換...

3..交換52次之後..可以做出很平均的亂數處理..

所以..如果要產生A~B不重複的亂數.演算法如下..

var

Nums: array of integer;

i,j,k,temp: integer;

begin

randomize; 灑下亂數種子

setlength(Nums,B-A) //產生B-A張牌

for i := 0 to (B-A)-1 do

Nums[i] := i; //產生一副新牌..都是照順序排好的

for i := 0 to (B-A)-1 do

begin

j := random(B-A+1); //隨便選兩張牌(索引) 取出0~(B-A)的亂數

k := random(B-A+1);

temp := Nums[j]; //交換兩張隨便取的牌

Nums[j] := Nums[k];

Nums[k] := temp;

end;

for i := 0 to (B-A)-1 do

Nums[j]:=Nums[j]+A; //最後..把這邊的排全部變成A~B的值

end;



假如您要取5個..

那只要選Nums[0]~Nums[4]..就是一組很漂亮的亂數..

效率極佳..只需要O(n)次...

而一般人想到那種差勁的演算法..差不多到100..程式就要死當了


全站熱搜

Nelson 發表在 痞客邦 留言(2) 人氣()