递归+记忆化搜索_为黑盒递归函数自动引入记忆化搜索

边界条件与递归方程是递归函数的两个要素。

1）阶乘函数

Int fac(int n)

{

If (n==0) return 1;

Else return n*fac(n-1);

}

这里，第一句的if是边界条件，第二句是递归方程。0的阶乘为1，n的阶乘为（n-1）的阶乘再乘n。

2）汉诺塔问题

Void move(int n,int a,int b,int c)

{

If (n==1) cout<<a<<”->”<<c<<endl;

Else

{

Move(n-1,a,c,b);

Cout<<a<<”->”<<c<<endl;

Move(n-1,b,a,c);

}

这个问题，是个问题。首先，明确一下这里形参的含义：n表示现在有n个盘需要移动，a表示盘子现在在哪里，b表示中间的媒介，c表示盘子要去哪里。然后，这里的if语句还是边界，就是当n=1的时候，也就是现在只有一个盘子的时候，直接移动并输出路径。底下else语句中的是主体：因为当前有n个盘子需要移动，而最终目的是让第n号盘子从a移动到c，因此我们分为三步：①把上面的n-1个盘子看做一个整体，从a先移动到b；②把第n号盘子从a移动到c，输出路径；③把那n-1个盘子再从b移动到c。

递归函数的执行流程分为两个阶段：递归前进段、递归返回段。

这可以说一个很神奇的东西。总的来说就是：递归前进段就是你按它函数的顺序执行下去，直到碰到边界；递归返回段就是当你碰到了边界，你把刚刚所有递归嵌套的函数值算出来，一步一步返回值，返回给最初的值。

这里有一个我很容易搞错的东西，也很难理解的东西：没每递归调用一次函数，系统就会生成一个新的函数实例。这些函数实例有同名的参数和局部变量，但各自独立，互不干扰。流程执行到哪一层，那一层的变量就起作用，返回上一层，就释放掉低层的同名变量。这个需要深刻理解一下。

3）斐波那契数列

板子很简单：

Int f(int n)

{

If (n<=2) return 1;

Else return f(n-2)+f(n-1);

}

接下来学一个记忆化搜索

来看一下斐波那契数列的板子：

Int f[max]={0};

Int f(int n)

{

If (f[n]!=0) return f[n];

If (n<=2) return f[n]=1;

Else return f[n]=f(n-2)+f(n-1);

}

可以这么理解：你先打一个不用记忆化搜索的板子，然后把它转换为记忆化搜索。记忆化搜索的话，要多加一个数组，用来存储已经求过的函数值。然后，你再在递归函数里面先加一句话——if （这个数组的值不为0） return 这个值；另外，后面的递归返回值里在前面多加一个——“数组=”递归返回值。

 

还是斐波那契数列，板子还可以这样打：

 

Int t1,t2,r;

t1=t2=r=1;

for (int i=3;i<=n;++i)

{

r=t1+t2;

t1=t2;

t2=r;

}

cout<<r;

 

这种方法连数组都不用。

 

递归构建有三个条件：1）参数；2）边界；3）范围。

据此来分析递归过程如何写。

1） 参数：明确参数的意义以及当前的值；

2） 边界：一个递归函数一定要有边界，而且边界一定要考虑全面，不能漏，否则它就可能死循环；

3） 范围：就是你在递归时的选择往哪儿走，也就是说，你的递归调用的函数返回值。

然后我们现在再来看一下记忆化搜索：

①定义好一个数组，用来存储递归所求出来的值；②在主程序里，memset一下，一般都是赋初值为-1，然后把这个数组的边界值设置好；③在递归函数里，首先加一句：if （这个数组的值>=0） return 这个值【如果赋初值为-1的话，一般都是>=0】；其次，在后面的递归调用中，先给这个数组赋值，再return。

 例题

poj1579

Function Run Fun

Description

We all love recursion! Don't we? 

Consider a three-parameter recursive function w(a, b, c): 

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 
1 

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: 
w(20, 20, 20) 

if a < b and b < c, then w(a, b, c) returns: 
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 

otherwise it returns: 
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion. 

Input

The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.

Output

Print the value for w(a,b,c) for each triple.

Sample Input

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

Sample Output

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

 

题目大意：

如果a <= 0或b <= 0或c <= 0，则w（a，b，c）返回1如果a> 20或b> 20或c> 20，则w（a，b，c）返回w（20,20,20）如果a <b且b <c，那么w（a，b，c）返回w（a，b，c-1）+ w（a，b-1，c-1）-w（a，b-1，C）否则它返回w（a-1，b，c）+ w（a-1，b-1，c）+ w（a-1，b，c-1）-w（a-1，b-1，C-1）

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
long long v[25][25][25];
int w(ll a,ll b,ll c)
{
    if(a <= 0 || b <= 0 || c <= 0)
        return 1;
    else if (a > 20||b > 20||c > 20)
        return v[20][20][20]=w(20,20,20);
    else if(v[a][b][c] == 0)
    {
        if(a < b && b <c)
            return v[a][b][c] = w(a,b,c - 1) + w(a,b - 1,c - 1) - w(a,b - 1,c);
          else
           return v[a][b][c] =  w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }
    return v[a][b][c];
}
int main()
{
    ll a,b,c;
    while(scanf("%lld %lld %lld",&a,&b,&c)!=EOF)
    {
        if(a == -1 && b == -1 && c== -1)
        {
            break;
        }
        else
        {
            printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
        }
 
    }
 
    return 0;
}