let me put my question in a simpler way,i have a 8 x 8 matrix.... from that matrix i want to read the elements like the link below and want to store in a 1-D buffer .
There is a function used to show that NxN has the same
cardinality as N (Here N is the set of natural numbers starting at
zero)
consider a point in NxN, <m,n>, then
f(m,n) = 1/2[(m+n)^2 +3m+n] defines a one-to-one onto relationship
between the desired sets.
This function "moves" in the zig-zag pattern you want.
so given an 8x8 matrix (however you implement that) I will
assume you access it as your_matrix[m][n], then the assignement
to a vector would be
first you need to compute a number
int j = (7 >= m+n ? 0:(m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0:(m+n - 7)); i++)
j += 2i ;
if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
plz can you explain more by a small code??
You are perfectly on track !!!
The code posted earlier is exactly what is required.
To make it more clear:
You were trying to generate the zig-zag sequence algorithmically
And I have suggested to hard-code it in your code itself in the form of 8x8 matrix.
Ofcourse assuming 8x8 the only type you deal with.
Thats is because your indices are wrong.
I made the change ion the code below
The function works, but It could be cleaned up a bit.
Originally posted by maxima
hi souldog,
your given function is interesting. but it is not giving me the correct result.
i wrote a small code for this.......
Code:
#include<stdio.h>
int main()
{
int my_vector[65];//buffer
int my_matrix[8][8] = { { 0,1,5,6,14,15, 27, 28 },
{ 2,4,7,13,16,26,29,42},
{ 3,8,12,17,25,30,41,43},
{ 9,11,18,24,31,40,44,53},
{ 10,19,23,32,39,45,52,54},
{ 20,22,33,38,46,51,55,60},
{ 21,34,37,47,50,56,59,61},
{ 35,36,48,49,57,58,62,63}
};
for(int m=0;m<8;m++) //CHANGE UPPER LIMIT TO EIGHT
for(int n =0;n<8;n++) //CHANGE UPPER LIMIT TO EIGHT
{
int j = (7 >= m+n ? 0 : (m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;
my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];
}
for(m=0;m<64;m++) printf("%d\n",my_vector[m]);
return 0;
}
if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
plz can you explain more by a small code??
thanks
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."
This is a prodecural approach using stepwise refinement.
Say you have two indexes i and j. The start condition is i=j=0 and the end condition is i=j=7. The indexes can 'move' in two diagonal directions diag_up and diag_down. There are four 'borders' that can be reached border_1 to border_4. When a border is reach the indexes can be advanced in four ways, advance_1 to advance_4 and the direction changes.
In pseudo code this translates to,
Code:
boolean up = true; // direction
int i=j=0; // start
while (!(i == 7) && (j ==7 )) { // stop
if (border_1()) { // a border is reached
advance_1(); up = !up; // advance and change direction
} else if (border_2()) {
advance_2(); up = !up;
} else if (border_3()) {
advance_3(); up = !up;
} else if (border_4()) {
advance_4(); up = !up;
} else { // no border
if (up) diag_up(); else diag_down(); // cont. is same dir.
}
}
What remains is to identify the actual index increments/decrements. For example diag_up is i++, j--. Lim_1 is j==0. Advance_1 is i++.
Originally posted by _uj
This is a prodecural approach using stepwise refinement.
Well, this is the first refinement. You have to change the pseudocode a little because you can reach two borders at the same time. As a matter of fact one such two-border position constitutes the end criteria.
This is a simple to understand procedural version. Say you have an 8x8 chessboard. You start in the 0,0 position then you walk diagonal up. If you land outside the chessboard you correct the position and change walking direction. You can land outside the chessboard in 5 different places,
Code:
int d=1; // start direction (diagonal up)
int i=0, j=0; // index
for (int k=0; k<64; k++) { // all chessboard squares
// TRACE(STR(k) + ":" + STR(i) + "/" + STR(j));
output_buffer[k] = chess_board[i,j];
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
Originally posted by maxima
chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.
I've run the chessboard algoritm with your index matrix. If you run the code snippet below you'll see that the elements come out in the expected order, namely: 1,2,3, ....... 63,64. Now you just have to plug in my_matrix instead and assign the elements to a 64 element int array using the k index. Use it if you like, it does the expected.
Code:
int my_index[8][8] =
{{1 , 2 , 6 , 7 , 15 , 16 , 28 , 29},
{3 , 5 , 8 , 14 , 17 , 27 , 30 , 43},
{4 , 9 , 13 , 18 , 26 , 31 , 42 , 44},
{10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
{11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
{21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
{22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
{36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
for (int d=1,i=0,j=0,k=0; k<64; k++) { // all chessboard squares
TRACE(STR(my_index[j][i])); // println
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
PS. TRACE and STR are just a way to print numbers.
To make the algoritm general and work for all 'chessboard' sizes like 9x9 you'll have to take care of the 'outside right and top' case too which would be easy.
algorithm needed
Reply With Quote
You have to change the pseudocode a little because you can reach two borders at the same time. As a matter of fact one such two-border position constitutes the end criteria.
Bookmarks