现在的位置: 首页 > 综合 > 正文

生成不重复的随机数序列

2012年09月08日 ⁄ 综合 ⁄ 共 6293字 ⁄ 字号 小 中 大 ⁄ 评论关闭

好久没写笔记了，刚刚我又被提升为高级会员了。真的感觉挺愧疚的。
其实这些天也并不是什么都没有做，相反而是做了很多，只是没有时间将做好的东西整理出来与大家分享。
现在就趁这个机会将前些天编的一个小程序说一说。

这个程序是用来产生0到n-1的n个不重复的随机数。去年或是什么时间就有人讨论过这个问题。后来我由于实际需要，就编了一个。感觉效率还不错，就在这里献丑了。

首先先介绍一下基本的思路吧：
我是用C#编写的代码。

1、不重复随机数的产生


说到随机数的生成大家肯定会想到.Net提供的Random类。当然，在不同的语言和开发平台中可能有类似的其他方法。
Random类的使用很简单。它提供了两种构造函数，一个构造函数没有参数，另外一个构造函数有一个Int32型的参数作为随机数产生的种子。在一般的使用中，声明并初始化Random对象后，只要在需要的时候不断调用Random的Next()方法（已经重载，通过设定参数可以取得某一区间内的随机数）就可以得到一系列随机数了。
Random产生的数能够保证随机，但并不能保证在一个随机数序列内每个数字只出现一次，也不能保证这个随机数列是由连续数值打乱顺序后得到的。
为了实现刚刚提到的要求，可以采取两种方案：

1）建立一个n维数组，用于保存已生成的并且合乎条件的随机数。利用Random类的Next(n-1);方法生成随机数，与前面已经生成的随机数进行比较，如果这个随机数已经生成过，就抛弃当前随机数，重新生成随机数与前面的随机数进行比较，直至所生成的随机数前面没有出现过为止，把这个随机数添加到数组中。同样方法，生成符合条件的n个随机数。

2）建立一个n维数组，用于保存生成的随机数；在建立一个n维bool型数组flag，并将元素全部初始化为false，作为某一个随机数是否已经生成的标志位。同样利用Random类的Next(n-1);方法生成随机数tmp，判断flag[tmp]是否为true，若为true（说明tmp在前面已经生成过），则放弃tmp重新生成随机数赋值给tmp，继续判断，直至flag[tmp]是否为false（说明tmp在以前还未出现过），此时将flag[tmp]赋值为true，表明tmp已经生成过了。同样方法，生成符合条件的n个随机数。
这两种方案显然后者要优于前者。虽然后者多声明了一个bool型的数组，但是避免了循环嵌套，使时间复杂度大为降低，有效提高了程序的运行效率。

2、随机数的显示


string类和StringBuilder类的比较
由于我是利用窗口来实现此程序，因此在显示过程中就要把新生成的随机数数组中每个元素转换成字符串添加到一个已有的随机数字符串中。
刚开始的时候使用string型的字符串，利用操作符“+”或者Insert()方法实现。但是这种方法的效率极低，甚至还慢于随机数的产生。
后来使用了StringBuilder型的字符串进行操作，利用Append()方法实现字符串的组合。效率明显提高。
string和StringBuilder在组合字符串过程中的效率不同主要原因在于string类型的字符串是静态的，而StringBuilder类型的字符串是动态的。
在string类型的字符串上添加字符串相当于把生成一个新的字符串，赋值给变量，而的字符串后被抛弃；但是在StringBuilder类型的字符串上添加字符串就是在原有的字符串上添加，不会再重新建立一个新的对象。这就是动态字符串处理的优势。

3、过程计时方法


刚才在讨论第二个问题时对于使用string和StringBuilder类型的效率我是通过程序执行时间来给出的。这里的时间不是我的主观感觉，而是在程序中利用DateTime类计时得到的。具体方法是在需要计时的程序段前写上一句“DateTime start=DateTime.Now;”，在程序段结束后写上一句“string timeCost=(DateTime.Now-start).ToString();”。这样程序段消耗时间就被保存在timeCost这个字符串中了。

