从 1-100 中 随机抽取10个不重复 数字
求 一个 最好的 效率 算法 ，谢谢 本帖最后由 CCM 于 2012-11-28 15:44 编辑精不精简不知道，以前玩抽抽乐的练习题，改成取10位数
Local $aNum
For $i = 0 To 100
$aNum[$i] = $i + 1
Next
For $i = 0 To 100
$r = Random($i, 100, 1)
$temp = $aNum[$i]
$aNum[$i] = $aNum[$r]
$aNum[$r] = $temp
Next
Dim $Ans
For $i = 0 To 9
$Ans &= $aNum[$i] & " "
Next
MsgBox(0, "", $Ans)
回复 1# bilinyee
我觉得你应该先给出自己的算法,然后求一个"更好的",而不是直接求一个"最好的"~~
不敢宣称自己的最好(甚至不好意思说好),所以就不上码了~~{:face (84):} 回复 1# bilinyee
整数还是小数 回复 2# CCM
很棒的方法~~~但
您这个为什么要include那个数组的UDF呢??
另外,为什么要多申请一个元素???多余的哦,与楼主要求的"最好"不符~~
呵呵`~~ 本帖最后由 netegg 于 2012-11-28 15:37 编辑
#include <Array.au3>
$timer = TimerInit()
$aR = _RandomUnique(0, 100, 10)
_ArrayDisplay($aR, 'Time : ' & Round(TimerDiff($timer) / 1000, 2) & ' sec', 100)
Func _RandomUnique($Min = 0, $Max = 1, $Count = 1)
Local $i, $k, $ts, $te, $tmp, $tmpNew, $iStep = 0, $nRnd, $iStepErr = 0
$k = $Max - $Min + 1
If $Min >= $Max Then Return SetError(1, 0, '')
If $k < $Count Then Return SetError(2, 0, '')
If $Count = 1 Then
Local $aUnique =
Return $aUnique
EndIf
Local $aStr[$k]
For $i = 0 To $k - 1
$aStr[$i] = $i + $Min
Next
If $Count > $k / 2 Then
Local $iCountExp = $k - $Count
Assign('', '', 1)
While $iStep < $iCountExp
$nRnd = Random(0, $k - 1, 1)
If IsDeclared($aStr[$nRnd] & '') <> -1 Then
$iStep += 1
$aStr[$nRnd] = ''
Assign($aStr[$nRnd] & '', '', 1)
Else
; v===================================v
$iStepErr += 1
If $iStepErr > $k / 4 Then
$d = 0
For $i = 0 To $k - 1
If $aStr[$i] Then
$aStr[$d] = $aStr[$i]
$d += 1
EndIf
Next
If $d > 0 Then
ReDim $aStr[$d]
$k = $d
$iStepErr = 0
Else
ExitLoop
EndIf
EndIf
; ^===================================^
EndIf
WEnd
$d = 0
Local $aUnique[$k]
For $i = 0 To $k - 1
If StringLen($aStr[$i]) Then
$d += 1
$aUnique[$d] = $aStr[$i]
EndIf
Next
ReDim $aUnique[$d + 1]
$aUnique = $d
; swap
For $i = 1 To $aUnique
$iR = Random($i, $aUnique, 1)
If $i = $iR Then ContinueLoop
If $iR = 0 Then $iR = $aUnique
$aTmp = $aUnique[$i]
$aUnique[$i] = $aUnique[$iR]
$aUnique[$iR] = $aTmp
Next
Else
Local $aUnique[$Count + 1] = [$Count]
Assign('', '', 1)
While $iStep < $Count
$nRnd = Random(0, $k - 1, 1)
If IsDeclared($aStr[$nRnd] & '') <> -1 Then
$iStep += 1
$aUnique[$iStep] = $aStr[$nRnd]
$aStr[$nRnd] = ''
Assign($aStr[$nRnd] & '', '', 1)
Else
; v===================================v
$iStepErr += 1
If $iStepErr > $k / 4 Then
$d = 0
For $i = 0 To $k - 1
If StringLen($aStr[$i]) Then
$aStr[$d] = $aStr[$i]
$d += 1
EndIf
Next
If $d > 0 Then
ReDim $aStr[$d]
$k = $d
$iStepErr = 0
Else
ExitLoop
EndIf
EndIf
; ^===================================^
EndIf
WEnd
EndIf
Return $aUnique
EndFunc ;==>_RandomUnique
印象里还有个简单的 本帖最后由 CCM 于 2012-11-28 15:45 编辑
回复 5# annybaby
include应该是我忘记删除掉，我是开旧文档，贴到正在练习的脚本，测试运作正常就贴过来了，回头我把那行删除掉。
至於多申请的是哪个？
这是以前GOOGLE找到改过来的...详细的内容其实我没多看，就当一个资料放着取用。 回复 8# CCM
就是第一行那个定义数组的,其实100个元素就可以了,不用101个~~ 6楼的代码太深了，可惜看不懂 本帖最后由 edisonx 于 2012-11-28 19:23 编辑
淺見，參考。
我們將問題重定義成較廣泛的問題。
如何產生 N 個 之整數亂數
(其中 N <= (UP-LOW+1) ，且 (UP-LOW+1) <= 2^31 )
為了方便說明，我們將 (UP-LOW+1) 定為 RANGE。
暴力法
直接用一個 Array 紀錄之前產生過的數字，每產生一個亂數再進去筆對。
暴力法產生在某些情況是適用的，通常是(N / RANGE) 較小，甚至一半的時候考慮使用。
但若比值近似於 1 ，且 RANGE 特大時，速度就很慢了。
舉個例，產生 1000 個 [-500,500] 不重覆亂數，這時候用暴力法就特慢。
#include <array.au3>
#include <timers.au3>
const $Lower = -500
const $Upper = 500
const $N = 1000
Dim $ckBeg, $Td
Dim $rst[$N]
$ckBeg = _Timer_Init()
ArrayRnd($Lower, $Upper, $N, $rst)
$Td = _Timer_Diff($ckBeg)
_ArrayDisplay($rst, "Td = " & $Td)
; --------------------------------------------------------------------------
; Force
Func ArrayRnd(const $Low, const $Up, const $N, ByRef $Rst)
Local$rnd
Local $i, $Count=0
Local $FindFlag
While $Count < $N
$FindFlag = False
$rnd =Random($Low, $Up, 1)
; 確認是否產生過
For $i=0 To $Count-1
If $rnd = $Rst[$i] Then
$FindFlag=True ; 有產生過
ExitLoop
EndIf
Next
; 若無產生過
IfNot $FindFlag Then
$Rst[$Count] = $rnd
$Count+=1
EndIf
WEnd
EndFunc
再次提醒，這種方式還是有優點的，當 RANGE 愈小，或 N / RANGE 愈小時，這種方法會是首選。
洗牌法 (shuffle)
洗牌法概念是先產生一副 之 poker，先拿出第 i 張牌出來，再隨機抽出第 j 張牌，將這兩張牌交換，最後再取出前面 N 張牌出來就是了。
洗牌不是洗愈多愈亂，目前筆者所知，網路上的洗牌法有以下概念 (恕以虛碼示之 )
const $Lower = -500
const $Upper = 500
const $N = 1000
Const $Range = ($Upper-$Lower+1)
Dim $Rst[$N] ; 放結果
Dim $Poker[$Range] ; Poker = i+low , for 0<=i < Range
Dim $rnd, $rnd1, $rnd2
; 法一：逐一交換, 保證每張牌都交換過
For $i = 0To $Range-1
$rnd = Random(0, N)
Swap ( [$Poker[$rnd], Poker[$i])
Next
; 最後再將 Poker 前 N 個丟給 Rst
; 法二：隨機取兩張牌交換，進行 Range 次
For $i = 0To $Range-1
$rnd1 = Random(0, $Range-1)
$rnd2 = Random(0, $Range-1)
Swap ( [$Poker[$rnd], Poker[$rnd2])
Next
; 最後再將 Poker 前 N 個丟給 Rst
但上述之方法都沒經過亂數均勻性測試，唯一有經過均勻性測試的是 Knuth Shuffle，
以下範例碼關鍵是 Func KnuthShuffle
#include <array.au3>
#include <timers.au3>
const $Lower = -500
const $Upper = 500
const $N = 1000
Dim $ckBeg, $Td
Dim $rst[$N]
$ckBeg = _Timer_Init()
KnuthShuffle($Lower, $Upper, $N, $rst)
$Td = _Timer_Diff($ckBeg)
_ArrayDisplay($rst, "Td = " & $Td)
Func KnuthShuffle(const $Low, const $Up, const $N, ByRef $Rst)
Local $i, $rnd, $tmp
Local $Range = ($Up-$Low+1)
Local $Poker[$Range]
; Generate a poker
For $i=0 to $Range-1
$Poker[$i] = $Low + $i
Next
; shuffle
For $i = $Range-1 to 1 step -1
$rnd = Random(0, $i)
; swap (poker, poker)
$tmp = $Poker[$i]
$Poker[$i] = $Poker[$rnd]
$Poker[$rnd] = $tmp
Next
; pick first N
For $i = 0 To $N-1
$Rst[$i] = $Poker[$i]
Next
EndFunc
但洗牌法還是有缺點，只要 N / RANGE 愈小，實際上所虛費的時間/內存空間就愈差。
適用性
(1) 注意rand / random 產生之最大亂數值，由於 AU3 最大可產生 2^31 之亂數，故前提已當是假設。
(2) 適用於整數，浮點數 (floating) 要看情況，有些可以調整，有些不行調整。
進階議題
這次我們玩個比較特別的東西。
如何產生 500 個 [-500 500] 之整數亂數，產生結果之陣列(array，數組)裡之內容必須由小到大排好？ As Soon As Possible
提示：其實用不到排序法，有用到上面洗牌法概念，有興趣的可稍想一下。
本帖最后由 zch11230 于 2012-11-28 20:00 编辑
网吧上网中 没AU3可以测 不知道是否可用。。。。晕。。。。没scite endif都忘写了 加上。。local $i=1,$num,$tmp
while $i<=10
$tmp=random(1,100,1)
if not stringregexp ($num,'\D'&$tmp&'\D',0) then
$num&=$tmp&" "
$i+=1
endif
wend
msgbox(0,"",$num) 如果是我的话，直接如下：
For $i = 1 To 10
MsgBox(0, $i, "")
Next
计算机生成的，还有我们一拍脑袋就能想到的，都是伪随机，所以还不如直接如此。 本帖最后由 edisonx 于 2012-11-28 20:45 编辑
忘了提下面方法，「依樓主之特列」( N /RANGE 不高，在50% 內都可接受)，此算法即使不是最優，但應"勘稱"是高效能。。
#include <Array.au3>
#include <Timers.au3>
$timer = _Timer_Init()
$rst = RandomForce(1, 100, 10)
_ArrayDisplay($rst, 'Time : ' & _Timer_Diff($timer) & ' msecs')
Func RandomForce(const $Lower, const $Upper, const $N)
Local $Diff = $Upper - $Lower
Local $Rng = $Diff+1
Local $Size = BitShift($Rng, 5) + 1
Local $Mask[$Size]
Local $Rnd, $Idx, $Bit, $Count = 0
Local $i, $Rst = ""
If $Upper <= $Lower Then Return SetError(1, 0, "")
If $Rng < $N Then Return SetError(2, 0, "")
While $Count<$N
$Rnd = Random(0, $Diff, 1)
$Idx = BitShift($Rnd, 5)
$Bit = -BitAnd($Rnd, 31)
If Not BitAND( $Mask[$Idx ], BitShift(1, $Bit ))Then
$Count+=1
$Rst = $Rst & ($Lower+$Rnd) & "|"
$Mask[$Idx] = BitOR($Mask[$idx], BitShift(1, $Bit))
EndIf
WEnd
Return SetError(0, 0, StringSPlit( StringTrimRight($Rst,1), "|", 2))
EndFunc
事實上還有修改空間，修改便是像 #6F 蛋大 的方式，
先判斷 N / RANGE 比值，再決定要用暴力法還是要用洗牌法 (剛有稍算交界，大概是 60%~70% 之間做切換)，
其他的就不再贅述。 本帖最后由 smartzbs 于 2012-11-29 14:23 编辑
Local $t=TimerInit()
Local $sNum = ",", $iNum
for $i=1 To 10
Do
$iNum = Random(1,100,1)
Until StringInStr($sNum, ","&$iNum&",",1)=0
$sNum &= $iNum & ","
Next
$sNum = StringTrimRight(StringTrimLeft($sNum,1),1)
ConsoleWrite($sNum&','&TimerDiff($t)&@CR)
Local $t=TimerInit()
Local $sNum = ""
For $i = 1 To 10
$sNum &= Random(($i-1)*10+1, $i*10, 1) &","
Next
$sNum = StringTrimRight($sNum,1)
ConsoleWrite($sNum&','&TimerDiff($t)&@CR)
喜欢另类的
#include <array.au3>
Local $aNum
For $i = 2 To 101
$aNum[$i] = $i + 1
Next
Local $out
For $i=0 To 9
$random=Random($i+2,101,1)
$out[$i]=$aNum[$random]
_ArraySwap($aNum[$i],$aNum[$random])
Next
_ArrayDisplay($out)
页:
[1]
2