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 阅读(3185) |
评论 (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)
思想:对于不超过n的每个非负整数P,删除2*P, 3*P…,当处理
完所有数之后,还没有被删除的就是素数。
若用vis[i]==1表示已被删除,则代码如下:
—————————————————–
代码一:
1memset(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 阅读(18285) |
评论 (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 阅读(1726) |
评论 (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,就是从底层一层层的计算,然后在当层中选取最优,逐层最优以至总体最优。
其实这个还是多做一些题就好了(⊙o⊙),大家别认为我是做题控,其实说实在话,看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 阅读(1708) |
评论 (0) |
编辑 收藏
摘要: 建议先看看前言:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一章把前面三篇的代码总结起来,然后推荐一些网上红黑树的优秀讲解资源。
代码:
1
2
3
...
阅读全文
posted @
2011-05-12 16:33 Tanky Woo 阅读(2012) |
评论 (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 阅读(1827) |
评论 (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 阅读(1470) |
评论 (1) |
编辑 收藏