某一個演算法
¶某一個演算法
原文連結: https://darkblack01.blogspot.com/2012/01/suppose-that-matrix-m-is-stored-in.html
移植時的最後更新日期: 2015-12-23T14:16:57.624+08:00
0 1 5 6 14 ···<o:p></o:p>
2 4 7 13 ···<o:p></o:p>
3 8 12 ···<o:p></o:p>
9 11 ···<o:p></o:p>
10 ···<o:p></o:p>
Please give the mapping function from m[i][ j] to a[k]. Note that the upper left corner of m is the<o:p></o:p>
first element m[0][0], the first element of a is a[0], m[0][1] = 1 and m[0][2] = 5. (8%)<o:p></o:p>
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][-1i+b] = k : m[-1i+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;
}
發表於