作者:梁利锋 标签:其它作品, Guess

5119天前 (阅读:11272)
  与以前的猜数字不同的是,这个程序主要是让电脑猜(也有玩者猜的界面),分别有几种不同的算法,目前“真正完全统计电脑猜数字”的效果最好,能在 7 步之内猜到;如果要猜测的数字首位不为 0 的话,则可以在 6 步之内猜到。
  我觉得很难做到比目前使用的“完全统计”算法更好的结果了,如果哪位有研究的话,欢迎讨论、指教,谢谢!
  增加了一个猜数字程序框架代码,优化一些代码,修正一些 Bug。

点击下载
mysword(非注册用户) 2004-5-14 21:58:08

评价标准不一样,就无所谓效果最好
你能保证7次猜到,但平均性能呢?就是说把5040个数据放进去,平均猜的次数有多少?
我现在做到的是5.31次,不知道你的性能如何呢?

梁利锋 2004-5-15 3:07:56

以这个标准,我的程序中最好的是“熵电脑猜数字”,5.338次;最差的是“傻瓜电脑猜数字”,5.56次。不过,我现在比较相信应该能在6步内猜到 —— 我还是对最大步数比较感兴趣 :)

跋锋寒(非注册用户) 2005-3-22 16:05:00

我用你的源代码,怎么改成数字只要1-9。不要0的。这样少一个数字的话,就只要更少的次数算出来。帮帮我

梁利锋 2005-3-22 20:45:29

修改主模块的 MyInitRand,令其只生成没有 0 的数字,修改 原始生成数字 函数,令其发现其参数 Num 中含有 0 的话,返回 false 就可以了。

yczni(非注册用户) 2005-8-15 10:17:07

目前我的最好结果:
第1步:1
第2步:5
第3步:55
第4步:627
第5步:2448
第6步:1850
第7步:54
6步猜中率:98.93%
5步猜中率:62.22%
平均步数:5.2385步


yczni(非注册用户) 2005-8-15 10:21:27

共5040个数,我只研究这个,首位不为0的那个我没研究过。
对5040个数我已证明了6步不可能猜完所有的数。
目前我的最好结果也要有54个数猜7步(这个结果与上面的证明无关)

yczni(非注册用户) 2005-8-15 10:23:41

猜数字联系我qq:149588829
请注明是聊猜数字

NadiaInoch(非注册用户) 2005-10-7 8:35:02

我目前最佳成绩:
总共26284步 平均5.215079步 最多7步猜中
  次数 n步以内%
1步  1  0.020%
2步  7  0.159%
3步  59  1.329%
4步 693  15.079%
5步 2436  63.413%
6步 1768  98.492%
7步  76 100.000%
算法很简单,只是这个算法要算非常非常久, 部分制成查表法后就快多了

yczni(非注册用户) 2005-10-13 7:42:02

不错,平均步数我到是没有那么好,我研究的方向是7步100%在六步猜中国率最大的情况下使五步猜中率也最大,目前的率步猜中率为98.93%,五步猜中率为62.48%,NadiaInoch,能留下qq吗

yczni(非注册用户) 2005-10-13 7:57:06

值得一提的是平均步数与6步猜中率是一对矛盾,要提高6猜中率,平均步数就要下降,要提高5步猜中率,平均步数同样也要下降,每步都是如此,当然这只是相对的一个好算法还是可以比一个差算法什么都好,但要达到最好的话平均步数和6步猜中率是不可能同时到最大的。顺便问一下,NadiaInoch你的程序算了多少天

yczni(非注册用户) 2005-10-13 12:36:30

NadiaInoch:再问你个问题,希望你能回答,如果第一步猜0123报出0A1B,第二步你的程序会猜什么

NadiaInoch(非注册用户) 2005-10-13 22:10:18

