HDU/HDOJ 1053 Entropy (Huffman树)

昨晚做了一晚上,可是状态不好,今天下午去踢了会球,发挥的不错,晚上做题心情也好,哈哈,终于搞定了。

这两天把Huffman看了好几遍,看到了三种方法来处理Huffman这个数据结构:

1.STL中的priority_queue

2.链表表示Huffman Node的parent, lchild, rchild.

3.数组表示Huffman Node的parent, lchild, rchild.

关于数组控制Huffman结构的,我在http://www.cppleyuan.com/viewthread.php?tid=713 写过,

另外,关于优先级队列的,我会在总结算法导论之贪心算法中讲出。

这里我用的是最普遍的链表形式。

这里有一点不好控制:

如何找出当前最小的两个结点?

我给Huffman Node中增加了一个控制变量flag,默认为-1,表示未被适用,如果选出此点,则将flag设置为1,表示此结点已经是某一个子树的结点,这样,就不会再重复使用该点。

另外,注意Huffman树的叶结点有N个,则总结点数是2*N-1个,

所以我设置一个数组保存Huffman Node,则0~N-1为叶结点,2*N-2是根结点。这样一直从每个叶结点返回到根结点,求出当前叶结点的层数。

另外还有一点要注意:单独考虑只有

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <string>
#include <iostream>
#include <iomanip>
const int INF = 999999;
using namespace std;
 
typedef struct Node{
    int flag;   // 记录是否被用过
    int weight;
    //int level;
    char data;
    Node *lchild, *rchild, *parent;
}Node;
 
Node Huffman[1000];
 
int rec[27];
string ss;
Node *s1, *s2;
 
 
Node *select(int k);
int visit(int k);
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> ss && ss!="END")
    {
        // 初始化
        memset(rec, 0, sizeof(rec));
        int k = 0;  // 计数,Huffman Node的个数
        for(int i=0; i<1000; ++i)
        {
            Huffman[i].data = '#';
            Huffman[i].flag = -1;
            Huffman[i].lchild = Huffman[i].rchild = Huffman[i].parent = NULL;
            Huffman[i].weight = 0;
        }
        // 输入
        for(int i=0; i<ss.size(); ++i)
            if(ss[i] == '_')
                rec[26]++;
            else
                rec[ss[i]-'A']++;
 
 
        for(int i=0; i<27; ++i)
            if(rec[i])
            {
                if(i == 26)
                    Huffman[k].data = '_';
                else
                    Huffman[k].data = i+'A';
                //Huffman[k].flag = -1;
                Huffman[k].weight = rec[i];
                //Huffman[k].lchild = Huffman[k].rchild = Huffman[k].parent = NULL;
                ++k;
            }
        if(k == 1)
        {
            cout << ss.size()*8 << " " << ss.size() << " 8.0\n";
            continue;
        }
 
        //cout << "k = " << k << endl;
        // 生成其他结点
        for(int i=k; i<=2*k-2; ++i)
        {
            s1 = select(i);
            s2 = select(i);
            Huffman[i].lchild = s1;
            Huffman[i].rchild = s2;
            Huffman[i].parent = NULL;//
            Huffman[i].flag = -1;//
            Huffman[i].weight = s1->weight + s2->weight;
            Huffman[i].data = '#';
            //cout << "Node " << k << ": " << Huffman[i].data << " " << Huffman[i].weight << endl;
            s1->parent = &Huffman[i];
            s2->parent = &Huffman[i];
        }
 
        int len1 = 8 * ss.size();
        int len2 = visit(k);
        cout << len1 << " " << len2 << " " << setiosflags( ios::fixed | ios::showpoint) << setprecision(1) << (double)len1/len2 << endl;
 
 
    }
}
 
Node *select(int k)
{
    Node *t = &Huffman[0];
    int _max = INF;
    for(int i=0; i<k; ++i)
    {
        if(Huffman[i].flag == -1 && Huffman[i].weight < _max)
        {
            _max = Huffman[i].weight;
            t = &Huffman[i];
        }
    }
    t->flag = 1;
    return t;
}
 
