ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 16 из 20
  16  все
Пятничная задачка для ума за 1 миллион $
    #39527289
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Уточнение:
3. ... с учетом *полной* симметрии (вращение и зеркало).
Если только зеркало, то уникальность не нужно проверять.
...
Рейтинг: 0 / 0
27.09.2017, 19:59
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527293
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ex1276,

Какая польза в выделении ладейных матриц? Они уже учтены в общем ферзевом алгоритме. И нам от них нет пользы.
...
Рейтинг: 0 / 0
27.09.2017, 20:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527314
ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ex1276
Гость
maytonКакая польза в выделении ладейных матриц? Они уже учтены в общем ферзевом алгоритме. И нам от них нет пользы.

По ощущению, каким бы способом мы не проверяли доску на свободные вертикали-горизонтали, быстрее чем через комбинаторную перестановку вектора N (описывающего как раз ладейные матрицы) - проверку сделать не получится.

Но рассудит нас только алгоритм. Буду рад ошибиться
...
Рейтинг: 0 / 0
27.09.2017, 21:47
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527318
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да это верно. Мы будем комбинировать ладей. Но если ладья №254 вдруг стала на диагональ с ладьей №255
то мы можем прервать итерацию. Нам нет смысла достраивать оставшихся 745 ладей для финала итерации.
Тоесть расстановка ладей прервана.
...
Рейтинг: 0 / 0
27.09.2017, 22:07
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527354
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98maytonКак хранить найденные матрицы? Если база - то оптимально положить вектор ферзей в строку Да может банально в 4 столба? id, num, row, col ? для начала. К полю по его номеру доступаться не комильфо. Тем более рекуррентно доступаться.
Вопрос другой, как долго хранитель будет хранить?
Я думаю что хранить удобно денормализованно. В виде вектора номеров горизонталей. По верикали - просто
последовательность поэтому ее можно поскипать.

Например для доски 10х10:

IDQueenVector02,4,6,8,10,1,3,5,7,9

И я бы добавил лидирующие нули для того чтобы сделать запись позиционной. Тогда и разделители можно убрать.

IDQueenVector002040608100103050709

Для доски 10х10 будет соотв. два знакоместа под номер горизонтали. А для доски 1000х1000
надо будет три знака 000..999

Почему мне захотелось убрать запятые и сделать позиционность? Ну... КМК для решения задачи
"остаточных ферзей" нам нужно будет искать по шаблону все расстановки в которых
требуемые места забиты шаблоном а все остальные - метасимволом % или _ (в терминологии SQL).

Пример:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
create table queen10x10(
 id number primary key,
 queenvector varchar(20) not null,
 constraint queen_unq unique (queenvector)
);
....

select * from queen10x10 where queenvector like '02__06__10__03050709';



По поводу зеркал... ну... ХЗ. Цена вопроса - размер. Если не жалко - то хранить. Если жалко - то
преобазовывать при поиске в набор шаблонов.
...
Рейтинг: 0 / 0
27.09.2017, 23:50
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527367
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Для чего нужны расстановки в базе данных?
...
Рейтинг: 0 / 0
28.09.2017, 00:28
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527417
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Пока не знаю. А для чего нужен этот топик?
Вы знаете... в математике самый запрещенный вопрос - "для чего".

Ни для чего. Просто - поток мозгового сознания контролирует топик.
...
Рейтинг: 0 / 0
28.09.2017, 08:22
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527550
ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ex1276
Гость
Коллеги, призываю к вашему опыту.

Понимаю, что не хватает мастерства в программировании.
Не могу найти/сделать быстрый алгоритм генерации N-перестановок. Все варианты не нравятся.

Пишу на дельфи, на входе N и вектор текущего решения S[1..N]
Алгоритм, естественно, нерекурсивный.

Пример: S = 12345, N=5
Генерируем: 12354, 12534, 12543 и тд. все N!-1 перестановок.

Хочется изящное простое решение, может кто его знает?
...
Рейтинг: 0 / 0
28.09.2017, 11:32
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527552
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
ex1276Хочется изящное простое решение, может кто его знает?
гугл знает 100-пудово
...
Рейтинг: 0 / 0
28.09.2017, 11:36
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527554
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
https://www.google.ru/search?q=N!-1 перестановки алгоритм
...
Рейтинг: 0 / 0
28.09.2017, 11:37
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527565
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ex1276Коллеги, призываю к вашему опыту.

Понимаю, что не хватает мастерства в программировании.
Не могу найти/сделать быстрый алгоритм генерации N-перестановок. Все варианты не нравятся.

Пишу на дельфи, на входе N и вектор текущего решения S[1..N]
Алгоритм, естественно, нерекурсивный.

Пример: S = 12345, N=5
Генерируем: 12354, 12534, 12543 и тд. все N!-1 перестановок.

