【作者】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 的頭像
Nelson

Nelson 的小世界

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


留言列表 (2)

發表留言
  • 囧
  • 改良一下
    use system.math

    randomize; ///亂數種子
    A:=1;
    B:=38;
    setlength(Nums,B+1); //產生B張牌 0~B= 0不用

    for i := 1 to B do begin
    Nums[i] := i; //產生一副新牌..都是照順序排好的
    end;
    for i := 1 to B do begin
    j := RandomRange(A,(B-A)+1); //隨便選兩張牌(索引) 取出A~B的亂數
    k := RandomRange(A,(B-A)+1);
    temp := Nums[j]; //交換兩張隨便取的牌
    Nums[j] := Nums[k];
    Nums[k] := temp;
    end;
  • 訪客
  • 請問一下 我按照你的方法做 最後一項都都會是52
    哪裡有問題嗎?