首页 > 试题广场 >

魔法币

[编程题]魔法币

热度指数：22086 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币
魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。

输入描述:

输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9),表示小易需要的魔法币数量。

输出描述:

输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符'1'和'2'。

示例1

输入

输出

算法知识视频讲解

Python

MinGo215

s = int(input())
x = 0
a = []
while True:
    if s %2 != 0:
        s = (s - 1) / 2
        a.append('1')
    else:
        s = (s - 2) / 2
        a.append('2')
    if s == 0:
        break
b = a[::-1]
print(''.join(b))

编辑于 2018-09-10 20:14:58 回复(0)

Python

对方正在输入201803061117536

num = []
n = int(input(">>>")) while n != 0:  if n%2 == 0:
        n = (n - 2)/2  num.append("2")  else:
        n = (n - 1)/2  num.append('1')
list = num[::-1]
b = ''.join(list) print(b)

	



	



	不知道哪里错了，求解



	还有输入检查因为偷懒没写，只写了整体思路

编辑于 2018-03-28 20:43:29 回复(0)

Python

麻瓜工程师

# -*- coding: utf-8 -*-
import sys
class Node():
    def __init__(self,Data,left = None,right = None,path = None):
        self.Data = Data
        self.left = left
        self.right = right
        self.path = path
    def addchild(self,choice):
        if choice == 0:
            self.left = Node(Data = 2*self.Data + 1,path = self.path + '1')
        if choice == 1:
            self.right = Node(Data = 2*self.Data + 2,path = self.path + '2')

def search(target,tree):
    if tree.Data == target:
        path = tree.path
        return path
    elif tree.Data > target:
        return None
    else:
        if tree.Data*2 + 1 <= target:
            tree.addchild(0)
            path = search(target,tree.left)
            if path:
                return path
            elif tree.Data*2 +2 <= target:
                tree.addchild(1)
                path = search(target,tree.right)
                if path:
                    return path
            
n = int(sys.stdin.readline().strip())
root = Node(0,path='')
x = search(target = n,tree = root)
print(x)

使用DFS回溯的一种解法，内存受限。虽然不如奇数偶数关系明确，但是可以适应多种不同的问题，只要改变公式就可以

编辑于 2018-03-27 07:06:38 回复(0)

Python

小瘦猴

result = int(input())
a = []
while result != 0:
    if (result-1)%2 == 0:
        result = (result-1)/2
        a.append(1)
    else:
        result = (result-2)/2
        a.append(2)
b = [str(i) for i in a[::-1]]
print(''.join(b))

发表于 2018-03-26 19:22:06 回复(0)

Python

胖小夜曲灬

def judgeup(x): if x%2 == 0: return [2,(x-2)/2] else: return [1,(x-1)/2]
n = input( )
output = [] while n > 0:
    judge = judgeup(n)
    output.append(str(judge[0]))
    n = judge[1] print ''.join(output[::-1])

发表于 2018-03-25 10:12:59 回复(0)

Python

牛客8410186号





 Python
其实就是一个奇数和偶数的问题。
从输入的数n开始，判断n的奇偶，如果是奇数，
那么前一次肯定是machine 1，否则就是machine 2

递归计算n的前一次的数。。。直到前一个数为0


def magic_machine(x):
    Operations = [] 
    def _head_number(x): 
        if x%2 <1: #偶数 
            head_x = (x - 2)/2  
            Operations.append('2') 
        else:
            head_x = (x - 1)/2  
            Operations.append('1') 
    
        if head_x == 0: 
            return head_x 
        else: 
            return _head_number(head_x)
    _head_number(x)
    Operations.reverse() 
    return ''.join(Operations) 

def main_function(): 
    import sys 
    for line in sys.stdin:
        line = int(line)
        output = magic_machine(line) 
        print(output) 

if __name__ == '__main__':
    main_function()

编辑于 2018-04-27 17:21:41 回复(0)

Python

R4093

def f(n):
    s = []
    while n>=1:
        if n ==0:
            return
        if (n&0x1) == 1:
            n = (n-1)//2
            s +='1'
        else:
            n = n//2-1
            s +='2'
    s.reverse()
    s = ''.join(s)
    return s
num = int(input())
s= f(num)
print(s)

发表于 2017-09-15 19:25:53 回复(0)

Python

张胜虎

n=int(raw_input())
str=''
def magic(n):
    global str
    if n==0:
       print str
    elif n%2==0 and n!=0:
       str='2'+str
       magic((n-2)/2)    
    else:
       str='1'+str
       magic((n-1)/2)      
magic(n)

发表于 2017-09-12 19:40:17 回复(0)