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

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

алгоритмические задачки 02 Фев 2020 07:01 #121

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84267
  • Thank you received: 1250
  • Karma: 61
Гораздо супрематичнее, чем у Малевича :yess:
Каждому - своё.

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

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
Sam Sebe wrote:
Чего никто не оценит мой супрематизм? :(

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

Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?

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

Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.

Возможно ли вывести общую формулу подсчёта максимально допустимых закрашенных клеток при другой размерности доски?
Доска 1*1 = 1 закрашенная клетка;
Доска 2*2 = 3 клетки;
Доска 3*3 = 7 клеток;
Доска 4*4 = 11, и т.д.
...не мы первые, не мы последние...

алгоритмические задачки 02 Фев 2020 09:26 #123

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?

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

Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.

Возможно ли вывести общую формулу подсчёта максимально допустимых закрашенных клеток при другой размерности доски?
Доска 1*1 = 1 закрашенная клетка;
Доска 2*2 = 3 клетки;
Доска 3*3 = 7 клеток;
Доска 4*4 = 11, и т.д.

На 1-й вопрос не знаю, как ответить. Надо подумать.
На вопрос про распределение "кораблей" ответить проще.
А насчет размерности больше восьми... думаю, моему компьютеру не под силу будет.
Сам себе доктор наук
Last Edit: 02 Фев 2020 09:33 by Sam Sebe.

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

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

Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?

Вот, нашел это распределение.

touchs.png


Эти 108 + 8 змеек (исчерпывающее число) максимальной длины (42 клетки) стартуют в 1-м квадранте, и 16 из них в нем же финишируют, т.е. 8 змеек учитываются дважды: в одном направлении и в другом. Случаев касания, оказывается, не от 2 до 6, а от 5 до 8.
Сам себе доктор наук
Last Edit: 02 Фев 2020 19:21 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Вот еще вдогонку распределение змеек по числу изломов.

knees.png
Сам себе доктор наук
Last Edit: 03 Фев 2020 10:31 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.

Кстати, хорошая наводка. Сколько существует различных начальных расстановок кораблей в классическом Морском бое?

Поле 10х10, один линкор (4-клеточный), два крейсера (3-кл.), три эсминца (2-кл.) и четыре катера (1-кл.). Касания и изломы не допускаются.
Сам себе доктор наук

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
Сколько существует различных начальных расстановок кораблей в классическом Морском бое?

Поле 10х10, один линкор (4-клеточный), два крейсера (3-кл.), три эсминца (2-кл.) и четыре катера (1-кл.). Касания и изломы кораблей не допускаются.

Вопрос оказался интересным. Ответить на него я пока не смог, зато возникли другие интересные вопросы.

Возьмем произвольную расстановку. Корабли и запретные зоны вокруг них (корабли не касаются друг друга) заполняют какое-то количество клеток игрового поля. Но некоторые клетки остаются незаполненными. Спрашивается, каково минимальное возможное число этих незаполненных клеток и то же максимальное? В частности, можно ли заполнить все игровое поле без остатка или, наоборот, оставить незаполненной, скажем, его половину? Как вы считаете? Я рассмотрел 1 миллион случайных расстановок (возможно, совпадающих: я не следил) и в его пределах ответы знаю.
Сам себе доктор наук

алгоритмические задачки 04 Фев 2020 14:09 #128

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
Оставить половину можно, для этого надо постараться компактно втиснуть.

▄▄▄ ▄▄ ▄▄▄ 3+1+2+1+3=10
▄▄ ▄▄ ▄▄ ▄ 2+1+2+1+2+1+1=10
▄▄▄▄ ▄ ▄ ▄ 4+1+1+1+1+1+1=10

В игре такую расстановку не применять! Противник сходу просечёт поляну потопит все корабли. :bugaga:
...не мы первые, не мы последние...
Last Edit: 04 Фев 2020 14:11 by Andralex.

алгоритмические задачки 04 Фев 2020 14:26 #129

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Оставить половину можно, для этого надо постараться компактно втиснуть.

▄▄▄ ▄▄ ▄▄▄ 3+1+2+1+3=10
▄▄ ▄▄ ▄▄ ▄ 2+1+2+1+2+1+1=10
▄▄▄▄ ▄ ▄ ▄ 4+1+1+1+1+1+1=10

В игре такую расстановку не применять! Противник сходу просечёт поляну потопит все корабли. :bugaga:

Нет, это было бы чересчур просто, это всегда 80 пустых клеток. В вопросе спрашивается про заполнение не только собственно корабельных клеток, но и зон вокруг них. Например, линкор - это не только 4 его клетки, но и, в худшем случае, еще 14 клеток вокруг.
Сам себе доктор наук
Last Edit: 04 Фев 2020 14:28 by Sam Sebe.

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

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 40040
  • Thank you received: 89
  • Karma: 24
:dontknow:

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Вот какого вида заполнения имеются в виду. Здесь незаполненными остались 1 клетка и 37 клеток.

battle_o1.png
battle_o37.png


А про выигрышные расстановки я еще скажу.
Сам себе доктор наук
Last Edit: 04 Фев 2020 15:38 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
А вот какое распределение
1 миллиона случайных расстановок
соответствующее получилось.

buttle_o.png


Кстати, 37/100 - это 1/e, можно сказать.
Сам себе доктор наук
Last Edit: 04 Фев 2020 15:41 by Sam Sebe.

алгоритмические задачки 05 Фев 2020 07:20 #133

  • инфолиократ
  • инфолиократ's Avatar
Т.е. ТАКИ
1. точно - случайность - непознанная закономерность?
2. очевидно (объективно, трояко): есть начало таблицы, есть середина...
3. субъективно, жаль что
Число, которое считаю "моё" 23- в нижней половине получилось.
З павагай да неабыякавых
Зы. Целиком и полностью полагаясь на ваше усмотрение, ув. Sam Sebe, не вычислите ли сумму всех усеченных гармонических рядов (без 1, без 2-х, без ТРЕХ цифр) и не определите ли № конечного слагаемого ГР, обеспечивающего ТОЧНО ТАКУЮ ЖЕ СУММУ? А вдруг полученныое требуемое число слагаемых Гармонического ряда ТОЧНО совпадет с числом, которое называл СергеП для вселенсконатурального7. З павагай, паклонам

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Оптимизировал программу, и она стала считать в 10 раз быстрее, так что тот же миллион случайных расстановок кораблей получился за 6 минут. Распределение по числу незаполненных (за вычетом кораблей и примыкающих к ним клеток) похожее.

battleship_o_1000000.png


Вот две крайние расстановки из найденных: одна полностью (о=0) заполняет игровое поле, а другая - по минимуму (о=38).

battleship_o0-38.png


Кстати, 38 : 62 - это золотое сечение. Подозреваю, 62 заполненные клетки из 100 - это действительно минимум. Впрочем, теперь реально рассмотреть и целых 10 миллионов расстановок.
Сам себе доктор наук
Last Edit: 06 Фев 2020 13:46 by Sam Sebe.

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

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
А если зеленый трехпалубник из центра (o=38) подвинуть вправо на край доски? Чёрных клеток станет больше.
...не мы первые, не мы последние...

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Да, правильно, на 4 штуки. Значит, не золотое сечение. Очень жаль. Ладно, сейчас на 10 миллионах проверим.

А еще и одну-две красные можно подвинуть.
Сам себе доктор наук
Last Edit: 06 Фев 2020 13:56 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Sam Sebe wrote:
Ладно, сейчас на 10 миллионах проверим.

battleship_o_10000000.png


Чуть лучше (о=39), но все равно не минимум.
Сам себе доктор наук

алгоритмические задачки 06 Фев 2020 19:20 #138

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Интересную вещь заметил. Если уменьшить игровое поле до 9х9, то при последовательной (линкор - крейсера - эсминцы - катера), но случайной расстановке кораблей примерно в одном из 300-400 случаев осуществить ее не удается: не всем катерам хватает места (бывает даже, что только одному хватает). А вот на поле 10х10 такого не случается, т.е. набор кораблей для него как бы оптимален.
Сам себе доктор наук
Last Edit: 06 Фев 2020 19:21 by Sam Sebe.

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

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

Посмотрел в Википедии про "Морской бой". Оказывается, привычный нам набор кораблей присутствует только в ее русскоязычной версии, а во всех других ее версиях, даже в хохляцкой, он другой (6х1 + 4х2 + 3х3 + 2х4 = 31 клетка) - под копирку с англоязычной версии, хотя игровое поле прежнее, 10х10. Но в таком виде случайную расстановку кораблей удается осуществить только 96-97 % случаев - в этом смысле такой набор кораблей для поля 10х10 является неестественным, избыточным. Чисто по-мерикански. Властелины морей океанов. ))
Сам себе доктор наук
Last Edit: 07 Фев 2020 18:41 by Sam Sebe.

