下载此文档

C语言递归算法ppt课件.ppt


文档分类:IT计算机 | 页数:约39页 举报非法文档有奖
1/39
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/39 下载此文档
文档列表 文档介绍
第四章 递归算法
1
完整版课件
前面已经介绍了关于递归调用这样一种操作,而递归程序设计是C++语言程序设计中的一种重要的方法,它使许多复杂的问题变得简单,容易解决了。递归特点是:函数或过程调用它自己本身。其中直接调用自己称为直接递归,而将A调用B,B以调用A的递归叫做间接递归。
2
完整版课件
【例1】 给定n(n>=1),用递归的方法计算1+2+3+4+...+(n-1)+n。
【算法分析】
本题可以用递归方法求解,其原因在于它符合递归的三个条件:
     (1)本题是累加问题:当前和=前一次和+当前项,而前一次和的计算方法与其相同,只是数据不同s(n)=s(n-1)+n;
      (2)给定n,所以是有限次的递归调用;
      (3)结束条件是当n=1,则s=1。
【参考程序】
#include<iostream>
using namespace std;
int fac(int); //递归函数
int main()
{
  int t;
  cin>>t; //输入t的值
  cout<<"s="<<fac(t)<<endl; //计算1到t的累加和,输出结果
}
int fac(int n)
{
  if (n==1) return 1;
  return(fac(n-1)+n); //调用下一层递归
}
3
完整版课件
运行程序,当T=5时,输出结果:S=15,其递归调用执行过程是:(设T=3)
递归调用过程,实质上是不断调用过程或函数的过程,由于递归调用一次,所有子程序的变量(局部变量、变参等)、地址在计算机内部都有用特殊的管理方法——栈(先进后出)来管理,一旦递归调用结束,计算机便开始根据栈中存储的地址返回各子程序变量的值,并进行相应操作。
4
完整版课件
【例2】 设有N个数已经按从大到小的顺序排列,现在输入X,判断它是否在这N个数中,如果存在则输出:“YES” 否则输出“NO”。
【算法分析】
该问题属于数据的查找问题,数据查找有多种方法,通常方法是:顺序查找和二分查找,当N个数排好序时,用二分查找方法速度大大加快。二分查找算法:
   (1) 设有N个数,存放在A数组中,待查找数为X,用L指向数据的高端,用R指向数据的低端,MID指向中间:
   (2) 若X=A[MID] 输出 “YES”;
   (3)若X<A[MID]则到数据后半段查找:R不变,L=MID+1,计算新的MID值,并进行新的一段查找;
   (4) 若X>A[MID]则到数据前半段查找:L不变,R=MID-1,计算新的MID值,并进行新的一段查找;
    (5)若L>R都没有查找到,则输出“NO”。
    该算法符合递归程序设计的基本规律,可以用递归方法设计。
5
完整版课件
【参考程序】  
#include<iostream>
  #include<cstdlib>
  using namespace std;
  int a[11];
  void search(int,int,int);
  int main() //主程序
  {
    int k,x,L=1,R=10;
    cout<<"输入10个从大到小顺序的数:"<<endl;
    for (k=1;k<=10;k++)
    cin>>a[k];
    cin>>x;
    search(x,L,R);
    system("pause");
  }
  void search(int x,int top,int bot) //二分查找递归过程
  {
    int mid;
    if (top<=bot)
   {
   mid=(top+bot)/2; //求中间数的位置
6
完整版课件
if (x==a[mid]) cout<<"YES"<<endl; //找到就输出
   else
   if (x<a[mid]) search(x,mid+1,bot); //判断在前半段还是后半段查找
   else search

C语言递归算法ppt课件 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数39
  • 收藏数0 收藏
  • 顶次数0
  • 上传人相惜
  • 文件大小368 KB
  • 时间2021-06-21