假设有0个1,那么剩下的问题就是在9个数字中找个18位数,每个数字不能出现不能超过三次,等于每个数字必然出现两次。然后递归下去。。。
假设有1个1,共有18种可能的位置,剩下的问题就是在9个数字中找个17位数,每个数字不能出现不能超过三次,然后递归下去。。。
假设有2个1,共有18*17/2种可能的位置组合,剩下问题就是在9个数字钟找个16位数,每个数字不能出现超过三次。然后递归下去。。。
用程序伪代码应该就是这样的,一个函数long count(int n,int m)代表从n个数字中找个m位数,每个数字出现次数不超过三。
long count(int n,int m){
if(n==1) {
return 1;
}
else if (m>2n) {
return 0;//这样必然出现3个以上的重复数字。
} else if(m==2n){
return m*(m-1)/2*count(n-1,m-2);//之后每个数字必然出现2次。
} else if (m==2n-1) {
return m*count(n-1,m-1) + m*(m-1)/2*count(n-1,m-2);//每个数字可能出现1次或者2次
} else {
return count(n-1,m)+m*count(n-1,m-1)+m*(m-1)/2*count(n-1,m-2);//每个数字出现0次1次2次都有可能。
}
|