Хочется изящное простое решение, может кто его знает?

Найдешь быстрее, компенсирую разницу )) http://guildalfa.ru/alsha/node/26
...
Рейтинг: 0 / 0
28.09.2017, 11:44
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527624
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
как правильно смотреть на задачу про ферзей

представьте пароль, который надо узнать:
j9320i09kimvmwl,dpo23kf98ij(FJ(HUGH4ujg3jfifjiokk4ghbcnhbeuhb34y8hUFHuhUh843hf83uhfuHFUHuigh34hik1kjwnefjknvr
его можно узнать только методом перебора, иначе запутаешься в проверенных значениях
но очень хочется узнать его Сразу и Весь
за "целый" миллион
(а пароль открывает двери для всего на свете...)

зы: нигде в природе не видел подобных решений в принципе
зыы: и зеркалирование им тут не подойдёт )
...
Рейтинг: 0 / 0
28.09.2017, 13:15
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527628
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чорт ! Одни делфисты
...
Рейтинг: 0 / 0
28.09.2017, 13:18
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527648
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
tip78 как правильно смотреть на задачу про ферзей
представьте пароль, который надо узнать ... его можно узнать только методом перебора ...но очень хочется узнать его Сразу и Весь Так и хочется ответить, что гладко было на бумаге, да забыли про овраги.
Тем не менее, наука умеет много гитик. Наводка на реальность. Сделали Вин-95. Там тоже надо было вводить пароль однако ...

quot ex1276] навскидку: 12345... - единичная матрица, оно же самое маленькое число. Тупо суммируем с единичкой, с переносом, по модулю N.
Сорри, если чево не так.
...
Рейтинг: 0 / 0
28.09.2017, 13:46
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527654
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
tip78представьте пароль, который надо узнать:
Ещё одна гитика из жизни. На уроке программирования чел. доказывает, чтобы упорядочить числа, надо сравнить каждое с каждым. Иначе как ты узнаешь кто из них больше? Преп намекнул, что сравнение транзитивно ...

Могу согласиться только, что зеркалирования недостаточно.
...
Рейтинг: 0 / 0
28.09.2017, 13:58
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527673
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
ex1276, выше мой вариант не проходит, последовательность меняет монотонность ... хватит с меня.
...
Рейтинг: 0 / 0
28.09.2017, 14:30
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527911
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Из ссылки, данной на ИБМу, вытащил расстановки для N=9 (и кажется одну забыл) написано: решений = 46 / 352.
136824975 = (1)(23648795)
 
137285946 = (1)(23796584)
138692574 = (1)(23875946)
146392857 =
146825397 =
147925863 =
148397526 =
157938246 =
157942863 =
159642837 =
168374295 =
174835926 = (1)(27965348)
174839625 =
241796358 = (12473)(598)(6)
247139685 = (124)(37695)(8)
248396157 =
249731685 =
249753168 =
257936418 =
257948136 =
258136974 =
258196374 =
258693147 =
258693174 =
259418637 = (125)(39768)(4)
261379485 = (8)(12695743)
261753948 =
261958473 =
263184975 =
269358417 =
275194683 =
279631485 =
281479635 =
285396417 =
286931475 = (128749536)
358296174 = (1387)(2594)(6)
358297146 = (138425967)
359247186 = (13967)(254)(8)
362951847 = (1326)(/4978)(5)
368159247 = (1384)(2697)(5)
368519724 =
369741825 =
372859164 =
386192574 = (136287594)
427918536 = (2)(14968375)

Хочу отметить вещи в меру своего понимания, известные уже либо неверные. Вдруг кого-то вдохновит.

Раскладываем правильную перестановку матрицы в суперпозицию циклов.
9 = разложение в сумму чисел (что-то мог пропустить)
 
9 +0
1+8
2+7
2*х +у
3+6
3+5+1
4+5
3+3+3
3+3+ * +*
4+4+1
Вещь такая. Наличие 2 - брутальное транспонирование 2-х элементов - неправильная м-ца
Наличие от двух 3 - скорее всего не пройдёт из-за диагоналей
3+6 - кажется просто теоретически невозможным
Наличие от двух 1 - фишки на главной диагонали.

Остаются классы
9
1+8
3+5+1
4+4+1

1) Не они ли дают тот самый блочный метод?

2) В классе у разложений одинаковый порядок р в силу цикличности разложений
Код: plsql
1.
2.
3.
4.
5.
class  p  count(p)
9  ?  ?
1+8   ?  ?                 -- их меньше чем для 9 ?
3+5+1  3*5=15   ?  
4+4+1   4*4=16  ?

3) Наличие от двух 3 (от 3-х 4 и т.п.) - на больших размерах наверняка существуют.

