2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 21, 22, 23, 24, 25, 26, 27 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение19.06.2012, 11:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #586776 писал(а):
Здесь цифра 1 остается на месте, а все остальные цифры врашаются по кругу по часовой стрелке.

Да, действительно.

Но мне непонятно, к чему вообще "пришить" эти разбиения. Для чего они?

-- Вт июн 19, 2012 12:22:11 --

svb
Ага. Пойдём дальше :-)

Что там утверждается в следующей теореме 4.5?
А после неё как раз следуют весьма интересные разбиения.

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


20/01/10
766
Нижний Новгород
Теорема 4.5 - обобщение теоремы 4.4, формулировка почти такая же, только 1 заменяется на $c'$.

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


21/02/10
1594
Екатеринбург
И в чем польза теоремы 4.4?
Скажем для С=10 построите вы С-раскрашиваемый прямоугольник 11х450! Что вы с ним делать будете? Как из него получить квадрат 100х100?

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


22/03/08

7154
Саратов
svb
Теорему 4.5 тоже приблизительно понимаю.

А про разбиения скажете что-нибудь? :-)
К чему они? С чем их "кушать"?

Там написано примерно следующее: "сейчас мы приведём некоторые примеры...", это сразу после теоремы 4.5.

-- Вт июн 19, 2012 12:43:46 --

Pavlovsky в сообщении #586783 писал(а):
И в чем польза теоремы 4.4?

Не все йогурты теоремы одинаково полезны :D

Цитата:
Скажем для С=10 построите вы С-раскрашиваемый прямоугольник 11х450! Что вы с ним делать будете? Как из него получить квадрат 100х100?

Я уже говорила, что надо строить для C=10, или-или-или:

1. 100 непересекающихся комбинайций из чисел 1,2,3,...,10 (длины 10);
2. 100 комбинаций из тех же чисел, но длины 20 (разрешаются пересеченяи по числам 1,2);
3. 100 комбинаций из тех же чисел, но длины 50 (разрешаются пересечения по числам 1,2,3,4,5).

Это чтобы получить решение N=100x100.

В свете новой леммы Макаровой-Беляева можно строить и другие прямоугольники, к которым затем можно применить лемму 4.3 :D

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


21/02/10
1594
Екатеринбург
Теорема 4.5 не лучше. Согласно следствию, сможем для С=10 построить прямоугольник 20х190. Останется вычеркнуть из него 90 лишних колонок и добавить недостающие 80 строк и решение 100х100 готово!

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


22/03/08

7154
Саратов
Pavlovsky
я же вам сказала: пользуйтесь леммой Макаровой-Беляева, и всё получится просто на раз :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #586795 писал(а):
пользуйтесь леммой Макаровой-Беляева

В ближайшее время собираюсь порыть именно в этом направлении.

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


24/05/09

2054
Изображение

20x20 6 цветов. Результат конечно скромный, зато расцветочка элегантная - чистый рэндом без каких-либо формул!

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


22/03/08

7154
Саратов
Alexu007
если бы вы читали тему, увидели бы, что для C=6 элементарно получается решение N=26x26.
Вообще без ничего: ни формул, ни рэндома :D
Чисто использование одного хорошего свойства!
И раскраска намного симпатичнее рэндома.

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


22/03/08

7154
Саратов
Так никто ничего и не сказал про разбиения :cry:
Для чего они? Куда их "пришить"?
Почему именно для 2n=6 и 2n=8?

Pavlovsky сказал, что теоремы 4.4 и 4.5 в рассматриваемой статье бесполезные.
А какие полезные - не сказал :D

Так и придётся срочно выучить английский :?

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


24/05/09

2054
Nataly-Mak в сообщении #586939 писал(а):
Alexu007
если бы вы читали тему, увидели бы, что для C=6 элементарно получается решение N=26x26.
Вообще без ничего: ни формул, ни рэндома :D
Чисто использование одного хорошего свойства!

Я очень ленив. Мне лень читать 24 стр. темы и мне тем более лень вручную получать решение, даже элементарно и даже с использованием некоего хорошего свойства. Тем более, что оно скорее всего работает для одной конкретной комбинации, и не поможет ни в каком другом случае.

За меня же работает компьютер.

Цитата:
И раскраска намного симпатичнее рэндома.

Дело вкуса.

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


22/03/08

7154
Саратов
Alexu007 в сообщении #587011 писал(а):
Тем более, что оно скорее всего работает для одной конкретной комбинации, и не поможет ни в каком другом случае.

