|
一：汉诺塔问题：
一道经典问题了，我在其他博主那里找解题思路。给了我很大帮助。
博客地址:(3条消息) 汉诺塔问题——递归（时隔9个月，终于懂了）_Patience-CSDN博客_汉诺塔递归
汉诺塔问题是：汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
package extra;
public class Hanois {
public static int steps = 0;
public void move(int id,char hole1,char hole2) {
System.out.println(steps++ + ": plate "+id+" moves from "+hole1+ " to "+hole2);
}
//n个在x上的盘子通过y移动到z
public void Hanoi(int n,char starthole,char inhole,char endhole) {//从左到右分别是盘子数，从哪个杆开始，中间杆，到哪个杆。
if(n==0) return;
Hanoi(n-1,starthole,endhole,inhole);
move(n,starthole,endhole);
Hanoi(n-1,inhole,starthole,endhole);
}
public static void main(String[] args) {
Hanois ho = new Hanois();
char a = 'a';
char b = 'b';
char c = 'c';
ho.Hanoi(5,a,b,c);
}
}
做完真的感觉挺神奇的，原本以为会用到很多代码，结果核心代码就那么几行，不过换做是我自己想肯定想不出来。
通过其他博主所描述的，比如你要移动64个盘，就将前面63个看作整体。这种看作整体的思想仔细想想原来也接触过，比如说就在c语言反转链表时，当使用递归的方法时，就会有化作整体的思想。
递归的关键有两个：
（1）递归的结束条件（不写会死循环，TLE）
（2）递归最后一层和其他有关系的层的关系怎样用非递归函数来表达
比如：斐波纳契亚数列，（1）当n==1和n==2的时候f(n)=1，这就是递归的终止条件。给了终止条件，计算机才能进行求解子问题并回溯，最终求出f(n)
?
关于关键中的第(2)点，这里就体现在了move函数上面，而move就表现出了和其他层的关系，并且是非递归函数。
要明白最后一步的前一步是什么，明白的话基本就赢了。
那么这一步的前一步是什么？
记住了，在求解f(n, other variables)的时候，我们直接默认f(n - 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。
我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想
那么，前一步也就是f(n - 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上，over
二：哈夫曼编码：
哈夫曼节点类代码如下：
package huffmanTreeMyself;
public class Node {
public Node lChild;
public Node rChild;
public String code;// 节点的哈夫曼编码
public int codeSize;// 节点哈夫曼编码的长度
public String data;// 节点的数据
public int count;// 节点的权值
public String config = "";//用来标记节点是左节点或者是右节点。
//哈夫曼编码说白了就是用左0右1来进行表示。
public Node() {
}
public Node(String data, int count) {
this.data = data;
this.count = count;
}
public Node(int count, Node lChild, Node rChild) {
this.count = count;
this.lChild = lChild;
this.rChild = rChild;
}
public Node(String data, int count, Node lChild, Node rChild) {
this.data = data;
this.count = count;
this.lChild = lChild;
this.rChild = rChild;
}
public static void main(String[] args) {
}
}
以下是huffman编码的正式代码,期间用到了图的键值对存储，最终可以获得每个节点的Huffman编码。
哦，忘了说，这里最终输出出来的话是节点本身的值(不是权值)带上哈夫曼编码。
package huffmanTreeMyself;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
public class Huffman {
String newstr;// 经过编码后形成的huffman编码字符串
private String readtext;// 压缩前的字符串。
private Node root;// 哈夫曼二叉树的根节点
// private boolean flag;// 最新的字符是否已经存在的标签
private ArrayList<String> charList;// 存储不同字符的队列 相同字符存在同一位置
private ArrayList<Node> NodeList;// 存储节点的队列
public void CreateHuffman(String strs) {
// 1：找权值。
this.readtext = strs;
charList = new ArrayList<>();
NodeList = new ArrayList<>();
boolean flag;// flag标识符标识唯一存在的情况,true表示当前唯一存在
for (int i = 0; i < strs.length(); i++) {
char ch = strs.charAt(i);
flag = true;
for (int j = 0; j < charList.size(); j++) {
if (charList.get(j).charAt(0) == ch) {
flag = false;
String temp = charList.get(j) + ch;
charList.set(j, temp);
break;
}
}
if (flag) {// 这里if一定要放在for循环外，不然根本无法触发添加的操作，会一直是0的状态。
String temp = "" + ch;
charList.add(charList.size(), temp);// 添加到指定位置
}
}
// 接下来将产生哈夫曼树的节点。连接huffman树节点的操作在下一步进行。
for (int i = 0; i < charList.size(); i++) {
String temp = charList.get(i).charAt(0) + "";
Node node = new Node(temp, charList.get(i).length());// string int
NodeList.add(i, node);
}
// 接下来对Huffman树节点进行连接。(当然要使用huffman那里的编码方式)
// 此外，需要写一个排序方法，来对权值进行排序。（这里使用冒泡排序）
while (NodeList.size() > 1) {
NodeSort(NodeList);
Node temp1 = NodeList.remove(0);
Node temp2 = NodeList.remove(0);
int value = temp1.count + temp2.count;
temp1.config = "0";
temp2.config = "1";//左0右1。
Node temp3 = new Node(value, temp1, temp2);
NodeList.add(temp3);// 将temp3置于首位，因为之后还会排序
}
root = NodeList.get(0);// 需要root这个载体去承接已经创建好的哈夫曼树。(非常重要要)
}
public void NodeSort(ArrayList<Node> NodeList) {// 这里是从小到大排序
for (int i = 0; i < NodeList.size() - 1; i++) {
for (int j = i + 1; j < NodeList.size(); j++) {
Node temp;
if (NodeList.get(i).count > NodeList.get(j).count) {
temp = NodeList.get(i);
NodeList.set(i, NodeList.get(j));
NodeList.set(j, temp);
}
}
}
}
public void show(ArrayList<Node> NodeList) {
for(int i = 0;i<NodeList.size();i++) {
System.out.print(NodeList.get(i).count+" ");
}
}
public void inOrderReverse(Node node) {
if (node.lChild != null) {
inOrderReverse(node.lChild);
}
System.out.print(" " + node.count);
if (node.rChild != null) {
inOrderReverse(node.rChild);
}
}
public void inOrderReverse() {
inOrderReverse(root);
}
public String ReadFromFiles(File location) {
FileInputStream fis = null;
try {//使用字节流进行对文本字符进行读取。
fis =new FileInputStream(location);
byte[] bytes = new byte[1024*1024];//1M每次
readtext = "";
int count = 0;
while((count = fis.read(bytes))!=-1) {
readtext += new String(bytes,0,count);
}
return readtext;
} catch (IOException e) {
e.printStackTrace();
}finally {
if(fis!=null) {
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return null;
}//调用此方法来读取文件中的字符串究竟是多少。
//以下方法是获得的每个节点的哈夫曼编码。
private void GetHuffmanCodes(Node node,String goal,HashMap<String, String> hfmMap) {//goal是要查找的节点
if(node!=null) {
goal += node.config;
if(node.lChild==null&&node.rChild==null) {
hfmMap.put(node.data,goal);
}
}
if(node.lChild!=null) {
GetHuffmanCodes(node.lChild,goal,hfmMap);
}
if(node.rChild!=null) {
GetHuffmanCodes(node.rChild,goal,hfmMap);
}
// if(node.data.equals(goal)==true) {//包含了树中为空的节点，不能包含。。。。。
// return newstr;
// }else {
// if(node.lChild!=null) {
// GetHuffmanCodes(node.lChild,goal);
// }
// else if(node.rChild!=null) {
// GetHuffmanCodes(node.rChild,goal);
// }
// }
// return null;
}
public void GetHuffmanCodes(String goal) {
HashMap<String,String> hfmMap = new HashMap<String,String>();
GetHuffmanCodes(root.lChild,goal,hfmMap);//利用图来存储键值对，最后取出需要的键值对即可。
System.out.println(hfmMap.get("a"));
}//最终方法输出获取的哈夫曼编码。
public static void main(String[] args) {
Huffman huf = new Huffman();
// huf.CreateHuffman("sdfassvvdfgsfdfsdfs");
// huf.inOrderReverse();//我这个也是对的，带权路径长度是一样的。
File inputtext = new File("D:\\filetest\\temp.txt");
//首先，对字符串文件内容进行读取。使用字节流或字符流都可以，字符流应该要简单一点。
huf.CreateHuffman(huf.ReadFromFiles(inputtext));
huf.inOrderReverse();
System.out.println("");
huf.GetHuffmanCodes("a");
}
}
4 8 2 4 1 2 1 19 5 11 6
a0110
|