时间戳

首页 > 解决方案 > 谷歌 Foobar 游戏

algorithm - 谷歌 Foobar 游戏

问题描述

所以这可能是最愚蠢的问题，但英语不是我的第一语言，我似乎无法理解这个问题的上下文。

嘿，我已经这样做了！

指挥官 Lambda 使用自动算法将奴才随机分配给任务，以使她的奴才保持警觉。但是你已经注意到算法中的一个缺陷——它最终会循环回到自己身上，因此它不会在迭代时分配新的奴才，而是卡在一个值循环中，这样相同的奴才最终会重复执行相同的任务并且再次。您认为向指挥官 Lambda 证明这一点将有助于您为下一次晋升提供依据。

您已经计算出该算法具有以下过程：

  1. 从一个随机的 minion ID n 开始，它是一个以 b 为底的长度为 k 的非负整数
  2. 将 x 和 y 定义为长度为 k 的整数。x 以降序排列 n 的数字，y 以升序排列 n 的数字
  3. 定义 z = x - y。如有必要，将前导零添加到 z 以保持长度 k
  4. 赋值n = z得到下一个minion ID，返回步骤2

例如，给定 minion ID n = 1211，k = 4，b = 10，则 x = 2111，y = 1112 和 z = 2111 - 1112 = 0999。那么下一个 minion ID 将是 n = 0999，算法再次迭代: x = 9990, y = 0999 和 z = 9990 - 0999 = 8991，以此类推。

根据 n、k（从 n 导出）和 b 的值，算法在某个点上会达到一个循环，例如通过达到一个常数值。例如，从 n = 210022, k = 6, b = 3 开始，算法将到达值的循环 [210111, 122221, 102212]，无论它继续迭代多少次，它都将停留在这个循环中。从 n = 1211 开始，例程将到达整数 6174，并且由于 7641 - 1467 是 6174，因此无论迭代多少次，它都将保持该值。

给定一个 minion ID 作为字符串 n，表示以 b 为底的长度为 k 的非负整数，其中 2 <= k <= 9 和 2 <= b <= 10，编写一个函数 solution(n, b)，它返回上述算法的结束循环，从 n 开始。例如，在上面的示例中，solution(210022, 3) 将返回 3，因为在以 3 为底的情况下，对 102212 的迭代将返回 210111。如果算法达到常数，例如 0，则长度为 1。

我的问题是：编写一个函数解决方案（n，b）是什么意思，它返回上面从n开始的算法的结束循环的长度？字面上不知道。任何帮助，将不胜感激。

标签： algorithm

解决方案

如果您遵循算法“处理”说明，步骤 1 到 4，n每次都会被分配一个新值（一个棘手的部分可能是考虑数字基数）。现在想象一下，我们记录了到达当前所采取的步骤，并为我们得到n的每个步骤记录下来。n根据描述，我们最终会遇到一个n我们已经见过的。任务是告诉它从我们已经看到的地方走了多少步n，直到再次看到它——这是一个“周期长度”。

推荐阅读