设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索
楼主: 沙漠点灰

[讨论] 几个有意思的问题_第二弹

[复制链接]

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-12 02:29:26 | 显示全部楼层
evolniar 发表于 2011-4-11 11:00
你看错啦,我的代码是,通过算一次,不通过也算一次~

while 结束后会立刻进入 if 内部 o_o
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-12 04:40:01 | 显示全部楼层
苏小脉 发表于 2011-4-12 02:29
while 结束后会立刻进入 if 内部 o_o

while (n < number)

    {

      num[n-1]=0;

      n=n+2*i;

      time+=1;

    }

    if (n>=number)

    {

      time+=1;

    }
你看错了吧。。。怎么毁呢
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-12 07:22:21 | 显示全部楼层
evolniar 发表于 2011-4-12 04:40
while (n < number)

    {

while 终止的时候,n >= number
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-12 11:50:52 | 显示全部楼层
本帖最后由 evolniar 于 2011-4-12 11:54 编辑
苏小脉 发表于 2011-4-12 07:22
while 终止的时候,n >= number


我明白你的意思了哈。
还有,我们的代码除了i与i*2,之外,没什么差别。
怎么会“互补”呢?怎么可能减少100多次呢?
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-12 12:44:31 | 显示全部楼层
evolniar 发表于 2011-4-12 11:50
我明白你的意思了哈。
还有,我们的代码除了i与i*2,之外,没什么差别。
怎么会“互补”呢?怎么可能减少 ...

学生判断了外层循环变量 i 是否是质数,如果是则往后筛,否则不用筛,因为 i 的质因数的所有倍数在先前的迭代中已经都被筛掉了,其中就包含了 i 自己的所有倍数。
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-12 14:46:46 | 显示全部楼层
苏小脉 发表于 2011-4-12 12:44
学生判断了外层循环变量 i 是否是质数,如果是则往后筛,否则不用筛,因为 i 的质因数的所有倍数在先前的 ...

你这个想法很好,我也考虑过了。
但是你有没有想过,每判断一次 i 是不是质数,也算一次迭代啊。。。所以,用这个方法,迭代次数是不会减少的。
不过我思考了许久,还是想出了一个简化方法,把迭代次数减少到了472次。
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-12 15:20:39 | 显示全部楼层
evolniar 发表于 2011-4-12 14:46
你这个想法很好,我也考虑过了。
但是你有没有想过,每判断一次 i 是不是质数,也算一次迭代啊。。。所以 ...

学生前日见先生说“每一次判断都得算作一次迭代”时就颇为疑惑,不解先生对迭代的定义是什么。依 Wikipedia 定义,迭代是“通过从一个初始估计出发寻找一系列近似解来解决问题的过程”。在我们讨论的 Eratosthenes 筛法中,若是不计初始化,只剩枚举奇数和筛选这两个(循环)过程可被称为迭代。我们加入计数递增之处正是(处于相同循环之中的)一系列语句被循环执行了一次之时。

这里是否是质数的判断仅仅涉及到了一次数组的随机访问,O(1) 的时间并不会增加算法复杂度,反而会避免很多次不必要的循环。我们计算迭代次数纯粹是为了满足楼主在主楼的需求,但迭代次数只能针对算法时间复杂度,不能针对真实的执行效率。
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-12 15:32:02 | 显示全部楼层
本帖最后由 fux2 于 2011-4-12 16:50 编辑
苏小脉 发表于 2011-4-12 15:20
学生前日见先生说“每一次判断都得算作一次迭代”时就颇为疑惑,不解先生对迭代的定义是什么。依 Wikiped ...


你的意思是,跳过i=9,15,21,27?
我对迭代(iteration?)的定义是:每进行一次一次判断,即为一次迭代
.
刚才又做了测试,按我的定义,迭代次数472,。按你的定义,迭代次数457.也有可能是462

夜深了,我去睡了
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-13 04:33:21 | 显示全部楼层
evolniar 发表于 2011-4-12 15:32
你的意思是,跳过i=9,15,21,27?
我对迭代(iteration?)的定义是:每进行一次一次判断,即为一次迭代
.

i 是所有合数的时候都跳过了。462 是我的答案,457 是不计没进入内层 while 的场合,但确实该计~
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-13 06:14:08 | 显示全部楼层
苏小脉 发表于 2011-4-13 04:33
i 是所有合数的时候都跳过了。462 是我的答案,457 是不计没进入内层 while 的场合,但确实该计~ ...

while ((n==9)||(n==15)||(n==25)||(n==21)||(n==27))
你不认为这种方法太机械了么。
改成 if (((i!=3)&&(i%3==0))||((i!=5)&&(i%5==0))) 更好,还是逻辑判断。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:fux2@moe9th.com|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2019-7-20 13:56

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表