首页 > 试题广场 >

魔法币

[编程题]魔法币

热度指数：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

输入

输出

算法知识视频讲解

buaaqlyj

魔法机器1只能产生奇数，魔法机器2只能产生偶数。

从n不断按奇偶倒推回0就可以了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int coinCount = in.nextInt();
            StringBuilder sb = new StringBuilder();
            while (coinCount > 0) {
                if (coinCount % 2 == 0) {
                    //偶数
                    coinCount = (coinCount - 2) / 2;
                    sb.append("2");
                } else {
                    //奇数
                    coinCount = (coinCount - 1) / 2;
                    sb.append("1");
                }
            }
            System.out.println(sb.reverse().toString());
        }
    }
}

编辑于 2017-09-09 22:56:30 回复(22)

C/C++

EugeneZheng

水题，求 x 经过若干次 f(x) = 2x + c 的变换恰好到 n ，显然次数不超过 log(n) + 1 = 32 次；

而 c = 1 || 2 使得每次 n' 具有奇偶特征，直接递归出来。

#include <stdio.h>

int n;

void read() {
    scanf("%d", &n);
}

void magic(int n) {
    if (n <= 0) return;
    if (n & 1) {
        magic((n - 1) / 2);
        putchar('1');
    } else {
        magic((n - 2) / 2);
        putchar('2');
    }
}

void work() {
    magic(n);
    putchar('\n');
}

int main() {
    read();
    work();
    return 0;
}

编辑于 2017-09-22 18:14:37 回复(14)

淋不湿的人

def function(n):
    if(n<=0):
        return
    str=''
    while(n>0):
        if (n%2): #odd
            n=(n-1)/2
            str='1'+str
        else:
            n=(n-2)/2
            str='2'+str
    return str
n=int(input())
print(function(n))

发表于 2018-03-26 09:16:51 回复(0)

JavaScript

Conan06

var n = parseInt(readline());
var result = [];

while(n) {
  if(n % 2 == 0) {
    n = (n - 2) / 2;
    result.unshift("2");
  } else {
    n = (n - 1) / 2;
    result.unshift("1");
  }
}

print(result.join(""));

发表于 2017-09-12 10:24:04 回复(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)

霍七

语言：C++ 运行时间： 1 ms 占用内存：376K 状态：答案正确
2x + 1一定是奇数，2x + 2一定是偶数。
如果n是奇数，那最后一步一定是使用魔法机器1；如果n是偶数，最后一步一定是使用魔法机器2。
由此想法可以递推，输出在每次递推之后，这样可以保证倒序输出。
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)上，持续更新。

#include 
using namespace std;
void recursion(int n);
int main()
{
    int n; cin >> n;
    recursion(n);
    return 0;
}
void recursion(int n)
{
    if (n != 0) {
        if (n % 2) {
            recursion((n - 1) / 2);
            cout << "1";
        }
        else {
            recursion((n - 2) / 2);
            cout << "2";
        }
    }
}

发表于 2017-10-10 10:12:55 回复(3)

元气の悟空

#include<stdio.h>
#include<vector>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        vector<char> res;
        while(n){
            if(n%2==0){
                n=(n-2)/2;
                res.push_back('2');
            }else{
                n=(n-1)/2;
                res.push_back('1');
            }
        }
        for(n=res.size()-1;n>=0;n--) printf("%c",res[n]);
        printf("\n");
    }
}

发表于 2017-09-18 19:48:23 回复(0)

宁爷

典型的深度搜索问题，利用递归可以轻松得到结果

#include<iostream>

#define true 1
#define false 0
int sum,k;
vector<int> a;
int step=0;
bool DFS(int n,int type)
{
int n1;
if(n>k)
return false;
if(n==k)
return true;
if(DFS(2*n+1,1))
a[step++]=1;
if(DFS(2*n+2,2))
a[step++]=2;
}
int main()
{
sum=0;
cin>>k;
DFS(sum,1);
for(int i=0;i<step;i++)
{
if(a[i]==1)
cout<<'1';
if(a[i]==2)
cout<<'2';
}
cout<<endl;
return 0;
}

发表于 2017-09-17 20:42:56 回复(0)

超级无敌小浪浪

importjava.util.Scanner;