4、TextBox的输入验证：Validating


在变这个程序的时候还试用了一下Validating事件。
先引用一段MSDN中的话吧：
当通过使用键盘（Tab、Shift+Tab 等）、通过调用 Select 或 SelectNextControl 方法或者通过将 ContainerControl..::.ActiveControl 属性设置为当前窗体等方式更改焦点时，焦点事件按以下顺序发生：
Enter
GotFocus
Leave
Validating
Validated
LostFocus
当通过使用鼠标或调用 Focus 方法的方式更改焦点时，焦点事件按以下顺序发生：
Enter
GotFocus
LostFocus
Leave
Validating
Validated
如果 CausesValidation 属性设置为 false，则将取消 Validating 和 Validated 事件。
这句话告诉了我们Validating以及其他类似事件会在什么时候发生。我在程序中就是用这个事件来判断在输入随机数种子和随机数个数的TextBox中输入的内容是否合法。如果不合法就重新定位到输入的TextBox控件上。

Code:
  1. private void textBox_Validating(object sender, System.ComponentModel.CancelEventArgs e)   
  2. {   
  3.     try  
  4.     {   
  5.         Convert.ToInt32((sender as TextBox).Text);   
  6.     }   
  7.     catch (Exception)   
  8.     {   
  9.         MessageBox.Show("请输入数值！");   
  10.         (sender as TextBox).SelectAll();   
  11.         (sender as TextBox).Focus();   
  12.     }   
  13. }  

不知道这种验证方法是否合理。请高人指教。

下面是程序运行的测试结果：
我的电脑CPU：P8700（2.53G双核）；内存：2G；系统：Win7

//利用一个数组双重循环嵌套生成随机数，用StringBuilder显示
数量:90000
种子:234
获取耗时:00:03:38.8595180
显示耗时:00:00:06.2623582

//利用两个数组生成随机数，用StringBuilder显示
数量:90000
种子:234
获取耗时:00:00:06.3733645
显示耗时:00:00:06.3743646

//利用两个数组生成随机数，用string显示
数量:90000
种子:234
获取耗时:00:00:06.5443743
显示耗时:00:02:47.9316051

就不多罗嗦了，给大家看代码吧。

Code:
  1. //使用一个数组生成随机数   
  2. /*初始化   
  3.  * 注意：    
  4.  * 这里不用对table进行初始化，    
  5.  * 因为在tmp与之比较时，只比较已经被有效随机数更新的数据    
  6.  */     
  7. num = Convert.ToInt32(textBox3.Text); //textBox3用于输入随机数总数   
  8. table = new int[num];      
  9. textBox1.Text = "";      
  10. textBox1.Update();      
  11. progressBar1.Maximum = num;      
  12.      
  13. //产生随机数      
  14. /*    
  15.  * (1)最后一个数不再用随机数找了，而是通过计算得出    
  16.  * 用此方法，在num=10000时大约节约时间1s    
  17.  */     
  18. Random rand = new Random(Convert.ToInt32(textBox2.Text)); //textBox2用于输入随机数种子   
  19. DateTime time1 = DateTime.Now;//用于获取随机数计时      
  20. int sum1 = 0, sum2 = 0;//(1)计算最后一个数所用到的两个参数      
  21. for (int k = 0; k < num - 1; k++)//(1)这里只循环num-1次      
  22. {      
  23.     bool flag;//用于判断当前产生的随机数在前面是否已经产生过：产生过（true）      
  24.     int tmp;      
  25.     do     
  26.     {      
  27.         flag = false;      
  28.         tmp = rand.Next(num);      
  29.         for (int j = 0; j < k; j++)      
  30.         {      
  31.             if (tmp == table[j])      
  32.             {      
  33.                 flag = true;      
  34.                 break;      
  35.             }      
  36.         }      
  37.     } while (flag);//若产生过，则重新产生新随机数，在重复比较。      
  38.     table[k] = tmp;//若没有产生过，则将该随机数保存，并开始寻找下一个随机数。      
  39.      
  40.     sum1 += k + 1;//(1)计算最后一个数所用到的参数，记录从1加到num的总和      
  41.     sum2 += table[k];//(1)计算最后一个数所用到的参数，记录前面得到的num-1个随机数的总和      
  42.      
  43.     progressBar1.Value = k;      
  44.     this.Text = "产生随机数:" + k.ToString();      
  45. }      
  46. table[num - 1] = sum1 - sum2;//(1)计算得出最后一个数值      
  47. textBox1.Text += ("数量:" + num.ToString() +      
  48.                   "/r/n种子:" + textBox2.Text +      
  49.                   "/r/n获取耗时:" + (DateTime.Now - time1).ToString() + "/r/n");      
  50. textBox1.Update();      
  51.      
  52. //显示随机数      
  53. progressBar1.Value = 0;      
  54. //string tmpstr = "";//使用string类型显示随机数      
  55. StringBuilder tmpStrB = new StringBuilder("");//使用StringBuilder类型显示随机数      
  56. DateTime time2 = DateTime.Now;//用于显示随机数计时      
  57. for (int i = 0; i < num; i++)      
  58. {      
  59.     //tmpstr += (i.ToString("000000") + " | " + table[i].ToString() + "/r/n");//使用string类型显示随机数      
  60.     tmpStrB.Append(i.ToString("000000") + " | " + table[i].ToString() + "/r/n");//使用StringBuilder类型显示随机数      
  61.     progressBar1.Value = i;      
  62.     this.Text = "显示随机数:" + i.ToString();      
  63. }      
  64. textBox1.Text += "显示耗时:" + (DateTime.Now - time2).ToString() +      
  65.                  "/r/n*************/r/n 序号  | 数值/r/n";      
  66. //textBox1.Text += tmpStr;//使用string类型显示随机数      
  67. textBox1.Text += tmpStrB;//使用StringBuilder类型显示随机数     
