Зацените игру "Пятнашки"

[Casper-SC]

Сообщение от Никки

Что ещё можно исправить, добавить в игру? Так глядишь и на новую версию изменений наберу...

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

Сделай, чтобы можно было собирать не картинку, а видео =)
Это возможно в WPF например. Где-то я видел видео, но сейчас найти не смог.

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

[apromix]

Суперово))) Мне понравилось))

[dampirik]

размешивание можно делать не случайное.... а так сказать "игровое" (передвигать фишки в случайном порядке по возможным позициям...)

[Гром]

Можно. Но только это надо как минимум пару сотен (или тысяч) раз переместить фишки, чтобы хорошо перемешалось. Гораздо проще один раз рандомом раскидать, посчитать за один проход что надо и в случае необходимости всего две фишки местами один раз поменять.

[Gorychev]

И свои 5 копеек добавлю, тож делал такую игрушку ради тренировки, кому интересно можно здесь скачать\посмотреть описание - Пятнашки
Есть также, описание алгоритма, правда особо сильно не описывал, поленился, но зато сорец с коментами - алгоритм
ЗЫ. Проверки на то, сложится или нет расклад, не делал. Как нибудь по свободе прикручу.

[leoparrd]

Для того чтобы задача сходилась есть простейший алгоритм. Надо сделать чётное число обменов с нетронутыми фишками.
В исходной позиции 15 фишек расставлены в правильном порядке. Следовательно может быть 2 4 6 перестановок.
1 Задаём случайное число в диапазоне 1-3 и умножаем на 2
Это будет количество обменов. Назначаем её переменной N
2 Выбираем случайным образом любую фишку.
3 Выбираем случайным образом "партнёра для обмена"
4 Меняем местами.
5 Эти фишки исключаем из дальнейшего выбора.
Пункты 2-5 повторить N раз

PS Нечётное число перестановок приводит к неразрешимой комбинации.

[Гром]

ИМХО, 15 раз вызвать функцию random (или еще какую), а затем 14 раз линейно пробежаться по массиву (причем каждый раз все меньше и меньше бегать), а затем, если надо, поменять две фишки местами - значительно проще, чем вызывать функцию random 2 * N раз (N - порядка 1000-10000 чтобы перемешивание было качественное).
Я по-прежнему считаю, что мой алгоритм - самый оптимальный!
Если же будет предложен алгоритм, более оптимальный, чем мой - с удовольствием это признаю, и возьму его на вооружение.

[leoparrd]

Уважаемый Гром
Ваш метод называется "Вдогонку" Сначала дал по морде а потом думаешь, а надо было? Того ли ударил? Это непрофессионально. В моём алгоритме, напротив, результат заранее известен.

[Гром]

Позволю себе не согласиться как с общей мыслью, так и со сравнением. "Дать в морду" - процесс необратимый (даже если заплатишь за лечение - сколько времени на это уйдет, а уж психологические и социальные последствия будут еще больше), а случайное раскидывание конечного числа фишек по дискретному набору позиций - вполне себе. Так что морально-этические категории к такому алгоритму неприменимы. Ну а применимы категории эффективности, и вот они-то как раз и указывают, что этот алгоритм лучше.
Разберем эти два алгоритма поподробнее.
Итак, мой алгоритм. 1-я стадия. Случайным образом раскидываем 15 фишек (чтобы не нарушать единообразия - даже на 15-ю позицию рандомом выбираем фишку, хотя и остался всего один вариант). Для i-й позиции (первая - за номером 0) у нас остается 15 - i свободных фишек из 15 возможных вариантов. => в среднем нужно вызвать функцию random 15 / (15 - i) раз.
Итого, всего за первый этап она вызывается 15 / 15 + 15 / 14 + ... + 15 / 1 = 50 раз.
Теперь рассмотрим второй этап - когда мы просматриваем весь массив из 15 элементов 14 раз - сначала сравниваем 1-й элемент с другими 14, потом 2-й - с 13 и т.д. Итого у нас 14 + 13 + 12 + ... + 1 = 105 итераций внутреннего цикла плюс 14 - внешнего.
Итого, считаем:
функция random() - 50 раз
итерации цикла - 119 штук
"ха-ха" - 2 раза
"проходите, проходите, здесь дует" - 1 раз.
Не так уж плохо.

Посмотрим ваш алгоритм. На каждый обмен позиций нам нужно 2 раза вызвать функцию random(). Число таких обменов для того, чтобы перемешать M фишек достаточно хорошо (растет экспоненциально с ростом M) я оцениваю в 2 ^ (M - 1), пусть даже 2 ^ (M - 2). При M = 15 получаем N ~ 2 ^ (15 - 2) = 8192. Итого, порядка от 1000 (довольно плохой вариант) до примерно 10000 (хороший вариант). И за обмен функция random() вызывается дважды.
В общем, получаем 16384 вызовов функции random().

Подводя окончательные итоги - оба алгоритма дают одинаковые результаты при следующем количестве операций (в среднем):
Мой - 50 вызовов random(), 120 итераций цикла
Ваш - 16000 вызовов random().

По-моему, мой алгоритм по-прежнему довольно профессионален.

[leoparrd]

Гром
Ну вы даёте! Очень внимательно почитайте мой алгоритм.
Первый вызов random - это определение количество обменов. Поскольку фишек 15
а количество обменов должно быть чётным то только 3 варианта
2 обмена положение изменяют только 4 фишки - 4 random
4 обмена положение меняют 8 фишек - 8 random
6 обменов положение меняют 12 фишек - 12 random

так что 3 варианта обмена. максимально число random - 12 плюс random на выбор варианта. Итого - 13 random

Вы забыли тот факт, что выбранные фишки исключаются из выбора. Пункт 5.

Было 15 первый обмен - осталось 13
Было 13 второй обмен - осталось 11
------------------------------------ конец 1 варианта
Было 11 третий обмен - осталось 9
Было 9 четвёртый обмен - осталось 7
------------------------------------- конец 2 варианта
Было 7 пятый обмен - осталось 5
Было 5 шестой обмен - осталось 3
-------------------------------------- конец 3 варианта

В принципе можно попробовать обмен с пустышкой. Тогда 4 вариант (8 обменов)
Но это надо попробовать.