21ic电子技术开发论坛 › 单片机与嵌入式系统 › 侃单片机论坛 › 求算法（范围内不重复随机数）
返回列表 发新帖我要提问

求算法（范围内不重复随机数）

[复制链接]
5911|16
 楼主| sysdriver 发表于 2011-5-5 23:19 | 显示全部楼层 |阅读模式
随机数, random, AN, 函数, DM
已知，函数char random(a)可以返回一个0~a-1的数。
求一个函数un_repeat_random(a)，使得在一定范围内取得的随机数不重复。

例：
char un_repeat_random(char dat)
{

}

void main(void)
{
       char i;
       i = un_repeat_random(10); //假设第一个取得3
       i = un_repeat_random(10); //那么0~9中，不能取3，假设取5
       i = un_repeat_random(10); //那么0~9中，不能取3，5。依次类推。。。
       i = un_repeat_random(10);
       i = un_repeat_random(10);
       i = un_repeat_random(10);
       i = un_repeat_random(10);
       i = un_repeat_random(10);
       i = un_repeat_random(10);
       i = un_repeat_random(10);

       i = un_repeat_random(10); //因为前面已经满10次了，故这次可以取0~9，假设取2
       i = un_repeat_random(10); //那么0~9中，不能取2，类似上面10个
       //。。。

       while(1);
}

上面只是个例子，你添加变量或改动结构都可以，只有实现题目要求就行。用汇编或C都可以，反正你想怎么写就怎么写。
回复

收藏 举报

相关帖子
Eve_dark 发表于 2011-5-6 13:01 | 显示全部楼层
一个常用的方法，但是和你的要求不太一样
假设你要10个随机数，下面的函数把结果返回到ans[10]的数组中
void un_repeat_random()
{
    int ans[10],i,j,t;
    for(i=0;i<10;i++)
        ans[i]=i;
    for(i=9;i>0;i--)
    {
        j=random(i);
        t=ans[i];
        ans[i]=ans[j];
        ans[j]=t;
    }
}
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-6 23:35 | 显示全部楼层
本帖最后由 sysdriver 于 2011-5-6 23:41 编辑

2# Eve_dark 参考你的意思，可以在外面加个封装，应该就符合要求了。


typedef unsigned char uchar;

#define max_random 10
uchar random_buf[max_random];

/*
* 打乱一个顺序数组，使其成随机数组
*/
void upset_random_buf(uchar *ranbuf, uchar n)
{
      uchar i, j, t;
      for(i=n;i>0;i--)
     {
          j = random(i);
          t = ranbuf;
          ranbuf = ranbuf[j];
          ranbuf[j] = t;
     }
}

/*
* 取得范围内不重复随机数函数
*/
uchar un_repeat_random(uchar n)
{
     static uchar ran_count =0;
     uchar i;
     if(ran_count==n) ran_count = 0;
     if(ran_count==0)
             upset_random_buf(random_buf, n);
     i = random_buf[ran_count++];
     return i;
}

void main(void)
{
     uchar i;

     for(i=0;i<max_random;i++) random_buf = i;

     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     i = un_repeat_random(max_random);
     while(1);
}
回复

收藏 举报

SeaSun 发表于 2011-5-7 17:24 | 显示全部楼层
"一定范围内取得的随机数不重复"
这样的数还能算是随机数吗
回复

收藏 举报

yewuyi 发表于 2011-5-7 17:28 | 显示全部楼层
呵呵，LS一语中的。

既然是随机，就可能重复，只是你不能确定是在什么时候重复而已。

如果不想重复的话，呵呵，很简单啊，每次取X++的值就好了。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-7 20:30 | 显示全部楼层
LS两位很严谨，只是我的描述能力有限，抛开标题，相信题目的要求和例子，相信大多数人都理解的。

而且，这个题目估计会有很多方法或算法来实现题目所表述的意思。就是想看看那种是最佳的，也想看看大家的思路跟我自己的一不一样，后面我会把我想到的贴上来的。

实际上，我开发产品时便有几次遇到这样的例子，并不是我凭空想象的。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-7 20:36 | 显示全部楼层
2楼的算法，我也遇见过，所以2楼提到一小部分我就知道是什么意思了。

5楼的，X++是顺序的，其实，在一定范围内，是随机的，不重复的，题目好像不矛盾。随机是指在这个范围内的数都有可能出现，不重复是指在这个范围内，已经出现过的就不要再出现了。
回复