int visit(int k)
{
    int sum = 0;
    Node *t = &Huffman[0];
    int level;
    for(int i=0; i<k; ++i)
    {
        level = 0;
        t = &Huffman[i];
        while(t->parent != NULL)
        {
            level ++;
            t = t->parent;
        }
        sum += level*Huffman[i].weight;
 
    }
    return sum;
}

谈一下ACM的入门书籍及方法

首先说一下,ACM的入门方法多种多样,大部分人还是跟着学校一起参加集训,所以我这里主要是想对那些准备ACM入门的业余的朋友谈的。

入门书籍

首先推荐一些ACM的书籍:
(以下我都会给出在当当网的页面,方便大家直接购买,以下排名不分先后)

  • 1.《程序设计导引及在线实践》

http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub
这是我的第一本入门书,这本书是配套北大的百炼习题,注意不是POJ,貌似是北大内部测试用的,不过也是对外开放的,去年好像百炼变化过,所以不知道这本书还适不适合那个新的百炼系统。

  • 2.《算法竞赛入门经典》

http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub
这本书没话说,刘汝佳的白书,经典的算法入门书籍。强烈推荐!

  • 3.《算法艺术与信息学竞赛》

http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub
刘汝佳的黑书,难度较深,题目基本来至Uva,我是看了前面以部分,后面就没咋看了。。。

  • 4.《算法导论》

http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub
经典的书籍是不需要解释的。
这是我曾经上传过的英文版CHM算法导论,可以下载了看看:
http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA
我最近也在写算法导论的读书总结,欢迎大家探讨:
http://www.wutianqi.com/?p=2403

  • 5.《编程之美》

http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub
挺有意思的,不能作为一个算法的全面书籍,而是作为一本拓宽思维的书籍,有兴趣的建议要看看。

  • 6.《计算机程序设计艺术》

http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub
有好几卷的,只给出一卷的连接,而且网上版本很多,大家可以自行选择。
这个还没看,关键是没时间了,准备考研完了就趁着假期看完。

  • 7.《组合数学》

http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix
鸽巢原理,博弈,容斥原理,Catalan数等都属于这个范畴的,建议看看。

  • 8.《数据结构(C语言版)》严蔚敏

http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub
数据结构,这个必须得学好啊~~~

  • 9.《数据结构与算法分析C++描述(第三版)》

http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub
有时间可以看看,C++ Template写的,可以顺便巩固下template。

 

以下基本都没看过,不过貌似很有名,给出书名和连接:

  • 10.《世界大学生程序设计竞赛(ACM/ICPC)高级教程.第一册.程序设计中常用的计算思维方式》

http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub
这本我其实买了,但是还没有时间看。

  • 11.《国际大学生程序设计竞赛指南—ACM程序设计》

http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub

  • 12.《国际大学生程序设计竞赛例题解(三)图论、动态规划算法、综合题专集》

http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub
这个好像也有好几册,每一册都是单独讲一个方面的。

  • 13.《挑战编程:程序设计竞赛训练手册》

http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub

