字符串排序回溯计算概论习题.ppt

《字符串排序回溯计算概论习题.ppt》由会员分享，可在线阅读，更多相关《字符串排序回溯计算概论习题.ppt（65页珍藏版）》请在三一办公上搜索。

1、字符串,排序,(回溯)计算概论习题课,高圣亮 2007-11-27,字符串处理in c&c+提纲,概论字符串处理中经常用到的功能功能的三种实现方法：C风格字符数组遍历C风格库函数C+风格库(字符串类)与字符串处理相关的两个重要问题字符串的输入和输出 字符数组与指针的关系,字符串处理in c&c+概论,存在形式c:以null结尾的字符数组c+：类，对象特点c+的方法更直观c的方法实现效率更高c/c+字符串表达方式的的相互转化string s(“example”);s.c_str();,字符串处理in c&c+常用功能,赋值 判断一个字符串的长度 比较两个字符串（如何界定比较？）字符串的拼接查找（

2、获得）/添加/删除/替换（特定位置的）一个特定字串/一段区间查找/添加/删除/替换 一个特定字符/一个索引位置的字符,字符串处理in c&c+功能的三种实现,以获得一个字符串的长度为例：C风格字符数组遍历#include#include int length(char*);int main()char szInput256;printf(“Enter a sentence:”);gets(szInput);printf(“The sentence entered is%u characters long.n”,length(szInput);/strlen()int length(char*s

3、)int count=0;while(*s+!=0)count+;return count;,字符串处理in c&c+功能的三种实现,2.c风格处理strlen()函数 返回从给定指针到终结的0中间的字符个数 3.c+风格处理size(),length()成员函数返回整个字符串的长度#include#include using namespace std;int main()string s;getline(cin,s);int n=s.size();int m=s.length();/length()是size()的别名 coutn mendl;return 0;,字符串处理in c&c+功

4、能的三种实现,以字符串的比较功能看c+实现比c实现的直观C风格#include int main()char*sa=test;char sb80;scanf(“%s”,sb);if(!strcmp(sa,sb)printf(Right!n);elseprintf(Guess again!n);,字符串处理in c&c+功能的三种实现,字符串的比较 C+风格=!=#include#include using namespace std;int main()string s;char cs80;gets(cs);getline(cin,s);if(cs=s)cout s)cout“s endl;e

5、lsecout cs s endl;,字符串处理in c&c+功能的三种实现,以字符串的拼接功能看c+实现比c实现的普适(重载机制)可用于string 与字符数组和单个字符的拼接#include#include#include using namespace std;int main()string s;s=changed;char b20=yes;s=s+b;cout s endl b endl;,字符串处理in c&c+功能的三种实现,以字符串的赋值看c+实现比c实现的内存透明性 string s1=“yes”;s2=“no”;s2=s1;#include#include int main

6、()char str1=Sample string;char str240;char str340;strcpy(str2,str1);strcpy(str3,copy successful);printf(str1:%snstr2:%snstr3:%sn,str1,str2,str3);需要特别注意溢出的函数 strcpy strcat,字符串处理in c&c+功能的三种实现,查找（获得）/添加/删除/替换（特定位置的）一个特定字串/一段区间查找/添加/删除/替换 一个特定字符/一个索引位置的字符strchr(),strstr(),strpbrk().find(),insert(),repl

7、ace(),erase(),append().讨论：Do we need to reinvent the wheel?,字符串处理in c&c+两个问题,1.字符串的输入和输出字符串往往对应于行或词行适用函数gets,fgetsputs,fputs其中gets有溢出危险 fgets对字符串结尾的n予以保留puts,fputs功能相似，都是削掉0,加上ngetline,cin.getline词适用函数 scanf,printfcin,cout综合 istringstream,字符串处理in c&c+两个问题,2.字符数组与指针的关系常量和变量对数组不能使用增量运算符，因为增量运算符意味着重新赋值

8、；不能对指针指向的常量字符串进行修改；字符指针可以重新赋值；字符数组不能；字符数组可以通过它改变其中元素，字符指针不能；可以将数组指定给指针，反之不能.#include int main(void)char sz1=“I Love You,LP”;char*sz2=“I Love You,LG”;/此时“I Love You,LG”表示常量字符串 int i;/指针和数组都可以使用数组符号for(i=0;i6;i+)putchar(sz1i);putchar(n);for(i=0;i6;i+)putchar(sz2i);putchar(n);,字符串处理in c&c+两个问题,/指针和数组都可

