-6

我想知道如何创建一个值从 1111 开始一直到 8888 的数组。我问这个是因为我需要生成一个 4 位数字的列表,每个数字的范围为 1-8。我想把它做成一个循环形式。此外,我在下面的程序中迷失了我的函数 trim、methicalEliminateguessAndEliminateguessThreeThenEliminate。以下是方向:

该作业侧重于在程序中使用数组,包括将数组用作函数的参数。

问题描述 在 Mastermind 游戏中,玩家只获得有限次数的猜测来尝试识别隐藏的组合(例如 12 次猜测)。通常这是玩游戏的唯一限制。但是有些玩家可能会互相竞争,看谁能在更少的尝试中猜出对方的组合。在这种情况下,问题不仅在于提出一种可以在指定范围内找到答案的策略,还在于找到一种可能需要最少猜测次数的策略。

这就是计算机的用武之地——人们可以编写一个程序来尝试不同的猜测策略,看看它们是如何工作的。由于计算机可以比人更快地进行分析和计算,它可以使用我们选择的任何策略假装代表我们玩 Mastermind,并告诉我们这样做需要多长时间。

整体解决方案

当然,教计算机按照与人相同的思路进行推理是极其困难的。例如,如果我们猜出一个组合 1111 并得到一个黑色钉子,我们会在心里记下答案中正好有一个 1,然后在记住这一事实的情况下继续进行其他猜测。如果我们接下来猜测 1222 并得到一个白色钉子,我们会知道没有 2,并且单个 1 不在第一个位置。但是如何在一系列猜测之后跟踪这些信息将是相当困难的。

幸运的是,对于带有数组的计算机模拟,我们可以以不同的方式记录所有已知的事实。我们只是维护一个可能存在的所有可能答案的列表,然后从列表中删除不再是解决方案的数字。如果我们的第一个猜测告诉我们恰好有一个 1 数字,我们将删除所有不具有该特征的数字。当我们发现没有 2 时,我们消除所有包含 2 的值。最终,剩下的唯一数字将是正确的答案。

一些简单的策略

  1. 这是许多玩家使用的策略,类似于上面描述的策略。只是有条不紊地以一种简单的方式解决了这些可能性。1111 的第一个猜测将回答解决方案中有多少个 1;下一个猜测将回答解决方案中有多少个 2,并说出任何 1 可能在哪里,等等。使用我们的列表方法,其中包含从 1111、1112、1113、1114 等开始的顺序的大量可能性,我们的下一个猜测将始终是列表中的第一个。

  2. 下一个策略是为那些喜欢更多刺激的人准备的。这些猜测似乎或多或少是随机的,希望能发现更多信息。模拟这种方法非常简单——如果你有一个数字列表,只需随机选择一个。如果您在一个数组中有 837 种可能性可供选择,只需在 0 到 836 范围内随机选择一个下标。

  3. 第三种策略考虑了给定猜测给出相似结果的答案在某种意义上彼此相似的可能性。因此,为了获得更多信息,它仍然会随机选择一些数字,而不考虑它们是如何评估的,然后才开始考虑结果。为了实现这一点,让我们选择任意三个可能的答案并猜测它们,暂时忽略它们为我们赢得了多少黑钉和白钉。只有在做出这些猜测之后,我们才会修剪可能性列表,然后按照上面的第二个策略进行。

示例界面 这些是当前实现的示例结果:请输入要尝试的组合,或 0 表示随机值:0 猜测 2475

Guessing 1111...
Guessing 2222...
Guessing 2333...
Guessing 2444...
Guessing 2455...
Guessing 2456...
Guessing 2475...

有条不紊地消除所需的 7 次尝试。

Guessing 6452...
Guessing 2416...
Guessing 2485...
Guessing 2445...
Guessing 2435...
Guessing 2425...
Guessing 2475...

猜测和消除需要 7 次尝试。

Guessing 7872...
Guessing 6472...
Guessing 1784...
Guessing 2475...

猜三然后消除所需的 4 次尝试。

玩另一个游戏?(y/n) y 请输入要尝试的组合,或 0 表示随机值:0 猜测 4474

Guessing 1111...
Guessing 2222...
Guessing 3333...
Guessing 4444...
Guessing 4445...
Guessing 4464...
Guessing 4474...

有条不紊地消除所需的 7 次尝试。

Guessing 3585...
Guessing 7162...
Guessing 4474...

猜测和消除需要 3 次尝试。

Guessing 8587...
Guessing 1342...
Guessing 1555...
Guessing 7464...
Guessing 6764...
Guessing 4468...
Guessing 4474...

猜三然后消除所需的 7 次尝试。注意:这个程序允许每个数字上升到 8 而不是 6。即使有 4096 个可能的答案,它仍然可以很快找到它们。

