ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 17 из 20
  17  все
Пятничная задачка для ума за 1 миллион $
    #39528345
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Не вызывает вопросов почему при доле удачи на 46 порядков меньше, не удаётся промахнуться? С отладкой ГУИ, обычн наоборот, сколько его ни тестируй, юзер в первый же день наткнётся на фигню.
...
Рейтинг: 0 / 0
29.09.2017, 13:55
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528360
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Интересно взглянуть с т.зр. теории кодирования. С какого момента нач-ая позиция становится префиксным кодом? Подразумеваю, что кодируем 2 значения, т.е. как бы имеем 2 вида хэшей - прав и неправ. Мож надо грамотней сформулировать ...
...
Рейтинг: 0 / 0
29.09.2017, 14:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528367
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98Ошибки точно нет? другие подтверждают подобное?

Ошибки нет. Четверть поставленных ферзей еще оставляет достаточно степеней свободы для поиска завершения. Примерно при 15000 ферзей завершения уже находятся не с первой попытки, а затем и вовсе перестают находиться.

Кто другие? Скомпилируй и стань другим )
...
Рейтинг: 0 / 0
29.09.2017, 14:14
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528384
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aleksandr Sharahov Скомпилируй и стань другим ) кто доказал, что исходники без ош?

Но я другое хотел сказать, может твоя статистика про 25% в этом русле.
Давным-давно возникала т.н. "алгоритмическая проблема разрешимости для полугрупп с конечным числом образующих" (не знаю, возможно, что на сегодня она породила кучу детализированных подпроблем )

У нас же группа, т.е. частный случай ПГ.
Так вот был результат, вроде такого (за диапазоны не ручаюсь), что если образующие налезают друг на друга до 1/4 своей длины, то проблема разрешима. Если от 1/3 - нет. В промежутке - как сложится.
ПГ представляются в виде слов из алфавита + определяющие комбинации слов наподобие таблицы умножения. Более точно формализовать наш случай сейчас не смогу. Просто вывод сходный: чем больше начальных данных, тем надёжней классифицировать, если доля неоднозначностей не очень большая.
...
Рейтинг: 0 / 0
29.09.2017, 14:38
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528389
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98кто доказал, что исходники без ош?

Совсем не требуется, чтобы исходники были без ошибок )

Требуется, чтобы найденное завершение было правильным. А это легко проверить. Надеюсь, не ошибешься.

Вещи кажутся невероятными до тех пор, пока к ним не привыкли. Но это проходит.
...
Рейтинг: 0 / 0
29.09.2017, 14:47
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528437
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Если проверялка в другой проге, то мой вопрос доказательства был о ней. Правдободобность не означает достоверности. А для 10 тыс глазками проверять - стал быть д.б. прога, хоть бы и в эксэл, я так думаю.
...
Рейтинг: 0 / 0
29.09.2017, 15:24
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528507
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98Если проверялка в другой проге, то мой вопрос доказательства был о ней. Правдободобность не означает достоверности. А для 10 тыс глазками проверять - стал быть д.б. прога, хоть бы и в эксэл, я так думаю.

Не надо проверять ни другой прогой, ни глазами.
Достаточно вызвать простую функцию вроде этой:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;
...
Рейтинг: 0 / 0
29.09.2017, 16:39
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528509
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov, потерял строчку в начале функции
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;
...
Рейтинг: 0 / 0
29.09.2017, 16:42
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528541
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
См. мой предыдущий пост.

З.Ы. Ну и довольно, ведь так в лом было признаться, мол, питаем доверие к процедуре.
Типа см. сам и тоже питай доверие. Особенно, учитывая загадочные QueenColRow и CountDiagM ...

Если есть спортивный интерес, то ...
для N=9 самыми популярными разложениями оказались вида Card(4+4+1)=13 / 42 и Card(8+1)=16 / 42. Даже не удивлюсь, если заполнять ими (или пятёрками) до 60% , что всё равно будут ответы.
для 4+5 =1 /42, наверное доска маленькая, даже удивился
1+3+5 =9 / 42
9+0 =6 / 42
...
Рейтинг: 0 / 0
29.09.2017, 17:16
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528554
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98См. мой предыдущий пост.
З.Ы. Ну и довольно, ведь так в лом было признаться, мол, питаем доверие к процедуре.
Типа см. сам и тоже питай доверие. Особенно, учитывая загадочные QueenColRow и CountDiagM ...


Загадочный QueenColRow - массив положений ферзей,
а CountCol, CountDiagM, CountDiagM, - счетчики ферзей в столбцах и на диагоналях.

Да, я "питаю доверие" к оператору сложения, а ты?
...
Рейтинг: 0 / 0
29.09.2017, 17:29
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528731
Tactical Nuclear Penguin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tactical Nuclear Penguin
Участник
Aleksandr SharahovAleksandr Sharahov, потерял строчку в начале функции
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;



простите, а зачем писать так:
Код: pascal
1.
begin;
...
Рейтинг: 0 / 0
30.09.2017, 05:30
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39528751
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Tactical Nuclear PenguinAleksandr SharahovAleksandr Sharahov, потерял строчку в начале функции
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
function IsSolutionValid: boolean;
var
  i, r, c: integer;
