ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 4 из 20
  4  все
Пятничная задачка для ума за 1 миллион $
    #39516210
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonНе в обиду будь сказано но я иногда тихонько ржу с делфистов. Особенно из их
Желания создать везде forms-приложение даже в тех случаях когда эта форма вообще не нужна.

А так в целом делфисты - классные парни. Классные...

Тоже не в обиду сишникам:
неумение отделить мух от котлет у многих из них в крови
и является предметом особой гордости.

P.S. Работа с формой там только для удобства тестирования и визуализации,
а сами алгоритмы - обычные плоские функции.
...
Рейтинг: 0 / 0
06.09.2017, 10:20
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516224
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Aleksandr Sharahovtip78, в первую очередь проще, понятнее и эффективнее должен быть сам алгоритм.

А что не так с этим объявлением?
то что в массиве 0-X вам надо делать -1 при получении размера
...
Рейтинг: 0 / 0
06.09.2017, 10:32
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516227
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
причём у вас их столько, что имело смысл переменную завести
...
Рейтинг: 0 / 0
06.09.2017, 10:34
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516235
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
tip78Aleksandr Sharahovtip78, в первую очередь проще, понятнее и эффективнее должен быть сам алгоритм.

А что не так с этим объявлением?
то что в массиве 0-X вам надо делать -1 при получении размера

Ну, возьми сравни два любых нетривиальных алгоритма с базой 0 и с базой не 0.
Почти наверняка с базой 0 будет понятнее и проще.
И уж точно привычнее и потому вероятность появления ошибки в нем меньше.
...
Рейтинг: 0 / 0
06.09.2017, 10:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516273
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
В тему не влезал, а просто попалось на глаза:
2000 = 5^5 * 4^2 -- наверное это сугубо тяпничное равенство.

Однако Гольдбах и сформулирован проще, а стоит стокаже, может лучше его? при условии конечно, что его ещё не сделали ... А интересно, сколько страниц займёт топик на ярд баков?
...
Рейтинг: 0 / 0
06.09.2017, 11:25
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516284
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98,

Гольдбах не взлетит в медийном пространстве. Это удел математиков.

А шахматы - понятны почти всем. Их можно обсуждать даже на обывательком уровне.
...
Рейтинг: 0 / 0
06.09.2017, 11:31
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516287
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp982000 = 5^5 * 4^2 -- наверное это сугубо тяпничное равенство.


Спасибо за найденную опечатку.
Если не ошибаюсь, 2000 = 5^3 * 4^2 )
...
Рейтинг: 0 / 0
06.09.2017, 11:37
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516323
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
maytonГольдбах не взлетит в медийном пространстве. Это удел математиков. Ну не скажи. Лет 15 назад встретил статейку типа "Пролетая над миллионом баксов". То есть как подать ... тем более, что полнолуние на носу очередное ...
А там вроде программист о своём пролёте и о переборе чисел, и строил графики, убеждая что чем длиннее график, тем убедительнее. Что-то в этом роде.
...
Рейтинг: 0 / 0
06.09.2017, 11:58
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516398
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98,

Скажи честно. Какой процент из твоих коллег айтишников в состоянии поддержать беседу на тему этих гольбахов, риманов ?
...
Рейтинг: 0 / 0
06.09.2017, 12:55
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516406
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Небольшие улучшения-уточнения к алгоритмам 20774198

1. В процедуре подсчета решений можно сэкономить 1 проход цикла,
т.к. объединение больших диагоналей с пустыми не меняет количество модулярных решений:
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
procedure CountSolution;
var
  i: integer;
begin;
  if SolCount=0 then ShowFirstSolution;
  inc(SolCount); //total
  for i:=0 to BoardSize-2 do //excluding big digonals
    if (CanDiagP[i]=CanDiagP[i+BoardSize])
    or (CanDiagM[i+1]=CanDiagM[i+1-BoardSize]) then exit;
  if ModCount=0 then ShowFirstSolution;
  inc(ModCount); //modular
  end;



2. Соответственно можно убрать ставшие лишними пустые диагонали из массивов:
 
Код: pascal
1.
2.
  CanDiagP: array[0..2*MaxBoardSize-2] of boolean;
  CanDiagM: array[-MaxBoardSize+1..MaxBoardSize-1] of boolean;



3. Начальные условия для Completion Problem задаются серией вызовов процедуры SetColRow,
код которой я забыл привести:
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
function SetColRow(Col, Row: integer): boolean;
var
  Queen, OldRow: integer;