Code:
  1. //使用两个数组生成随机数               
  2. //初始化   
  3. num = Convert.ToInt32(textBox3.Text);   
  4. table = new int[num];   
  5. test = new bool[num];//用于判断当前产生的随机数之前是否产生过。产生过（true）   
  6. textBox1.Text = "";   
  7. textBox1.Update();   
  8. progressBar1.Maximum = num;   
  9. for (int i = 0; i < num; i++)   
  10. {//清空随机数序列。即，给这个序列每一个元素都赋一个超出所需随机数范围的数值。   
  11.     test[i] = false;   
  12. }   
  13.  
  14. //产生随机数   
  15. /*  
  16.  * (1)最后一个数不再用随机数找了，而是通过计算得出  
  17.  * 用此方法，在num=10000时大约节约时间1s  
  18.  */  
  19. Random rand = new Random(Convert.ToInt32(textBox2.Text));   
  20. int sum1 = 0, sum2 = 0;//(1)计算最后一个数所用到的两个参数   
  21. DateTime time1 = DateTime.Now;//用于获取随机数计时   
  22. for (int k = 0; k < num - 1; k++)//(1)这里只循环num-1次   
  23. {   
  24.     int tmp;   
  25.     do  
  26.     {   
  27.         tmp = rand.Next(num);   
  28.     } while (test[tmp]);//若产生过，则重新产生新随机数，在重复比较。   
  29.     test[tmp] = true;   
  30.     table[k] = tmp;//若没有产生过，则将该随机数保存，并开始寻找下一个随机数。   
  31.   
  32.     sum1 += k + 1;//(1)计算最后一个数所用到的参数，记录从1加到num的总和   
  33.     sum2 += table[k];//(1)计算最后一个数所用到的参数，记录前面得到的num-1个随机数的总和   
  34.   
  35.     progressBar1.Value = k;   
  36.     this.Text = "产生随机数:" + k.ToString();   
  37. }   
  38. table[num - 1] = sum1 - sum2;//(1)计算得出最后一个数值   
  39. textBox1.Text += ("数量:" + num.ToString() +   
  40.                   "/r/n种子:" + textBox2.Text +   
  41.                   "/r/n获取耗时:" + (DateTime.Now - time1).ToString() + "/r/n");   
  42. textBox1.Update();  

结束！！！

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