次の表に使用できる閉じたフォームがありますか？

Question

以下は、現在のセルの値が上のセルと左のセルの合計であるため、再帰的関係を持つテーブルです。

Iは最初の列に示されるようv(x)を付し、任意の所与の行の奇数の位置を見つけたいです。

現在、私は新しい合計値で更新し、各位置の値が奇数か偶数かを文字通りチェックする2つの配列を維持しています。

奇妙な位置が何であるかを直接言うことができる閉じた形がありますか（たとえば、4行目の場合、p1とp4が奇妙な場所であると言わなければなりません）。

特定のパターンに従っているので、各値を計算してチェックするのではなく、数学的に私に位置を教えてくれる閉じたフォームが存在するはずです。

何か助けていただければ幸いです。ありがとう。

Answer 1

あなたが見ている数字は、パスカルの三角形の数字で、ちょうど90度回転しています。あなたは、より典型的には、それは次のように書き出さ参照：

   1 
      1 1 
      1 2 1 
     1 3 3 1 
     1 4 6 4 1 
    1 5 10 10 5 1 
    1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
      ... 

あなたは（あなたの視点に応じて、または右）のストリップを左に下る対角線のストライプに沿ってパスカルの三角形を切断している、とあなたが求めている質問はどのようにあります各ストライプ内の奇数の位置を求める。

Lucas's theoremと呼ばれる数学的結果があります。これは、パスカルの三角形内の特定のエントリが偶数か奇数かを判断するのに便利です。パスカル三角形の行m、列nのエントリは（m choose n）で与えられ、ルーカスの定理によれば、（mはnを選択する）mod 2（奇数なら1、そうでなければ0） mとnのnがmがそのビットセットを持たない位置に設定されたビットを有する場合、（mはnを選択する）は偶数である。そうでなければ、（mはnを選択する）が奇数である。

例として、（5を選択してください）3を試してみましょう。 5のビットは101である.3のビットは011である.2のビット3がセットされ、2のビット5がセットされないので、量（5を選択する3）は偶数でなければならない。そして（5は3を選ぶ）= 10なので、これは本当に事実です！

関係演算子を使って擬似コードで

、あなたは基本的に次のことをしたい：

if ((~m & n) != 0) { 
    // Row m, entry n is even 
} else { 
    // Row m, entry n is odd. 
}