In computer games and also in simulations of card-playing scenarios, we sometime

Question

In computer games and also in simulations of card-playing scenarios, we sometimes need to use a computer to simulate the way that person wou shuffle a deck of cards. Given two decks of n cards each, the riffle shuffle algorithm involves repeatedly choosing one of the two decks at random and then removing the bottom card from that deck and placing that card on the top of an output deck. This card-choosing step is repeated until all the original cards are placed in the output deck. Define a recursive-riffle algorithm, which cuts a deck of n cards into two decks of n/2 each, where n is a power of 2, and then calls the recursive-riffle algorithm on each half. When these recursive calls return, the recursive-riffle algorithm on each half. When these recursive calls return, the recurisve-riffle algorithm then performs a riffle shuffle of the two decks to produce the shuffled result. Show that every card in the original deck has an equal probability of being the top card after a recursive-riffle is performed on the deck, and analyze the running time of the recurisve-riffle algorithm using a recurrence equation.

Explanation / Answer

/** * An object of type Deck represents a deck of playing cards. The deck * is a regular poker deck that contains 52 regular cards and that can * also optionally include two Jokers. */ public class Deck { /** * An array of 52 or 54 cards. A 54-card deck contains two Jokers, * in addition to the 52 cards of a regular poker deck. */ private Card[] deck; /** * Keeps track of the number of cards that have been dealt from * the deck so far. */ private int cardsUsed; /** * Constructs a regular 52-card poker deck. Initially, the cards * are in a sorted order. The shuffle() method can be called to * randomize the order. (Note that "new Deck()" is equivalent * to "new Deck(false)".) */ public Deck() { this(false); // Just call the other constructor in this class. } /** * Constructs a poker deck of playing cards, The deck contains * the usual 52 cards and can optionally contain two Jokers * in addition, for a total of 54 cards. Initially the cards * are in a sorted order. The shuffle() method can be called to * randomize the order. * @param includeJokers if true, two Jokers are included in the deck; if false, * there are no Jokers in the deck. */ public Deck(boolean includeJokers) { if (includeJokers) deck = new Card[54]; else deck = new Card[52]; int cardCt = 0; // How many cards have been created so far. for ( int suit = 0; suit

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.