简要叙述如何规划建设一个企业网站,网站建设修饰商品,品牌vi设计模板,沧州做网站的专业公司1. 算法简介
递推和递归虽然叫法不同#xff0c;但它们的基本思想是一致的#xff0c;在很多程序中#xff0c;这两种算法可以通用#xff0c;不同的是递推法效率更高#xff0c;递归法更方便阅读。
#xff08;1#xff09;递推法
递推法是一种重要的数学方法#…1. 算法简介
递推和递归虽然叫法不同但它们的基本思想是一致的在很多程序中这两种算法可以通用不同的是递推法效率更高递归法更方便阅读。
1递推法
递推法是一种重要的数学方法同时也是计算机进行数值计算的个重要算法。 递推法的核心是找到计算前后过程之间的数量关系即递推式。递推式往往根据已知条件和所求问题之间存在的某种相互联系推导得出。递推计算时需要将复杂运算转换为若干步重复的简单运算这样可以发挥计算机擅于重复处理数据的特点。递推法避开了求通项公式的麻烦把一个复杂问题的求解分解成了连续的若干歩简单运算可以将递推法看成一种特殊的迭代算法。 [案例解析]铺方格 有2×n个长方形的方格用一个1×2的骨牌铺满方格。例如当03时为2×3方格骨牌的铺放方案有3种 骨牌铺设方案1 编写一个程序试对给出的任意一个n(n0)输出铺法总数。针对这个问题要想直接获得问题的解答是相当困难的。可以用递推法从简单到复杂逐步归纳出问题解的一般规律。分析过程如下。 当n1时只能有一种铺法 如图4-2(a)所示铺法总数为X11。 当n2时骨牌可以并列竖排也可以并列横排再无其他排列方法如图2(b)所示铺法总数为X2 2。 当n3时,骨牌可以全部竖排也可以认为在方格中已经有一个竖排骨牌、需要在方格中排列两个横排骨牌(无重复方法)若已经在方格中排列两个横排骨牌则必须在方格中排列一个竖排骨牌如图2(c)所示再无其他排列方法,铺法总数为X3 3。 骨牌铺放方案(2) 由此可以看出当n3时排列骨牌的方法数是n1和n2时排列方法数之和。 推出一般规律对一般的n要求Xn。可以这样考虑若第一个骨牌是竖排列则剩下n-1个骨牌需要排列这时排列方法数为Xn-1若第一个骨牌是横排列则整个方格至少有2个骨牌是横排列(1×2骨牌)因此剩下n-2个骨牌需要排列这时排列方法数为Xn-2从第一种骨牌排列方法考虑只有这两种可能,所以有
XnXn-1Xn-2(n 2)
X11
X22
XnXn-1 Xn-2就是问题求解的递推公式 任意n都可以从中获得解答。 例如n5
X3X2X13
X4X3X25
X5X4X38 利用程序表示为
cinn;
a[1]1;a[2]2;
for(i3;in; i)
a[i]a[i-1]a[i-2];
couta[n];
2递归法
在计算机科学中如果某个函数的实现中出现了对函数自身的调用语句则称该函数为递归函数。 递推法可以用递归函数实现。一般来说循环递推法比递归函数的速度更快但递归函数的可读性更强。 例如上述平铺方格问题改写成递归函数的形式如下。
int pu(int n)
{
if(n1) return 1;
if(n2) return 2;
return pu(n-1) pu(n-2);
}
递归函数在它的函数体内直接或者间接地调用自身每调用一次就进入新的一层。递归函数必须有结束递归的条件。函数会一直递推 直到遇到结束 条件返回递归函数调用的一般过程如图3所示,这里以n6为例。 递归函数的调用过程 2. 取数位2017年试题E
【问题描述】 求一个整数的第k位数字有很多种方法以下下方法就是其中一种。 //求x用十进制表示时的数位长度 int len(int x){
if(x10) return 1;
return len(x/10)1;
}
//取x的第k位数字
int f(int x, int k) {
if(len(x)-k0) returnx%10;
return ( ) //填空
}
int main()
int x 23574;
printf(d\n, f(x,3));
return 0;
}
对于题目中的测试数据应该打印5。 请仔细分析源码并补充画线部分缺少的代码。 注意只提交缺失的代码不要填写任何已有内容或说明性文字。
答案——取数位 //求 x 用十进制表示时的数位长度int len(int x){if(x10) return 1;return len(x/10)1;}//取 x 的第 k 位数字int f(int x, int k) {if(len(x)-k0) return x%10;return f(x/10,k) //填空}int main()int x 23574;printf(d\n, f(x,3));return 0;}