程序规范 指定的程序必须实现以下所有功能。根据需要允许额外的 - 以下这些是必需的。未来的作业将不会详细说明以下功能——而是要求学生提前设计自己的功能描述以编写程序。main:简单地控制程序的整体行为。将选择一个数字作为目标组合,然后每个策略将尝试找到它。调用:generateAnswer,(要比较所有三个必须有相同的答案)methodicalEliminate、guessAndEliminate、guessThreeThenEliminate

generateAnswer: 要么让用户在键盘上选择神秘组合,要么让计算机生成一个随机组合。(对于竞技游戏,知道哪种组合最难猜可能会很有趣!) 参数:无!返回: 4 位组合,每个数字在 1 到 8 范围内

generateSearchSpace:用 1 到 8 范围内的四位值的所有可能组合填充一个数组。 参数:guesses(修改后的 int 数组)猜测列表长度(输出 int)列表中的值数量前提条件:数组必须是分配给不少于 4096 个元素。

trim:分析对特定猜测的响应,然后从可能性列表中消除不再可能的答案的任何值。在每种情况下,它都假定列表中的一个值是一个答案,并相应地评估猜测。如果黑白钉的数量与指定的数量不同,则不能是正确答案。 参数: guesses(修改后的 int 数组) 猜测列表长度(修改后的 int) 列表中的值数许多猜猜 的白钉子赚了前提条件: 黑色和白色实际上确实包含将猜测与实际答案进行比较的结果 后置条件: 长度已减少(我们学到了一些东西)可行的答案占据了猜测数组中的第一个“长度”位置(因此列表更短)调用:评估

methodicalEliminate:从所有可能的候选答案列表开始,不断猜测列表中的第一个元素,并相应地修剪答案,直到找到答案 参数:答案(输入 int)实际答案(获得黑白钉所必需的) 返回:找到答案所需的猜测次数调用:generateSearchSpace、evaluate、trim

gusssAndEliminate:从所有可能的候选答案列表开始,不断猜测列表中的随机元素,并相应地修剪答案,直到找到答案 参数:答案(输入 int)实际答案返回:找到答案所需的猜测次数调用:generateSearchSpace、评估、修剪

gusssThreeThenEliminate:从所有可能的候选答案列表开始,首先随机猜测三个答案,然后修剪可能的列表,然后缩小答案,一次随机猜测一个参数:答案(输入 int)实际答案返回:数量找到答案所需的猜测调用:generateSearchSpace、evaluate、trim

注意:最后这些函数使用正确答案来评估每个猜测,然后使用黑色/白色钉子进行猜测策略。这些策略中的任何一个都可能会偷看答案以决定下一步该做什么!

另外:以下功能也应该出现在上一个作业的这个程序中,尽管它们本身不属于本次作业的成绩。

评估:通过将组合与答案进行比较来评估组合 正确性由黑色钉子(正确位置的正确数字)和白色钉子(错误位置的正确数字)表示 参数:答案(输入 int)正确的组合猜测(输入 int)当前猜测 black (output int) 黑色钉子的数量 white (output int) 白色钉子的数量 前置条件:答案和猜测都是 4 位数字,没有零位 后置条件:黑色和白色都 > 0 并且它们的总和 <= 4 调用:nthDigit, clearNthDigit

nthDigit:标识组合的第 n 位数字是从左到右还是从右到左计数未指定参数:组合(输入 int)组合以检查位置(输入 int)要检查的数字(返回)(输出 int)实际位数的值前置条件:组合有合适的位数,且0<位置<=位数后置条件:0<=返回位数<=9(个位数)

clearNthDigit:将组合的第n个数字设为0,因此不再匹配数字必须以与上述nthDigit相同的方式计算。参数:combination (in/out int) 修改位置的组合(input int) 将哪个数字设为0 前置条件:与上面nthDigit 相同 后置条件:对应的数字设为0 调用:nthDigit(可选,取决于关于实施)

感谢您阅读这么长的问题,希望您能在数组方面帮助我!

4

1 回答 1

0

仅仅因为您的猜测具有 1111 到 8888 的形式,并不意味着它们是数字。

如果对它们进行算术计算有意义,它们就是数字。对猜测定义算术计算是没有意义的:将猜测 4571 添加到猜测 6214 意味着什么?

如果您的猜测不是数字,请不要使用为数字保留的表示。但是,您可以使用由四个整数组成的数组:

int guesses[4][4096];
int g = 0;
for (int i = 1; i <= 8; ++i)
  for (int j = 1; j <= 8; ++j)
    for (int k = 1; k <= 8; ++k)
      for (int m = 1; m <= 8; ++m)
        guesses[g++] = {i, j, k, m};

我非常确信将所有可能的猜测都放入这样的数组guesses中也不是一个好主意。该代码主要演示了如何生成猜测。

通过其他功能,考虑应该对剩余的猜测执行哪些高级操作(例如“消除所有在第三位置具有一定数量的猜测”等)。这应该让您了解替换guesses数组的更好数据结构。

于 2013-10-24T21:35:53.233 回答