2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 31, 32, 33, 34, 35, 36, 37 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение25.06.2012, 08:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint в сообщении #588756 писал(а):
Вчера всю ночь квадраты снились.

Ага, а мне всю ночь снилось достраивание прямоугольников :D
Подробностей тоже не помню, но вот уже как будто получилось достроить прямоугольник 9х12 3-coloring до квадрата 13х13 4-coloring очень гармонично и надо было это срочно записать, но во сне, увы, записывать не умею :-)

-- Пн июн 25, 2012 09:49:53 --

Цитата:
Получилась слишком оптимистическая картина. По лемме есть возможность построить диагональное решение 10х10 для С=3, 18х18 для С=4, 28х28 для С=5.

svb
не пробовали построение диагонального решения C=5, N=28x28?
У вас по программе это должно быстро получиться (паче чаяния такое решение действительно существует), если для С=6, N=36x36 получилось мгновенно.

Ждём новый рекорд! :D

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


20/01/10
766
Нижний Новгород
Nataly-Mak в [url=http://dxdy.ru/post588735.html#p588735 писал(а):
svb
если вы разобрались с теоремой 4.12, скажите, пожалуйста:
какой из выложенных мной трёх вариантов прямоугольника 9х12 3-coloring построен по этой теореме?
Тогда я буду думать над достраиванием правильного варианта.
Если вы про формулировку, то там и переводить нечего - приведены формулы возможных прямоугольников. Доказательство основывается на лемме 4.11 и на существовании полей с числом элементов равным степени простого числа. Нас могут интересовать c=8,9,16. Я не стал разбираться, а попытался найти эти поля - кончилось тем, что для с=16 пришлось писать программку для получения таблиц сложения и умножения элементов поля. Далее написал простенькую программу формирования нужных нам квадратов для получения квадратов $c^2$ (для полей). Собрался было писать программу достраивания перебором, но удалось придумать и реализовать программно получение $c^2+c+1$ - этой ночью. Это дает 19.777562 при текущих рекордах, теперь начинается основное.

-- Пн июн 25, 2012 09:10:16 --

Цитата:
не пробовали построение диагонального решения C=5, N=28x28?
- откуда вы взяли, что это возможно?

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


21/02/10
1594
Екатеринбург
svb в сообщении #588761 писал(а):
откуда вы взяли, что это возможно?

Тут немного пофлеймили, поэтому мои посты затерялись
post588417.html#p588417
post588744.html#p588744

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


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #588763 писал(а):
Тут немного пофлеймили, поэтому мои посты затерялись
post588417.html#p588417
post588744.html#p588744
Увы, если ломать диагонали - а именно для этого случая я делал перебор - то 25 это максимум. Если же их не ломать, то ситуация с перебором, боюсь, выскочит за пределы возможного :-(

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #588739 писал(а):
dimkadimon в сообщении #588736 писал(а):
...но Pavlovsky описал и объяснил теорему 4.12 ещё в самом начале. Эта теорема описывает как строить C^2 x C^2 С-coloring когда С простое число.
Нужно числа от 1 до С^2 разбить на С групп по С чисел и сделать это С раз так что любая пара чисел встречалась не более чем в одной группе.

Вот это мне не надо объяснять!
Построение квадрата C^2xC^2 C-coloring для С простых я давным-давно поняла, все эти квадраты построила и отправила на конкурс.

Теперь речь совсем о другом! О построении прямоугольника С^2+C C-coloring.
Вы хоть вникли в то, о чём я прошу svb???

Вы получили подсказку и радуйтесь. Кстати, вообще говоря, Pavlovsky нарушил правила конкурса. Он не имел права давать вам явную подсказку.
А я не прошу никаких подсказок. Я прошу нормальный перевод теоремы 4.12 на русский язык. Это не является подсказкой! Вам понятно?


Построение прямоугольника С^2+С основано на построении С^2. Если вы поняли как строить С^2 по 4.12 то остался всего лишь один шаг до (С^2+С) х С^2. Если точнее то вам осталось найти ещё одно разбиение...

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

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


20/01/10
766
Нижний Новгород
Pavlovsky
Хотя ... можно будет потом посмотреть :-)

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


21/02/10
1594
Екатеринбург
svb в сообщении #588768 писал(а):
Увы, если ломать диагонали - а именно для этого случая я делал перебор - то 25 это максимум


Я рассматриваю все 2n-1 диагонали. Требование расскрашивать ломанные диагонали (полученные циклическим сдвигом) в один цвет, на мой взгляд, слишком надуманое. Разве что перебор сокращается.

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


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #588774 писал(а):
Я рассматриваю все 2n-1 диагонали. Требование расскрашивать ломанные диагонали (полученные циклическим сдвигом) в один цвет, на мой взгляд, слишком надуманое. Разве что перебор сокращается.
Вы правы. Когда я увидел какой-то диагональный квадрат, который приводила Наталия, то мне бросилась в глаза раскраска, не соответствующая ломаным диагоналям. При ломаных диагоналях приходится накладывать дополнительные условия, что очень сильно уменьшает перебор, но и число возможных квадратов резко сужается.

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


21/02/10
1594
Екатеринбург
А насчет перебора, есть много разных способов. Например проблема 28х28 для С=5. У меня есть раскраска 12 диагоналей одним цветом. Осталось расскрасить оставшиеся 55-12=43 диагонали в 4 цвета. То есть по 11 диагоналей на один цвет (одним цветом 10 диагоналей). Задача вполне реальная. К тому же различных раскрасок диагоналей в один цвет на самом деле не так много. Пусть у нас есть раскраска диагоналей (a1,...ak), где a1,..,ak номера диагоналей. Тогда раскраска (a1+d,...ak+d) тоже корректная. Зеркальное отражение раскраски диагоналей, тоже корректное. Анализ показывает достаточно двух видов раскрасок, которые начинаются (1,2,4,...) и (1,3,4,...) эти раскраски прекрасно вкладываются друг в друга.

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


22/03/08

7154
Саратов
Цитата:
Построение прямоугольника С^2+С основано на построении С^2. Если вы поняли как строить С^2 по 4.12 то остался всего лишь один шаг до (С^2+С) х С^2. Если точнее то вам осталось найти ещё одно разбиение...

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

Блин!!!
Я же сказала, что умею строить прямоугольники (С^2+С) х С^2! Привела здесь такие прямоугольники 9х12 3-coloring, 25x30 5-coloring.
Похоже, вы совсем не понимаете по-русски. Я вам уже трижды всё пояснила, а вы опять повторяете то же самое.

Да, я поняла, как строить C^2 по объяснению Pavlovsky.
Это тут уже 5 раз написала!
Вы читать будете мои сообщения???

Какой ещё один шаг мне остался?

Мне остался один шаг - это достраивание прямоугольника (С^2+С) х С^2 С-coloring до квадрата С^2+C+1 (C+1)-coloring.

Вот как делать достраивание - этот один шаг - я не знаю.
Если вы хотите мне помочь (в чём я очень сильно сомневаюсь), тогда дайте ответ на мой вопрос: правильно ли я построила прямоугольники (С^2+С) х С^2!

Что вы мне объясняете, как строить прямоугольники, если я их уже построила?
Ещё раз специально для вас повторяю:
я не знаю, соответствуют ли мои прямоугольники алгоритму теоремы 4.12.

Цитата:
...на некоторые ваши вопросы уже ответили (может частично), но вы эти ответы не заметили вот и всё.

Приведите пример такого ответа, который я не заметила!

-- Пн июн 25, 2012 11:55:10 --

Вот прямоугольник 81х90 9-coloring:

Изображение

Повторяю вопрос, специально для dimkadimon, а также и для svb, потому что в его посте я не увидела ответ на свой вопрос:

этот прямоугольник соответствует алгоритму теоремы 4.12??

Я легко могу построить и следующие прямоугольники, для С=11 121х132, для С=13 169х182 и т.д.

Но не умею пока эти прямоугольники достраивать до квадратов.

И ещё раз повторюсь (это важно!): Pavlovsky тут делал замечание, что прямоугольники должны быть построены именно по алгоритму теоремы 4.12.
А я их строю по-своему.

-- Пн июн 25, 2012 12:06:07 --

svb в сообщении #588761 писал(а):
Если вы про формулировку, то там и переводить нечего - приведены формулы возможных прямоугольников. Доказательство основывается на лемме 4.11 и на существовании полей с числом элементов равным степени простого числа. Нас могут интересовать c=8,9,16. Я не стал разбираться, а попытался найти эти поля - кончилось тем, что для с=16 пришлось писать программку для получения таблиц сложения и умножения элементов поля.

Как я понимаю, вы не знаете ответ на мой вопрос: соответствуют ли построенные мной прямоугольники C^2x(C^2+C) алгоритму теоремы 4.12.

Pavlovsky писал, что эти прямоугольники должны быть построены по алгоритму именно этой теоремы.

Значит, вы не разбирались в этой теореме и решили задачу по-своему. Правильно понимаю?

Конечно же, меня интересует не формулировка теоремы :D Что утверждает теорема, я вроде как поняла.
Меня интересует её доказательство, так как именно в доказательстве (как я предполагаю) и есть тот самый алгоритм.

Ну, спасибо хотя бы за отклик.
Заодно похвалились своими успехами.
Значит, джентльменский набор решений вы тоже получили :D

-- Пн июн 25, 2012 12:18:49 --

Вот они - джентльмены :D

Код:
6  Tom Sirgedas 19.777600 06-07-2012 @ 07:11:18
7  Il brigante Pennastorta 19.777600 06-08-2012 @ 16:28:33
8  Valery Pavlovsky 19.777600 06-15-2012 @ 11:02:58

Плюс svb.

Интересно, сколько таких джентльменов будет к концу конкурса. Думаю, что немало.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #588784 писал(а):
Pavlovsky писал, что эти прямоугольники должны быть построены по алгоритму именно этой теоремы.


Осторожно подсказка удалена!

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


22/03/08

7154
Саратов
Подсказку не открывала!! Честное слово! :D
А вы кому подсказываете-то? Надеюсь, что не мне :wink:

Вот формулировка теоремы 4.12

Код:
Theorem 4.12
Let p be a prime and s, d ∈ N.
1. Gpds,
pds−1
p−1
is strongly pds−s
-colorable.
2. Gpds,
pds−1
p−1 pds−s is pds−s
-colorable.

Извиняюсь за плохую копию, но лучше не получается.

А это перевод, сделанный в Google

Цитата:
теорема 4.12 Пусть р-простое число, S, D ∈ N. 1. ГФД, PDS-1 Р-1 сильно PDS-х годов -раскрашиваем. 2. ГФД, PDS-1 р-1 PDS-S PDS-х годов -раскрашиваем.

:D

Толковый перевод, не правда ли?
По такому переводу даже будучи семи пядей во лбу понять что-либо абсолютно невозможно.

Но я формулировку теоремы поняла без перевода.

-- Пн июн 25, 2012 12:38:13 --

Pavlovsky в сообщении #588794 писал(а):
Осторожно подсказка удалена!

Вот и отлично!
Мне не нужны ваши подсказки. Я больше не читаю спрятанных текстов.

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


22/03/08

7154
Саратов
Диагональное решение C=5, N=26x26 :D

Изображение

Хи-хи...
Не пугайтесь, решение с ошибками. 206 ошибок.
Взяла диагональное решение C=5, N=20x20 и просто продолжила его до квадрата 26х26.

-- Пн июн 25, 2012 14:45:08 --

Довольно быстро удалось свести количество ошибок к 123 (вручную в программе Эда).
Обратите внимание: диагональность испортилась совсем немного.

Изображение

Вполне возможно, что диагональное решение C=5, N=26x26 существует.

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


22/03/08

7154
Саратов
Диагональное решение C=4, N=18x18, 102 ошибки:

Изображение

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


22/03/08

7154
Саратов
Решение С=4, N=7x7 "ход конём"

Изображение

Интересно, для каких C и N существуют решения "ход конём"?
Такие решения очень просто составлять.

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

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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