java实现砝码称重

5个砝码

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。

如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。

本题目要求编程实现：对用户给定的重量，给出砝码组合方案。

例如：

用户输入：

5

程序输出：

9-3-1

用户输入：

19

程序输出：

27-9+1

要求程序输出的组合总是大数在前小数在后。

可以假设用户的输入的数字符合范围1~121。

//方法1：三进制处理

package com.liu.ex1;

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static int[] value = new int[6];

    public void printResult(int n) {

        int count = 0;

        while(n > 0) {  //把n转换为三进制数

            value[count++] = n % 3;

            n = n / 3;

        }

        //对n的三进制数进行处理，得到砝码组合结果

        for(int i = 0;i < 5;i++) {

            if(value[i] >= 2) {

                value[i] = value[i] - 3;

                value[i + 1] = value[i + 1] + 1;

            }

        }

        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i = 5;i >= 0;i--) {

            if(value[i] == 1) {

                int a = (int) Math.pow(3, i);

                list.add(a);

            } else if(value[i] == -1) {

                int a = (int) (-1 * Math.pow(3, i));

                list.add(a);

            }

        }

        System.out.print(list.get(0));

        for(int i = 1;i < list.size();i++) {

            if(list.get(i) > 0) {

                System.out.print("+");

            }

            System.out.print(list.get(i));

        }

        return;

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        test.printResult(n);

    }

}

//方法2：DFS搜索

package com.liu.ex1;

import java.util.ArrayList;

import java.util.Scanner;

public class Main1 {

    public static int[] value = {1,3,9,27,81};

    public static int n = 0;

    public static ArrayList<Integer> result = new ArrayList<Integer>();

    public int getSum() {

        int sum = 0;

        for(int i = 0;i < result.size();i++)

            sum += result.get(i);

        return sum;

    }

    public void dfs(int step) {

        if(step == 5) {

            if(getSum() == n) {

                int i = result.size() - 1;

                for(;i >= 0;i--) {

                    if(result.get(i) != 0) {

                        System.out.print(result.get(i));

                        i--;

                        break;

                    }

                }

                for(;i >= 0;i--) {

                    if(result.get(i) == 0)

                        continue;

                    if(result.get(i) > 0)

                        System.out.print("+");

                    System.out.print(result.get(i));

                }

            }

        } else {

            for(int i = -1;i <= 1;i++) {

                int a = i * value[step];

                result.add(a);

                dfs(step + 1);

                result.remove(result.size() - 1);

            }

         }

    }

    public static void main(String[] args) {

        Main1 test = new Main1();

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        test.dfs(0);

    }

}

巴特西

java实现砝码称重

最新文章

热门文章