1

N x N のオブジェクトの 2 次元配列があるとします。水平、垂直、または斜めに隣接するすべてのオブジェクトのペアからペアを作成できると仮定します。N の任意の値に対して一意のペアがいくつあるかをどうやって数えることができますか?

たとえば、N = 2 の場合

0 1
2 3

01 02 03 21 23 31 を取得できます。03 は 30 と同じであることに注意してください。

特定の N に対してこれらのペアがいくつ存在するかを判断する式はありますか?これらを生成するためのさらに優れたアルゴリズムはありますか?

言語はそれほど重要ではありませんが、c++ を使用します。

以下のアルゴリズムを使用して重複するインデックスを削除すると、次のカウントが得られます。式はまだわかりません。

For size N=2
Unique pairs is =6
For size N=3
Unique pairs is =20
For size N=4
Unique pairs is =42
For size N=5
Unique pairs is =72
For size N=6
Unique pairs is =110
For size N=7
Unique pairs is =156
For size N=8
Unique pairs is =210
For size N=9
Unique pairs is =272

興味深いことに、式は 2^2+2、4^2+4、6^2+6、8^2+8 ... のようです。

4

3 に答える 3

1

ペアの各タイプの代表的なオブジェクトを選択するのが最も簡単だと思います (つまり、垂直ペアの一番上のオブジェクト、水平ペアの左端のオブジェクト、対角線のペアを選択します)。これにより、n(n-1)縦のペア、n(n-1)横のペア、および2(n-1)^2斜めのペア (各品種の等量) が得られます。2(n-1)(n+n-1)=2(n-1)(2n-1)あなたの推測と一致して、合計はになります。

于 2013-10-17T03:33:50.190 に答える
1

各行には n-1 行内ペアがあり、n 行あります。

各列には n-1 個の列内ペアがあり、n 個の列があります。

行の各隣接ペアには 2*(n-1) 対角線ペアがあり、(n-1) 隣接行ペアがあります。

これらの数値を掛けて足すと、解が得られます。

于 2013-10-17T04:20:00.640 に答える