algorithm - 如何找到一个数字在帕斯卡三角形中重复的次数？

Question

谁能给出一个算法来找到一个数字在帕斯卡三角形中重复的次数？例如

num - 次数

1 - infinite
2 - 1
3 - 2
4 - 2
.   .
6 - 3
.   .
10 - 4
.   .

图片http://mathforum.org/dr.cgi/pascal.html

^{或者以其他方式，对于n} C _r = x可能有多少ⁿ C _r，其中 x 是任何给定的整数？

Answer 1

数一数。你知道 n > 1 只能出现在帕斯卡三角形的前 n+1 行。并且每一行都是对称的，并且增加（对于前半部分）。这样可以节省时间。

有关序列的更多信息，请参见http://oeis.org/A003016

Answer 2

我不得不为黑客马拉松挑战写一些类似的东西。此代码将在大小为 PASC_SIZE 的帕斯卡三角形中查找计数大于 MINIMUM_COUNT 的所有数字 1 到 MAX_NUMBER_TO_SEARCH。您显然可以将其更改为仅计算一个数字。显然不是超级有效。

function pasc(n) {
     var xx = [];
     var d = 0;
     var result = [];
     result[0] = [1];
     result[1] = [1, 1];
     for (var row = 2; row < n; row++) {
         result[row] = [1];
         for (var col = 1; col <= row - 1; col++) {
             result[row][col] = result[row - 1][col] + result[row - 1][col - 1];

             result[row].push(1);
         }
         for (var ff = 0; ff < result[row].length; ff++) {
             xx[d++] = (result[row][ff]);
         }
     }
     return xx;
 }

 function countInArray(array, what) {
     var count = 0;
     for (var i = 0; i < array.length; i++) {
         if (array[i] === what) {
             count++;
         }
     }
     return count;
 }

 var MAX_NUMBER_TO_SEARCH = 5000;
 var MINIMUM_COUNT = 5;
 var PASC_SIZE = 1000;

 var dataset = pasc(PASC_SIZE);
 for (var i = 0; i < MAX_NUMBER_TO_SEARCH; i++) {
     if (countInArray(dataset, i) >= MINIMUM_COUNT) {
         console.log(i + " Count:" + countInArray(dataset, i) + "\n");
     }
 }