代码之家 › 专栏 › 技术社区 › Aemilius

公牛和奶牛-破解密码-算法

pseudocode algorithm

Aemilius · 技术社区 · 7 年前

公牛和奶牛的比赛由两名选手进行。其中一个玩家想到了一个4位数的密码(0到9之间的数字),然后,另一个玩家提出了一个建议。第一个玩家用正确放置的数字(公牛)和正确但位置错误的数字(奶牛)来回应。
我想写一个程序,猜测密码,然后读取公牛和奶牛的数量,再进行猜测。我希望这一过程相对较快地结束。

1. Create a 4-dimensional boolean array 10 x 10 x 10 x 10
2. Set all elements of this array to true, bulls = 0, cows = 0
3. While bulls != 4
   3.1. Find the first element of the array which is set to true
   3.2. Make a guess with this number
   3.3. Read the number of bulls and cows
   3.4. If bulls = 0 and cows = 0
        set all codes containing any of the digits from the last code to false

这就是我用这个算法得到的结果。我不知道如何进行。对我来说,最明显的方法是手动分析所有可能的公牛和奶牛数量,但这只会占用太长的时间和太多的空间。你能给我一个提示吗,如果有一个通用的方法来满足所有可能的情况?

1 回复 | 直到 7 年前

CÅur N0mi 4 年前

这个游戏让我想起了这个游戏 Jotto ,两个玩家挑选单词,然后试着猜对方的单词,只被告知他们猜出的单词中有多少个字母是在实际单词中(一个很大的区别是在Jotto中只能使用实际单词)。

我的第一步是识别4头牛/公牛。这样我们就有了所有的4位数,然后我们就可以担心订单是否正确了。

要识别4头牛/公牛,我们首先要猜测4个随机数。如果我们运气好,奶牛+公牛=0,那么我们可以消除所有4个数字。否则,我们将一次更改一个数字的猜测。假设我们用a,b,c,d猜,然后用a,b,c,e猜。

如果奶牛+公牛在下一次猜测后下降1,我们可以得出结论,我们删除的数字(d)是一头奶牛或公牛,而新的数字(e)不是一头奶牛或公牛。

如果奶牛+公牛没有变化,那么d和e都是奶牛/公牛,或者d和e都不是奶牛/公牛。我们可以尝试另一个数字(f),直到看到变化,并从中得出结论。

如果奶牛+公牛增加1,那么我们可以得出结论,e是奶牛/公牛,d既不是奶牛也不是公牛。

我们将继续这样做,直到我们拥有全部4个数字。然后,我们可以尝试不同的安排,一次一个变化,以确定我们是越来越近还是越来越远。

推荐文章

JP_99 · 如果不需要类型转换,编程语言的类型规则是什么?

6 年前

Papi Harpy · 如何在python中声明2d数组?

6 年前

Stefan Octavian · 将半透明转换为纯色的算法

6 年前

Aemilius · 公牛和奶牛-破解密码-算法

7 年前

Imran Saleem · SQL Server:存储最近5个日期

7 年前

user405381 · 将伪代码翻译成python(割线方法)

7 年前

user8386896 · 伪代码-这有什么错

7 年前

Eonm · 在不使用数组或任何使用数组或任何其他集合的函数的情况下,查找用户给定的n个值的中值

7 年前

briyan · 查找最强人算法

7 年前

Alex Chan · 按第一个字母对字符串的链接列表排序

7 年前