Нет, вы ошибаетесь. Это хорошее свойство работает для многих случаев!

А лень - это очень плохо. На ней вы далеко не уедете :D где сядете, там и слезете.
Интересно, а книги за вас тоже компьютер читает?

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #587039 писал(а):
А лень - это очень плохо. На ней вы далеко не уедете :D где сядете, там и слезете.
Интересно, а книги за вас тоже компьютер читает?


Кстати насчет лени... а почему бы вам не написать программу которая проверяет решения на правильность. Ета программа всего несколько строчек (7) и она уже есть на сайте в разделе Code.

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


22/03/08

7154
Саратов
А потому что я не хочу писать программы, которые мне не нужны и писать которые мне неинтересно.
(Ха! Ну и что интересного в программе проверки правильности??? Ну, да 7 строчек. Организовать циклы, по всем строкам, по всем столбцам квадрата (прямоугольника) и проверять одинаковость цветов во всех вершинах внутренних прямоугольников.)

Как я уже говорила, программа проверки правильности мне абсолютно не нужна!
Все составленные мной решения я проверяю в программе Эда или прямо на конкурсе.

Ещё вопросы есть?

Уж не хотите ли вы обвинить меня в лени?
Достаточно посмотреть мой сайт, чтобы устыдиться подобного обвинения!

Сейчас я собираюсь писать статью о конкурсной задаче.
Мне абсолютно неинтересно писать программы перебора, что-то ещё вымучивать. Я удовлетворена теми результатами, которые получила.

Да, мне интересны решения, основанные на математических идеях. Пока я все их не знаю. Может быть, и не узнаю. Но всё знать невозможно!

Мне, например, было интересно составлять прямоугольник strong-(6,2)-coloring, чтобы потом применить к этому прямоугольнику лемму 4.3. Я написала для этой задачки простенькую программку. Нашла прямоугольник 7х12. Кстати, очень удачно ошиблась! Получила интересный результат. Но об этом тут уже подробно написано.

Вот это мне интересно. А вымучивать решения перебором - это скучно.

[я пишу переборные программы для построения магических квадратов, но там не тупой перебор, там есть разработанные мной алгоритмы; тупой перебор мне абсоолютно неинтересен]

Мне интересны вспомогательные задачи. Я поставила несколько таких задач: об уникальных перестановках, о непересекающихся комбинациях. Поставила и здесь, и ещё на одном форуме (nazva.net, ссылку на этот форум давала в теме "Уникальные перестановки").
Мне интересны закономерности, я люблю математическую гармонию.
Выше я приводилп головоломку с непересекающимися комбинациями из чисел 1,2,3,...,10.
Почему-то здесь она не вызвала никакого интереса.
Я решить её не смогла. А на форуме nazva.net её блестяще решили.

Вы тут приводили набор из 32 непересекающихся комбинаций из чисел 1,2,3,...,10. Я не увидела в ваших комбинациях никакой закономерности, по-моему, числа расположены в комбинациях хаотично. Скорее всего, комбинации найдены перебором или перебором плюс случайная генерация.
А вот теперь посмотрите на то решение, которое искала я:

Код:
1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2
1 3 3 3 3 3 3 3 3 3
1 4 4 4 4 4 4 4 4 4
1 5 5 5 5 5 5 5 5 5
1 6 6 6 6 6 6 6 6 6
1 7 7 7 7 7 7 7 7 7
1 8 8 8 8 8 8 8 8 8
1 9 9 9 9 9 9 9 9 9
1 10 10 10 10 10 10 10 10 10
2 1 2 3 4 5 6 7 8 9
2 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 1
2 4 5 6 7 8 9 10 1 2
2 5 6 7 8 9 10 1 2 3
2 6 7 8 9 10 1 2 3 4
2 7 8 9 10 1 2 3 4 5
2 8 9 10 1 2 3 4 5 6
2 9 10 1 2 3 4 5 6 7
2 10 1 2 3 4 5 6 7 8
3 1 3 10 9 8 5 6 2 5
3 2 4 1 10 9 6 7 3 6
3 3 5 2 1 10 7 8 4 7
3 4 6 3 2 1 8 9 5 8
3 5 7 4 3 2 9 10 6 9
3 6 8 5 4 3 10 1 7 10
3 7 9 6 5 4 1 2 8 1
3 8 10 7 6 5 2 3 9 2
3 9 1 8 7 6 3 4 10 3
3 10 2 9 8 7 4 5 1 4
4 1 10 9 7 4 8 8 4 4
4 2 1 10 8 5 9 9 5 5
4 3 2 1 9 6 10 10 6 6
4 4 3 2 10 7 1 1 7 7
4 5 4 3 1 8 2 2 8 8
4 6 5 4 2 9 3 3 9 9
4 7 6 5 3 10 4 4 10 10
4 8 7 6 4 1 5 5 1 1
4 9 8 7 5 2 6 6 2 2
4 10 9 8 6 3 7 7 3 3
5 1 9 8 10 7 7 3 7 8
5 2 10 9 1 8 8 4 8 9
5 3 1 10 2 9 9 5 9 10
5 4 2 1 3 10 10 6 10 1
5 5 3 2 4 1 1 7 1 2
5 6 4 3 5 2 2 8 2 3
5 7 5 4 6 3 3 9 3 4
5 8 6 5 7 4 4 10 4 5
5 9 7 6 8 5 5 1 5 6
5 10 8 7 9 6 6 2 6 7

