В данной статье я бы хотел показать один из вариантов алгоритма, выполняющего перетасовку колоды игральных карт, и, безусловно, обсудить его достоинства и недостатки.
Если вы захотите написать программу для игры в карты, то неизбежно столкнетесь с необходимостью перетасовки колоды карт. Обычно, эта операция выполняется перед каждой сдачей карт, то есть, возможно, десятки раз за игру (в зависимости от правил конкретной игры). Поэтому качество выполнения данной операции может существенно сказаться на результатах игры.
На первый взгляд, в решении этой задачи нет ничего сложного. Нужно просто поменять местами карты в колоде так, чтобы они располагались случайным образом. Но что означает «случайным образом»? Ответ простой: «Во взаимном расположении карт не должно быть никаких закономерностей». Но ведь компьютер выполняет только то, что написано в программе. Команды из серии: «Возьми то, не знаю что», тут не проходят. Поэтому в первую очередь нам нужен источник случайных чисел.
И вот тут возникает проблема. На сегодняшний день не существует источника по-настоящему случайных чисел. Но зато есть огромное количество алгоритмов, которые позволяют получать, так называемые, псевдослучайные числа. Практически каждый язык программирования имеет встроенные функции для генерирования псевдослучайных последовательностей чисел. Разница между случайными и псевдослучайными числами в том, что последние получены с использованием какого-то алгоритма. А это означает наличие некоторой закономерности в появлении таких чисел.
Я не буду анализировать особенности этих алгоритмов, это тема не статьи, а книги (скорее нескольких). Те, кому интересно, могут посмотреть литературу по вычислительной математике или теории чисел.
В этой статье я расскажу о возможностях, которые нам предоставляет стандартная библиотека языка Java. Есть два варианта. Первый – использовать метод random() класса java.lang.Math.. Второй – воспользоваться одним из методов класса java.util.Random.
Мы будем использовать второй вариант, т.к. он обеспечивает более широкую функциональность.
В первую очередь, я хочу показать, что этот класс генерирует псевдослучайные числа. Напишем простенькую программку:
import java.util.Random;public class Main {
public Main() {
}
public static void main(String[] args) {
//создаем новый генератор псевдослучайных чисел, и задаем
//начальное значение для алгоритма генерации чисел
Random generator = new Random(20);
//выводим десять случайных чисел
for(int i = 0; i < 10; i++) {
if(i == 9) {
System.out.println(generator.nextInt(100));
}
else {
System.out.print(generator.nextInt(100) + "; ");
}
}
}
}
Тут все предельно просто. Программа генерирует 10 случайных чисел, и выводит их в одну строку. Если мы запустим программу 3 раза подряд, то получим три строки с числами:
53; 36; 1; 61; 5; 95; 33; 55; 93; 88
53; 36; 1; 61; 5; 95; 33; 55; 93; 88
53; 36; 1; 61; 5; 95; 33; 55; 93; 88
Как видите, все строки одинаковые. Это происходит из-за того, что аргументом в конструкторе класса Random у нас является одно и то же число (20). Кстати, если использовать конструктор без аргументов, то начальное значение будет выбрано по специальному алгоритму, и генерируемые числа будут разными.
Но я не зря использовал именно этот конструктор. Дело в том, что в качестве начального значения для генератора случайных чисел можно использовать текущее значение системного времени. Действительно, нельзя точно предугадать в какой момент времени пользователь запустит программу, миллисекундой раньше, миллисекундой позже…
Создать генератор случайных чисел, с системным временем в качестве базового числа, можно так:
Random generator = new Random(new Date().getTime());
Или, если у вас уже есть объект типа Random:
generator.setSeed(new Date().getTime());
Итак, с созданием случайных чисел разобрались. Переходим непосредственно к алгоритму перетасовки карт.
Прежде всего, просмотрите его исходный код, а затем я объясню, как это все работает.
public static void reshuffle(int[] pack) {
if(pack != null) {
int length = pack.length;
//создаем генератор случайных чисел, в качестве начального
//значения передаем системное время
Random generator = new Random(new Date().getTime());
//тосуем колоду карт
//перебираем все карты колоды
for(int i = 0; i < length; i++) {
//генерируем случайное число, в диапазоне от нуля до
//конца колоды
int newPos = generator.nextInt(length);
//меняем местами текущую карту с картой, которая находится
//в pack[newPos]
int curCard = pack[i];
pack[i] = pack[newPos];
pack[newPos] = curCard;
//для увеличения эффекта "случайности" возникновения чисел,
//в течении перетасовки колоды, четыре раза устанавливаем
//новое начальное значение генератора случайных чисел
if(i%(length/4) == 0) {
//генерируем случайный интервал времени (мс)
int pause = generator.nextInt(20);
try {
//останавливаем работу программы на полученный
//интервал времени (максимально возможная задержка
//восемдесят миллисекунд)
Thread.currentThread().sleep(pause);
}
catch (InterruptedException ex) {}
//уставливаем новое начальное значение генератора
generator.setSeed(new Date().getTime());
}
}
}
}
За основу я взял давно известный алгоритм, но для увеличения степени “случайности” возникновения чисел, ввел несколько изменений.
Допустим, у нас есть колода из 36 карт. Для её хранения мы используем массив из 36 элементов, каждый из которых может принимать значения от 0 до 35.
Перетасовка выполняется следующим образом. Мы последовательно перебираем все ячейки массива с картами. Для каждой ячейки мы генерируем случайное число (newPos) в диапазоне от 0 до 35. Это число является новым положением карты в массиве. Т.е. мы меняем местами текущую карту с картой, которая лежит в ячейке с индексом newPos.
Теперь обратите внимание на строки начиная с if(i%(length/4) == 0) {. Этот блок кода будет выполняться четыре раза в течение работы метода. Принцип работы следующий. В первую очередь мы получаем случайное число в диапазоне от 0 до 20. Почему выбран именно этот диапазон, я объясню чуть позже. Это число задает время, на которое программа приостанавливает свою работу.
Остановка программы выполняем с помощью метода sleep(). После этого, мы опять устанавливаем текущее время в качестве нового базового значения для генератора случайных чисел.
Теперь разберемся, что все это нам дает. В первую очередь увеличивается время выполнения перетасовки. Это, конечно, не очень хорошо, но давайте подумаем. Максимально возможная задержка составляет 80 мс. Данный алгоритм предназначен для использования в карточных играх, в которых, при перетасовке карт, игроку обычно показывают какую-нибудь анимацию (это увеличивает реалистичность игры). Длительность такой анимации обычно около секунды или больше (игрок должен хоть что-то рассмотреть:-)). Т.е., за время этой анимации, можно будет раз десять перетасовать колоду.
А теперь посмотрим на сильные стороны этого алгоритма. Мы четыре раза устанавливаем новое базовое число. Предсказать значение этого числа практически невозможно, и не только потому, что длительность паузы мы выбираем случайным образом. Любая современная операционная система вносит дополнительный эффект случайности в работу алгоритма. Дело в том, что в системе выполняется одновременно несколько десятков процессов (программ). Но один процессор (не многоядерный) может выполнять одновременно только одну программу. Поэтому для создания эффекта многозадачности используется специальная программа – планировщик, которая переключает процессы. Сначала выполняется несколько команд из одной программы, потом – несколько из другой, и так далее. Порядок переключения программ зависит от многих причин. Это и приоритеты процессов, и тактовая частота процессора, и версия операционной системы, и многое другое.
Таким образом, существует высокая вероятность того, что выполнение нашего метода перетасовки будет прервано планировщиком (и не один раз). Системное время, естественно, не зависит от порядка работы нашей программы, и значения, которые возвращает метод getTime() предсказать практически невозможно. А именно этого мы и добиваемся.
Для тестирования работы алгоритма я написал небольшую программу. В неё входят 3 файла с исходными кодами. Reshuffler.java – имеет один статический метод, который и выполняет перетасовку карт. CardsPack.java – этот файл, содержит класс, который используется для создания колоды карт. Он содержит два метода: getPackOfCards() – возвращает массив с номерами карт;
toString() – возвращает строку с названиями карт в колоде.
Оба эти метода находятся в пакете cards.tools.
Main.java – содержит класс с функцией main, которая выполняет следующие операции:
- создает новую колоду;
- выводит её содержимое;
- перетасовывает колоду;
- и опять выводит её содержимое.
Теперь посмотрим результаты работы программы:
| Начальное расположение карт в колоде | Расположение карт после сортировки |
| шестерка пик семерка пик восьмерка пик девятка пик десятка пик валет пик дама пик король пик туз пик шестерка треф семерка треф восьмерка треф девятка треф десятка треф валет треф дама треф король треф туз треф шестерка бубен семерка бубен восьмерка бубен девятка бубен десятка бубен валет бубен дама бубен король бубен туз бубен шестерка червей семерка червей восьмерка червей девятка червей десятка червей валет червей дама червей король червей туз червей |
король пик десятка червей король червей восьмерка червей девятка треф валет червей восьмерка треф десятка пик шестерка треф семерка треф шестерка бубен король бубен туз треф валет пик туз бубен девятка пик король треф валет бубен восьмерка пик дама пик дама треф девятка червей семерка бубен туз червей десятка треф семерка червей шестерка червей десятка бубен дама бубен восьмерка бубен девятка бубен туз пик шестерка пик семерка пик дама червей валет треф |
Как видите, у нас все получилось.
Скачать исходный код проекта: cards_reshuffler_src.zip (2,6 кБ).
Скачать программу:cards_reshuffler_prog.zip (2,3 кБ).
Желаю успехов.
Постовой