begin;
  Result:=false;
  if (Col>=BoardSize) or (Row>=BoardSize) or not CanColRow(Col, Row) then exit;
  PushColRow(Col, Row);
  dec(QueenCount);
  OldRow:=QueenToRow[QueenCount];
  QueenToRow[QueenCount]:=Row;
  for Queen:=QueenCount-1 downto 0 do
    if QueenToRow[Queen]=Row
    then QueenToRow[Queen]:=OldRow;
  Result:=true;
  end;



4. Все классовые методы а также процедуры, в которых упоминается Form1,
без всякого ущерба можно выкинуть или заменить консольные.
Это всего-навсего лишь примеры вызова из Delphi процедур-решателей.
...
Рейтинг: 0 / 0
06.09.2017, 13:07
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516432
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Александр. А чем твой алгоритм отличается от описанных в wiki?
...
Рейтинг: 0 / 0
06.09.2017, 13:37
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516450
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
maytonСкажи честно. Какой процент из твоих коллег айтишников в состоянии поддержать беседу на тему этих гольбахов, риманов ? Скажу честно, %=0, даже среди тех, с кем выпускался. Более того, на уровне теории я профан.

Однако же и на тему ОТО и СТО их процент тоже =0, тем не менее среди не айти молоденьких бывших коллег подобные вопросы вызывали живой интерес причём не я даже инициировал тему.
Но ведь и вы же здесь тоже не теории разрабатываете, а суперэффективная программулька может оказаться полезной.
...
Рейтинг: 0 / 0
06.09.2017, 13:52
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516452
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonАлександр. А чем твой алгоритм отличается от описанных в wiki?

Ща почитаю. Шутка.

1. В принципе у меня обычный поиск с возвратом, чуть иначе записанный, чтобы рекурсия была прозрачной. Думаю, за счет использования массивов занятых вертикалей и диагоналей даже у рекурсивного варианта должна быть неплохая скорость.

2. Второй вариант - те же яйца, но без рекурсии. Скорость в 1.5 раза выше, что, в общем-то, смешно, конечно.

3. И, наконец, третий вариант позволяет задать начальную расстановку произвольного количества ферзей, которую надо "дорешать". Он чуть медленнее второго за счет косвенного перебора строк.
...
Рейтинг: 0 / 0
06.09.2017, 13:53
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516461
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Ах, да, забыл.
Все варианты подсчитывают общее количество решений и количество модулярных решений.
Модулярные хороши тем, что ими можно мостить.
Ну и, в добавок, программирующие на Delphi видят доску с решением на экране )
...
Рейтинг: 0 / 0
06.09.2017, 13:58
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516602
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
1.5 раза это просто коэффициент который в рамках той астрономически великой оценки не играет никакого значения.

Даже если вы перепишете все на ассемблере и подключить амазон Клауд -- это все равно не поможет нам найти генерализованную
Расстановку за разумное время.

Причина - экспоненциальная сложность. Наша задача-минимум свести эту сложность к полиномиальной. А это можно сделать только
Отказавшись от классического алгоритма. То есть выкинуть его вообще.
...
Рейтинг: 0 / 0
06.09.2017, 16:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516633
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

тут есть кто-то, кто этого не понимает? )
...
Рейтинг: 0 / 0
06.09.2017, 17:03
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516668
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
В таких случаях один наш преп деликатно вопрошал: "Поднимите руку, кто понял."
...
Рейтинг: 0 / 0
06.09.2017, 17:31
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516725
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Отлично. Тогда давайте делится идеями о том как улучшить асимптоматику ферзей.
...
Рейтинг: 0 / 0
06.09.2017, 18:43
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516728
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
mayton1.5 раза это просто коэффициент который в рамках той астрономически великой оценки не играет никакого значения.

Даже если вы перепишете все на ассемблере и подключить амазон Клауд -- это все равно не поможет нам найти генерализованную
Расстановку за разумное время.

Причина - экспоненциальная сложность. Наша задача-минимум свести эту сложность к полиномиальной. А это можно сделать только
Отказавшись от классического алгоритма. То есть выкинуть его вообще.
надо всего-лишь найти способ сразу ставить 8 фигур на доску ))
...
Рейтинг: 0 / 0
06.09.2017, 18:49
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516729
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
технически, если наша цель - поиск всех готовых решений, неплохо бы научиться использовать битмапы из прошлых 27 досок...
...
Рейтинг: 0 / 0
06.09.2017, 18:50
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516755
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonОтказавшись от классического алгоритма. То есть выкинуть его вообще.
tip78надо всего-лишь найти способ сразу ставить 8 фигур на доску ))
технически, если наша цель - поиск всех готовых решений, неплохо бы научиться использовать битмапы из прошлых 27 досок...
можно ограничения переформулировать в матричном виде
на вскидку, как-то так:

