首页 > 试题广场 >

魔法币

[编程题]魔法币
  • 热度指数:22004 时间限制: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

输入

10

输出

122

魔法机器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)
水题,求 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)

#include<iostream>
#include <vector>
#include<string>
#include <algorithm> 
using namespace std;
int main()
{
    int n;
    cin >> n;
    string str;
    
    while (n != 0)
    {
        if (n % 2)
        {
            n = (n - 1) / 2;
            str=str + '1';
            
        }
        else
        {
            n = (n-2) / 2;
            str = str + '2';
        }
    }
    reverse(str.begin(), str.end());
    cout << str<<endl;
}
 
发表于 2017-09-17 21:27:41 回复(7)
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
其实就是一个奇数和偶数的问题。
从输入的数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)
 #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)
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)
题目设计有问题啊……投入的币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)
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)
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)
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)
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)
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)