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

24小时热门版块排行榜    

Znn3bq.jpeg
小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 【讨论】出个算法题大家松松脑筋
222/3返回列表上一页123下一页
查看: 1089  |  回复: 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下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[教师之家] 上海大学实验技术岗位非升即走 +8 嘻嘻哈哈乐呵呵 2026-05-15 8/400 2026-05-18 11:53 by ning312
[硕博家园] 考博自荐 +5 科研狗111 2026-05-13 6/300 2026-05-18 11:22 by 糊糊涂涂好
[基金申请] 青C资助名额大幅增加！ +12 西葫芦炒鸡蛋 2026-05-13 16/800 2026-05-18 10:02 by Equinoxhua
[基金申请] 面上本子正文33页，违规吗？会被低分嘛？ +5 1234567wang 2026-05-17 6/300 2026-05-17 21:18 by maxjing
[找工作] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +4 ky2p12rrjj 2026-05-15 4/200 2026-05-17 19:47 by Equinoxhua
[硕博家园] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +6 l7k6xnh0yc 2026-05-14 7/350 2026-05-17 19:42 by Equinoxhua
[考博] 2026博士还有哪些学校有名额 +6 小王求读研 2026-05-15 7/350 2026-05-17 16:54 by 知音湖畔
[考博] 光量子物理方向 博士招生 1人（2026.09） +3 sandyworld 2026-05-15 4/200 2026-05-17 14:38 by sandyworld
[考博] 26/27博士推荐 +3 1木头人13949 2026-05-13 3/150 2026-05-17 09:41 by YuY66
[硕博家园] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +4 v9tggjlwd0 2026-05-15 4/200 2026-05-17 08:06 by 11n4dfd8yn
[考博] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +3 7hlccowb3h 2026-05-15 4/200 2026-05-17 07:46 by 11n4dfd8yn
[硕博家园] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +5 cjf4bx70cj 2026-05-14 7/350 2026-05-17 06:55 by 11n4dfd8yn
[考研] 售SCI一区T0P文章，我:8.O.5.5.1.O.5.4,科目齐全,可+急 +3 ky2p12rrjj 2026-05-15 4/200 2026-05-17 00:50 by ue3ir18jc3
[基金申请] 请问大佬b0816评完了吗 +4 市民华南虎 2026-05-12 8/400 2026-05-16 19:54 by Equinoxhua
[高分子] 本人最近太闲了，谁有问题可以提，每天会统一回复 +9 一切都是空工 2026-05-12 20/1000 2026-05-16 19:52 by Equinoxhua
[有机交流] 求助2，4-二氯-5-嘧啶甲醛的合成方法 20+3 光吃不拉 2026-05-14 6/300 2026-05-16 19:46 by Equinoxhua
[有机交流] 求有机合成大神指点三硫酸乙烯酯（CAS：2793408-99-6）的合成路线 30+3 Leekmid 2026-05-13 10/500 2026-05-16 16:37 by czyzsu
[有机交流] 如何实现卤原子转化 +3 BT20230424 2026-05-15 5/250 2026-05-16 16:20 by czyzsu
[文学芳草园] 风把牡丹吹跑了 +5 myrtle 2026-05-12 9/450 2026-05-15 15:27 by myrtle
[考博] 材料类只有一篇综述能申博么 +4 乐逍遥谷 2026-05-13 4/200 2026-05-14 12:05 by zhyzzh
信息提示
关闭
请填处理意见
关闭