2 qq 36804678 qq_36804678 于 2017.01.05 14:09 提问

根据哈夫曼树的原理求n个自然数相加减后结果最小(中间结果、最后结果不能负)。

根据哈夫曼树的原理求n个自然数相加减后结果最小(中间结果、最后结果不能负)。
问题描述:输入n个自然数,输出这n个数只做加减运算后得到的结果值最小,写出输出结果。
要求:
1)可以循环测试,可以选择退出程序;
2)打印这n个自然数进行加减的表达式(注意:中间结果不能为负);
例如:输入1,2,3,最后打印出3-2-1=0
3)输入数据要进行合法性检查;

12个回答

qq_36230119
qq_36230119   2017.01.06 13:16
已采纳

图片说明

qq_36804678
qq_36804678 评论里我不知道怎么上传照片,我在回答里上传了,您可以看一下,出错的那组数据最小值是正确的,但是加减顺序是错误的
12 个月之前 回复
qq_36804678
qq_36804678 我看了您运行的结果没有问题,我自己运行到第三组数据出错了(见下图),不过还是很感谢您,采纳了
12 个月之前 回复
qq_36804678
qq_36804678 这次没有问题!再多的感谢之词抵不上我果断的采纳您的方法!
12 个月之前 回复
miaoch
miaoch   2017.01.05 14:27

说说看法吧 哈弗曼生成算法 是选取最小的两个点 组合成新结点 新结点的值为 两个原结点的和
所以我觉得要使最后结果最小的话,只要用这n个树组成一个哈弗曼树 (如算法为右子树较大),然后取根节点的右子树减去左子树应该就是结果了。
如果我的想法不对的话,就说出来让我再想想

miaoch
miaoch   2017.01.05 14:43

额我写了个算法 发现自己这么想是错的

miaoch
miaoch   2017.01.05 15:13

然后我又想了一个 每次取最大的两个做减法 循环直到就剩1个,同时生成表达式字符串
剩下一个对其进行正则表达式匹配 将\+[0-9]{1,}的都移到最左边,我用java写的
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TestMain {

public static void main(String[] args) {
    List<Node> list = new ArrayList<>();
    for (int i=1; i<=20; i++) {
        list.add(new Node(i));
    }
    String result = "+" + getResult(list);
    String regex1 = "\\+[0-9]{1,}";
    String regex2 = "\\-[0-9]{1,}";
    Pattern p1 = Pattern.compile(regex1);
    Pattern p2 = Pattern.compile(regex2);
    Matcher m1 = p1.matcher(result);
    Matcher m2 = p2.matcher(result);
    String trueR = "";
    while (m1.find()) {
        trueR += m1.group();
    }
    while (m2.find()) {
        trueR += m2.group();
    }
    System.out.println(trueR.substring(1));
} 

private static String getResult(List<Node> nodes) {
    while (nodes.size() > 1) {  
        Collections.sort(nodes, new Comparator<Node>() {
            //降序
            @Override
            public int compare(Node o1, Node o2) {
                return o1.value - o2.value;
            }
        });
        Node right = nodes.get(nodes.size()-1);  
        Node left = nodes.get(nodes.size()-2);  
        Node newNode = new Node(right.value - left.value, right.expression + "-" + left.expression.replace("+", "@").replace("-", "+").replace("@", "-"));
        nodes.remove(nodes.size()-1);  
        nodes.remove(nodes.size()-1);  
        nodes.add(newNode);  
    }  
    Collections.sort(nodes, new Comparator<Node>() {
        //降序
        @Override
        public int compare(Node o1, Node o2) {
            return o1.value - o2.value;
        }
    });
    return nodes.get(0).expression;
}

}
class Node {

public Node(int value, String expression) {
    this.value = value;
    this.expression = expression;
}

public Node(int value) {
    this.value = value;
    expression = value + "";
}

String expression;
int value;

}


qq_36804678
qq_36804678 我请教老师他给了我用C写的关键代码 在他的论文里 我待会上传到这里
12 个月之前 回复
qq_36804678
qq_36804678   2017.01.05 15:54

图片说明

qq_36230119
qq_36230119   2017.01.05 18:18

我自己做的也不知道对不对

 package Test;

import java.util.Arrays;
import java.util.Scanner;

