天平秤重

天平秤重

问题描述：

用天平秤重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果有无限个砝码，但是他们的重量分别是1，3，9，27，81, .....等2的指数幂 神奇之处在于 他们的组合可以秤出任意整数重量（砝码允许放在左右两个盘中）。

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

例如：

用户输入：

5

程序输出：

9-3-1

/*** 7=(2,1)3=(1,-1,1)3    '3'指三进制* 先转换为三进制 然后反向防止溢出 */
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner input=new Scanner(System.in);int num&#Int();method(num);}private static void method(int num) {String str&#String(num, 3);//将数字转换为3进制int t=Integer.parseInt(str);int temp;int arr[]=new int[13];int i=0;temp=t;while(temp>0){arr[i]=temp%10;temp=temp/10;i++;}int arr1[]=new int[i+1];for (int j = 0; j <arr1.length; j++) {if (arr[j]==1) {arr1[j]=1;}else if (arr[j]==2) {arr1[j]=-1;arr[j+1]=arr[j+1]+1;}else if(arr[j]==3){arr[j+1]+=1;}}int k=1;for (int j = 0; j < arr1.length; j++) {arr1[j]=arr1[j]*k;		k=k*3;}for (int j = arr1.length-1; j>=0; j--) {if (arr1[j]!=0) {System.out.print(arr1[j]+" ");}}}}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main{	public static void method(int num){StringBuffer sb=new StringBuffer();int s[]={-1,0,1};for (int i = 1; i >-2; i--) {for (int j = 1; j >-2; j--) {for (int j2 = 1; j2 > -2; j2--) {for (int k = 1; k >-2; k--) {for (int k2 = 1; k2 >-2; k2--) {for (int l =1; l >-2; l--) {for (int l2 = 1; l2 >-2; l2--) {for (int m = 1; m >-2; m--) {for (int m2 = 1; m2 >-2; m2--) {for (int n = 1; n >-2; n--) {for (int n2 = 1; n2 >-2; n2--) {for (int o = 1; o >-2; o--) {for (int o2 = 1; o2 >-2; o2--) {for (int p = 1; p>-2; p--) {for (int p2 = 1; p2>-2; p2--) {
//																		1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 if(p2*1+p*3+o2*9+o*27+n2*81+n*243+m2*729+m*2187+l2*6561+l*19683+k2*59049+k*177147+j2*531441+j*1594323+i*4782969==num){if(i!=0)  sb.append(i*4782969+" ");if(j!=0)  sb.append(j*1594323+" ");if(j2!=0)  sb.append(j2*531441+" ");if(k!=0)  sb.append(k*177147+" ");if(k2!=0)  sb.append(k2*59049+" ");if(l!=0)  sb.append(l*19683+" ");if(l2!=0)  sb.append(l2*6561+" ");if(m!=0)  sb.append(m*2187+" ");if(m2!=0)  sb.append(m2*729+" ");if(n!=0)  sb.append(n*243+" ");if(n2!=0)  sb.append(n2*81+" ");if(o!=0)  sb.append(o*27+" ");if(o2!=0)  sb.append(o2*9+" ");if(p!=0)  sb.append(p*3+" ");if(p2!=0)  sb.append(p2*1+" ");System.out.println(sb);return;}}}}}}}}}}}}}}}}}public static void main(String[] args) {Scanner input=new Scanner(System.in);int num&#Int();method(num);}}

import java.util.Scanner;public class Main {static int len = 0;static int[] weight;// 打表public static void init(int n) {weight = new int[n + 1];while (true) {weight[len] = (int) Math.pow(3, len);if (weight[len++] > n) break;}}// 每个砝码只能用一次，所以当出现余数为2时，就当前位置变为-1，再往前进一位(使用更大的砝码)public static void solve(int n) {int p = 0;int[] arr = new int[len];String res = "";while (n > 0) {if (n % 3 == 2) {arr[p++] = -1;n = n / 3 + 1;} else {arr[p++] = n % 3;n /= 3;}}for (p = len - 1; p >= 0; p--) {if (arr[p] != 0) {if (arr[p] == 1) res += "+" + weight[p] * arr[p];else res += weight[p] * arr[p];}}System.out.println(res.startsWith("+") ? res.substring(1) : res);}public static void main(String[] args) {// TODO Auto-generated method stubScanner input = new Scanner(System.in);init(1000000); // MAX 1000000while (input.hasNext()) {int n = Int();solve(n);}input.close();}}