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

)]) >= 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 时间: 2010-9-24 10:05
本帖最后由 IamI 于 2010-9-24 13:09 编辑

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

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

复制代码

作者: 神思 时间: 2010-9-24 12:05
楼上想复杂了。其实4个数可拆开，逐个判断。次数不超过4*10…

作者: orochi2k 时间: 2010-9-24 12:08

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

作者: 小幽的马甲 时间: 2010-9-24 13:04
本帖最后由小幽的马甲于 2010-9-24 16:29 编辑

class Guess
def initialize(answer)
@ans = []
for i in 0..9999
@ans.push(i) if possible(i)
end
@s = answer
end
def possible(i)
q = []
q[0..9] = 0
a = arr(i)
for n in a
return false if q[n] == 1
q[n] = 1
end
end
def arr(num)
a = []
for i in 0..3
a[3 - i] = num % 10
num /= 10
end
return a
end
def check(a1, a2, a, b)
arr1 = arr(a1)
arr2 = arr(a2)
t = 0
for i in 0..3
t += 1 if arr1[i] == arr2[i]
end
return true if t != a
q = Array.new(10, 0)
t = 0
for i in arr1
q[i] = 1
end
for i in arr2
t += q[i]
end
return t != a + b
end
def ask(num,num2 = @s)
arr1 = arr(num2)
arr2 = arr(num)
a = 0
for i in 0..3
a += 1 if arr1[i] == arr2[i]
end
q = Array.new(10, 0)
b = -a
for i in arr1
q[i] = 1
end
for i in arr2
b += q[i]
end
return [a,b]
end
def getnum
ti = rand(@ans.size)
t = @ans.size
for o in 1..10
i1 = rand(@ans.size)
i = @ans[i1]
aa = 0
r1 = [1000/@ans.size].min
for r in 1..r1
j = @ans[rand(@ans.size)]
a, b = *ask(j,i)
s = @ans.size
for k in @ans
s -= 1 if check(j, k, a, b)
end
aa = s if s > aa
end
if aa <= t and aa > 0
t = aa
ti = i1
end
end
return ti
end
def calc
time = 0
while @ans.size > 0
time += 1
i1 = ((time == 1) ? 123 : getnum)
i = @ans[i1]
a, b = *ask(i)
str = i.to_s
str = '0' + str if i < 1000
print "第#{time}次\n#{str}\n#{a}A#{b}B"
if a == 4
print "答案是#{str}"
return true
end
for num in [email protected]
@ans[num] = nil if check(i,@ans[num],a,b)
end
@ans[i1] = nil
@ans.compact!
end
p "Impossible!"
return false
end
end
guess = Guess.new(1234)
guess.calc

复制代码

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

作者: david50407 时间: 2010-9-25 10:04
啊~原来是找出答案阿

建表?

$question = "5968"
$table = array.new
for i in 0..9
for j in 0..9
for k in 0..9
for l in 0..9
$table.push("#{i}#{j}#{k}#{l}") # 建表
end
end
end
end
def check(c)
a = b = 0
if (p = $question.match("["+c+"]")) != nil # 测试是否有A或B的情况
for i in p
if $question.index(i) == c.index(i)
a += 1
else
b += 1
end
end
end
return a,b
end
def guess(g)
a,b = check(g) # 检查?A?B
$table.collect! {|t| check(t) == a,b ? t : nil}
$table = $table.compact
end
guess_times = 4
guess("1234")
guess("3456")
guess("5678")
guess("7890")
for i in $table
guess_times+=1
if guess(i) == 4,0 # 4A0B
p "Ans: #{i}\nGuess #{guess_times} times"
end
end

复制代码

