递推和递归方法在C语言程序设计中的应用

1 递归和递推算法
递归作为一种算法在程序设计语言中广泛应用。它是调
用一个函数的过程中又出现直接或者间接地调用该函数本身。
递归是计算机科学的一个重要概念, 递归的方法是程序设计中
有效的方法, 采用递归编写程序能使程序变得简洁和清晰。
递推算法是一种用若 干 步 可 重 复 的 简 运 算( 规 律) 来
描述复杂问题的方 法。递 推 是 序 列 计 算 机 中 的 一 种 常 用
算法。递推法的特点是从一个已知的事实出发, 按照一定
规律推出下一个事实, 再 从 这 个 新 的 已 知 事 实 出 发, 再 向
下推出一个新的事实。

2 问题提出
一场球赛开始前, 售 票 工 作 正 在 紧 张 进 行 中, 每 张 球
票为50元, 现有 m+n个人排队等待购票, 其中有 m 个人
手持50 元 的 钞 票, 另 外 n个 人 手 持100 元 的 钞 票。假 设
开始售票时 售 票 处 没 有 零 钱, 求 出 这 m+n 个 人 排 队 购
票, 使售票处 不 至 出 现 找 不 开 钱 的 局 面 的 不 同 排 队 种 数
( 这里正整数 m、 n从键盘输入)。
这个问题用一般的解决方法非常麻烦, 下面用递归和
递推方法解决。

3 购票问题分析
这是一道组合计数问题。令f ( m, n) 表示有 m 个人手持
50元的钞票, n个人手持100元的钞票时共有的方案总数。
( 1) n=0。n=0意味着排队购票的所有人手中拿的都是
50元的钞票, 那么这 m个人的排队总数为1, 即f ( m, 0) =1。
( 2)m<n。当 m<n时, 即 排 队 购 票 的 人 中 持50 元
的人数小于持100元的人数, 即 使 把 m 张50元 的 钞 票 都
找出去, 仍会出现找不开钱的局面, 所以f ( m, n) =0。
( 3)其它情况。m+n个人排队购票, 第 m+n个人站
在第 m+n-1个人的后面, 则第 m+n个人的排队方式可
由两种情况获得: ① 第 m+n个 人 手 持100 元 的 钞 票, 则
在他之前的 m+n-1个人中有 m 个人手持50元的钞票,
有n-1 个 人 手 持100 元 的 钞 票, 此 种 情 况 共 有f( m, n-
1); ②第 m+n个人手持50元的钞票, 则在他 之 前 的 m+
n-1个人中有 m-1个 人 手 持50 元 的 钞 票, 有 n个 人 手
持100元的钞票, 此种情况共有f ( m-1, n)。
由加法原理得到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 购票排队递归程序实现

#include

long f(int j, int i)
{
	long y=0;
	if(i==0)  y=1;
	else if(j<i) y=0 ;/*确定初始条件*/
	else y=f(j-1,i)+f(j,i-1);/*实施递归*/
	return y;
}

int main()
{
	int m,n;
	printf("input m n:");
	scanf("%d%d",&m,&n);
	printf("f(%d,%d)=%ld.\n",m,n,f(m,n));

}


5购票排队递推程序实现

#include<stdio.h>
void main()
{
int m,n,i,j;
long f[100][100];
printf(“inputm,n:”);
scanf(“%d,%d”,&m,&n);
for(j=1;j<=m;j++)
f[j][0]=1;
for(j=0;j<=m;j++)
for(i=j+1;i<=n;i++)
f[j][i]=0;
for(i=1;i<=n;i++)
for(j=i;j<=m;j++)
f[j][i]=f[j-1][i]+f[j][i-1];
printf(“f(%d,%d)=%ld.\n”,m,n,f[m][n]);
}

6结语
递归和递推算法解决问题结构清晰、可读性强,而且
容易用数学归纳法来证明算法的正确性,为设计算法、调
试程序带来很大方便。且递推程序的运行速度要快于递
归程序

还没有评论,快来抢沙发!

发表评论

  • 😉
  • 😐
  • 😡
  • 😈
  • 😯
  • 😛
  • 😳
  • 😮
  • 😆
  • 💡
  • 😀
  • 👿
  • 😥
  • 😎
  • 😕