C++博客-qinzuoyan-最新评论http://www.cppblog.com/qinzuoyan/CommentsRSS.aspxzh-cnSun, 12 Dec 2010 16:20:07 GMTSun, 12 Dec 2010 16:20:07 GMTcnblogsre: 一道笔试题 - strrep()函数的实现[未登录]http://www.cppblog.com/qinzuoyan/archive/2010/06/11/117548.html#117626expterexpterFri, 11 Jun 2010 02:58:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2010/06/11/117548.html#117626

expter 2010-06-11 10:58 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2010/05/06/93306.html#114689ztztThu, 06 May 2010 10:48:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2010/05/06/93306.html#114689

zt 2010-05-06 18:48 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93451左言左言Sat, 15 Aug 2009 12:05:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93451
直接枚举法，你说的是对5040种排列依次猜测吗。。。？最坏情况下猜测次数可能5040次吧。或者你有更好的办法吗？


左言 2009-08-15 20:05 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93402凡客诚品凡客诚品Sat, 15 Aug 2009 03:35:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93402

凡客诚品 2009-08-15 11:35 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93389空明流转空明流转Fri, 14 Aug 2009 22:54:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/15/93306.html#93389

空明流转 2009-08-15 06:54 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93335左言左言Fri, 14 Aug 2009 08:06:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93335
我觉得不应当考虑概率，而应当考虑在任意时刻，可行解集合里任何数都有可能是正确结果。实际上就是在一个状态转移图中，任何可行的路径都有可能沿着走下去，每选择一个数，就走进了一个分支。


左言 2009-08-14 16:06 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93332东坡_居士东坡_居士Fri, 14 Aug 2009 07:55:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93332
恩，是这样，我现在觉得能存下来，不过需要hash一下，时间上应该还行，一两个小时我也认了~呵呵~

还有一个问题是这样，在一个可行解集合里，每一个数的概率是一样的吧？

东坡_居士 2009-08-14 15:55 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93331左言左言Fri, 14 Aug 2009 07:49:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93331上面公式还可以进一步修改一下：
t(F) = min{ t( F- conf(f) ) + 1, for all f belongs to F}， 其中conf(f)指与f冲突的集合（每一种返回结果就对应一个冲突集，所以复杂度又上升了）。

左言 2009-08-14 15:49 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93330左言左言Fri, 14 Aug 2009 07:44:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93330我猜测你也在考虑“动态规划”方法。
我考虑过“动态规划”算法，递推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是当前可行集，t(F)为该可行集 F 条件下猜出结果的次数，f 为 F 中的一个可行排列。
但是我没有编程实现，因为担心复杂度太高运行不完。但是可以保证这样能得到最优解。
贪心算法得到的应当不是最优解，但是近似最优解，而且也是可以接受的。

左言 2009-08-14 15:44 发表评论
]]>re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现http://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93326东坡_居士东坡_居士Fri, 14 Aug 2009 07:32:00 GMThttp://www.cppblog.com/qinzuoyan/archive/2009/08/14/93306.html#93326恩，我理解错了~

我之前想的新的思路是这样：

因为问题的根源都在于我们怎样评价一个状态的好坏，我们现在都用数字的多少区评价，数字越多越糟糕。这个评价还是很初级简单的。

显然，既然求最小步数，那么最准确的评价就是，这个状态可以（平均、最坏）多少步得到解。

但是，这个评价标准需要递归（太慢，我测试9876用了十几分钟），或者记录状态（太大存不下）

我现在在想这个的优化~希望在可接受时间内跑出所有解~

东坡_居士 2009-08-14 15:32 发表评论
]]>