我不用QQ,只有MSN:nadiaInochi@msn.com(但这个不收信),mail请寄:nadia@ms34.url.com.tw
目前我是用树状展开来挑选最短路径,在同样总路径长最短的几组数据中,还是可以选择7次出现率较低的
我用的是HTML+javascript,无限路径展开法要算非常久,常常只能切割成小问题来分析,即使如此还是要算一两天

NadiaInoch(非注册用户) 2005-10-13 22:15:34

并且只从可能答案来展开路径(近似最佳解)和把所有5040组解都列入试算(最佳解)耗费时间会相差非常多
因此实作程序时是把运算所得转成动态查表法,可以试试:http://myweb.hinet.net/home3/nadiainochi/guessnum3.htm
(会另开窗口显示数据,因此要允许快显)
猜0123得0A1B,第二步猜与0123的关系为0A1B的任一组皆可,ex:3456

NadiaInoch(非注册用户) 2005-10-13 22:28:07

我的运算法可用数学理论验证它能找到最佳解(最低平均猜测次数),因为它搜寻了所有可能猜测路径,只是计算时间是个大问题,有兴趣可Email来谈,版主抱歉占用了这里一些空间

NadiaInoch(非注册用户) 2005-10-13 23:00:50

提出一个有趣的问题,当可能答案剩下这六组{1936,2936,7036,7236,7906,7916}时,猜什么数字可以用最少的平均猜测次数猜中答案?

yczni(非注册用户) 2005-10-16 12:50:51

http://myweb.hinet.net/home3/nadiainochi/guessnum3.htm
这个页我打开后都是乱码

yczni(非注册用户) 2005-10-16 12:56:56

没想到这么快你就给我答复,真是很高兴。因为由我作的一些结果看要是允许有一个数猜8次平均步数就会降低好多,所以我就转而去研究六步猜中率和五步猜中率。

yczni(非注册用户) 2005-10-16 13:22:51

http://myweb.hinet.net/home3/nadiainochi/guessnum3.htm
我用了一下这个页面里的程序,怎么它猜了4次就不猜了,打出来了21个数,你能不能写一个直到猜出为止的程序
我的email是zzzwww0899@163.com
我会给你发信的

yczni(非注册用户) 2005-10-16 13:44:18

问一下你那6个数是怎么产生的,经过怎样的猜的过程,我的程序是把5040个数编成了1到5040个数,如果中途再转换比较麻烦,6个数是可以完全搜索找到最佳答案的

yczni(非注册用户) 2005-10-16 13:46:48

不知道为什么我写好了的信发不出去,不知道163出了什么问题,收信到是可以。我这人很少聊天,又不喜欢用新事物,所以一直也没用msn

yczni(非注册用户) 2005-10-16 13:50:32

最好第一个数是猜0123因为我的程序第一个数都是猜0123,要是改的话就要通过换算也很麻烦

yczni(非注册用户) 2005-10-16 17:34:56

我可以基本断定我们俩的做法差不多,方向不太一样,但都在做着一样的事。
我只有一台机器,而且不快。
所以效率很低
平均步数的差别关键在0A1B差了一百多步

yczni(非注册用户) 2005-10-16 19:29:44

天下居然有此等不谋而合的事,你算出这个最小的平均步数如果用一台机器的话要用多久

NadiaInoch(非注册用户) 2005-10-17 0:36:43

我的程序正常可用,请将语言设成繁体中文,并请不要封锁快显功能,它会另开一个新窗口显示数据(不包括Hinet的广告窗口),如果这个新窗口没有被打开,程序就无法执行无限展开法,然后导致程序中途停止,无限展开法的计算需要数秒至数十秒,请耐心等待,还有就是最好使用IE6.0来跑这个程序

NadiaInoch(非注册用户) 2005-10-17 0:41:05

那六个数是由下列猜测顺序产生:猜7936得3A0B;猜0126得1A1B;之后可能答案就是剩下:1936,2936,7036,7236,7906,7916这六组(这是之前找到的最佳猜测顺序,后来还发现更好的猜测顺序:第一次猜得3A0B的话第二次应该猜和第一次关系为1A1B的猜组,例:0123得3A0B的话,第二次应该要猜0345)

