08 贪心法.ppt

第1页：第八讲贪心法封面

本页为第八讲 贪心法章节封面，本讲以事件序列、区间覆盖、删数问题等为例讲解贪心策略。

第2页：最长事件序列问题

包含 N 个时间不重叠事件的数目称为序列的长度，编程求最长序列。

第3页：十二个事件的起止时刻表

第4页：事件在时间轴上的分布

本页以图形方式展示 12 个事件在时间轴上的分布，横轴为时刻 0~20，用于观察事件之间是否重叠。

第5页：事件不重叠的条件

a 和 b 事件的开始时刻小于结束时刻：

Begin[a] < End[a] Begin[b] < End[b]

b 事件的开始时刻大于等于 a 事件的结束时刻，即 Begin[b] >= End[a]，记为 b > a，这时 b 事件与 a 事件不重叠。

第6页：所有不重叠的事件序列

找出时间上不重叠的事件，共有以下 8 种序列：

• 2#，9#
• 2#，8#，10#
• 2#，8#，11#
• 0#，3#，8#，10#
• 0#，3#，8#，11#
• 0#，1#，5#，8#，10#
• 0#，1#，5#，8#，11#
• 0#，1#，6#，10#
• 0#，1#，6#，11#

第7页：贪心策略的选择

每个都选择最早结束的序列——贪心策略：

0# - 1# - 5# - 8# - 10#

这是最长序列。

第8页：输出结果函数OtputResult

#include<iostream.h> const int N=12; void OtputResult(int Select[N]); { cout<<"{ 0"; for( int i=1; i<N; i++ ) if ( Select[ i ]=1) cout<<","<< i ; cout<< " } " <<endl; }

说明：源程序此处有两处笔误——函数名 OtputResult 与后文调用的 OutputResult 不一致（按 OutputResult 为准），判断式 Select[i]=1 应为 Select[i]==1，这里按标准写法更正。

第9页：贪心法主函数的数据定义

