不可能的搜索算法面试问题



你会如何解决这个问题?

你从一个盒子开始,里面有数量 x 的红色弹珠,y 的绿色弹珠 弹珠和Z蓝色弹珠,以及无限供应的红色,绿色 和盒子外面的蓝色弹珠。一招包括选择两步 不同的颜色,从盒子里取出两个弹珠(每个一个 您选择的两种颜色(,然后添加第三种颜色的大理石 从您的供应到盒子。例如,如果您选择红色 和绿色,然后你取出一个红色和一个绿色的大理石,然后放回去 一个蓝色的。对于什么起始条件(表示为 x,y,z(您可以通过执行零来获得盒子中的一颗弹珠吗 还是更多动作?

如果出现以下情况,它将收敛为一个:

1(在三个(x,y,z(中,只有两个是偶数或奇数。 也就是说,这三个都不能是偶数或奇数,一个必须是不同的。

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

编辑:正如@onelyner最初指出的那样,尽管遵循第一条规则,(3,0,0(将无法正常工作。推广

2(如果第三个不等于1,则(x,y,z(中的任何两个最初都不能为零。

即它不能看起来像 (0, 0, n(,其中 n 不等于 1。

这里需要注意的是,我们可以从 (3, 0, 0( 到达 (2, 1, 1(,它应该收敛为 1,因为它遵循两个规则。如果做得好,它肯定会收敛到一个

(2, 1, 1( -> (1, 2, 0( -> (0, 1, 1(-> (1, 0, 0(

为了解释 TotallyNoob 揭示的奇偶校验问题,我们可以将状态视为将总和分为三个部分。在每个阶段,总和减少 1 (-2 + 1(,这意味着总和的奇偶性翻转。对于奇数,有两种方法将其表示为三的总和(奇数

+ 奇数 + 奇数(或(偶数 + 偶数 + 奇数(,对于偶数,也有两种方式(奇数 + 奇数 + 偶数(或(偶数 + 偶数 + 偶数(。我们还知道,在每一步中,所有三个部分都翻转奇偶校验,因为两个递减,一个递增。因此,我们要么在(奇数,奇数,奇数(和(偶数,偶数,偶数(之间移动,要么在(奇数,奇数,偶数(和(偶数,偶数,奇数(之间移动。由于我们知道最终状态是

(偶数,偶数,奇数(,我们知道状态变化必须在(奇数,奇数,偶数(和(偶数,偶数,奇数(之间。但这足以知道任何起始值(除了明显的{x, 0, 0}, x > 1(都会起作用吗?

向后工作...

从 {0,0,1} 开始,我们可以通过重复选取 1 递减来得到任何 k>= 0 的 {0,1,k}。

从 {0,1,k}, k>=1,我们可以通过在 k 和 1 之间交替递减来得到 {2x,1,k(。

从 {2x,1,k}, k>=1,我们可以通过在 2x 和 k 之间交替递减来得到 {2x,2y+1,k(。

因此,任何至少有一个偶数、至少一个奇数和至少比零 2 的三重奏都可以从反向的单个大理石到达。

最新更新