NadiaInoch(非注册用户) 2005-10-17 0:47:55

我没有特别去计测时间,为了测试各种猜测顺序的效率,以建构动态查表法, 程序前后跑了有几十天吧(CPU P4-2.4CG),不过给你的程序是用动态查表法搭配无限展开法,已经避开了前几手所需要的庞大计算,因此整场游戏猜到中为止只要一分钟以内的时间

yczni(非注册用户) 2005-10-17 10:57:39

我的思想和你差不多,确实没有几十天算不完,我现在只有白天时间算有时还会停下来做别的,很辛苦,猜数字我说得更清楚点就是分类,有些类5步以内可以猜出,但要扩大到6步平均步数就有减少的可能,但什么都要有标准而且当猜到这类时谁也不会想对方想的那个数刚好需要六次,所以我宁愿选择升高平均步数而让这类所有的数都在5步猜出,这样的例子有很多。

yczni(非注册用户) 2005-10-17 10:59:48

你说的那个我没算因为天天算很烦。我想5步猜出平均步数会小些,但可在4步内猜出。我的之所以能有到这一步是由于我做了一个六步不可能猜出所有数的程序证明,稍变一下形做的事和你就差不多了。

yczni(非注册用户) 2005-10-17 11:11:39

7步100%是第一个标准。之后我的标准1是6步猜中率最大,然后考虑平均步数最小。标准2是6步猜中率最大,然后是5步猜中率最大,然后是平均步数。现在我也做了一些以你的标准的事,平均步数确实降了很多,但6步猜中率也降了。

yczni(非注册用户) 2005-10-17 13:23:14

其实我们能做的也就是递归两次,5040*13*5040*13,再多了,我们的机会就算不过来了,我是从今年的六月份才做的六次不能猜出所有数的证明,然后七月份就做了你所谓的无限展开法,我的说法就是分类。寻找6步猜中率的最大值,5步猜中率的最大值,差不多用了一个月。七月底的结果是六步猜中率为98.93%,现在已没什么信心再做下去了。

yczni(非注册用户) 2005-10-17 13:32:31

一个数对一组数进行分类可以得到00,01,02,等等共14类,我一开始做了一个假设,如果两个数对一组数进行分类所得到的对应类中数的个数相同,则这样的两个数我只检查一个,以使要检查的数变少,但后来我发现这个假设是错误的,我又做了更全面的检查,但我发现我一个人一台机器要进行更全面的检查实在是力不从心。

NadiaInoch(非注册用户) 2005-10-17 23:55:31

{1936,2936,7036,7236,7906,7916}的答案是猜0237,这样下一步可以依对方的回答全部猜中: 0A1B->7916; 1A0b->1936; 0A2B->7906; 1A1B->2936; 1A2B->7036; 2A1B->7236;

yczni(非注册用户) 2005-10-18 10:21:18

我没有写给出具体几个数后怎么猜的程序,我一直是自上而下的研究。你的那个页,我猜了四次后他说几步以内可以猜出剩下的数但是就不让我继续猜了,应该一直让人家猜完啊,其实我研究这个问题还有一个动力,就是有个人在2000年写了一个变底猜数字,我是2004才看到的,与他也联系不上了。

yczni(非注册用户) 2005-10-18 10:23:52

研究一个问题很有趣总是会有新的收获和想法,这个过程会让人有快乐的感觉,结果已经不重要了,最好的方法就是递归,关键是怎么剪支,过几天就会想到一个新方法去剪,很快乐。

yczni(非注册用户) 2005-10-18 10:51:53

问你个问题,第一步0123得2A0B第二步0245得1A0B剩下28个数,猜这28个数需要的最少步数是多少。如果允许6步内猜出所有的数则平均步数会小些,但这些数是可以在5步内都猜出的(平均步数会增加)。你会选哪种方法猜这些数。

