algorithm - パスカルの三角形で繰り返される数を見つける方法は?

Question

パスカルの三角形で数値が繰り返される回数を見つけるアルゴリズムを誰か教えてください。例えば

num - 回数

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

画像用http://mathforum.org/dr.cgi/pascal.html

または、別の言い方をすれば、 ⁿ C _r = x (x は任意の整数) に対して可能な n C r の^数は_{いくつでしょうか?}

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");
     }
 }