算法合集 | 无限的路（递推） - HDU 2073
算法合集 | 无限的路（递推） - HDU 2073
递推和递归有着很多的相似之处，甚至可以看做是递归的反向。递归的目的性很强，只解需要解的问题，递推有点“步步为营”的味道，不断的利用已有的信息推导出新的东西，而递归是构造出了一个通过简化问题来解决问题的途径。 递推在组合数学中有着典型应用。
本题是递推的示例题，之前算法合集（点击菜单）还有一些部分没有完成，后面还是接着一点点的完善！
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 5Sample 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;
}