蛋疼数学程序帝！猜数字解法

DeathKing

　　猜数字（又称 Bulls and Cows ）是一种大概于20世纪中期兴起于英国的益智类小游戏。一般由两个人玩，也可以由一个人和电脑玩，在纸上、在网上都可以玩。这种游戏规则简单，但可以考验人的严谨和耐心。

　　通常由两个人玩，一方出数字，一方猜。出数字的人要想好一个没有重复数字的4位数，不能让猜的人知道。猜的人就可以开始猜。每猜一个数字，出数者就要根据这个数字给出几A几B，其中A前面的数字表示位置正确的数的个数，而B前的数字表示数字正确而位置不对的数的个数。

　　如正确答案为 5234，而猜的人猜 5346，则是 1A2B，其中有一个5的位置对了，记为1A，而3和4这两个数字对了，而位置没对，因此记为 2B，合起来就是 1A2B。

　　接着猜的人再根据出题者的几A几B继续猜，直到猜中（即 4A0B）为止。

　　假定正确答案为1234，则：
　　0123 #=> 0A3B
　　1423 #=> 1A3B
　　1234 #=> 4A0B

　　试找到一种行之有效的方法，使得程序在最短时间以及最小尝试次数内（不能超过10次）找到答案。

　　可以是伪代码、Pascal语言、C/C++/C#语言、Basic语言、Ruby语言以及其他高级语言。并请各位自行编写生成正确答案与获得结果的函数。

---

1、百度百科，猜数字：http://baike.baidu.com/view/358630.htm
2、Mastermind - Wiki：http://en.wikipedia.org/wiki/Mastermind_(board_game)
3、Mastermind 解法综述：http://mathworld.wolfram.com/Mastermind.html
4、Knuth (1976). The Computer As Master Mind：http://www.dcc.fc.up.pt/~sssousa/RM09101.pdf
5、Kooi (2005). Yet Another Mastermind Strategy： http://www.philos.rug.nl/~barteld/master.pdf

429259591

这个我妈的手机有，可是我还是不明白游戏规则

david50407

出数字的人要想好一个没有重复数字的4位数 <===关键

不论 题目走访 或 答案走访 "最多"都要重复 4 * 4 = 16 次运算
不过因为上面的关键
所以只要这样就好

假C/C++ language... :
#include <stdio.h>
#include <stdlib.h>
char ques[] = "1234"
char ans[] = "0123";
int ans_l[10] = {-1};
int a = 0;
int b = 0;
int temp = 0;
for (int i = 0; i < 4; ++i)
  ans_l[atoi(ans)] = i; // atoi() convert char to int, and fetch answer's char into array list
// 差点就end了 = =|
for (int i = 0; i < 4; ++i)
  if ((temp = ans_l[atoi(ques)]) >= 0) // if the question's char is in the answer
    if (temp == i) // A
      ++a;
    else // B
      ++b;
printf("%dA%dB", a, b);

共 4 + 4 次 = =b

IamI

第三轮？继续决绝占楼
……最高次数不过5040次，毫无压力= =b

1. # 假定持有判定函数 answer(num1,num2,num3,num4)，返回数组[A,B]
   
2. # start
   
3. for i in 0..9
   
4.         for j in 0..9
   
5.                 for k in 0..9
   
6.                         for l in 0..9
   
7.                                 next if (i = j or i = k or i = l or j = k or j = l or k = l)
   
8.                                 return 1000 * i + 100 * j + 10 * k + l if answer(i,j,k,l)[0] == 4
   
9.                         end
   
10.                 end
    
11.         end
    
12. end

复制代码

神思

楼上想复杂了。其实4个数可拆开，逐个判断。次数不超过4*10…

orochi2k

蛋痛邪恶程序帝表示偶觉得直接找到存放答案的内存地址然后读它比较快（被PIA飞）

小幽的马甲

1. class Guess
   
2.   
   
3.   def initialize(answer)
   
4.     @ans = []
   
5.     for i in 0..9999
   
6.       @ans.push(i) if possible(i)
   
7.     end
   
8.     @s = answer
   
9.   end
   
10.   
    
11.   def possible(i)
    
12.     q = []
    
13.     q[0..9] = 0
    
14.     a = arr(i)
    
15.     for n in a
    
16.       return false if q[n] == 1
    
17.       q[n] = 1
    
18.     end
    
19.   end
    
20. 
    
21.   def arr(num)
    
22.     a = []
    
23.     for i in 0..3
    
