应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 【讨论】出个算法题大家松松脑筋
222/3返回列表上一页123下一页
查看: 901  |  回复: 21
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前主题已经存档。

wade_thunder

新虫 (小有名气)

去除法

★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖交流
rjjy(金币+1,VIP+0):谢谢交流! 6-20 20:34
wangen994(金币+1,VIP+0):谢谢交流 6-21 08:30
生成30个不重复的从100个之中去掉，可以提高两倍的效率
赞一下(13人) 回复此楼
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)。
很巧妙，不知道谁第一个发现的，膜拜一下！
赞一下(6人) 回复此楼
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－１个数都是未被选到的，同样可以直 ...

这个方法挺有意思，另一个思路，佩服（我是看了答案后就不动脑筋了，这个方法让我想我是想不出来的）。
有个小问题，因为每一次都修改了rand函数的范围，这样得到的数字随机性可能会减小（具体可以看一下数论中关于伪随机数生成的原理）。
我看到的答案就是做1-100一个数组，然后取N次随机数，每一次都用该随机数作为下标来交换数字位置。例如：第一次得到随机数55，就让55和1交换位置，第二次得到随机数72，就让72和2交换位置。执行多次后，整个数组位置完全打乱，取头70个就好了。
赞一下(6人) 回复此楼
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
把已经取过的数做个标记吧.
赞一下(7人) 回复此楼
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 ]
赞一下(7人) 回复此楼
17楼2009-06-25 08:40:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

loujing

铁杆木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖交流
产生一个数组，里面放1-100共100个数，随机抽取，然后该位置0。
赞一下(1人) 回复此楼
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个数的数组...是不是大材小用了？
赞一下(6人) 回复此楼
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;
}
赞一下(1人) 回复此楼
20楼2009-06-30 21:42:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 ms98 的主题更新
222/3返回列表上一页123下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