2014 dxdy logo

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

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




На страницу Пред.  1 ... 76, 77, 78, 79, 80, 81, 82 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 14:06 
Аватара пользователя
Дополнение.
Похоже, что в первом варианте вместо p[i,(n-j)mod n] можно использовать любой латинский квадрат?

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 14:15 
Аватара пользователя
svb в сообщении #600405 писал(а):
т.е. мы использовали ассоциативность и коммутативность сложения, а требование к умножению только одно.
Меня смущает одна вещь. При удается использовать только часть таблицы "умножения", а далее использовать Г-достраиваие.


Ааа вы все свои идеи изложили ввиде трех строчек кода. :-) Посмотрю внимательно.

А Г-достраивание наверно будет нужно всегда.

Функция присовения цвета такова (i*k+j+l), что если прямоугольник находится в одном квадранте, то формула i*k+j+l = i*c+j+d = a*c+b+d = a*k+b+l
Превращается в j+l = j+d = b+d = b+l
То есть каждый квадрант у нас будет латинским квадратом(в строках и колонках нет одинаковых чисел). А это означает, что Г-крюк всегда можно добавить.
Получается, что все выкладки можно применить к области под Г-крюком. То есть мы строим квадрат со стороной С^2-C, разбитый на квадранты со стороной С (или С-1). Впрочем размер таблицы умножения при этом не уменьшается и задача проще не становится.

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:06 
Аватара пользователя
Nataly-Mak
Цитата:
но как я понимаю, тут мало кто интересуется чужими идеями, все сами с усами :D
Ну, почему же? Но из того, что
Цитата:
Всё это я уже рассказывала.
что должно следовать? А другие не рассказывали, но это не обозначает, что они эти идеи задолго до вас не обдумали. Все участники так или иначе проходят сходные пути в своих рассуждениях, но они все-таки различные. Иногда встречаются трудности, выявляющие некую общую часть различных подходов. В этом случае возникает потребность в более глубоком осмыслении этой трудности, в общении с другими людьми. К сожалению, до окончания конкурса участники сильно ограничены в общении, это приходится учитывать.

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

Прошу не воспринимать мои слова отрицательно - к сожалению, я часто этим грешу. Меня иногда так и подмывает кого-нибудь укусить. Относитесь к ним, как к обыкновенному "трепу" человека, который застрял во "втором классе" :-) Я бы мог подыскать себе оправдания, дескать старый и больной на голову, дескать я мало времени занимаюсь задачей, и т.д. Но это не так :-(

-- Сб июл 28, 2012 15:10:27 --

Pavlovsky
Цитата:
А Г-достраивание наверно будет нужно всегда.
В примере для GF(4), который я приводил, этого нет.

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:26 
Аватара пользователя
svb в сообщении #600433 писал(а):
Я не хочу ничего плохого говорить о ваших идеях, но постоянные реплики "Я это уже рассказывала" могут вызвать недоумение. Ну и что?

Постараюсь ответить кратко, без лишнего "трёпа".

Я прекрасно знаю ваше отношение к моим идеям (не только по форуму, но и по личной переписке). Это первое.

Второе: я была приведена в неописуемое удивление, когда тут разволновались, как бы вас не отлучили от конкурса за то, что вы выложили решение C6N36 :D
Два часа смеялась и до сих пор смеюсь :D
Ведь я выложила это решение, наверное, месяц назад!

Вот это и дало мне основания предполагать, что я совершенно напрасно стараюсь выкладывать здесь свои идеи, их всё равно никто не читает. Увы, но это так.

(Оффтоп)

Это заодно и ответ на вопрос, почему я вас "принципиально игнорирую".
И давайте не будем дальше развивать "трёп".
Помните, как вы написали в теме "Магические квадраты": "Я на вас обиделся". Я на вас тоже обиделась, потому и игнорирую.

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:27 
Аватара пользователя
svb в сообщении #600433 писал(а):
В примере для GF(4), который я приводил, этого нет.

Смогли построить квадрат целиком из ЛК. Для p^s это возможно. А для С=6 уже требуется каемка на коврике. Или можно построить решение C6N36 целиком состоящее из ЛК 6х6??

-- Сб июл 28, 2012 17:31:45 --

svb в сообщении #600433 писал(а):
Меня удивило сообщение Павловского, я искренне считал это хорошо известным.

Интересно откуда я мог это узнать? Можно ссылку где это обсуждалось. Стараюсь тщательно мониторить информацию по теме. Конечно, всякое бывает, может где то бегло пробежалася по сообщениям, ничего не понял и пошел дальше.

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:35 
Аватара пользователя
Pavlovsky в сообщении #600437 писал(а):
Интересно откуда я мог это узнать? Можно ссылку где это обсуждалось.

Не удивляйтесь!
svb считает, что все просто обязаны знать то, что знает он.
Вот я поля обязана была узнать в университете, а почему-то не узнала :D

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:47 
Аватара пользователя
Nataly-Mak в сообщении #600440 писал(а):
svb считает, что все просто обязаны знать то, что знает он.


Да ладно многие так считают. Всем кажется, что тема которую они обдумывают, простая и естественная. Помню как Алексей Чернов искренне удивлялся, что есть люди которые не читали книжек по компьютерной графике. :D

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 15:57 
Аватара пользователя
Pavlovsky
Про поля было в "основной" статье.

Nataly-Mak
Цитата:
svb считает, что все просто обязаны знать то, что знает он.
Это невозможно :-) - я слишком много знаю :D .

