第16讲2_2分治策略之递归.ppt

河南理工大学ACM-ICPC培训 ACM-ICPC培训 程序设计实习第15讲 分治策略之递归 内容提要 存在的若干问题总结 递归的基本思想 例题 练习 栈与递归 实训 * 二维数组的动态分配问题 数组动态分配P = new T[N]; 如何动态分配二维数组？ 分配? int ? **ptr=new ? int*[num1]; ? ? for(int i=0; i num1; i++) ? ? ? ? ? ? ptr[i]=new ?int[num2]; 清除时反着来： ? ? for(int ? i=0;inum1;i++) ? ? ? ? ? ? delete ? []ptr[i]; ? ? delete ? []ptr; ?  * 其他常见问题 对于不好的编程习惯导致格式不清，最后使逻辑混乱的问题，逻辑混乱后出问题往往难以发现。建议仔细想好了程序的思路，在纸上画下流程图后再动手编写。 由于功能代码过长过于复杂导致错误难以发现。建议尽量分而治之的解决问题。多使用函数，做到每个独立功能的代码段不超过50行，并写上注释。 对输入数据的多样性估计不足，当数据不对时候，发生a[-1]越界这样的问题，有些越界后程序并没有run time error 错误非常隐蔽，对于每一个数组都应该检查分析它是否有可能出现越界错误。 在代码中尽量减少精度误差 如：result=a*b/c在计算机中和 temp＝b/c; result=a*temp;运行结果并不是都是相同的。代码中做得先乘后除非常必要。如果不能做得先乘后除，那么务必在运算中使用double类型的变量保存中间结果。 * 其他常见问题 直接使用整数表达式的值作为if（）的内容，如if（n％4）…，功力不够这样写的代码容易出错。而且一时间错误难以发现。建议取缔这样的编程风格，一律使用布尔表达式的值作为if（）的内容，如if（n％4＝＝0），使得逻辑尽量清晰。另外杜绝复杂的if条件，当情况复杂，建议多写几个判断分支。 字符串声明的时候要注意留出保存字符串结束符’\0’的位置，所以编程时可以考虑声明一个大一点的空间以免越界。 仍然有许多同学不会使用断点、debug等功能调试程序，应当尽快学会使用这些方便的工具帮助自己解决问题，这样可以事半功倍。 除非特殊说明，测试题都是读入一行数据，输出一个结果，不必一次性读入全部数据，然后一次性输出所有结果。 关于提交问题时Wrong Answer的问题。对于大部分问题而言，很多同学要么是没有考虑到一些边界数据，要么是在处理输入输出格式时出了问题。在遇到Wrong Answer时，首先考虑一下自己是不是有一些边界数据没有处理，然后再看看是不是完全符合题目的输入输出要求，尽量跳出自己写程序时的思路，这样会比较容易发现错误。 * 递 归 * 递归的基本思想 什么是递归？ 递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解。 总体思想： 将待求解问题的解看作输入变量x的函数f(x) 通过寻找函数g,使得f(x) = g(f(x-1)) 并且已知f(0)的值，就可以通过f(0)和g求出f(x)的值． 这样一个思想也可以推广到多个输入变量x,y,z等，x-1也可以推广到 x - x1,只要递归朝着出口的方向走就可以了． * 递归的基本思想 递归的几个特点 递归式：如何将原问题划分成子问题。 递归出口：递归终止的条件，即最小子问题的求解，可以允许多个出口。 界函数：问题规模变化的函数，它保证递归的规模向出口条件靠拢 * 讲解１：POJ2753菲波那契数列 输入一个整数n，求菲波那契数列的第n项． 算法：设第n项值为f(n)，则 　f(n) = f(n-1)+f(n-2)．已知f(1)=1，f(2)=1，则从第３项开始，可以用公式求． 程序：int f(int n){ if(n==1 || n==2) return 1; else return f(n-1)+f(n-2); } * 讲解２：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、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法