NadiaInoch(非注册用户) 2005-10-18 19:13:04

你的问题我拿去跑双层5040的分析,目前还在运算中,系统估计它要算约1小时,目前分析了1/3,曾得到的暂时结果是总合78步/5手可猜中,后来被[9083]77步/6手取代(程序设定总步数少的优先),最终结果算完后我再Po出来

NadiaInoch(非注册用户) 2005-10-18 19:15:59

不知道是你的系统有冲到还是怎样, 也许换另一台计算机跑看看, 按理说有出现几步以内可猜中时, 同时也应该显示一个红色数字, 那就是它猜的数字, 你回答是几A几B以后它应该会继续运算下去, 这个程序在这边的BBS上公开过, 没有人反应过有这样的问题, 一定能运算到猜中为止的

yczni(非注册用户) 2005-10-18 19:38:01

其实只能递两层,三层就跑不动了,这可以说明你的做法是对的,我的做法也是对的只是时间问题。你还那么有信心在研究,真是佩服。几个月来我今天头一天没跑程序在看网页和表天

yczni(非注册用户) 2005-10-18 19:43:16

其实只要一组结果通过换算就可以了,这些都是我想做的,你已经都做完了。我是用pascal+excel做的现存数据几十m不过大部分都是没什么用的,pascal虽然老了点但我总是受其束缚不好再学其他语言,如果同样的事用c来做可能更快

yczni(非注册用户) 2005-10-18 19:49:44

这个地方真好,不需要注册,可以想怎么发就怎么发,其实这个问题再简单不过了,只是时间问题,我在证明六步不能猜完所有数的时候程序就跑了三个白天,是想到剪支后才三天不然就是80天。整个过程中就是想怎么找剪支的方法让我感受到最大的乐趣,总是会有新发现

NadiaInoch(非注册用户) 2005-10-18 20:01:25

我的程序的答案是0xx1(xx可填入任何到第二步为止还没猜过的数字,例:0671,0891等),分析结果是:"★总手数和76~104; 4次以内可猜中; 平均要猜2.714次".我把删去分支的动作称为"折迭",基本上还没猜过的数字6,7,8,9是"可折迭"的,在所有可能答案中不出现的数字2,5也是"可折迭"的,这次运算经过折迭后剩下501组数字要算,总共花费约40分钟

NadiaInoch(非注册用户) 2005-10-18 21:47:51

修改程序以压制最大手数的模式重跑,结果答案是xxx3(xxx以6,7,8,9随意代入,例:6783),总手数和78,总共5手以内可猜中,还有第二步你是选0245,我的话是0456,变底猜数字是会偷偷换答案的猜数字吗?我写过一个 http://myweb.hinet.net/home3/nadiainochi/ab-cheater.htm

NadiaInoch(非注册用户) 2005-10-19 5:13:49

经过初步计算,0123猜得2A后第二步你猜0245是对的,可以比我的猜法快约3步,现在正在深入计算中,这下查表法也要修改了,当初因为180组算两层太久,结果只算一层还真的不够可靠,总之谢谢你的数据~

yczni(非注册用户) 2005-10-20 7:28:12

就是因为有了变底猜数字所以我才证明了六次不可能猜出所有的数。方法很简单,在分类时每次都选最大的那一类,就可以了。就是说第一步一定是0A1B,以后看程序了。有趣的是如果第一步猜0A2B,以后都选最大的类就有办法在6次猜中.那个2000年之的程序就是这样的他只有第一步是0A1B,0A2B其它的都是最大的类,所以如果它给出0A2B我就可以在六步猜中

yczni(非注册用户) 2005-10-20 7:37:08

你的那个折迭2和5是我前几天刚刚想到的。原因就是当猜出0A0B时下面可猜的情况太多,折迭后七八百组数就剩100多组好算多了。你用的词都是很标准的计算机专业词汇,相比之下我就是个老土了。

yczni(非注册用户) 2005-10-20 7:44:18