алгоритмические задачки 07 Фев 2020 21:27 #140

  • инфолиократ
  • инфолиократ's Avatar
Andralex wrote:
А если зеленый трехпалубник из центра (o=38) подвинуть вправо на край доски? Чёрных клеток станет больше.
А если поменять его с левым угловым двухпалубником?

З павагай да неабыякавых

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

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
Sam Sebe wrote:
Но в таком виде случайную расстановку кораблей удается осуществить только 96-97 % случаев - в этом смысле такой набор кораблей для поля 10х10 является неестественным, избыточным.

Дополнение.
В настоящее время, имея под рукой компьютеры, не составит труда рассчитать оптимальное количество кораблей на доске N*N. Так, чтобы было не тесно,-- тогда быстро игра закончится, но и не просторно,-- тогда игроки от постоянных бультыханий снарядов в воду просто впадут в унылость.
Но, игра морской бой известна ещё до начала повальной компьютеризации.
Возникает вопрос: как же так высчитали идеально?
Ответ: постепенно и опытным путём. Так же как и шахматы за тысячи лет обтесались др идеала.
...не мы первые, не мы последние...

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

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
инфолиократ wrote:
А если поменять его с левым угловым двухпалубником?

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

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Выигрышная стратегия в "Морской бой" описана в Википедии. Если коротно, то все корабли, кроме катеров, надо собрать в одну кучу, чтобы оставить для катеров площадь побольше, где их трудно будет найти. Правда, мне это несколько сомнительно: вдруг противник быстренько (коль скоро ход не передается) перебьет всю кучу и возьмется за катера, а я еще ничего не успею.

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