收藏 举报

云的追寻 发表于 2011-5-7 20:40 | 显示全部楼层
学习了。。。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-8 21:48 | 显示全部楼层
相似的问题，论坛里面也有人问过了

这个问题，用2楼的方**好对得上。而我提出的，不是求一个序列，只是要求在这个范围内不重复就行，实现的方法估计有多种，不一定非得数组。

不过我在实现的过程中发现3楼中有个BUG，for循环中应该是i=n-1，而不是i=n。

random(n)函数。是用定时器做种子及调用srand(n)和rand()来实现的；有个缺点就是，每次重启后随机数是一样的。有人提议可以用按键或输入或EPPROM来初始化种子，也可以实现，但在这里不是重点，重点是是否有一个较好的算法，使得程序简单高效，占用空间少。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？注册

×
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-8 21:56 | 显示全部楼层
复制
  1. // main.c
    


  2. 

  3. #include 
    

  4. #include         //使用srand(int n)和rand()随机函数
    


  5. 

  6. typedef unsigned char uchar;
    

  7. typedef unsigned int  uint;
    

  8. typedef unsigned long ulong;
    


  9. 

  10. #define max_random 10
    

  11. uchar random_buf[max_random];
    


  12. 


  13. 

  14. int rand(void);
    

  15. void srand(int n);
    

  16. void initial_timer(void);
    


  17. 

  18. uchar random(uchar i);
    

  19. uchar un_repeat_random(uchar n);
    

  20. void upset_random_buf(uchar *ranbuf, uchar n);
    


  21. 

  22. /***************************************************/
    


  23. 

  24. void main(void)
    

  25. {
    

  26.         uchar i;
    


  27. 

  28.         initial_timer();
    

  29.         for(i=0;i<max_random;i++) random_buf[i] = i;
    


  30. 

  31.         i = un_repeat_random(max_random);
    

  32.         i = un_repeat_random(max_random);
    

  33.         i = un_repeat_random(max_random);
    

  34.         i = un_repeat_random(max_random);
    

  35.         i = un_repeat_random(max_random);
    

  36.         i = un_repeat_random(max_random);
    

  37.         i = un_repeat_random(max_random);
    

  38.         i = un_repeat_random(max_random);
    

  39.         i = un_repeat_random(max_random);
    

  40.         i = un_repeat_random(max_random);
    


  41. 

  42.         while(1);
    

  43. }
    


  44. 

  45. /***************************************************/
    


  46. 

  47. /*
    

  48.  * 取得范围内不重复随机数函数
    

  49.  */
    

  50. uchar un_repeat_random(uchar n)
    

  51. {
    

  52.         static uchar ran_count =0;
    

  53.         uchar i;
    


  54. 

  55.         if(ran_count==n) ran_count = 0;
    

  56.         if(ran_count==0)
    

  57.                 upset_random_buf(random_buf, n);
    

  58.         i = random_buf[ran_count++];
    

  59.         return i;
    

  60. }
    


  61. 

  62. /*
    

  63.  * 打乱一个顺序数组，使其成为随机数组
    

  64.  */
    

  65. void upset_random_buf(uchar *ranbuf, uchar n)
    

  66. {
    

  67.         uchar i, j, t;
    


  68. 

  69.         for(i=n-1;i>0;i--)
    

  70.         {
    

  71.                 j = random(i);
    

  72.                 t = ranbuf[i];
    

  73.                 ranbuf[i] = ranbuf[j];
    

  74.                 ranbuf[j] = t;
    

  75.         }
    

  76. }
    


  77. 

  78. /*
    

  79.  * 定时器计数做种子
    

  80.  */
    

  81. uchar random(uchar i)
    

  82. {
    

  83.         uchar k;
    

  84.         int t;
    


  85. 

  86.         srand((int)(TH0*256 + TL0));
    

  87.         t = rand();
    

  88.         k = (uchar)(t % i);
    


  89. 

  90.         return k;
    

  91. }
    


  92. 

  93. /***************************************************/
    


  94. 

  95. /*
    

  96.  * 初始化定时器
    

  97.  */
    

  98. void initial_timer(void)
    

  99. {
    

  100.         TMOD = 0x01;
    

  101.         TH0 = 0;
    

  102.         TL0 = 0;
    

  103.         TR0 = 1;
    

  104. }
    


  105. 


  106. 

  107. // main.c ends here
