【专题】小球与盘子在4中限制下的放置可能性——同球同盘、异球同盘、同球异盘、异球异盘，C++算法实现

╰+攻爆jí腚メ 2022-08-29 10:04 54阅读 0赞

# 0\#引入 #

考试时遇到同球同盘的问题，一开始想用插板法，终究失败，只拿了20分，回家问了老师，老师告了我方法并让我自己研究剩下三种。

# 1\#同球同盘——递推或递归（+记忆化改进优化） #

这个我有真题[http://www.kencoding.net/problem.php?id=1369][http_www.kencoding.net_problem.php_id_1369]，大家可以去做一下

我先把递推公式列在这里：  
（n是球数，m是盘子数）  
 \{ f ( 0 , 0 ) = 1 f ( n , 1 ) = 1 f ( n , m ) = f ( n , n )     i f ( n < m ) f ( n , m ) = f ( n − m , m ) + f ( n , m − 1 )     i f ( n ≥ m ) \\left\\\{ \\begin\{array\}\{ll\} f(0,0)=1\\\\ f(n,1) = 1\\\\ f(n, m)=f(n,n) \\ \\ \\ if(n < m)\\\\ f(n,m) = f(n - m, m) + f(n, m-1)\\ \\ \\ if(n\\ge m)\\\\ \\end\{array\} \\right. ⎩⎪⎪⎨⎪⎪⎧f(0,0)=1f(n,1)=1f(n,m)=f(n,n)   if(n<m)f(n,m)=f(n−m,m)\+f(n,m−1)   if(n≥m)

第一个是人为修正的，后两个是可以理解的，第三个我来解释一下：

如果n大于等于m时，那么分为两种情况（1）放满盘子；（2）有空盘。

（1） f ( n − m , m ) f(n-m,m) f(n−m,m)的意思是：既然要将球放满，那么就从每个盘子里拿走一个球，即球数减盘子数，剩下的球在其中继续排列结果是不变的，因为同球同盘嘛。如果第一次每个盘子取一个之后球数仍然大于盘子数，那么将会在第二次再次执行每个盘子去一个球的操作。  
（2） f ( n , m − 1 ) f(n,m-1) f(n,m−1)的意思是：有空盘的话，就先拿走一个盘子，剩下的球在剩下的盘子中排列，直到盘子数减到1。

0的特殊情况：我们来看一个实例，按照我们的公式，f(2,2)会执行如下操作：

f ( 2 , 2 ) = f ( 0 , 2 ) + f ( 2 , 1 ) = f ( 0 , 0 ) + 1 = ? + 1 f(2,2)=f(0,2) + f(2,1)=f(0,0) + 1 = ? + 1 f(2,2)=f(0,2)\+f(2,1)=f(0,0)\+1=?\+1

我们实际算一下，f(2,2)应该是2，那么f(0,0)是多少呢？？？只能是一了，所以我就这么尴尬的定下来了。

下面我给出代码，这道题可以AC该题目：

（1）递推版本：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int n, m, p;
    int dp[1010][1010];
    int main()
    { 
        cin >> n >> m >> p;
        for (int i = 1; i <= 1001; i++)
        { 
            dp[i][1] = 1;
            // dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++)
        { 
            for (int j = 1; j <= m; j++)
            { 
                if (i < j)
                    dp[i][j] = dp[i][i];
                else if (i > j)
                { 
                    dp[i][j] = (dp[i][j - 1] + dp[i - j][j]) % p;
                }
                else if (i == j)
                { 
                    dp[i][j] = (1 + dp[i][j - 1]) % p;
                }
            }
        }
        cout << dp[n][m] << endl;
        return 0;
    }

严谨一些我们可以加上一些初始化比如memset

（2）递归版本，会超时

#include <iostream>
     
    #include <cstring>
    #include <cstdio>
     
    using namespace std;
    int p;
    int f(int n, int m)
    { 
        if (m == 1)
            return 1;
        if (n == 0)
            return 1;
        if (m > n)
            return f(n, n) % p;
        if (m <= n)
        { 
            return (f(n, m - 1) + f(n - m, m)) % p;
        }
    }
     
    int main()
    { 
        int n, m;
        cin >> n >> m >> p;
        cout << f(n, m) % p << endl;
        return 0;
    }

为什么会超时呢？这就像我们的经典例题斐波那契数列了，我们会发现有很多的重复调用，所以我们需要用数组来解决问题，也就是记忆化搜索，而改变为记忆化搜索之后递归也就从根本上和递推是一个道理了，可以统称为动态规划了。

（3）数组改版递归，记忆化搜索

#include <iostream>
     
    #include <cstring>
    #include <cstdio>
     
    using namespace std;
    int p;
    int dp[1010][1010];
    int f(int n, int m)
    { 
        if (m == 1)
            return 1;
        if (n == 0 && m == 0)
            return 1;
        if (m > n)
            return f(n, n) % p;
        if (m <= n && dp[n][m] == -1)
        { 
            dp[n][m] = (f(n, m - 1) + f(n - m, m)) % p;
            return dp[n][m];
        }
        else
        { 
            return dp[n][m];
        }
    }
     
    int main()
    { 
        int n, m;
        memset(dp, -1, sizeof(dp));
        for (int i = 1; i <= 1001; i++)
        { 
            dp[i][1] = 1;
            dp[0][i] = 1;
        }
        cin >> n >> m >> p;
        cout << f(n, m) % p << endl;
        return 0;
    }

AC散花。

错误总结：  
不能忘记取模的优先级，一定要加括号，一直因为这个小问题耽误了60分！！！

# 2\#异球同盘——递归 #

n个各不相同的球放在m个相同的盘子里，问所有情况有多少种？

递推（归）公式：

这个递推公式是用来算**全放满**的可能性的  
 \{ f ( n , 1 ) = 1 f ( n , 0 ) = 1 f ( n , m ) = 1     i f ( n = m ) f ( n , m ) = f ( n − 1 , m − 1 ) + f ( n − 1 , m ) × m     i f ( n ≥ m ) \\left\\\{ \\begin\{array\}\{ll\} f(n,1)=1\\\\ f(n,0) = 1\\\\ f(n, m)=1 \\ \\ \\ if(n = m)\\\\ f(n,m) = f(n - 1, m - 1) + f(n-1, m)\\times m\\ \\ \\ if(n\\ge m)\\\\ \\end\{array\} \\right. ⎩⎪⎪⎨⎪⎪⎧f(n,1)=1f(n,0)=1f(n,m)=1   if(n=m)f(n,m)=f(n−1,m−1)\+f(n−1,m)×m   if(n≥m)

有了这个递推公式，那么就可以把盘子数从小到大循环上去，每次调用一个对应的函数，然后累加结果，就是答案了。

解释：

（1） f ( n , 1 ) = 1 f(n,1)=1 f(n,1)=1 和  f ( n , 0 ) = 1 f(n,0)=1 f(n,0)=1可以理解  
（2） f ( n , m ) = 1 f(n,m)=1 f(n,m)=1因为必须全放满，而且因为是异球同盘，所以n=m时只能有一种情况。  
（3）最后的关系式：分为两个步骤，首先我们先去掉一个球和一个盘子，就是f(n-1,m-1)，使得单独的一个小球与盘子独立，然后算剩下的小球在剩下的盘子里面的排法；但是这样不能使得排法全面，所以我们暂时将盘子放回来，变成m个盘子，小球还在外面，算n-1个球在m个盘子中的排法，为什么要乘m？因为最后一个小球还要放进来，小球可以放在m个位置，而没放在一个位置，都会对应着所有的排法的改变，故乘m。为什么要这么干呢？因为这样可以使得状态逐步向n<m发展，也能计算有堆叠球的情况，这就是状态转移的概念。

/* 问题描述： n个不同的球放在m个同样的盘子中 允许空盘：（大于） 分别计算0个、1个、2个...n-1个空盘的数值，并求和 不允许空盘：题解函数 盘子相同的情况下，如果盘子比球多，则忽略多余的盘子 解法思路：根据第一个小球的情况分情况递归（独自一盘，与它球共处一盘） */
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int ballPlate2(int ballNum, int plateNum)
    { 
    	if (plateNum == 1)
    	{ 
    		return 1;
    	}
    	if (plateNum < 1)
    	{ 
    		return 0;
    	}
    	if (ballNum == plateNum)
    	{ 
    		return 1;
    	}
    	if (ballNum < plateNum)
    	{ 
    		return 0;
    	}
    	int a1, a2;
    	a1 = ballPlate2(ballNum - 1, plateNum - 1);
    	a2 = ballPlate2(ballNum - 1, plateNum);
    	return a1 + a2 * plateNum;
    }
    int ballPlate2_empty(int ballNum, int plateNum)
    { 
    	int sum = 0;
    	for (int i = 0; i <= plateNum; i++)
    	{ 
    		int a = ballPlate2(ballNum, i); // 盘子数不断增加算每一种
    		sum += a; // 累加结果，即为所有结果
    	}
    	return sum;
    }
    int main()
    { 
    	cout << ballPlate2(4, 3) << endl; // 全放满的结果
    	cout << ballPlate2_empty(4, 3) << endl; // 所有结果
    	return 0;
    }

也可以加上记忆化优化。。。

# 3\#同球异盘——插板法 #

这道题倒是用不到递推，我们可以用简单的排列组合插板法解决

也就是将m-1个板子插到n-1个空档中。用程序中的`full_f()`函数解决，但这个只能算出全放满的可能性。

要算出所有结果，我一开始写的是循环，但是错了，其实有一个非常简单的方法直接去算(n + m - 1, m - 1)的插板就行了。我们可以这么理解，插板法都是插在球的内部，那为了插出空盘，就可以将空档增加，增加到盘子外面，这样就有了额外的空档，可以插出空盘，也可以插出全满。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

#include <iostream>
    
    using namespace std;
    int n, m;
    int full_f(int n, int m)
    { 
        int a = 1;
        for (int i = 1; i <= m; i++)
        { 
            a *= (n - i + 1);
        }
        for (int i = 1; i <= m; i++)
        { 
            a /= i;
        }
        return a;
    }
    int d(int n, int m)
    { 
        return full_f(n + m - 1, m - 1);
    }
    int main()
    { 
        cin >> n >> m;
        cout << full_f(n - 1, m - 1) << endl; // 放满结果
        cout << d(n, m) << endl; //所有结果
        return 0;
    }

# 4\#异球异盘——最简单的mn #

既然是异球异盘，我们可以看出来每一个球都有m个选择，每个球还不怕重复，所以n个球m个盘子，那么结果就是mn

#include <iostream>
    #include <math.h>
    using namespace std;
    int binPow(int n, int m) // 快速幂
    { 
        int result = 1;
        while (m != 0)
        { 
            if (m % 2 != 0)
                result *= n;
            n *= n;
            m /= 2;
        }
        return result;
    }
    int fac(int n) // 阶乘factorial
    { 
        int ans = 1;
        for (int i = 1; i <= n; i++)
        { 
            ans *= i;
        }
        return ans;
    }
    
    int f(int n, int m) // 这是异球同盘的程序
    { 
        if (m == 1)
            return 1;
        else if (m == 0)
            return 0;
        if (n == m)
            return 1;
        else if (n < m)
            return 0;
        if (n >= m)
        { 
            int a1 = f(n - 1, m - 1);
            int a2 = f(n - 1, m) * m;
            return a1 + a2 * m;
        }
    }
    
    int bp_empty(int ballNum, int plateNum)
    { 
        return binPow(plateNum, ballNum);
    }
    int bpf(int ballNum, int plateNum)
    { 
        int b = f(ballNum, plateNum);
        int a = fac(plateNum);
        return a * b; // 将盘子的排法和异球同盘相乘
    }
    
    int main()
    { 
        int n, m;
        cin >> n >> m;
        cout << bpf(n, m) << endl; // 全放满
        cout << bp_empty(n, m) << endl; // 所有情况,m^n
        return 0;
    }

# 5\#总结 #

这四个题目的程序思维都不一样，都需要思考很久，有时想了很久都想不出来，出去休息一会回来突然就有了新的思路。。

[http_www.kencoding.net_problem.php_id_1369]: http://www.kencoding.net/problem.php?id=1369
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/83687547d83441cdace558df39c7b282.png