C语言程序设计上机编程方法
2000年1月25日 北京理工大学 / 《C语言程序设计》上机编程方法 《C语言程序设计》上机编程方法系列讲座 5月24日 中心教学楼0231 下午3:30 专题1：递归程序设计方法 陈朔鹰 5月24日 中心教学楼0211 晚上6:30 专题2：简单图形输出方法 李凤霞 5月24日 中心教学楼0231 晚上6:30 专题3：使用穷举法编程 薛 庆 《C语言程序设计》上机编程方法系列讲座 5月31日 中心教学楼0231 下午3:30 专题2：简单图形输出方法 李凤霞 5月31日 中心教学楼0211 晚上6:30 专题1：递归程序设计方法 陈朔鹰 5月31日 中心教学楼0231 晚上6:30 专题3：使用穷举法编程 薛 庆 《C语言程序设计》上机编程方法系列讲座 6月7日 中心教学楼0231 下午3:30 专题3：使用穷举法编程 薛 庆 6月7日 中心教学楼0211 晚上6:30 专题1：递归程序设计方法 陈朔鹰 6月7日 中心教学楼0231 晚上6:30 专题2：简单图形输出方法 李凤霞 计算机科学工程系 陈朔鹰 编写递归程序之前的准备 编写递归程序的一般方法 编写数值型递归程序 数值型问题的递归求解一般方法 从数学公式入手，推导出问题的递归定义；确定问题的边界条件；再得到问题的递归算法和递归结束条件 例1：求自然数 1 到 n 之和。 建立问题的递归定义： f(n) = 1 当 n=1 时 f(n) = n + f(n-1) 当 n>1 时 程序： add ( n ) int n; { if (n==1)return (1); /* 递归结束条件 */ else return ( n + add(n-1) ); } 编写数值型递归程序 例2：求菲波那奇序列：1，1，2，3，5，8，13，21，…… 建立问题的递归定义： f(n)=1 当 n=1或n=2 时 f(n)=f(n-1)+f(n-2) 当 n>2 时 程序： f ( n ) int n; { if (n==1||n==2) return (1); /* 结束条件 */ else return ( f(n-1)+f(n-2) ); } 编写数值型递归程序 例3：打印杨辉三角型： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 …………………………………… 建立问题的递归定义(对于第 x 行的第 y 个值)： c(x,y) = 1 y=1 或 y=x+1 c(x,y) = c(x-1,y-1) + c(x-1,y) 其它 程序： int c ( x, y ) /* 求第 x 行第 y 列的值 */ int x, y; { if ( (y==1) || (y==x) ) return (1); return ( c(x-1,y-1) + c(x-1,y) ); } 编写数值型递归程序 例C4_5003.C：请用递归的方法计算下列函数的值： px(x,n) = x - x2 + x3 - x4 + ...... (-1)n-1xn n>0 已知程序： double px ( x, n ) int n; double x; { if (n==1) return ( ); else return ( x * ) ; } 请填写适当的语句，使之成为正确的程序。 编写数值型递归程序 分析： px(x,n)= x - x2 + x3 - x4 + ...... (-1)n-1xn n>0 = x * ( 1 - x + x2 - x3 + ...... (-1)n-1xn-1 ) = x * ( 1 - (x - x2 + x3 - ...... (-1)n-2xn-1 )) = x * ( 1 - px(x,n-1) ) 可将原来的非递归定义形式转化为等价的递归定义： px(x,n) = x
