程序设计实习 第七讲 递归

《程序设计实习》课程(C++ProgrammingPractice)程序设计实习第七讲递归主讲教师：田永鸿[e-mail]://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年3月17日北京大学《程序设计实习》课程2内容提要关于作业中的若干问题递归的基本思想例题练习栈与递归作业北京大学《程序设计实习》课程3关于作业提交1、从作业布置之日起，下一周的周日24：00前提交的，起评分为10分如3月10日布置的作业，3月23日24：00前提交2、从作业布置之日起，下下一周的周日24：00前提交的，起评分为5分如3月10日布置的作业，3月30日24：00前提交3、之后提交的作业，不得分作业布置周起评10分起评5分起评0分北京大学《程序设计实习》课程4例2#includeiostream.h#includestdio.hvoidmain(){chartest1[1001],test2[1001],test3[1001];cin.getline(test1,1000,'a');scanf(%s,test2);cin.getline(test3,1000,'a');couttest1:test1endl;couttest2:test2;coutendl;couttest3:test3endl;}输入：qweabgdfdda北京大学《程序设计实习》课程5例2输出VisualStudio.Net/GCC/部分VisualC++6.0环境输出test1:qwetest2:bgtest3:dfddPressanykeytocontinue部分VisualC++6.0环境输出test1:qwetest2:dfdtest3:bgdPressanykeytocontinue原因：混用cin和scanf造成的错误北京大学《程序设计实习》课程6例3#includestdio.h#includeiostream.hvoidmain(){chartest1[10001],test2[1001],test3[1001];cin.getline(test1,10,'a');scanf(%c,&(test2[0]));cin.getline(test3,1000,'a');couttest1:test1;printf(test2:%c,test2[0]);coutendl;couttest3:test3endl;}输入：qwertabbbccccacbb北京大学《程序设计实习》课程7例3输出VisualStudio.Net/GCC/部分VisualC++6.0环境输出test1:qwerttest2:btest3:bbccccPressanykeytocontinue部分VisualC++6.0环境输出test2:ctest1:qwerttest3:bbbPressanykeytocontinue结论：1、不要混用iosteam和stdio的输入输出函数。2、使用cin.get(),cin.getline()经常出现问题，和缓冲区有关，有时需要使用fflush(stdin)清缓冲区后才能正常处理输入，所以建议不要使用。原因：混用cin和scanf、cout和printf造成的错误北京大学《程序设计实习》课程8二维数组的动态分配问题数组动态分配P=newT[N];如何动态分配二维数组？分配int**ptr=newint*[num1];for(inti=0;inum1;i++)ptr[i]=newint[num2];清除时反着来：for(inti=0;inum1;i++)delete[]ptr[i];delete[]ptr;北京大学《程序设计实习》课程9其他常见问题1.对于不好的编程习惯导致格式不清，最后使逻辑混乱的问题，逻辑混乱后出问题往往难以发现。建议仔细想好了程序的思路，在纸上画下流程图后再动手编写。2.由于功能代码过长过于复杂导致错误难以发现。建议尽量分而治之的解决问题。多使用函数，做到每个独立功能的代码段不超过50行，并写上注释。3.对输入数据的多样性估计不足，当数据不对时候，发生a[-1]越界这样的问题，有些越界后程序并没有runtimeerror错误非常隐蔽，对于每一个数组都应该检查分析它是否有可能出现越界错误。4.在代码中尽量减少精度误差如：result=a*b/c在计算机中和temp＝b/c;result=a*temp;运行结果并不是都是相同的。代码中做得先乘后除非常必要。如果不能做得先乘后除，那么务必在运算中使用double类型的变量保存中间结果。北京大学《程序设计实习》课程10其他常见问题5.直接使用整数表达式的值作为if（）的内容，如if（n％4）…，功力不够这样写的代码容易出错。而且一时间错误难以发现。建议取缔这样的编程风格，一律使用布尔表达式的值作为if（）的内容，如if（n％4＝＝0），使得逻辑尽量清晰。另外杜绝复杂的if条件，当情况复杂，建议多写几个判断分支。6.字符串声明的时候要注意留出保存字符串结束符’\0’的位置，所以编程时可以考虑声明一个大一点的空间以免越界。7.仍然有许多同学不会使用断点、debug等功能调试程序，应当尽快学会使用这些方便的工具帮助自己解决问题，这样可以事半功倍。8.除非特殊说明，测试题都是读入一行数据，输出一个结果，不必一次性读入全部数据，然后一次性输出所有结果。9.关于提交问题时WrongAnswer的问题。对于大部分问题而言，很多同学要么是没有考虑到一些边界数据，要么是在处理输入输出格式时出了问题。在遇到WrongAnswer时，首先考虑一下自己是不是有一些边界数据没有处理，然后再看看是不是完全符合题目的输入输出要求，尽量跳出自己写程序时的思路，这样会比较容易发现错误。北京大学《程序设计实习》课程11递归北京大学《程序设计实习》课程12递归的基本思想什么是递归？递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解。总体思想：将待求解问题的解看作输入变量x的函数f(x)通过寻找函数g,使得f(x)=g(f(x-1))并且已知f(0)的值，就可以通过f(0)和g求出f(x)的值．这样一个思想也可以推广到多个输入变量x,y,z等，x-1也可以推广到x-x1,只要递归朝着出口的方向走就可以了．北京大学《程序设计实习》课程13递归的基本思想递归的几个特点递归式：如何将原问题划分成子问题。递归出口：递归终止的条件，即最小子问题的求解，可以允许多个出口。界函数：问题规模变化的函数，它保证递归的规模向出口条件靠拢北京大学《程序设计实习》课程14例１：POJ2753菲波那契数列输入一个整数n，求菲波那契数列的第n项．算法：设第n项值为f(n)，则f(n)=f(n-1)+f(n-2)．已知f(1)=1，f(2)=1，则从第３项开始，可以用公式求．程序：intf(intn){if(n==1||n==2)return1;elsereturnf(n-1)+f(n-2);}北京大学《程序设计实习》课程15例２：POJ1664放苹果输入：m个苹果，n个盘子，问多少种不同放法．算法：设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论，当nm：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(nm)f(m,n)=f(m,m)当n=m：不同的放法可以分成两类：1、有至少一个盘子空着，即相当于f(m,n)=f(m,n-1);或2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n)=f(m-n,n).而总的放苹果的放法数目等于两者的和，即f(m,n)=f(m,n-1)+f(m-n,n)北京大学《程序设计实习》课程16例２：POJ1664放苹果（续）POJ1664程序intf(intm,intn){if(n==1||m==0)return1;if(nm)returnf(m,m);returnf(m,n-1)+f(m-n,n);}出口条件说明：当n=1时，所有苹果都必须放在一个盘子里，所以返回１；当没有苹果可放时，定义为１种放法；递归的两条路，第一条n会逐渐减少，终会到达出口n==1;第二条m会逐渐减少，因为nm时，我们会returnf(m,m)所以终会到达出口m==0．北京大学《程序设计实习》课程17例３：POJ2755神奇口袋给出小于40的正整数a1,a2……an，问凑出和为40有多少种方法。算法：设f(a1,a2……an,40,)为用a1,a2……an凑出40的方法数，考虑凑数的方法分为两类，用到a1和用不到a1,则有f(a1,a2……an,40)=f(a2……an,40-a1)+f(a2……an,40)这里考虑到在实现上函数的参数个数要统一，所以把a1，a2……an放到一个数组中，用numbers[]存放所有的整数，n表示数组中整数的个数，ith表示从数组中第ith个整数开始凑数，sum表示要凑出的总数，则上面的公式变为f(numbers,n,ith,sum)=f(numbers,n,ith+1,sum-numbers[ith])//用到ith+f(numbers,n,ith+1,sum)//不用ith北京大学《程序设计实习》课程18例３：POJ2755神奇口袋（续）在实现上有两种考虑：因为numbers,n与递归没有太大关系，可以考虑使用全局量；如果不使用全局量，而通过参数传递numbers,n，可以增强递归函数的独立性程序（将numbers,n设为全局量）intcount(intith,intsum){if(sum==0)return1;if(ith==n||sum0)return0;returncount(ith+1,sum-numbers[ith])+count(ith+1,sum);}北京大学《程序设计实习》课程19例３：POJ2755神奇口袋（续）递归出口说明如果sum等于0，说明前面已经找到一种成功的组合方式，返回1，否则，就是sum不等于0如果ith==n，说明没有可选的数来完成这一组和方式，返回0，如果sum0，说明刚刚尝试的组合凑不出要组合的数，所以返回0。北京大学《程序设计实习》课程20例４POJ1979黑瓷砖上行走问题描述：有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。北京大学《程序设计实习》课程21POJ1979黑瓷砖上行走输入：包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下‘.’：黑色的瓷砖‘#’：白色的瓷砖‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次当在一行中读入的是两个零时，表示输入结束。输出：对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)北京大学《程序设计实习》课程22POJ1979黑瓷砖上行走样例输入：69....#......#..............................#@...#.#..#.00样例输出：45北京大学《程序设计实习》课程23POJ1979问题1.递归函数如何构造？2.递归函数的出口如何定义？如何定义数组，以使递归出口判断简单化？3.小问题如何防止走过的瓷砖不被重复走过？读入初始点时，如何处理？北京大学