字符串字符串,排序排序,(回溯回溯)计算概论习题课计算概论习题课高圣亮2007-11-27gslnet.pku.edu.cn撩锰邯韦滦典挝膛朋示勤购切酋僻殷关阅荣秦党阁淋压灌倪躁皖吹溢尿缕字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+提纲概论字符串处理中经常用到的功能功能的三种实现方法：C风格字符数组遍历C风格库函数C+风格库(字符串类)与字符串处理相关的两个重要问题字符串的输入和输出字符数组与指针的关系筛帽屏哮绩镀棵腰世术糯炙血古皖澈填贡颠梭迂撅攘羚旷嘲缸胰唬酵撑肺字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+概论存在形式c:以null结尾的字符数组c+：类，对象特点c+的方法更直观c的方法实现效率更高c/c+字符串表达方式的的相互转化strings(“example”);s.c_str();蚌酥颠小孰胞椰严氏帮亡伯诸荧即闲矿雁黍射博那启票佛匈棵惟延蔷香耸字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+常用功能赋值判断一个字符串的长度比较两个字符串（如何界定比较？）字符串的拼接查找（获得）/添加/删除/替换（特定位置的）一个特定字串/一段区间查找/添加/删除/替换一个特定字符/一个索引位置的字符靶泣画徐壹屋哭迁广瘴勘担寸耶壕彰困困钾鹰啊通全瞬盅波铣憋坑矣横旁字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现以获得一个字符串的长度为例：以获得一个字符串的长度为例：1.C风格风格字符数组遍历字符数组遍历#include#includeintlength(char*);intmain()charszInput256;printf(“Enterasentence:”);gets(szInput);printf(“Thesentenceenteredis%ucharacterslong.n”,length(szInput);/strlen()intlength(char*s)intcount=0;while(*s+!=0)count+;returncount;狡箍貉无畜屡沥立侧风候堑敝岁吐侠虏痛用帐纹忽娃坷达觅碾晃小会腰运字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现2.c风格处理strlen()函数返回从给定指针到终结的0中间的字符个数3.c+风格处理size(),length()成员函数返回整个字符串的长度#include#includeusingnamespacestd;intmain()strings;getline(cin,s);intn=s.size();intm=s.length();/length()是size()的别名coutnmendl;return0;抄怨嫉滇玩嘴揉媚读术颖燕痈矿哺入渺匈彤濒屉诣惺迎镊耐饥趋桓茎迅任字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现以字符串的比较功能看c+实现比c实现的直观C风格#includeintmain()char*sa=test;charsb80;scanf(“%s”,sb);if(!strcmp(sa,sb)printf(Right!n);elseprintf(Guessagain!n);闯倦音桑奸法姬沂抗警彤猛刽嘉锡菜纺邵敞很何队邢鹊盔手犹妄挑讫前豪字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现字符串的比较C+风格=!=共六个重载的操作符#include#include#includeusingnamespacestd;intmain()strings;charcs80;gets(cs);getline(cin,s);if(cs=s)coutEqual!“s)coutcs“sendl;elsecoutcssendl;替赠粮炯租庸佐叔哗仇嘉其赊圆幕豹革穴沁檄颇前俏伴癸讼睬暗凡奸讲武字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现以字符串的拼接功能看c+实现比c实现的普适(重载机制)可用于string与字符数组和单个字符的拼接#include#include#includeusingnamespacestd;intmain()strings;s=changed;charb20=yes;s=s+b;coutsendlbendl;碎碑醋帝畸圾云弹十锗钦表汹郧劲夏闰庙买兽抬藩旦奸帛闯供惮投叫隋夯字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现以字符串的赋值看以字符串的赋值看c+实现比实现比c实现的内存透明性实现的内存透明性strings1=“yes”;s2=“no”;s2=s1;#include#includeintmain()charstr1=Samplestring;charstr240;charstr340;strcpy(str2,str1);strcpy(str3,copysuccessful);printf(str1:%snstr2:%snstr3:%sn,str1,str2,str3);需要特别注意溢出的函数需要特别注意溢出的函数strcpystrcat恩讥站穗眉盅绝虽画降淤笛土捕女坐婿沾喂宴吕铁蹿雾袍冈郡恐响甲雇豪字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+功能的三种实现查找（获得）/添加/删除/替换（特定位置的）一个特定字串/一段区间查找/添加/删除/替换一个特定字符/一个索引位置的字符strchr(),strstr(),strpbrk().find(),insert(),replace(),erase(),append().讨论：Doweneedtoreinventthewheel?件怂姿栅毁握颖楷歉琐丈汝拿聋趾命材涩跃笑吮宏伙速啦座下矿亏哲秉尝字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+两个问题1.字符串的输入和输出字符串往往对应于行或词行适用函数gets,fgetsputs,fputs其中gets有溢出危险fgets对字符串结尾的n予以保留puts,fputs功能相似，都是削掉0,加上ngetline,cin.getline词适用函数scanf,printfcin,cout综合istringstream搓眯藕负鳞归额泥暑崎盒蜂族威境般掣饰讲伯咒漂篡陶拦侄澜唾情拈诺远字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+两个问题2.字符数组与指针的关系字符数组与指针的关系常量和变量常量和变量对数组不能使用增量运算符，因为增量运算符意味着重新赋值；对数组不能使用增量运算符，因为增量运算符意味着重新赋值；不能对指针指向的常量字符串进行修改；不能对指针指向的常量字符串进行修改；字符指针可以重新赋值；字符数组不能；字符指针可以重新赋值；字符数组不能；字符数组可以通过它改变其中元素，字符指针不能；字符数组可以通过它改变其中元素，字符指针不能；可以将数组指定给指针，反之不能可以将数组指定给指针，反之不能.#includeintmain(void)charsz1=“ILoveYou,LP”;char*sz2=“ILoveYou,LG”;/此时此时“ILoveYou,LG”表示常量字符串表示常量字符串inti;/指针和数组都可以使用数组符号指针和数组都可以使用数组符号for(i=0;i6;i+)putchar(sz1i);putchar(n);for(i=0;i6;i+)putchar(sz2i);putchar(n);纫述盯轿吻姓栅锹脖仟闺浑魔又始如欣咆朱榔胀垄牟收矾塘伸组刽括磋刑字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+两个问题/指针和数组都可以使用指针加法指针和数组都可以使用指针加法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);*/夕唾摸栏媳堕焦豢览垦坪础藉涧靠话省故力膊瓮铺啥谬迁赎考友甄鸿世宜字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件字符串处理inc&c+两个问题/可以改变字符数组变量中的任意字母sz11=t;puts(sz1);/不能对指针指向的字符串作此种修改,这样修改之后数据就乱了/sz21=t;/puts(sz2);/可以将数组指定给指针(实际上是将数组的首地址指定给该指针)，反之则不行sz2=sz1;while(*(sz2)!=0)putchar(*(sz2+);putchar(n);印纯别恿捍为剔精姑戮市厦翠尼辖湃痊欺幢甄房谋抨屑刊呕矣吓告妇匠汽字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2689大小写字母互换Description把一个字符串中所有出现的大写字母都替换成小写字母，同时把小写字母替换成大写字母。Input输入一行：待互换的字符串。Output输出一行：完成互换的字符串（字符串长度小于80）。SampleInputIfso,youalreadyhaveaGoogleAccount.Youcansigninontheright.SampleOutputiFSO,YOUALREADYHAVEAgOOGLEaCCOUNT.yOUCANSIGNINONTHERIGHT.柿米崇爪冷悼摆牙缘驾细农疾滥舟俐斡牟级杠锻爷劳口泽垃遇啡吓呼桔畴字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2689#include#includeusingnamespacestd;intmain()strings;getline(cin,s);for(inti=0;i=A&si=a&si=z)si-=a-A;coutsendl;画铺摧贬搬媒科笋须漏附打鲸况挚挥咖液憎煤彦闯荔逼糖吃二渠扁搐公提字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2690Description对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。在字符串中，单词之间通过空白符分隔，空白符包括：空格()、制表符(t)、回车符(r)、换行符(n)。Input输入一行：待处理的字符串（长度小于80）。Output输出一行：转换后的字符串。SampleInputifso,youalreadyhaveagoogleaccount.youcansigninontheright.SampleOutputIfSo,YouAlreadyHaveAGoogleAccount.YouCanSignInOnTheRight.窥战徘蒸怀刮扶镣炳刚规磕民苟刑板吧刑真医鲁蝴桐蝎馆案园罗圃嗅躲诧字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2690#include#includeusingnamespacestd;intmain()strings,t;getline(cin,s);inti=0;boolhead=true;while(i!=s.size()if(si=97&si=122&head=true)t+=(char)(si-32);head=false;elseif(si=|si=t|si=r)head=true;t+=si;else t+=si;head=false;i+;couttendl;堆妈袋募吊长萌善箔装麻叙桩悠毡佃等隙去昂淬储橙动郧嗓王酒疼销超军字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2880句中最长的单词Description输入一个英文句子，长度不超过40个字符。编写程序，输出句子中最长的一个单词。Input长度不超过40的字符串Output句中最长的单词SampleInputThisisatestsentenceSampleOutputsentenceHint1.输入只有一个句子，不需使用while2.若句尾有标点，则标点和最后一个单词可看成是一个单词，可以不用作额外判断3.假设句中最长的单词只有一个尉鸳善稀淬茶熟握足醚弄岸材毗亥服江硅末囊熔预亿王叶掷绅拎会肮译艇字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件#include#include#includeusingnamespacestd;intmain()strings,w,re;intbig=0;getline(cin,s);istringstreamstream(s);while(streamw)if(w.size()big)big=w.size();re=w;coutreendl;POJ2880摩酪啤濒果遇服臼绍担绸鞠讨嘛彻暑羽撵返金法翅昭媒贾榷输综索旋糯悬字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ2927Description判断一行字符串中的数字出现的个数。Input输入只有一行。输入一个字符串，该字符串中可以包含&$#*任何符号以及空格。输入以回车结束。Output有多行。输出该字符串中每个出现过的数字，然后在冒号“:”后面输出该数字出现的次数。按数字大小，从小到大的顺序输出。一行输出一个数字及其出现次数。没有出现过的数字不输出。SampleInputldksfj857ld*&%&%00000138*0055endSampleOutput0:55:17:18:10:21:13:15:28:1绩崩轮谷蓟瑶芜挪嘲男扇栋因郴苛键含框茂焰疾彰隐樱拒悦私襟则沦曼柄字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件#includeintmain()chars200;while(fgets(s,200,stdin)inta10=0;char*p=s;while(*p!=n)if(*p=0&*p=9)a*p-0+;p+;for(inti=0;i10;i+)if(ai=0)continue;elseprintf(%d:%dn,i,ai);POJ2927烛誊秽跳疥匪秒或支蚤六稽闲舟硕郝饵俊汗外正宾大揩瀑善补膜歧谊台躬字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件排序内排序和外排序时空代价分析三种O（n2）级别的排序及代码实现插入排序冒泡排序选择排序Shell排序分治法排序（快速排序归并排序）堆排序桶式排序基数排序例题POJ2871略娘谎考蠕酱烟耘阴瘩波球货旅裂历嘴网炕球毯镑柴捆挡愈蜀鞍霓排菠药寄字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件插入排序InsertSort(intArray,intn)for(inti=1;i0;j-)if(ArrayjArrayj-1)swap(Array,j,j-1);elsebreak;过帖自几惦赤鲜们狗伤滑阎伶痛朽丽肉仁桨肪汕潭愁要赞雄埋倡弹鸥勋撂字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件冒泡排序BubbleSort(intArray,intn)/第i个记录冒泡for(inti=1;i=i;j-)if(ArrayjArrayj-1)swap(Array,j,j-1);堪博啸厂本畜口觅虞化谊络妊槐腮糜止吟伍或奇钱贝逃竖境屑秦炭媒熙联字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件直接选择排序SelectionSort(RecordArray,intn)for(inti=0;in-1;i+)/首先假设记录i就是最小的intSmallest=i;/开始向后扫描所有剩余记录for(intj=i+1;jn;j+)/如果发现更小的记录，记录它的位置if(ArrayjArraySmallest)Smallest=j;/将第i小的记录放在数组中第i个位置swap(Array,i,Smallest);押原握勋旧黔妇饲乡泥苹锑斯干稽脆晃奸蛔汐垂涯趟科骚摹块恼品孪角信字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件快速排序算法思想快速排序是基于交换排序的一种算法快速排序是基于交换排序的一种算法在待排序序列中按某种方法选取一个元素在待排序序列中按某种方法选取一个元素K，以它为分界点，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成则在右边。形成“左子序列左子序列K右子序列右子序列”。再分别对左、右。再分别对左、右两部分实施上述分解过程，直到各子序列长度为两部分实施上述分解过程，直到各子序列长度为1，即有序为，即有序为止止.分界点元素值分界点元素值K的选取方法不同，将构成不同的排序法，也将的选取方法不同，将构成不同的排序法，也将影响排序的效率：例如，可取左边第影响排序的效率：例如，可取左边第1个元素为分界点、取中个元素为分界点、取中点点A（left+right）/2为分界点、或选取最大和最小值的平均为分界点、或选取最大和最小值的平均值为分界点等。值为分界点等。库函数：库函数：voidqsort(void*base,size_tnum,size_tsize,int(*comparator)(constvoid*,constvoid*);荐唁镑吹制平亮侄翌卸芦灰昼弗祷吴了搽冗库占饼傅闯坏裳蓉缘山喂抬赤字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ1321棋盘问题Description在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。每组数据的第一行是两个正整数，nk，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。n=8,k=n当为-1-1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中#表示棋盘区域，.表示空白区域（数据保证不出现多余的空白行或者空白列）。沈摇话却联槐步芥散析矢瘩棚毒袁最仿纠惊垣热诚肩悼注舍疾芭牺锰敖豢字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件POJ1321棋盘问题(cont.)Output对于每一组数据，给出一行输出，输出摆放的方案数目对于每一组数据，给出一行输出，输出摆放的方案数目C（数据保证（数据保证C231）。）。SampleInput21#.#44.#.#.#.#.-1-1SampleOutput21辞奏政坑崔欢顿脐损紧镁啤禁泼伤唇佃旷紊魁嫂妻与赴菱委智央腰魁立赃字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件#includeusingnamespacestd;intn,k,me;boolmap88,usedy8;voidTry(intx,intm)for(inti=m;in;i+)/处理第处理第i行行if(n-ik-x+1)break;/如果剩下的行数少于剩下的棋子数结束判断如果剩下的行数少于剩下的棋子数结束判断for(intj=0;jn;j+)/对广义棋盘区域内每个位置进行判断对广义棋盘区域内每个位置进行判断if(!usedyj)&mapij)/如果位置在有效区域内并且纵列上没有被占如果位置在有效区域内并且纵列上没有被占用的情况用的情况usedyj=1;/标记占用标记占用if(xnk)me=0;/对每一组初始化方案数if(n=-1)break;for(inti=0;in;i+)for(intj=0;jtmp;mapij=tmp=#;/如果属于棋盘区域mapij则等于1usedxi=usedyi=0;初始化占用矩阵Try(1,0);/将第一枚棋子放在第零行coutme=n)output(x);/tn时，算法已经搜索到叶结点elsefor(inti=f(n,t);i=g(n,t);i+) /f()和g():当前扩展点子树待处理的起点与终点xt=h(i);设置xt所涉及的标记;/h()表示当前扩展点处xt的第i个可选值if(constraint(t)&bound(t)/constraint()是当前扩展结点处的约束函数；/bound()是当前扩展结点处的限界函数backtrack(t+1);回溯，抹去Xk涉及的标记；李宛毒磅孟滁幻勾镰疯祸螟杉足辱他猫凛炕唁鳃约嫂蓑否眨因严诫肤焦绘字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件递递 归归 算算 法法 举举 例例四皇后问题四皇后问题蝎贸肇旬纪犊壮颊痊歧修驰郭甲躇柯拾醚韧肇办唐绦默幂捍嗽寨榜铸桓裁字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件39 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8畴暑碗债伏汀蔗枣脸乘什诗箍描柠艰屠槛燕库谁变续咐沾浓囤挑嫡瞧疾鹊字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件40 在在88的棋盘上，放置的棋盘上，放置8个皇后（棋子），使两两个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：要满足： （1）不在棋盘的同一行；）不在棋盘的同一行； （2）不在棋盘的同一列；）不在棋盘的同一列； （3）不在棋盘的同一对角线上。）不在棋盘的同一对角线上。 因此可以推论出，棋盘共有因此可以推论出，棋盘共有8行，每行有且仅有一行，每行有且仅有一个皇后，故至多有个皇后，故至多有8个皇后。这个皇后。这8个皇后每个应该放个皇后每个应该放在哪一列上是解该题的任务。我们还是用试探的方在哪一列上是解该题的任务。我们还是用试探的方法法“向前走，碰壁回头向前走，碰壁回头”的策略。这就是的策略。这就是“回溯法回溯法”的的解题思路。解题思路。墅黑君蚤衅斡儿唤疮芯蓝拳缮虾楚垦念瘪素蛀奸昏野筒夯化窘鲜粳著奋隧字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件411、定义、定义Try( i )试探放第试探放第 i 行上的皇后。行上的皇后。2、讨论将第、讨论将第 i 行上的皇后放在行上的皇后放在 j 列位置上的安全性。列位置上的安全性。我们可以逐行地放每一个皇后，因此，在做这一步我们可以逐行地放每一个皇后，因此，在做这一步时，假定第时，假定第 i 行上还没有皇后，不会在行上遭到其它行上还没有皇后，不会在行上遭到其它皇后的攻击。只考虑来自列和对角线的攻击。我们皇后的攻击。只考虑来自列和对角线的攻击。我们定义定义 q( i ) = j 表示第表示第 i 行上的皇后放在第行上的皇后放在第 j 列列，一，一旦这样做了，就要考虑第旦这样做了，就要考虑第 i 个皇后所在的列不安全个皇后所在的列不安全了，这时让了，这时让 C j = false，同时，要考虑通过，同时，要考虑通过( i, j ) 位位置的两条对角线也不安全了。分析看出从左上到右置的两条对角线也不安全了。分析看出从左上到右下的对角线上的每个位置都有下的对角线上的每个位置都有 i j = 常数常数 的特点；的特点；从左下到右上的对角线上的每个位置都有从左下到右上的对角线上的每个位置都有 i + j = 常常数数 的特点。的特点。胺袄邮梢佛稗诊煌速半潭荡壁谜嗓芜程污登伙淑盅画靡严官婶搓稠技支援字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件42如何降低难度？如何降低难度？先讨论四皇后问题目的是降低规模,降低难度,寻找解题规律之后再回到原题的解法再一点是从第一行开始放,按顺序一行一行放可以不用判行是否安全,只判列和对角线是否安全忱莆尺交急蝶痕怎贷汰习背军目础迂杨聋啤帘耳凰彤耐忧二鹃决幻但耽方字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件判列是否安全问题判列是否安全问题可以使用数组可以使用数组j=5,定义定义Cj;true第第j列未放皇后列未放皇后Cj=false第第j列已放皇后列已放皇后j=1,2,3,4下面的难点是判对角线是否安全问题下面的难点是判对角线是否安全问题辉词氟将挠纂幼碌楼棱阳龚乱食铱杯晓冻报基肠庙涎变增施峭虑激洲滑钩字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件QQQQ A Try( i )A Try( i ) j = 1 2 . . . 4 j = 1 2 . . . 4酿掺拦访瓮汝廊畸鸣畸竖沤喷誉窜竖谢践炉贿碳将裔磅廷堵鸦耪艰距砍含字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件QQ A Try( i )A Try( i ) j = 1 2 . . . 4 j = 1 2 . . . 4QQQQ堰脂戳睦邵姑热溜妄邯陆从顽赦羡灰贝怀腆掀娘潭北阵佳掌瞻室派棵天泞字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件QQ A Try( i )A Try( i ) j = 1 2 . . . 4 j = 1 2 . . . 4QQ姐角捣打格擒囚弥需炕梭球盆始们算会涌岩艇捆辅皮辙侦迄拦继刺夷穷倦字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件QQ A Try( i )A Try( i ) j = 1 2 . . . 4 j = 1 2 . . . 4遏锦鞍突熬榆市恍瑶踞焰护厩改拭米似葬踏书布摘酷馅睹咆锣秩燃刨致绒字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件QQ A Try( i )A Try( i ) j = 1 2 . . . 4 j = 1 2 . . . 4QQQQQQ呀蘸勤须截仍斜枢荣富恤储廖城摩袖驶花窝霸畦刽睬热神桌道样拂勋钠患字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件123412341Q1Q2Q2Q33Q44123412341Q1Q2Q2Q3Q3Q4Q4Q硝佑灾摘沁苔傻郑舆屋乘抢晾语缩卑蔓窗脓魔阵翁乳稽蛛柜容缚荚持霜泪字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件重点研究怎样描述对角线j2123431i+j42i536478稍轻措撵碘坛爽锑宾阴拾蓬完尹柞款篓薛汾冶簧眺寓刹亚蔫剐巴伴绽砸谐字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件ji-ji-j+51234-321-23i2-143054162738减藤晦纳册确论藻滇抵鳞躯猜睬艘洪妊龋护颖冤淘蚤澳页贩扛吾艰霹仟我字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件使用数组来描述对角线上是否安全使用数组来描述对角线上是否安全定义定义boolR9Rkk=2,3,8k=i+ji=1,2,4j=1,2,4描述从右上至左下的对角线是否安全描述从右上至左下的对角线是否安全数据类型为布尔型数据类型为布尔型true-安全安全false-不安全不安全令声绑莲消世豫布洁磐健柯西鸵鸣琼讲川胆峻唯寥巧细谈洒坪啡梁藩钓瑞字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件定义定义boolL9Lkk=2,3,8k=ij+5i=1,2,4j=1,2,4描述从左上至右下的对角线是否安全描述从左上至右下的对角线是否安全数据类型为布尔型数据类型为布尔型true-安全安全false-不安全不安全狂揍拯蹈荚谈泣峡低蟹竭恭邹沈庸佯沦变隶兼绰娶气姨民粥衬匿萨透交茎字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件利用这个特点，我们可以令利用这个特点，我们可以令Li-j+5=false;Ri+j=false;来表示在来表示在(i,j)位置放皇后之后，通过该位置放皇后之后，通过该位置的两条对角线上不安全了。位置的两条对角线上不安全了。这样我们得出了在这样我们得出了在(i,j)位置放皇后的安位置放皇后的安全条件为全条件为nq=Cj&Li-j+5&Ri+j腆消咋萤订谍卜魔胁兢及惟尘聪涧理罢坚吊攀烛摹挂拭擂廉跃陀粹盂掌惟字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件有了上述铺垫之后我们就可以设计算法有了上述铺垫之后我们就可以设计算法了了首先先想到递归算法画出与或结点图首先先想到递归算法画出与或结点图司淄灶憎束成涉颜舒尺晒俞嘘剖蚌弥瓷进疟霖托摸咕幽揖殖缉寥兰水何早字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件ATry(i)j=12.4Lp裂酱厉拔幌窄析滦颖倾战孩昨母媒几孺棋纵著晃灶毒裳驯憨映协壕感篱坐字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件Lp不安全不安全安全安全什麽也不做什麽也不做qi=j;cj=true;Cj=false;Ri+j=true;Li-j+5=false;i4i=4Li-j+5=true;Ri+j=false;Try(i+1);Num+;输出输出夺牛藉拇皋浪可亦湖谰捕厩丈锣绿乓明释羡东圣佣狭惋猎骨距争辑橱吼顽字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件 参考程序参考程序掉治闻虞鸦省经蓉塑滚斧俄奏掇鸥异滑歹扛拨守签镑遣男杠蕊泞童忙狗簇字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件/ */ * 程程 序：序：6_9.cpp */ * 主要功能：四皇后问题主要功能：四皇后问题 */ *#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)对角线是否安全对角线是否安全榴潭变甘票很纽夕贷耽暗匪签抖巍星漫拾嘎峨缄菜酋绵臼蘸椽拼使声汽酥字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件60voidTry(inti)/被调用函数被调用函数intj;/循环变量，表示列号循环变量，表示列号intk;/临时变量临时变量for(j=1;j=4;j+) /循环循环if(Cj=true)&(Ri+j)=true)&(Li-j+Normalize=true)/表示第表示第i行，第行，第j列是安全的列是安全的撅队儡诣辛谭跺意任泳苍济了铭痰估诚崇往轰遣络靠冰岿涧衬撵澎代吊必字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件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;茨哆涩诌腐腕痴转涝崎影广缀各丫轻刁伞赌脊综养绍望小咆焦所凳肆豫氧字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件62/ 循环结束循环结束/ 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;钎统渣眨菇隙季擦聘搭锡紧封愉他绝喧截砸别惭剑峦软坷限闸地甜暗炊胶字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件63推荐资源：http:/cplusplus.comhttp:/db.pku.edu.cn/mzhang/DShttp:/db.pku.edu.cn/mzhang/DS/shixi/烛烂滞粒腹胃删楞肠铰封阻需缨娘皖阀池哺氧隅锣贵峙澜丹育掣淤拼敲拿字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件谢谢！涅仓诡深甘律咕气邢纱算詹钻烫塑家龚督心敦士惺呸爸臂扩探隧绑乔床簇字符串排序回溯计算概论习题课ppt课件字符串排序回溯计算概论习题课ppt课件