根据哈夫曼树的原理求n个自然数相加减后结果最小（中间结果、最后结果不能负）。
根据哈夫曼树的原理求n个自然数相加减后结果最小（中间结果、最后结果不能负）。
问题描述：输入n个自然数，输出这n个数只做加减运算后得到的结果值最小，写出输出结果。
要求：
1）可以循环测试，可以选择退出程序；
2）打印这n个自然数进行加减的表达式（注意：中间结果不能为负）；
例如：输入1,2,3，最后打印出3-2-1=0
3）输入数据要进行合法性检查；
说说看法吧 哈弗曼生成算法 是选取最小的两个点 组合成新结点 新结点的值为 两个原结点的和
所以我觉得要使最后结果最小的话，只要用这n个树组成一个哈弗曼树 （如算法为右子树较大），然后取根节点的右子树减去左子树应该就是结果了。
如果我的想法不对的话，就说出来让我再想想
额我写了个算法 发现自己这么想是错的
然后我又想了一个 每次取最大的两个做减法 循环直到就剩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;
}
<br>
图片说明](https://img-ask.csdn.net/upload/201701/05/1483602817_56157.png)
我自己做的也不知道对不对
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;
}
}
}
这是跑出来的结果
重写了一遍，按照你给的资料
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 = "";//该节点对其子节点进行的操作
}
}
非得用哈夫曼数吗？
如果用简单的排序，不是挺简单的吗？
先从大大小排序，然后最大的数减去次大的数，得到的值，再与剩下的数进行降序排序。
然后依次类推，就可以得到最小值了，而且保证不出现负数啊。
21,20,5，1
第一轮，21-20=1
降序5,1,1
第二轮，5-1=4
降序4,1
第三轮，4-1=3得到答案。
package Test;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.swing.tree.TreeNode;
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数组
Integer [] intArr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
intArr[i] = Integer.valueOf(strArr[i]);
}
//排序
Arrays.sort(intArr,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
//将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);
//输出结果
int result = Demo2.rootNode.value;
System.out.println("---------结果值-------------");
System.out.println(result);
String str = "";
boolean flag = true;
//设置节点的符号
for (int i = 0; i < leafNode.length; i++) {
//获取该节点的1的个数
int count = 0;
count = getCount(leafNode[i]);
if(count%2 == 0){
leafNode[i].addOrSub = "+";
}else{
leafNode[i].addOrSub = "-";
}
if("+".equals(leafNode[i].addOrSub)){
if(flag){
str += leafNode[i].value;
flag = false;
}else
str += leafNode[i].addOrSub + leafNode[i].value;
}
}
for (int i = 0; i < leafNode.length; i++) {
if("-".equals(leafNode[i].addOrSub)){
str += leafNode[i].addOrSub + leafNode[i].value;
}
}
str+="="+result;
System.out.println(str);
}else{
System.out.println("输入的字符串格式错误!!");
System.out.println("--------------结束-----------------");
continue;
}
}
System.out.println("--------------结束-----------------");
}
sc.close();
}
private static int getCount(Node node) {
if(node.parentNode != null){
if("left".equals(node.isLeftOrRight)){
return 1+getCount(node.parentNode);
}else
return getCount(node.parentNode);
}else{
return 0;
}
}
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 o2.value-o1.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.leftNode.value - rootNode.rightNode.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 = "";//该节点对其子节点进行的操作
}
}
这还不对我也没辙了！挣点C币真难
