Ключевое слово
03 | 04 | 2020
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 09 Фев 2020 11:50 #151

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.

Понятно. При попадании в корабль происходит переход на второстепенную подпрограмму SUB_DESTROY() добивания. Если корабль уничтожен, то при выходе из SUB_DESTROY() должен поменяться контекст, чтобы вызывающая функция была "в курсе".
И здесь тоже важно определить, в какую сторону добивать без промаха. Как это сделать, пока неизвестно.

Warning: Spoiler! [ Click to expand ]
...не мы первые, не мы последние...

алгоритмические задачки 09 Фев 2020 12:38 #152

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Да, при добивании придется рассматривать множество случаев. Пожалуй, не буду заморачиваться. :(
Сам себе доктор наук

алгоритмические задачки 11 Фев 2020 07:03 #153

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Есть некоторые стратегии выигрыша в "морском бое".
...не мы первые, не мы последние...

алгоритмические задачки 11 Фев 2020 07:29 #154

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Есть некоторые стратегии выигрыша в "морском бое".

Там все формулы непропечатаны, читать одно неудовольствие. ((
Сам себе доктор наук

алгоритмические задачки 12 Фев 2020 16:12 #155

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.

Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.
Сам себе доктор наук
Last Edit: 12 Фев 2020 16:14 by Sam Sebe.

алгоритмические задачки 13 Фев 2020 13:51 #156

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.

Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.

Убрал это упрощение. Зато программа усложнилась (анализатор пишет, что ее цикломатическую сложность 52 надо бы уменьшить до 26). Теперь все происходит хоть и случайно, но реалистично.

Снова рассмотрел 1 млн случайных расстановок. Теперь для уничтожения всех кораблей требуется от 37 до 92 выстрелов, в среднем 64. Заодно посчитал, сколько клеток остаются чистыми (без кораблей, зон вокруг и выстрелов): оказалось, что от 0 до 25, в среднем 3.

Если хотите, можете предложить какую-нибудь другую стратегию игры, а я попробую оценить ее вместо рассмотренной случайной.
Сам себе доктор наук

алгоритмические задачки 14 Фев 2020 06:17 #157

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Вот, нашел распределение вероятности по типу корабля, уничтоженного 1-м, 2-м, ..., 10-м. Первая, априори очевидная строчка, говорящая о том, что 1-м скорее всего (30 + 30 = 60 % случаев) будет уничтожен крейсер или эсминец, свидетельствует, что программа работает верно. Последние же строчки, указывающие на то, что к концу игры вероятнее всего выживут только катера, в общем тоже ожидаемы - качественно, но вряд ли количественно. При чисто случайном обнаружении кораблей, разумеется.

probability_battle.png
Сам себе доктор наук

алгоритмические задачки 15 Фев 2020 06:27 #158

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Напрашивается следующая полуслучайная стратегия игры в Морской бой. Раскрасим игровое поле в виде шахматной доски и будем стрелять по клеткам одного цвета, пока гарантированно не уничтожим все большие корабли, а потом - по оставшимся клеткам, если катера еще остались.

И снова рассмотрим 1 млн случайных расстановок кораблей. При чисто случайной стрельбе (см. выше) требовалось 37-92 выстрела, в среднем 64, а теперь требуется 37-86 выстрелов, в среднем 63. Небольшое, но улучшение есть. Вероятности тоже изменились.

battle_37-63-86_0-3-24.png


Вместо рассмотренных случайных расстановок я рассмотрел также 1 млн расстановок не совсем случайных, тоже упомянутых выше: большие корабле прижимаются к краям игрового поля и/или друг к другу, а катера размещаются равномерно в оставшихся клетках. Такие расстановки действительно оказалось поразить труднее. Потребовалось 40-89 выстрелов, в среднем 67. Странно, но вероятности почему-то вышли те же самые, надо будет перепроверить.

battle_40-67-89_0-4-28.png
Сам себе доктор наук
Last Edit: 15 Фев 2020 06:32 by Sam Sebe.

алгоритмические задачки 15 Фев 2020 15:39 #159

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Насчет вероятностей вроде все верно, практически одно и то же. Подсчитал еще, сколько выстрелов нужно, чтобы уничтожить все большие корабли: 22-75, в среднем 51 (в случае 63 выстрелов) или 52 (в случае 67 выстрелов).
Сам себе доктор наук
Last Edit: 15 Фев 2020 15:41 by Sam Sebe.

алгоритмические задачки 17 Фев 2020 07:10 #160

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Выше я раскрасил игровое поле в шахматном порядке, но не сказал, с какого цвета начинать обстрел. На самом деле я выбирал его наугад индивидуально для каждой расстановки кораблей. А теперь усовершенствовал идею и для статистики обстреливаю каждую расстановку дважды, так и так.

Я рассматривал 1 млн расстановок. Достаточно этого статистически или нет? Отдельную расстановку можно описать последовательностью, в которой предложенная стратегия уничтожает корабли, а теперь даже двумя последовательностями. Одни последовательности встречаются чаще, другие реже: например, катера чаще уничтожаются последними. Сколько их, этих последовательностей может быть всего? Очевидно,

C(10, 4)*C(6, 3)*C(3, 2)*C(1, 1) = 12 600 штук (4 катера, 3 эсминца, 2 крейсера, 1 линкор).

Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.
Сам себе доктор наук
Last Edit: 17 Фев 2020 07:11 by Sam Sebe.

алгоритмические задачки 17 Фев 2020 10:21 #161

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Если повороты и зеркальные отражения не учитываются, то можно говорить об уникальных расстановках.
Одна расстановка имеет 2 зеркальных отражения и 4 поворота. Итого 2*4=8.
...не мы первые, не мы последние...

алгоритмические задачки 17 Фев 2020 10:30 #162

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.

Рассмотрел 5 млн расстановок, или 10 млн последовательностей, различных среди последних оказалось 12 599 штук, т.е. не оказалось всего одной, какой-то типа 1*1***11**, где 1 обозначает катер.
Сам себе доктор наук

алгоритмические задачки 18 Фев 2020 13:28 #163

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Обнаружил неожиданную вещь. Казалось бы, вероятность, с которой корабль данного типа будет уничтожен первым, пропорциональна суммарной площади кораблей этого типа. Т.е. линкор и катер будут уничтожены первыми с одинаковой вероятностью (4 = 1 + 1 + 1 + 1), то же самое крейсер и эсминец (3 + 3 = 2 + 2 + 2). Но по факту это не совсем так. Оказалось, эта вероятность зависит от последовательности, в которой корабли расставляются на игровом поле, и эта зависимость не исчезает с увеличением числа рассматриваемых расстановок. Я объясняю это тем, что равномерно случайно на поле можно поставить только первый корабль, а последующие ставятся уже не совсем равномерно.

Поэтому я решил последовательность расстановки также сделать случайной. Правда, не часто, но изредка линкор или второй крейсер не удается вставить в поле - такие расстановки я пропускаю, в расчет не беру. Вот какие вероятности того, что корабль данного типа будет уничтожен 1-м, 2-м, ..., 10-м, получились для 1 000 000 расстановок (или 1 001 262 вместе с пропущенными).

battle_1001262.png
Сам себе доктор наук
Last Edit: 18 Фев 2020 13:33 by Sam Sebe.

алгоритмические задачки 18 Фев 2020 15:54 #164

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Получается, что сначала лучше расставить мелкие катера, тогда случайность будет наибольшей. А линкор последним, - он слишком неповоротливый.
...не мы первые, не мы последние...

алгоритмические задачки 18 Фев 2020 16:12 #165

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Ну наверное. Только разница вероятностей хоть и есть, но небольшая, в сотых. Опять же если начинать с катеров, то линкору или крейсеру может места не хватить, придется переделывать.
Сам себе доктор наук

алгоритмические задачки 19 Фев 2020 07:51 #166

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Вот какая идея. Допустим, мы рассматриваем (измеряем, оцениваем и т.п.) некоторый объект с помощью некоего метода. Метод этот обладает определенной двойственностью, "бинокулярностью", так сказать. С одной стороны, он дает числовой результат x, а с другой - число y, пусть y > x > 0. Данную бинокулярность можно определить как

k = (y - x)/(y + x).

Параллельно объект характеризуется сопряженной величиной, не знаю, как ее назвать образно,

k* = x/y.

В нашем случае объектом является расстановка кораблей, а методом - стратегия ее обстрела. Если начинать обстрел с клеток одного цвета, удастся уничтожить все корабли за x > 20 выстрелов, а если начнем с другого, потребуется y < 100 выстрелов. Я подсчитал на 1 млн расстановок, что в 5% случаев k = 0, но бывает и k > 30%, а в средневзвешенном k = 5%.

Как можно было бы назвать k и k* в этом случае, что скажете?
Сам себе доктор наук
Last Edit: 19 Фев 2020 07:56 by Sam Sebe.

алгоритмические задачки 19 Фев 2020 16:05 #167

  • инфолиократ
  • инфолиократ's Avatar
В нашем случае объектом является расстановка кораблей, а методом - стратегия ее обстрела.
И в любом ином случае понятия эти (объект и метод) имеют место быть, не только в играх. Так как на примере шахмат защищались и экономические диссертации, то данные коэффициенты очевидно универсальнополезными могут быть не только для "уничтожения уорабликов" или удовольствия ради... Поэтому, даже если меня неспрашивают, вставлю свой пятак я так:
Как можно было бы назвать k и k* в этом случае, что скажете?
С учетом того что в любой теории ключевое понятие может быть произвольным и на конечные результаты название термина не влияет, называю ТРИварианта (формально абстрактно, по автору, объективно по эффективности, субъективно - произвольно):
1. k и k* Это коэффициенты Ксс
2. По аналогии, есть же
коэффициент вариации
- коэффициент эффективности МЕТо = метода с объектом.
3. кнс= каждый назовет свое.
З павагай да неабыякавых

алгоритмические задачки 20 Фев 2020 14:37 #168

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
:idea:: объединить две предыдущие задачи!

Расстановку кораблей назовем связной, если существует змейка, их всех содержащая;
минимальную длину этих змеек назовем степенью связности. Сразу возникает несколько вопросов.

1. Существуют ли несвязные расстановки?
2. Каковы минимальная и максимальная степени связности?
3. Влияет ли степень связности на скорость уничтожения расстановки?
Сам себе доктор наук

алгоритмические задачки 23 Фев 2020 14:03 #169

  • инфолиократ
  • инфолиократ's Avatar
С 23 февраля! С праздником (в той теме есть картинка с одним фасадом +2 за).
С учетом предыдущего (см. выше)
Я объясняю это тем, что равномерно случайно на поле можно поставить только первый корабль, а последующие ставятся уже не совсем равномерно.

Поэтому я решил последовательность расстановки также сделать случайной.
отмечу:
1. Расстановку кораблей назовем связной, если существует змейка, + "случайная" расстановка подсказывают ответ на 1?
2. Здорово было бы,чтобы k и k* в этом случае поучавствовали в ответе на 2?
3. 3? сугубо "криптографический": определив конечное число для пп 1 и2, найдя "ключ" можно повлиять на "скорость уничтожения расстановки". Таковы мои инфолиопримитивнослучайные предположения сегодня после вчерашнего.
З павагай да неабыякавых

алгоритмические задачки 24 Фев 2020 18:35 #170

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
1. Существуют ли несвязные расстановки?
2. Каковы минимальная и максимальная степени связности?

1. Проверил 100 тысяч случайных расстановок. Все оказались связными.

2. Очевидно, минимум = 20 + 9 = 29. С максимумом сложнее. Проверил 10 тысяч расстановок (~ 10 минут компьютерного времени). Для каждой расстановки змейка минимальной длины искалась до тех пор, пока очередная найденная змейка не совпадала по длине с одной из найденных ранее. Конечно, логичнее было бы, чтобы повторилась не какая-то длина, а минимальная среди найденных ранее, но этого слишком долго жать. Вот какое распределение получилось - со средней степенью связности e = 44 и со средним числом n = 4 найденных змеек разной длины на одну расстановку.

zmejka_44_4.png


P.S. Забыл пояснить, что ради минимальности все найденные змейки обрезаются до корабля со стороны старта и кораблем же финишируют. Кстати, по факту это не то же самое, что при поиске (случайном) всегда стартовать с корабля.
Сам себе доктор наук
Last Edit: 25 Фев 2020 04:09 by Sam Sebe.

алгоритмические задачки 25 Фев 2020 19:33 #171

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Решил посмотреть, кораблем какой длины l змейка начинается (после обрезания) и какой кончается. Рассмотрел 40 тысяч змеек (39 555, точнее), в среднем по 4 змейки (разной длины) на 10 тысяч расстановок кораблей; именно про них говорится в предыдущем посте. Соответствующие распределения a и b, в процентах, получились следующие.

zmejki_a-b_renew.png


P.S. Исправил неточность в изображении.
Сам себе доктор наук
Last Edit: 26 Фев 2020 13:22 by Sam Sebe.

алгоритмические задачки 26 Фев 2020 07:36 #172

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
:idea: По идее змейка минимальной длины, содержащая все корабли, может начинаться и кончаться катером, эсминцем, крейсером и линкором (длиной l = 1, 2, 3 и 4). Всего 15 возможностей (16-я отсутствует, поскольку линкор только один).

Возникает смутная мысль об аналогии с игрой в пятнашки в коробочке 4х4, где требуется упорядочить исходную случайную комбинаций из 15 пронумерованных подвижных клеток-костяшек за (желательно) минимальное число движений. Тогда разрешимость этой задачи - исследованной вдоль и поперек - аналогична (?) связности расстановки кораблей. С известной оговоркой задача всегда разрешима -

Вики wrote:
Если допустить поворот коробки на 90 градусов, при котором изображения цифр окажутся лежащими на боку, то можно перевести неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо цифр на костяшки нанести точки и не фиксировать положение коробки, то неразрешимых комбинаций вообще не окажется.

Вот, объединил две таблички из предыдущего поста в одну. Строки - это корабль в начале змейки, а столбцы - в конце.

zmejki_ab_2020-02-26.png
Сам себе доктор наук
Last Edit: 26 Фев 2020 11:54 by Sam Sebe.

алгоритмические задачки 27 Фев 2020 15:16 #173

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Выше получилось, что в среднем длина змейки, содержащей все корабли, равна 44. Это значение можно немного уменьшить. Как только установлена последовательность кораблей в змейке, нетрудно вычислить манхеттенское расстояние между ними и тем самым оценить снизу минимальную длину змеек, содержащих корабли в данной последовательности, чтобы по факту уменьшить 44 от силы до 41.
Сам себе доктор наук

алгоритмические задачки 27 Фев 2020 15:28 #174

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Сможет ли соперник догадаться, что корабли расставлены по змейке?
Не каждый. :|
...не мы первые, не мы последние...

алгоритмические задачки 27 Фев 2020 15:38 #175

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Нет, пока никакого соперника нет. Речь идет о "змеиной" характеристике расстановки кораблей.
Сам себе доктор наук

алгоритмические задачки 29 Фев 2020 06:43 #176

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?
Сам себе доктор наук

алгоритмические задачки 29 Фев 2020 08:01 #177

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 429
  • Thank you received: 9
  • Karma: 3
Sam Sebe wrote:
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?

Сложновато будет, я пас. :dontknow:
...не мы первые, не мы последние...

алгоритмические задачки 04 Март 2020 06:51 #178

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Sam Sebe wrote:
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?

Сложновато будет, я пас. :dontknow:

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

Зато возникла новая идея. :idea:

Раньше я брал произвольную расстановку кораблей и старался найти змейку минимальной длины, проходящую через них. Но ведь можно и наоборот. Можно взять змейку максимальной длины и попытаться найти все расстановки кораблей, помещающиеся в нее, - с целью выяснить, всегда ли они существуют, эти расстановки, и сколько их в среднем. А главное, змейку (или змейки) максимальной в этом смысле "емкости" можно было бы рекомендовать (?!) в качестве стратегии расстановки кораблей.

Но для этого нужно сначала найти все змейки максимальной длины. Эта задача уже решалась выше, но там игровое поле было меньше - не 10х10, а 8х8, и максимальная длина змейки была известна - 42 клетки. А здесь пока ничего не известно. :dontknow:
Сам себе доктор наук
Last Edit: 04 Март 2020 07:26 by Sam Sebe.

алгоритмические задачки 08 Март 2020 15:41 #179

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Идея предыдущего поста неплохая, но труднореализуемая. Из тех змеек, что я нашел, максимальные имеют длину 63 клетки. И число помещающихся в них расстановок кораблей так велико, что не поддается счету. Поэтому пришлось взять змейки покороче и ограничить их количество. Я взял 10 первых попавшихся змеек длиной по 35 клеток. В качестве примера изображена последняя змейка, самая емкая из 10 (стартующая в середине игрового поля и финиширующая в углу), в которую помещается 46 592 расстановки кораблей: линкор (4 клетки), 2 крейсера (по 3 клетки), 3 эсминца (по 2 клетки) и 4 катера (одноклеточных); крестики - это клетки змейки, остальные клетки пустые; корабли не должны касаться друг друга. Вот какая статистика получилась, причем 2 змейки оказались нулевой емкости.

m46592.png


Я не придумал ничего лучше, чем запрограммировать 10 вложенных циклов, чтобы перебрать все возможные взаимные положения 10 кораблей, одновременно отбрасывая повторяющиеся расстановки, повторяющиеся из-за того, что корабли одного типа неразличимы, так что найденные расстановки нужно еще и запоминать.
Сам себе доктор наук
Last Edit: 08 Март 2020 15:58 by Sam Sebe.

алгоритмические задачки 09 Март 2020 18:11 #180

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1235
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
Я не придумал ничего лучше, чем запрограммировать 10 вложенных циклов, чтобы перебрать все возможные взаимные положения 10 кораблей, одновременно отбрасывая повторяющиеся расстановки, повторяющиеся из-за того, что корабли одного типа неразличимы, так что найденные расстановки нужно еще и запоминать.

Усовершенствовал программу, чтобы расстановки не повторялись, и теперь их не нужно запоминать и сравнивать, коль скоро нам надо просто их сосчитать. Программа заработала на два порядка быстрее, и предыдущая статистика получилась за 10 секунд вместо 22 минут, так что теперь можно брать змейки и подлиннее. Вот, например, статистика для змеек в 40 клеток за менее чем 5 минут. Приведена также одна из 10 змеек, попавшаяся последней.

l40.png


Но до змеек длиной 63 клетки все равно далеко. ((
Сам себе доктор наук
Last Edit: 09 Март 2020 18:53 by Sam Sebe.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум