面试时遇到的一道笔试题

Question

一道面试题。

贝壳国法定货币是贝壳。贝壳特性如下：
1：贝壳以颜色区分面值。
2：较大面值一定是较小面值的整数倍。（例如，1,2,4,12）
3：贝壳面值都是正整数

贝壳国旅游业发达，国外游客游历贝壳国需要携带贝壳币，等额RMB换取等额贝壳币。贝壳币可以从ATM机中换取。

贝壳国ATM机换取规则如下：
同等金额下，使用尽可能少的币种组合。

例如：假设贝壳国有只有3中面额货币，1,2,4。某游客换取5RMB，可能的组合有：
1）5个1
2）2个2 + 1个1
3）1个4 + 1个1
4）2个2 + 1个1
5) 3个1 + 1个2

显然，1个4 + 1个1的组合是最少币种组合。

问题1：假设面值是（1,2,4,12），游客至少需要投入多少RMB才能推测出贝壳国所有货币的颜色代表的面额？
问题2：有没有可能存在某种面值组合，游客一次投入RMB无法推测所有货币的面额？若存在，举出例子。
问题3：设计程序分析，哪些组合是可以一次性推测出的，哪些不可以。

Answer 1

上面的又错了，- -!，跟 @TinaRose 交流后发现自己之前确实弄错了。难怪一直觉得不太对劲，肯定是忽略了什么问题，现在终于知道了！

问题1：答案确实是12+4+2+1=19元，方法是分4次兑换，先换12元，再换4元，再换2元，最后换1元，这样就能确定所有贝壳币的颜色了。因为没说只能换1次，所以这样分开兑换所花的钱最少。

问题2：存在，例如1, 2, 4这种组合，无论一次兑换多少钱，都无法做到每种贝壳币数量各不相同。因为，首先1元的只能是1枚（超过1枚的部分必然会合并到2元上去），所以2元的必然要大于1枚，但这也是不可能的，因为这时超过的部分也会合并到4元上去。所以无论如何也无法区分出1元和2元

问题3：
分析：
有面值组合(a1, a2, ..., am)，则每次兑换所投入的RMB总额可以表示为：
a1*n1 + a2*n2 + a3*n3 + ... + am*nm
如果可以一次性区分出所有面值的颜色，那么n1, n2, n3, ..., nm必然各不相同，并且对于任何一种面值ak，ak*nk的值必然小于a[k+1]（否则就会合并到更大的面值上去）。

设a[k+1]/ak的比值为qk，则：

q1 = a2/a1
q2 = a3/a2
...
q[m-1] = am/a[m-1]

根据前面任意的k都必然有ak*nk<a[k+1]的结论，可以知道n1, n2 ... n[k-1]全部小于qk（这个结论还反映出一点，即对最后一项nm是没有要求的，实际上也确实如此，nm的值上不封顶，如果需要可以是任意大的值）。

根据以上结论，可以设计出以下算法：

1. 我们可以用一个n的备选集合来作为检查集合，集合初始化为(1, 2, 3, ..., m-1)。

2. 然后遍历比值q的集合(q1, q2, ..., q[m-1])，对每一个qk，执行以下检查：
   (1) 当qk >= k时，将n[qk-1]（注意不是n[q[k-1]]而是n[(qk)-1]）标记为“已占用”。如果n[qk-1]已经被占用，则进行与第2步相同的操作
   (2) 当qk < k时，从n1~n[k-1]之间找一个未被占用的，将其标记为“已占用”。如果找不到，则表示此面值组合无法一次性推断出来。如果遍历结束，未出现“找不到”的情况，则表示此面值组合可以一次性推断出来。

如果能一次性推断出来，那么遍历的过程也是找到答案的过程，按顺序将被占用的n的值写出来就是答案（但可能不是最优的答案）。

例如对于(1, 2, 4)这个面值组合，其比值集合为(2, 2)，先看q1，为2，我们将n1标记为“已占用的”，再看q2，为2，由于这时n1已被占用，因此此组合无法一次性推断出来。

再看看(1, 2, 8)这个，其比值集合为(2, 4)，q1会把n1占掉，q2会把n3占掉，两者没有冲突，所以这个组合是可以一次性推断出来的，而(1*1+2*3+8*?)就是其中的一种方法（?表示随便选一个不与前面有冲突的即可，例如2）

Answer 2

第一题：45元。解释如下：

我们知道，贝壳的面值只与颜色有关，所以我们可以根据兑换的不同颜色贝壳数量的不同来进行区分。
投入人民币45元，按照货币最少的原则，我们可以得到3×12+2×4+1×1=45；
即得到3枚币值为12的贝壳，2枚币值为4的贝壳，1枚币值为1的贝壳。
即得到的贝壳中，有三枚颜色一样的贝壳面值为12，两枚颜色一样的颜色贝壳面值是4，一枚的面值是1，
剩下的另外一种颜色货币面值就是2啦。
（反推的话：根据倍数原则，面值为1的贝壳不能超过2枚，因为超过2枚，按照货币最少原则，
就只能兑换一枚面值为2的贝壳，而不是两枚面值为1的，同理，面值为2的也不能超过2枚，
面值为4的不能超过3枚，面值12的无限制；总共有4种面值，我们可以只知道其中3种面值即可，
剩下的一种自然就知道了，也就是说兑换的贝壳中，三种颜色的贝壳必须符合个数1、2、3的原则，
根据前面的个数限制，所以面值12的3枚，面值4的2枚，面值1的1枚）

第二题： 1 2 4 8的面值组合。（因为 1、2、4都不能超过2枚，无法组合成个数1、2、3的组合，所以无法判断）
第三题：略。哈哈~~根据上面的规律自己写吧~

Answer 3

问题1: 从最小的数值开始枚举。没次枚举都要用排列组合的方法求出最小的货币组合。然后用广度搜索来把各个最小的货币组合求并集。直的得到能覆盖所有面额的集合为止,那么这是广度搜索的深度就是答案
问题2：集合数字规律符合 n+3>=2*(n-2+...+n)
问题3：第一种方法，判断集合的规律符不符合问题2中的规律。第二种方法,用方法一求出广度搜索的深度是否为大于1

Answer 4

每天能够获得300W的极品装备

Answer 5

其实第一题。4+2+1=7元 就可以了，每次投入1种面额，最后没见过的那种就是12元的拉~~~
ps这里就不脑洞大开的讨论用4元的贝壳币去换RMB的问题了。

第二题前面那几位回答的都很好了，就不再说啦 不过@universe_of_code 的例子是错的。1, 2, 4这种组合。投入10元就鉴定出来了。 2个4 + 1个2 + 0个1 。所以至少要出现多一个数才行的。 例如 1，2，4，8 ？

第三题，可以略么？随便聊聊思路吧。。
因为较大面值一定是较小面值的整数倍，所以就是看这个倍数之间的间隙了。例如1，2，4，8 这种组合，出现2个1就会合并到前面。所以至多1个，2、4都是，这样就没法区分了。所以需要出现的间隙至少是个等差数列。。。
不过还有个坑要考虑。。那就是0。某个面值的贝壳是可以在兑换的时候不出现的，这样可能性又增加了N种。。。
从数学角度写这个，会是很长的一个函数。。。从程序角度嘛、、最笨的办法吧。递归、、做个N*N的递归，一层层进去尝试能不能出现每个面值都不同的集合，能的话，输出到屏幕~~~跑上几百年，哈哈。。

才拙勿喷~