 |
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 97039
- Thank you received: 1702
-
Karma: 100
-
|
Гораздо супрематичнее, чем у Малевича
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
Sam Sebe wrote:
Чего никто не оценит мой супрематизм? 
Нет, внимательно наблюдаем.
На диаграммах, где змейка меняют направление, встречаются случаи углового касания.
Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?
В случаях с разомкнутыми змейками появляется закономерность. К каждому из четырёх боков примыкает одна фигура, состоящая из белых клеток. На рисунке это: с юга - линия из трёх клеток; с запада - одна клетка; с севера - тоже трёхклеточная линия; с востока - двухклетка.
Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.
Возможно ли вывести общую формулу подсчёта максимально допустимых закрашенных клеток при другой размерности доски?
Доска 1*1 = 1 закрашенная клетка;
Доска 2*2 = 3 клетки;
Доска 3*3 = 7 клеток;
Доска 4*4 = 11, и т.д.
|
...не мы первые, не мы последние...
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
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.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Andralex wrote:
На диаграммах, где змейка меняют направление, встречаются случаи углового касания.
Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?
Вот, нашел это распределение.
Эти 108 + 8 змеек (исчерпывающее число) максимальной длины (42 клетки) стартуют в 1-м квадранте, и 16 из них в нем же финишируют, т.е. 8 змеек учитываются дважды: в одном направлении и в другом. Случаев касания, оказывается, не от 2 до 6, а от 5 до 8.
|
Last Edit: 02 Фев 2020 19:21 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Вот еще вдогонку распределение змеек по числу изломов.
|
Last Edit: 03 Фев 2020 10:31 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Andralex wrote:
Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.
Кстати, хорошая наводка. Сколько существует различных начальных расстановок кораблей в классическом Морском бое?
Поле 10х10, один линкор (4-клеточный), два крейсера (3-кл.), три эсминца (2-кл.) и четыре катера (1-кл.). Касания и изломы не допускаются.
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Sam Sebe wrote:
Сколько существует различных начальных расстановок кораблей в классическом Морском бое?
Поле 10х10, один линкор (4-клеточный), два крейсера (3-кл.), три эсминца (2-кл.) и четыре катера (1-кл.). Касания и изломы кораблей не допускаются.
Вопрос оказался интересным. Ответить на него я пока не смог, зато возникли другие интересные вопросы.
Возьмем произвольную расстановку. Корабли и запретные зоны вокруг них (корабли не касаются друг друга) заполняют какое-то количество клеток игрового поля. Но некоторые клетки остаются незаполненными. Спрашивается, каково минимальное возможное число этих незаполненных клеток и то же максимальное? В частности, можно ли заполнить все игровое поле без остатка или, наоборот, оставить незаполненной, скажем, его половину? Как вы считаете? Я рассмотрел 1 миллион случайных расстановок (возможно, совпадающих: я не следил) и в его пределах ответы знаю.
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
Оставить половину можно, для этого надо постараться компактно втиснуть.
▄▄▄ ▄▄ ▄▄▄ 3+1+ 2+1+ 3=10
▄▄ ▄▄ ▄▄ ▄ 2+1+ 2+1+ 2+1+ 1=10
▄▄▄▄ ▄ ▄ ▄ 4+1+ 1+1+ 1+1+ 1=10
В игре такую расстановку не применять! Противник сходу просечёт поляну потопит все корабли.
|
...не мы первые, не мы последние...
Last Edit: 04 Фев 2020 14:11 by Andralex.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
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
В игре такую расстановку не применять! Противник сходу просечёт поляну потопит все корабли. 
Нет, это было бы чересчур просто, это всегда 80 пустых клеток. В вопросе спрашивается про заполнение не только собственно корабельных клеток, но и зон вокруг них. Например, линкор - это не только 4 его клетки, но и, в худшем случае, еще 14 клеток вокруг.
|
Last Edit: 04 Фев 2020 14:28 by Sam Sebe.
|
-
Хайдук
-
-
NOW ONLINE
-
Наместник
-
- Posts: 45062
- Thank you received: 108
-
Karma: 22
-
|
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Вот какого вида заполнения имеются в виду. Здесь незаполненными остались 1 клетка и 37 клеток.
А про выигрышные расстановки я еще скажу.
|
Last Edit: 04 Фев 2020 15:38 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
А вот какое распределение
1 миллиона случайных расстановок
соответствующее получилось.
Кстати, 37/100 - это 1/e, можно сказать.
|
Last Edit: 04 Фев 2020 15:41 by Sam Sebe.
|
-
инфолиократ
-
|
Т.е. ТАКИ
1. точно - случайность - непознанная закономерность?
2. очевидно (объективно, трояко): есть начало таблицы, есть середина...
3. субъективно, жаль что
Число, которое считаю "моё" 23- в нижней половине получилось.
З павагай да неабыякавых
Зы. Целиком и полностью полагаясь на ваше усмотрение, ув. Sam Sebe, не вычислите ли сумму всех усеченных гармонических рядов (без 1, без 2-х, без ТРЕХ цифр) и не определите ли № конечного слагаемого ГР, обеспечивающего ТОЧНО ТАКУЮ ЖЕ СУММУ? А вдруг полученныое требуемое число слагаемых Гармонического ряда ТОЧНО совпадет с числом, которое называл СергеП для вселенсконатурального7. З павагай, паклонам
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Оптимизировал программу, и она стала считать в 10 раз быстрее, так что тот же миллион случайных расстановок кораблей получился за 6 минут. Распределение по числу незаполненных (за вычетом кораблей и примыкающих к ним клеток) похожее.
Вот две крайние расстановки из найденных: одна полностью (о=0) заполняет игровое поле, а другая - по минимуму (о=38).
Кстати, 38 : 62 - это золотое сечение. Подозреваю, 62 заполненные клетки из 100 - это действительно минимум. Впрочем, теперь реально рассмотреть и целых 10 миллионов расстановок.
|
Last Edit: 06 Фев 2020 13:46 by Sam Sebe.
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
А если зеленый трехпалубник из центра (o=38) подвинуть вправо на край доски? Чёрных клеток станет больше.
|
...не мы первые, не мы последние...
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Да, правильно, на 4 штуки. Значит, не золотое сечение. Очень жаль. Ладно, сейчас на 10 миллионах проверим.
А еще и одну-две красные можно подвинуть.
|
Last Edit: 06 Фев 2020 13:56 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Sam Sebe wrote:
Ладно, сейчас на 10 миллионах проверим.
Чуть лучше (о=39), но все равно не минимум.
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Интересную вещь заметил. Если уменьшить игровое поле до 9х9, то при последовательной (линкор - крейсера - эсминцы - катера), но случайной расстановке кораблей примерно в одном из 300-400 случаев осуществить ее не удается: не всем катерам хватает места (бывает даже, что только одному хватает). А вот на поле 10х10 такого не случается, т.е. набор кораблей для него как бы оптимален.
|
Last Edit: 06 Фев 2020 19:21 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
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.
|
-
инфолиократ
-
|
Andralex wrote:
А если зеленый трехпалубник из центра (o=38) подвинуть вправо на край доски? Чёрных клеток станет больше. А если поменять его с левым угловым двухпалубником?
З павагай да неабыякавых
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
Sam Sebe wrote:Но в таком виде случайную расстановку кораблей удается осуществить только 96-97 % случаев - в этом смысле такой набор кораблей для поля 10х10 является неестественным, избыточным.
Дополнение.
В настоящее время, имея под рукой компьютеры, не составит труда рассчитать оптимальное количество кораблей на доске N*N. Так, чтобы было не тесно,-- тогда быстро игра закончится, но и не просторно,-- тогда игроки от постоянных бультыханий снарядов в воду просто впадут в унылость.
Но, игра морской бой известна ещё до начала повальной компьютеризации.
Возникает вопрос: как же так высчитали идеально?
Ответ: постепенно и опытным путём. Так же как и шахматы за тысячи лет обтесались др идеала.
|
...не мы первые, не мы последние...
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
инфолиократ wrote:
А если поменять его с левым угловым двухпалубником?
И вообще, если каждый корабль имеет вокруг себя нейтральную зону из клеток, то часть этой зоны (одного борта) можно просто убрать, поместив корабль на край доски. В итоге, высвободится лишнее место для свободных клеток.
|
...не мы первые, не мы последние...
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Выигрышная стратегия в "Морской бой" описана в Википедии. Если коротно, то все корабли, кроме катеров, надо собрать в одну кучу, чтобы оставить для катеров площадь побольше, где их трудно будет найти. Правда, мне это несколько сомнительно: вдруг противник быстренько (коль скоро ход не передается) перебьет всю кучу и возьмется за катера, а я еще ничего не успею.
Вот, рассмотрел 1 млн расстановок без катеров, чтобы найти для последних максимально возможную площадь размещения.
Получилось, что max = 60, но расстановка такая нашлась всего одна. И она "полукомпактная", т.е. 3 корабля прижаты к одному краю и 3 к противоположному, а 60 клеток в центре остаются незанятыми (чтобы равномерно разместить там катера).
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
вдруг противник быстренько (коль скоро ход не передается) перебьет всю кучу и возьмется за катера, а я еще ничего не успею. Для таких случаев особо хитрые игроки в начале рисуют не десять, а девять кораблей, и одноклеточный катер в самом конце игры, в последний момент.
|
...не мы первые, не мы последние...
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Нашел еще несколько расстановок с о=60, некоторые их них совпадают. Все они такие: корабли прижимаются или к одному краю игрового поля, или к двум противоположным краям, или к двум смежным, что неудивительно, поскольку всякий раз корабли расставлялись хоть и случайно, но так, чтобы примыкать к зонам уже расставленных кораблей и/или к краям игрового поля, а иначе достичь о=60 не удается.
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Andralex wrote:
Для таких случаев особо хитрые игроки в начале рисуют не десять, а девять кораблей, и одноклеточный катер в самом конце игры, в последний момент.
Ну это как бы для школьников, которым важно победить, а не просто убить время.
|
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Получил-таки 7 расстановок с о=44, все разные.
Это для набора из 10 кораблей, с катерами.
|
Last Edit: 09 Фев 2020 10:38 by Sam Sebe.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Теперь бы следовало проверить каждую найденную случайную расстановку на то, за сколько ходов удастся полностью ее уничтожить случайным обстрелом. Но, думаю, времени много потребуется.
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 1718
- Thank you received: 42
-
Karma: 10
-
|
Сам алгоритм случайного обстрела по функции определения координат F(X,Y)=10*rand() можно заменить известным алгоритмом обхода коня доски.
Возможно, результаты такого просеивания будут лучше.
|
...не мы первые, не мы последние...
Last Edit: 09 Фев 2020 11:39 by Andralex.
|
-
Sam Sebe
-
-
OFFLINE
-
Боярин
-
- Posts: 1309
- Thank you received: 28
-
Karma: 3
-
|
Andralex wrote:
Сам алгоритм случайного обстрела по функции определения координат F(X,Y)=8*rand() можно заменить известным алгоритмом обхода коня доски.
Возможно, результаты такого просеивания будут лучше.
Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.
|
|
|
|
 |