public class Demo {

    public static Demo demo = new Demo();
    public static int [] nArr = null;

    public static void main(String[] args) {
        System.out.println("___________开始_______________");
        Scanner scanner = new Scanner(System.in);
        String numbers = scanner.nextLine();
        scanner.close();
        String [] numberArr = numbers.split(",");
        nArr = new int[numberArr.length];
        for (int i = 0; i < numberArr.length; i++) {
            nArr[i] = Integer.valueOf(numberArr[i]);
        }
        Arrays.sort(nArr);
        //树的跟节点
        Node treeNode = demo.new Node();
        treeNode.parentNode=null;
        beTree(treeNode,nArr,nArr.length-1);
        System.out.println(treeNode);


        //计算获得根节点的值
        int result = getTreeNodeValue(treeNode);
        System.out.println(result);

        //输出表达式
        Node rightNode = null;
        //获得最右边的子节点
        rightNode = getRightNode(treeNode);
        System.out.println(rightNode);
        //变成表达式
        String str = beString(treeNode);
        System.out.println(str+"="+result);
        System.out.println("__________结束__________________");
    }


    private static String beString(Node treeNode) {
        if(treeNode.rightNode.isLeaf){
            return "("+treeNode.rightNode.value+treeNode.addOrSub+treeNode.leftNode.value+")";
        }else{
            if("-".equals(treeNode.addOrSub)){
                if(treeNode.leftNode.value > treeNode.rightNode.value){
                    return "("+treeNode.leftNode.value+treeNode.addOrSub+beString(treeNode.rightNode)+")";
                }else{
                    return "("+beString(treeNode.rightNode)+treeNode.addOrSub+treeNode.leftNode.value+")";
                }
            }
            return "("+beString(treeNode.rightNode)+treeNode.addOrSub+treeNode.leftNode.value+")";
        }
    }
    private static Node getRightNode(Node treeNode) {
        if(treeNode.rightNode.isLeaf)
            return treeNode.rightNode;
        else
            return getRightNode(treeNode.rightNode);
    }
    private static int getTreeNodeValue(Node treeNode) {
        //该节点为非叶子节点
        if(!treeNode.isLeaf){
            int add = getTreeNodeValue(treeNode.rightNode)+treeNode.leftNode.value;
            int sub = Math.abs(getTreeNodeValue(treeNode.rightNode)-treeNode.leftNode.value);

            if(treeNode.parentNode == null){
                return Math.abs(treeNode.leftNode.value - treeNode.rightNode.value);
            }

            int compareNumber = treeNode.parentNode.leftNode.value;

            if(Math.abs(add-compareNumber) > Math.abs(sub-compareNumber) ){
                treeNode.addOrSub = "-";
                treeNode.value = sub;
            }else{
                treeNode.addOrSub="+";
                treeNode.value = add;
            }

            return treeNode.value;
        }else{
            return treeNode.value;
        }
    }

    public class Node{
        //该节点自身值
        public int value;
        //该节点的左节点
        public Node leftNode;
        //该节点的右节点
        public Node rightNode;
        //该节点的父节点
        public Node parentNode;
        //是否为叶子节点
        public boolean isLeaf;
        //该节点对子节点进行的运算,默认为减
        public String addOrSub = "-";
        @Override
        public String toString() {
            String str = "";
            str += "[value=" + value;
            if(this.leftNode != null)
                str += "leftNodeValue="+leftNode.toString();
            if(this.rightNode != null)
                str += "rightNodeValue="+rightNode.toString();
            str+="]";
            return str;
        }

    }

    public static void beTree(Node treeNode,int [] nArr,int length){
        if(length > 1){
            //左节点
            treeNode.leftNode = demo.new Node();
            treeNode.leftNode.value = nArr[length];
            treeNode.leftNode.isLeaf = true;
            treeNode.leftNode.parentNode = treeNode;

            //右节点
            treeNode.rightNode = demo.new Node();
            beTree(treeNode.rightNode, nArr, length-1);
            treeNode.rightNode.parentNode = treeNode;
        }else{
            //左节点
            treeNode.leftNode = demo.new Node();
            treeNode.leftNode.value = nArr[1];
            treeNode.leftNode.isLeaf = true;

            //右节点
            treeNode.rightNode = demo.new Node();
            treeNode.rightNode.value = nArr[0];
            treeNode.rightNode.isLeaf = true;
        }
    }

}

