Consider a matrix M of size 2k x 2k. A Z-listing of the elements of the matrix is described in the following figure. Part (a) illustrates the special case k = 3. Part (b) describes a recursive strategy for the Z-listing. First break M into four 2k-1 x 2k-1 submatrices and recursively print the submatrices in the order: "top-left", "top-right", "bottom-left" and "bottom-right". When the dimension of the matrix is 1 x 1, the only element of the matrix is printed without further recursive calls.
In this assignment, you are asked to populate a 2k x 2k matrix M with the integers 1,2,3,...,22k in such a manner that the Z-listing of M prints the integers 1,2,3,...,22k in sorted order.
Define a structure to represent a two-dimensional matrix.
#define MAXDIM 50
typedef struct {
unsigned int r; /* row dimension */
unsigned int c; /* column dimension */
int elt[MAXDIM][MAXDIM]; /* 2-d array of the elements of the matrix */
} matrix;
Part 1 [Credit: 20%]
Write a function that accepts a matrix as its sole argument and prints the matrix in the standard row-major order. Print a line break after every row of the matrix.
void printMat ( matrix M );
Now I provide a function that prints the Z-listing of the elements of a matrix. The function assumes that the matrix is of dimension 2k x 2k for some k. The function prints a new-line charater after printing 15 array elements in a line. This line-breaking is controlled by the second argument neltp passed to the function.
int printMatZ ( matrix M, int neltp )
{
matrix N;
int i,j,n;
/* No recursive calls are made for 1 x 1 matrices */
if (M.r == 1) {
printf("%5d", M.elt[0][0]);
if (++neltp == 15) { printf("\n"); neltp = 0; }
return neltp;
}
/* Set the dimensions of the submatrices */
n = (M.r) / 2;
N.r = N.c = n;
/* Recursively print the top left submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[i][j];
neltp = printMatZ(N,neltp);
/* Recursively print the top right submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[i][n+j];
neltp = printMatZ(N,neltp);
/* Recursively print the bottom left submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[n+i][j];
neltp = printMatZ(N,neltp);
/* Recursively print the bottom right submatrix */
for (i=0; i<n; ++i) for (j=0; j<n; ++j) N.elt[i][j] = M.elt[n+i][n+j];
neltp = printMatZ(N,neltp);
return neltp;
}
Part 2 [Credit: 60%]
You are now asked to write a recursive function initMatRec() that, upon input k, returns a 2k x 2k matrix whose Z-listing produces the integers 1,2,3,...,22k in sorted order. Assign values to the array elements in the same order they are printed by the function printMatZ() given above. You may maintain a global counter, or pass a pointer to an integer counter, that generates the integers 1,2,3,...,22k in that sequence.
matrix initMatRec ( unsigned int k, unsigned int *cnt );
Part 3: [Credit: 20%]
Write a function that returns the same matrix as initMatRec() without making any recursive call. Look at the pattern of the array elements for the case k = 3 below and generalize for higher dimensions. More precisely, initially set the top-left element to 1. Then for d = 0,1,2,...,k-1, make three copies with appropriate shifts of the 2d x 2d submatrix at the top-left corner so as to obtain the correct 2d+1 x 2d+1 submatrix at the top-left corner.
matrix initMatItr ( unsigned int k );
Your main() function should look like the following:
int main ()
{
matrix M, N;
unsigned int k;
unsigned int cnt = 0;
printf("k = "); scanf("%u", &k); printf("%u\n", k);
M = initMatRec(k,&cnt);
printf("\nRow-major listing of M:\n");
printMat(M);
printf("\nZ-listing of M:\n");
printMatZ(M,0);
printf("\n");
N = initMatItr(k);
printf("\nRow-major listing of N:\n");
printMat(N);
printf("\nZ-listing of N:\n");
printMatZ(N,0);
printf("\n");
}
Sample output
k = 3
Row-major listing of M:
1 2 5 6 17 18 21 22
3 4 7 8 19 20 23 24
9 10 13 14 25 26 29 30
11 12 15 16 27 28 31 32
33 34 37 38 49 50 53 54
35 36 39 40 51 52 55 56
41 42 45 46 57 58 61 62
43 44 47 48 59 60 63 64
Z-listing of M:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64
Row-major listing of N:
1 2 5 6 17 18 21 22
3 4 7 8 19 20 23 24
9 10 13 14 25 26 29 30
11 12 15 16 27 28 31 32
33 34 37 38 49 50 53 54
35 36 39 40 51 52 55 56
41 42 45 46 57 58 61 62
43 44 47 48 59 60 63 64
Z-listing of N:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64
Report the output of your program for k = 5.
Download the skeleton of the program.