我的第一个折迭方法就是那个假设,所来被认为是错误的,但也不是一点价值也没有的,至少它帮我找到了98.93%后来的方法保守很多第一步猜0123第二步猜时如果没有0123就猜4567如果0123出现过一个数就用456,789就不用了。如果出现两个数就用45,6789就都不用了,但1435和3415我认为是不同的猜法。

yczni(非注册用户) 2005-10-20 7:51:07

就是每一次寻找折迭的方法给我带来了很大的乐趣,程序的运行是枯燥的,我一般都会去做些别的。本来想做完了写本书,但天下总是会有这种无独有偶的事,所以又有点不想了。如果你想写的话,我们可以合作,把我的一些思想加进去,如果你是计算机专业的一定会有很多机器,应该让更多的机器跑起来。

yczni(非注册用户) 2005-10-20 7:56:44

我做猜数字时走了很多弯路,但我可以正重的说我的每一思想都是自子想出来的。我的第一个程序是在剩下的数中选一个编号(我对5040个数做了编号,用数组做的)最小的,这时有2个数要猜9次,有几百个数要猜8次,这时我是自上而下的第二步任选一个数,以后的还是每次取最小了,研究了一段时间,可以让所在的数都在7次内猜出,当时已是很高兴了。

yczni(非注册用户) 2005-10-20 8:03:15

所来我想到了分类,就想到了方差,所来我看了网上的说法就是梁利锋所谓的熵电脑猜数字,但是我是做了另外改进的这时我也试图用最开始的方法做了一两个月,所以我的结果比他的好,那时平均步数有5.265.后来还被一个计算机专业的写本科论文时用了我不知道他怎么写的,但我的一段代码给他了。

yczni(非注册用户) 2005-10-20 8:10:23

也就是在他那个本科论文写差不多完的时候,又(在这之前我有大半年没再研究了)燃起了我对猜数字研究的冲动,于是我对变底猜数字做了研究。后经改动就是现在的递归方法了。其实我作的不是递归,是自上而下正着写的,有点相当于递归。你一定是计算机专业的而且对计算机的字体还相当有研究,程序用的是繁体字。

yczni(非注册用户) 2005-10-20 8:28:55

你的那个折迭的方法我还真想过,就是看下一步猜的数和上一步是几A几B的关系(也用在了第二步的试猜上),但我没有做深入研究。第一步猜0123,第二步猜1045和4510是有些不同的。1045的1占了0123中0的位置,而4510互相都没有占对方的位置,虽然他们和0123都是0A2B的关系但还是有不同的,如果到了每三步我就想不清是什么关系了,所以这种方法我就没有深入的想了。

yczni(非注册用户) 2005-10-20 8:36:43

你是做什么工作的,多大了。我毕业两年多了,现在是个教书的,很没意思,由于我是学俄语的没什么英语基础所以很难。要是有计算机的活肯要我,我会加倍努力。愿意为计算机贡献出我的力量。本人只求学技术,工资多少无所谓。

NadiaInoch(非注册用户) 2005-10-21 6:14:20

其实关于计算机和算法方面我都是自学的,词汇的使用是直觉想到怎么用就用了,所以也没有什么专业用词啦,我自己也是只有两台计算机,其中一台很慢很少用,我用繁体字是因为我住在台湾,要打简体字还要靠Word做转换呢,我30几岁,目前长期洗肾(血液透析)中,算法方面的研究是我空闲时的乐趣

NadiaInoch(非注册用户) 2005-10-21 6:19:38

你的第一个折迭的假设我也有在用,试过的结果是如果只用它来折迭可能答案和可能答案之间的关系(表内无限展开)还算是好用,如果用它来折迭可能答案和所有5040组数字间的关系(全5040组无限展开),好像比较容易发生漏掉最佳猜数的情形

NadiaInoch(非注册用户) 2005-10-21 6:37:22