应该就这样 (汗

作者: 紫苏 时间: 2010-9-26 04:24
本帖最后由紫苏于 2010-9-26 04:42 编辑

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

module BullsAndCowsServices
# 生成无重复数位的随机四位数
def generate_digits
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
arr.slice!(rand(9))*1000 +
arr.slice!(rand(9))*100 +
arr.slice!(rand(8))*10 +
arr.slice!(rand(7))
end
# 把四位整数转换为数位数组
def digits2arr(digits)
return [digits%10, digits/10%10, digits/100%10, digits/1000]
end
# 返回猜测的结果
def judge(ans, num)
a = b = 0
ans_digs = digits2arr(ans)
my_digs = digits2arr(num)
for i in 0..3
if my_digs[i] == ans_digs[i]
a += 1
elsif ans_digs.include?(my_digs[i])
b += 1
end
end
return a*10+b
end
end
class BullsAndCows
include BullsAndCowsServices
attr_reader :step
# 初始化
def initialize
@num = generate_digits
@step = 0
end
# 猜一个数字，返回结果
def guess(num)
result = judge(@num, num)
@step += 1
p "guessing #{num}, (#{result/10}A#{result%10}B), step ##@step"
return result
end
end
class BullsAndCowsBreaker
include BullsAndCowsServices
# 初始化
def initialize(bac)
@bac = bac
@possible_guesses = []
for i in 1023..9876
ans_digs = digits2arr(i)
if ans_digs.uniq.length == ans_digs.length
@possible_guesses << i
end
end
end
# 排除不可能的数字
def eliminate(guess, result)
@possible_guesses.delete_if do |possible_guess|
indirect_result = judge(guess, possible_guess)
indirect_result/10 != result/10 || indirect_result%10 != result%10
end
end
# 开始破译
def start_guessing(best_guess = 1023)
loop do
result = @bac.guess(best_guess)
eliminate(best_guess, result)
break if result == 40
best_guess = @possible_guesses[rand(@possible_guess)]
end
end
end

复制代码

实际测试时可以：

bac = BullsAndCows.new
bacb = BullsAndCowsBreaker.new(bac)
bacb.start_guessing

复制代码

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

TIMES = 1000
best = 999
worst = 1
sum = 0
TIMES.times do |i|
bac = BullsAndCows.new
bacb = BullsAndCowsBreaker.new(bac)
bacb.start_guessing
sum += bac.step
worst = bac.step if bac.step > worst
best = bac.step if bac.step < best
end
p "best:#{best},worst:#{worst},average:#{sum.to_f/TIMES}"

复制代码

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

作者: 精灵使者 时间: 2010-9-26 08:27
本帖最后由精灵使者于 2010-9-26 09:05 编辑

我使用替换法来猜……我简要的写个算法吧。
首先，直接输入1234和5678（这前两个为固定式），然后判断他们的情况。
于是出现了两种情况。
如果里面的A,B里面加在一起等于4
那么可以肯定9,0被排除在数字之外。
如果A,B加在一起小于四的话就麻烦了。说明了，9和0之间会有一个数字是正确的。
于是，我们就尽量靠近两个极端
一个是0A0B（这四个数字都不是答案数字，可以排除很多情况）（可以更换其中的一些数字来观察情况，从而判断是不是答案数字）
一个是A+B = 4（这样的话全部数字都是答案数字，排除其余数字的情况）
然后再使用确认不是答案数字的字符来计算其他的数字是不是答案数字。
判断的差不多了的情况下，然后再计算以前的结果判断四个正确数字的位置。
基本上能够在8次以内猜中。
为了能减少猜的次数，有效的数字可以在各位出现，以判断有效的数字的正确位置。
所以，可以化整为零，每一个数字都做一个数组
分别为（数字，有效度，位置）
数字：0-9
有效度：（0-2）（0：未知，1：无效，2：有效）
位置（0-4）只有有效度有效的时候才会判断位置。
那么，最后的结果是
A 1 1
B 1 2
C 1 3
D 1 4
于是正确答案是ABCD。
每次答案的结果反馈进去，会自动生成下一个新的数字，来进行猜测。
整个思路就是：先猜测能完成的数字的大致范围（1234,5678）
然后再调换数字同时调整排序，根据结果来计算出正确的数字集（这个时侯可以用2-3次，而且可以用已鉴定完成的数字去鉴定未完成的数字）
找到数字的大致范围以后，计算它的位置（通过前几次的统计结果，确认正确的数字位置，其中如果有正确的数字被判断B的话，那么在此位上就不能是这个数字。提出的数字不能和以前的计算结果相抵触。）这样，随着提示越来越多，你就应该能算出正确的数字了。

作者: goahead 时间: 2010-9-28 17:53
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Project1 (https://rpg.blue/)