这是跑出来的结果图片说明

qq_36804678
qq_36804678 回复从基本的安装开始: 您可以看下我下面放的我们老师的论文 有用C写的关于这个的关键代码
12 个月之前 回复
qq_36230119
qq_36230119 回复大二小菜鸟: 我想了一下,我这样做是错的,这样不行,这里面水满深的
12 个月之前 回复
qq_36804678
qq_36804678 回复从基本的安装开始:您好 我在VC++6.0上运行3个报错。我初学数据结构您可以把加了循环和校验没做,加个while,和正则的完整代码发给我吗 一定感谢您
12 个月之前 回复
qq_36230119
qq_36230119 循环和校验没做,加个while,和正则就好了
12 个月之前 回复
qq_36804678
qq_36804678   2017.01.05 15:54

图片说明
![图片说明](http://img.ask.csdn.net/upload/201701/05/1483602833_866292.png)<br>
图片说明

qq_36230119
qq_36230119   2017.01.06 01:08

重写了一遍,按照你给的资料

package test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Demo2 {
    public static Demo2 demo = new Demo2();
    public static Node rootNode = null;
    public static String result = null;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            System.out.println("------------------开始-----------------");
            System.out.println("请输入'1,2,3,4,'格式的字符,输入‘0’结束");
            String numbers = sc.nextLine();
            if("0".equals(numbers)){
                System.out.println("------------结束----------------------");
                break;
            }else{
                Pattern p = Pattern.compile("([\\d]+,)+");
                Matcher match = p.matcher(numbers);
                if(match.matches()){
                    //将字符串变为字符串数组
                    String [] strArr = numbers.split(",");
                    //将字符串数组变为int数组
                    int [] intArr = new int[strArr.length];
                    for (int i = 0; i < strArr.length; i++) {
                        intArr[i] = Integer.valueOf(strArr[i]);
                    }
                    //排序
                    Arrays.sort(intArr);
                    //将int数组变为叶子节点数组,并打印所有的叶子节点
                    Node [] leafNode = new Node[intArr.length];
                    for (int i = 0; i < leafNode.length; i++) {
                        leafNode[i] = demo.new Node();
                        leafNode[i].value = intArr[i];
                        leafNode[i].isLeaf = true;
                        System.out.println("第"+i+"个叶子,其值为"+leafNode[i].value);
                    }
                    //将叶子变为一颗树,递归实现
                    beTree(leafNode);
                    String last = null;
                    int length1 = 0;
                    int length2 = 0;
                    for (int i = 0; i < leafNode.length; i++) {
                        System.out.println(leafNode[i].isLeftOrRight + "____" + leafNode[i].value +"  "+leafNode[i].parentNode.value);
                        //递归判断该子节点的正负
                        sureSign(leafNode[i]);
                        System.out.println(leafNode[i].addOrSub);
                        //根据addOrSub的最后以为判断奇偶,确定其正负
                        last = leafNode[i].addOrSub.substring(leafNode[i].addOrSub.length()-1);
//                      System.out.println(last);
                        if("0".equals(last)){
                            leafNode[i].addOrSub = "+";
                            length1 ++;
                        }else{
                            leafNode[i].addOrSub = "-";
                            length2 ++;
                        }
                    }
                    //输出结果
                    int result = 0;
                    //所有符号为正的
                    Node [] node1 = new Node[length1];
                    Node [] node2 = new Node[length2];
                    length1 = 0;
                    length2 = 0;
                    for (int i = 0; i < leafNode.length; i++) {
                        if("+".equals(leafNode[i].addOrSub)){
                            node1[length1]=leafNode[i];
                            length1 ++;
                            result += leafNode[i].value;
                        }else{
                            node2[length2]=leafNode[i];
                            length2 ++;
                            result -= leafNode[i].value;
                        }
                    }
                    String str = "";
                    if(result > 0){
                        for (int i = 0; i < node1.length; i++) {
                            if(i == 0)
                                str += node1[i].value;
                            else
                                str += node1[i].addOrSub + node1[i].value;
                        }
                        for (int i = 0; i < node2.length; i++) {
                            str += node2[i].addOrSub + node2[i].value;
                        }
                        str += "="+result;
                    }else{
                        for (int i = 0; i < node2.length; i++) {
                            if(i == 0)
                                str += node2[i].value;
                            else
                                str += "+" + node2[i].value;
                        }
                        for (int i = 0; i < node1.length; i++) {
                                str += "-" + node1[i].value;
                        }
                        str += "="+Math.abs(result);
                    }
                    System.out.println(str);
                }else{
                    System.out.println("输入的字符串格式错误!!");
                    System.out.println("--------------结束-----------------");
                    continue;
                }
            }
            System.out.println("--------------结束-----------------");
        }   
        sc.close();
    }

    private static String sureSign(Node node) {
        if(! (node.parentNode == null)){
            if("left".equals(node.isLeftOrRight))
                node.addOrSub = "0" + sureSign(node.parentNode);
            else
                node.addOrSub = "1" + sureSign(node.parentNode);
            return node.addOrSub;
        }
        return "";
    }

    private static void beTree(Node[] leafNode) {
        //当还剩下超过两个节点时做递归
        if(leafNode.length > 2){
            Node newNode = demo.new Node();
            newNode.leftNode = leafNode[0];
            newNode.leftNode.parentNode = newNode;
            newNode.leftNode.isLeftOrRight = "left";
            newNode.rightNode = leafNode[1];
            newNode.rightNode.parentNode = newNode;
            newNode.rightNode.isLeftOrRight = "right";
            newNode.value = newNode.leftNode.value + newNode.rightNode.value;
            //变为新的数组
            Node [] newNodeArr = new Node[leafNode.length-1];
            for (int i = 0; i < leafNode.length-2; i++) {
                newNodeArr[i] = leafNode[i+2];
            }
            newNodeArr[newNodeArr.length-1] = newNode;
            //排序,传入比较规则
            Arrays.sort(newNodeArr, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return o1.value-o2.value;
                }
            });
            for (int i = 0; i < newNodeArr.length; i++) {
                System.out.print(newNodeArr[i].value+",");
            }
            System.out.println("");
            beTree(newNodeArr);
        }else{//当只剩下两个节点时
            Demo2.rootNode = demo.new Node();
            Demo2.rootNode.leftNode = leafNode[0];
            Demo2.rootNode.leftNode.parentNode = Demo2.rootNode;
            Demo2.rootNode.leftNode.isLeftOrRight = "left";
            Demo2.rootNode.rightNode = leafNode[1];
            Demo2.rootNode.rightNode.parentNode = Demo2.rootNode;
            Demo2.rootNode.rightNode.isLeftOrRight = "right";
            Demo2.rootNode.value = rootNode.rightNode.value + rootNode.leftNode.value;
        }
    }

    //树节点
    public class Node{
        public int value;//节点自身值
        public Node leftNode;//该节点的左节点
        public Node rightNode;//该节点的右节点
        public Node parentNode;//该节点的父节点
        public String isLeftOrRight;//该子节点为左还是右
        public boolean isLeaf;//该节点是否为叶子节点
        public String addOrSub = "";//该节点对其子节点进行的操作
    }
}

qq_36230119
qq_36230119   2017.01.06 01:09

图片说明

qq_36804678
qq_36804678 谢谢您辛苦了 可是根据你上面截图输入的1,2,3,4,5,6,6,7,8这几个数相加减结果最小 且中间结果和最后结果不能为负应该是(8-7)+(6-6)+(5-4)+(3-2)+1=4啊 不是你上面那样啊
12 个月之前 回复
iamhycljc
iamhycljc   2017.01.06 10:01

非得用哈夫曼数吗?
如果用简单的排序,不是挺简单的吗?
先从大大小排序,然后最大的数减去次大的数,得到的值,再与剩下的数进行降序排序。
然后依次类推,就可以得到最小值了,而且保证不出现负数啊。

21,20,5,1
第一轮,21-20=1
降序5,1,1

第二轮,5-1=4
降序4,1

第三轮,4-1=3得到答案。

qq_36804678
qq_36804678 要求只能用哈夫曼输 啊
12 个月之前 回复
共12条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!