递推和递归有着很多的相似之处,甚至可以看做是递归的反向。递归的目的性很强,只解需要解的问题,递推有点“步步为营”的味道,不断的利用已有的信息推导出新的东西,而递归是构造出了一个通过简化问题来解决问题的途径。 递推在组合数学中有着典型应用。
本题是递推的示例题,之前算法合集(点击菜单)还有一些部分没有完成,后面还是接着一点点的完善!
Problem Description
甜甜从小就喜欢画图画,最近他买了一支智能画笔,由于刚刚接触,所以甜甜只会用它来画直线,于是他就在平面直角坐标系中画出如下的图形:
甜甜的好朋友蜜蜜发现上面的图还是有点规则的,于是他问甜甜:在你画的图中,我给你两个点,请你算一算连接两点的折线长度(即沿折线走的路线长度)吧。
Input
第一个数是正整数N(≤100)。代表数据的组数。 每组数据由四个非负整数组成x1,y1,x2,y2;所有的数都不会大于100。
Output
对于每组数据,输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。
Sample Input
5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5
Sample Output
1.000
2.414
10.646
54985.047
0.000
解题思路:
这道题刚开始看比较难找到规律,要从这个图形里抽象出可以解题的方法,主要是分两步,第一步,要考虑从起点(0,0)到目标点(x,y)的距离,第二步就是计算两个距离之间的差值。
作为“递推”算法的示例,其实也就是从(0,0)开始算,一步步算到终点的一个思想。
递归和递推正好相反,比如求阶乘,递归是从n开始往起始处推导,如果用递归算法,那么有递归式子:
而递推只能是通过迭代从1乘到n:
for(int i=1; i<=n; ++i) {
...
}
回到题目上,对于第一步来说,比较难的地方在于如何计算距离,这里的距离分为两个部分,一部分是45度的斜线,另一部分是从点(n,0)到点(0, n+1)的长度,归纳起来可以自己画个图,参考代码注释很容易就能明白了。
源代码:G++
#include<stdio.h>
#include<math.h>
double distance(int x, int y)
{
double dis = 0;
double segment = sqrt(2.0);
//45度线的总和
for (int i = 1; i <= x + y; i++)
dis += (i * segment);
//减去多加的最后一部分
dis -= (y * segment);
//加上斜线的总和(包括第一条竖线)
//勾股定理
for (int i = 0; i < x + y; i++)
dis += sqrt((double)i * i + (double)(i + 1) * (i + 1));
return dis;
}
int main()
{
int count, x1, x2, y1, y2;
scanf("%d", &count);
while (count--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
//递推算法
//先计算从(0,0)到(x,y)的距离
//再计算差值
double ans = fabs(distance(x1, y1) - distance(x2, y2));
printf("%.3f\n", ans);
}
return 0;
}