AD
еще можно прочитать в строку, проифать минус, а дальше все в unsigned
Size: a a a
2021 March 31
AD
сейчас ты криво читаешь числа большие 2^63
AD
и ты ничего с этим не можешь поделать
2021 April 01
A
Чат, подскажите по задачке. Дан текст в виде строки. Надо найти топ десять повторяющихся фраз.
CD
что такое фраза
A
что такое фраза
A phrase is a stretch of three to ten consecutive words and cannot span sentences. Omit a phrase if it is a subset of another, longer phrase, even if the shorter phrase occurs more frequently (for example, if “cool and collected” and “calm cool and collected” are repeated, do not include “cool and collected” in the returned set)
АJ
Возможно всё зависит от реализации, но какова сложность решения задачи о N ферзях при использовании поиска с возвратом?
P
Пусть мы прочитали 2^64 в тип long long - будет преобразование типов и получим -1, тогда на первом сравнении выведет "char", хотя это не подходит.
Пусть мы прочитали -1 в тип long long - на первом if "char" нам подходит.
Таким образом механизм считывания кандидата в long long здесь не правильный - тебе нужно читать в строку.
Пусть мы прочитали -1 в тип long long - на первом if "char" нам подходит.
Таким образом механизм считывания кандидата в long long здесь не правильный - тебе нужно читать в строку.
D
Возможно всё зависит от реализации, но какова сложность решения задачи о N ферзях при использовании поиска с возвратом?
Какая-то экспонента
NK
Какая-то экспонента
А не n! ? Мне кажется число расстановок ферзей растет как n!/c^n
D
А не n! ? Мне кажется число расстановок ферзей растет как n!/c^n
А, ну я живу мыслями в сат солверах. n! явно лучшая оценка.
2021 April 02
G
У кого-то есть идеи по поводу функции которая находит все комбинации покера из списка карт, запоминает какие карты используются в комбинации , и выбирает из них самую лучшую?
GF
Возможно всё зависит от реализации, но какова сложность решения задачи о N ферзях при использовании поиска с возвратом?
Стивен Скиена в книге "Алгоритмы: руководство по разработке" в седьмой главе как раз рассказывал про поиск с возвратом на примере решения задачи о покрытии доски. Там действительно сложность n!, но они оптимизировали алгоритм, отсекая тупиковые перестановки, что он смог отработать за приемлемое время. Собственно процесс оптимизации кратко там и описан.
CD
Стивен Скиена в книге "Алгоритмы: руководство по разработке" в седьмой главе как раз рассказывал про поиск с возвратом на примере решения задачи о покрытии доски. Там действительно сложность n!, но они оптимизировали алгоритм, отсекая тупиковые перестановки, что он смог отработать за приемлемое время. Собственно процесс оптимизации кратко там и описан.
Тут скорее всего надо согласиться с nkarpov в оценке n!/c^n; мысль такая: возьмём случайную перестановку ферзей; среди них точно не больше N^2 пар бьют друг друга; в похожей ситуации для ладей и выбора расстановки по одной в каждой строке получалось n! ~ n^n/e^n и вряд ли наша ситуация лучше
CD
То есть скорее всего N-queen просто имеет n!/c^n решений
EZ
То есть скорее всего N-queen просто имеет n!/c^n решений
многовато
EZ
То есть скорее всего N-queen просто имеет n!/c^n решений
тогда тупо рандомить решало бы за полином, не?
CD
тогда тупо рандомить решало бы за полином, не?
за c^n же, если перестановку
EZ
за c^n же, если перестановку
Справедливо, тупанул
CD
Справедливо, тупанул
в общем-то рандомные проверки подтверждают
https://oeis.org/A000170/list
(20!/39029188884)^(1/20) = 2.45
(27!/234907967154122528)^(1/27) = 2.48
https://oeis.org/A000170/list
(20!/39029188884)^(1/20) = 2.45
(27!/234907967154122528)^(1/27) = 2.48