有谁知道“猜数字”游戏的算法?(50分)

  • 主题发起人 主题发起人 iCANK
  • 开始时间 开始时间
Town:
以下这步花的时间太长,因为遍历的数字多,又要进行比较,不知道有没有办法改进。
遍历第二步中的数组, 把所有与1234比较的结果等于xAyB的都保留下来,
保存到数组或者TStringList中
 
现在大家已经到了比速度的阶段了——看来我可以出场了 :)

1.穷举0..9中任取4个数(不重复)的排列,我做了一个小程序,在亚秒级的时间内(大约0.2s吧)
就可以完成。(最终结果是字符串形式——上面的时间已经包含了字符串在Memo中的显示时间)

2.对这个问题,完全可以采用TList——它的节点可以存放一个Integer类型的数字,分成4Byte,
每个Byte表示一个0..9的数字——够用了吧?

3.第一步生成的时候并不需要穷举所有排列——只要将所有组合穷举出来即可(从5040下降到210)。
根据回答可以将不合条件的组合删除掉,然后在剩下的为数不多的组合中进行穷举排列——每个组合
可以生成24种排列,在这一步可以进行进一步的过滤。
例如:
1234 的回答是 1A1B,对组合来说,就是有且仅有1+1个数字在1..4中。在进行穷举的时候根据
这一条进行过滤,就会得到: 1256,1257,1258,...,2459,...,3490
然后,对每个合理的组合进行全排列的穷举:
1256-> 1256, 1265, 1526, 1562, .....
1257-> .........
...........
将排列穷举的结果针对1A(有多少个B已经不必考虑了)进行过滤,最终得到: 1526, 1562, ...

由于采用了“组合-排列”技术,算法的复杂度被大大的降低了,我们甚至有充裕的时间在每一步
从头开始算起而不必使用以前的结果!
 
高手就是高手啊~~~
呵呵, 第一步确实没必要穷举全部排列的. 因为第一次猜中的概率
极低,所以没必要一定要包含此数字的.


 
多谢大家,有学了一招!:)

不过,没有多少分,不好意思。:P
 

Similar threads

S
回复
0
查看
1K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
900
SUNSTONE的Delphi笔记
S
S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
回复
0
查看
756
import
I
后退
顶部