n x n matrix transposition recursive algorithm.

[maev]

Warm welcome to all of you, programmers.

In fact I'm beginning my journey with coding, and I just encountered
my first real problem. I would like to find the solution by my own, but
it isn't easy at all.

My main goal is to code simple console application, which can
transpose n x n matrix. I need some help with the algorithm itself. As
far I do know, it should use recursion. I consider it as a challenge.

But can you spare me some tips ? Actually I have no clue how to shape
it up.

best regards !

M.

 

[Heinz Ozwirk]

My main goal is to code simple console application, which can
transpose n x n matrix. I need some help with the algorithm itself. As
far I do know, it should use recursion.

Why do you think you should use recursion? Transposing a matrix A simply means swapping all elements A[j] and A[j]. I don't see any recursion there, only two nested loops:

for (int i = 0; i < n; ++i)
for (int j = 0; j < i / 2; ++j)
std::swap(a[j], a[j]);

Heinz

 

[Gavin Deane]

Warm welcome to all of you, programmers.

In fact I'm beginning my journey with coding, and I just encountered
my first real problem. I would like to find the solution by my own, but
it isn't easy at all.

My main goal is to code simple console application, which can
transpose n x n matrix. I need some help with the algorithm itself. As
far I do know, it should use recursion. I consider it as a challenge.

But can you spare me some tips ? Actually I have no clue how to shape
it up.

Presumably you have enough C++ understanding to write a console program
and to implement some logic once you know what logic you need to
implement.

Get a pencil and a piece of paper. Write down step by step instructions
for how to transpose a 2x2 matrix. Write them in sufficient detail (a
separate instruction for each logical action) that you could give any
2x2 matrix, plus your step by step instructions, to a non-mathematician
and they could transpose the matrix for you. Note that you haven't been
near a C++ compiler yet.

Now, start with

int main()
{
// Define a variable to hold your initial matrix and another
// to hold your transposed matrix. I would suggest a
// std::vector of std::vectors.

// Your logic goes here.

// Display the initial and the transposed matrices
// so you can see that the program worked.
}

and replace

// Your logic goes here

with the C++ implementation of your step by step instructions.

That's 2x2 done. Go back to your pencil and paper and write out the
instructions for transposing a 3x3 matrix. Go down to the same level of
detail. Consolidate your two sets of instructions into one set that
doesn't explicitly mention the matrix size anywhere.

Modify the logic in your program to follow this latest set of
instructions. Now you've got a program that transposes an n x n matrix.

If you have any problems getting code to work, the guidelines in this
FAQ explain how to get help.

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.8

Gavin Deane

 

[maev]

Thank you Heinz for fast and clearly answer. I am ashamed because of
simplicity of the solution. I seriously need to work with my
concetration and focus.

As for me, next thing to do is to implement this one in simple MPI
application. Actually I mean coding parallel calculation of matrix
transposition with using from 3 - 4 processors. Off to work I go !

To define recursion we must first define recursion ;-)

Mae