det(A * N - N* A) <> 0, det(A * N + N* A) <> 0 - условие на пересечение диагоналей
abs(det(A)) = 1 - пересечение строк и столбцов
где
A = E * A'
E - единичная матрица
N = 1 1 1...2 2 2...............N N N...


{A} -?

не знаю правда, может ли это чем ни будь помочь
...
Рейтинг: 0 / 0
06.09.2017, 19:54
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516819
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
как найти одно случайное решение (в т.ч. завершение) за полиномиальное время:

http://www.fizyka.umk.pl/~milosz/AlgIILab/10.1.1.57.4685.pdf
...
Рейтинг: 0 / 0
06.09.2017, 23:01
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516826
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте я еще подкину несколько мыслей. Или несколько предположений.
А вы скажите годные они или нет и как их можно применить в этой задаче.

1) Почему так долго ищем расстановки? Если честно я пока не знаю. Скорее всего из-за того что
мы ищем вслепую не учитывая особенности эвристик. Несколько месяцев назад
в подфоруме Java один чел решал задачу Knight-Tour. И заюзал правило Варнсдорфа.
Вобщем суть в том что шахматный конь смотрит на 2 хода вперед и решает двигаться
туда откуда будет меньше ходов. Такая простая эвристика застваляет коня притягиваться
к краям доски или к площади уже покрытой ходами и как следствие "уходить" в сторону
от открытых площадей где идет сильное ветвление дерева (до 7 потомков на каждом узле).
Это наивное правило очень эффективно работало для этой задачи. Надо поискать аналог
для ферзей.

2) О пользе индексирования.

Зачем индексировать? Ну я как бывший базовик скажу вам. Если чото медленно
ищется - индексируй. Как - куча направлений. По сути индексирование - это
создание доп-структур данных которые помогают в более быстром поиске.

Это не обязательно применяется к 1-мерным данным. К чему угодно. Индексируется
пространство на картах гугла и ядекса. Q-Tree, R-Tree, M-Tree, кривые Гильберта и
Мортона и прочие коробочные технологии Spatial. Почему не индексировать доску?

Я рассматривал некоторые завершенные решения расстановок ферзей на
https://forany.xyz/a-16?pg=11 и обратил внимание на следующее.

Доска сбалансирована относительно центра. Если условно разбить ее на 4 четверти.
Или на 4 комнаты. То в каждой комнате будет сидеть одинаковое число ферзей
относительно центра.

Это можно использовать для принятия решения о том куда поставить следующего
ферзя. Мы учитываем пробивание вертикалей горизонталей и диагоналей
но очевидно что можем учитывать еще и заполнение комнат.
(Если кто-то найдет еще какие-то признаки - то пишите.)
...
Рейтинг: 0 / 0
06.09.2017, 23:15
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516839
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Aleksandr Sharahovкак найти одно случайное решение (в т.ч. завершение) за полиномиальное время:

http://www.fizyka.umk.pl/~milosz/AlgIILab/10.1.1.57.4685.pdf
и чего, британские (и все остальные в мире) ботаники не знают про этот документ от 1990г ?
а откуда у них в 1990г было УЖЕ решение на 100х100, когда современные супер-компы умерли на 27х27 ? они вообще про какую задачу?
500000x500000 ? srsly? in 1990?
"по-моему всё-таки Вася 3.14здит" (с)
...
Рейтинг: 0 / 0
06.09.2017, 23:44
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39516842
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tip78
Участник
Код: html
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
        1 2 3 4 5 6 7 8 9 0
1       @ · · · · · · · · ·
2       · · @ · · · · · · ·
3       · · · · @ · · · · ·
4       · @ · · · · · · · ·
5       · · · @ · · · · · ·
6       · · · · · · · · @ ·
7       · · · · · · · · · ·
8       · · · · · · · · · ·
9       · · · · · · · · · ·
10      · · · · · @ · · ·


вот видите паттерн в виде ромба в левом-верхнем углу (ij): 23,35,54,42
ими можно заполнять любую доску сразу и выкидывать из проверки, сокращая кол-во вариантов
возможно можно даже заранее высчитывать, сколько их поместится на ту или иную доску
а ведь есть и другие паттерны
...
Рейтинг: 0 / 0
07.09.2017, 00:00
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 4 из 20
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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