public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.print("请输入0-121之间的数字:");
int n=sc.nextInt();
if(n>=0&&n<=121){
int[] a={0,-1,1};
int[] b={0,-3,3};
int[] c={0,-9,9};
int[] d={0,-27,27};
int[] e={0,-81,81};
for(int h=0;h<a.length;h++){
for(int i=0;i<b.length;i++){
for(int j=0;j<c.length;j++){
for(int k=0;k<d.length;k++){
for(int l=0;l<e.length;l++){
if(a[h]+b[i]+c[j]+d[k]+e[l]==n){
if(e[l]!=0){
System.out.print(e[l]+"+");
}
if(d[k]!=0){
System.out.print(d[k]+"+");
}
if(c[j]!=0){
System.out.print(c[j]+"+");
}
if(b[i]!=0){
System.out.print(b[i]+"+");
}
if(a[h]!=0){
System.out.print(a[h]);
}
}
}
}
}
}
}
}else{
System.out.println("输入不合法");
}
}
获取组合的方法,首先数组元素做全部组合,然后各组合的元素依次加上正负符号求和,把和满足1-121之间的组合(包括正负符号一起)保存到map中for example
import java.util.*;
public class Test {
public static void main(String[] args) throws Throwable {
int[] a = {1, 3, 9, 27, 81};
Map<Integer, List<int[]>> map = getSolutions(a);
Scanner sc = new Scanner(System.in);
String num = "";
int weight = 0;
while (true) {
System.out.printf("请输入1-121之间的重量[输入负数退出程序]:");
try {
num = sc.nextLine();
weight = Integer.parseInt(num);
if (weight < 0) {
System.out.println("Bye...");
break;
}
if (weight < 1 || weight > 121) {
throw new Exception("非法输入");
} int[] n = map.get(weight).get(0);
System.out.printf("%d=%d", weight, n[0]);
for (int i=1; i<n.length; i++) {
System.out.printf("%s%d", (n[i]<0 ? "" : "+"), n[i]);
}
System.out.println();
} catch (Exception e) {
System.out.printf("非法输入,请重新输入\n");
continue;
}
}
} public static Map<Integer, List<int[]>> getSolutions(int[] a) { //获取各种组合
Map<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();
int cnt = (int)Math.pow(2, a.length);
for (int i=1, j=0, k=0, t=i; i<cnt; i++,j=0,k=0,t=i) {
int[] n = new int[Integer.bitCount(t)];
while (t > 0) {
if (t%2 == 1) n[j++] = a[k];
t >>= 1;
k++;
} int p = (int)Math.pow(2, n.length);
for (int u=0, v=u; u<p; u++, v=u) {
int sum = 0;
int[] m = Arrays.copyOf(n, n.length);
for (int w=0; w<m.length; w++) {
if ((v>>w & 0x01) == 1) m[w] *= -1;
sum += m[w];
}
if (sum > 0) {
if (! map.containsKey(sum)) {
map.put(sum, new ArrayList<int[]>());
} Arrays.sort(m);
for (int w=0,x=0; w<m.length/2; w++) {
x = m[w];
m[w] = m[m.length-w-1];
m[m.length-w-1] = x;
}
map.get(sum).add(m);
}
}
}
return map;
}
}
public class DemoMain {
static int w [] = {1,3,9,27,81};
public static void main(String[] args) {
int input = 1;
while(input != 122)
{
int temp = input;
int flag = 1;
String result = "";
for(int i =4; i > -1 ;i--)
{
if(temp ==w[i])
{
result = result = result + "+" +w[i];
break;
}
if(temp ==-w[i])
{
result = result = result + "-" +w[i];
break;
}
if(temp > (w[i]+1)/(-2) && temp < (w[i]+1)/(2) &&temp != (w[i]+1)/(-2) && temp != (w[i]+1)/(2) )
{
continue;
}
else if(temp <= (w[i]+1)/(-2))
{
temp = temp +w[i];
result = result + "-" +w[i];
}
else if(temp >= (w[i]+1)/(2))
{
temp = temp -w[i];
result = result + "+" +w[i];
}
}
System.out.println(result.substring(1));
input ++;
}
}
}
int[] fama砝码的重量;
int weight要求的重量。
Stack stack储存比weight小的数;
例如:int[] fama = {1, 3, 9, 27, 81};int weight=50;stack={1,3,9,27};
执行action(50,sb)//sb stringbuffer;
1.如果weight > stack元素之和,说明81在 sb中。所以 sb = 81-(;运行aciton(81-50,sb);
2.如果 weight = stack元素之和,直接sb = 1+3+9+27;
3.如果 weight< stack元素之和,把27出栈顶,运行aciton(50,sb);
所以执行1了,运行action(31,sb)
执行1,31> 1+3+9,所以找到27
如果 27>31 sb=81-(27-
如果27<31 sb = 81-(27+
重复操作
最后结果是
81+(27-(9-(3-(1))));
剩下的就是拆括号了。import java.util.Stack;public class TianPing {
Integer[] fama;
int weight;
Stack<Integer> stack=new Stack<Integer>();
StringBuffer sb = new StringBuffer();
public TianPing(Integer[] array,int weight){
this.fama = array;
this.weight = weight;
for(int a:fama){
if(a <= weight){
stack.push(a);
}
}
action(weight,sb);
System.out.println(sb.toString());
}
public void action(int weight,StringBuffer sb){
int totalWeight = 0;
while(weight <= stack.peek()){
if(weight==stack.peek()){
sb.append(stack.peek());
return;
}
stack.pop();
}
for(int i=0;i<stack.size();i++){
totalWeight+=stack.elementAt(i);
}
if(weight>totalWeight){
if(fama[stack.size()]>weight){
sb.append(fama[stack.size()]+"-(");
action(fama[stack.size()]-weight,sb);
}
else if(fama[stack.size()]<weight){
sb.append(fama[stack.size()]+"+(");
action(weight - fama[stack.size()],sb);
}
sb.append(")");
}
else if(weight < totalWeight){
stack.pop();
action(weight,sb);
}
else if(weight == totalWeight){
while(!stack.isEmpty()){
sb.append(stack.pop()+"+");
}
sb.setLength(sb.length()-1);
return;
}
}
public static void main(String args[]){
Integer []array = {1,3,9,27,81};
new TianPing(array,101);
}
}
public class TianPing {
Integer[] fama;
int weight;
Stack<Integer> stack=new Stack<Integer>();
StringBuffer sb = new StringBuffer();
public TianPing(Integer[] array,int weight){
this.fama = array;
this.weight = weight;
for(int a:fama){
if(a <= weight){
stack.push(a);
}
}
action(weight,sb);
System.out.println(sb.toString());
}
public void action(int weight,StringBuffer sb){
int totalWeight = 0;
while(weight <= stack.peek()){
if(weight==stack.peek()){
sb.append(stack.peek());
return;
}
stack.pop();
}
for(int i=0;i<stack.size();i++){
totalWeight+=stack.elementAt(i);
}
if(weight>totalWeight){
if(fama[stack.size()]>weight){
sb.append(fama[stack.size()]+"-(");
action(fama[stack.size()]-weight,sb);
sb.append(")");
}
else if(fama[stack.size()]<weight){
sb.append(fama[stack.size()]+"+");
action(weight - fama[stack.size()],sb);
}
}
else if(weight < totalWeight){
stack.pop();
action(weight,sb);
}
else if(weight == totalWeight){
while(!stack.isEmpty()){
sb.append(stack.pop()+"+");
}
sb.setLength(sb.length()-1);
return;
}
}
public static void main(String args[]){
Integer []array = {1,3,9,27,81};
for(int i=1;i<=121;i++){
new TianPing(array,i);
}
}
}
//这次好了。原理一样的。
public class DemoMain {
static int w [] = {1,3,9,27,81};
public static void main(String[] args) {
int input = 1;
while(input != 122)
{
int temp = input;
String result = "";
for(int i =4; i > -1 ;i--)
{
//找到了最后一个结束
if(temp ==w[i])
{
result = result = result + "+" +w[i];
break;
}
if(temp ==-w[i])
{
result = result = result + "-" +w[i];
break;
}
if(temp > (w[i]+1)/(-2) && temp < (w[i]+1)/(2) )//本次不能加也不能减
{
continue;
}
else if(temp <= (w[i]+1)/(-2))//本次必须减(不减后面无解)
{
temp = temp +w[i];
result = result + "-" +w[i];
}
else if(temp >= (w[i]+1)/(2))//本次必须加(不加后面无解)
{
temp = temp -w[i];
result = result + "+" +w[i];
}
}
System.out.println(result.substring(1));
input ++;
}
}
}
using namespace std;int main()
{
int input;
cin >> input; int w[5] = {0, 0, 0, 0, 0};
int weight = 81;
int remain = input;
int i = 4;
//求input对应的三进制
while(input != 0)
{
if(weight > input)
{
weight /= 3;
i--;
}
else
{
input -= weight;
w[i]++;
}
}
//修改,逢3向前进1,逢2原位改为-1并向前进1
for(i = 0; i < 4; i++)
{
if(w[i] == 3)
w[i] = 0, w[i+1]++;
else if(w[i] == 2)
w[i] = -1, w[i+1]++;
} //输出
bool first = true;
for(weight = 81, i = 4; i >= 0; i--, weight /= 3)
{
if(w[i] > 0 && !first)
cout << "+";
if(w[i] != 0)
{
cout << w[i] * weight;
first = false;
}
}
cout << endl; return 0;
}
#include <stdio.h>unsigned three[21] = {1};
int s[21];int main()
{
int n;
for (int i = 1; i < 21; ++i)
three[i] = three[i-1]*3;
while (scanf("%d", &n) != EOF)
{
int carry = 0, i;
printf("%d = ", n);
for (i = 0; n; n /= 3, ++i)
if (carry = (s[i] = n%3+carry) > 1)
s[i] -= 3;
if (carry) s[i++] = carry;
printf("%u", three[--i]);
while (i)
if (s[--i])
printf(" %c %u", s[i] > 0 ? '+' : '-', three[i]);
putchar('\n');
}
return 0;
}
SA、AB、BC、CD、DE的权值分别为1,3,9,27,81
S到A有两条路径,一条权值为1,另一条为-1
AB、BC、CD、DE类似
用户的输入可以看成是一个权值
而算法的输出是可以得到用户输入权值的路径
这样就可以借助动态规划问题的解法来解题了不知这样可不可以??
#include <stdio.h>#define NUM 5
int Stac[NUM] = {1,3,9,27,81};
int m_Scan;void De2(int tc)
{
int temp;
for(int i = NUM-1;i>-1;i--)
{
if(Stac[i]<tc)
{
temp = tc - Stac[i];
printf("%d-",Stac[i]);
De2(temp);
return;
}
else if(Stac[i] == tc)
{
printf("%d",Stac[i]);
return;
}
}
}void Defop(int tc)
{
int temp;
for(int i = 0;i<NUM;i++)
{
if(Stac[i]>tc)
{
temp = Stac[i] - tc;
printf("%d-",Stac[i]);
De2(temp);
return;
}
else if(Stac[i] == tc)
{
printf("%d",Stac[i]);
return;
}
}
}int main(int argv,char **argc)
{
scanf("%d",&m_Scan);
Defop(m_Scan);
}
package com.test;import java.util.ArrayList;
import java.util.List;public class Tianping {
static List<String> list = new ArrayList<String>();
static int[] fama = new int[]{1,3,9,27,81};
/**
* @param args
*/
public static void main(String[] args) {
int[] fama = new int[]{1,3,9,27,81};
for (int i = 0 ; i < fama.length ;i++){
put(i);
}
for (String v : list) {
System.out.println(v);
} }
public static void put(int num){
int base = fama[num];
int baseLenth ;
if (num == 0 ){
list.add(String.valueOf(fama[0]));
}else{
baseLenth = list.size();
System.out.println("current map.size is :" + baseLenth);
for (int i = 0 ; i < baseLenth ; i++){
list.add(base+ "-" +list.get(baseLenth - i -1).replaceAll("\\+", "##").replaceAll("-", "\\+").replaceAll("##", "-"));
}
list.add(String.valueOf(base));
for (int i = 0 ; i < baseLenth ; i++){
list.add(base+ "+" +list.get(i));
}
}
}}
private static int[] has = new int[5];// -1表示减,0表示无,1表示加
private static int[] fama = { 1, 3, 9, 27, 81 }; public static void main(String[] args) {
f(0);
} private static void f(int n) {// 回溯
if (n == 5) {
if (sum() == weight) {
System.out.println(Arrays.toString(has));
System.exit(1);
}
} else {
for (int i = -1; i < 2; ++i) {
has[n] = i;
f(n + 1);
}
}
} private static int sum() {
int a = 0;
for (int i = 0; i < 5; i++) {
a += has[i] * fama[i];
}
return a;
}
}
public class test{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.print("请输入0-121之间的数字:");
int n=sc.nextInt();
if(n>=0&&n<=121){
int[] a={0,-1,1};
int[] b={0,-3,3};
int[] c={0,-9,9};
int[] d={0,-27,27};
int[] e={0,-81,81};
for(int h=0;h<a.length;h++){
for(int i=0;i<b.length;i++){
for(int j=0;j<c.length;j++){
for(int k=0;k<d.length;k++){
for(int l=0;l<e.length;l++){
if(a[h]+b[i]+c[j]+d[k]+e[l]==n){
if(e[l]!=0){
System.out.print(e[l]);
}
if(d[k]!=0){
if(d[k]>0) {
if(e[l]==0) System.out.print(d[k]);
else System.out.print("+"+d[k]);
}
else System.out.print(d[k]);
}
if(c[j]!=0){
if(c[j]>0){
if(d[k]==0&&e[l]==0) System.out.print(c[j]);
else System.out.print("+"+c[j]);
}
else System.out.print(c[j]);
}
if(b[i]!=0){
if(b[i]>0){ if(c[j]==0&&d[k]==0&&e[l]==0)
System.out.print(b[i]);
else System.out.print("+"+b[i]);
}
else System.out.print(b[i]);
}
if(a[h]!=0){
if(a[h]>0){
if(b[i]==0&&c[j]==0&&d[k]==0&&e[l]==0)
System.out.print(a[h]);
else System.out.print("+"+a[h]);
}
System.out.print(a[h]);
}
}
}
}
}
}
}
}else{
System.out.println("输入不合法");
}
}
}
(2) 问题关键在于算法中如何体现砝码放在天平左边,右边或没有参加称量。这里可以用-1,1,0表示砝码放在天平左,右和没有参加称量,再没有其他数,所以称为三进制数,每个砝码都有这样的三种状态。
(3) 被称物体质量计算:m=a*81+b*27+c*9+d*3+e。这里a,b,c,d,e分别表示81,27,9,3,1克的砝码是放在天平的左边,右边或是没用。
for a: = 0 to 1 do
for b = -1 to 1 do
for c: = -1 to 1 do
for d: = -1 to 1 do
for e:= -1 to 1 do
package com.test;public class Tianping2 { /**
* @param args
*/
public static void main(String[] args) {
int input = 106;
int[] a , b , c , d , e;
a = b = c = d = e = new int[]{-1,0,1};
for (int ai : a){
for (int bi : b){
for (int ci : c){
for (int di : d){
for (int ei : e){
if (input == ei*81 + di*27 + ci*9 + bi*3 + ai*1){
System.out.println(ei*81 + "+" + di*27 + "+" + ci*9 + "+" + bi*3 + "+" + ai*1);
}else{
continue;
}
}
}
}
}
} }}
final static int COUNT = 5;
final static int[] CANDIDATE;
final static int[] SUM; static {
CANDIDATE = new int[COUNT];
SUM = new int[COUNT];
int tmp = 1, i = 0;
do {
CANDIDATE[i] = tmp;
SUM[i] = (i == 0 ? tmp : (SUM[i - 1] + tmp));
tmp *= 3;
i++;
} while (i < COUNT);
} static void getCombine(int num, int[] arr, int index) {
if (num == 0)
return;
for (int i = 0; i < COUNT; i++) {
if (num == CANDIDATE[i] || num == -CANDIDATE[i]) {
arr[index] = num;
return;
} else if (num > 0) {
if (num <= SUM[i]) {
arr[index] = CANDIDATE[i];
getCombine(num - CANDIDATE[i], arr, index + 1);
return;
}
} else {
if (-num <= SUM[i]) {
arr[index] = -CANDIDATE[i];
getCombine(num + CANDIDATE[i], arr, index + 1);
return;
}
}
}
} static void getCombine(int num) {
int[] result = new int[COUNT];
if (num >= SUM[0] && num <= SUM[COUNT - 1]) {
getCombine(num, result, 0);
StringBuilder builder = new StringBuilder();
for (int i = 0; i < COUNT; i++) {
if (result[i] == 0)
break;
else if (result[i] > 0) {
builder.append((i == 0 ? "" : "+") + result[i]);
} else {
builder.append("" + result[i]);
}
}
System.out.println(builder);
} else {
System.out.println("invalid input");
}
} public static void main(String[] args) {
getCombine(16);
}
}
final static int COUNT = 5;
final static int[] CANDIDATE;
final static int[] SUM; static {
CANDIDATE = new int[COUNT];
SUM = new int[COUNT];
int tmp = 1, i = 0;
do {
CANDIDATE[i] = tmp;
SUM[i] = (i == 0 ? tmp : (SUM[i - 1] + tmp));
tmp *= 3;
i++;
} while (i < COUNT);
} static void getCombine(int num, int[] arr, int index) {
if (num == 0)
return;
for (int i = 0; i < COUNT; i++) {
if (num == CANDIDATE[i] || num == -CANDIDATE[i]) {
arr[index] = num;
return;
} else if (num > 0) {
if (num <= SUM[i]) {
arr[index] = CANDIDATE[i];
getCombine(num - CANDIDATE[i], arr, index + 1);
return;
}
} else {
if (-num <= SUM[i]) {
arr[index] = -CANDIDATE[i];
getCombine(num + CANDIDATE[i], arr, index + 1);
return;
}
}
}
} static void getCombine(int num) throws Exception {
int[] result = new int[COUNT];
if (num >= SUM[0] && num <= SUM[COUNT - 1]) {
getCombine(num, result, 0);
StringBuilder builder = new StringBuilder();
for (int i = 0; i < COUNT; i++) {
if (result[i] == 0)
break;
else if (result[i] > 0) {
builder.append(i == 0 ? result[i] : ("+" + result[i]));
} else {
builder.append(result[i]);
}
}
System.out.println(builder);
} else {
throw new Exception("invalid input");
}
} public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
try {
int num = scanner.nextInt();
getCombine(num);
} catch (Exception e) {
System.out.println("invalid input");
return;
}
}
}
加了个捕捉输入
#include <iostream>using namespace std;
int T[10] = {81,-81,27,-27,9,-9,3,-3,1,-1};
int C[5];
int count;
int NUM;
void FS(int pos)
{
if(count) return;
int sum = 0;
for(int i = 0;C[i]&&i != 5;++i)
sum+=C[i];
if(sum == NUM)
{
for(int i = 0;C[i]&&i != 5;++i)
cout<<C[i]<<" ";
cout<<endl;
++count;
return;
}
if(pos == 5) return;
for(int i = 0;i != 10;++i)
{
int value = T[i];
int j;
for(j = 0;j != pos;++j)
if(value == C[j]||value+C[j] == 0) break;
if(j == pos)
{
C[pos] = value;
for(j = pos+1;j != 5;j++)
C[j] = 0;
FS(pos+1);
}
}
}
int main()
{
cin >> NUM;
FS(0);
return 0;
}
public String calculate(int number)
{
int[] weight = {1,3,9,27,81};
StringBuffer buffer = new StringBuffer();
if(number > 121 || number < 1)
{
return "输入非法";
}
int count = number;
int i = weight.length - 1;
while(i >= 0)
{
int total = 0;
for(int j = 0; j < i; j ++)
{
total += weight[j];
}
if(count > 0 && count - weight[i] >= 0 || (count - weight[i] < 0 && count - weight[i] + total >= 0 ))
{
count -= weight[i];
buffer.append("+" + weight[i]);
}
else if(count < 0)
{
count += weight[i];
buffer.append("-" + weight[i]);
}
i--;
}
return buffer.toString();
}
public String calculate(int number)
{
int[] weight = {1,3,9,27,81};
StringBuffer buffer = new StringBuffer();
if(number > 121 || number < 1)
{
return "输入非法";
}
int count = number;
int i = weight.length - 1;
while(i >= 0)
{
int total = 0;
for(int j = 0; j < i; j ++)
{
total += weight[j];
}
if(count > 0 && count - weight[i] >= 0 || (count - weight[i] < 0 && count - weight[i] + total >= 0 ))
{
count -= weight[i];
buffer.append("+" + weight[i]);
}
else if(count < 0)
{
count += weight[i];
buffer.append("-" + weight[i]);
}
i--;
}
return buffer.toString();
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Question
{
public class QuestionDemo
{
#region
//用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
//如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
//本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
//例如:
//用户输入:
//5
//程序输出:
//9-3-1
//用户输入:
//19
//程序输出:
//27-9+1
//输入:
//41
//输出:
//81-27-9-3-1
//要求程序输出的组合总是大数在前小数在后。
//可以假设用户的输入的数字符合范围1~121。
static int maxNum = 121;
public static int NUM_LENGTH = 5;
static int[] metaNum = { 1, 3, 9, 27, 81 };
static int[] metaNumReverse = { -1, -3, -9, -27, -81 }; public static void GetBalanceFormula(int n, ref int[] result)
{
if (n > maxNum)
{
Console.WriteLine("方法参数大于{0},请输入正确的参数调用方法", maxNum);
}
else
{
int i = 0;
int tempSum = 0;
bool isHaveNegativeNum = false;
int sign = n < 0 ? -1 : 1;
for (; i < metaNum.Length; i++)
{
tempSum += metaNum[i];
if (Math.Abs(n) == metaNum[i])
{
result[i] = sign * metaNum[i];
return;
}
else if (Math.Abs(n) == tempSum)
{
while (i >= 0)
{
result[i] = sign * metaNum[i];
i--;
}
return;
}
else if (Math.Abs(n) < tempSum)
{
break;
}
else if (Math.Abs(n) < metaNum[i + 1])
{
if (Math.Abs(n) > tempSum)
{
isHaveNegativeNum = true;
}
break;
}
}
if (isHaveNegativeNum)
{
result[i + 1] = sign * metaNum[i + 1];
GetBalanceFormula(n - sign * metaNum[i + 1], ref result);
}
else
{
result[i] = sign * metaNum[i];
GetBalanceFormula(n - sign * metaNum[i], ref result);
}
}
}
#endregion
}
class Program
{
static void Main(string[] args)
{ for (int j = 1; j <= 121; j++)
{
int[] result = new int[QuestionDemo.NUM_LENGTH];
QuestionDemo.GetBalanceFormula(j, ref result);
int sumMeta = 0;
for (int i = result.Length - 1; i >= 0; i--)
{
if (result[i] != 0)
{
sumMeta += result[i];
Console.Write("{0}\t", result[i]);
}
else
{
Console.Write("\t");
}
}
if (sumMeta == j)
{
Console.Write("Total is:{0}\t{1}\t", sumMeta, true);
}
else
{
Console.Write("Total is:{0}\t{1}\t", sumMeta, false);
}
Console.WriteLine();
}
Console.ReadLine();
}
}
}