我曾经写E-Mail过去,不知道你有没有收到,猜数字程序我写好后已经放着一段时间没动了,最近碰到你才再开始跑测试做一些修改,近日和朋友合作了一个黑白棋的小游戏(我写程序, S.H源提供绘图),有空不妨玩玩看, S.H源和我都玩不过5级的计算机 http://myweb.hinet.net/home3/nadiainochi/othello/index.htm

yczni(非注册用户) 2005-10-21 12:49:44

原来的假设,不是很好,但有很好的参考价值,我的新的方法虽然也有用但折不了那么多,算起来很烦。那你要保重身体呀,如果不是你我也许还会研究,看到这种无独有偶的情况,我还反而解脱了,我的平均步数几乎是不可能达到你的那么好,所以我四天没运行程序了,停下来调整一下。

yczni(非注册用户) 2005-10-21 12:56:05

我很少看邮箱,现在马上看。我用的是pascal,而且我只用了数组和循环,说真的其它功能不是很会用。所以我也看到过网上的黑白棋文章,但这对我来说就是很无力的了,我很想入到计算机里,不过目前只能是自己乱做点东西

NadiaInoch(非注册用户) 2005-10-26 7:55:50

寄来的数据已经收到了, 谢谢, 之后想把资料用”前两层5040组无限展开法”+”其它层表内无限展开法”计算, 其中光是分析一组378个数字的预估时间就高达2000小时, 还好现在程序改过后可以分段计算, 我打算在有用到计算机的时候让它在背景慢慢算…目前成绩26278 / 5040 = 5.213889手

yczni(非注册用户) 2005-11-20 11:16:36

遇到你后,我已几个星期没再搞程序了,也许再弄也不会有你的结果好了。
那么多个月的努力我觉得我最大的成就就是完整的证明了六次不可能猜完所有的数。
还有就是六步猜中在98.93%。
其它的就没什么有用的东西了。

mrmengyi(非注册用户) 2005-12-27 19:26:42

yczni,怎么联系不上你呢~?
我想知道你是怎么证明6次不能猜出来的。
我目前的想法就是全部遍历一遍,反正公司计算机多,晚上分开来在几个计算机上跑,嘿嘿。

mrmengyi(非注册用户) 2005-12-27 19:28:20

mail:mrmengyi@sina.com
不晓得为什么公司把163.net的信箱过滤,只好用这个啦

mrmengyi(非注册用户) 2005-12-27 19:30:54

还是QQ吧,sina也过滤了,太过分了~

Owen(非注册用户) 2006-1-7 23:27:06

我找出最佳解了……
http://www.javaworld.com.tw/jute/post/view?bid=35&id=140216&sty=3&age=0&tpg=1&ppg=1#140216

yczni(非注册用户) 2007-6-10 9:17:49

我又回来了,还想再弄弄

yczni(非注册用户) 2007-6-10 9:18:59

我的qq149588829
你是哪个公司的
你的qq是多少

高某(非注册用户) 2007-7-21 16:11:10

帮忙猜猜,每句话猜一个字. 关公策马走单行,人尔相逢两不离.数千数万从我起,几棵树木不成林.
文字里面我最行.阴曹地俯为首领`

Now I'm like, well duh! Truly thknufal for your he(非注册用户) 2013-8-28 15:27:12

Now I'm like, well duh! Truly thknufal for your help.

Such a deep answer! compared levitra viagra dosing(非注册用户) 2014-2-4 23:10:06

Such a deep answer! compared levitra viagra dosing heliomeds.com  bestlifeinsurpolicy.com  comparehealthinsur.com virgin islands health insurance GD&RVVF

It occasionally actually inquires, when an inciden(非注册用户) 2014-3-4 10:15:39

It occasionally actually inquires, when an incident is investigated by an insurance QuotesChimp. Frequently, including critiquing your previous health-related records and also additional useful content. Perhaps you are requested to signal mandates for the business to get such owner's manual, that you should do unless you might have legitimate reasons for refusing the petition (like being requested to reveal personal info which doesn't have anything regarding your state).