# C++ exercise

Discussion in 'Programmer's Corner' started by Eric007, Oct 3, 2013.

1. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
Hi All,

Trying to do this little C++ exercise attached.

For question:

a) my answer is p = {2,0,1}. Is it correct? I'm currently revising it. Let me know if you find otherwise.

As for the remaining questions, will try to post my answers as soon as I can but if anyone wants to post fine!

File size:
136 KB
Views:
63
2. ### joeyd999 AAC Fanatic!

Jun 6, 2011
4,035
5,709
Looks like C to me...

3. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
is "int []a" valid syntax in C++?

I'm used to either "int *a" or "int a[]".

4. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
Me too. Have never really found the *big* difference between the two actually.

So am I correct?

initially p [] = {0,1,2} with the first 'for' used to initialize it.
line6: i = 1,2

when i = 1:
line8: k=1, j=1 then while in line 9 is false! so it jumps to line14 and p[1] = 1.

then jumping back to line6 for the 2nd iteration of the for loop:
k=2, j=2.

line9 while ((2>0) && (2>-4)) is true
p[2] = p[1] = 1 and j=1.

back to line 9 while ((1>0) && (-1>-4)) is true
p[1] = p[0] = 0 and j = 0.

back to line 9 ((0>0) && ( a[p[-1]]>-4)) is false as p[-1] does not exist so we jump to line14 and p[0] = 2

=> p = {2, 0, 1}. That's how I came up with this answer.

what do you think!?

Edit: and what can you say about the other part of the question a " In general, what does the function Do it do." ?

Last edited: Oct 3, 2013
5. ### joeyd999 AAC Fanatic!

Jun 6, 2011
4,035
5,709
Pretty sure it's a syntax error.

6. ### joeyd999 AAC Fanatic!

Jun 6, 2011
4,035
5,709
The difference is pretty much the Object Oriented extensions, none of which are shown in your example.

It seems like you are taking C++ without the need of a C prerequisite? That seems odd to me.

Eric007 likes this.
7. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
I did 'VB.6' first then 'C' then 'C++' at school. I can write code using these languages BUT I am not an expert or very competent with these languages. And I can master these languages if I want to and will later on BUT I am too busy with embedded programing for now!

Oh and I know a little of VB.Net

This exercise is from Software engineering course!

8. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
Here's my answer for question b attached!
The numbers are from the lines of codes as they are.

Any comment!?

File size:
142.1 KB
Views:
24
9. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
There are some telltales that give a hint as to what it is doing, but do what it says and draw a flow chart for the function. That will make the telltales stand out a bit and let you view the function from a slightly higher, more abstract viewpoint which generally lets you see the higher, more abstract functionality a bit more easily.

Eric007 likes this.
10. ### joeyd999 AAC Fanatic!

Jun 6, 2011
4,035
5,709
Confirmed with gcc -- not valid syntax. Some class!

Eric, rather than asking us if your answer is right or wrong, why not compile it and check for yourself?

panic mode and Eric007 like this.
11. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
This is not a flowchart. In particular, you have one state with two possible paths leaving it and no indication of when you take each path.

A chart with just a bunch of line numbers that you have to go back and reference specific lines to see what is going on forces you to work at too low a level of detail. Draw your flowchart so that it is stand alone so that you can view the entire algorithm at once.

12. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
That's correct! Yes I can compile it with Visual Studio...and can fix the syntax errors if any but not sure how to see the content of p though!

Will give it a shot...trying to answer the other theoretical questions, if I can. If I cannot I drop/leave it...

Thanks!

13. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
What I drew is the 'control flow graph' actually as required.
Well...

14. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
So a "control flow graph" doesn't have to give any indication of what determines which of two branches you take when you leave a node?

And a "control flow graph" doesn't need to every terminate, despite the fact that the code it is for clearly does?

15. ### THE_RB AAC Fanatic!

