Раздел: Документация
0 ... 67 68 69 70 71 72 73 ... 117 Рис. 14.2. Идеальное тасование внахлест 22 карт (слева) и грубое тасование внахлест (быстрое тасование) этих карт (справа). т и 2к - т карт, причем мы будем предполагать, что к < т < к + 3 (почти совершенное снятие карт). Часть т карт сверху колоды (если мы начинаем с новой колоды, то они маркированы числами 1,2,... , т) быстро тасуется с оставшимися картами. Имеется 2к ~ т + 1 «щелей» между оставшимися картами, в которые могут войти m верхних карт, а именно «щель» над картой т + 1 и щели ниже карт т + 1, m + 2,... , 2к. Будем предполагать, что быстрое тасование вкладывает 0, 1, 2 или 3 карты в каждую из этих щелей. Попытаемся сделать разумное предположение о вероятностях для числа карт 0, 1, 2 или 3 быть вложенными в определенную щель. Пусть есть вероятность гкарт попасть в щель, ; = 1, 2, 3,4. Тогда мы, конечно, хотим, чтобы Ра +Pi+P2 +РЗ = 1- «Ожидаемое» число карт, входящих в щель, равно pi + 2р2 + Зрз, а всего имеется 2к - т + 1 щелей, так что «ожидаемое» число использованных карт есть (2к - т + l)(pi + 2р2 + Зрз). Возможно, мы должны уравнять это с числом имеющихся в нашем распоряжении карт, которое равно т. Поэтому будем считать, что (2к -да + + 2ра + Зрз) = да. Таким образом, если р2 и рз заданы {как и к и т), то ро и pi даются выражениями m - 2р2-3р3, Ро = 1 -Р1-Р2-Рз- (14.5) 2к - т + 1 Конечно, р2 ирз надо выбрать так, чтобы ро ир± были положительными и < 1. Заменяя дробь в (14.5) на 1 (что является разумным приближением при больших к), покажите, что нам нужно выбрать лишь р2 и рз приусловии 2р2 + Зрз < 1 . При больших к это будет служить руководством при выборе р и ft. Какие значения для р2 и рз вы считаете разумными? Какие значения получаются для ро и pi в случае п = 2к = 52 (обычной колоды) для каждого из четырех возможных значений т? Для вас написан М-файл ruf fl.el.rn, который реализует описанную выше модель быстрого тасования внахлест. Это довольно сложная программа, поскольку там тщательно рассматриваются различные возможности, как, например, когда карты 1,2,... ,т кончаются прежде заполнения щелей, и наоборот. При получении отрицательных значений ро или р% работа М-файла на этом заканчивается. Выполните М-файл ruffl.el.rn несколько раз, используя разумные с вашей точки зрения значения вероятностей и положив к - 26 (обычная колода). Возможно, вы сможете взять один из результатов и показать с помощью подходящей диаграммы, как карты из одной (грубо) половины входят в промежутки (зазоры) между картами другой половины. М-файл ruf fie lc ,m находит циклы быстрого тасования, как и выше, в § 14.3. Прогоните его три раза и каждый раз вычислите порядок тасования, равный НОК длин циклов. Он совпадает с числом повторений быстрого тасования, после которых восстанавливается первоначальный порядок карт. Единственная особенность здесь в том, что вы найдете этот порядок сильно отличающимся от порядка после идеального тасования 52 карт внахлест. 14-4-2- Дваи больше быстрых тасований М-файл ruf f 1е2 .тимеет больше возможностей в том, что касается последовательности быстрых тасований. В ваших экспериментах вы сможете выполнить до четырех тасований. Наша цель - узнать, насколько успешно 2, 3 или 4 быстрых тасования «рандомизируют»
колоду. При выполнении тасований вам будет предложено выбрать единственную карту, г-ю слева после очередного тасования (в колоде это i-я карта сверху) и передвинуть ее на j-e место слева, где ; и j не должны находиться слишком близко друг к другу. (Совет: Чтобы упростить ваши эксперименты, придерживайтесь ; = 1: первая карта всегда куда-то перемещается.) Запишите значение карты, которую вы передвинули. Мы увидим, можно ли угадать, какая карта была передвинута; если можно, то это верный знак, что колода не была рандомизирована. После перемещения одной карты все карты определенным образом раскладываются в столбцы. Выполняя М-файл с некоторым достаточно малым к (вам придется быть очень осторожным при выборе значений для Р2 и рз при малых к), посмотрите, сможете ли вы раскрыть метод, использованный при раскладывании карт по столбцам. Не обращайте внимания на все числа -1 в столбцах: они просто заполняют там место. При удаче передвинутая карта появится в отдельном столбце (не считая -1 ниже ее). Поэкспериментируйте с двумя, тремя или четырьмя тасованиями и проанализируйте ваши результаты в отгадывании передвинутой карты. Попробуйте проделать это с реальной колодой! Здесь мы приводим результаты типичного прогона для Р2 = 0.2, рз = 0.05 и трех тасований. Карта с номером 28 была перемещена на десятое место (так как [i, j] есть [1 10]), и, как вы можете видеть, она стоит отдельно как воспаленный большой палец! ans = 0 ... 67 68 69 70 71 72 73 ... 117
|
