【电脑】随机数

偶随手给她用ASP.Net做了一个页面，输入所要Matrix的行数与列数之后，会输出相应的随机Matrix……页面的核心代码如下：

Dim h, w, i, j, t As Integer
h = TextBox1.Text
w = TextBox2.Text

Dim arr(h * w) As boolean
For i = 1 To h * w
 arr(i) = false
Next
Dim flag As Boolean
Dim r As New Random
Response.Write("<table border=1>")
For i = 1 To h
 Response.Write("<tr>")
 For j = 1 To w
  flag = False
  While (flag = False)
   t = r.Next(1, h * w + 1)
   If arr(t) = false Then
    Response.Write("<td>" + t.ToString + "</td>")
    arr(t) = true
    flag = True
   End If
  End While
 Next j
 Response.Write("</tr>")
Next i
Response.Write("</table>")

这个算法，其实……蛮恶心的……因为要求生成的随机数字不重复，都定义了arr()这个布尔数组……当一个数字出现后，就在相应的数组位置做一个标记……

程序里面有一个while循环……倘若随机出来的数字都是已经出现过的，就继续随机生成新的数字，直到出现新的没有出现过的数字才输出到Matrix里面……挺恶心的……理论上来说，如果我运气超级不好的话，程序可能永远都死在这个循环里面……

不过，这个只是理论……在实际上，偶让程序生成一个300*300的Matrix也只是用了1秒的时间……100*100以下的话，几乎就是即点即有……

对于要生成不重复的一系列确定范围的随机数，偶还真想不出更好的办法……

偶是在去年龙音的时候，想出这个算法的……当时是在用kjava做百家乐的手机游戏……要模拟发牌的过程……8副牌，也就是要有一个大小为8*54=432的数组……每张牌发出去后，在数组相应位置做一个标记，需要再发牌时，一直随机访问数组，找没有发过的牌……每发出4副牌后，整个数组清空……这也是赌场的规矩……使用8副牌，发完四副就重新洗牌……

当时，带偶做这个游戏的同事对偶这样的算法一开始不怎么认同……他原来的做法是也是弄一个大小432的数组，每个成员代表一张牌……然后用某个算法对数组进行反复排序……模拟洗牌的过程……发牌的时候，就按照顺序从数组的第一位开始发……

偶不清楚那个排序算法是怎么弄的……完全不清楚它的“随机性”究竟有多大……反正，在我看来，经过“洗牌”之后，以后要发的牌已经是确定的……而且，是在进入游戏的时候，就进行这些操作……倘若那个排序算法很复杂……也许进入游戏的时候会觉得慢……而且，最终会发出的牌只是前216张牌而已……对数组的后216张牌进行排序，是完全没有意义的……

而偶的算法，则是将计算分布在了每一次发牌过程……至少进入游戏的，“随机”发牌的总时间应该会比对数组进行排序多……但，被偶拆分到了每一张牌上……程序实际运行的时候，玩家不会感觉到发牌的停顿……并且，每一张牌都是“随机”产生的，你永远不会知道下一张牌是什么……

跟同事争论了粉久……他甚至还写了个C＋＋程序来检验偶的算法……最终他对偶的算法表示赞同……

可是……偶自己还是觉得挺那个的……

万一……Java虚拟机或者.Net framework的伪随机数生成有问题，总是随机出来出现过的数要咋办？敢情就一直死在循环里面么？

可是，有更好的算法么？

偶暂时想不出来……

方遒 在 2/17/2005 6:40:00 PM 说:

记得大一时学C/C++，我也用这个算法，没觉得有什么不妥。如果作一下算法分析，算出Big Oh, Big Omega, Big Theta，不知是怎样的结果……

---

汗～ 在 2/17/2005 12:33:24 PM 说:

打错了。更正
for (i=1;i<=10000;i++) swap(a[rand()*9],a[rand()*9]);

---

汗～ 在 2/17/2005 12:32:45 PM 说:

数组里给1-9， 循环10000次随机给两个数据交换。
for (i=1;i<=9;i++) a[i]=i;
for (i=1;i<=10000;i++) swap(a[rand()*i],a[rand()*i]);
然后输出～

---