[编程题]魔法币
• 热度指数：21726 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

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

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

`10`

## 输出

`122`

```#include <stdio.h>

int n;

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() {
work();
return 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());
}
}
}```

#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;
}

``````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(""));
``````

```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))```

```

Python

```
```
def magic_machine(x):
Operations = []
if x%2 <1: #偶数
Operations.append('2')
else:
Operations.append('1')

else:
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()

```

2x + 1一定是奇数，2x + 2一定是偶数。

``````#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";
}
}
}
``````

```#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");
}
}
```

#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;
}

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");
}
}

`}`

``` #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);
}

```

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();
}
}

```#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;
}```

``````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)
``````

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());
}

}

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());
}
}

```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;
}
```

```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);
}```

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))

115条回答 18888浏览

# 通过挑战的用户

• 2022-01-28 17:53:48
• 2022-01-23 22:53:46
• 2022-01-20 22:56:09
• 2022-01-17 20:07:45
• 2022-01-08 10:12:36

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题