help me with this prog problem

[z0mb13]

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut);

Find the result of shuffles(1002,101)

any hints of the algorithm???

 

[z0mb13]

should this be posted in highly techincal instead??

 

[Mrfrog840]

/me sucks at math

 

[z0mb13]

no one?

 

[notfred]

Originally posted by: z0mb13

static long shuffles(int nCards,int iCut);

Find the result of shuffles(1002,101)

any hints of the algorithm???

take the input deck, split it into two arrays.
one deck of height (nCards-iCut), and one of height iCut.

Find the shorter stack.

if(nCards-iCut > iCut){
taller = nCards is the taller stack;
}
else{
taller = iCut is the taller stack
}

Take the taller stack, and subtract iCut*2

int tallHeigt = height(taller - height(iCut)*2);

make a final array:

deck final;

copy the top cards into the final deck
for(int i = 0; i < tallHeight<i++){
final = taller
}

copy from both arrays until you run out.
for(int i = 0; i < iCut*2;i+=2){
final = taller;
final[i+1] = shorter;
}

There, you're done.

Yes, it's in some type of pseudocode, and it leaves out things, but the logic of thye program is all there.

 

[z0mb13]

but the problem is finding the number of perfect shuffles required to return the deck to its original order, notfred's solution just does the shuffling (if I am not mistaken)

 

[TuxDave]

I don't see how there can be a concrete answer for this question as the deck isn't guaranteed to be cut exactly in half. Some ways can restore the deck in nCards moves....

 

[Cenalian]

I think he just means assume there is a machine cutting and shuffiling (for arguments sake)

I know for a standard deck its 13 shuffles (I used to be able to do it), but not sure of a formula, I'll try to think of one though.

 

[lukatmyshu]

Since it asks for the number of "perfect" shuffles before you have the array in it's original order ... why don't you just keep doing the same algorithm over and over again until the array is in it's original order. Keep a counter, increment it every iteration and as soon as it is the same you have your answer.

 

[z0mb13]

Originally posted by: lukatmyshu
Since it asks for the number of "perfect" shuffles before you have the array in it's original order ... why don't you just keep doing the same algorithm over and over again until the array is in it's original order. Keep a counter, increment it every iteration and as soon as it is the same you have your answer.

yep I can do that, but there must be some more elegant way to solve this problem