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

问题描述 投票:1回答:3

您将如何解决这个问题?

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

algorithm search
3个回答
3
投票

如果满足以下条件,它将收敛为一个:

1]在三个(x,y,z)中,只有两个是偶数或奇数。即,所有三个字符不能都是偶数或奇数,一个必须不同。

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

编辑:正如@onelyner最初指出的那样,尽管遵循了第一个规则,但(3,0,0)仍然无效。概括,

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

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

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

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


1
投票

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

[我们也知道,在每个步骤中,所有三个部分都翻转奇偶校验,因为两个递减,一个递增。因此,要么我们在(奇数,奇数,奇数)和(偶数,偶数,偶数)之间移动,要么在(奇数,奇数,偶数)和(偶数,偶数,奇数)之间移动。因为我们知道最终状态是(偶数,偶数,奇数),所以我们知道状态变化必须在(奇数,奇数,偶数)和(偶数,偶数,奇数)之间。

但是这足以知道任何起始值(显而易见的{x, 0, 0}, x > 1除外)都可以工作吗?


0
投票

向后工作...

从{0,0,1}开始,对于k> = 0的任意k,通过反复选择1递减,可以得出{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个。

© www.soinside.com 2019 - 2024. All rights reserved.