解题思路
我们把“兑换”过程视为一棵二叉树：每次把一张面额为 x>1 的钞票拆成 ⌊x/2⌋、x mod 2、⌊x/2⌋，其中当且仅当 x 为偶数时会产生一张 0。因此，问题等价于：整棵树里一共分裂了多少次“偶数面额”的节点。
设答案为 f(n)。直接递推可得
题目内容
小明手头有一个面额为 n 的钞票，他试图钱生钱，魔神用语言欺骗小明将钞票给了魔神。魔神承诺拿到钞票后，会将钞票拆分成面额分别为 n/2，n mod 2，n/2 的钞票（显然钞票的总金额没有发生变化，而且会出现面值为 0 的钞票），然后退回给小明。小明已经失去了理智，他会将所有面额大于 1 的钞票与魔神兑换，请问他最后会有几张面额为 0 的钞票。n mod 2 指 n 除以 2 的余数，例如 3 mod 2=1，4 mod 2=0 。 [x] 指最大且不大于 x 的整数
