版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
C程序设计专题辅导课
递归函数程序设计递归函数函数直接或间接地调用自己的形式称为函数的递归调用。递推法与递归法求阶乘递推法n!=1*2*3*....*nfor(result=1,i=1;i<=n;i++)result=result*i;递归法递归定义n!=n*(n-1)!(n>1)n!=1(n=0,1)递归函数fact(n)程序解析例10-3用递归函数求n!。#include<stdio.h>doublefact(intn);int
main(void){intn;
scanf("%d",&n);
printf("%f",fact(n));return0;}doublefact(intn) /*函数定义*/{doubleresult;
if(n==1||n==0) /*递归出口*/result=1;elseresult=n*fact(n-1);
returnresult;}求n!递归定义n!=n*(n-1)!(n>1)n!=1(n=0,1)fact(n)=n*fact(n-1);递归式main()fact(3)fact(2)fact(1){....{....{....{....printf(fact(3))f=3*fact(2)f=2*fact(1)f=1}return(f)return(f)return(f)}}}递归函数fact(n)的实现过程fact(3)=
2*1=23*2=6同时有4个函数在运行,且都未完成3*fact(2)=2*fact(1)=fact(1)=1递归程序设计用递归实现的问题,满足两个条件:问题可以逐步简化成自身较简单的形式(递归式)n!=n*(n-1)!nn-1Σi=n+Σi
i=1i=1递归最终能结束(递归出口)两个条件缺一不可解决递归问题的两个着眼点递归函数可以用数学归纳法来理解数学归纳法:首先证明初值成立,然后假设n时成立,再证明n+1时成立,则问题得到证明。例10-4写输出结果#include<stdio.h>longfib(intg){switch(g){case1:case2:return(1);}return(fib(g-1)+fib(g-2));}voidmain(){longk;k=fib(5);
printf("k=%ld\n",k);}fib(g)=1g=1fib(g)=1g=2fib(g)=fib(g-1)+fib(g-2)g>=3k=5Fibonacci数列递归公式递归式递归出口例10-5汉诺(Hanoi)塔将64个盘从座A搬到座B(1)一次只能搬一个盘子(2)盘子只能插在A、B、C三个杆中(3)大盘不能压在小盘上
A B C分析
A B C
A B Cnn-1函数
/*搬动n个盘,从a到b,c为中间过渡*/voidhanio(intn,chara,charb,charc){if(n==1)printf("%c-->%c\n",a,b);else{hanio(n-1,a,c,b);
printf("%c-->%c\n",a,b);hanio(n-1,c,b,a);}}hanio(n个盘,A→B)//C为过渡{if(n==1)直接把盘子A→Belse{hanio(n-1个盘,A→C)
把n号盘A→B hanio(n-1个盘,C→B) }}算法八皇后问题八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是著名的数学家高斯提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。11111111八皇后问题分析:任意两个皇后都不能处于同一行、同一列或同一斜线上,可用数组a记录各行皇后所在的列,数组b,c反映两条斜线上是否安全。0123456701234567b数组C数组八皇后问题#include<stdio.h>#defineN8/*定义列数*/int
a[N]={0};intb[2*N-1]={0};intc[2*N-1]={0};int
q[N][N]={0};intcount=0;voidqueen(intn){intj;for(j=0;j<N;j++)/*对第n行进行第n个皇后的位置确定*/if(a[j]==0&&b[n+j]==0&&c[n-j+N-1]==0){/*可以作皇后候选位置*/
q[n][j]=1;a[j]=1;b[n+j]=1;c[n-j+N-1]=1;/*皇后占领的位置标记*/
if(n==N-1)print();elsequeen(n+1);
q[n][j]=0;a[j]=0;b[n+j]=0;c[n-j+N-1]=0;}}voidmain(){queen(0);}voidprint(){int
i,j;for(i=0;i<N;i++){for(j=0;j<N;j++)
printf("%d",q[i][j]);printf("\n");}
printf("---------%d-------\n“,++count);}递归算法递归算法往往有着算法简单,容易理解,可读性好的优点,但执行效率不高。如果存在较明确的递推算法时,递推算法执行效率较高。典型:Fibonacci数列递归算法效率非常低Fibonacci数列递归程序效率fib(5)fib(4)fib(3)fib(2)fib(1)fib(3)fib(2)fib(2)fib(1)fib(6)fib(4)fib(3)fib(2)fib(2)fib(1)fib(g)=1g=1fib(g)=1g=2fib(g)=fib(g-1)+fib(g-2)g>=3用递归方法实现对一个整数进行逆序输出。voidreverse(intn){if(n/10==0)
printf("%d",n);else{printf("%d",n%10);reverse(n/10);}}voidreverse(intn){if(n/10==0)
printf("%d",n);else{reverse(n/10);printf("%d",n%10);}}该函数的功能?2008试题B#include<stdio.h>voidfun(intn,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 儿科手术室医院感染的诊断标准
- 糖尿病运动治疗指南
- 销售接待流程:快速成交策略
- 离职证明书的开具样本有效期
- 公有住房物业管理的绿色环保实践
- 物业管理市场竞争力分析
- 肝源性糖尿病:并发症识别与预防
- 信息化公司物业管理系统管理制度
- 糖尿病与时间管理:效率提升培训
- 两人合伙做生意协议书
- 四级专项指南:翻译 PPT
- 2023-2024学年江苏省启东市小学数学五年级下册期末高分试卷
- 2022年全国统一高考日语真题试卷及答案
- 雨季三防专项会议记录
- GB/T 8165-2008不锈钢复合钢板和钢带
- GB/T 220-2001煤对二氧化碳化学反应性的测定方法
- GB/T 17213.7-2017工业过程控制阀第7部分:控制阀数据单
- 超星尔雅学习通【中国近现代史纲要(首都师范大学)】章节测试含答案
- GA/T 1690.1-2019法庭科学印章印文检验第1部分:显微检验法
- GA 576-2018防尾随联动互锁安全门通用技术条件
评论
0/150
提交评论