首页 > 试题广场 >

魔法币

[编程题]魔法币

热度指数：318 时间限制：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

输入

输出

算法知识视频讲解

萍水依依

n=int(input())
list=[]
while n>1:
    if n%2==0:
        list.append(2)
        n=(n-2)/2
    else:
        list.append(1)
        n=(n-1)/2
if n==1:
    list.append(1)
list1=map(str,list[::-1])
list2=''.join(list1)
print(list2)

发表于 2019-09-01 09:49:26 回复(0)

Java

白不老

public class MagicCoin {

   public static String coin(int n) {
       if (n == 0) {
           return "";
       }
       if (n % 2 == 0) {
           n = (n - 2) / 2;
           return coin(n) + '2';// 递归
       } else {
           n = (n - 1) / 2;
           return coin(n) + '1';
       }
   }

   public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       in.close();
       System.out.print(coin(n));
   }
}

发表于 2018-07-06 00:03:41 回复(0)

牛客340721090号

//从前面往后面算非常困难，此题从后面往前面算会简单很多。
//题目等价于：初始有n个金币，求上一次使用的魔法机，更新n，然后一直循环下去求上一次x直到n=1或者n=2为止。

#include <iostream>
#include <vector>
using namespace std;

int main(){
    uint n;
    cin>>n;
    vector<string> str;

    bool endFlag = false;
    while(!endFlag){
        if(n == 1 || n == 2){
            str.push_back(to_string(n));
            endFlag = true;
            break;
        }
        if(n%2 == 1){
            str.push_back("1");
            n = (n-1)/2;
        }else{
            str.push_back("2");
            n = (n-2)/2;
        }
    }
    for(int i = str.size()-1;i>=0;i--){
        cout<<str.at(i);
    }
}

发表于 2022-05-16 17:47:58 回复(0)

C/C++

易也

//机器1产生的魔法币：1，3，5，7，9，11，13，15.。。。。。。。奇数
//机器2产生的魔法币：2，4，6，8，10，12，14，16.。。。。。。偶数
//对于输入的n，先判断奇偶，然后依次向前推记录路径，奇数向前推是（n-1）/2;偶数向前推是(n-2)/2,最后推到n变成1或者2，

	
	
		
		
			#include <stdio.h>
		

		
			intmain() {
		

		
			longlongn;
		

		
			inta[10000];
		

		
			scanf("%ld",&n);
		

		
			intcount = 0; //记录机器序列
		

		
			while(n){
		

		
			if(n == 1)
		

		
			{
		

		
			a[count++] = 1;
		

		
			break;
		

		
			}
		

		
			
		

		
			if(n == 2)
		

		
			{
		

		
			a[count++] = 2;
		

		
			break;
		

		
			}
		

		
			if(n%2 == 0){ //如果是偶数
		

		
			a[count++] = 2;
		

		
			n = (n-2)/2;
		

		
			}
		

		
			if(n%2 == 1){ //如果是奇数
		

		
			a[count++] = 1;
		

		
			n = (n-1)/2;
		

		
			}
		

		
			}
		

		
			for(inti = count-1;i>=0;i--)
		

		
			printf("%d",a[i]);
		

		
			return0;
		

		
			}