求解一条简单的NOIP题将n个不同颜色的球放入k个无标号的盒子中(n≥k,且盒子不允许为空)的方案数为S(n,k),例如:n=4,k=3时,S(n,k)=6,当n=6,k=3时,S(n,k)=______帮我解一下这个递归方程就好
来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/15 23:27:57
求解一条简单的NOIP题将n个不同颜色的球放入k个无标号的盒子中(n≥k,且盒子不允许为空)的方案数为S(n,k),例如:n=4,k=3时,S(n,k)=6,当n=6,k=3时,S(n,k)=______帮我解一下这个递归方程就好
求解一条简单的NOIP题
将n个不同颜色的球放入k个无标号的盒子中(n≥k,且盒子不允许为空)的方案数为S(n,k),例如:n=4,k=3时,S(n,k)=6,当n=6,k=3时,S(n,k)=______
帮我解一下这个递归方程就好,我没学过递归方程
S₂(n,k)=kS₂(n-1,k)+S₂(n-1,k-1)
求解一条简单的NOIP题将n个不同颜色的球放入k个无标号的盒子中(n≥k,且盒子不允许为空)的方案数为S(n,k),例如:n=4,k=3时,S(n,k)=6,当n=6,k=3时,S(n,k)=______帮我解一下这个递归方程就好
s(n,k)表示将n个不同颜色的球放入k个无标号的盒子中的方案数,
根据分类加法原理,将s(n,k)个方案分为两类,
1),第n个球单独在一个盒子内,则前n-1个球在k-1个盒子内,这类方案数为s(n-1,k-1);
2),第n个球不单独在一个盒子内,则先将前n-1个球放在k个盒子内,即s(n-1,k),然后将第n个球放在k个盒子的任意一个里,即k*s(n-1,k);
所以,有S(n,k)=kS(n-1,k)+S(n-1,k-1).
边界情况不解释,具体可看南大版中学高级本教材···
随便写个记忆化搜索好吧?
你做的是NOIP的初赛题吧。
你都写出来方程了,然后手工模拟递推一下就可以了。
此类方程的通项公式非常麻烦,需要很多高级知识,一般都是带无理数之类的东西,不会加快你的计算,我不会,NOIP也不要求。
你强
我贝司奏