09年买的这本书，不过先开始一直没怎么用，直到去年6月份左右开始搞ACM，才偶尔翻翻这本书。
这本书给我这样的感觉：有时遇到一个算法，在网上找了很多相关资料，但是看完后还是有点迷茫，然后才想起《算法导论》，遇到翻开目录，发现有相关的章节，于是去认真阅读，顿时发现自己的很多问题都可以解决了。它就是这么一本书，也许你会把它当一本圣经来供养，但是当你认真阅读后，你会发现你受益颇多。
于是，自从几次问题通过《算法导论》解决后，我开始意识到，这是一个多么大的宝库啊。它容纳的目前常用的诸多算法，并且都给予了详细解释，图文并茂，易于理解。
到目前为止，中间零散的看过一些章节。我有这么一个习惯，就是每学到一个算法，我都会把这个算法总结一下，我觉得虽然当时写这个总结时有点占用时间，但是当你再温故时，你只需要短短的5分钟，就可以再次记住这个算法，并且通过以前总结的，你也许还可以发现不足，并改正。就像我之前有两次都中断了算法的学习，并且一断就是几个月，但是当我再次拾起算法时，我只需要看看我以前总结的笔记，就可以很快的拾起。在这里推荐下我的算法专题：http://www.wutianqi.com/sfzt.html
所以，这次我也准备把《算法导论》这本书好好总结一下，这样当我总结时，我就可以知道哪些我彻底掌握了，因为如果我只掌握其表面内容，我是没法用自己的话去总结。二是这样大家通过各种搜索引擎搜到我的文章时，可以互相探讨，并且发现哪些地方我理解错了，因为我是非计科生，从大一到现在都是我自己一个人自学过来的，中间肯定会走一些弯路，对一些知识产生曲解，所以这样也可以通过大家来改正我的错误，大家互相学习，互相探讨，交一个可以讨论学术的朋友，何乐而不为呢？
网上有些朋友推荐再遇到算法问题时可以把《算法导论》当字典来查，但是个人觉得，这本书读多少遍都值得，所以完完整整的把这本书看一遍是必须的，以后再可以当一个工具书去查。所以推荐大家一起好好把《算法导论》学习下。
另外，我推荐每学一个算法，就去各个OJ（Online Judge）找一些相关题目做做，有时理论让人很无语，分析代码也是一个不错的选择。
对于接下来要写的一些总结文章，我想做一些约定：
1.写这个总结，我不能确定时间，也许一天总结一章，也许几天总结一章，但是我不会断的，鉴于书上有35章，我估计最快得两个月的时间，最慢应该会花3个月在暑期之前搞定。(因为我还得准备考研，悲催啊。。。)
2.对于后序总结，我不会照搬书上去写，我会尽量少写书上已有的一些原话，我要写的会是强调一些重点，以及书上讲解过少的地方，我会找资料补充起来。
3.当然事情不是绝对的，对一些很重要的概念，算法等，我会根据书上及其他资料再写一遍。
4.对于一些书上内容，当我借鉴时，我可能会直接从英文版的chm书上直接copy或者截图(比如有特殊符号)。
5.因为我只看过部分章节，还有一些章节我也是小白，所以肯定会有一些地方自己也迷糊，大家发现我哪些地方讲的不足，如果发现网上有讲的详细的，可以把网址通过留言告诉我，谢谢。
6.如果我文章里的哪些文字伤害了你的心灵，你可以留言告诉我，我会尽力去安慰你。（呵呵，开个玩笑），大家和谐讨论，和谐学习，和谐共处
7.以后有需要补充的约定我还会再添加。。。
接下来，就让我们大家一起来学习《算法导论》吧！
再废话一句：
推荐论坛：C++奋斗乐园(C/C++/算法)：http://www.cppleyuan.com/
推荐QQ群：119154131（里面有一些高校的牛。。。加群请填写ACM验证）
http://www.wutianqi.com/?p=2298
posted @
2011-04-09 12:13 Tanky Woo 阅读(3187) |
评论 (9) |
编辑 收藏
我的独立博客：http://www.wutianqi.com/
希望大家支持。
谢谢
posted @
2010-09-24 09:22 Tanky Woo 阅读(226) |
评论 (2) |
编辑 收藏原文链接：
http://www.wutianqi.com/?p=1028
今天看了rakerichard的一篇文章，是写的看了《
疯狂的程序员》后的一点感想。
回忆起以前我看这本书，联系自己学编程这一年多，感触颇多。记得这本书刚出来时，我就在中关村图书大厦买了一本。至今已经快一年了。故事情节依稀记得一点。
里面讲到了BOSS 绝的奋斗史，读大学时和寝室一伙人到处折腾，给别人装机子，去小公司找工作，以及后来的作为招聘人员去自己学校招员工，私下接外挂破解，和女友的坎坷经历直到最后的分手。
绝影的人生并不好走，虽然大学还未毕业就找到工作了，但是可以看出他的艰辛，经常熬夜赶项目；节假日不能陪家人，结果女友也要求分手了。
我不知道该说什么好，别人都说嫁人要嫁程序员，程序员只关心电脑，不会在外面过那种花花绿绿的生活，这是褒义，还是贬义？也许只有说这话的人心里才清楚。
我大学是读自动化的，连我都不知道我为何要报自动化，我只知道，高考没考到自己预想的分数，考了一个半吊子的分数：568分，而一本分数线是548.就这么高不高，低不低的。连我老爸当年读的中南财经政法大学都读不了，于是我也懒得管了，直接让我父母报，结果第一志愿是北京化工大学的机械工程及其自动化，第二志愿是北京化工大学的自动化。最后第一志愿没录取，于是我到了北化的自动化系。虽然读了两年大学，我还不知道我这个专业到底是干啥的，只知道这个专业是一个万金油，啥都行~~~
大一刚进校，因为高考完在家天天玩网游，开学了还没回过神来，别人都忙于互相认识，一起游览北京的一些旅游景点，而我却忙于在网吧与寝室两地颠簸。那时刚开学，班级和学校有许多的活动，我一个都没参加，记得开学就有学校和院的各个部门招人手，我那时没认识到德育分的重要性，也没有刻意去培养自己的结交能力(不过我的朋友还是非常多的~~在学校，许多人都和我很熟悉，因为我个人性格是比较活泼开朗的，且喜欢开玩笑，所以都比较随和。)，但学校又要求每人都得报2项，所以其中一项我没去，另外一项别人打电话过来了，我也说没时间~~~（是不是很拽？）其实也不是不给他们面子，只是在我眼中，我不喜欢这些权势及口头上的较量，靠嘴皮子进去，一点用都没，而且在我看来，这些东西都是无聊至极的，一群把自己当成官一样来看待的，让我感觉很不舒服。我喜欢那种靠自己真实实力较量的生活。并且在我看来，等工作了这些权势竞争的生活多的是，在大学去浪费时间花在这上面太不值得了。就这么浑浑噩噩的一个学期快过完了，临近寒假，发现别人虽然分一部分心思去弄学校各个部门的活，但是也确实培养了他们的个人能力，而我呢？除了会去网吧，还是去网吧。虽然那时成绩不差，在班级30人中还能排在第10名。但是自己缺乏了其他独特的能力。因为我接触计算机很早，是从小学5年级开始的，所以我想到了从计算机这方面发展，刚开始对编程一窍不通，买了基本PS,FLASH,DW的书看，结果自己就是在美术细胞上太过于匮乏，始终弄不好，就这样折腾了3个多月，最终放弃了，那时也知道了C语言，且知道下学期要学C语言，所以就提前自学了。我的编程生涯也就是从这个时候开始的（起步很晚~~）。
刚开始学C语言，我就被吸引了，作为男生，我相信好多人都很YM那些开发软件的人，我也不例外，而接触了C语言，我才知道，这就是可以开发出软件的东东，于是，我埋头苦学…汗，其实也算不上苦学，就是把自己的课程都丢了，天天只看C语言的书，因为我不是计算机专业的，没人教我，也没人给我经验，我就只能靠自己，计算机编程这方面的书都很贵的，还好有父母的经济支持，这样算一算，我10个月在买书上就花了2000元。我到现在都不知道怎么花的，反正牛人的书我都买了，还订了好多杂志。记得看了谭老的《C语言程序》，《C Primer Plus》, 《The C Programming Language》 《C陷阱与缺陷》 《C专家编程》等等~~~太多了，我经常没去上课，一个人抱着书和电脑去图书馆学。结果自己专业没顾着，大二下学期还弄了个年级300人，倒数10几名~~
大二上学期我报了等级考试的三级数据库，也顺利的一次通过。呵呵，现在想来，也没啥高兴的，毕竟那些都是虚的，只需要靠2本书死记就过的，没有一点技术含量，不值得高兴。到了现在，数据库的一些知识也快忘光了。
大二上学期的暑假，我开始学习C++了。那时学了一段时间，寂寞了，于是建了几个QQ群，在网上召集了一批C++爱好者一起交流，也就是那个时候，有了创办一个论坛让大家一起交流学习的想法。也就是在大二下学期开学后，随着群的人越来越多，许多人也提议弄一个专门学习交流的地方，于是我买了空间和域名，办了一个论坛。因为我觉得人生就要奋斗，我们学习编程，何尝不是在为以后而奋斗，所以我给群，以及论坛取名叫C++奋斗乐园。域名我也选择了cppleyuan。
最开始接触ACM不知道是在什么时候，应该实在大一下学期或大二上学期吧。那时就觉得这挺有趣的，但是也没买书学习算法，就这么直接找上了POJ，经常把题目看懂就花了1个小时，然后做不出来，再分析别人代码又是几个小时~~~汗…后来觉得这东西不是我这种人弄的，就放弃了。不过还好，只是暂时放弃，在大二下学期开学后1个月，也就是2010年4月份左右吧。我又开始搞ACM了，因为学习C和C++也有一段时间了，对于编程也有了一定的认识，不再是那个初入编程大门，懵懵懂懂乱学的人了，我买了刘如佳老师的《算法学习经典入门》，《算法艺术与信息学竞赛》，吴文虎老师的《世界大学生程序设计竞赛》以及算法的圣经—-《算法导论》。就这么开始一个人在算法的海洋里探索了。也就是这个时候，因为自己对这方面有了解，并且觉得论坛不能只搞C++方面，所以我把论坛一部分分给了算法。毕竟算法是程序的灵魂。但是POJ对于我这个刚起步的小菜来说还是难了些。所以我开始转向HDOJ了，7月10号注册的。今天是8月17号，已经刷了210道水题了。我感觉，每AC一道题目，就感觉自己快乐了一分。也许这就是算法的魅力把，也可能这就是男人喜欢对事物的绝对掌控，感觉自己学懂了这个算法，就感觉自己多了一项能力。
假期我给论坛弄了C/C++小项目和ACM刷题活动。当时我还到处找资料，花了一下午为C/C++小项目的第一个写了一个详细的流程图，结果到最后无人问津，只有个别人做了，wujing的就做的很好，赞一个。不过还好，ACM刷题活动倒是很受欢迎，每天都有一批人和我一起刷，包括MiYu,大帅，萝莉，timest,ac-quest等等。当然，amb教主我就不多说了，我只能YM。小白就是专门和我竞争的家伙。。。最近被他赶超了10题。郁闷。不过假期确实还是很开心的。毕竟结交了一群志同道合的朋友。
现在假期也快结束了，8月20号返校，还得搬校区。
看的书很多，想的也很多。喜欢思考编程，思考人生哲理。平时除了编程的书，我就最喜欢看自然科学和人生哲理了，《当下的力量》，《遇见心想事成的自己》，《秘密》这些书都很好，教会了我很多道理。感觉这些书就和算法一样，讲的都是内涵。人生就像编程，编的是人生，让人生合理，规划好人生，人生才能成功。
最后，我想感谢C++奋斗乐园的各位斑竹，感谢假期陪我刷题的哥们，感谢支持我的论坛会员们。Orz
以上算是发泄自己的情感，也算是倾述自己的经历，或算是总结自己的经验。不求能给大家什么帮助，只求大家能一起多交流点自己的经验，互相借鉴，互相学习。
TankyWoo
2010年8月7号
我的博客：http://www.wutianqi.com/ 希望大家多多交流。
posted @
2010-08-17 11:33 Tanky Woo 阅读(2231) |
评论 (25) |
编辑 收藏The Sieve of Eratosthens
爱拉托逊斯筛选法
（原创链接：http://www.wutianqi.com/?p=264）![[2:23]](http://www.wutianqi.com/wp-includes/images/smilies/23.gif)
思想：对于不超过n的每个非负整数P，删除2*P, 3*P…，当处理
完所有数之后，还没有被删除的就是素数。
若用vis[i]==1表示已被删除，则代码如下：
—————————————————–
代码一：
1
memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3 for(int j = i*2; j <= 100; j += i)
4 vis[j] = 1;
上面的代码效率已经很高了。
但还可以继续优化。
看一个改进的代码：
——————————————————
代码二：
1int m = sqrt(double(n+0.5));
2
3for(int i = 2; i <= m; i++)
4 if(!vis[i])
5
{
6
prime[c++] = i;
7 for(int j = i*i; j <= n; j += i)
8
{
9 vis[j] = 1;
10
}
11
}
——————————————————
先分析代码一：
这个代码就是简单的将Eratosthenes筛选法描述出来。不用多说。
分析代码二：
考虑几点：
1.为何从i=2~m?
因为下面的j是从i*i开始的。
2.为何j从i*i开始？
因为首先在i=2时，偶数都已经被删除了。
其次，“对于不超过n的每个非负整数P”， P可以限定为素数，
为什么？
因为，在 i 执行到P时，P之前所有的数的倍数都已经被删除，若P
没有被删除，则P一定是素数。
而P的倍数中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因为P为素数，所以为奇数，而偶数已被删除，不需要考虑p*(p
-1)等）（Tanky Woo的程序人生）
又因为(p-4)*p 已在 (p-4)的p倍中被删去，故只考虑：
p*p, p*(p+2)….即可
这也是i只需要从2到m的原因。
当然，上面 p*p, p*(p+2)…的前提是偶数都已经被删去，而代码
二若改成 j += 2*i ,则没有除去所有偶数，所以要想直接 加2*i
。只需在代码二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
这样，i只需从3开始，而j每次可以直接加 2*i.
------------------------------------------------------
这里用代码二给大家一个完整的代码：
1//版本二
2//Author: Tanky Woo
3//Blog: www.wutianqi.com
4
5#include <stdio.h>
6#include <string.h>
7#include <math.h>
8int vis[100];
9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14 scanf("%d", &n);
15 int cnt = 1;
16
17 memset(vis, 0, sizeof(vis));
18 int m = sqrt(double(n+0.5));
19
20 for(int i = 2; i <= m; i++)
21 if(!vis[i])
22 {
23 prime[c++] = i;
24 for(int j = i*i; j <= n; j += i)
25 {
26 vis[j] = 1;
27 //printf("%d\n", j);
28 }
29 }
30
31 for(int i = 2; i < n; i++)
32 {
33 if(vis[i] == 0)
34 {
35 printf("%d ", i);
36 cnt++;
37 if(cnt % 10 == 0)
38 printf("\n");
39 }
40 }
41 printf("\ncnt = %d\n", cnt);
42 return 0;
43}
完毕。
欢迎大家和我交流。(我的博客:http://www.wutianqi.com/)
posted @
2010-08-04 13:55 Tanky Woo 阅读(1154) |
评论 (1) |
编辑 收藏
摘要: 母函数（Generating function）详解
（因为我是用Word写好了贴上来的，不知为何图片点插入不管用，这是原文：http://www.wutianqi.com/?p=596，大家可以直接去这里看。）
前段时间写了一篇《背包之01背包、完全背包、多重背包详解》，看到支持的人很多，我不是大牛，只是一个和大家一样学习的人，写这些文章的目的只是为了一是希望让大家学的轻松，二是让自己复...
阅读全文
posted @
2010-08-02 15:34 Tanky Woo 阅读(7154) |
评论 (8) |
编辑 收藏背包之01背包、完全背包、多重背包详解
PS：大家觉得写得还过得去，就帮我顶博客，谢谢。
首先说下动态规划，动态规划这东西就和递归一样，只能找局部关系，若想全部列出来，是很难的，比如汉诺塔。你可以说先把除最后一层的其他所有层都移动到2，再把最后一层移动到3，最后再把其余的从2移动到3，这是一个直观的关系，但是想列举出来是很难的，也许当层数n=3时还可以模拟下，再大一些就不可能了，所以，诸如递归，动态规划之类的，不能细想，只能找局部关系。
1.汉诺塔图片
（引至杭电课件:DP最关键的就是状态，在DP时用到的数组时，也就是存储的每个状态的最优值，也就是记忆化搜索）
要了解背包，首先得清楚动态规划：
动态规划算法可分解成从先到后的4个步骤：
1. 描述一个最优解的结构；
2. 递归地定义最优解的值；
3. 以“自底向上”的方式计算最优解的值；
4. 从已计算的信息中构建出最优解的路径。
其中步骤1~3是动态规划求解问题的基础。如果题目只要求最优解的值，则步骤4可以省略。
背包的基本模型就是给你一个容量为V的背包
在一定的限制条件下放进最多(最少?)价值的东西
当前状态→ 以前状态
看了dd大牛的《背包九讲》(点击下载)，迷糊中带着一丝清醒，这里我也总结下01背包，完全背包，多重背包这三者的使用和区别，部分会引用dd大牛的《背包九讲》，如果有错，欢迎指出。
(www.wutianqi.com留言即可)
首先我们把三种情况放在一起来看：
01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。
——————————————————————————————————————————————————————————–：
01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把这个过程理解下：在前i件物品放进容量v的背包时，
它有两种情况：
第一种是第i件不放进去，这时所得价值为:f[i-1][v]
第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）
最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。
（这是基础，要理解！）
这里是用二位数组存储的，可以把空间优化，用一位数组存储。
用f[0..v]表示，f[v]表示把前i件物品放入容量为v的背包里得到的价值。把i从1~n(n件)循环后，最后f[v]表示所求最大值。
*这里f[v]就相当于二位数组的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重点！思考）
首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N
现在思考如何能在是f[v]表示当前状态是容量为v的背包所得价值，而又使f[v]和f[v-c[i]]+w[i]标签前一状态的价值？
逆序！
这就是关键！
1for i=1..N
2 for v=V..0
3 f[v]=max{f[v],f[v-c[i]]+w[i]};
4
分析上面的代码：当内循环是逆序时，就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的！
这里给大家一组测试数据：
测试数据：
10,3
3,4
4,5
5,6
这个图表画得很好，借此来分析：
C[v]从物品i=1开始，循环到物品3，期间，每次逆序得到容量v在前i件物品时可以得到的最大值。（请在草稿纸上自己画一画）
这里以一道题目来具体看看：
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2602
代码在这里：http://www.wutianqi.com/?p=533
分析：
具体根据上面的解释以及我给出的代码分析。这题很基础，看懂上面的知识应该就会做了。
——————————————————————————————————————————————————————————–
完全背包：
完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
同样可以转换成一维数组来表示：
伪代码如下：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
顺序！
想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。
现在关键的是考虑：为何完全背包可以这么写？
在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。
那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？
因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。
这里同样给大家一道题目：
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1114
代码：http://www.wutianqi.com/?p=535
（分析代码也是学习算法的一种途径，有时并不一定要看算法分析，结合题目反而更容易理解。）
——————————————————————————————————————————————————————————–
多重背包
多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
这里同样转换为01背包：
普通的转换对于数量较多时，则可能会超时，可以转换成二进制（暂时不了解，所以先不讲）
对于普通的。就是多了一个中间的循环，把j=0~bag[i]，表示把第i中背包从取0件枚举到取bag[i]件。
给出一个例题：
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2191
代码：http://www.wutianqi.com/?p=537
因为限于个人的能力，我只能讲出个大概，请大家具体还是好好看看dd大牛的《背包九讲》。
暂时讲完后，随着以后更深入的了解，我会把资料继续完善，供大家一起学习探讨。(我的博客：www.wutianqi.com如果大家有问题或者资料里的内容有错误，可以留言给出，谢谢您的支持。)
原文下载地址：（Word版）
http://download.csdn.net/sour
个人原创，转载请注明本文链接：http://www.wutianqi.com/?p=539
posted @
2010-07-31 19:07 Tanky Woo 阅读(18286) |
评论 (11) |
编辑 收藏
建议先看看前言：http://www.wutianqi.com/?p=2298
连载总目录：http://www.wutianqi.com/?p=2403
说到贪心算法，避免不了于DP对比，所以前面的DP要了解。
贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生一个全局最优解。
依然和上一章总结DP一样，我先给出一个最容易入门的例子，来看看神马是贪心？(是人就会贪心，这个算法很人性化啊
=。=)
一个最简单的例子：
部分背包问题：
有N个物品，第i个物品价值vi，重wi，现在你有一个可以装W 磅的包，你可以选择带走每个物品的全部或一部分，求如何选择可以使背包所装的价值最大？(这个是不是和前面DP中讲的01背包很像？认真看清楚两者题目的不同！)
假如有三种物品，背包可装50磅的物品，物品1重10磅，价值60元；物品2重20磅，价值100元；物品3重30磅，价值120元。因此，既然可以选择只装一部分，我们可以算出每种物品的单位价值，物品1是每磅6元，物品2是美邦5元，物品3是每磅4元。按照贪心策略，应该现状物品1，如果装完物品1背包还有空间，再装物品2……
最后的结果是：
而如果按01背包，则结果是：
有兴趣的可以拿我那01背包的程序去验证这个结果。
下面是一个部分背包的小程序：
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
|
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Thing{
double v; // value
double w; // weight
}Thing;
Thing arr[100];
int n;
double W;
bool cmp(Thing a, Thing b)
{
return a.v/a.w > b.v/b.w;
}
int main()
{
cout << "输入物品个数: ";
cin >> n;
cout << "输入背包可载重量: ";
cin >> W;
cout << "输入" << n << "个物品的价值和重量:" << endl;
for(int i=0; i<n; ++i)
cin >> arr[i].v >> arr[i].w;
sort(arr, arr+n, cmp);
int k = 0;
double value = 0;
while(W)
{
if(W >= arr[k].w)
{
W -= arr[k].w;
value += arr[k].v;
}
else
{
value += W * arr[k].v / arr[k].w;
W = 0;
}
++k;
}
cout << "最大价值是: " << value << endl;
return 0;
} |
结果如图：
posted @
2011-06-14 13:17 Tanky Woo 阅读(1727) |
评论 (5) |
编辑 收藏
建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这个案例也比较简单，最长公共子序列(LCS)，网上的分析非常多，给力啊！
按照上一篇总结所说的，找状态转移方程：
所以按照所给方程，写代码的工作就非常非常简单轻松了：
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的结果图：
又是一个给力的图,建议自己按照程序把这个图画出来.
另外,说到LCS,不得不说的是LIS(最长上升子序列)，也是一个DP，我曾经总结过：
http://www.wutianqi.com/?p=1850
Tanky Woo 标签:
DP，
动态规划，
LCS
posted @
2011-05-26 18:55 Tanky Woo 阅读(1487) |
评论 (2) |
编辑 收藏
建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一节可以看到《算法导论》学习总结 — 16.第15章 动态规划(1) 基本入门的补充。
采用动态规划的最优化问题的两个要素：最优子结构和重叠子问题。
先看看最优子结构：
在第17篇总结时，装配线调度问题中，已经设计到了最优子结构，证明最优子结构问题可以用书上说的“剪贴技术”，即假设存在更优的解，来反正最优解矛盾。
再看看重叠子问题：
当一个递归算法不断的调用同一个问题时，我们说该最有问题包含“重叠子问题”。
上面这句话不好理解？
看看下面这个比较：
递归算法：自顶而下，对在递归树中重复出现的每个子问题都要重复解一次。
动态规划：自下而上，对每个只解一次。
结合第16篇总结的三角形求值例子，可以看得到，自下而上导致每个子问题只求解一次。
以上理论性有点强，我最开始学DP看的是HDOJ的课件，有兴趣的可以去看看。
在那里面，主要讲到了是找状态转移方程，在第16篇的三角形求值例子和第17篇的装配线调度例子，那些递归公式都是状态转移方程。
下面这段话好好理解：
——————————————————————–
动态规划的几个概念:
阶段：据空间顺序或时间顺序对问题的求解划分阶段。
状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。
决策：根据题意要求，对每个阶段所做出的某种选择性操作。
状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。
动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化的一种方法。
所谓多阶段决策过程，是将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。
动态规划所依据的是“最优性原理”。
“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。
最优决策序列的子序列，一定是局部最优决策子序列。
包含有非局部最优的决策子序列，一定不是最优决策序列。
动态规划的指导思想是：
在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。
——————————————————————–
看见有人说递归就是DFS，而DP就是BFS，感觉有那么一点意思，对于DP，就是从底层一层层的计算，然后在当层中选取最优，逐层最优以至总体最优。
其实这个还是多做一些题就好了(⊙ｏ⊙)，大家别认为我是做题控，其实说实在话，看N遍不如做一题，说白了，算法数学本一家，算法就是数学，走过高中的，都知道数学题得多做，尤其压轴题，看N遍不如做一遍，这个也是一样做几题就知道DP是神马东东了！
在我独立博客上的原文：http://www.wutianqi.com/?p=2500
欢迎大家互相学习，互相进步！
posted @
2011-05-23 12:03 Tanky Woo 阅读(1553) |
评论 (0) |
编辑 收藏
建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
原来打算把算法导论在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的标志之一。
步骤二：
找出这个递归关系，由步骤一可以得到这个递归关系：
步骤三：
因为递归的关系，一般总是可以转换为非递归的算法。
由已知量f1[1], f2[1]逐步推出未知量，推啊推，推啊推，最后就推到结果了~~~~
步骤四：
再由已知结果返回求路径。
这一节最给力的就是这个例子以及相应的图：
拿起笔，用书上给出的例子，分析这个图！
以下是代码：
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;
} |
最后还是要感叹一下，《算法导论》讲的真是棒极了，希望大家能静下心把这一章节好好看看。
在我独立博客上的原文：http://www.wutianqi.com/?p=2496
欢迎大家互相学习，互相进步！
posted @
2011-05-20 11:57 Tanky Woo 阅读(1748) |
评论 (2) |
编辑 收藏第十四章我想放在后面再看，先搁下。希望大家总结的一些文章也能向我推荐下，大家互相学习。
首先，还是建议看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
其次，阿门，感谢老天送给了我们这么一本圣经，看了这一章，再次感受到了《算法导论》分析问题的精辟，强悍的魅力。Orz, Orz,各种Orz。
这一章讲的是动态规划，学算法的朋友，尤其是搞ACM的，对这个策略一定非常熟悉，所以这个算法网上的分析讲解教程也是铺天盖地，大家可以多搜几篇学习学习。
动态规划(Dynamic Programming，简称DP)是通过组合子问题的解来解决问题的。
注意这里的programming不是指编程，而是指一种规划。
因为DP用的太广泛了，并且书上也花了很大的篇幅来讲这一章，所以我也准备把这一章分几篇来总结，并且我不按照书上的顺序来总结，也不会全部用书上的例子。
这一章首先给出一些基础的概念，然后给出一个最基础入门的DP问题，三角形求值问题。
DP适用于子问题不是独立的情况，这样如果用分治法，也会作许多重复的工作，而DP只对子问题求解一次，将其结果保存在一张表中，从而避免了每次遇到各个子问题时重新计算的情况。
比较分治法于动态规划的区别：
分治法：将问题划分为一些独立的子问题，递归的求解各子问题，然后合并子问题的解而得到原问题的解。
eg.
MERGE-SORT(A, p, r)
1 if p < r
2 then q ← |(p + r)/2|
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
动态规划：适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题，鉴于会重复的求解各子问题，DP对每个问
题只求解一遍，将其保存在一张表中，从而避免重复计算。
DP算法的设计可以分为四个步骤：
①.描述最优解的结构。
②.递归定义最优解的值。
③.按自底而上的方式计算最优解的值。
④.由计算出的结果创造一个最优解。
下面来看看三角形求值这个问题：
将一个由N行数字组成的三角形，如图所以，设计一个算法，计算出三角形的由顶至底的一条路径，使该路径经过的数字总和最大。
这是在我见过的DP题目中，算是最简单的了，我相信就算没有学过DP的也会。
将上图转化一下：
假设上图用map[][]数组保存。
令f[i][j]表示从顶点(1, 1)到顶点(i, j)的最大值。
则可以得到状态转移方程：
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
此题既适合自顶而下的方法做，也适合自底而上的方法，
当用自顶而下的方法做时，最后要在在最后一列数中找出最大值，
而用自底而上的方法做时，f[1][1]即为最大值。
所以我们将图2根据状态转移方程可以得到图3：
最大值是30.
很简单的DP题，代码如下：
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
|
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
Description: 动态规划之三角形求值问题
*/
#include <iostream>
using namespace std;
int map[6][6] =
{
{0, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 0, 0},
{0, 3, 8, 0, 0, 0},
{0, 8, 1, 0, 0, 0},
{0, 2, 7, 4, 4, 0},
{0, 4, 5, 2, 6, 5}
};
int f[6][6];
int _max(int a, int b)
{
if(a >= b)
return a;
return b;
}
int main()
{
memset(f, 0, sizeof(f));
for(int i=0; i<6; ++i)
f[5][i] = map[5][i];
for(int i=4; i>=1; --i)
for(int j=1; j<=i; ++j)
f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
for(int i=1; i<=5; ++i)
{
for(int j=1; j<=5; ++j)
{
cout.width(2);
cout << f[i][j] << " ";
}
cout << endl;
}
cout << f[1][1] << endl;
} |
结果如图：
下一篇会将装配线的调度。
在我独立博客上的原文：http://www.wutianqi.com/?p=2484
欢迎大家互相学习，互相进步！
posted @
2011-05-20 07:27 Tanky Woo 阅读(1709) |
评论 (0) |
编辑 收藏
摘要: 建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一章把前面三篇的代码总结起来，然后推荐一些网上红黑树的优秀讲解资源。
代码：
1
2
3
...
阅读全文
posted @
2011-05-12 16:33 Tanky Woo 阅读(2013) |
评论 (1) |
编辑 收藏
建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一篇是关于红黑树的结点删除。
依然和上一篇的插入一样，先用到了BST的删除结点函数，然后做相应的调整。
不过，这里的调整思路颇为新颖。
还是来看看略微改变后的删除结点函数：
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
| Node* RBTreeDelete(RBTree T, Node *z)
{
Node *x, *y;
// z是要删除的节点,而y是要替换z的节点
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 当要删除的z至多有一个子树，则y=z；
else
y = RBTreeSuccessor(z); // y是z的后继
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
// 无条件执行p[x] = p[y]
x->parent = y->parent;
if(y->parent == NULL)
T = x;
else if(y == y->parent->lchild)
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
if(y->color == BLACK)
RBDeleteFixup(T, x);
return y;
} |
注意代码倒数第二和第三行，只有当后继结点y的颜色是黑色时，才做调整。
由此，引导出几个问题：
1.问：考虑为何当y的颜色是黑色时，才调整？当y的颜色是红黑时，会不会破坏性质4？
答：这里我一开始纠结了，后来反复看了几次BST的删除，再算想通。在BST中，删除结点z，并不是真的把z给移除了，其实删除的不是z，而是y！因为z始终没有动过，只是把y删除了，然后把y的key赋值给z的key。所以，在红黑树中，z的颜色没有变，依然符合红黑性质。（这里我先开始理解为y->color也要赋值给z->color，汗。。。）
2.问：考虑y为黑色时，破坏了哪几条红黑性质？
答：当y是根时，且y的一个孩子是红色，若此时这个孩子成为根结点。———>破坏了性质2
当x和p[y]都是红色时。 ———>破坏了性质4
包含y的路径中，黑高度都减少了。 ———>破坏了性质5
解决方法：
上一篇我解释过，性质五涉及到了整棵树，难以控制。
因此将x的颜色增加一重黑色，那么当:
①.x原先颜色为RED时——->x包含RED和BLACK两颜色
②.x原先颜色是BLACK时—–>x包含BLACK, BLACK两颜色。
此时性质5解决，但是又破坏了性质1.
接下来就是恢复性质1，2，4了。
将额外的一重黑色一直沿树向上移，直到x是根或者是红色结点。
看看具体的实现代码：
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
| void RBDeleteFixup(RBTree &T, Node *x)
{
while(x != T && x->color == BLACK)
{
if(x == x->parent->lchild)
{
Node *w = x->parent->rchild;
///////////// Case 1 /////////////
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
LeftRotate(T, x->parent);
w = x->parent->rchild;
}
///////////// Case 2 /////////////
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
///////////// Case 3 /////////////
if(w->rchild->color == BLACK)
{
w->lchild->color = BLACK;
w->color = RED;
RightRotate(T, w);
w = x->parent->rchild;
}
///////////// Case 4 /////////////
w->color = x->parent->color;
x->parent->color = BLACK;
w->rchild->color = BLACK;
LeftRotate(T, x->parent);
x = T;
}
}
else
{
Node *w = x->parent->lchild;
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
RightRotate(T, x->parent);
w = x->parent->lchild;
}
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if(w->lchild->color == BLACK)
{
w->rchild->color = BLACK;
w->color = RED;
LeftRotate(T, w);
w = x->parent->lchild;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->lchild->color = BLACK;
RightRotate(T, x->parent);
x = T;
}
}
}
x->color = BLACK;
} |
对于删除的调整，共八种情况(左右对称各四种)，这里在书上P175面讲的很详细，所以我也就不再画图了，大家可以自己拿起笔在草稿纸上画一
在我独立博客上的原文：http://www.wutianqi.com/?p=2449
欢迎大家互相讨论，一起进步！
posted @
2011-05-11 11:52 Tanky Woo 阅读(1828) |
评论 (1) |
编辑 收藏
建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
插入结点用到了上一次BST的插入函数(做了一点添加)，并且在此基础上增加了保持红黑性质的调整函数。
还是先看看插入函数：
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
|
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
和上一次的BST基本没区别，只是添加了对新加结点z的颜色和子节点的处理。
这里把z的颜色设置为红色，然后进行处理。
问：考虑为何把z的颜色设置为红色？
答：个人认为如果设置为黑色，则破坏了性质五，而性质五关于黑高度的问题，涉及到了整棵树，全局性难以把握，所以这里设置为红色，虽然破坏了性质4，然是相对破坏性质5来说，更容易恢复红黑性质。大家如果有不同的想法，也可以留言谈谈。
接下来，就是对整棵树的调整了。
答：考虑插入z结点后，破坏的哪几条红黑性质？
答：破坏了性质2和性质4.
5条红黑性质要熟记，我这里再贴出来：
1. 每个结点或是红色，或是是黑色。
2. 根结点是黑的。
3. 所有的叶结点(NULL)是黑色的。（NULL被视为一个哨兵结点，所有应该指向NULL的指针，都看成指向了NULL结点。）
4. 如果一个结点是红色的，则它的两个儿子节点都是黑色的。
5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
所以我们要做的就是恢复性质2和性质4.
先来看看具体实现的代码(这里只贴出部分代码)：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
///////////////////////
}
}
T->color = BLACK;
}
|
分三种情况，在代码中已用Case 1, Case 2, Case 3标记出。
大致说下判断情况：
1.首先让一个指针y指向z的叔父结点(z是要删除的结点)。
2.如果y的颜色是红色，Case 1。则使z的父亲结点和叔父结点的颜色改为黑，z的祖父结点颜色改为红。然后让z转移到z的祖父结点。
3.当y的颜色是黑色时，
①.首先判断z是否是其父亲结点的右儿子，若是，则调整为左儿子(用旋转)。
②.其次使z的父亲结点颜色为黑，z的祖父结点颜色为红，并以z的祖父结点为轴右旋。
具体我还是在草稿纸上画出。。。(可怜买不起数码相机，只能用手机拍了。。。)
（弱弱的问一句，看见网上有很多朋友做的一些代码讲解图很给力，不知道大家有什么软件吗？求推荐。。。）
以下是插入的完整代码：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
Node *y = z->parent->parent->lchild;
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->lchild)
{
z = z->parent;
RightRotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate(T, z->parent->parent);
}
}
}
T->color = BLACK;
}
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
下一篇是关于红黑树的删除。
posted @
2011-05-08 08:26 Tanky Woo 阅读(1471) |
评论 (1) |
编辑 收藏