Re: array lines shifting
From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 06/25/04
- Next message: Karl Heinz Buchegger: "Re: array lines shifting"
- Previous message: Karl Heinz Buchegger: "Re: array lines shifting"
- In reply to: Ronen Kfir: "Re: array lines shifting"
- Next in thread: Ronen Kfir: "Re: array lines shifting"
- Reply: Ronen Kfir: "Re: array lines shifting"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 25 Jun 2004 10:10:54 +0200
Ronen Kfir wrote:
>
> Karl Heinz Buchegger <kbuchegg@gascad.at> wrote in message news:<40DAB725.F230ED2B@gascad.at>...
> > Ronen Kfir wrote:
> > >
> > [snip]
> > > else
> > > {
> > > for (j=1;j<=x;j=j-m)
> >
> >
> > What's that supposed to do?
> >
> > j starts with a value of 1. m is a positive number
> > (you insured that by testing the users input). What
> > do you think will happen when you calculate j - m
> > will it get bigger or smaller ?
>
> for (j=1;j<=x;j=j-m)
> Is suppose to do the thing this program is ment to do, I'm just not
> very sure about the way...
So the next question is:
What is it ment to do?
Take paper and pencil and do some tests.
assume you have entered a value of 5 for x and a value of 2 for m
j x m
j = 1 1 5 1
j <= x yes
j = j - m 0 5 1
j <= x yes
j = j - m -1 5 1
j <= x yes
j = j - m -2 5 1
j <= x yes
j = j - m -3 5 1
...
so j gets smaller and smaller, each time the loop is
run through.
Honestly. I think you make the same mistake so many
people make. A computer is *not* something magical.
A program is *not* something magical. It doesn't work
the way, that you just write something and the computer
figures out what you ment. A computer is like a baby.
You have to tell him everything up to the least detail
to make him do what you want him to do.
At the time you start programming you *must* be able to
solve the problem with paper and pencil and have analyzed
exactly what you have done. Every step. In which order
and why.
"Computer, remodulate shields to match the phaser frequency"
works on the Enterprise only.
> As I wrote before: Lines in the array should shift from their current
> place- upward, determined by the value m holds. I tried to change the
> value of j, with respect to m value.
> See example above.
Start with paper and pencil.
This is your array:
1 12 5
7 5 3
9 7 2
then make a mark on paper, which axis is the first array
index, and which one is the second array index (is rows
or columns the first array index), eg.
1. index ----->
2. index 1 12 5
| 7 5 3
| 9 7 2
v
ok. Now that this is fixed down, it shouldn't be a problem
any more, to use the indexing in a consistent way.
What is the goal, the goal is, to rotate array rows, the
first row should become the last and all other rows move
one row upwards. (Yes. I know you want to rotate n rows
where n doesn't have to be 1. But since you couldn't manage
to do it for n, do it for 1. That's general: If something
is complicated, solve a simpler problem. Once you know how
to solve the simpler problem, look at the solution and see
how you can use the simpler solution to solve the harder
problem. In the above a strategy that comes to mind immediatly
is: If I have a function which can rotate by 1 row, I can call
it n times to rotate by n rows. Not very efficient, but it
solves the problem. Another general rule: Better a solution
which is not efficient but works as to have a solution which
is maximal efficient but doesn't work.
So from
1 12 5
7 5 3
9 7 2
you want to reach
7 5 3
9 7 2
1 12 5
how to do that? What have you done?
I have done it the following way:
I have looked at element [0][0], the one
in the upper left corner. (Since we have
fixed already what is the first index and
what is the second index, it should be no problem
any more to figure out, which element eg [1][2]
denotes.) [0][0] happens to be 1. I am pretty sure
that I will need this number again, thus I remember
it somewhere.
1 12 5 1
7 5 3
9 7 2
The next thing I did was to copy the 7 from [0][1]
to position [0][0]
7 12 5 1
7 5 3
9 7 2
and the 9 from [0][2] to [0][1]
7 12 5 1
9 5 3
9 7 2
and then insert the stored 1 into [0][2]
7 12 5 1
9 5 3
1 7 2
Copmaring this with the expected output, I see that
indeed this makes the first column correct.
Doing the same with the second column
store [1][0] somewhere
copy [1][1] to [1][0]
copy [1][2] to [1][1]
putting the stored value to [1][2]
7 5 5 12
9 7 3
1 12 2
Comparing with the expected output: -> looks OK
store [2][0] somewhere
copy [2][1] to [2][0]
copy [2][2] to [2][1]
putting the stored value to [2][2]
7 5 3 5
9 7 2
1 12 5
Looks OK also.
So summarazy what I have done ( x -> y denotes: x is assigned to y,
y gets the value of x)
[0][0] -> stored value
[0][1] -> [0][0]
[0][2] -> [0][1]
stored value -> [0][2]
[1][0] -> stored value
[1][1] -> [1][0]
[1][2] -> [1][1]
stored value -> [1][2]
[2][0] -> stored value
[2][1] -> [2][0]
[2][2] -> [2][1]
stored value -> [2][2]
Thus were the steps. The next task is to find some patterns
in the above. The way I have written it already makes some
pattern visible. It is 3 blocks of exactly the same things,
only that the first index is 0 in the first block, 1 in the
second and 2 in the third. Hmm. Why does it stop with 2,
why not 3 or 4 or 5. Because it denotes the array dimension
which was given from the user. The user entered 3 and thats
why the first index runs from 0 to 2.
Using what I found out, lets me simplify that above sequence.
for i = 0 .. x - 1
[i][0] -> stored value
[i][1] -> [i][0]
[i][2] -> [i][1]
stored value -> [i][2]
I just have introduced a looping construct (C or C++ syntax
is unimportant right now. I am devloping an algorithm, which
will form the backbone of my program. I don't care for syntax
right now, as long as I undoubtly can recognize what is ment).
Make you sure you see that the above is really equivalent to
the sequence of actions I have come up with earlier.
What else can be done. Looking at the assignments in the loop
there is something interesting. There also seems to be
some structure. There is an assignment to stored value
in front, then some copying actions and an assignment from
the stored value. It is the middle part that is interesting.
Doing some more examples (of course on paper), would show
that it always has the same form: There is one assignment
less then the array dimension in the seond index. The numbers
on the right side of the assignment and on the left side seem
to be somehow related: one is always 1 less then the other.
This looks like some overall structure (and remember that
x was 3)
[i][0] -> stored value
for j = 0 .. x - 2
[i][j+1] -> [i][j]
stored value -> [i][x-1]
Convince yourself, that when you set 3 for x and walk through
the loop, that indeed the loop generates the assignments we
previously had:
x x - 2 j [j+1] | [i][j+1] -> [i][j]
--------------------------+-------------------------
3 1 0 1 | [i][1] -> [i][0]
3 1 1 2 | [i][2] -> [i][1]
the loop will terminate, since j has reached x - 2
Looks like the right side of the table looks exactly like
the sequence of assignments the loop is intended to replace.
Doing a few more test (with different x) shows that this
really the case.
So what have we got up to now:
for i = 0 .. x - 1
[i][0] -> stored value
for j = 0 .. x - 2
[i][j+1] -> [i][j]
stored value -> [i][x-1]
Anthing else that looks like candidate for working on.
No, not really. Seems like this is a short recipe for
solving the problem: Given a 2 dimensional array, rotate
the rows one time upwards.
Note: Everything has been done on paper up to now. Only now
when you know what to do, in which order and why, it is time
to fire up the editor and translate the above into a programming
language.
for( int i = 0; i < x; i++ ) {
int tmp = A[i][0];
for( int j = 0; j < x - 1; j++ ) {
A[i][j] = A[i][j+1];
}
A[i][x-1] = tmp;
}
Again: assuming a value of 3 for x, make sure you see
why eg.
for( int j = 0; j < x - 1; j++ ) {
matches
for j = 0 .. x - 2
I hand over to you right now: Add the input and output part
and see if this really works. It may be a good idea to put
this into a function, since the long time goal was not to
rotate by 1 row, but to rotate by m rows. As has been
shown this can easily be achieved by: call the function m
times. Or what is equivalent
for( int Nr = 0; Nr < m; ++ nr ) {
for( int i = 0; i < x; i++ ) {
int tmp = A[i][0];
for( int j = 0; j < x - 1; j++ ) {
A[i][j] = A[i][j+1];
}
A[i][x-1] = tmp;
}
}
As said: It is not the efficienst solution, but it is a solution.
If you want something better: Back to paper and pencil and figure
out what you do, when you rotate a single column not by 1 row
but by m rows.
Yes. That's how writing a program works: Watch closely how a human
solves a problem with paper and pencil. Note each and every step.
Find patterns in what he has done. Write everything down and test
it (again: on paper and pencil). Only after you are convinced that
you know each and every step, why it is there and why it has to
be the way you wrote it down - Only then are you ready to write
a program that does the same.
-- Karl Heinz Buchegger kbuchegg@gascad.at
- Next message: Karl Heinz Buchegger: "Re: array lines shifting"
- Previous message: Karl Heinz Buchegger: "Re: array lines shifting"
- In reply to: Ronen Kfir: "Re: array lines shifting"
- Next in thread: Ronen Kfir: "Re: array lines shifting"
- Reply: Ronen Kfir: "Re: array lines shifting"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