begin;
  Result:=false;
  FillChar(CountCol[0], BoardSize, 0);
  FillChar(CountDiagP[0], 2*BoardSize-1, 0);
  FillChar(CountDiagM[1-BoardSize], 2*BoardSize-1, 0);
  for i:=0 to BoardSize-1 do with QueenColRow[i] do begin;
    c:=QueenCol;
    r:=QueenRow;
    if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;
    if CountCol[c]<>0 then exit;
    CountCol[c]:=1;
    if CountDiagP[c+r]<>0 then exit;
    CountDiagP[c+r]:=1;
    if CountDiagM[c-r]<>0 then exit;
    CountDiagM[c-r]:=1;
    end;
  Result:=true;
  end;



простите, а зачем писать так:
Код: pascal
1.
begin;



простите, а почему вас не смущает, что написано так:
Код: pascal
1.
2.
  Result:=true;
  end;
...
Рейтинг: 0 / 0
30.09.2017, 09:42
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529323
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Tactical Nuclear Penguin а зачем писать так:
Код: pascal
1.
begin;

а в запросах я часто пишу так
Код: plsql
1.
2.
where  2=2
   and ....

и зачем так делаю ...

авторДа, я "питаю доверие" к оператору сложения, а ты? остаётся питать доверие к "дельфийскому" оракулу.
По-видимому, ВБУ нас просто развели. Получается, что у каждого решения есть свой "родственник" - не решение. Ясно, что при N-1 уже не найдётся, а какая-нить прапрабабушка - да.

Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить. А точнее, найти минимальное такое начальное положение, к-рое притворяется правильным. Начиная с 10к. Вот, к примеру, задачка в отдельную тему на 2,6 млн, баки клянчить у того же клейна.
...
Рейтинг: 0 / 0
02.10.2017, 12:10
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529364
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
exp98Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить. А точнее, найти минимальное такое начальное положение, к-рое притворяется правильным. Начиная с 10к. Вот, к примеру, задачка в отдельную тему на 2,6 млн, баки клянчить у того же клейна.откуда такой вывод? их по идее куда больше
...
Рейтинг: 0 / 0
02.10.2017, 13:23
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529380
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Не знаю, это фантазия, во всяк Дмитрий затрудняется получить такую позу. Будет интересно узнать, что это не так.
А у меня, не вдаваясь в детали, первой реакцие было как раз, чо этого не мб. А теперь думаю наоборот, что возможно по причине редкости у каждой законченной позы и найдётся не очень близкий предок - их же много больше. Правда правильные позы не равномерн распределены, в каких-то разложениях они гуще. Тем интереснее.
Основываюсь только на словах в теме.
...
Рейтинг: 0 / 0
02.10.2017, 13:53
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529383
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
У Александра Ш, не дмитрия, то есть,
...
Рейтинг: 0 / 0
02.10.2017, 13:54
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529742
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98Вместо, чтоб искать завершение расстановок, надо искать начальные положения, к-рые невозможно завершить.

Вот, например, если взять решение для доски 5х5 и поместить в центр доски NxN (N-нечетное), то его можно будет завершить только при N>=25.

Или, например, решение для доски 6х6, помещенное в центр доски NxN (N-четное), невозможно завершить при N<=28 (при N>28 не проверял).

И что это дает?
...
Рейтинг: 0 / 0
02.10.2017, 23:48
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529745
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovИли, например, решение для доски 6х6, помещенное в центр доски NxN (N-четное), невозможно завершить при N<=28 (при N>28 не проверял).

Проверил: при N=30 завершения есть.
...
Рейтинг: 0 / 0
03.10.2017, 00:03
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39529951
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aleksandr SharahovИ что это дает? отдельную тему на 2,6 млн, других задумок не было/
...
Рейтинг: 0 / 0
03.10.2017, 10:53
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532513
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Продолжаю свою мысль о permutations с пропусками. Нарисую поясняющую картинку.
...
Рейтинг: 0 / 0
06.10.2017, 21:23
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532536
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Как-то так. Главное - как оптимизировать копирование массивов в рекурсию.
...
Рейтинг: 0 / 0
06.10.2017, 23:03
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532688
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У меня не хватило терпенья нарисовать все 24 листа. Но 2 решения я обозначил.
Здесь выполняются условия оптимизации. Имеют места "отсечения" (по типу альфа-бет) заведомо тупиковых веток.
И процедура проверки "ферзей" под боем не зависит линейно от N=1000. Чему равна
средняя глубина дерева - можно прикинуть экспериментально.

Для 1000-й доски возможно не хватит стека чтобы сохранять состояние этого автомата
поэтому придется использовать Heap. В наихудшем случае это будет прогрессия 1000,999,998 e.t.c.
Тоесть приблизительно - полу-площадь шахматной доски. 500 тыс элементов. Для short
типа данных - это (2 байта на элемент) будет примерно 500 000 * 2 = 1 000 000 байт
или примерно 1 мегабайт стека массивов.

Алтернативный вариант - модифицировать вектор ферзей при каждом погружении
в рекурсию а при выходе наверх - восстанавливать. И возможно это не вектор а list.
Или версионный list.
...
Рейтинг: 0 / 0
07.10.2017, 14:29
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532753
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

неясно, это поиск с возвратом или что-то другое?
...
Рейтинг: 0 / 0
07.10.2017, 18:59
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532793
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Определённо это поиск. И возврат тоже есть. Но это не самые главные вопросы.
...
Рейтинг: 0 / 0
07.10.2017, 21:09
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39532798
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
если это выглядит как утка ... ))
...
Рейтинг: 0 / 0
07.10.2017, 21:22
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 17 из 20
  17  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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