battle_o29-60.png


Получилось, что max = 60, но расстановка такая нашлась всего одна. И она "полукомпактная", т.е. 3 корабля прижаты к одному краю и 3 к противоположному, а 60 клеток в центре остаются незанятыми (чтобы равномерно разместить там катера).
Сам себе доктор наук

алгоритмические задачки 08 Фев 2020 18:42 #144

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
вдруг противник быстренько (коль скоро ход не передается) перебьет всю кучу и возьмется за катера, а я еще ничего не успею.
Для таких случаев особо хитрые игроки в начале рисуют не десять, а девять кораблей, и одноклеточный катер в самом конце игры, в последний момент.
...не мы первые, не мы последние...

алгоритмические задачки 08 Фев 2020 18:52 #145

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

battle_o28-60.png
Сам себе доктор наук

алгоритмические задачки 08 Фев 2020 18:57 #146

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

Ну это как бы для школьников, которым важно победить, а не просто убить время.
Сам себе доктор наук

алгоритмические задачки 09 Фев 2020 10:35 #147

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Получил-таки 7 расстановок с о=44, все разные.
Это для набора из 10 кораблей, с катерами.

battle_o6-44.png
Сам себе доктор наук
Last Edit: 09 Фев 2020 10:38 by Sam Sebe.

алгоритмические задачки 09 Фев 2020 10:41 #148

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

алгоритмические задачки 09 Фев 2020 10:52 #149

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 432
  • Thank you received: 9
  • Karma: 3
Сам алгоритм случайного обстрела по функции определения координат F(X,Y)=10*rand() можно заменить известным алгоритмом обхода коня доски.
Возможно, результаты такого просеивания будут лучше.
...не мы первые, не мы последние...
Last Edit: 09 Фев 2020 11:39 by Andralex.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1257
  • Thank you received: 23
  • Karma: 3
Andralex wrote:
Сам алгоритм случайного обстрела по функции определения координат F(X,Y)=8*rand() можно заменить известным алгоритмом обхода коня доски.
Возможно, результаты такого просеивания будут лучше.

Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.
Сам себе доктор наук
Moderators: Grigoriy
Рейтинг@Mail.ru

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