Есть мнения?
...
Рейтинг: 0 / 0
28.09.2017, 19:23
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527922
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот и базячка пригодится. Чтоб ваши гипотезы обкатать. И не на жлобском поле 9х9.
...
Рейтинг: 0 / 0
28.09.2017, 19:53
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527936
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonВот и базячка пригодится. Чтоб ваши гипотезы обкатать. И не на жлобском поле 9х9.

Простые гипотезы можно проверять, задавая начальное положение для большого N>=50000.
Практически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.
...
Рейтинг: 0 / 0
28.09.2017, 20:31
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39527951
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Увы мне увы... Душа требует водки а мозк новых задач с ферзями и конями.
...
Рейтинг: 0 / 0
28.09.2017, 21:54
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528140
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
maytonжлобском поле 9х9. Замечу, что данный топик порождён как раз на основе жлобских размеров. Как и многое другое в теории чисел.

Вчерашний труд завершил (за что наверняка получу пендаля от начальства), пока каждую приходится копи/вставкой в силу несовершенства запроса.
Замечен французский перевёртыш
174839625 = (1)(27 69 5348)
174835926 = (1)(27 96 5348)

N=9, 46/352
357142869 = (13786254)(9) ...
 
136824975 = (1)(23648795)
137285946 = (1)(23796584)
138692574 = (1)(23875946)
146392857 = (1)(2436)(5978)
146825397 = (1)(24897365)
147925863 = (1)(24937865)
148397526 = (1)(2438)(5967)
157938246 = (1)(2537)(4968)
157942863 = (1)(25493786)
159642837 = (1)(2546)(3978)
168374295 = (1)(26438957)
174835926 = (1)(27965348)
174839625 = (1)(27695348)
241796358 = (12473)(598)(6)
247139685 = (124)(37695)(8)
248396157 = (12438597)(6)
249731685 = (12476)(395)(8)
249753168 = (1247)(3986)(5)
257936418 = (12537498)(6)
257948136 = (125496837)
258136974 = (12538794)(6)
258196374 = (12594)(387)(6)
258693147 = (12597)(3846)
258693174 = (125946387)
259418637 = (125)(39768)(4)
261379485 = (12695743)(8)
261753948 = (1263)(4798)(1)
261958473 = (12687493)(5)
263184975 = (1264)(5879)(3)
269358417 = (1268)(3974)(5)
275194683 = (12764)(359)(8)
279631485 = (395)(12746)(8)
281479635 = (1283)(5769)(4)
285396417 = (128)(35974)(6)
286931475 = (128749536)
358296174 = (1387)(2594)(6)
358297146 = (138425967)
359247186 = (13967)(254)(8)
362951847 = (1326)(4978)(5)
368159247 = (1384)(2697)(5)
368519724 = (13826945)(7)
369741825 = (139547826)
372859164 = (1327)(4869)(5)
386192574 = (136287594)
427918536 = (2)(14968375)
Просто интересно, кто не понимает, что за выражениями (1327)(4869)(5) стоит произведение матриц, причём "неправильных" в целом и оно коммутативно?
...
Рейтинг: 0 / 0
29.09.2017, 10:36
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528238
ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ex1276
Гость
Aleksandr SharahovПрактически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.

Вы попробуйте предустанавливаемых ферзей ставить ближе к центру. Например в центральном квадранте.
Интересно сможет ли алгоритм найти решения хотя бы при 100 центральных ферзях на поле 50 000.
...
Рейтинг: 0 / 0
29.09.2017, 12:28
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528251
ex1276
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ex1276
Гость
Может нам устроить тогда гонку размерности решений.
Надо придумать способ представить решение в кратком, наглядном и удобоваримом для интернета виде.
Может так:

N-размерность, дата, автор решения, алгоритм, время поиска в чч:мм:cc
X1,X2,X3,X4...XN

Хотя решение на 50 000 займет 250 Кб, а на 1 млн = 6 Мб.
...
Рейтинг: 0 / 0
29.09.2017, 12:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528314
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ex1276Aleksandr SharahovПрактически невозможно задать начальное положение нескольких ферзей, чтобы не было завершения.
Даже для 25000 ферзей находятся завершения.

Вы попробуйте предустанавливаемых ферзей ставить ближе к центру. Например в центральном квадранте.
Интересно сможет ли алгоритм найти решения хотя бы при 100 центральных ферзях на поле 50 000.

Попробовал на поле 50000х50000 в центральный квадрат 25000х25000 случайно ставить 12500 ферзей.
Завершение нашлось во всех 10 проведенных тестах.
...
Рейтинг: 0 / 0
29.09.2017, 13:32
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528340
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Ошибки точно нет? другие подтверждают подобное?
...
Рейтинг: 0 / 0
29.09.2017, 13:49
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 16 из 20
  16  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]