Написать пост

Напишите метод, тасующий карточную колоду

Аватар Типичный программист

Обложка поста Напишите метод, тасующий карточную колоду

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

Решение

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

Давайте будем решать задачу «в лоб». Можно выбрать карты в произвольном порядке и поместить их в новую колоду. Фактически колода представляет собой массив, следовательно, нам нужен способ, позволяющий заблокировать отдельные элементы.

			Исходная колода (до выбора 4):		   [1]	[2]	[3]	[4]	[5]
/* Выбираем случайный элемент для помещения его в начало перетасованной колоды
* Помечаем элемент в оригинальной колоде как "заблокированный", чтобы
* не выбрать его снова */
Перемешанная колода (после выбора 4):	[4]	[?]	[?]	[?]	[?]	
Исходная колода (после выбора 4):		[1]	[2]	[3]	[X]	[5]
		

Если мы пометим элемент [4], что помешает выбрать его еще раз? Один из способов – поменять местами «мертвый» ([4]) и первый элементы колоды:

			Исходная колода (до выбора 4): 		 [1]	 [2]	[3]	[4]	[5]
/* Выбираем случайный элемент для перемещения его в начало перетассованной колоды
* Существует элемент 1, который заменит выбранный элемент. */
Перемешанная колода (после выбора 4):	[4]	[?]	[?]	[?]	[?]
Исходная колода (после выбора 4):		[X]	[2]	[3]	[1]	[5]
/* Выбираем случайный элемент для перемещения его в начало
* перетасованной колоды. Есть элемент 2, который заменит только что
* выбранный элемент */
Перетасованная колода (после выбора 3):  [4]	[3]	[?]	[?]	[?]
Исходная колода (после выбора 3):		[X]	[X]	[2]	[1]	[5]
		

Алгоритм проще реализовать для ситуации, когда «мертвы» первые k карт, чем для ситуации, когда, например, «мертвы» третья, четвертая и девятая карты.
Оптимизировать алгоритм можно, объединив перемешанную и исходную колоды вместе.

			Исходная колода (до выбора 4):		[1]	[2]	[3]	[4]	[5]
/*Выбираем случайный элемент между 1 и 5 и меняем его местами с 1.
* В этом примере мы выбрали элемент 4.
* После этого элемент 1 - "мертв" */
Исходная колода (после выбора 4): 	[4]	[2]	[3]	[1]	[5]
/* Элемент 1 "мертв". Выбираем случайный элемент для замены с 
* элементом2. В этом примере пусть мы выберем элемент
* 3.*/
Исходная колода (после выбора 3):	 [4]	[3]	[2]	[1]	[5]
/* Повторяем. Для всех i между 0 и n-1 меняем местами случайный элемент j
* (j >= i, j < n) и элемент i. */
		

Этот алгоритм легко реализовать итеративно:

			public void shuffleArray(int[] cards) {
	int temp, index;
	for (int i = 0; < cards.length; i++) {
	/*Карты с индексами от 0 до i-1 уже были выбраны
	* (они перемещены в начало массива), поэтому сейчас мы
	* выбираем случайную карту с индексом, больше или равным i
	* */
	index = (int) (Math.random() * (cards.length - i)) + i;
	temp = cards[i];
		cards[i] = cards[index];
		cards[index] = temp;
	}
}
		

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»

Следите за новыми постами
Следите за новыми постами по любимым темам
12К открытий12К показов