某一個演算法

Suppose that a matrix m[ ][ ] is stored in a linear array a[ ] with the following sequence:

0 1 5 6 14 ···

2 4 7 13 ···

3 8 12 ···

9 11 ···

10 ···

Please give the mapping function from m[i][ j] to a[k]. Note that the upper left corner of m is the

first element m[0][0], the first element of a is a[0], m[0][1] = 1 and m[0][2] = 5. (8%)

Sol)

將數列排成這樣
m[i][j]=k, i+j
m[0][0]=0,   0
m[0][1]=1,   1
m[1][0]=2,   1
m[2][0]=3,   2
m[1][1]=4,   2
m[0][2]=5,   2
m[0][3]=6,   3
m[1][2]=7,   3
m[2][1]=8,   3
m[3][0]=9,   3
m[4][0]=10, 4
...
程式分成幾個步驟，圖的紅線和藍線
紅線為執行運算

為保持紅線的走訪方向，假設直線方程式y=ax+b
a=-1, b=i+j;

藍線為執行控制
判斷b的奇偶，執行i, j對調

將數列切割成下列的樣子：

m[i][j]=k, i+j
m[0][0]=0,   0


m[0][1]=1,   1
m[1][0]=2,   1

m[2][0]=3,   2
m[1][1]=4,   2
m[0][2]=5,   2

m[0][3]=6,   3
m[1][2]=7,   3
m[2][1]=8,   3
m[3][0]=9,   3

m[4][0]=10, 4

...



#include <iostream>

using namespace std;

int main()
{
    bool T = false;
    int i, j, k, b = 0;

    const int size = 10;

    int m[size][size];

    for (j = 0; j < size ; ++j){
    for (i = 0; i < size ; ++i){
        m[i][j] = 0;
    }}
    i = 0, k = 0 ;

    while (i < size && i<=b)
    {
        T ? m[i][-1*i+b] = k : m[-1*i+b][i] = k;
        (i == b) ? i = 0, T = T ? false : true, b++ : i++;
        k++;
    }

    for (j = 0; j < size ; ++j){
    for (i = 0; i < size ; ++i){
        printf("%3d  ", m[i][j]);
    }   printf("\n");
    }
    return 0;
}