在一个黑袋中共有m个白球和n个黑球（m，n>0）,袋外还有一些白球。每次随机从袋中取出两球，若取出的球颜色相同，则放回一白球；若取出两球颜色不同，则放回一黑球，直到取完（取出最后两球不放回）。请编程求多少种取法，并说明最后两球的颜色。（用递归方法求解）

用f[i,j]表示i个白球，j个黑球时取法的总数，易知:f[0,2]=1,f[2,0]=1,f[1,1]=1;

对于f[i,j],用加法原则找出他的递归式：
取出两白球(i>=2):f[i-1,j]
取出两黑球(j>=2):f[i+1,j-2]
取出一黑一白(i>=1 && j>=1):f[i-1,j]

我们观察到f[i,j]所转移的两个状态实际上总球数都会减1,所以不会出现死循环递归的情况

int f(int m,int n)
{
    if (n+m==2) return 1;
    int p=0;
    if (m>=2) p+=f(m-1,n);
    if (n>=2) p+=f(m+1,n-2);
    if (m>=1 && n>=1) p+=f(m-1,n);
    return p;
}

实现的时候为了效率问题，你可以改成循环实现，也可以改成记忆化递归

下面是记忆化递归的实现

首先在定义一个数组ff[m][n],ff[0][2]=1,ff[2][0]=1,ff[1][1]=1;

int f(int m,int n)
{
    if (ff[n][m]!=0) return ff[m][n];
    int p=0;
    if (m>=2) p+=f(m-1,n);
    if (n>=2) p+=f(m+1,n-2);
    if (m>=1 && n>=1) p+=f(m-1,n);
    ff[m][n]=p;
    return p;
}

[ 本帖最后由 czz5242199 于 2011-12-9 18:43 编辑 ]