3

仮定する：

2D array:  abcdef
           ghijkl
           mnopqr

長さ幅*高さの単純な文字列に格納されているので、それをarrと呼びましょう。

arr = abcdefghijklmnopqr
width = 6
height = strlen ( arr ) / width

目標は、この配列を45度（PI / 4）回転させて、次の結果を取得することです。

arr = abgchmdinejofkplqr
width = 3
height = 8
converted to 2D array:  a..
                        bg.
                        chm
                        din
                        ejo
                        fkp
                        .lq
                        ..r

私はこの変換を行う方法を理解するために数時間を費やし、いくつかの半機能的な解決策を考え出しましたが、それを完全に機能させることはできません。これを解決するアルゴリズムを説明/作成できますか？できればCで。

助けてくれてありがとう

編集：これは私がすでに試したことです編集
2：45度の回転の目的は、対角線を線に変えて、strstrを使用して検索できるようにすることです。

// this is 90 degree rotation. pretty simple
for ( i = 0; i < width * height; i++ ) {
  if ( i != 0 && !(i % height) ) row++;
  fieldVertical[i] = field[( ( i % height ) * width ) + row];
}   

// but I just can't get my head over rotating it 45 degrees. 
// this is what I've tried. It works untile 'border' is near the first edge.

row = 0;
int border = 1, rowMax = 0, col = 0; // Note that the array may be longer
// than wider and vice versa. In that case rowMax should be called colMax.

for ( i = 0; i < width * height; ) { 
  for ( j = 0; j < border; j++, i++ ) {
    fieldCClockwise[row * width + col] = field[i];
    col--;
    row++;
  }

  col = border;
  row = 0;
  border++;
}

私のコードの「境界線」は架空の境界線です。ソースでは、対角線を区切る対角線です。結果として、それは各行の間の水平線になります。

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

それらのスラッシュは私たちの境界線です。アルゴリズムは非常に単純で、最初の数字が1、次に2、次に6、次に3、次に7、次に11、次に4というように三角形を読み取る必要があります。

4

3 に答える 3

2

インスピレーションを得るためにhttp://en.wikipedia.org/wiki/Shear_mappingを見て、次のPythonコードを作成しました。

a = [['a', 'b', 'c', 'd', 'e', 'f'],
     ['g', 'h', 'i', 'j', 'k', 'l'],
     ['m', 'n', 'o', 'p', 'q', 'r']]

m = 1 # 1/m = slope

def shear_45_ccw(array):
    ret = []
    for i in range(len(array)):
        ret.append([0] * 8)
        for j in range(len(array[i])):
            ret[i][int(i + m * j)] = array[i][j]
    return ret

print(shear_45_ccw(a))

生成：

[['a', 'b', 'c', 'd', 'e', 'f', 0, 0], 
 [0, 'g', 'h', 'i', 'j', 'k', 'l', 0], 
 [0, 0, 'm', 'n', 'o', 'p', 'q', 'r']]

それはあなたが望むもののようなものです。アルゴリズムは、Pythonであっても、読みやすいものであることが望まれます。それの肉はこれです：ret[i][int(i + m * j)] = array[i][j]。幸運を！アレイを初期化したときにだましました。とにかく、Cでは別の方法で対処する必要があります。

編集：また、私はあなたの結果が反転した理由がわかりませんでした：あなたが正しい行動を起こすことができると私は信じています。

于 2012-11-24T23:47:19.460 に答える
1

これを45度回転ではなく、斜めスキャンと呼びます。

あなたの例では、対角線は左下に走っています。それらを列挙することができます1、2、...：

123456
234567
345678

これは、外側のループの反復のカウンターになります。内側のループは1、2、または3回の反復で実行されます。ある番号の付いた記号から別の記号にジャンプするには、同じようにするか、線形インデックスにcol--; row++;追加します。width-1

....5. (example)
...5..
..5...

コード（未テスト）：

char *field;
int width = 6;
int height = 3;
char *field45 = malloc(width * height);
int diag_x = 0, diag_y = 0; // coordinate at which the diagonal starts
int x, y; // coordinate of the symbol to output
while (diag_y < height)
{
    x = diag_x; y = diag_y;
    while (x >= 0 && y < height) // repeat until out of field
    {
        *field45++ = field[y * width + x]; // output current symbol
        --x; ++y; // go to next symbol on the diagonal
    }
    // Now go to next diagonal - either right or down, whatever is possible
    if (diag_x == width - 1)
        ++diag_y;
    else
        ++diag_x;
}

別の方向に「回転」させたい場合は、コードの周囲に変更し、ループの境界チェックを反対++方向に変更することをお勧めします。--

さらに、(x,y)座標を1つのインデックスで置き換えることができます（で置き換える++y）index+=width。(x,y)わかりやすくするために使用しました。

于 2012-11-26T22:15:07.710 に答える
0

私は上記の助けを借りて、例によってこれを解決したいと思います：

import pandas as pd
import numpy as np
bd = np.matrix([[44., -1., 40., 42., 40., 39., 37., 36., -1.],
                [42., -1., 43., 42., 39., 39., 41., 40., 36.],
                [37., 37., 37., 35., 38., 37., 37., 33., 34.],
                [35., 38., -1., 35., 37., 36., 36., 35., -1.],
                [36., 35., 36., 35., 34., 33., 32., 29., 28.],
                [38., 37., 35., -1., 30., -1., 29., 30., 32.]])
def rotate45(array):
    rot = []
    for i in range(len(array)):
        rot.append([0] * (len(array)+len(array[0])-1))
        for j in range(len(array[i])):
            rot[i][int(i + j)] = array[i][j]
    return rot

df_bd = pd.DataFrame(data=np.matrix(rotate45(bd.transpose().tolist())))
df_bd = df_bd.transpose()
print df_bd

その出力は次のようになります。

44   0   0   0   0   0   0   0   0
42  -1   0   0   0   0   0   0   0
37  -1  40   0   0   0   0   0   0
35  37  43  42   0   0   0   0   0
36  38  37  42  40   0   0   0   0
38  35  -1  35  39  39   0   0   0
0   37  36  35  38  39  37   0   0
0    0  35  35  37  37  41  36   0
0    0   0  -1  34  36  37  40  -1
0    0   0   0  30  33  36  33  36
0    0   0   0   0  -1  32  35  34
0    0   0   0   0   0  29  29  -1
0    0   0   0   0   0   0  30  28
0    0   0   0   0   0   0   0  32

于 2017-08-19T08:07:12.790 に答える