不可能搜索算法面试问题

Question

你将如何解决这个问题？

你从一个盒子开始，盒子里有x个红色大理石，y个绿色大理石和z个蓝色大理石，盒子外还有无限量的红色、绿色和蓝色大理石。一个步骤是选择两种不同的颜色，从盒子中取出两个大理石（两种颜色各一个），然后从你的供应中向盒子中添加第三种颜色的大理石。例如，如果你选择红色和绿色，那么你移除一个红色和一个绿色的大理石，然后放回一个蓝色的。对于什么样的起始条件（表示为x、y、z上的约束），通过执行零次或多次移动，可以在框中获得一个弹珠？

Answer 1

反向工作。。。

从{0,0,1}我们可以得到任意k的{0,1,k}

从{0,1，k}，k

从{2x，1，k}，k

因此，任何具有至少一个偶数、至少一个奇数和至少2高于零的三重奏都可以从反向的单个大理石中获得。

Answer 2

为了解释奇偶性问题TotalyNoob揭示的，我们可以把状态看作是一个总和分成三部分的划分。在每个阶段，总和减少1（-21），这意味着总和的奇偶性翻转。对于奇数，有两种方式可以表示为三（奇奇奇）或（偶偶奇）之和，对于偶数，也有两种方式（奇奇偶）或（偶偶偶偶）。

我们还知道，在每一步，所有三个部分都会翻转奇偶校验，因为两个部分递减，一个部分递增。所以要么我们在（奇数，奇数，奇数）和（偶数，偶数，偶数）之间移动，要么我们在（奇数，奇数，偶数）和（偶数，偶数，奇数）之间移动。因为我们知道最终状态是（偶数，偶数，奇数），所以我们知道状态变化必须在（奇数，奇数，偶数）和（偶数，偶数，奇数）之间。

但是，这是否足以知道任何起始值（除了明显的{x，0，0}，x）

Answer 3

如果：

在三个（x，y，z）中，只有两个是偶数或奇数。也就是说，三个都不可能是偶数或奇数，一个必须是不同的。

它们中的任何一个都可以是偶数或奇数——颜色没有限制。

编辑：正如@onelyner最初指出的，尽管遵循了第一条规则，（3,0,0）还是不起作用。泛化，

2）任何两个（x， y， z）不能是零，如果第三个不等于一。

i、 e.它不能看起来像（0，0，n），其中n不等于1。

这里需要注意的是，我们可以从（2，1，1）中得到（3，0，0），它应该收敛到一，因为它遵循这两个规则。如果处理得当，它肯定会收敛到一个

(2, 1, 1) -