一道竞赛题目、、求各种答案、、来牛人

Jly8232 2012-04-04 08:56:49

加精

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
例如：
用户输入：
5
程序输出：
9-3-1
用户输入：
19
程序输出：
27-9+1

输入：
41
输出：
81-27-9-3-1

要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。

...全文

15679 256 打赏收藏转发到动态举报

写回复

用AI写文章

256 条回复

切换为时间正序

请发表友善的回复…

发表回复

ZBDZZG 2014-12-10

打赏
举报

public class Foo {
    private static final int[] item = new int[] {1, 3, 9, 27, 81, 243};
    private static int target;

    private static final int[] sign = new int[item.length];

    public static void main(String[] args) throws IOException {
        int S = 0;
        for (int anItem : item) {
            S += anItem;
        }

        for (target = 1; target <= S; target++) {
            calculate(0);
        }
    }

    private static void calculate(int deepth) {
        if (deepth == item.length) {
            int S = 0;
            for (int i = 0; i < item.length; i++) {
                S += item[i] * sign[i];
            }
            if (S == target) {
                for (int i = item.length - 1; i >= 0; i--) {
                    switch(sign[i]) {
                        case 0: break;
                        case 1:
                            System.out.print(" + " + item[i]);
                            break;
                        case -1:
                            System.out.print(" - " + item[i]);
                    }
                }
                System.out.println(" = " + target);
            }
        } else {
            for (int s = -1; s < 2; s++) {
                sign[deepth] = s;
                calculate(deepth + 1);
            }
        }
    }
}

from java

AP0511502 2013-12-27

打赏
举报

public class BalanceWeigh { int balanceWeight = 81; int[] needBalanceWeights = { 0, 0, 0, 0, 0 }; boolean isHaveNegativeNumber = false; int negativeNumberIndex = 0; int i = 4; private void changeInputValueToTernary(int inputValue) { int inputValueTemp = inputValue; while (inputValue != 0) { if (balanceWeight > inputValue) { balanceWeight /= 3; i--; } else { inputValue -= balanceWeight; needBalanceWeights[i]++; } } changeToNeedBalanceWeights(); printNeedBalanceWeights(inputValueTemp); } private void changeToNeedBalanceWeights() { for (int j = 0; j < needBalanceWeights.length; j++) { if (needBalanceWeights[j] == 2) { needBalanceWeights[j] = -1; needBalanceWeights[j + 1] = needBalanceWeights[j + 1] + 1; negativeNumberIndex = j; isHaveNegativeNumber = true; } else if (needBalanceWeights[j] == 3) { needBalanceWeights[j + 1] = needBalanceWeights[j + 1] + 1; } } } private void printNeedBalanceWeights(int inputValue) { StringBuffer needBalanceWeightStr = new StringBuffer("输入的重量：" + inputValue + "\n"); needBalanceWeightStr.append("需要砝码的三进制：" + Arrays.toString(needBalanceWeights) + "\n"); needBalanceWeightStr.append("左边需要的砝码：%s;右边需要的砝码：%s"); StringBuffer leftBalances = new StringBuffer(); StringBuffer rightBalances = new StringBuffer(); for (int j = 0; j < needBalanceWeights.length; j++) { if(needBalanceWeights[j]==0) continue; double temp = 0; if (isHaveNegativeNumber && j <= negativeNumberIndex) { if(needBalanceWeights[j]<0){ temp = -needBalanceWeights[j]*Math.pow(3,j); }else{ temp = needBalanceWeights[j]*Math.pow(3,j); } leftBalances.append("[" + temp + "] "); } else { temp = needBalanceWeights[j]*Math.pow(3,j); rightBalances.append("[" + temp + "] "); } } System.out.printf(needBalanceWeightStr.toString(),leftBalances,rightBalances); } public static void main(String[] args) { BalanceWeigh balanceWeigh = new BalanceWeigh(); Scanner sc = new Scanner(System.in); System.out.print("请输入0-121之间的数字："); int inputValue = sc.nextInt(); balanceWeigh.changeInputValueToTernary(inputValue); } }

SevenTi 2013-11-19

打赏
举报

受教了。。。。。！感谢！！！！

472701579 2013-07-17

打赏
举报

xx070911 2013-07-16

打赏
举报

收藏，以后看、

z599245299 2013-07-13

打赏
举报

4#的代码有问题加号减号乱了

