第4章利用函数编程..ppt

递归方法求n! 4.5.3 排队购票 1. 案例描述 一场球赛开始前，售票工作正在紧张的进行中。每张球票为50元，现有30个人排队等待购票，其中有20个人手持50元的钞票，另外10个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这30个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数。(约定：拿同样面值钞票的人对换位置后为同—种排队)。 2. 案例分析 我们考虑一般情形：有m＋n个人排队等待购票，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。求出这m＋n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数(这里正整数m、n从键盘输入)。这是一道典型的组合计数问题，考虑用递推求解。 令f(m，n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。 4.5.3 排队购票 3. 算法描述 根据加法原理可得到f(m，n)的递推关系为： f(m，n)＝f(m，n－1)＋f(m－1，n) 初始条件： 当m＜n时，f(m，n)＝0 当n＝0时，f(m，n)＝1 4.5.3 排队购票 4. 程序实现 # includestdio.h // 排队购票递归程序 void main() long f(int j-int i) { int m，n；long y； printf(“Please input n，n：”)； scanf(“％d，%d”，m，n)； printf(“ f(%d，％d)=％ld．\n”，m，n，f(m，n))； if(i==0) y=1； else if(ji) y=0； //确定初始条件 else y=f(j-i,i)+f(j-i-1) //实施递归 return(y)； } 4.5.3 排队购票 [运行程序] Please input m-n：15，12 F(15，12)＝4345965． 4.5.3 排队购票 4.5.4 谁是最小年龄 1. 案例描述 有5个学生坐在一起，问第5个学生多少岁，他说比第4个学生大2岁。问第4个学生岁数，他说比第3个学生大2岁。问第3个学生，又说比第2个学生大2岁。问第2个学生，说比第1个学生大2岁。最后问第1个学生，他说是10岁。请问第5个学生多大。 2. 案例分析 要求第5个学生的年龄，必须先知道第4个学生的年龄，而求第4个学生的年龄必须先知道第3个学生的年龄，可第3个学生的年龄又取决于第2个学生的年龄，第2个学生的年龄取决于，第1个学生的年龄，而且每一个学生的年龄都比其前1个学生的年龄大2。显然，这是一个典型的递归问题。 3. 算法描述 根据题意，可用数学公式表述如下： age(5)＝age(4)＋2 age(4)＝age(3)＋2 age(3)＝age(2)＋2 age(2)＝age(1)＋2 age(1)＝10 由此，可得出如下递推公式： age(n)＝10 (n＝1) age(n)＝age(n一1)+2 (n1) 4.5.4 谁是最小年龄 初始条为：age(1)＝10 当n＞l时，求第n个学生的年龄的公式是相同的，age(1)＝10就是使递归结束的条件。 4. 程序实现 用一个主函数调用age函数，求得第5个学生的年龄。整个程序如下： # includestdio.h int main() { int age(int n)； printf(“NO.5，age：％d\n”，age(5))； return 0； } 4.5.4 谁是最小年龄 int age(int n) { int c； if(n==1) c=10； else c=age(n-1)+2； return(c)； } [运行程序] NO.5，age：18 4.5.4 谁是最小年龄 [问题点拨] main函数中实际上只有一个语句。整个问题的求解全靠一个age(5)函数调用来解决。age函数共被调用5次，即age(5)、age(4)、age(3)、age(2)、age(1)。其中age(5)是main函数调用的，其余4次是在age函数中调用的，即递归调用4次。 〖请读者思考〗上述调用的全过程。应当强调说明的是在某一次调用age函数时并不是立