Последний раз редактировалось Skipper 29.06.2023, 17:07, всего редактировалось 2 раз(а).
Есть такая Windows игра Freecell, она же "Свободная ячейка", она же - по одному неправильному переводу на русский - Солитер. Даётся колода карт, есть 4 свободные ячейки, и все карты нужно сложить в дом по определенным правилам.
В расширенной версии Freecell можно сгенерировать, до 8 миллиардов разных изначальных конфигураций карт ("типов раскладов"). Каждый номер соответствует (однозначно переводится) в какую то определенную начальную конфигурацию карт.
Например, ввели номер "178" - получили расклад, пытаемся разложить, т.е. решить игру с данным номером.
Если не получилось- можем снова ввести тот же номер, и ту же начальную конфигурацию раскладывать заново с начала.
Позже были написаны программы, которые могут при введенном номере посчитать, и решить, раскладывается вообще данный номер игры или нет. Т.е. имеется ли принципиально, теоретически возможное решение. Некоторые номера настолько трудные, что ни один человек решить не может, (это недоступно человеческому мозгу), но программа доказывает что принципиально, какое то решение существует. (тогда любители головоломок всё таки упорно пытаются решить, а другие просто "подглядывают", какое же решение существует, и тем самым лишают себя удовольствия, решить головоломку).
Но игру Freecell можно разнообразить, играть не именно с 4-мя свободными ячейками, а скажем, с 3-мя, с 2-мя, с 5-ю, и т.д. С любым количеством. Понятно, что чем больше свободных ячеек, тем легче выиграть, т.е. сложить расклад по правилам.
И вот эти программы перебрали уже много миллиардов типов раскладов, и было установлено следующее:
0) примерно 0,2% от всех раскладов, можно решить, имея минимум 0 (ноль) свободных ячеек. Т.е. даже если их вообще нету, свободных ячеек, то это подмножество начальных конфигураций карт, разложимо.
1) примерно 15% от всех раскладов, можно решить, имея минимум 1 свободную ячейку, т.е. с одной это подмножество раскладов разрешимо, с меньшим количеством свободных ячеек - нет.
2) примерно 64% от всех раскладов, можно решить, имея минимум 2 свободные ячейки, т.е. с двумя это подмножество раскладов разрешимо, с меньшим количеством свободных ячеек - нет.
3) примерно 20% от всех раскладов, можно решить, имея минимум 3 свободные ячейки, т.е. с тремя это подмножество раскладов разрешимо, с меньшим количеством свободных ячеек - нет.
4) примерно 0,7% от всех раскладов, можно решить, имея минимум 4 свободные ячейки, т.е. с четырьмя это подмножество раскладов разрешимо, с меньшим количеством свободных ячеек - нет.
5) примерно 1 / 78000 от всех раскладов, можно решить, имея минимум 5 свободных ячеек, т.е. с пятью это подмножество раскладов - (в среднем один такой попадается на 78 тысяч), разрешимо, с меньшим количеством свободных ячеек - нет.
6) примерно 1 / 700 000 000 от всех раскладов, можно решить, имея минимум 6 свободных ячеек, т.е. с шестью это подмножество раскладов - (в среднем один такой попадается на 700 миллионов), разрешимо, а с меньшим количеством свободных ячеек - нет.
Можно построить график, и увидеть функцию в зависимости от этого числа ячеек. Посчитать вероятность для 7-ми, 8-ми, и т.д. ячеек, точно невозможно, но такое распределение скорее всего встречается и в других задачах на теорию вероятностей, а значит скорее всего, можно посчитать приблизительно, если знать тип распределения.
Какой же тип в данном случае, статистического распределения может быть, и какова вероятность, для двух следующих подмножеств - раскладов которые потребуют минимум 7 свободных ячеек, и 8 свободных ячеек?
|
