?

Log in

No account? Create an account
burtsev [entries|archive|friends|userinfo]
burtsev

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Получил от детей задачу [Oct. 7th, 2014|03:55 am]
burtsev
Есть клетчатое поле 5х13. Надо посадить на нем как можно больше тростника. В каждой клетке или тростник, или вода. Тростниковая клетка должна граничить через сторону хотя бы с одной водяной.
Для майнкрафта нужно.
LinkReply

Comments:
[User Picture]From: sorotokin
2014-10-07 02:22 pm (UTC)
Лучшее что у меня пока получилось - 16 клеток воды
(Reply) (Thread)
[User Picture]From: sorotokin
2014-10-07 02:28 pm (UTC)
Ещё легко доказать что меньше 15 не сделаешь.
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-07 11:39 pm (UTC)
Я сумел найти только 17...
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-08 03:23 am (UTC)
Не, стал рисовать - одна дырка осталась. Не получается 16.
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-08 04:52 pm (UTC)
Дырка была в центре? (А то как ты ее не заметил, одну, или у тебя решение "несимметричное"?
У нас решение простое: 2-3-2-3-2-3-2.
(Reply) (Parent) (Thread)
From: (Anonymous)
2014-10-08 04:59 pm (UTC)
Ну да 2-3-...-2 я тоже, понятно, нашел. 17 можно и кучей несимметричных решений получить, и мне показалось что и 16 тоже можно. Дырка была как раз с краю.

Вообще, надо программу написать (это кстати не так просто, как кажется, т.к. тупой перебор слишком медленный).
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-08 10:31 pm (UTC)
Одно из несимметричных:

O...O.O...O.O
..O.....O....
O....O....OO.
...O...O.....
.O...O...O..O


17 улучшить не выходит.
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-09 12:16 am (UTC)
Ага, я проверил))

5x13

жж png не показал, gif испортил, jpg-300 точек нерезкий, попробовал еще ссылку из фотоальбома:



Edited at 2014-10-09 12:47 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: lepestriny
2014-10-08 11:57 am (UTC)
У меня тоже 17
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-08 04:49 pm (UTC)
Теперь задание 7х13. Боюсь, придется в конце концов общий ответ давать)))
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-08 10:28 pm (UTC)
Искусственный интеллект говорит 22. Вручную не пытался.
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-08 10:34 pm (UTC)
.O...O.O...O.
...O.....O...
O.....O.....O
..O.O...O.O..
O.....O.....O
...O.....O...
.O...O.O...O.


выдели, чтобы увидеть
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-09 12:40 am (UTC)
А что он говорит про 13х13?
Я для 7х13 и 13х13 сравнивал "симметричный" ответ типа 2-3-2-3 с замощением "шахматным конем" и последующим исправлением на границе.
Получилось для 7х13 24 против 25, а для 13х13 уже кони выиграли 43 против 45.
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-09 01:42 am (UTC)
Result: water cells: 40
.O...O...O.O.
...O...O.....
O....O....O.O
..O.....O....
O...O.O....O.
..O......O...
O....O.O....O
...O......O..
.O....O.O...O
....O.....O..
O.O....O....O
.....O...O...
.O.O...O...O.


or this:

..O.O...O.O..
O.....O.....O
...O.....O...
.O...O.O...O.
...O.....O...
O.....O.....O
..O.O...O.O..
O.....O.....O
...O.....O...
.O...O.O...O.
...O.....O...
O.....O.....O
..O.O...O.O..
(Reply) (Parent) (Thread)
[User Picture]From: sorotokin
2014-10-09 01:47 am (UTC)
собственно, два склееных 7х13 как раз и дают 13х13. 22 + 22 - 4 = 40 (4 общие)
(Reply) (Parent) (Thread)
[User Picture]From: burtsev
2014-10-09 09:54 am (UTC)
Тут дело пахнет рекуррентной формулой. Правда я не понимаю, почему обязательно с краю 13 должно быть 4.
(Reply) (Parent) (Thread)