问题：有两台魔法机器可以通过投入X个魔法币产生更多的魔法币。X可以为零，因为首次投魔法币的时候X必然为零。
机器1：投入x个，生产2*x+1个
机器2：投入x个，生产2*x+2个
请设计一个方案，使得最后刚好拥有N个魔法币。
输入：输入包括一行，包括一个正数N(1<=N<=10^9)
输出:输出一个字符串，每个字符表示选取的机器编号。其中1表示机器1，2表示机器2。
示例:
输入:10
输出:122
分析过程：机器1只会生奇数个魔法币，机器2生产偶数个魔法币。假设当前魔法币有i个，投入j个：如果投入机器1，则魔法币数变为i+j+1；如果投入机器2，则变为i+j+2个。显然，存在关系j<=i。
反过来思考，当前魔法币个数为n的时候，则前一次魔法币个数m=n-step。为了尽可能地减少兑换次数，显然step越大越好，也就是优先选机器2，即step=j+2。
基于上述分析，计算方法如下:
步骤1 如果n是偶数，由于i+j=n-2，则j最大为(n-2)/2，为了让步长step最大，则可令j等于此最大值
步骤2. 如果n是奇数，则相当于在拥有n-1魔法币的时候，投入1个币到机器1的结果。此时再倒推计算n-1是怎么选取的。进入步骤1
步骤3:当计算出来的j等于零，则逆推到了第一次投零个魔法币的时候。
def getChoice(inputNum):
choice='',
if inputNum%2 != 0:
inputNum-=1
if inputNum == 0:
return 0, choice
j=(inputNum-2)/2
if j == 0:
return 0, '2'+choice
i=inputNum-2-j
return i, '2'+choice
n=int(input())
curChoice=''
while(n>0):
网友评论