24小时热门版块排行榜    

查看: 901  |  回复: 21
当前主题已经存档。

wade_thunder

新虫 (小有名气)

去除法

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
rjjy(金币+1,VIP+0):谢谢交流! 6-20 20:34
wangen994(金币+1,VIP+0):谢谢交流 6-21 08:30
生成30个不重复的从100个之中去掉,可以提高两倍的效率
11楼2009-06-20 19:35:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ms98


wangen994(金币+1,VIP+0):谢谢交流 6-21 08:30
8楼正解哦,这个算法在“计算机编程艺术”中有阐述,主要原理是利用位置改变不会引入新的元素来产生随机和避免重复。
我的想法也是判断重复的,复杂度是O(n^2),而这个算法的复杂度是O(n)。
很巧妙,不知道谁第一个发现的,膜拜一下!
12楼2009-06-20 21:10:49
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ms98

★ ★
wangen994(金币+2,VIP+0):谢谢交流 6-21 08:30
引用回帖:
Originally posted by dellus at 2009-6-20 08:38:
补充一下
采用数组G存放1-100
假设进行到某一步时存在N个未被选的数,选到其中第M个(M<=N),取出G(M),然后将G(M)赋值为最后一个数G(N),这样下一步数组中前N-1个数都是未被选到的,同样可以直 ...

这个方法挺有意思,另一个思路,佩服(我是看了答案后就不动脑筋了,这个方法让我想我是想不出来的)。
有个小问题,因为每一次都修改了rand函数的范围,这样得到的数字随机性可能会减小(具体可以看一下数论中关于伪随机数生成的原理)。
我看到的答案就是做1-100一个数组,然后取N次随机数,每一次都用该随机数作为下标来交换数字位置。例如:第一次得到随机数55,就让55和1交换位置,第二次得到随机数72,就让72和2交换位置。执行多次后,整个数组位置完全打乱,取头70个就好了。
13楼2009-06-21 02:49:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ms98

引用回帖:
Originally posted by wade_thunder at 2009-6-20 19:35:
生成30个不重复的从100个之中去掉,可以提高两倍的效率

话是这样讲了...
从算法角度来讲,生成30个不重复的,和生成70个不重复的时间复杂度一样,O(n^2),效率上一样的...
14楼2009-06-21 02:51:31
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

woshilsh

荣誉版主 (职业作家)

优秀版主

8楼办法确实好,简单使用,呵呵,
[center][url=http://www.91cool.net/][img]http://id.91cool.net/sign/?name=小木虫印&say=各位版主辛苦了![/img][/url][/center]
15楼2009-06-21 09:36:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

duyingchun

银虫 (小有名气)

★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
wangen994(金币+1,VIP+0):谢谢交流 6-27 08:39
把已经取过的数做个标记吧.
16楼2009-06-25 08:19:43
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

duyingchun

银虫 (小有名气)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖交流
wangen994(金币+2,VIP+0):感谢参与 6-26 13:43
用做标记的方法可以大大减少计算量,数越多优势越大,小于64K个数,可以用char数组,每个数占一个字节,64K~8*64K可以用位做标记,也可以用char数组,不过每一个数占一位,这种方法可以省去N多的检测循环,对于大数可以大大提高运算速度

#define TOTALNUM     100
#define MAXNUM          70

char *Mark=NULL;
unsigned int   RandNum[MaxNum];

void InitData()
{
Mark=(char *)malloc((TOTALNUM>>3)+1);
memset(Mark,0,(TOTALNUM>>3)+1);
}

void CreateData()
{
int n=0;
unsigned randdata;
char Mask[8]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};

while(n       {
        randdata=random(TOTALNUM);//取随机数
        if((Mark[randdata>>3]&Mask[randdata&0x07])) continue;//检测标记
        RandData[n]=randdata;//赋值
        Mark[randdata>>3]|=Mask[randdata&0x07];//做标记
        n++;//下一个数
      }
}

void DeleteData
{
free(Mark);
}

[ Last edited by duyingchun on 2009-6-25 at 08:41 ]
17楼2009-06-25 08:40:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

loujing

铁杆木虫 (正式写手)


小木虫(金币+0.5):给个红包,谢谢回帖交流
产生一个数组,里面放1-100共100个数,随机抽取,然后该位置0。
18楼2009-06-26 13:17:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ms98


wangen994(金币+1,VIP+0):谢谢交流 6-27 08:40
引用回帖:
Originally posted by duyingchun at 2009-6-25 08:40:
用做标记的方法可以大大减少计算量,数越多优势越大,小于64K个数,可以用char数组,每个数占一个字节,64K~8*64K可以用位做标记,也可以用char数组,不过每一个数占一位,这种方法可以省去N多的检测循环,对于大数可以大大 ...

这个方法可以节约空间并保证速度,但是用于只有100个数的数组...是不是大材小用了?
19楼2009-06-26 17:16:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

叶伟522

铁虫 (初入文坛)


小木虫(金币+0.5):给个红包,谢谢回帖交流
我写的程序:
#include
#include
int main(void)
{
        int a[70],i,j,m;
        a[0] =rand() % 100;
        for (i=1; j<70; i++)
        {
                m = rand() % 100;
                for (j=0; j                 {
                        if (m != a[j])
                        {
                                a = m;
                        }
                }
        }
        for (i=0; i<70; i++)
        {
                printf("%d%c",a,i%7 == 6 ? '\n' : ' ');
        }
        return 0;
}
20楼2009-06-30 21:42:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 ms98 的主题更新
普通表情 高级回复 (可上传附件)
信息提示
请填处理意见