(作者:Tanky Woo, 个人博客:http://www.wutianqi.com ,C++/算法论坛:http://www.cppleyuan.com/ 。转载请注明个人及原文连接,谢谢合作)

入门方法
这么多书,不可能全部都看的,我觉得前10本,也就是我看过的,都还不错,大家可以看看。
另外,我个人推荐ACM可以这样入门(以下用到了上面书籍前面的序号):(当然,如果学校有专门培训的,则跟着学校来更好)

1.数据结构是基础,建议先把8号严蔚敏老师的《数据结构》好好看1~2遍,代码都手动敲一敲。
2.再看2号刘汝佳的白书
3.去年暑假(2010.7~2010.9月),我曾经给我的论坛(C++奋斗乐园:http://www.cppleyuan.com/)搞过一次ACM专题训练,训练题全部来至HDOJ,当时我是由易到难,每天选择一个专题,在HDOJ上找3~4题,然后在论坛给出题目,大家可以到HDOJ去提交,然后贴到论坛供其他朋友参考。板块是:http://www.cppleyuan.com/forumdisplay.php?fid=40,前面都是看书,这里就建议大家开始实战了,在论坛里一共除了200多题,大家一定要做!
4.有了一定的基础,就可以再一边进行深入(看书),一边做题了。这个时候神马《算法导论》,《计算机程序设计艺术》等等都可以看看。
5.到了这个阶段,没啥说的了,自由学习~~~

最后说一句:算法魅力,无与伦比,欢迎大家来到ACM的世界!加油!

(作者:Tanky Woo, 个人博客:http://www.wutianqi.com ,C++/算法论坛:http://www.cppleyuan.com/ 。转载请注明个人及原文连接,谢谢合作)

《算法导论》学习总结 — 19.第15章 动态规划(4) 案例之LCS

建议先看看前言:http://www.wutianqi.com/?p=2298

这个案例也比较简单,最长公共子序列(LCS),网上的分析非常多,给力啊!

按照上一篇总结所说的,找状态转移方程:

15_5

所以按照所给方程,写代码的工作就非常非常简单轻松了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法导论》15.4 最长公共自序列(LCS)
*/
 
#include <iostream>
using namespace std;
 
char b[20][20];
int c[20][20];
 
char x[20], y[20];
 
void LCS()
{
	int m = strlen(x+1);
	int n = strlen(y+1);
 
	for(int i=1; i<=m; ++i)
		c[i][0] = 0;
	for(int j=1; j<=n; ++j)
		c[0][j] = 0;
 
	for(int i=1; i<=m; ++i)
		for(int j=1; j<=n; ++j)
		{
			if(x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = '\\';    // 注意这里第一个\\是转移字符,代表\
			}
			else if(c[i-1][j] >= c[i][j-1])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = '|';
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = '-';
			}
		}
}
 
void printLCS(int i, int j)
{
	if(i == 0 || j == 0)
		return;
	if(b[i][j] == '\\')
	{
		printLCS(i-1, j-1);
		cout << x[i] << " ";
	}
	else if(b[i][j] == '|')
		printLCS(i-1, j);
	else
		printLCS(i, j-1);
}
 
int main()
{
	cout << "Input the array A:\n";
	cin >> x+1;
	cout << "Input the array B:\n";
	cin >> y+1;
	LCS();
	printLCS(strlen(x+1), strlen(y+1));
}

看书上图15-6的结果图:

15_6

又是一个给力的图,建议自己按照程序把这个图画出来.

另外,说到LCS,不得不说的是LIS(最长上升子序列),也是一个DP,我曾经总结过:

http://www.wutianqi.com/?p=1850

Tanky Woo 标签:

《算法导论》学习总结 — 18.第15章 动态规划(3) 基础入门2

建议先看看前言:http://www.wutianqi.com/?p=2298

这一节可以看到《算法导论》学习总结 — 16.第15章 动态规划(1) 基本入门的补充。

采用动态规划的最优化问题的两个要素:最优子结构重叠子问题

先看看最优子结构:

在第17篇总结时,装配线调度问题中,已经设计到了最优子结构,证明最优子结构问题可以用书上说的“剪贴技术”,即假设存在更优的解,来反正最优解矛盾。

再看看重叠子问题:

当一个递归算法不断的调用同一个问题时,我们说该最有问题包含“重叠子问题”。

上面这句话不好理解?

看看下面这个比较:

递归算法:自顶而下,对在递归树中重复出现的每个子问题都要重复解一次。

动态规划:自下而上,对每个只解一次。

结合第16篇总结的三角形求值例子,可以看得到,自下而上导致每个子问题只求解一次。

 

以上理论性有点强,我最开始学DP看的是HDOJ的课件,有兴趣的可以去看看。

在那里面,主要讲到了是找状态转移方程,在第16篇的三角形求值例子和第17篇的装配线调度例子,那些递归公式都是状态转移方程。

下面这段话好好理解:

——————————————————————–

动态规划的几个概念:
阶段:据空间顺序或时间顺序对问题的求解划分阶段。
状态:描述事物的性质,不同事物有不同的性质,因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。
决策:根据题意要求,对每个阶段所做出的某种选择性操作。
状态转移方程:用数学公式描述与阶段相关的状态间的演变规律。

动态规划是运筹学的一个重要分支,是解决多阶段决策过程最优化的一种方法。

所谓多阶段决策过程,是将所研究的过程划分为若干个相互联系的阶段,在求解时,对每一个阶段都要做出决策,前一个决策确定以后,常常会影响下一个阶段的决策。

动态规划所依据的是“最优性原理”。
“最优性原理”可陈述为:不论初始状态和第一步决策是什么,余下的决策相对于前一次决策所产生的新状态,构成一个最优决策序列。

最优决策序列的子序列,一定是局部最优决策子序列。
包含有非局部最优的决策子序列,一定不是最优决策序列。

动态规划的指导思想是:

在做每一步决策时,列出各种可能的局部解,之后依据某种判定条件,舍弃那些肯定不能得到最优解的局部解。这样,在每一步都经过筛选,以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝(从搜索角度看),效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优,不能保证全局最优,因为有些问题不符合最优性原理。

——————————————————————–

 

看见有人说递归就是DFS,而DP就是BFS,感觉有那么一点意思,对于DP,就是从底层一层层的计算,然后在当层中选取最优,逐层最优以至总体最优。

 

其实这个还是多做一些题就好了(⊙o⊙),大家别认为我是做题控,其实说实在话,看N遍不如做一题,说白了,算法数学本一家,算法就是数学,走过高中的,都知道数学题得多做,尤其压轴题,看N遍不如做一遍,这个也是一样做几题就知道DP是神马东东了!

 

Tanky Woo 标签:

《算法导论》学习总结 — 17.第15章 动态规划(2) 案例之装配线调度

原来打算把算法导论在7月份前搞定,现在已经过去一个多月了,才只看到第15章,后面也只零散看了一些,不知道假期前能否看完。。。够呛啊,马上要期末考试了,上学期GPA不到2,被学位警告了,虽说以后不学这个专业了,但起码成绩单上也不能有挂科是吧。。。要是平时一点不看,考前靠春哥,曾哥,关公哥都不行啊。。。这进度,郁闷!

尽力吧!

顺便还是说两句话:

1.有些书上分析的相当好了,我不想做画蛇添足的人,所以有的地方我会适当省略,当然也不是说我总结的地方就是书上讲的不好的地方,只是没人有一套自己的理解方式,我用自己的话去总结了,当时也就是最适合我的知识!所以,建议大家多写一些算法总结,你会体会到好处的!

2.而且我这个的性质是总结,不是对一个算法的具体讲解,所以不先看书,大家应该读不懂的,就比如下面,题目我就没有贴出来,大家不看数,肯定就读不懂,我的目的是大家看完书后,谢谢总结,或者看看别人写的总结,说不定可以发现自己哪些地方理解错了,哪些地方不理解,或是哪些地方值得探讨。

建议先看看前言:http://www.wutianqi.com/?p=2298

这一次主要是分析15.1节的例子—装配线调度问题。

题目有点长,首先得把题目读懂。

这个例子书上花了6面纸的篇幅来详细分析,由此可见其重要性。

谈到DP,不得不说的就是暴力法,大家都知道,如果用暴力解决类似问题,一般时间复杂度都是非常非常的高,这个时候救世主DP就出来了,DP以避免了许多重复的计算,而大大降低了时间复杂度。

按照书上的四个步骤,我在这里提取一些重点,建议还是把P194~196这四步完整步骤看书上的分析。只有慢慢品味,你才会发现《算法导论》的美。

步骤一

分析问题,比如一个底盘要到达S[1][j],则有两种情况,第一种是从S[1][j-1]到S[1][j],第二种是从S[2][j-1]到S[1][j]。找出这两者所花时间的最小,则就是S[1][j]所需时间的最小。

这就是有局部最优解求全局最优解。也就是说,一个问题的最优解包含了子问题的一个最优解。我们称这个性质为最优子结构。这是是否可以应用DP的标志之一。

步骤二

找出这个递归关系,由步骤一可以得到这个递归关系:

15_2

步骤三

因为递归的关系,一般总是可以转换为非递归的算法。

由已知量f1[1], f2[1]逐步推出未知量,推啊推,推啊推,最后就推到结果了~~~~

步骤四

再由已知结果返回求路径。

这一节最给力的就是这个例子以及相应的

15_3

拿起笔,用书上给出的例子,分析这个图!

以下是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法导论》15.1 装配线调度
*/
#include <iostream>
using namespace std;
 
int n;                 // 一个装配线上有n个装配站
int e1, e2;            // 进入装配线1,2需要的时间
int x1, x2;            // 离开装配线1,2需要的时间
int t[3][100];         // t[1][j]表示底盘从S[1][j]移动到S[2][j+1]所需时间,同理t[2][j]
int a[3][100];         // a[1][j]表示在装配站S[1][j]所需时间
int f1[100], f2[100];  // f1[j], f2[j]分别表示在第一/第二条装配线上第j个装配站的最优解
int ln1[100], ln2[100];// ln1[j]记录第一条装配线上,最优解时第j个装配站的前一个装配站是第一条线还是第二条线上
int f, ln;             // 最优解是,f代表最小花费时间,ln表示最后出来时是从装配线1还是装配线2
 
void DP()
{
	f1[1] = e1 + a[1][1];
	f2[1] = e2 + a[2][1];
	for(int j=2; j<=n; ++j)
	{
		// 处理第一条装配线的最优子结构
		if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
		{
			f1[j] = f1[j-1] + a[1][j];
			ln1[j] = 1;
		}
		else
		{
			f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
			ln1[j] = 2;
		}
		// 处理第二条装配线的最优子结构
		if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
		{
			f2[j] = f2[j-1] + a[2][j];
			ln2[j] = 2;
		}
		else
		{
			f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
			ln2[j] = 1;
		}
	}
	if(f1[n] + x1 <= f2[n] + x2)
	{
		f = f1[n] + x1;
		ln = 1;
	}
	else
	{
		f = f2[n] + x2;
		ln = 2;
	}
}
 
void PrintStation()
{
	int i= ln;
	cout << "line " << i << ", station " << n << endl;
	for(int j=n; j>=2; --j)
	{
		if(i == 1)
			i = ln1[j];
		else
			i = ln2[j];
		cout << "line " << i << ", station " << j-1 << endl;
	}
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	cout << "输入装配站的个数: ";
	cin >> n;
	cout << "输入进入装配线1,2所需的时间e1, e2 :";
	cin >> e1 >> e2;
	cout << "输入离开装配线1, 2所需的时间x1, x2: ";
	cin >> x1 >> x2;
	cout << "输入装配线1上各站加工所需时间a[1][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[1][i];
	cout << "输入装配线2上各站加工所需时间a[2][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[2][i];
	cout << "输入装配线1上的站到装配线2上的站所需时间t[1][j]: ";
	//注意这里是i<n,不是i<=n
	for(int i=1; i<n; ++i)
		cin >> t[1][i];
	cout << "输入装配线2上的站到装配线1上的站所需时间t[2][j]: ";
	for(int i=1; i<n; ++i)
		cin >> t[2][i];
	DP();
	cout << "最快需要时间: " << f << endl;
	cout << "路线是: " << endl;
	PrintStation();
	cout << endl;
}

最后还是要感叹一下,《算法导论》讲的真是棒极了,希望大家能静下心把这一章节好好看看。