Здесь 50 непересекающихся комбинаций. Какая красивая закономерность! Вот это мне нравится!
Конечно, для решения конкурсной задачи мне это ничего не даёт, так как тут всего решение N=50x50.
Точнее: тут решение 50х100. Ровно половина квадрата 100х100.
Но какое красивое решение!
Выше я приводила решение 72х144 12-coloring, полученные из уникальных перестановок. Тоже очень красивое решение.

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

-- Ср июн 20, 2012 07:29:51 --

dimkadimon
а что вы можете сказать о тех разбиениях, о которых я здесь спрашивала вчера и ещё раньше?
Мне очень интересно, для чего в статье приведены эти разбиения. К чему их можно применить?

(речь идёт о самой первой статье в списке литературы на главной странице конкурса)

Вот перевод этого фрагмента статьи, сделанный в Гугле:

Цитата:
Для доказательства теоремы 4.5, мы будем использовать раздел [2n] 2 в совершенные паросочетания в [2П] для определенных значениях л. Каждое полное совпадение, следовательно, имеет размер н. Сначала мы приведем несколько примеров, а затем общей леммы. Пример 4.6 1. Если п = 3, 2n = 6, 2n - 1 = 5. Мы покажем разбиение [6] 2 на 5 частей размером 3. мы Первая пара на элементы, как следует, каждый номер в верхнем ряду сопряжения с Число ниже: 1 2 3 6 5 4 Это соответствует {1, 6}, {2, 5}, {3, 4}. Это наша первая часть размером 3. Мы продолжаем 1 фиксированный и сохранить вращение по часовой стрелке, другие номера, чтобы получить следующие частей.
1 6 2
5 4 3
1 5 6
4 3 2

1 4 5
3 2 6
1 3 4
2 6 5
Отметим, что первая пара пошла {1, 5}, {1, 4}, {1, 3}, {1, 2}. То есть, 1 была установлена, но
других элементов уменьшается на 1. Также отметим, что вторая и третья пары были и
элементов уменьшается на 1, за исключением 2 идет до 6. Этот раздел представляет собой частный случай общего
Строительство у нас будет позже. То же самое относится к следующему примеру.

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

И вот уже в третий раз я задаю вопрос об этих разбиениях, а в ответ... тишина.

Что, никто не знает ответ? Или наоборот: все знают, но сказать не хотят :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #586963 писал(а):
Так никто ничего и не сказал про разбиения Для чего они? Куда их "пришить"?Почему именно для 2n=6 и 2n=8?Pavlovsky сказал, что теоремы 4.4 и 4.5 в рассматриваемой статье бесполезные.А какие полезные - не сказал


Теоремы 4.4 и 4.5 позволяют строить низенькие, но очень длинные С-раскрашиваемые прямоугольники. То есть для построения квдаратов они мало пригодны.
Доказательство теорем 4.4 и 4.5 фактически представляет описание алгоритма построения С-раскрашиваемых прямоугольников с заявленными свойствами. Примеры разбиений для =6 и 2n=8 используются в этих алгоритмах.

Какая теорема полезная я говрил в самом начале конкурса. Теорема 4.12. Именно по ней можно получить решение С^2 для С=p^s, где p простое.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 21, 22, 23, 24, 25, 26, 27 ... 130  След.

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



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

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


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

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