Matrix

[michellee]

Hi! I have homework connected with spiral matrix 5x5. This code is for another problem but it does not work. I want to understand this to have the opportunity to try to solve the spiral matrix.

This problem should look like

0 20 19 17 14
1 0 18 16 13
2 5 0 15 12
3 6 8 0 11
4 7 9 10 0

#include "stdafx.h"
#include <iostream>
using namespace std;
void main()
{
	const int N = 5;
	int a[N][N], i, j, k;

	for (i = 0; i < N; i++)
		a[i][j] = 0;
	for (i = 0; i < N-1; i++)
	for (j = i + 1; j < N; j++)
	{
		k++;
		a[j][i] = k;
	}
	for (i = N - 1; i >= 0;i--)
	for (j = i - 1; j >= 0; j--)
	{
		k++;
		a[j][j] = k;
	}


	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
			cout << a[i][j] << "";
		cout << endl;
	}
	system("pause");
}

[keskiverto]

That code compiles with two warnings:

10:14: warning: 'j' is used uninitialized in this function [-Wuninitialized]
7:21: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]

Line 10: Which elements are set 0?

Line 21: Which elements are set k?

A debug hints:

1. Comment out lines 9-22 and run the program. What is the output? (You are probably "unlucky" and get all 0's.)

2. Comment out only lines 9-16 and set k=10; before line 17. What is the output?

[michellee]

No zeros at all. Big and strange numbers only. With k=10 it's the same, I mean - not the numbers I want.

I dont understand even why we use this 'k' . I dont know whats going out between 17 and 22 line.

[keskiverto]

No zeros at all.

Good. They are random values, because the array has not been initialized with any specific values. Some compilers do zero-initialize memory in some modes, which masks errors.

Oh, line 28, those double quotes print empty string, i.e. nothing visible between numbers on the line.
Change that

""

into

" "

Now, lets modify line 7 into:

int a[N][N] {}; // zero-initialize all elements
int i;
int j = 0;
int k = 0;

If you do keep the lines 9-16 commented, then the 17-22 will be the only code that changes the values in the array.

What do you get now?

[michellee]

ALMOST!

25 0 0 0 0
1 23 0 0 0
2 5 20 0 0
3 6 8 16 0
4 7 9 10 11

[keskiverto]

Good.

However, you had the lines 12-16 nested loop uncommented, because I see the values 1-10 in the lower triangle. That loop works as expected, but it now distracts from the doings of the 17-22 loop.

Furthermore, these loops might overwrite, what the loop on lines 9-10 does. That loop (setting some elements to 0) is now unnecessary, because the entire array is initialized to 0. However, it was the source of a compiler warning:

10:14: warning: 'j' is used uninitialized in this function [-Wuninitialized]

Why? Look closely:

	for (i = 0; i < N; i++)
		a[ i ][ j ] = 0;

What is the value of j? If your code now initializes j to 0, then the loop sets the first column of the array to 0.
I bet that is not the intention. Perhaps the loop should set the diagonal to 0?
If so, different indices have to be used.
The elements of the diagonal are: a[0][0] a[1][1] a[2][2] a[3][3] a[4][4]


Coincidentally, those seem to be the elements that the lines 17-22 loop is writing to (but should not). Perhaps an another indexing error? (The answer is yes.)


What is the k used for? It is written into elements of the array. Each iteration increments the k by one, so we get numbers 1 2 3 4 5 ..
The loop counters decide where to write and the k says what to write.

[michellee]

I thought that

for (i = 0; i < N; i++)
		a[i][j] = 0;

this is about the diagonal elements. I dont understand how everything up from the diagonal elements is now 0. I really dont know how to rewrite 17-22. What do you mean with indexing error?

[whitenite1]

@michellee

Corrected the program, so it has correct output

#include <iostream>

using std::endl;
using std::cout;
using std::cin;

int main()
{
const int N = 5; // Don't initialize over 19 or screen output is affected 
int a[N][N], i, j, k=0; // k initialized

for (i = 0; i < N; i++)
   for (j = 0; j < N; j++)
		a[i][j] = 0;//array a, set to 0
for (i = 0; i < N - 1; i++)
{
  for (j = i + 1; j < N; j++)
  {
   k++;
   a[j][i] = k;
  }
}
k = (N*N) - N; //  If N is changed, k is still correct. k set to highest possible value

for (j = 1; j < N ; j++)
{
	 for (i = 0; i < j;i++)
  {
	a[i][j] = k;
	k--; //Reduce k by 1
   }
	}

for (i = 0; i < N; i++)
{
  for (j = 0; j < N; j++)
  {
	if (a[i][j] < 10)//Just to even out the output, so numbers line up
	cout << " ";
	cout << a[i][j] << " ";
  }
	cout << endl;
}
cout << endl << endl<< "\t\tProgram finished.. Press any key to quit." << endl << endl;
cin >> k;
}

[keskiverto]

Lets "unroll" that loop (because we know that N==5):

i = 0;
a[i][j] = 0; // i==0, j==?
i++;
a[i][j] = 0; // i==1, j==?
i++;
a[i][j] = 0; // i==2, j==?
i++;
a[i][j] = 0; // i==3, j==?
i++;
a[i][j] = 0; // i==4, j==? 

On each diagonal element the row-index is equal to column-index. Therefore:

for ( i = 0; i < N; ++i ) {
		a[ i ][ i ] = 0;
}

I dont understand how everything up from the diagonal elements is now 0.

They are, because we did:
int a[N][N] {}; // initialize all elements
Those braces on modern C++ do initialize every element in the array with the default value for int, which is 0.

That one line does the same as this:

int a[N][N]; // uninitialized
for ( i = 0; i < N; ++i ) {
  for ( j = 0; j < N; ++j )
    a[ i ][ j ] = 0;
}

Here is an another "debugging" program:

#include <iostream>

int main()
{
	const int N = 5;
	int k=10;

	for ( int col = N - 1; 0 <= col; --col ) {
	    for ( int row = col - 1; 0 <= row; --row ) {
		    ++k;
            std::cout << "column=" << col << " row=" << row << " k=" << k << '\n';
        }
	}
    return 0;
}

Run it. The output should contain the (k) values that you want to write to the upper triangle and some other numbers.

Then look at the output that you should get from your program. What are the row and column indices for each value (11..20) that are still missing?

For example, where should value 16 show up? Which row, which column?

[michellee]

column 3 row 1
I dont understand where are you going with this :D
I tried to rewrite 17-22 in some ways but im not getting close to the solution.

[keskiverto]

column 3 row 1

In other words, the value 16 should be in a[1][3]

Now, the last "debugging" program did write out on one line:

column=3 row=1 k=16

Is it a coincidence that the loop has values 1, 3 and 16?
Wouldn't a[row][col] = k; at least on that iteration store a right value (16) into right place a[1][3]?

What about the other iterations? Do they too have appropriate row and col values to match the k?