2

この変換に頭を悩ませています。2D NxN 行列をその z オーダー バージョンに再帰的に変換したいと考えています。

たとえば、与えられた配列：

[ 1  2 ]
[ 3  4 ]

Zオーダーは

[ 1 2 3 4]

z オーダー変換の再帰的な手順は何ですか?

4

2 に答える 2

4

再帰的な方法は簡単です:

  • 左上にアクセス
  • 右上にアクセス
  • 左下にアクセス
  • 右下にアクセス

コード内

#include <iostream>

template<typename M, typename CBACK>
void zorder(const M& m, int y0, int x0, int size,
            CBACK cback)
{
    if (size == 1) {
        // Base case, just one cell
        cback(m[y0][x0]);
    } else {
        // Recurse in Z-order
        int h = size/2;
        zorder(m, y0,   x0,   h, cback); // top-left
        zorder(m, y0,   x0+h, h, cback); // top-right
        zorder(m, y0+h, x0,   h, cback); // bottom-left
        zorder(m, y0+h, x0+h, h, cback); // bottom-right
    }
}

void print(int x) {
    std::cout << x << " ";
}

int main(int argc, const char *argv[]) {
    int x[][4] = {{ 1,  2,  3,  4},
                  { 5,  6,  7,  8},
                  { 9, 10, 11, 12},
                  {13, 14, 15, 16}};
    zorder(x, 0, 0, 4, print);
    std::cout << std::endl;
    return 0;
}

このプログラムの出力は

1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16

別の非再帰的アプローチもあることに注意してください: z オーダーで要素にアクセスするには、カウンターを反復処理し、奇数ビットを y として、偶数ビットを x として取ることができます (ビットを 0 から数えます)。

int zorder_x_of(int index) {
    int x = 0;
    for (int b=0,k=0; (1<<b) <= index; b+=2,k++) {
        x += ((index & (1<<b)) != 0) << k;
    }
    return x;
}

int zorder_y_of(int index) {
    return zorder_x_of(index>>1);
}

template<typename M, typename CBACK>
void zorder2(const M& m, int size, CBACK cback)
{
    for (int i=0; i<size*size; i++) {
        cback(m[zorder_y_of(i)][zorder_x_of(i)]);
    }
}

ノート：

上記のコード サンプルでは、​​「コールバック」( という名前cback) を受け入れる関数を作成しました。この関数は、行列の要素を一度に 1 つずつ z オーダーで呼び出します。

マトリックスとしてもコールバックとしても使用できるようにするために、二重[]インデックスをサポートするものと呼び出すことができるものをすべて使用できるようにするために、C++ テンプレートを使用しました。

メイン プログラム as matrix では、整数の 2 次元配列と関数を使用しましたが、コードは、たとえばstd::vector< std::vector< double > >as マトリックスと、コールバックとして提供するクラスのオブジェクト インスタンスを使用してもコンパイルさoperator()(double)れます。

于 2013-10-06T22:33:50.860 に答える
0

2D マトリックスは内部で 1D 配列として動作します。つまり、すでに "Z オーダー" になっています。

最初の要素を指すポインターを、列NxMの数と行の数まで繰り返すだけです。NM

例：

int arr[2][2] = {{2,4},{3,5}};
for (int i=0; i<2 * 2; ++i){
    std::cout << *(&arr[0][0] + i);  // or *(arr + i)
}
于 2013-10-06T21:51:07.447 に答える