Computer Science Canada

ARRAYS!!- Shift Down...
Author:  Shivu [ Sat Apr 19, 2008 9:52 pm ]
Post subject:  ARRAYS!!- Shift Down...
hi! we started learning arrays about a week ago and now i'm stuck in this problem. I've been working on it for four hours now and i can't seem to figure out the logic. I've been working on it on paper, like tracing through the diagrams, but I still can't find out the answer. Here is the question:

ShiftDown.java: Write a program that asks user to input 20 integers and stores them in an array. It then shifts the content of the array down by 2 (elements at the bottom will wrap around to go to the top)
An example of shifting an array of size 5 down by 2:

45 A [0]
23 A [1]
16 A [2]
10 A [3]
12 A [4]

THIS IS WHAT THE USER
INPUTS FOR EXAMPLE


THIS IS THE OUTPUT (ONLY USING ONE ARRAY)

10 A [0]
12 A [1]
45 A [2]
23 A [3]
16 A [4]

If someone can please help me, i'll be grateful Very Happy and also, if you can EXPLAIN it to me that'd be great!

thanks!
Author:  Shivu [ Sat Apr 19, 2008 10:22 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
one thing to add on.... it should be able to work with only one array declared and no if statements and i think only 2 variables.. (this is what one i was told)- but obviously i'm not able to figure it out..
Author:  syntax_error [ Sat Apr 19, 2008 11:22 pm ]
Post subject:  RE:ARRAYS!!- Shift Down...
here a concept: use a temp variable to hold one value in then shift that value 2 down then place temp in the spot that you shifted and so forth.

Also showing some code to show what you are trying would be nice to see Wink

P.S. dont forget code tags
Author:  Shivu [ Sat Apr 19, 2008 11:33 pm ]
Post subject:  Re: RE:ARRAYS!!- Shift Down...
code:

import java.util.*;

public class ShiftDown
{
        public static void main (String [] args)
        {
        Scanner sc = new Scanner (System.in);
       
        final int MAX = 5;
        int [] num = new int [MAX];
       
        for (int i =0; i <MAX; i++) {
                System.out.print ("Enter a number:  ");
                num [i] = sc.nextInt();
        }
       
       
        int temp1=0, temp2=0, temp3=0;
       
       
        temp1 = num[MAX-1];
        temp2 = num[MAX-2];
       
       
       
        for (int i =0; i<3; i++) {
       
       
                if (i ==0) {
                        num[i] = temp2;
                } else if (i ==1) {
               
                num [i] = temp1;
                } else {
       
        temp3 = num [i];
        num[i+2]= temp3;       
        }
       
       
       
               
       
       
        }
       

       
        for (int i=0; i<MAX; i++) {
                System.out.println (num[i]);
        }
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
        }
}



my code is totally confusing... the logic is obviously wrong since i'm not able to solve it....

as a reply to your message, if you move that temp variable two steps down, then it will take the place of another value- right, so that value also has to be stroed somewhere, and also the bottom two values have to go to the top...

Wink - lol
so i think that there needs to be three thigns going on at the same time...

thanks a lot!
Author:  r691175002 [ Sat Apr 19, 2008 11:38 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
Essentially you will store the last value in one of your temporaries and then move the entire array down by one, finally appending the temporary to the front.
The use of only two variables total (Including loop indexes?) will be a bit of a pain, but can be worked around with clever use of the % operator or copy pasting.

I believe this is possible with only a single variable as a loop index if you use xor swaps.
Author:  Shivu [ Sat Apr 19, 2008 11:41 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
ok.... um what is the % operator? and won't an if statement in the loop in order for the temp value to go to the front?... and there are two values that need to go to the front...

thanks Smile
Author:  Shivu [ Sat Apr 19, 2008 11:42 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
and what are xor swaps?... sry, i'm new at all this...
Author:  Shivu [ Sat Apr 19, 2008 11:50 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
code:

import java.util.*;

public class ShiftDown
{
        public static void main (String [] args)
        {
        Scanner sc = new Scanner (System.in);
       
        final int MAX = 5;
        int [] num = new int [MAX];
       
        for (int i =0; i <MAX; i++) {
                System.out.print ("Enter a number:  ");
                num [i] = sc.nextInt();
        }
       
       
        int temp1=0, temp2=0, temp3=0;
       
       
        temp1 = num[MAX-1];
        temp2 = num[MAX-2];
       
        for (int i =0; i<3; i++) {
       
                if (i ==0) {
                        num[i] = temp2;
                } else if (i ==1) {
               
                num [i] = temp1;
                } else {
       
        temp3 = num [i];
        num[i+2]= temp3;       
        }
        }
       
        for (int i=0; i<MAX; i++) {
                System.out.println (num[i]);
        }
}
}


This code here works... i think... but it uses 3 temp variables and i have a feeling that this is not the right way to do it...

so i really need some help for this!!

Thanks a lot!! Smile
Author:  r691175002 [ Sun Apr 20, 2008 12:01 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
Well the first hint I can give you is to forget about moving the array down twice in a single go. Shifting the entire array down two spots is the same as shifting it down one spot twice.
Shifting it down only one spot is much easier.

The % (modulo) operator essentially wraps a number around to within a bound. You can also think of it as the remainder of a division. Try:
code:

System.out.println (
for (int i = 0; i < 10; i++)
    System.out.println ("I: " + i + " Mod: " + i%3);

System.out.println ("\nLoop Twice:");
int arrayLength = 3;
for (int i = 0; i < arrayLength*2; i++)
    System.out.println (i%arrayLength);

I will say right now, don't use the modulo if you dont feel comfortable. The same thing can be accomplished by copy pasting the same code twice.



The next issue comes down to limiting your temporary variables. I suggest making a list of each step and the swap required to perform it, try to find a pattern.

Here is one way to do it, there may be easier ones:
code:

/*
1 2 3 4 5
5 2 3 4 1 First and last
4 2 3 5 1 First and second last
3 2 4 5 1 First and third last
2 3 4 5 1 First and fourth last
*/

Paste somewhere in your code and try to implement it.
Author:  syntax_error [ Sun Apr 20, 2008 12:05 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
Shivu wrote:

ok.... um what is the % operator? and won't an if statement in the loop in order for the temp value to go to the front?... and there are two values that need to go to the front...

thanks )


the % is mod

Shivu wrote:

and what are xor swaps?... sry, i'm new at all this...


xor is a bitwise operation, I think, for now I would suggest to do it with those and do it with the temp var; after when you get time look it up on wiki or i think there is even a tut on it here.
Author:  r691175002 [ Sun Apr 20, 2008 12:08 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
Just a question, did you make up the example in the question yourself? The elements have been moved down three indexes, not two.
The one issue with an xor swap is that it fails on numbers of the same value so you will need an if (Or a ternary to get around the restriction). Or you could probably find a way to exploit the standard library to knock down the variable count some more.
Author:  Shivu [ Sun Apr 20, 2008 12:13 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
r691175002 @ Sun Apr 20, 2008 12:08 am wrote:
Just a question, did you make up the example in the question yourself? The elements have been moved down three indexes, not two.
The one issue with an xor swap is that it fails on numbers of the same value so you will need an if (Or a ternary to get around the restriction). Or you could probably find a way to exploit the standard library to knock down the variable count some more.


thanks for the previous help- but if you could explain the code you wrote, that'd be great, because i didn't really understand what it does...

and about the example, i didn't make it up, and the elements go down only two indexes... (check again)

and what do you mean by exploiting the library to knock down the variable count?

so if you could explain that code, that'd be grat Smile
thanks a lot!
Author:  r691175002 [ Sun Apr 20, 2008 12:17 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
Ah yes, you are correct, I misunderstood.

Assuming that you want to start with an array such as:
code:
1 2 3 4 5

And end with something like:
code:
5 1 2 3 4

You need to perform a series of swaps that hopefully follow a pattern.
Heres what I came up with:
code:
1 2 3 4 5
5 2 3 4 1 Swap the first and last
5 1 3 4 2 Swap the second and last
5 1 2 4 3 Swap the third and last
5 1 2 3 4 Swap the fourth and last.

As you can see, this follows a clear pattern that should be easy to implement with a loop.

I would suggest starting to solve this problem by creating code that outputs the correct indexes to swap, for example:
code:
Output:
0 4
1 4
2 4
3 4


From there, if you perform the actual swaps, you should have a working algorithm to shift the array down once.
Copy and paste and you are done.


My code just does a quick run through of what the % operator does, but it isn't necessary to solve this question so its not a big deal.
Author:  Shivu [ Sun Apr 20, 2008 12:38 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
wow!! how did you come up with that pattern?

so here's what i did so far... but i used two loops...

code:

import java.util.*;
public class ShiftDown
{
        public static void main (String [] args)
        {
        Scanner sc = new Scanner (System.in);
       
        final int MAX = 20;
        int [] num = new int [MAX];
       
        for (int i =0; i <MAX; i++) {
                System.out.print ("Enter a number:  ");
                num [i] = sc.nextInt();
        }
       
        int temp1=0, temp2=0;

for  (int count =0; count <2; count++) {
        for (int i=0; i<MAX; i++) {
       
        temp1 = num [i];
       
        temp2 = num [MAX-1];
       
        num[i]=temp2;
        num[MAX-1] = temp1;

        }
}              
        for (int i=0; i<MAX; i++) {
                System.out.println (num[i]);
                }
        }
}


i don't think i can use only one loop, because it has to repeat the procedure two times right?... so...


thanks a lot for your help!! Very Happy
i really appreciate it!!!!
Author:  Shivu [ Sun Apr 20, 2008 12:39 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
or can i use only one loop :S
Author:  Shivu [ Sun Apr 20, 2008 12:41 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
yup, i'll just copy and paste then!

thanks a lot again! Smile
Author:  r691175002 [ Sun Apr 20, 2008 2:14 am ]
Post subject:  Re: ARRAYS!!- Shift Down...
Ah, sorry I came back a little late.

The easiest solution is just to copy and paste the loop like you have done (Make sure you reuse the counter variable though if you think the teacher will count each one separately). If you absolutely have to use a single loop thats where the % operator comes into play:
code:
for (int i = 0; i < LOOP_TIMES*2; i++)
    System.out.println (i % LOOP_TIMES);
    // % Will wrap i around so that it is always within LOOP_TIMES
    // 0 % 3 = 0
    // 1 % 3 = 1
    // 2 % 3 = 2
    // 3 % 3 = 0 // Wrapped around
    // 4 % 3 = 1
    // 5 % 3 = 2
    // 6 % 3 = 0 // Wrapped around again
    // 7 % 3 = 1 ...

This will output 0 to LOOP_TIMES-1 twice.

Your code:
code:
for (int i=0; i<MAX; i++) {
    temp1 = num [i];
   
    temp2 = num [MAX-1];
   
    num[i]=temp2;
    num[MAX-1] = temp1;
}

Becomes:
code:
for (int i=0; i<(MAX*2); i++) {
    temp1 = num [i%MAX];
   
    temp2 = num [MAX%MAX-1];
   
    num[i%MAX]=temp2;
    num[MAX%MAX-1] = temp1;
}

(Untested, it may have a few off by one errors)

Picking up patterns like this is something that comes with time. I basically played around a bit and finally ended up with something that looked like it would work.
Author:  Shivu [ Sun Apr 20, 2008 2:45 pm ]
Post subject:  RE:ARRAYS!!- Shift Down...
hi! thanks for that....

but for the % operator, i'm a bit confused on what it does... meaning:

what does it mean to "wrap" i around?, does it reset i?

thanks
Author:  jernst [ Sun Apr 20, 2008 3:15 pm ]
Post subject:  Re: RE:ARRAYS!!- Shift Down...
Shivu @ Sun Apr 20, 2008 2:45 pm wrote:
hi! thanks for that....

but for the % operator, i'm a bit confused on what it does... meaning:

what does it mean to "wrap" i around?, does it reset i?

thanks


Like the people above have said it gives a remainder from a divison. So it "wraps around" everytime the remainder returns to 0. For your example with 5 elements:

5 % 5 = 0
10 % 5 = 0
15 % 5 = 0

Similarly,
6 % 5 = 1
11 % 5 = 1 ..etc

So instead of trying to figure out when a counter should return back to zero to wrap the array back to the start you can use the modulo (%) to turn the 5 into a 0. I dont know if that made it any more clear or worse but I gave it a try Razz
Author:  Shivu [ Sun Apr 20, 2008 3:40 pm ]
Post subject:  RE:ARRAYS!!- Shift Down...
no no that was great! Smile

ok... so, regarding the code above (before the above post),

num [i%MAX]; the i%MAX makes sure that i stays less than MAX (which is 5 for example) ??

so like:

code:

 for (int i=0; i<MAX*2; i++) {

temp1 = num[i%MAX];

//the index # (of num) will be 0, then it'll be 1, then 2, then 3, then 4, then 5, and then again 0,1,2,3,4,5 =>that'll be when i will be less than MAX *2 (in this case 10).  so the loop will be run two times!?

}




cuz if the condition would be i <MAX, then the loop would only run till i = 4...

oh!! i get it:) (or i think i get it...)

if someone could let me know if i'm understanding it properly, that'd be great! -lol

thanks a lot to everyone!!!!
Author:  jernst [ Sun Apr 20, 2008 3:43 pm ]
Post subject:  Re: ARRAYS!!- Shift Down...
Looks like you've got it Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy