回 帖 发 新 帖 刷新版面

主题:致歉,关于第56次编程比赛

实在对不起大家,因为毕业离校,网络不通,加上马上要工作了,琐碎的事情也不少。这次比赛的结果迟迟没有公布,在这里向大家道歉了。

我现在在网吧给iAkiak测了一下,从0123到9876,每个数字都能在七次内正确猜出。不过运行效率稍低,我运行了接近一个小时才把数千个数字全部验证完。

关于其他几位参赛者的情况。
yuanhongqian123:看来你并没有弄清楚题目的意思。题目是要你的程序来猜数字,不是让用户输入数字。
逆行行:也没有弄清题目的意思。而且接口也被修改掉了。
htqx:你帖代码的时间晚了点~ 并且直接使用rand函数,似乎猜中的几率太低了。你可以参考一下后面我的思路。

因此,这里选择[color=FF0000]iAkiak作为比赛的冠军[/color]。

我叙述一下我的思路:
首先,所有的数字都有可能。在这些可能的数字中,选择一个来“猜”,然后会得到几A几B的结果。根据这个结果,判断出某些数字其实是不可能的,将它们删除。在剩下的可能数字中再选择一个来“猜”,直到猜中或者次数用尽为止。
iAkiak的程序比我的要复杂的多,速度也慢了上百倍,从实际效果上看,分数也比我的略高,但大体的思路也是一样的。但是iAkiak的程序中,保存“可能的数”时使用了vector,并且利用push_back和pop_back来操作,这可能是效率低下的原因。我的做法是使用一个bool数组来保存每一个数是否可能,这样快了不少。

最近确实上网的机会太少,过两天还要坐40个小时的火车去到工作的地方。等不那么忙了,我会再来的。到时候也会放出新一课的OpenGL入门教程。

看到飞燕选为了斑竹,在这里祝贺一下。

回复列表 (共5个回复)

沙发

我对这个题目的评价:题目门槛高了,加上是在期末阶段,
愿意去做并且有时间的人相对很少。
并且由于这是在论坛,不是Online Judge,菜鸟毕竟占大多数。
论坛的编程比赛应该是带动大家来学习。
我认为应该要找些想出思路不难,也不复杂,但大有优化余地的题目

板凳

呵呵,我专门让它多算一会找得分能高一些的数来猜。
"每次调用不超过10秒,内存不超过1G"这个限制,用来测试所有的5040组,那恐怕要测14小时了...

我的思路是:任意一次猜测能得到的反馈数据(nAmB)可以用来把可能解做一次分类,每次分类都将使得可能解的范围缩小。猜什么数字能够使得最坏情况下可能解的数量最小,这个猜测是当前情况下最有效的。
注意,这里可能会选择猜一些不在可能解集合内的数甚至猜测包含同样数字的数。
但由于尝试所有的可能(10000次比较)耗费时间太长,于是采用随机算法,抽取一部分数字,取其中最有效缩小可能解的数字来猜。

如果把代码里
//#define USE_RANDOM
的注释打开,应该就和你的算法一样了。

3 楼

我还是喜欢难一点的题目,毕竟,我不是菜鸟~~~

4 楼

那楼上的比偶强,偶还是小菜鸟一个

5 楼


嘻嘻,只可惜比赛那会偶还没来呢。[em11][em12]

我来回复

您尚未登录,请登录后再回复。点此登录或注册