首页 > 试题广场 >

魔法币

[编程题]魔法币

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

输入

输出

算法知识视频讲解

Java

文不成武不就

//分奇偶数去求，若是奇数输出的最后一位肯定是1，同理。

import java.util.*;

public class Javapractice
{
    public static void main(String arg[])
    {
        ArrayList a=new ArrayList();
        boolean flag=true;
        int n=0;
        Scanner num=new Scanner(System.in);
        //StringBuilder a1 = new StringBuilder();
        while(flag){
                n=num.nextInt();
                //num.close();
                flag=false;
                if(n<1||n>(10e9)){
                    System.out.println("输入错误,请重新输入");
                    flag=true;}
                else
                    num.close();
                }

        while(n!=0)
        {

            if(n%2!=0)
            {
                --n;
                n=n/2;
                //a1.append("1");
                a.add("1");
            }
            else
            {
                n=n-2;
                n=n/2;
                //a1.append("2");
                a.add("2");
            }
        }
        //System.out.println(a1.reverse().toString());
        for(int i=a.size()-1;i>=0;i--)
            System.out.print(a.get(i));
    }
}

发表于 2018-04-27 19:56:53 回复(0)

Java

zhaoyf

这是一个变相的二进制计算问题。
数值   ：1  2   3   4   5   6   7
机器序列:1  2  11  12  21  22  111
0是机器1，1是机器2，机器序列表示为二进制：
二进制 ：0  1  00  01  10  11  000
高位补1：10 11 100 101 110 111 1000
新数值 ：2  3   4   5   6   7   8
新数值＝数值+1，新数值直接使用二进制位来判断;最高位1用于结束判断。
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        System.out.println(magic(num));
    }
    private static StringBuilder magic(int num) {
        num++;
        StringBuilder builder = new StringBuilder();
        while (num > 1) {
            if ((num & 1) > 0) {
                builder.insert(0, "2");
            } else {
                builder.insert(0, "1");
            }
            num = num >> 1;
        }
        return builder;
    }
}

发表于 2018-02-08 15:31:38 回复(0)

Java

帅～

import java.util.Scanner;

public class Main {
private static String numstr = "";


public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    computer(num);
    print();
}
public static int fun1(int n) {
    return (n - 1) % 2;
}
public static int fun2(int n) {
    return (n - 2) % 2;
}
public static int computer(int m) {
    int n = 0;
    while (m > 0) {
        n = fun1(m);
        if (n == 0) {
            numstr = numstr + 1 + ",";
            m = (m - 1) / 2;
            m = computer(m);
        } else {
            n = fun2(m);
            if (n == 0) {
                numstr = numstr + 2 + ",";
                m = (m - 2) / 2;
                m = computer(m);
            }
        }
    }
    return m;
}
public static void print() {
    String[] str = numstr.split(",");
    for (int i = str.length - 1; i >= 0; i--) {
        System.out.print(str[i]);
    }
}


}

编辑于 2017-12-17 11:30:13 回复(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)

Java

阿雪的贾哥

package demo;

import java.util.ArrayList;
import java.util.Scanner;

public class Demo01 {
    public static void main(String[] args) {
        //用ArrayList存储输出的结果
        ArrayList<Integer> list = new ArrayList<>(100);
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //用反推的思路,从后向前求解,最后将list中的值反向输出
        //当 n 不等于 0 时,一直循环下去
        while (n != 0){
            if ( (n-1)%2 == 0 ){ //(n-1)%2 == 0说明上一次用的是 1 号机器
                list.add(1);     //将值存入 list 中
                n = (n-1)/2;     //更新 n 的值
            } else{              //否则,说明上一次用的是 2 号机器
                list.add(2);     //将值存入 list 中
                n = (n-2)/2;     //更新 n 的值
            }
        }
        //反向输出list中的值
        for (int i = list.size()-1;i>= 0;i--)
            System.out.print(list.get(i));
    }
}

编辑于 2017-10-10 10:55:26 回复(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)

Java

没名没姓

import java.util.Scanner;

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    //输入需要的魔法币数
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    StringBuffer sb = new StringBuffer();

    while (n >= 0) {
        if (n == 0) {
            System.out.println(sb.reverse().toString());
            break;
        } else if (n > 0) {
            if (n % 2 == 0) {
                // 偶数
                n = (n - 2) / 2;
                sb.append("2");
            } else {
                // 奇数
                n = (n - 1) / 2;
                sb.append("1");
            }
        } else {
            System.out.println("无法获得所需魔法币！");
        }
    }
    /*String str = "";

    while (n >= 0) {
        if (n == 0) {
            System.out.println("依次投入机器顺序：" + str);
            break;
        } else if (n > 0) {
            if (n % 2 == 0) {
                // 偶数
                n = (n - 2) / 2;
                str = "2" + str; 
            } else {
                // 奇数
                n = (n - 1) / 2;
                str = "1" + str;
            }
        } else {
            System.out.println("无法获得所需魔法币！");
        }
    }*/

}

}

发表于 2017-09-25 10:59:31 回复(0)

Java

木子牙膏

import java.util.Scanner;

public class Main {

public static void main(String[] args) throws Exception{

Scanner scanner =new Scanner(System.in);

intnum = Integer.parseInt(scanner.nextLine());

String result = analize(num);

System.out.println(result);

}

/**

```
dfs
```

publicstaticString analize(intn)throwsException {

String str ="";

while(n >0){

if(n %2==0){

str +=2;

n = (n-2)/2;

}else{

str +=1;

n = (n-1)/2;

}

returnnewStringBuffer(str).reverse().toString();

}

编辑于 2017-09-11 15:51:45 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师贪心模拟网易 2018 数学 Java工程师

来自：网易2018校园招聘编...

上传者：小小

难度：

9条回答 892收藏 21409浏览

通过挑战的用户

洒脱7

2022-11-11 15:22:35
小小陈~

2022-10-24 18:49:27
wit1905...

2022-10-19 15:59:41
ringtt

2022-10-15 17:00:16
WA到头皮发麻

2022-10-07 17:15:32

魔法币

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题