求算法(范围内不重复随机数)

[复制链接]
5900|16
 楼主| sysdriver 发表于 2011-5-5 23:19 | 显示全部楼层 |阅读模式
已知,函数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. #include
  3. #include         //使用srand(int n)和rand()随机函数

  4. typedef unsigned char uchar;
  5. typedef unsigned int  uint;
  6. typedef unsigned long ulong;

  7. #define max_random 10
  8. uchar random_buf[max_random];


  9. int rand(void);
  10. void srand(int n);
  11. void initial_timer(void);

  12. uchar random(uchar i);
  13. uchar un_repeat_random(uchar n);
  14. void upset_random_buf(uchar *ranbuf, uchar n);

  15. /***************************************************/

  16. void main(void)
  17. {
  18.         uchar i;

  19.         initial_timer();
  20.         for(i=0;i<max_random;i++) random_buf[i] = i;

  21.         i = un_repeat_random(max_random);
  22.         i = un_repeat_random(max_random);
  23.         i = un_repeat_random(max_random);
  24.         i = un_repeat_random(max_random);
  25.         i = un_repeat_random(max_random);
  26.         i = un_repeat_random(max_random);
  27.         i = un_repeat_random(max_random);
  28.         i = un_repeat_random(max_random);
  29.         i = un_repeat_random(max_random);
  30.         i = un_repeat_random(max_random);

  31.         while(1);
  32. }

  33. /***************************************************/

  34. /*
  35. * 取得范围内不重复随机数函数
  36. */
  37. uchar un_repeat_random(uchar n)
  38. {
  39.         static uchar ran_count =0;
  40.         uchar i;

  41.         if(ran_count==n) ran_count = 0;
  42.         if(ran_count==0)
  43.                 upset_random_buf(random_buf, n);
  44.         i = random_buf[ran_count++];
  45.         return i;
  46. }

  47. /*
  48. * 打乱一个顺序数组,使其成为随机数组
  49. */
  50. void upset_random_buf(uchar *ranbuf, uchar n)
  51. {
  52.         uchar i, j, t;

  53.         for(i=n-1;i>0;i--)
  54.         {
  55.                 j = random(i);
  56.                 t = ranbuf[i];
  57.                 ranbuf[i] = ranbuf[j];
  58.                 ranbuf[j] = t;
  59.         }
  60. }

  61. /*
  62. * 定时器计数做种子
  63. */
  64. uchar random(uchar i)
  65. {
  66.         uchar k;
  67.         int t;

  68.         srand((int)(TH0*256 + TL0));
  69.         t = rand();
  70.         k = (uchar)(t % i);

  71.         return k;
  72. }

  73. /***************************************************/

  74. /*
  75. * 初始化定时器
  76. */
  77. void initial_timer(void)
  78. {
  79.         TMOD = 0x01;
  80.         TH0 = 0;
  81.         TL0 = 0;
  82.         TR0 = 1;
  83. }


  84. // 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表进行伪随机去吧。我之前做过一些小案子,由于RAM不够,只能用表的方式,每次产生一个随机数,指向对应的表就行了。简单,高效
jtboy105 发表于 2011-5-9 21:24 | 显示全部楼层
如果是用算法,如果是产生100个数内的,你肯定要用的RAM很多,单片机RAM本身就不多,你就不用做别的事了。最多建几个几K的表。
 楼主| sysdriver 发表于 2011-5-9 22:16 | 显示全部楼层
有一个很简单的方法,建几个table表进行伪随机去吧。我之前做过一些小案子,由于RAM不够,只能用表的方式,每次产生一个随机数,指向对应的表就行了。简单,高效 ...
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 | 显示全部楼层
我是用EXCEL中的宏进行产生一些表,之前一个案子是,从20道题目里每次随机出10道不重复的题。
方式如2楼一样,只是用这种方式,随机产生一些表,比如可能产生100个这样符合要求的表。再用一个随机数,指定用100个中的那个表,顺序读出来就行了。
如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},...........
;
因为我用汇编,很少用C,仅供参考。呵呵,这个方法比较笨。
 楼主| sysdriver 发表于 2011-5-9 23:23 | 显示全部楼层
16# jtboy105

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

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

本版积分规则

5

主题

687

帖子

0

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