2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 09:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #589173 писал(а):
Если все получится, буду искать решение 40х40 для С=6. В квадрате 40х40 раскрасить 28 диагоналей в два цвета возможно. Остается окрасить оставшиеся 79-28=51 диагонали в четыре цвета.

Очень реально, что существует решение для C=6 больше, чем N=36x36.
У меня очень быстро достроился из моего решения прямоугольник 37х36 6-coloring. Но пристроить ещё столбец вручную не получилось.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 10:04 
Аватара пользователя


21/02/10
1594
Екатеринбург
alexBlack в сообщении #589166 писал(а):
По крайней мере для одного вида решений для простых C очевидно, что при добавлении одного цвета можно увеличить размер на (C+1). Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу.


Так Алексей начал колоться, а ведь мы еще не использовали утюг и паяльник. :D

У меня уже появились идеи как к оценке С^2-C+1 добавить еще единицу, надо вечером попробовать.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 10:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack в сообщении #589166 писал(а):
Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу.

Я об этом давно догадывалась, что такое расширение возможно.
Вот:

Цитата:
Если я правильно поняла приведённую выше формулу, она даёт:

C=12, N=133x133
C=14, N=183x183
C=18, N=307x307
C=20, N=381x381

Все полученные результаты на 1 больше.
Получается вроде того: все полученные по известному алгоритму квадраты как-то расширяются на 1.

То есть совсем не надо долго "трясти" решение для C=10, N=91x91, чтобы получить из него решение N=92x92. Делается это как-то очень красиво.

Тогда на моё сообщение никто не обратил внимания.
Только dimkadimon ответил: "Вы правильно поняли формулу, но есть исключения".
Оказывается, это совсем даже не исключения! :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 10:12 
Аватара пользователя


21/02/10
1594
Екатеринбург
Возникает новый джентельменский набор.
1) Взять готовые результаты для (С=2,3,4).
2) Найти решение 36х36 для (С=6).
3) Реализовать алгоритм для С простых чисел (С=5,7,11,13,17,19).
4) Реализовать алгоритм для С, являющихся степенью простого числа (С=8,9,16).
5) Реализовать алгоритм C=p^k+1, p - простое число в степени, k>=1 с оценкой С^2-С+2 (С=10,12,14,18,20).
6) Получить решение для С+1, с оценкой F(С)+1, где F(C) решение для С (С=15,21).

При текущих рекордах получается 19,8509 балла.
Цитата:
4 Nick Gardner 19.850900 06-21-2012 @ 17:41:06

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 10:15 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #589191 писал(а):
5) Реализовать алгоритм C=p^k+1, p - простое число, k>=1 с оценкой С^2-С+2 (С=10,12,14,18,20).

Да, да, именно пункт 5 и был "зашит" в моём давнишнем сообщении :-)

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 10:51 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #589161 писал(а):
dimkadimon в сообщении #589157 писал(а):
А можно я тоже буду считаться россиянином? Всё таки я родился в Москве и говорю по русски :)


Австралийцем быть прикольнее. Хочу в Австралию. Ведь там живут антиподы (Алиса в стране чудес).


Да ну может быть :) Австралия действительно классное место. Если вы когда-нибудь сюда собирётесь то сообщите и мы встретимся.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 11:43 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот это достраивание мне точно снилось во сне :D

Изображение

Именно оно - вполне гармоничное.
Решение родилось в творческих муках, во сне и наяву :roll:

Ох! А для С=9 я вообще не знаю, как делать разбиения :-(
Придётся попробовать сначала решение для C=11, с этим проще, оно простое число. Знаю, как делать разбиения.

Надо ещё и для C=5 сделать, для порядка и для опыта.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 12:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И вот оно решение C=6, N=31x31, очень красивое!

Изображение

Уф! С замиранием души приступаю к решению для C=12 :D
Решение для С=10 пока пропускаю, т.к. не умею для C=9 делать разбиения.

Кстати, интересно: можно ли достроить это решение 31х31 до решения 36х36?
Тут есть нечто красивое (не просто "потрясти")?
Полученное мной раньше решение 31х31 (точнее: 31х36) я достроила до 36х36 вручную в программе Эда. Получилось весьма симпатичное решение.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 13:44 
Аватара пользователя


21/02/10
1594
Екатеринбург

(Оффтоп)

Наталия может скроете картинку в оффтопик. Во-первых решение само по себе 31х31 приличное. Во-вторых явно виден алгоритм достраивания.


-- Вт июн 26, 2012 15:49:40 --

Наталия, офрмительский совет. В программе Эда есть галочка sub-grids. Можно красиво разбить квадрат на подквадраты.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 18:17 


26/01/10
959
Nataly-Mak в сообщении #589244 писал(а):
И вот оно решение C=6, N=31x31, очень красивое!

Есть значительно красивее. Могу потом показать.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 19:24 
Аватара пользователя


21/02/10
1594
Екатеринбург
Чего то туплю. Помогите. Надо заполнить прямоугольник 5х9 максимальным количеством единичек. Чтобы не было запрещенных прямоугольников.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 19:39 


26/01/10
959
Pavlovsky в сообщении #589398 писал(а):
Чего то туплю. Помогите. Надо заполнить прямоугольник 5х9 максимальным количеством единичек. Чтобы не было запрещенных прямоугольников.

Вручную у меня больше 16 не получается. А что, перебором не получается?

-- Вт июн 26, 2012 19:41:20 --

Zealint в сообщении #589402 писал(а):
Вручную у меня больше 16 не получается.

18 сделал

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 19:51 
Аватара пользователя


21/02/10
1594
Екатеринбург
Zealint в сообщении #589402 писал(а):
18 сделал

Я тоже сделал 18! Оказывается достаточно написать, чтобы проблема решилась. :-)

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 19:52 


26/01/10
959
Zealint в сообщении #589402 писал(а):
18 сделал

(Больше не получается)

Метод убывающих семёрок:

Код:
111100000
000111100
001000111
010001001
100010010


-- Вт июн 26, 2012 19:52:48 --

Pavlovsky в сообщении #589406 писал(а):
Я тоже сделал 18! Оказывается достаточно написать, чтобы проблема решилась.

Надо только доказать, что больше нельзя.

-- Вт июн 26, 2012 20:00:02 --

Pavlovsky в сообщении #589406 писал(а):
Оказывается достаточно написать, чтобы проблема решилась.

Да? Дайте-ка я напишу... Чего то туплю. Помогите. Надо заполнить прямоугольник 100х100 десятью цветами. Чтобы не было запрещенных прямоугольников.

-- Вт июн 26, 2012 20:01:42 --

Что-то не решается : )

-- Вт июн 26, 2012 20:12:23 --

Диагонального решения для 17x17, C=4 тоже не существует.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 20:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Великолепная мозаика!

Изображение

Ещё раз огромное спасибо Эду за программу!
Такая красота! Любуюсь, любуюсь... :roll:

Кстати, в этой мозаике есть нечто диагональное и даже пандиагональное (наличие разломанных диагоналей).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group