fenfafei 2013-05-29

打赏
举报

膜拜大神

jie38song 2013-05-20

打赏
举报

还没有进一步简化，这样足矣了吧。至于思想，楼主自己慢慢看吧。


import java.util.Scanner;

public class CacuTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		System.out.println("please input the number you want to get:");
		Scanner in=new Scanner(System.in);
		int num;
		num=in.nextInt();
		System.out.println(toString(num));

	}

	private static String toString(int num) {
		for(int i=1;i<=121;i++){
			
			String str=Integer.toString(i, 3);
			int sum=0;
			for(int j=0;j<str.length();j++){
				sum+=(int)Math.pow(3, j)*(Integer.parseInt(""+str.charAt(j))-1);
			}
			if(sum==num){
				StringBuilder sb=new StringBuilder();
				for(int k=4;k>=0;k--){
					if(k>=str.length()){
						continue;
					}
					switch(str.charAt(k)){
					case '2':
						if(sb.length()!=0){
							sb.append("+");
						}
						sb.append(""+(int)Math.pow(3,k));
						break;
					case '1':
						break;
					case '0':
						sb.append("-"+(int)Math.pow(3, k));
					default:
						break;
					}
				}
				return sb.toString();
			}
		}
		
		
		return null;
	}

}

测试通过

-try 2013-04-26

打赏
举报

膜拜

冷艳 2013-04-26

打赏
举报

我这还没入门的菜鸟表示很佩服很佩服，学习了，以后好好学习，天天算法。

Chenzhenqing 2013-04-19

打赏
举报

引用 20 楼 BikeyTang 的回复:

计算机算法中的--贪心法算法--可以解决。

怎么做，不懂。。。

叮咚细语 2013-04-13

打赏
举报

引用 4 楼 liwei1292359 的回复:

Java code?1234567891011121314151617181920212223242526272829303132333435363738394041public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print("请输入0……

for循环太多了,不够优化

从此安心潜水被占用 2013-02-18

打赏
举报

好吧，我又挖坟了，勿怪

从此安心潜水被占用 2013-02-18

打赏
举报

引用 221 楼 wskld85 的回复:

左边放一5克的东西，（9-3-1）右边要怎么放？砝码还能减？

你可以把3+1放到左边盘里啊

LogicTeamLeader 2012-09-24

打赏
举报

想搞递归没想清楚，搞了个最简单的，掩面而走：



/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package chapter4;



import java.io.IOException;

import java.util.Scanner;

import java.util.logging.Level;

import java.util.logging.Logger;



/**

 *

 * @author user

 */

public class Guess {



    public static void main(String[] args) {

        System.out.print("input your number:");

        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        boolean flag = false;

        for (int a = -1; a < 2; a++) {

            for (int b = -1; b < 2; b++) {

                for (int c = -1; c < 2; c++) {

                    for (int d = -1; d < 2; d++) {

                        for (int e = -1; e < 2; e++) {

                            if (num == 1 * a + 3 * b + 9 * c + 27 * d + 81 * e) {

                                if (e == 1) {

                                    System.out.print("81");

                                    flag = true;

                                }

                                if (d == 1) {

                                    if (flag) {

                                        System.out.print("+");

                                    }

                                    System.out.print("27");

                                    flag = true;

                                } else if (d == -1) {

                                    if (flag) {

                                        System.out.print("-");

                                    }

                                    System.out.print("27");

                                    flag = true;

                                }

                                if (c == 1) {

                                    if (flag) {

                                        System.out.print("+");

                                    }

                                    System.out.print("9");

                                    flag = true;

                                } else if (c == -1) {

                                    if (flag) {

                                        System.out.print("-");

                                    }

                                    System.out.print("9");

                                    flag = true;



                                }

                                if (b == 1) {

                                    if (flag) {

                                        System.out.print("+");

                                    }

                                    System.out.print("3");

                                    flag = true;

                                } else if (b == -1) {

                                    if (flag) {

                                        System.out.print("-");

                                    }

                                    System.out.print("3");

                                    flag = true;

                                }

                                if (a == 1) {

                                    if (flag) {

                                        System.out.print("+");

                                    }

                                    System.out.print("1");

                                } else if (a == -1) {

                                    if (flag) {

                                        System.out.print("-");

                                    }

                                    System.out.print("1");

                                }

                            }

                        }

                    }

                }

            }

        }

    }

}