面试时遇到的一道笔试题

pingfengafei
  • 560

一道面试题。

贝壳国法定货币是贝壳。贝壳特性如下:
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:设计程序分析,哪些组合是可以一次性推测出的,哪些不可以。

回复
阅读 2.8k
5 个回答

上面的又错了,- -!,跟 @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必然各不相同,并且对于任何一种面值akak*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

第一题: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的组合,所以无法判断)
第三题:略。哈哈~~根据上面的规律自己写吧~

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

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

其实第一题。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的递归,一层层进去尝试能不能出现每个面值都不同的集合,能的话,输出到屏幕~~~跑上几百年,哈哈。。

才拙勿喷~

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