close
一般人看到【取亂數不重複】..很直接的想法就是一直取，每次取完之後再跟之前的比較..
其實這樣的效率極差!取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..程式就要死當了
arrow
arrow
    全站熱搜

    Felix 發表在 痞客邦 留言(1) 人氣()

    E-mail轉寄