面试时遇到的一道笔试题

Question

一道面试题。
贝壳国法定货币是贝壳。贝壳特性如下：1：贝壳以颜色区分面值。2：较大面值一定是较小面值的整数倍。（例如，1,2,4,12）3：贝壳面值都是正整数
贝壳国旅游业发达，国外游客游历贝壳国需要携带贝壳币，等额RMB换取等额贝壳币。贝壳币可以从ATM机中换取。
贝壳国ATM机换取规则如下：同等金额下，使用尽可能少的币种组合。
例如：假设贝壳国有只有3中面额货币，1,2,4。某游客换取5RMB，可能的组合有：1）5个12）2个2+1个13）1个4+1个14）2个2+1个15)3个1+1个2
显然，1个4+1个1的组合是最少币种组合。
问题1：假设面值是（1,2,4,12），游客至少需要投入多少RMB才能推测出贝壳国所有货币的颜色代表的面额？问题2：有没有可能存在某种面值组合，游客一次投入RMB无法推测所有货币的面额？若存在，举出例子。问题3：设计程序分析，哪些组合是可以一次性推测出的，哪些不可以。

Answer 1

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