void main( ) { int Begin[N]={1,3,0,3,2,5,6,4,10,8,15,15}; int End[N]={3,4,7,8,9,10,12,14,15,18,19,20}; int Select[N]={0,0,0,0,0,0,0,0,0,0,0,0}; int i=0; int TimeStart=0; 
第10页：贪心选择的循环
while( i < N ) { if ( Begin[ i ]>=TimeStart ) { Select[ i ]=1; TimeStart=End[ i ]; } i ++; } OutputResult ( Select ) ; }
循环的含义：从左到右扫描事件，只要当前事件的开始时刻不早于已选序列的结束时刻，就把它选入序列，并把可选的最早开始时刻更新为该事件的结束时刻，这正是“每次选最早结束者”的贪心策略。
第11页：三个数组的状态表
贪心法执行后 Begin、End 与 Select 数组的取值
下标
0
1
2
3
4
5
6
7
8
9
10
11
Begin
1
3
0
3
2
5
6
4
10
8
15
15
End
3
4
7
8
9
10
12
14
15
18
19
20
Select
1
1
0
0
1
0
1
0
1
0
1
0
说明：源文件该页 Select 一行以粘连字符形式给出，上表数值为依据贪心算法（每次取最早结束者）与前后页所列结果 0#、1#、5#、8#、10# 还原，供对照原图核对。
第12页：区间覆盖问题
区间覆盖问题：本页以图形方式给出待覆盖的区间与可供选择的若干子区间（图上标注了 f1 至 f4 等取值），讲解用贪心策略做区间覆盖的思路。
说明：源文件该页以图形为主，文字与数据呈粘连状态，建议对照原图核对区间端点与覆盖方案。
第13页：删数问题
删数问题：从 N 位数字串中删去 M 个数，使剩下的数字串所表示的数值最小。
第14页：删数问题的思路
解题思路：从一个例子开始分析——数字串 5 0 2 6 7 5 3 9：
5 0 2 6 7 5 3 9 （箭头表示 0 与 5 的高低关系） 0 2 6 7 5 3 9 （5 值高，删去） 0 2 6 5 3 9 （7 值高，删去） 0 2 5 3 9 （6 值高，删去） 0 2 3 9 （5 值高，删去） 2 3 9 （去掉高位 0）
每一步都删去一个使数值尽可能变小的数字，这正是贪心策略。最后还要去掉数字串高位的 0。
第15页：删数问题的算法
总结算法：
用键盘输入数字串 S[]
测 S 的串长 L
输入要删除的数字个数 M
当 ( M>0 ) 时，做：
{ i=1; 当( i < L 且 S[ i ]<=S[ i +1] ) i = i +1; 删去 S[ i ]; }
去掉 S 串中的高位 0
第16页：删除字符的函数deleteS
#include <iostream.h> void deleteS(char *p) { while(*p) { *p = *(p+1); p++; } }
函数通过把后面的字符逐个前移一位，实现从字符串中删掉指定位置的一个字符。
第17页：删数问题的主函数前段
int main() { char S[240]; int i,m; cout <<"请输入数字串:"<<endl; cin >> S; cout <<"请输入须删掉多少个数:"<<endl; do { cout <<"0 < N <数字串的长度" <<endl; cin >> m; } while( m<0 || m >= (int)strlen(S) );
第18页：删数问题的处理主循环
while(m>0) { i = 0; while((S[i]<S[i+1])) i++; deleteS(&S[i]); m--; }while(S[0]=='0') deleteS(&S[0]); cout << S <<endl; return 0; }
主循环每轮从头扫描，找到第一个“后一位比前一位大”的位置并删去该位，重复 m 次后去掉高位 0 并输出结果串。
第19页：C猜测前的情形
例子 2. 第二步让 B 猜：B 看到 a=1，c=3，他会想到自己头上的数不是 2 就是 4。B 面对的猜测函数为：
check(a,a+c,c,2) = check(1,4,3,2); check(a,|a-c|,c,2) = check(1,2,3,2);
第20页：B为什么也猜不到
例子：B 还会想为什么 A 猜不到呢？B 想：
如果 b2=2，A 看到 b=2，c=3，会想到自己头上的数是……
如果 b2=4，A 看到 b=4，c=3，会想到自己头上的数是……
这两种情况 A 都不也猜。B 认为 A 不也猜有道理，B 自己也不敢猜。
第21页：C面对的两个猜测函数
例子 3. 第三步让 C 猜：C 看到 a=1，b=2，他会想到自己头上的数不是 1 就是 3。C 面对的猜测函数为：
check(a,b,a+b,3) = check(1,2,3,3); check(a,b,|a-b|,3) = check(1,2,1,3);
第22页：C排除一种可能性
例子：C 会想为什么 B 猜不到呢？C 想：如果 c3=1，对 B 而言，B 看到 a=1、c3=1，B 会很快判断出 b=a+c3=1+1=2。可是 B 并未猜出，说明 c3=1 应被排除。两种可能性，一个被排除了，另一个就是所求了，即 c3=3。我们用“与或”结点图来描述 C 的猜测过程。
第23页：与或图中的CB1与CB2
例子：在上图中，
CB1 表示的是：C 想，如果自己头上是 3，B 能不能猜出 b=2
CB2 表示的是：C 想，如果自己头上是 1，B 能不能猜出 b=2
第24页：异或运算判定CB
例子：C 推测 B 对 C 头上的两种可能数字的反映，来判定该排除哪一个、保留哪一个。如果能够保留一个排除一个，则 CB=true；如果两个都保留或两上都排除，则 CB=false。因此 CB 应为 CB1 与 CB2 的异或运算结果。
上述这张图的物理意义是：要想判断 check(1,2,3,3) 是 true 还是 false，要把它转化为 check(1,2,3,3) XOR check(1,2,1,2)。check(1,2,3,3) 是说让 B 猜，B 如果看到 c=1、a=1，他会抢先猜到自己头上的数是 2，但这不是事实，因为 B 没敢猜。可见 B 看到的不是 c=1，而是另一种可能 c=3。故 B 帮助 C 排除了一种可能，成全了 C，让 C 猜到 c=3。
第25页：猜数函数的定义
下面我们给出更为全面的与或结点图——3 人猜自己帽子上的数的“与或”结点图。
定义：check(a,b,c,k) 为猜数函数，为布尔型函数。其中 a、b、c 分别为 A、B、C 三人，k 为第 k 次猜。规定 k=1 为 A 猜，k=2 为 B 猜，k=3 为 C 猜。如猜测次数超过 3，则有 k mod 3 = 1 为 A 猜，k mod 3 = 2 为 B 猜，k mod 3 = 0 为 C 猜。
第26页：三人猜数的与或结点图
本页以图形方式给出三人猜自己帽子上数字的与或结点图，源文件未给出更多文字说明。
第27页：三组递推关系式
AC1=check(b+c,b,c,k-1); AC2=check(abs(b-c),b,c,k-1); AC=AC1 XOR AC2; BA1=check(a,a+c,c,k-1); BA2=check(a,abs(a-c),c,k-1); BA=BA1 XOR BA2; CB1=check(a,b,a+b,k-1); CB2=check(a,b,abs(a-b),k-1); CB=CB1 XOR CB2;
第28页：与或结点图的说明
说明：
结点 F 是函数 check(a,b,c,k)，意思是第 k 次猜出来了吗？如果函数值为 true 表示猜出了，false 表示猜不出
结点 F 是一个或结点，以 k=0 还是 k>0 分支。当 k=0 时为直接可解结点 E，函数值为 false，可解释为还没让猜，当然为 false
当 k>0 时，分支至 D 结点。D 也是一个或结点，有三个分支
第29页：第八讲结束页
本页为第八讲 贪心法的结束页，本讲内容至此结束。