24.       a[3 - i] = num % 10
    
25.       num /= 10
    
26.     end
    
27.     return a
    
28.   end
    
29.   
    
30.   def check(a1, a2, a, b)
    
31.     arr1 = arr(a1)
    
32.     arr2 = arr(a2)
    
33.     t = 0
    
34.     for i in 0..3
    
35.       t += 1 if arr1[i] == arr2[i]
    
36.     end
    
37.     return true if t != a
    
38.     q = Array.new(10, 0)
    
39.     t = 0
    
40.     for i in arr1
    
41.       q[i] = 1
    
42.     end
    
43.     for i in arr2
    
44.       t += q[i]
    
45.     end
    
46.     return t != a + b
    
47.   end
    
48. 
    
49.   def ask(num,num2 = @s)
    
50.     arr1 = arr(num2)
    
51.     arr2 = arr(num)
    
52.     a = 0
    
53.     for i in 0..3
    
54.       a += 1 if arr1[i] == arr2[i]
    
55.     end
    
56.     q = Array.new(10, 0)
    
57.     b = -a
    
58.     for i in arr1
    
59.       q[i] = 1
    
60.     end
    
61.     for i in arr2
    
62.       b += q[i]
    
63.     end
    
64.     return [a,b]
    
65.   end
    
66. 
    
67.   def getnum
    
68.     ti = rand(@ans.size)
    
69.     t = @ans.size
    
70.     for o in 1..10
    
71.       i1 = rand(@ans.size)
    
72.       i = @ans[i1]
    
73.       aa = 0
    
74.       r1 = [1000/@ans.size].min
    
75.       for r in 1..r1
    
76.         j = @ans[rand(@ans.size)]
    
77.         a, b = *ask(j,i)
    
78.         s = @ans.size
    
79.         for k in @ans
    
80.           s -= 1 if check(j, k, a, b)
    
81.         end
    
82.         aa = s if s > aa
    
83.       end
    
84.       if aa <= t and aa > 0
    
85.         t = aa
    
86.         ti = i1
    
87.       end
    
88.     end
    
89.     return ti
    
90.   end
    
91.   
    
92.   def calc
    
93.     time = 0
    
94.     while @ans.size > 0
    
95.       time += 1
    
96.       i1 = ((time == 1) ? 123 : getnum)
    
97.       i = @ans[i1]
    
98.       a, b = *ask(i)
    
99.       str = i.to_s
    
100.       str = '0' + str if i < 1000
     
101.       print "第#{time}次\n#{str}\n#{a}A#{b}B"
     
102.       if a == 4
     
103.         print "答案是#{str}"
     
104.         return true
     
105.       end
     
106.       for num in [email protected]
     
107.         @ans[num] = nil if check(i,@ans[num],a,b)
     
108.       end
     
109.       @ans[i1] = nil
     
110.       @ans.compact!
     
111.     end
     
112.     p "Impossible!"
     
113.     return false
     
114.   end
     
115. end
     
116. 
     
117. guess = Guess.new(1234)
     
118. guess.calc

复制代码

先丢半成品
关键在getnum这个方法上，先再想想= =

david50407

啊~原来是找出答案阿

建表?

1. $question = "5968"
   
2. 
   
3. $table = array.new
   
4. for i in 0..9
   
5.   for j in 0..9
   
6.     for k in 0..9
   
7.       for l in 0..9
   
8.         $table.push("#{i}#{j}#{k}#{l}") # 建表
   
9.       end
   
10.     end
    
11.   end
    
12. end
    
13. 
    
14. def check(c)
    
15.   a = b = 0
    
16.   if (p = $question.match("["+c+"]")) != nil # 测试是否有A或B的情况
    
17.     for i in p
    
18.       if $question.index(i) == c.index(i)
    
19.         a += 1
    
20.       else
    
21.         b += 1
    
22.       end
    
23.     end
    
24.   end
    
25.   return a,b
    
26. end
    
27. 
    
28. def guess(g)
    
29.   a,b = check(g) # 检查?A?B
    
30.   $table.collect! {|t| check(t) == a,b ? t : nil}
    
31.   $table = $table.compact
    
32. end
    
33. 
    
34. guess_times = 4
    
35. guess("1234")
    
36. guess("3456")
    
37. guess("5678")
    
38. guess("7890")
    
39. for i in $table
    
40.   guess_times+=1
    
41.   if guess(i) == 4,0 # 4A0B
    
42.     p "Ans: #{i}\nGuess #{guess_times} times"
    
