黑马程序员技术交流社区

标题: 来一个算法题 [打印本页]

---

作者: 暮色醉玄阳    时间: 2014-10-17 11:56
标题: 来一个算法题
如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
例如：
用户输入：
5
程序输出：
9-3-1
用户输入：
19
程序输出：
27-9+1

---

作者: 暮色醉玄阳    时间: 2014-10-17 11:57
package com.yx;

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

这是我借鉴的了，来个大神给个3进制的算法

---

作者: 泡沫__opt    时间: 2014-10-17 15:25
我擦~~太猛了……看不懂啊……

---

作者: 潘杰    时间: 2014-10-17 23:32
Java不用搞这种算法题把好像...

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2