(Оффтоп)

Цитата:
Помните, как вы написали в теме "Магические квадраты": "Я на вас обиделся".
Честно скажу, абсолютно не помню. Может и писал, но уж, конечно, не помню за что обиделся. Я постоянно на кого-нибудь обижаюсь. На днях вот на дочь за что-то обиделся, а сейчас мы с ней прекрасно ладим. Я совершенно не отношусь к злопамятным людям, как некоторые (не буду тыкать пальцем :-) ).

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 16:15 
Аватара пользователя
svb в сообщении #600447 писал(а):
Про поля было в "основной" статье.


Про поля я читал. И даже нашел ссылки как с помощью полей строить ортогональные ЛК. А вот что можно просто цвет квадрата задавать функцией вида i*k+j+l там не было. Я все делал как написано в той статье, пункт за пунктом. В обсуждениях проскакивали намеки, что решения C^2 можно строить очень просто. Но конкретики не было. Ну а если пытаться читать между строк, так это никакого времени не хватит.

 
 
 
 Re: Новый конкурс программистов
Сообщение28.07.2012, 16:54 
Аватара пользователя
Pavlovsky
Цитата:
Я все делал как написано в той статье, пункт за пунктом.
Должен сознаться, что я остановился на слове "поле", а далее не читал по понятной мне и Наталии причине. До функции вида i*k+j+l я не сразу додумался и не вижу ничего странного в том, что ее можно пропустить. Но это вопрос времени, одни чуть раньше, другие чуть позже. Идеи они вообще в массе своей очень просты. Мой, достаточно богатый, опыт общения с различными людьми заставляет меня не завышать свои "способности", не занижать "способности" других людей. Редко я находил что-то, что ускользнуло от других. А идею функции i*k+j+l я никак не могу отнести к сложным, поэтому и был удивлен.

 
 
 
 Re: Новый конкурс программистов
Сообщение29.07.2012, 10:54 
Аватара пользователя
svb в сообщении #600363 писал(а):
dimkadimon
Цитата:
Хорошо можно сказать что p[a,b] = (a+b) mod n, a sq[a,b] = (ab) mod n?
для простых n это проходит, но уже для n=4 необходимо брать:
Код:
0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0


Спасибо. У меня теперь еще больше вопросов. Почему для простых проходит, а для остальных нет? То есть что ломается? Как называются эти группы которые вы показали для с=4? Если не ошибаюсь то вторая группа это Z_2 х Z_2? Как эти группы находить?

Меня очень интересуют группы порядка 10. Их две: D_5 и Z_5 x Z_2. Можно ли эти группы также использовать?

 
 
 
 Re: Новый конкурс программистов