9、以使用指针加法for(i=0;i6;i+)putchar(*(sz1+i);putchar(n);for(i=0;i6;i+)putchar(*(sz2+i);putchar(n);/但是只有指针可以使用增量运算符while(*(sz2)!=0)putchar(*(sz2+);putchar(n);/对数组使用增量运算符会发生错误/*while(*(sz1)!=0)putchar(*(sz1+);putchar(n);*/,字符串处理in c&c+两个问题,/可以改变字符数组变量中的任意字母sz11=t;puts(sz1);/不能对指针指向的字符串作此种修改,这样修改之后数据就乱了/sz21=

10、t;/puts(sz2);/可以将数组指定给指针(实际上是将数组的首地址指定给该指针)，反之则不行sz2=sz1;while(*(sz2)!=0)putchar(*(sz2+);putchar(n);,POJ 2689,大小写字母互换 Description把一个字符串中所有出现的大写字母都替换成小写字母，同时把小写字母替换成大写字母。Input输入一行：待互换的字符串。Output输出一行：完成互换的字符串（字符串长度小于80）。Sample InputIf so,you already have a Google Account.You can sign in on the right.S

11、ample OutputiF SO,YOU ALREADY HAVE A gOOGLE aCCOUNT.yOU CAN SIGN IN ON THE RIGHT.,POJ 2689,#include#include using namespace std;int main()string s;getline(cin,s);for(int i=0;i=A,POJ 2690,Description对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。在字符串中，单词之间通过空白符分隔，空白符包括：空格()、制表符(t)、回车符(r)、换行符(n)。Input输入一行

12、：待处理的字符串（长度小于80）。Output输出一行：转换后的字符串。Sample Inputif so,you already have a google account.you can sign in on the right.Sample OutputIf So,You Already Have A Google Account.You Can Sign In On The Right.,POJ 2690,#include#include using namespace std;int main()string s,t;getline(cin,s);int i=0;bool head=

13、true;while(i!=s.size()if(si=97,POJ 2880,句中最长的单词 Description输入一个英文句子，长度不超过40个字符。编写程序，输出句子中最长的一个单词。Input长度不超过40的字符串Output句中最长的单词Sample InputThis is a test sentence Sample Outputsentence Hint1.输入只有一个句子，不需使用while 2.若句尾有标点，则标点和最后一个单词可看成是一个单词，可以不用作额外判断 3.假设句中最长的单词只有一个,#include#include#include using namesp

14、ace std;int main()string s,w,re;int big=0;getline(cin,s);istringstream stream(s);while(streamw)if(w.size()big)big=w.size();re=w;coutreendl;,POJ 2880,POJ 2927,Description判断一行字符串中的数字出现的个数。Input输入只有一行。输入一个字符串，该字符串中可以包含&$#*任何符号以及空格。输入以回车结束。Output有多行。输出该字符串中每个出现过的数字，然后在冒号“:”后面输出该数字出现的次数。按数字大小，从小到大的顺序输出。一

15、行输出一个数字及其出现次数。没有出现过的数字不输出。Sample Inputldksfj857ld*&%&%00000 138*0055end Sample Output0:5 5:1 7:1 8:1 0:2 1:1 3:1 5:2 8:1,#include int main()char s200;while(fgets(s,200,stdin)int a10=0;char*p=s;while(*p!=n)if(*p=0,POJ 2927,排序,内排序和外排序时空代价分析三种O（n2）级别的排序及代码实现插入排序冒泡排序选择排序Shell 排序分治法排序（快速排序 归并排序）堆排序桶式排序 基

16、数排序例题 POJ 2871 略,插入排序,InsertSort(int Array,int n)for(int i=1;i0;j-)if(ArrayjArrayj-1)swap(Array,j,j-1);else break;,冒泡排序,BubbleSort(int Array,int n)/第i个记录冒泡for(int i=1;i=i;j-)if(ArrayjArrayj-1)swap(Array,j,j-1);,直接选择排序,SelectionSort(Record Array,int n)for(int i=0;in-1;i+)/首先假设记录i就是最小的int Smallest=i;/

17、开始向后扫描所有剩余记录for(int j=i+1;jn;j+)/如果发现更小的记录，记录它的位置if(ArrayjArraySmallest)Smallest=j;/将第i小的记录放在数组中第i个位置swap(Array,i,Smallest);,快速排序算法思想,快速排序是基于交换排序的一种算法在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成“左子序列K右子序列”。再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止.分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：例如，可取左

18、边第1个元素为分界点、取中点A（left+right）/2为分界点、或选取最大和最小值的平均值为分界点等。库函数：void qsort(void*base,size_t num,size_t size,int(*comparator)(const void*,const void*);,POJ 1321 棋盘问题,Description在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。每组数据的第一行是两个正整数，

19、n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。n=8,k=n 当为-1-1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中#表示棋盘区域，.表示空白区域（数据保证不出现多余的空白行或者空白列）。,POJ 1321 棋盘问题(cont.),Output对于每一组数据，给出一行输出，输出摆放的方案数目C（数据保证C231）。Sample Input2 1#.#4 4.#.#.#.#.-1-1 Sample Output2 1,#include using namespace std;int n,k,me;bool map88,usedy8;voi

20、d Try(int x,int m)for(int i=m;in;i+)/处理第i行 if(n-ik-x+1)break;/如果剩下的行数少于剩下的棋子数结束判断 for(int j=0;jn;j+)/对广义棋盘区域内每个位置进行判断 if(!usedyj)/清除标记位 回溯,int main()while(cinnk)me=0;/对每一组初始化方案数 if(n=-1)break;for(int i=0;itmp;mapij=tmp=#;/如果属于棋盘区域 mapij则等于1 usedxi=usedyi=0;初始化占用矩阵 Try(1,0);/将第一枚棋子放在第零行 coutmeendl;,回

21、溯,回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。,四皇后问题,解空间树,树中的每一个结点确定所求解问题的一个问题状态（problem states）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）是这样的一些解状态S，对于这些解状态而言

22、，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state space tree),四皇后问题的解空间树,四皇后问题的状态空间树上共有24个叶结点(4!),就是问题的所有可能解树的内部结点代表问题的部分解例如36为部分解(x1,x2,x3)=(3,1,2)结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回溯方式遍历搜索的次序,原理描述回溯法的基本思想,基本思想：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数

23、用约束函数在扩展结点处剪去不满足约束的子树；对于优化问题，还可以用限界函数(Bounding Function)处理那些实际上不可能产生所需解的活结点也就是剪去得不到最优解的子树。递归回溯vs 迭代回溯,递归回溯通常解法,void backtrack(int t)if(t=n)output(x);/tn时，算法已经搜索到叶结点elsefor(int i=f(n,t);i=g(n,t);i+)/f()和g():当前扩展点子树待处理的起点与终点xt=h(i);设置xt所涉及的标记;/h()表示当前扩展点处xt的第i个可选值if(constraint(t)回溯，抹去Xk涉及的标记；,39,递 归 算

24、 法 举 例四皇后问题,40,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,41,在88的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：（1）不在棋盘的同一行；（2）不在棋盘的同一列；（3）不在棋盘的同一对角线上。因此可以推论出，棋盘共有8行，每行有且仅有一个皇后，故至多有8个皇后。这8个皇后每个应该放在哪一列上是解该题的任务。我们还是用试探的方法“向前走，碰壁回头”的策略。这就是“回溯法”的解题思路。,42,1、定义Try(i)试探放第 i 行上的皇后。2、讨论将第 i 行上的皇后放在 j 列位置上的安全性。我们可以逐行地放每一个皇

25、后，因此，在做这一步时，假定第 i 行上还没有皇后，不会在行上遭到其它皇后的攻击。只考虑来自列和对角线的攻击。我们定义 q(i)=j 表示第 i 行上的皇后放在第 j 列，一旦这样做了，就要考虑第 i 个皇后所在的列不安全了，这时让 C j=false，同时，要考虑通过(i,j)位置的两条对角线也不安全了。分析看出从左上到右下的对角线上的每个位置都有 i j=常数 的特点；从左下到右上的对角线上的每个位置都有 i+j=常数 的特点。,如何降低难度？,先讨论四皇后问题 目的是 降低规模,降低难度,寻找解题规律之后再回到原题的解法再一点是从第一行开始放,按顺序一行一行放可以不用判行是否安全,只判列

26、和对角线是否安全,判列是否安全问题可以使用数组 j=5,定义 C j;true 第 j 列未放皇后 C j=false 第 j 列已放皇后 j=1,2,3,4 下面的难点是判对角线是否安全问题,Q,Q,A Try(i)j=1 2.4,Q,A Try(i)j=1 2.4,Q,Q,Q,A Try(i)j=1 2.4,Q,Q,A Try(i)j=1 2.4,Q,A Try(i)j=1 2.4,Q,Q,Q,1 2 3 4 1 2 3 4 1 Q 1 Q 2 Q 2 Q 3 3 Q 4 4 1 2 3 4 1 2 3 4 1 Q 1 Q 2 Q 2 Q 3 Q 3 Q 4 Q 4 Q,重点研究怎样描述对

27、角线 j 2 1 2 3 4 3 1 i+j 4 2 i 5 3 6 4 7 8,j i-j i-j+5 1 2 3 4-3 2 1-2 3i 2-1 4 3 0 5 4 1 6 2 7 3 8,使用数组来描述对角线上是否安全定义 bool R 9 R k k=2,3,8 k=i+j i=1,2,4 j=1,2,4 描述从右上至左下的对角线是否安全 数据类型为布尔型 true-安全 false-不安全,定义 bool L 9 L k k=2,3,8 k=i j+5 i=1,2,4 j=1,2,4 描述从左上至右下的对角线是否安全 数据类型为布尔型 true-安全 false-不安全,利用这个特

28、点，我们可以令L i-j+5=false;R i+j=false;来表示在(i,j)位置放皇后之后，通过该位置的两条对角线上不安全了。这样我们得出了在(i,j)位置放皇后的安全条件为nq=C j&L i-j+5&R i+j,有了上述铺垫之后我们就可以设计算法了首先先想到递归算法画出与或结点图,A Try(i)j=1 2.4 Lp,Lp 不安全 安全什麽也不做qi=j;cj=true;Cj=false;Ri+j=true;Li-j+5=false;i4 i=4 Li-j+5=true;Ri+j=false;Try(i+1);Num+;输出,参考程序,60,/*/*程 序：6_9.cpp*/*主要

29、功能：四皇后问题*/*#include/预编译命令using namespace std;const int Normalize=5;/定义常量，用来统一数组下标int Num=1;/整型变量，记录方案数int q5;/记录4个皇后所占用的列号bool C5;/C1C4，布尔型变量，当前列是否安全bool L9;/L2L8，布尔型变量，(i-j)对角线是否安全bool R9;/R2R8，布尔型变量，(i+j)对角线是否安全,void Try(int i)/被调用函数int j;/循环变量，表示列号int k;/临时变量for(j=1;j=4;j+)/循环 if(Cj=true)&(Ri+j)=

30、true)&(Li-j+Normalize=true)/表示第i行，第j列是安全的,62,qi=j;/第一件事，占用位置(i,j)Cj=false;/修改安全标志，包括所在列和两个对角线 Li-j+Normalize=false;Ri+j=false;if(i4)/第二件事，判断是否放完8个皇后/未放完4个皇后Try(i+1);/则继续放下一个 else/已经放完4个皇后 Num+;/方案数加1cout 方案 Num：;/输出方案号for(k=1;k=4;k+)cout qk;/输出具体方案cout endl;/换行 Cj=true;/第三件事，修改安全标志，回溯Li-j+Normalize=true;Ri+j=true;,63,/循环结束/Try函数结束int main()/主函数int i;/循环变量Num=0;/方案数清零for(i=1;i5;i+)/置所有列为安全Ci=true;for(i=0;i9;i+)/置所有对角线为安全 Li=true;Ri=true;Try(1);/递归放置4个皇后，从第一个开始放 return 0;,推荐资源：,谢谢！,