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