Program Size: data=29.0 xdata=0 code=654

经过单步调试，确实能够实现题目的要求。自我感觉是，程序简单，时间复杂度也为O(n)。缺点是，这个算法的随机度不高，如果范围是100内，那么要用100B。
回复

收藏 举报

yewuyi 发表于 2011-5-9 09:07 | 显示全部楼层
随机数算法都需要一颗种子，伪随机则因为它的种子不是真随机而来，真随机数的关键就是设计一个真随机的种子，并让它发芽。

例如，可以用MCU测量环境中的辐射水平并以它作为随机的种子。
例如，可以用MCU测量工程人员操作按键的时刻点，并以它作为随机的种子。
例如，可以用MCU测量某个元件的白噪声幅度，并以它作为随机的种子。
例如，可以。。。。。。

不管如何，那种想通过纯粹的数**算而得到真随机的想法是不可实现的。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-9 13:23 | 显示全部楼层
11# yewuyi

这里不讨论真随机的问题。我只求算法，不管它真随机或伪随机。只要算法符合要求就行。

至于要不要真随机或每次重启随机数不一样的问题，让老板和客户考虑去吧，其实，客户的意思也要求不高，只要是随机，只要不重复就行。
回复

收藏 举报

jtboy105 发表于 2011-5-9 21:20 | 显示全部楼层
有一个很简单的方法，建几个table表进行伪随机去吧。我之前做过一些小案子，由于ＲＡＭ不够，只能用表的方式，每次产生一个随机数，指向对应的表就行了。简单，高效
回复

收藏 举报

jtboy105 发表于 2011-5-9 21:24 | 显示全部楼层
如果是用算法，如果是产生１００个数内的，你肯定要用的ＲＡＭ很多，单片机ＲＡＭ本身就不多，你就不用做别的事了。最多建几个几Ｋ的表。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-9 22:16 | 显示全部楼层
有一个很简单的方法，建几个table表进行伪随机去吧。我之前做过一些小案子，由于ＲＡＭ不够，只能用表的方式，每次产生一个随机数，指向对应的表就行了。简单，高效 ...
jtboy105 发表于 2011-5-9 21:20


这个方法能行吗？怎么确保指向的表的数据不重复？可以的话，能否简略的用代码描述一下？

uchar code table1[n]={};
uchar code table2[n]={};
uchar code table3[n]={};
怎么初始化这些表？
i = random(m);
k = table;
怎么查表，怎么确定取得的不重复？
我记得有人说过，不重复就得必须记录出现过的数，所以用RAM应该是少不了的。
回复

收藏 举报

jtboy105 发表于 2011-5-9 22:56 | 显示全部楼层
我是用ＥＸＣＥＬ中的宏进行产生一些表，之前一个案子是，从２０道题目里每次随机出１０道不重复的题。
方式如２楼一样，只是用这种方式，随机产生一些表，比如可能产生１００个这样符合要求的表。再用一个随机数，指定用１００个中的那个表，顺序读出来就行了。
如uchar code table1[100][10]={{9,7,5,3,2,8,4,1,6,10},{8,7,3,5,4,8,6,1,2,10},...........
;
因为我用汇编，很少用Ｃ，仅供参考。呵呵，这个方法比较笨。
回复

收藏 举报

 楼主| sysdriver 发表于 2011-5-9 23:23 | 显示全部楼层
16# jtboy105

我明白你的意思了，但是如果取得的随机数是相同的，那么调用的那个表也是相同的了。你的案子可能对随机数要求不高，也许你加多了个变量，让2次不重复，这样如果是傻傻用户，就以为是随机了。

算法跟汇编或C没有关系，只是C实现算法简单方便些。C最终还是会编译成汇编，所以汇编和C，本质是一样的，实现的过程不一样而已。我工作的时候有些单片机就用汇编，而且还是大部分，C也是很少用，但是我发现，写一小段C就相当于写一大段汇编，或者不用考虑什么标号跳转，指令判断等等，C就简单方便一些，特别是学数据结构，不了解C就不行了。
回复

收藏 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

sysdriver

5

主题

687

帖子

0

粉丝
快速回复 在线客服 返回列表 返回顶部