Quant interview的一道编程题

有多少个十八位数（首位不能为0）满足条件：没有1个数字在该数中出现3次以上？这是一道编程题！大家有没有什么想法？

这个论坛也研究编程问题？楼主早上6点半都起来发帖，先顶一个。。
不过这个题目初步思想可以把这个18位数视数组a【1】...a【18】用程序循环并计数得出结果。
还有这题貌似能用排列组合思想计数，假定最高位不为0然后后面排列组合，排除出现3次以上的情况，似乎计算不如写个循环程序运行的快，不过作为研究可以试一下。
恕我不能写出详细过程，我只是个业余者，距离我考计算机四级已经近8年了，毕业都快7年了，有点力不从心啊。

2# zziliwgh 不是的，我在美国，只是晚上发帖罢了。这个问题编程的难度在于如果用brute force，运行速度会非常慢，所以一定要找一种提高速度的方法。我原来也想用排列组合的方法算，化归该问题成30个数{0，0，0，1，1，1，。。。，9，9，9}选18个放到18个格子中，第一格只能从非零的元素中选，这样形成的不同的数的个数有多少。结果越想越晕，因为这样重复的数次数很难计算。

我觉得你这样化为30个数进行排列组合，你想想是不是程序的计算量突然增加了不少，这样对你的目的不合吧。我确实没考虑到你是在国外，呵呵，还以为你是在中国呢。

我又想了一下，计算量都很大，不实际动手不好判断哪个计算量更大。我的思路就是写18层嵌套循环，排除法穷举计数得出结果。好像这样以现在的计算能力恐怕不知多久才能运行结束。这种方法几乎不可取。接近于暴力那种，不知道新的程序思想是怎么搞定这个问题的。
如果分段的话不知道有没有合适的算法，考虑下矩阵能不能搞，我上班了

很像初中数学竞赛的题 呵呵
出了暴力运算之外 你可以这样想：(a) no 0; (b) one 0;(c) two 0.
if (a), 那么这就是一个简单的排列组合。两组这个的（1，2，3，4，5，6，7，8，9）排列，你可以用数学技巧算也可以循环做
if (b), 那就再分9种情况，分别是 no 1, no 2, no 3,.....
if (c), etc.....

5# archwizard 你说的（a）的情况就没那么容易算了，其实应该是（1 to 9）*3中(即27个数中)选18个数排列还要不重复，怎么算？

假设有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次都有可能。
}

简单验证了一下，如果是从2个数字中找到3位数，即n=2，m=3，可能的情况共有112，121，122，211，212，221等6种，程序返回为6。如果是从2个数字中找2位数，可能情况为12，11，21，22等4种。程序返回为4，我的金币啊啊啊~~
对了，由于上面的程序中是包括了0为首位的情况的，所以如果首位不包括0的话可以把结果乘以0.9，因为每一个数字开头都是等概率事件。

blackwood_li 发表于 2009-10-16 17:46
假设有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次都有可能。
}

高手，充币来的，哈哈，给他吧，不过这个解法也是暴力的，运算量太大

7# blackwood_li



你的解答的问题在于：
1.每个数字最多可以出现3次，你考虑的是每个数字最多可以出现2次
2.就算问题是不能出现三次及三次以上，也并不表示每个数必然出现2次，事实上完全可以做到两个数字出现1次，其余16个出现2次的情况（用鸽笼原理即知）)


我真的很想把论坛币给你，拜托再仔细想想好吗？