Feb 11, 2008
5,430
1,311
I would give the examiner a score of zero, for completely failing to comment, and for having typos that won't compile (and were obviously never tested). What a clown.

panic mode and Eric007 like this.
16. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
Since part of the problem is figuring out what the code does, it is not unreasonable for it to be uncommented. Having typos is less forgivable, but may well have a reasonable explanation if we knew the circumstances.

17. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
The first step is to rewrite the code so that it is reasonably formatted

Code ( (Unknown Language)):
1.
2. void Do_it(int *a, int *p, int N)
3. {
4.    int i, j, k;
5.
6.    for (i = 0; i < N; i++)
7.       p[i] = i;
8.
9.    for (i = 1; i < N; i++)
10.    {
11.       k = p[i];
12.       j = i;
13.       while ( (j>0) && (a[p[j-1]] > a[k]) )
14.       {
15.          p[j] = p[j-1];
16.          j--;
17.       }
18.       p[j] = k;
19.    }
20. }
21. [/i][/i]

Now, I haven't tried to compile or run this; as a result I might miss something in what I do next.

Looking at the code the second loop can be simplified quite a bit.

First, notice that within the for() loop, the value of i is never changed and the value of k is never changed after it is initialized.

Furthermore, the value of k is set equal to p at the start of the loop and that after that point the only elements of the p[] array that get changed are at p[j]. Then note that j starts out at i and only goes down from there. Thus, no value in the p[] array at an index greater than i is changed during any pass of the loop. As a consequence, in each pass of the loop when k is set equal to p, the value in p is the value it had before the for() loop started, which the prior for() loop set equal to i. Since k is set equal to i and then never changed, and since i never changes, we can simply use i and get rid of k completely. As a result, We can thus simplify the code as follows:

Code ( (Unknown Language)):
1.
2. void Do_it(int *a, int *p, int N)
3. {
4.    int i, j, k;
5.
6.    for (i = 0; i < N; i++)
7.       p[i] = i;
8.
9.    for (i = 1; i < N; i++)
10.    {
11.       j = i;
12.       while ( (j>0) && (a[p[j-1]] > a[i]) )
13.       {
14.          p[j] = p[j-1];
15.          j--;
16.       }
17.       p[j] = i;
18.    }
19. }
20. [/i][/i]

The next thing to note is that the inner while loop is nothing but a classic for() loop. So we can write the code as:

Code ( (Unknown Language)):
1.
2. void Do_it(int *a, int *p, int N)
3. {
4.    int i, j, k;
5.
6.    for (i = 0; i < N; i++)
7.       p[i] = i;
8.
9.    for (i = 1; i < N; i++)
10.    {
11.       while (j = i; (j>0) && (a[p[j-1]] > a[i]); j-- )
12.          p[j] = p[j-1];
13.       p[j] = i;
14.    }
15. }
16. [/i][/i]

The next thing to note is that the contents of the a[] array are never changed.

What role does the p[] array play?

The keys to this are that it is initialized to values from 0 through N-1 and that it is used in the expression a[p[j-1]]. This means that the values stored in the p[] array are being used as indices into the a[] array. This is consistent with the values that the p[] array is initialized to, namely the index values for an N-element array.

Is that enough to let you see what is happening and what the code is doing?

panic mode and Eric007 like this.
18. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
I've always considered that guy as a *clown* anyway...

19. ### Eric007 Thread Starter Senior Member

Aug 5, 2011
1,147
39
Looks like I was right...

Compiler found same answer p = {2, 0, 1}

File size:
190.8 KB
Views:
9
20. ### WBahn Moderator

Mar 31, 2012
23,587
7,216
I missed this post, so sorry for the late reply.

Did you figure out what the algorithm is doing, in general?

For instance, if you start with N=9 and the a1[] array being {-16, 7 , 3, 5, -2, 19, 13, 27, 1}, can you write down, by inspection, what the p[] array will contain?