suitIO] euit[l] suit[2] sult[3]

Рис. 5.22. Графическое представление массива suit

5.10. Учебный пример: моделирование тасования

и раздачи карт

в этом разделе мы используем генерацию случайных чисел для разработки программы моделирования тасования и раздачи карт. Эта программа может затем быть использована для разработки программ, которые играют в различные карточные игры. Чтобы показать некоторые тонкости проблем эффективности, мы умышленно использовали неоптимальные алгоритмы тасования и раздачи. В упражнениях и далее в тексте мы разовьем более эффективные алгоритмы.

Используя нисходящ;ую разработку с пошаговой детализацией, мы создадим программу, которая будет тасовать колоду из 52 игральных карт и затем раздавать их. Нисходящий подход особенно полезен при решении больших задач, более сложных, чем рассмотренные в предыдущих главах.

Для представления колоды игральных карт мы используем двумерный массив deck размером 4 на 13 (рис. 5.23). Строки соответствуют мастям - строка О соответствует червям, строка 1 - бубнам, строка 2 - трефам и строка 3 - пикам. Столбцы соответствуют значениям лицевых сторон (фигурам) карт - столбцы от О до 9 соответствуют фигурам от туза до десятки соответственно, а столбцы от 10 до 12 соответствуют валету, даме и королю. Мы загрузим в массив строк suit строки символов, представляющие четыре масти, а в массив строк face символьные строки, представляющие тринадцать значений фигур.

а. а

deck [2] [12] представляет короля треф Трефы \ Король

Рис. 5.23. Представление колоды карт двумерным массивом

Эта смоделированная колода карт может тасоваться следующим образом. Сначала массив deck обнуляется. Затем строка row 0-3 и столбец column 0-12 выбираются как случайные числа. В элемент массива deck[row][column] вставляется число 1, которое указывает, что эта карта будет сдана из тасуемой колоды первой. Этот процесс продолжается с числами 2, 3, 52, которые вставляются в массив deck и показывают, какие карты займут второе, третье,

пятьдесят второе место в тасуемой колоде. Во время заполнения массива deck номерами карт, может оказаться, что одна и та же карта должна попасть в него дважды, т.е. после случайного выбора карты deck[row][column] окажется ненулевым. Такой выбор просто игнорируется и повторно случайно выбираются другие строки и столбцы до тех пор, пока не будет найдена не выбиравшаяся ранее карта. В конечном счете числа с 1 по 52 займут 52 позиции массива deck. В этот момент колода карт полностью перетасована.

Этот алгоритм тасования может выполняться неопределенно долго, если карты, которые уже растасованы, случайно выбираются повторно. Это явление известно как неопределенная отсрочка. В упражнениях обсуждается лучшая тасующий алгоритм, который исключает возможность неопределенной отсрочки.

Совет по повышению эффективности 5.2

Иногда в алгоритме, который кажется естественным , могут таиться такие тонкие проблемы эффективности, как неопределенная отсрочка. Ищите алгоритмы, которые лишены проблемы неопределенной отсрочки.

Чтобы сдать первую карту, мы отыскиваем в массиве deck[row][col-umn] = 1. Это соответствует вложенной структуре for, которая варьирует row от о до 3 и column от О до 12. Какая карта соответствует этой позиции массива? В массив suit предварительно были загружены четыре масти, так что для получения масти мы печатаем символьную строку suit[row]. Аналогично, чтобы получить значение фигуры на карте, мы печатаем символьную строку face[column]. Мы печатаем также символьную строку масти . Печать этой информации в нужной последовательности дает нам возможность напечатать каждую карту в виде король масти трефы , туз масти бубны и т.д.

Приступим к процессу нисходящей пошаговой детализации. Вершина очевидна:

Тасовать и раздать 52 карты Наша первая детализация дает:

Задать начальные условия массиву suit (масть) Задать начальные условия массиву face (фигура) Задать начальные условия массиву deck (колода) Тасовать колоду Раздать 52 карты

Предложение Тасовать колоду может быть расширено следующим образом:

Цикл для каждой из 52 карт

Поместить номер карты в случайно выбранную незанятую позицию колоды

Предложение Раздать 52 карты может быть расширено следующим образом:

Цикл для каждой из 52 карт

Найти номер карты в массиве deck и напечатать фигуру и масть карты

Объединение этих расширений дает нам полную вторую детализацию:

Задать начальные условия массиву suit (масть) Задать начальные условия массиву face (фигура) Задать начальные условия массиву deck (колода)

ЦИКЛ для каждой из 52 карт

Поместить номер карты в случайно выбранную незанятую

позицию колоды ЦИКЛ для каждой из 52 карт

Найти номер карты в массиве deck и напечатать фигуру

и масть карты

Предложение Поместить номер карты в случайно выбранную незанятую позицию колоды может быть развернуто следующим образом:

Выбрать случайным образом позицию в колоде

ПОКА выбранная позиция в колоде оказывается уже выбранной

раньше

Выбрать случайным образом позицию в колоде Поместить номер карты в выбранную позицию колоды

Предложение Найти номер карты в массиве deck и напечатать фигуру и масть карты может быть развернуто следующим образом:

ЦИКЛ для каждой позиции массива deck

ЕСЛИ значение позиции равно номеру карты Напечатать фигуру и масть карты

Объединение этих расширений дает нам третью детализацию:

Задать начальные условия массиву suit (масть) Задать начальные условия массиву face (фигура) Задать начальные условия массиву deck (колода)

ЦИКЛ для каждой из 52 карт

Выбрать случайным образом позицию в колоде ПОКА выбранная позиция в колоде оказывается уже выбранной раньше

Выбрать случайным образом позицию в колоде Поместить номер карты в выбранную позицию колоды

ЦИКЛ для каждой из 52 карт

ЦИКЛ для каждой позиции массива deck

ЕСЛИ значение позиции равно номеру карты Напечатать фигуру и масть карты

Этим процесс детализаций завершается. Заметим, что программа станет более эффективной, если части алгоритма тасование и раздача скомбинировать так, чтобы каждая карта сдавалась, как только она помещается в