Сообщение29.07.2012, 12:37 
Аватара пользователя
dimkadimon
Цитата:
Почему для простых проходит, а для остальных нет?
Если не ошибаюсь, имеется теорема о том, что конечные поля из $C$ элементов существуют только для степеней простых чисел $C=p^s$. При $s=1$ это обычные конструкции по модулю $p$, а для больших степеней они устроены несколько сложнее. Нам оказались полезными поля GF(8), GF(9), GF(16), таблицы умножения и сложения для этих полей можно найти в интернете:

(Оффтоп)

Код:
GF(8)
0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 3 1 7 5
0 3 6 5 7 4 1 2
0 4 3 7 6 2 5 1
0 5 1 4 2 7 3 6
0 6 7 1 5 3 2 4
0 7 5 2 1 6 4 3

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

GF(9)
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
0 2 1 6 8 7 3 5 4
0 3 6 2 5 8 1 4 7
0 4 8 5 6 1 7 2 3
0 5 7 8 1 3 4 6 2
0 6 3 1 7 4 2 8 5
0 7 5 4 2 6 8 3 1
0 8 4 7 3 2 5 1 6

0 1 2 3 4 5 6 7 8
1 2 0 4 5 3 7 8 6
2 0 1 5 3 4 8 6 7
3 4 5 6 7 8 0 1 2
4 5 3 7 8 6 1 2 0
5 3 4 8 6 7 2 0 1
6 7 8 0 1 2 3 4 5
7 8 6 1 2 0 4 5 3
8 6 7 2 0 1 5 3 4

GF(16)
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  0  2  4  6  8 10 12 14  3  1  7  5 11  9 15 13
  0  3  6  5 12 15 10  9 11  8 13 14  7  4  1  2
  0  4  8 12  3  7 11 15  6  2 14 10  5  1 13  9
  0  5 10 15  7  2 13  8 14 11  4  1  9 12  3  6
  0  6 12 10 11 13  7  1  5  3  9 15 14  8  2  4
  0  7 14  9 15  8  1  6 13 10  3  4  2  5 12 11
  0  8  3 11  6 14  5 13 12  4 15  7 10  2  9  1
  0  9  1  8  2 11  3 10  4 13  5 12  6 15  7 14
  0 10  7 13 14  4  9  3 15  5  8  2  1 11  6 12
  0 11  5 14 10  1 15  4  7 12  2  9 13  6  8  3
  0 12 11  7  5  9 14  2 10  6  1 13 15  3  4  8
  0 13  9  4  1 12  8  5  2 15 11  6  3 14 10  7
  0 14 15  1 13  3  2 12  9  7  6  8  4 10 11  5
  0 15 13  2  9  6  4 11  1 14 12  3  8  7  5 10

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14
  2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13
  3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12
  4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11
  5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10
  6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9
  7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8
  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7
  9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6
10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5
11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4
12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3
13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2
14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1
15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
Требование быть полем слишком сильное для нашей задачи, поэтому остается надежда найти иные подходы. Увы, пока вопрос открыт :-(

Вот ссылка на вики. Вам, может, интереснее Finite field.

 
 
 
 Re: Новый конкурс программистов
Сообщение29.07.2012, 14:32 
Аватара пользователя
Я же говорила, что Алексей ещё пару строк припрятал :D

Цитата:
21 396 156816 Alex Chernov @ 13:53:04 on 07-29-2012 1

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

Получены на основе группы из 10 попарно ортогональных ЛК 10-го порядка с дырками.
[см. статью "Нетрадиционные латинские квадраты"; статья экспериментальная, ничего научного! :wink: ]

Хотя дырок в раскраске 100х100 10-color больше, чем в показанной выше раскраске (там было 790), но зато данная раскраска является регулярным решением. Каждый из 10 цветов в раскраске занимает 909 ячеек, символ NULL занимает 910 ячеек, это и есть дырки.

Изображение

И получена ещё раскраска 110х100 10-color, в которой тоже 910 дырок. Просто к раскраске 100х100 приписаны ещё 10 строк.

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение29.07.2012, 19:07 
Аватара пользователя
Удалось немного улучшить раскраску 100х100 10-color, количество дырок стало 820.
Каждый из 10 цветов занимает 918 ячеек. Опять очень равномерно распределены цвета.

Изображение

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 76, 77, 78, 79, 80, 81, 82 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group