Python代码
: 猜数字游戏的八步以内求解程序
001
#coding=utf-8
002
003
#猜数字游戏8步以内的求解程序
004
#每次给出结果,要求输入xAyB,比如2A0B这样的结果,不分大小写
005
#
006
#解题思路很简单:
007
#1. 生成所有的四位不重复的0-9的数字组合的集合
008
#2. 随便找四个数字,比如0123
009
#3. 根据用户返回结果(xAyB),砍掉集合里面不符合结果的
010
#4. 根据现有数字组合,猜下一个,主要技术含量在这里:
011
# a. 贪心算法,每次都找当前步骤里最优的
012
# b. “最优”的定义:
013
# b1. 选择一个组合
014
# b2. 把这个组合和剩下的组合进行匹配,统计xAyB出现的次数,
015
# 比如0A0B出现了10次,1A3B出现了0次等等
016
# b3. 如果xAyB的所有可能出现的机会最为均等,那么这个选择的“区分度”就很大
017
# 这个可以通过信息量理论进行衡量,也可以简化为通过“最小标准差”来衡量
018
# b4. 遍历所有组合,找出“区分度”最大的
019
#5. 重复步骤3, 4,直到用户给出4A0B或者集合里面只剩下一个元素
020
#
021
022
#生成所有的四位不重复的0-9的数字组合
023
# by Leo Jay
024
# 灭掉了所有的判断语句,同时用展开的方法灭掉了set,目前已知最快的
025
# 应该不能更快了,因为这个版本已经没有多余的操作了
026
#其他方法参见:http://www.fayaa.com/code/view/114/
027
def
init_set
():
028
ret
=
[]
029
for
i
in
xrange
(
0
,
10
):
030
for
j
in
xrange
(
i
+
1
,
10
):
031
for
k
in
xrange
(
j
+
1
,
10
):
032
for
l
in
xrange
(
k
+
1
,
10
):
033
ret
.
append
((
i
,
j
,
k
,
l
))
034
ret
.
append
((
i
,
j
,
l
,
k
))
035
ret
.
append
((
i
,
k
,
j
,
l
))
036
ret
.
append
((
i
,
k
,
l
,
j
))
037
ret
.
append
((
i
,
l
,
j
,
k
))
038
ret
.
append
((
i
,
l
,
k
,
j
))
039
ret
.
append
((
j
,
i
,
k
,
l
))
040
ret
.
append
((
j
,
i
,
l
,
k
))
041
ret
.
append
((
j
,
k
,
i
,
l
))
042
ret
.
append
((
j
,
k
,
l
,
i
))
043
ret
.
append
((
j
,
l
,
i
,
k
))
044
ret
.
append
((
j
,
l
,
k
,
i
))
045
ret
.
append
((
k
,
i
,
j
,
l
))
046
ret
.
append
((
k
,
i
,
l
,
j
))
047
ret
.
append
((
k
,
j
,
i
,
l
))
048
ret
.
append
((
k
,
j
,
l
,
i
))
049
ret
.
append
((
k
,
l
,
i
,
j
))
050
ret
.
append
((
k
,
l
,
j
,
i
))
051
ret
.
append
((
l
,
i
,
j
,
k
))
052
ret
.
append
((
l
,
i
,
k
,
j
))
053
ret
.
append
((
l
,
j
,
i
,
k
))
054
ret
.
append
((
l
,
j
,
k
,
i
))
055
ret
.
append
((
l
,
k
,
i
,
j
))
056
ret
.
append
((
l
,
k
,
j
,
i
))
057
return
ret
058
059
#对给定的两组数,计算xAyB
060
#不知道能不能更快些
061
def
get_match_ab
(
target
,
source
):
062
la
,
lb
=
0
,
0
063
for
(
i
,
t
)
in
enumerate
(
target
):
064
for
(
j
,
s
)
in
enumerate
(
source
):
065
if
s
==
t
:
066
if
i
==
j
:
067
la
+=
1
068
else
:
069
lb
+=
1
070
#break this loop since we already found match
071
break
072
return
(
la
,
lb
)
073
074
#检查target与source是否符合aAbB
075
def
match_guess
(
target
,
source
,
a
,
b
):
076
(
la
,
lb
)
=
get_match_ab
(
target
,
source
)
077
return
la
==
a
and
lb
==
b
078
079
#nums: the number_set list to be checked
080
#guess: last guess
081
#a, b: the number of aAbB
082
#@return: the rest number_sets which matche last guess
083
def
check_and_remove
(
nums
,
guess
,
a
,
b
):
084
rest_nums
=
[]
085
for
num_set
in
nums
:
086
if
match_guess
(
num_set
,
guess
,
a
,
b
):
087
rest_nums
.
append
(
num_set
)
088
return
rest_nums
089
090
#计算一个选择相对于选择集的“标准差”
091
def
calc_standard_deviation
(
target
,
nums
):
092
#a * 10 + b is used to indicate an "a & b" combination
093
ab_map
=
{}
094
#init ab_map
095
abs
=
(
0
,
1
,
2
,
3
,
4
,
10
,
11
,
12
,
13
,
20
,
21
,
22
,
30
,
31
,
40
)
096
for
ab
in
abs
:
097
ab_map
[
ab
]
=
0
098
#let's do the calculation
099
for
num_set
in
nums
:
100
(
a
,
b
)
=
get_match_ab
(
num_set
,
target
)
101
ab_map
[
a
*
10
+
b
]
+=
1
102
ab_counts
=
[
ab_map
[
ab
]
for
ab
in
abs
]
103
total
=
sum
(
ab_counts
)
104
avg
=
float
(
total
)
/
len
(
abs
)
105
sd
=
sum
([(
abc
-
avg
)
**
2
for
abc
in
ab_counts
])
106
return
sd
107
108
#根据现有集合寻找下一个集合
109
#采用“最小标准差”作为衡量标准
110
def
next_guess
(
nums
):
111
min_sd
=
0
112
min_set
=
()
113
touched
=
False
114
for
num_set
in
nums
:
115
sd
=
calc_standard_deviation
(
num_set
,
nums
)
116
if
not
touched
or
min_sd
>
sd
:
117
touched
=
相关推荐
python第一次写,猜数字 XAXB的小程序,写的不好,留着学习,正在写破解,觉得可以7次内完成,目前未完成
用c语言编写的猜数字游戏,就是四位数字,电脑提示xAxB,程序很清楚,简单明了。
每次猜测时需依序输入4个数字,程序会根据猜测的情况给出xAxB的反馈: A前面的数字代表:数字和位置都对的个数 B前面的数字代表:数字对但是位置不对的个数 举例说明: 如果这四个格子里面的数字为:1234,那么对于...
在十个数字0,1,2,3,4,5,6,7,8,9 文曲星会随机产生2个数让你来猜 你最多只有6次机会 例如 文曲星 随即产生 12这2个排列好的2位数字 ...就这样,每次输入2个数字 文曲星都会返回 xAxB 但最多只能猜6次
文曲星猜字 • 在十个数字0,1,2,3,4,5,6,7,8,9 • 文曲星会随机产生2个数让你来猜你最多只有6次机会 • 例如文曲星随即产生12这2个排列好的2位数字 ...就这样,每次输入2个数字文曲星都会返回xAxB 但最多只能猜6次
每次猜测时需依序输入4个数字,程序会根据猜测的情况给出xAxB的反馈,A前面的数字代表位置和数字都对的个数,B前面的数字代表数字对但是位置不对的个数。例如:答案是1 2 3 4, 那么对于不同的输入,有如下的输出 ...
XAXB集团 这是 Hasse、Sam、Philip 和 Mads 的组合。 这是我们的服务器应用程序。