publicclassMain {

publicstaticvoidmain(String[] args) {

// TODO Auto-generated method stub

Scanner sc = newScanner(System.in);

intn = sc.nextInt();

magic(n);

}

privatestaticvoidmagic(intn) {

// TODO Auto-generated method stub

intr = n;

if(r==0){

return;

}

if((n-1)%2==0){

r = (n-1)/2;

magic((n-1)/2);

System.out.print("1");

}

elseif((n-2)%2==0){

r = (n-2)/2;

magic((n-2)/2);

System.out.print("2");

}

发表于 2017-09-12 14:23:59 回复(0)

C/C++

Mesut10

 #include<stdlib.h>
#include<stdio.h>

void magicMachine(int n){
    if (n == 0)
        return;

    if (n %2){
        n = (n - 1) / 2;
        magicMachine(n);
        printf("1");
    }
    
    else{
        n = (n - 2) / 2;
        magicMachine(n);
        printf("2");
    }
}

int main(){
    int n = 0;
    scanf("%d", &n);
    if (n >= 1 && n <= 1000000000)
        magicMachine(n);
}

发表于 2018-02-28 18:11:06 回复(0)

Java

戏舞

import java.util.*;

/**
* 1.可以倒序来推倒,如果需要的硬币数量为偶数,那么最后一次一定使用的是
*     2x+2,否则是2x+1.
* 2.那么便可以从当前输入向上回溯,一直到初始为0,每次记录使用的机器编号.
* 3.利用StringBuilder保存编号,最后采用其倒置方法来获取输出
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int coinCount = input.nextInt();
System.out.println(execute(coinCount));
}

public static String execute(int coinCount) {
StringBuilder result = new StringBuilder();
while (coinCount > 0) {
if (coinCount % 2 == 0) {
coinCount = (coinCount - 2) / 2;
result.append("2");
}
else {
coinCount = (coinCount - 1) / 2;
result.append("1");
}
}

return result.reverse().toString();
}
}

发表于 2017-10-10 00:42:10 回复(0)

Ymir

题目设计有问题啊……投入的币x可以为0，那一机器投0可以得一个，机器二投0还可以得两个……

发表于 2017-09-29 08:45:20 回复(0)

水的一比

#include<stdlib.h>
#include<stdio.h>

//--观察发现当前魔法币，按照两个机器生产，可构成一颗完全二叉树
//--递归向根节点移动
void magicMachine(int n){
    if(n==0)
        return;
    
    //--当前为奇数个魔法币，是采用机器1生产得到的
    if(n&0x01==1){
        n=(n-1)/2;
        magicMachine(n);
        printf("1");
    }
    //--当前为偶数个魔法币，是采用机器2生产得到的
    else{
        n=(n-2)/2;
        magicMachine(n);
        printf("2");
    }
}

int main(){
    int n=0;
    scanf("%d",&n);
    if(n<1 || n>1000000000)
        return 0;
    
    magicMachine(n);
    return 0;
}

发表于 2017-09-11 16:02:40 回复(0)

向阳201712260557382

n = int(input())
ll=''
def f(n):
    if n%2 == 0 and n:
        f((n-2)/2)
        print(2,end='')
    elif n%2 == 1:
        f((n-1)/2)
        print(1,end='')
    elif n == 0:
        return
    return
f(n)

直接反向往回推，用递归很简单

发表于 2018-10-22 14:28:33 回复(0)

不掉一根毛

  importjava.util.Scanner; 
    
  publicclassMain { 
    
      publicstaticvoidmain(String[] args) { 
          Scanner s = newScanner(System.in); 
          intnum = s.nextInt(); 
          if(num<1|| num>1000000000){ 
              System.exit(0); 
          } 
          String temp = ""; 
          while(num>0){ 
              if(num%2== 0){ 
                  num = (num-2)/2; 
                  temp += "2"; 
              } 
              if(num%2== 1){ 
                  num = (num-1)/2; 
                  temp += "1"; 
              } 
          } 
          System.out.println(newStringBuilder(temp).reverse().toString()); 
      } 
    
  } 

发表于 2018-04-17 16:52:02 回复(0)

Java

沐遇晨光里

  importjava.util.Scanner; 
  publicclassMain{ 
      publicstaticvoidmain(String args[]){ 
          Scanner input = newScanner(System.in); 
          intnum = input.nextInt(); 
          StringBuffer str = newStringBuffer(""); 
          while(num > 0){ 
              if(num % 2== 0){ 
                  str.append("2"); 
                  num = (num - 2) / 2; 
              }else{ 
                  str.append("1"); 
                  num = (num - 1) / 2; 
              } 
          } 
          System.out.println(str.reverse().toString()); 
      } 
  } 

发表于 2017-10-18 18:19:59 回复(0)

y______

int main()
{
    int n;
    while(rd(n) != EOF)
    {
        string ans = "";
        while(n)
        {
            if(n & 1)//是奇数
            {
                n = (n - 1) / 2;
                ans += '1';
            }
            else
            {
                n = (n - 2) / 2;
                ans += '2';
            }
        }
        reverse(ans.begin(), ans.end());
        cout << ans <<endl;
    }
    return 0;
}

题目没有说清楚，每一次放必须投入手中所有的钱币还是部分钱币也可以。。。

发表于 2017-10-12 14:29:33 回复(0)

JavaScript

Orange。

while(line = readline()){
    var n = parseInt(line);
    var res = '';
    while(n){
        if(n%2 == 0){
            n = (n-2)/2;
            res += '2';
        }else{
            n = (n-1)/2;
            res += '1';
        }
    }
    var result = res.split('').reverse().join('');
    console.log(result);
}

发表于 2017-09-11 21:37:44 回复(5)

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)

没丶有梦想

s = readline()
var j = 1;
var result = [];
for(var i = 0; i < s.length-1;){
    while(s[i] === s[j]){
        j++;
    }
    result.push(j-i);
    i = j;
    j++;
}
if(s[s.length-1] !== s[s.length-2]) result.push(1);
var num = result.reduce(function(prev,next){return prev + next;})/result.length;
print(num.toFixed(2))

发表于 2017-09-21 14:38:14 回复(0)