8.11. Case Study: Card Shuffling and
Dealing Simulation
This section uses random-number
generation to develop a card shuffling and dealing simulation program. This
program can then be used as a basis for implementing programs that play specific
card games. To reveal some subtle performance problems, we have intentionally
used suboptimal shuffling and dealing algorithms.
Using the top-down, stepwise-refinement
approach, we develop a program that will shuffle a deck of 52 playing cards and
then deal each of the 52 cards. The top-down approach is particularly useful in
attacking larger, more complex problems than we have seen in the early
chapters.
We use a 4-by-13 two-dimensional array
deck to represent the deck of playing cards (Fig. 8.23). The rows correspond to the suits—row 0 corresponds to
hearts, row 1 to diamonds, row 2 to clubs and row 3 to spades. The columns
correspond to the face values of the cards—columns 0 through 9 correspond to the
faces ace through 10, respectively, and columns 10 through 12 correspond to the
jack, queen and king, respectively. We shall load the string array suit with
character strings representing the four suits (as in Fig.
8.22) and the string array face with character strings representing
the 13 face values.
This simulated deck of cards may be shuffled as follows. First
the 52-element array deck is initialized to zeros. Then, a row
(0–3) and a column (0–12) are each chosen at
random. The number 1 is inserted in array element deck[ row ][ column
] to indicate that this card is going to be the first
one dealt from the shuffled deck. This process continues with the numbers 2, 3,
..., 52 being randomly inserted in the deck array
to indicate which cards are to be placed second, third, ..., and 52nd in the
shuffled deck. As the deck array begins to fill with card numbers, it is possible
that a card will be selected twice (i.e., deck[ row ][ column ] will be nonzero when it is selected). This selection is
simply ignored, and other row and column combinations are repeatedly chosen at random until
an unselected card is found. Eventually, the numbers 1 through 52 will occupy
the 52 slots of the deck array. At this point,
the deck of cards is fully shuffled.
This shuffling algorithm could execute
for an indefinitely long period if cards that have already been shuffled are
repeatedly selected at random. This phenomenon is known as indefinite postponement (also called starvation).
Performance Tip 8.3
|
Sometimes
algorithms that emerge in a "natural" way can contain subtle performance
problems such as indefinite postponement. Seek algorithms that avoid indefinite
postponement. |
To deal the first card, we search the
array for the element deck[ row ][ column ] that matches 1.
This is accomplished with nested for statements that vary row
from 0 to 3 and column from 0 to 12. What
card does that slot of the array correspond to? The suit array has been preloaded with the four suits, so to get
the suit, we print the character string suit[ row ]. Similarly, to get the face value of the card, we print
the character string face[ column ]. We
also print the character string "of".
Printing this information in the proper order enables us to print each card in
the form "King of Clubs", "Ace of Diamonds" and so on.
Figures
8.24–8.26 contain the card shuffling and dealing program and a
sample execution. Note the output formatting used in function deal
(lines 81–83 of Fig.
8.25). The output statement outputs the face right
justified in a field of five characters and outputs the suit left justified in a
field of eight characters (Fig. 8.26). The output is printed in two-column format—if the
card being output is in the first column, a tab is output after the card to move
to the second column (line 83); otherwise, a newline is output.
Fig. 8.24. DeckOfCards header
file.
1 // Fig. 8.24: DeckOfCards.h
2 // Definition of class DeckOfCards that
3 // represents a deck of playing cards.
4
5 // DeckOfCards class definition
6 class DeckOfCards
7 {
8 public:
9 DeckOfCards(); // constructor initializes deck
10 void shuffle(); // shuffles cards in deck
11 void deal(); // deals cards in deck
12 private:
13 int deck[ 4 ][ 13 ]; // represents deck of cards
14 }; // end class DeckOfCards
|
Fig. 8.25. Definitions of
member functions for shuffling and dealing.
1 // Fig. 8.25: DeckOfCards.cpp
2 // Member-function definitions for class DeckOfCards that simulates
3 // the shuffling and dealing of a deck of playing cards.
4 #include <iostream>
5 using std::cout;
6 using std::left;
7 using std::right;
8
9 #include <iomanip>
10 using std::setw;
11
12 #include <cstdlib> // prototypes for rand and srand
13 using std::rand;
14 using std::srand;
15
16 #include <ctime> // prototype for time
17 using std::time;
18
19 #include "DeckOfCards.h" // DeckOfCards class definition
20
21 // DeckOfCards default constructor initializes deck
22 DeckOfCards::DeckOfCards()
23 {
24 // loop through rows of deck
25 for ( int row = 0; row <= 3; row++ )
26 {
27 // loop through columns of deck for current row
28 for ( int column = 0; column <= 12; column++ )
29 {
30 deck[ row ][ column ] = 0; // initialize slot of deck to 0
31 } // end inner for
32 } // end outer for
33
34 srand( time( 0 ) ); // seed random number generator
35 } // end DeckOfCards default constructor
36
37 // shuffle cards in deck
38 void DeckOfCards::shuffle()
39 {
40 int row; // represents suit value of card
41 int column; // represents face value of card
42
43 // for each of the 52 cards, choose a slot of the deck randomly
44 for ( int card = 1; card <= 52; card++ )
45 {
46 do // choose a new random location until unoccupied slot is found
47 {
48 row = rand() % 4; // randomly select the row (0 to 3)
49 column = rand() % 13; // randomly select the column (0 to 12)
50 } while( deck[ row ][ column ] != 0 ); // end do...while
51
52 // place card number in chosen slot of deck
53 deck[ row ][ column ] = card;
54 } // end for
55 } // end function shuffle
56
57 // deal cards in deck
58 void DeckOfCards::deal()
59 {
60 // initialize suit array
61 static const char *suit[ 4 ] =
62 { "Hearts", "Diamonds", "Clubs", "Spades" };
63
64 // initialize face array
65 static const char *face[ 13 ] =
66 { "Ace", "Deuce", "Three", "Four", "Five", "Six", "Seven",
67 "Eight", "Nine", "Ten", "Jack", "Queen", "King" };
68
69 // for each of the 52 cards
70 for ( int card = 1; card <= 52; card++ )
71 {
72 // loop through rows of deck
73 for ( int row = 0; row <= 3; row++ )
74 {
75 // loop through columns of deck for current row
76 for ( int column = 0; column <= 12; column++ )
77 {
78 // if slot contains current card, display card
79 if ( deck[ row ][ column ] == card )
80 {
81 cout << setw( 5 ) << right << face[ column ]
82 << " of " << setw( 8 ) << left << suit[ row ]
83 << ( card % 2 == 0 ? '\n' : '\t' );
84 } // end if
85 } // end innermost for
86 } // end inner for
87 } // end outer for
88 } // end function deal
|
Fig. 8.26. Card shuffling and dealing
program.
1 // Fig. 8.26: fig08_26.cpp
2 // Card shuffling and dealing program.
3 #include "DeckOfCards.h" // DeckOfCards class definition
4
5 int main()
6 {
7 DeckOfCards deckOfCards; // create DeckOfCards object
8
9 deckOfCards.shuffle(); // shuffle the cards in the deck
10 deckOfCards.deal(); // deal the cards in the deck
11 return 0; // indicates successful termination
12 } // end main
|
Nine of Spades Seven of Clubs
Five of Spades Eight of Clubs
Queen of Diamonds Three of Hearts
Jack of Spades Five of Diamonds
Jack of Diamonds Three of Diamonds
Three of Clubs Six of Clubs
Ten of Clubs Nine of Diamonds
Ace of Hearts Queen of Hearts
Seven of Spades Deuce of Spades
Six of Hearts Deuce of Clubs
Ace of Clubs Deuce of Diamonds
Nine of Hearts Seven of Diamonds
Six of Spades Eight of Diamonds
Ten of Spades King of Hearts
Four of Clubs Ace of Spades
Ten of Hearts Four of Spades
Eight of Hearts Eight of Spades
Jack of Hearts Ten of Diamonds
Four of Diamonds King of Diamonds
Seven of Hearts King of Spades
Queen of Spades Four of Hearts
Nine of Clubs Six of Diamonds
Deuce of Hearts Jack of Clubs
King of Clubs Three of Spades
Queen of Clubs Five of Clubs
Five of Hearts Ace of Diamonds
|
There is a weakness in the dealing
algorithm. Once a match is found, even if it is found on the first try, the two
inner for statements continue
searching the remaining elements of deck for a match.
No comments:
Post a Comment