2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 94, 95, 96, 97, 98, 99, 100 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение25.08.2012, 15:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #610394 писал(а):
С это простое число в степени плюс один. p простое число, а k любая степень. Для p=3 получаем N=3^2+3+1=13.

Ещё раз: у вас написано:
C=p^k+1.
Понятно, что p - простое число. Пусть p=3.
Что здесь k?
Что значит "k любая степень"? Это как?

Вот если k=1, то да, получаем: С=4, N=13.

А если k=2. Это значит: С=3^2+1=10.
Тогда что получаем по вашей формуле для N? В вашей формуле для N вообще нет k. И это неправильно.

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


22/03/08

7154
Саратов
И вот оно - ещё одно оригинальное решение для С=8. Это диагональное решение С8N57, построенное по алгоритму Герберта.
CDS (57,8,1) 1,2,7,16,23,27,46,56.

Изображение

Интересно распределение цветов в этом решении, цвет А занимает 456 ячеек, все остальные цвета по 399 ячеек.

Это максимальное диагональное решение для С=8?

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


26/01/10
959
Nataly-Mak в сообщении #610382 писал(а):
Я высказала гипотезу, что 10-сильная раскраска 84х10 не существует.

Вы ничего не путаете? Точно 84?

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


22/03/08

7154
Саратов
Я ничего не путаю.
Гипотеза выложена в теме с подробным описанием и наглядными примерами (моя попытка построить такую раскраску и соответствующий ей набор из 10 латинских прямоугольников 9х10 с неполной последней строкой и с 20 пустыми ячейками).

У вас есть опровержение гипотезы, то бишь 10-сильная раскраска 84х10?
Просто скажите: да или нет. Раскраску, естественно, покажете после окончания конкурса.

Интересно, что никто ничего не ответил по поводу моей гипотезы на форуме конкурса. Меня не поняли? :-(

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


26/01/10
959
Nataly-Mak в сообщении #610428 писал(а):
У вас есть опровержение гипотезы, то бишь 10-сильная раскраска 84х10?

Не помню уже... Но мне показалось, что я такую строил. Оказалась ненужной.

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


22/03/08

7154
Саратов
Так показалось или строили? :-)

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


26/01/10
959
Nataly-Mak в сообщении #610435 писал(а):
Так показалось или строили? :-)

Точно строил, но не помню, докуда достроил. Так что ладно... фиг с ней.

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


01/06/12
988
Adelaide, Australia
Nataly-Mak в сообщении #610404 писал(а):
dimkadimon в сообщении #610394 писал(а):
С это простое число в степени плюс один. p простое число, а k любая степень. Для p=3 получаем N=3^2+3+1=13.

Ещё раз: у вас написано:
C=p^k+1.
Понятно, что p - простое число. Пусть p=3.
Что здесь k?
Что значит "k любая степень"? Это как?

Вот если k=1, то да, получаем: С=4, N=13.

А если k=2. Это значит: С=3^2+1=10.
Тогда что получаем по вашей формуле для N? В вашей формуле для N вообще нет k. И это неправильно.


N=C^2-C+1 = (p^k+1)^2-(p^k+1)+1

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


22/03/08

7154
Саратов
Теперь правильно.
И это решения 1-го класса:

C=6, N=31
C=10, N=91

и т.д.

---

Очень давно, когда занималась пандиагональными магическими квадратами, один коллега признался, что не понимает разломанные диагонали.
Поместила в Википедию свою примитивную картинку, интерпретирующую разломанные диагонали. Картинка там прижилась :-)

Нечто аналогичное мы видим в диагональных решениях с правильным циклическим сдвигом:

Изображение

Это решение C3N7, построенное по алгоритму Герберта, подробно описал построение dimkadimon чуть выше.

Удивительно! У Герберта решение полностью определяется CDS; в данном случае это (1,2,4), то есть расположение только первого цвета А в первой строке.

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


22/03/08

7154
Саратов
Ещё одно решение, построено по алгоритму Герберта, C4N13.
CDS (1,2,4,10).

Изображение

Для сравнения покажу своё диагональное решение C4N13 с неправильным циклическим сдвигом:

Изображение

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


22/03/08

7154
Саратов
А это диагональное решение из Интернета C4N16, правильный циклический сдвиг:

Изображение

Тут можно сделать проще алгоритм, чем поиск характеристической строки длиной 16 :?:
Что-то аналогичное CDS...

По алгоритму Герберта строятся диагональные решения C5N21, C6N31. А как просто построить диагональные решения C5N25, C6N36?

Ещё раз подчеркну: речь идёт о диагональных решениях с правильным циклическим сдвигом.

Соответственно для С=3, по алгоритму Герберта строится диагональное решение C3N7 (показано выше), а svb привёл диагональное решение C3N9:

Код:
A,A,B,A,B,C,C,B,C,
A,B,A,B,C,C,B,C,A,
B,A,B,C,C,B,C,A,A,
A,B,C,C,B,C,A,A,B,
B,C,C,B,C,A,A,B,A,
C,C,B,C,A,A,B,A,B,
C,B,C,A,A,B,A,B,C,
B,C,A,A,B,A,B,C,C,
C,A,A,B,A,B,C,C,B


-- Вс авг 26, 2012 08:20:19 --

dimkadimon в сообщении #610359 писал(а):
По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1, точно не знаю какой ето класс. Немного изменив метод можно получить и лучше, например C5N25 и C6N36.

Вы уже знаете, как модифицировать метод Герберта?
Очень интересно! Будем ждать рассказ об этом.

Хотя... вы уже кое-что рассказали:

Цитата:
Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

Но я пока ничего не поняла :?

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


22/03/08

7154
Саратов
Начала вышивать крестиком диагональное решение C10N91 :roll:
Алгоритм Герберта.
CDS (91,10,1)
1,3,7,8,19,22,32,55,64,72

Получится?

Изображение

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


25/08/12
167
Germany
Алгоритм Герберта.
CDS (91,10,1)
1,3,7,8,19,22,32,55,64,72

Получится?

This function gives the color of cell a[x][y],1<=x,y<=91 for C10N91:

int color(int x, int y){

char cds[] = {1,3,7,8,19,22,32,55,64,72};
for (int i=0;i<10;i++)
for (int j=0;j<10;j++)
if ((91+x+y+cds[j]-cds[i])%91==1) return j+1;
}

The colors of the diagonal from lower left to upper right can be choosen arbitrarily.

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


22/03/08

7154
Саратов
Herbert Kociemba
как я понимаю, вы написали программу построения решения C10N91.
Спасибо!

К сожалению, не понимаю этот язык программирования :oops:
Я тоже немного автоматизировала процесс построения; у меня программка на языке QBASIC.

Мне интересен вопрос построения диагональных решений C^2xC^2.
Есть ли у вас идеи?
Как, например, быстро построить решения C4N16, C5N25 и т.д.?

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


01/06/12
988
Adelaide, Australia
Nataly-Mak в сообщении #610589 писал(а):
Вы уже знаете, как модифицировать метод Герберта?
Очень интересно! Будем ждать рассказ об этом.

Хотя... вы уже кое-что рассказали:

Цитата:
Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

Но я пока ничего не поняла :?


Суть в том что вместо одной CDS можно использовать несколько разных CDS. Причем можно использовать CDS в которой не все разницы от 1 до v-1, а только некоторые - главное чтобы все разницы были разными.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 94, 95, 96, 97, 98, 99, 100 ... 130  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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