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 评论里我不知道怎么上传照片,我在回答里上传了,您可以看一下,出错的那组数据最小值是正确的,但是加减顺序是错误的
一年多之前 回复
qq_36804678
qq_36804678 我看了您运行的结果没有问题,我自己运行到第三组数据出错了(见下图),不过还是很感谢您,采纳了
一年多之前 回复
qq_36804678
qq_36804678 这次没有问题!再多的感谢之词抵不上我果断的采纳您的方法!
一年多之前 回复
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写的关键代码 在他的论文里 我待会上传到这里
一年多之前 回复
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写的关于这个的关键代码
一年多之前 回复
qq_36230119
qq_36230119 回复大二小菜鸟: 我想了一下,我这样做是错的,这样不行,这里面水满深的
一年多之前 回复
qq_36804678
qq_36804678 回复从基本的安装开始:您好 我在VC++6.0上运行3个报错。我初学数据结构您可以把加了循环和校验没做,加个while,和正则的完整代码发给我吗 一定感谢您
一年多之前 回复
qq_36230119
qq_36230119 循环和校验没做,加个while,和正则就好了
一年多之前 回复
qq_36804678
qq_36804678   2017.01.05 15:54

图片说明
![图片说明](https://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啊 不是你上面那样啊
一年多之前 回复
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条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
8.求一元二次方程的根
求一元二次方程的根 本题目要求一元二次方程的根,结果保留2位小数。 输入格式: 输入在一行中给出3个浮点系数a、b、c,中间用空格分开。 输出格式: 根据系数情况,输出不同结果: 1)如果方程有两个不相等的实数根,则每行输出一个根,先大后小; 2)如果方程有两个不相等复数根,则每行按照格式“实部+虚部i”输出一个根,先输出虚部为正的,后输出虚部为负的;
找出n个自然数中(1,2,3,……,n)中取r个数的组合。eg:n=5,r=3 时组合数为10
/*方法一:#include&amp;lt;stdio.h&amp;gt;int main(){ int n,i,j,k,t; scanf(&quot;%d&quot;,&amp;amp;n); for(i=1;i&amp;lt;=n;i++) for(j=1;j&amp;lt;=n;j++) for(k=1;k&amp;lt;=n;k++) if(i&amp;lt;j&amp;amp;&amp;amp;j&amp;lt;k) { t=t+1; printf(...
算法题: 求一个整数数组中,通过元素加减运算得到指定结果的所有运算过程. 例如【5,4,6,7,1】= 9 ?
题目: 给定一个整数数组int[] a (a.length > 1),和一个整数值 m,试输出所有运算结果等于m的运算过程。可使用的运算方式只有加法和减法。数组元素最多参与一次运算。例如,给定数组【5,4,6,7,1】和整数9,输出运算结果为9的运算过程如下: +5+4=9 +5+4+6-7+1=9 +5+4-6+7-1=9 +5-4+7+1=9 +4+6-1=9 -4+6+7=9
输入一个自然数n,求 ,同时统计结果中有多少个0。
输入一个自然数n,求 ,同时统计结果中有多少个0。
C语言 输入一个自然数n,求 ,同时统计结果中有多少个0。
输入一个自然数n,求 ,同时统计结果中有多少个0。
根据后续和中序遍历输出先序遍历
7-1 根据后序和中序遍历输出先序遍历(25 分) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出格式: 在一行中输出Preorder:以及该树的先
大数阶乘并统计结果中0的个数
输入一个自然数n,求,同时统计结果中有多少个0。
关于无符号数的减法为负值
#include using namespace std; int main() { unsigned int u1 = 42, u2 = 10; cout << u1 - u2 << endl; cout << u2 - u1 << endl; return 0; } 上面的输出结果为: 32 4294967264 显然下面的结果是-32与16位整数取模后的值。 这样理解:
tyvj 1045 最大的算式 在n个数字中加k个乘号和n-k-1个加号,使最后结果最大
<br /> Fromsilence☆最大的算式        输入格式 Input Format   输入文件共有二行,第一行为两个有空格隔开的整数,表示N和K,其中(2<=N<=15, 0<=K<=N-1)。第二行为 N个用空格隔开的数字(每个数字在0到9之间)。        输出格式 Output Format   输出文件仅一行包含一个整数,表示要求的最大的结果<br />最后的结果<=maxlongint       样例输入 Sample Input    5 2 1 2 3
NYOJ 组合数问题
组合数 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。 输入输入n、r。输出按特定顺序输出所有组合。 特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。样例输入 5 3 样例输出 543 542 541 532 531 521 432 4