程序设计与实习讲义6 .ppt

程序设计实习2007 程序设计实习 第六讲 递归 /cpp2009 递归的基本思想 总体思想：将待求解问题的解看作输入变量x的函数f(x)，通过寻找函数g,使得f(x) = g(f(x-1))，并且已知f(0)的值，就可以通过f(0)和g求出f(x)的值． 这样一个思想也可以推广到多个输入变量x,y,z等，x-1也可以推广到 x - x1,只要递归朝着出口的方向走就可以了． #include iostream.h int Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); } 阶乘的栈 汉诺塔问题 汉诺塔问题 例题 ：POJ1664放苹果 a个苹果，d个盘子，问多少种不同放法．盘子和苹果都是没有编号的，即 1,2,3 和 3,2,1算是同一种放法 (d0) 例题：ai2755 神奇口袋 在实现上有两种考虑： 因为numbers, n与递归没有太大关系，可以考虑使用全局量； 如果不使用全局量，而通过参数传递numbers, n，可以增强递归函数的独立性 程序（将numbers, n设为全局量 ） int numbers[50],n; int count(int ith, int sum){ if(sum == 0) return 1; if(ith==n || sum 0) return 0; return count(ith+1,sum-numbers[ith]) +count(ith+1,sum); } 将 n 个数放入数组 numbers后， count(0,40); 就能求出结果 例题　ai1979 黑瓷砖上行走 问题描述：有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。 输入：包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 ‘.’：黑色的瓷砖 ‘#’：红色的瓷砖 ‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次 当在一行中读入的是两个零时，表示输入结束。 输出：对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖) 样例输入： 6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0 样例输出： 45 #include iostream using namespace std; const int MAX 22 //方块四周加红色块，去掉边界判断， //使得递归统一终止于红色块 char rect[MAX][MAX]; //返回从某点出发能走到的格子数 int walkFrom(int currentRow, int currentCol); void main(){ 　int col,row; 　while(cin col row , col!=0 row !=0){ 　　int i,j,startRow,startCol; 　　for(i=0;iMAX;i++)　 for(j=0;jMAX;j++) 　 　　　　rect[i][j]=#; 　　for(i=1;i=row;i++) 　 for(j=1;j=col;j++){　 　　　　 cin rect[i][j]; 　　　　 if(rect[i][j] == @){ 　　　　　　startRow = i; 　　　　　　startCol = j; 　　　　　　rect[i][j]=‘.’; 　//人站立处是黑砖 　　　　 } 　　} 　　cout walkFrom(startRow,startCol) endl; 　}//while } int walkFrom(int currentRow, int currentCol) { if(rect[currentRow][currentCol] == #) return 0; else{ //本瓷砖算走过，以后不能再走了 rect[currentRow][currentCol] = #; return 1+walkFrom(c