43.   end
    
44. end

复制代码

应该就这样 (汗

紫苏

BullsAndCowsServices 模块：提供 Bulls and Cows 游戏和破译器的一些通用服务；
BullsAndCows 是 Bulls and Cows 游戏的类，其实例是一次游戏的实例；
BullsAndCowsBreaker 是用来解 Bulls and Cows 的破译器的类；

1. 
   
2. module BullsAndCowsServices
   
3.   # 生成无重复数位的随机四位数
   
4.   def generate_digits
   
5.     arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
   
6.     arr.slice!(rand(9))*1000 +
   
7.     arr.slice!(rand(9))*100 +
   
8.     arr.slice!(rand(8))*10 +
   
9.     arr.slice!(rand(7))
   
10.   end
    
11.   # 把四位整数转换为数位数组
    
12.   def digits2arr(digits)
    
13.     return [digits%10, digits/10%10, digits/100%10, digits/1000]
    
14.   end
    
15.   # 返回猜测的结果
    
16.   def judge(ans, num)
    
17.     a = b = 0
    
18.     ans_digs = digits2arr(ans)
    
19.     my_digs = digits2arr(num)
    
20.     for i in 0..3
    
21.       if my_digs[i] == ans_digs[i]
    
22.         a += 1
    
23.       elsif ans_digs.include?(my_digs[i])
    
24.         b += 1
    
25.       end
    
26.     end
    
27.     return a*10+b
    
28.   end
    
29. end
    
30. 
    
31. class BullsAndCows
    
32.   include BullsAndCowsServices
    
33.   attr_reader :step
    
34.   # 初始化
    
35.   def initialize
    
36.     @num = generate_digits
    
37.     @step = 0
    
38.   end
    
39.   # 猜一个数字，返回结果
    
40.   def guess(num)
    
41.     result = judge(@num, num)
    
42.     @step += 1
    
43.     p "guessing #{num}, (#{result/10}A#{result%10}B), step ##@step"
    
44.     return result
    
45.   end
    
46. end
    
47. 
    
48. 
    
49. class BullsAndCowsBreaker
    
50.   include BullsAndCowsServices
    
51.   # 初始化
    
52.   def initialize(bac)
    
53.     @bac = bac
    
54.     @possible_guesses = []
    
55.     for i in 1023..9876
    
56.       ans_digs = digits2arr(i)
    
57.       if ans_digs.uniq.length == ans_digs.length
    
58.         @possible_guesses << i
    
59.       end
    
60.     end
    
61.   end
    
62.   # 排除不可能的数字
    
63.   def eliminate(guess, result)
    
64.     @possible_guesses.delete_if do |possible_guess|
    
65.       indirect_result = judge(guess, possible_guess)
    
66.       indirect_result/10 != result/10 || indirect_result%10 != result%10
    
67.     end
    
68.   end
    
69.   # 开始破译
    
70.   def start_guessing(best_guess = 1023)
    
71.     loop do
    
72.       result = @bac.guess(best_guess)
    
73.       eliminate(best_guess, result)
    
74.       break if result == 40
    
75.       best_guess = @possible_guesses[rand(@possible_guess)]
    
76.     end
    
77.   end
    
78. end

复制代码

实际测试时可以：

1.   bac = BullsAndCows.new
   
2.   bacb = BullsAndCowsBreaker.new(bac)
   
3.   bacb.start_guessing
   

复制代码

使用的步数在 2-8 之间，实际上理论上可以是一步到位，取决于第一次猜的时候使用的随机数字，当然概率极小；宏观方向测试：

1. 
   
2. TIMES = 1000
   
3. best = 999
   
4. worst = 1
   
5. sum = 0
   
6. TIMES.times do |i|
   
7.   bac = BullsAndCows.new
   
8.   bacb = BullsAndCowsBreaker.new(bac)
   
9.   bacb.start_guessing
   
10.   sum += bac.step
    
11.   worst = bac.step if bac.step > worst
    
12.   best = bac.step if bac.step < best
    
13. end
    
14. p "best:#{best},worst:#{worst},average:#{sum.to_f/TIMES}"
    

复制代码

输出：
best:2,worst:8,average:5.478
平均需要猜 5.478 次 ……|||
这里用的方法很弱智，每次猜完根据结果排除不可能是答案的数字，然后在剩下的数字里随机选一个……|| 如果精通博弈论、决策论的强人应该有更好的方法在每次排除之后找最有可能是答案的数字……||