C++编程贪心法-[装船-事 件-删数].pptVIP

* int main() { cout 请输入数字串:endl; char S[240]; cin S; int L = strlen(S); cout 请输入须删掉多少个数:Mendl; int M; do { cout 0 M 数字串的长度 endl; cin M; } while ( M0 || M = L ); * while(M0) { int i = 0; while( (i L) (S[i] = S[i+1]) ) i++; // 寻找待删除的数S[i]) deleteS(S[i]); // 删除S[i] // or: deleteS(S+i); M--; } * // 删除S串中高位的所有0 while (S[0] == ‘0’) // 字符串首位为0 deleteS(S[0]); // 删掉 // or: deleteS(S); if ( strlen(S) != 0 ) // 字符串长不为0 cout S endl; else // 字符串长为0 cout 0 endl;// 删空了！ return 0; } // main() END! * // 删除字符序列（数组）首字符的子函数 void deleteS(char *p) { while (*p) // 当p所指向的字符不是终止符 { *p = *(p+1); // p+1所指向的字符覆盖p所指向的字符 p++; } }// 删除当前所指字符，后续字符应向前补上 * s[0] p p+1 p=s[3] p+1=s[4] 0 2 6 7 5 3 9 \0 \0 *p=*(p+1); 5覆盖7 p p+1 p++ 0 2 6 5 5 3 9 \0 \0 *p=*(p+1); 3覆盖5 p p+1 p++ 0 2 6 5 3 3 9 \0 \0 *p=*(p+1); 9覆盖3 p p+1 p++ 0 2 6 5 3 9 9 \0 \0 *p=*(p+1); \0覆盖9 p 0 2 6 5 3 9 \0 \0 \0 请结合本页图示将删数程序看懂学会 * 思考题： 1. 本题使用了贪心策略，请问：具体“贪”在哪里呢？ 2. 对前一页图示中的最后一行，你认为下一步该删哪个数字了？请结合源程序手工删删看。 * 结 束 * 第十章 贪心法 教学目标 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项 内容要点 贪心法的应用 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项 * 引子（任务10.1）：事件序列的长度问题 事件序列长度：由N个在时间上不重叠的事件所组成的事件序列，其长度定义为N。 已知有若干事件，发生和结束的时刻等信息数据如下所示（见下页）。 试编程求出所给数据中最长的事件序列，即应由哪些事件组成一个事件序列，能使序列所含的事件数最多。 * 事件号按结束时刻从小到大排序 事件号 # 0 1 2 3 4 5 6 7 8 9 10 11 发生时刻 1 3 0 3 2 5 6 4 10 8 15 15 结束时刻 3 4 7 8 9 10 12 1415 18 19 20 * 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 11 13 15