Уменьшение числа валидных расстановок означает, что у нас реже будет возможность поставить ферзя и зайти в рекурсию (что уменьшает и глубину рекурсии как следствие).
При этом если мы имеем N цветов/ферзей и допустим что клеток каждого цвета поровну, то получим (для N = 8) что из исходных 64! / (56!*8!) расстановок ферзей только 8^8 (расстановок по 1 ферзю внутри N областей по N ячеек) будут подходить под условие цвета (без прочих условий). То есть уменьшение числа расстановок схоже с эффектом от проверки (только) горизонталей. Неравномерная раскраска же уменьшает количество расстановок ещё больше. Крайний случай = если возьмем 7 областей по 1 ячейке и одну область на 57, то расстановок вообще останется 57 без прочих проверок.
Поэтому я и предположил, что в среднем время поиска должно падать.
В случае когда мы ищем только первое решение из многих конечно получается что поиск может наоборот удлиняться (как и от остальных проверок), но в случае, когда решение всего одно (или их крайне мало относительно числа исходных перестановок) - нам нет большой разницы, ищем ли мы все решения или первое.
С проверкой цветов нюанс в том, что в худшем случае она вообще не влияет, а в лучшем упрощает решение до полинома (количество валидных расстановок может упасть пропорционально ~N-1!), но вот что там в среднем - вопрос хороший. Но я согласен - на верхнюю оценку действительно не влияет и она будет в районе N!
Неправильно делается вывод о сложности алгоритма. В худшем случае для первой строки придется N раз перебирать вторую строку, в которой в худшем случае N раз перебирать третью и т.д..
Итого получаем N^M где M число строк, ну или N^N для квадратной доски.
Эта верхняя оценка сильно сокращается проверками горизонталей, вертикалей и диагоналей (до N!). Дальше сокращается проверками цветов.
И вот на этапе проверки цветов (при условии что цветов тоже N), сложность должна радикально сокращаться, возможно до полинома, но посчитать конкретно мне способностей уже не хватает. Возможно следующий комментатор сможет раскрыть мою мысль.
Можно ещё отметить, что для областей цвета из 1 ячейки, в случае когда цветов столько сколько ферзей, известно что во всех таких ячейках будет стоять ферзь (на верхнюю оценку не влияет, но на практике такая оптимизация могла бы сильно ускорить решение)
Мы играли с другом, класс игры у нас очень средний (непрофессионалы), но зачастую эти "лучшие" ходы мы тоже видели (и ходили так в тот момент). И вот прикол - человек при ходе, перебирает наверное около 100 позиций
Компьютеру не надо перебирать обязательно 5 млн позиций, чтобы найти этот ход. Он перебирает 5 млн позиций, чтобы убедиться, что этот ход действительно лучший (насколько точно убедиться позволяют вычислительные мощности), и другой ход не дает больше преимущества через 15 ходов. И как следствие он играет не на "том же уровне", а на 10 голов выше всех чемпионов мира вместе. Если ограничить компьютер глубиной, на которой считает средний человек (~6-8 полуходов), то считать он будет намного меньше (не 100 позиций конечно, но в тысячах), но и средний уровень игры падает до продвинутого любителя. Другая часть перебора - это анализ ходов в поисках тактик, которые человек часто бракует моментально (случайные взятия и шахи например, или полный перебор на небольшую глубину) - но как следствие, несмотря на менее эффективные вычисления, и в этой области компьютер делает ходы точнее человека.
Мне кажется, что на определенном темпе продуктивности программиста, он начнет просто опережать инерционные бизнес процессы. Если фича готова за день, а не за месяц, в какой-то момент планы на фичи просто не будут успевать появляться (это конечно касается не всего бизнеса в принципе, но относимо к разным малым и средним). Однако, о чём я не подумал - бизнес может наверное как-то использовать (гипотетический) аги, чтобы выкатывать бизнес требования тоже в 10 раз быстрее (чаще). Тогда да, вы правы.
Ну с аги программисты быстро "вымрут". Потребность в программистах ранее поднялась, потому что много бизнесов и всем нужны айти продукты. Но в чисто количественный потолок уже +- упёрлись. Поэтому если опять поднять программистам в 10 раз производительность, уже начнет быстро падать необходимое число. Либо нужен какой то скачок в размерах ПО для бизнеса. Но без прогресса железа и сетей такого не видится пока что.
Пузырек - это сортировка пузырьком. Под хитрой сортировкой я имел в виду, например, сортировку по 2 и более полям (особенно если по возрастанию одного и убыванию второго), сортировку ссылочных типов.. в общем - сортировку используя самописную функцию-комбинатор.
Если бы задача стояла НЕ крутить списки то решал бы так :
Посчитать проходом по спискам отступ между головами.
Затем вторым проходом посчитать суммы по разрядам (без переноса), с записью в больший список.
Самое интересное это переносы. Последовательности вида "9 10" мы можем в наивном решении(два указателя current, next) устранить одним проходом. Но каждая девятка в последовательности увеличивает число проходов на один.
Чтобы этого избежать, будем крутить доп. цикл пока next = 9 (либо дойдем до 10+ и обновим значение по адресу current, а затем сменим current, либо встретим 8- и закончим цикл со сменой current). Временные затраты это не увеличит, затраты по памяти тоже, решение мне нравится.
Остаётся только проблема переноса из старшего разряда, но она на связных списках тривиальна.
Итого получаем 2N + M по времени (длины списков) и N+M по памяти (можно уменьшить до N если хранить исходные списки в ПЗУ, и можно ещё попытаться запихнуть список сумму в файл, но там труднее)
И это я за последние 3 года ни разу алгоритмических задач такого плана не решал. Предполагаю что мое решение не идеально.
На 1с периодически пишу пузырек, т.к иногда написать пузырек под какую нибудь хитрую сортировку будет быстрее чем библиотечный код написать. А то что он квадратный мне пофигу - массив на <100 элементов можно хоть молитвой сортировать
Я бы вывел в целом "Непрозрачность уровня ЗП". Имхо в хорошей организации большинство должно хотя бы примерно знать, сколько получает (большинство) коллег. В ту же топку грейды, за которыми не закреплена конкретная сумма.
Ну как минимум главбух конторы на 50 человек может пойти в контору на 5000 человек и получить там совсем другой опыт. Водитель ( и многие другие) может пойти вверх по принципу "строже и дороже". Конечно далеко не у всех потолок роста в 15 лет, но все таки, далеко не у всех он 0. А "сын генерала" это как раз весомая причина увольнения - у какого-то генерала сына "на месте" да не найдётся
Да, это какой то запредельный уровень бреда. Спросите уборщицу с месячной зарплатой в 200 долларов, есть ли у нее 100-200 долларов, и сколько лет она жила на койке в бараке, дожидаясь очередь на однушку. Потом можно спросить у американца "среднего класса" с зарплатой в 50-100 долларов за час, существенная ли для него сумма в 200 долларов.
Вот армия это буквально пик прикладной плановой экономики. Солдат обеспечен всем - едой, одеждой, жильем, но кроме того что он "потерял", того что "уже выдали в этом году", того что "до нас не дошло" - тут уж придется помощь извне запрашивать. Спасибо рынку что есть ларек у части.
А как будете решать кому сколько стейков надо? Вот комментатор выше человек активный, ему надо по 2 в неделю, а у меня на мясо аллергия, мне куда свои стейки по норме девать? Менять у комментатора выше на секс игрушки? Или же можно будет вместо карточки на стейки получить карточку на игрушки? А кто будет определять курс обмена? А как он будет корректироваться со временем? Игрушки надоедают, в ценности явно потеряют через несколько лет таких планов. И если официальная позиция меня не устроит - что мне мешает устроить рыночную экономику в рамках моего района и менять стейки на игрушки по цене, которая мне кажется более справедливой?
Уменьшение числа валидных расстановок означает, что у нас реже будет возможность поставить ферзя и зайти в рекурсию (что уменьшает и глубину рекурсии как следствие).
При этом если мы имеем N цветов/ферзей и допустим что клеток каждого цвета поровну, то получим (для N = 8) что из исходных 64! / (56!*8!) расстановок ферзей только 8^8 (расстановок по 1 ферзю внутри N областей по N ячеек) будут подходить под условие цвета (без прочих условий). То есть уменьшение числа расстановок схоже с эффектом от проверки (только) горизонталей.
Неравномерная раскраска же уменьшает количество расстановок ещё больше. Крайний случай = если возьмем 7 областей по 1 ячейке и одну область на 57, то расстановок вообще останется 57 без прочих проверок.
Поэтому я и предположил, что в среднем время поиска должно падать.
В случае когда мы ищем только первое решение из многих конечно получается что поиск может наоборот удлиняться (как и от остальных проверок), но в случае, когда решение всего одно (или их крайне мало относительно числа исходных перестановок) - нам нет большой разницы, ищем ли мы все решения или первое.
С проверкой цветов нюанс в том, что в худшем случае она вообще не влияет, а в лучшем упрощает решение до полинома (количество валидных расстановок может упасть пропорционально ~N-1!), но вот что там в среднем - вопрос хороший. Но я согласен - на верхнюю оценку действительно не влияет и она будет в районе N!
Неправильно делается вывод о сложности алгоритма. В худшем случае для первой строки придется N раз перебирать вторую строку, в которой в худшем случае N раз перебирать третью и т.д..
Итого получаем N^M где M число строк, ну или N^N для квадратной доски.
Эта верхняя оценка сильно сокращается проверками горизонталей, вертикалей и диагоналей (до N!). Дальше сокращается проверками цветов.
И вот на этапе проверки цветов (при условии что цветов тоже N), сложность должна радикально сокращаться, возможно до полинома, но посчитать конкретно мне способностей уже не хватает. Возможно следующий комментатор сможет раскрыть мою мысль.
Можно ещё отметить, что для областей цвета из 1 ячейки, в случае когда цветов столько сколько ферзей, известно что во всех таких ячейках будет стоять ферзь (на верхнюю оценку не влияет, но на практике такая оптимизация могла бы сильно ускорить решение)
Что кстати примерно равно скорости при падении с высоты 1м без учета сопротивления воздуха.
Компьютеру не надо перебирать обязательно 5 млн позиций, чтобы найти этот ход. Он перебирает 5 млн позиций, чтобы убедиться, что этот ход действительно лучший (насколько точно убедиться позволяют вычислительные мощности), и другой ход не дает больше преимущества через 15 ходов. И как следствие он играет не на "том же уровне", а на 10 голов выше всех чемпионов мира вместе. Если ограничить компьютер глубиной, на которой считает средний человек (~6-8 полуходов), то считать он будет намного меньше (не 100 позиций конечно, но в тысячах), но и средний уровень игры падает до продвинутого любителя. Другая часть перебора - это анализ ходов в поисках тактик, которые человек часто бракует моментально (случайные взятия и шахи например, или полный перебор на небольшую глубину) - но как следствие, несмотря на менее эффективные вычисления, и в этой области компьютер делает ходы точнее человека.
Мне кажется, что на определенном темпе продуктивности программиста, он начнет просто опережать инерционные бизнес процессы. Если фича готова за день, а не за месяц, в какой-то момент планы на фичи просто не будут успевать появляться (это конечно касается не всего бизнеса в принципе, но относимо к разным малым и средним). Однако, о чём я не подумал - бизнес может наверное как-то использовать (гипотетический) аги, чтобы выкатывать бизнес требования тоже в 10 раз быстрее (чаще). Тогда да, вы правы.
Ну с аги программисты быстро "вымрут". Потребность в программистах ранее поднялась, потому что много бизнесов и всем нужны айти продукты. Но в чисто количественный потолок уже +- упёрлись. Поэтому если опять поднять программистам в 10 раз производительность, уже начнет быстро падать необходимое число. Либо нужен какой то скачок в размерах ПО для бизнеса. Но без прогресса железа и сетей такого не видится пока что.
3N + M, извиняюсь
Пузырек - это сортировка пузырьком. Под хитрой сортировкой я имел в виду, например, сортировку по 2 и более полям (особенно если по возрастанию одного и убыванию второго), сортировку ссылочных типов.. в общем - сортировку используя самописную функцию-комбинатор.
Если бы задача стояла НЕ крутить списки то решал бы так :
Посчитать проходом по спискам отступ между головами.
Затем вторым проходом посчитать суммы по разрядам (без переноса), с записью в больший список.
Самое интересное это переносы. Последовательности вида "9 10" мы можем в наивном решении(два указателя current, next) устранить одним проходом. Но каждая девятка в последовательности увеличивает число проходов на один.
Чтобы этого избежать, будем крутить доп. цикл пока next = 9 (либо дойдем до 10+ и обновим значение по адресу current, а затем сменим current, либо встретим 8- и закончим цикл со сменой current). Временные затраты это не увеличит, затраты по памяти тоже, решение мне нравится.
Остаётся только проблема переноса из старшего разряда, но она на связных списках тривиальна.
Итого получаем 2N + M по времени (длины списков) и N+M по памяти (можно уменьшить до N если хранить исходные списки в ПЗУ, и можно ещё попытаться запихнуть список сумму в файл, но там труднее)
И это я за последние 3 года ни разу алгоритмических задач такого плана не решал. Предполагаю что мое решение не идеально.
На 1с периодически пишу пузырек, т.к иногда написать пузырек под какую нибудь хитрую сортировку будет быстрее чем библиотечный код написать. А то что он квадратный мне пофигу - массив на <100 элементов можно хоть молитвой сортировать
Выход - берём ипотеку на 9000, и привыкаем есть гречку
Я бы вывел в целом "Непрозрачность уровня ЗП". Имхо в хорошей организации большинство должно хотя бы примерно знать, сколько получает (большинство) коллег. В ту же топку грейды, за которыми не закреплена конкретная сумма.
Ну как минимум главбух конторы на 50 человек может пойти в контору на 5000 человек и получить там совсем другой опыт. Водитель ( и многие другие) может пойти вверх по принципу "строже и дороже". Конечно далеко не у всех потолок роста в 15 лет, но все таки, далеко не у всех он 0. А "сын генерала" это как раз весомая причина увольнения - у какого-то генерала сына "на месте" да не найдётся
Если что-то отсутствует (недостаточно) - то уходят ЗА. Если что-то должно отсутствовать (переизбыток) - уходят ОТ
Иногда я так рад, что у нас одни и те же рекомендации
Вы уж или трусы наденьте, или крестик снимите
Да, это какой то запредельный уровень бреда. Спросите уборщицу с месячной зарплатой в 200 долларов, есть ли у нее 100-200 долларов, и сколько лет она жила на койке в бараке, дожидаясь очередь на однушку. Потом можно спросить у американца "среднего класса" с зарплатой в 50-100 долларов за час, существенная ли для него сумма в 200 долларов.
Вот армия это буквально пик прикладной плановой экономики. Солдат обеспечен всем - едой, одеждой, жильем, но кроме того что он "потерял", того что "уже выдали в этом году", того что "до нас не дошло" - тут уж придется помощь извне запрашивать. Спасибо рынку что есть ларек у части.
А как будете решать кому сколько стейков надо? Вот комментатор выше человек активный, ему надо по 2 в неделю, а у меня на мясо аллергия, мне куда свои стейки по норме девать? Менять у комментатора выше на секс игрушки? Или же можно будет вместо карточки на стейки получить карточку на игрушки? А кто будет определять курс обмена? А как он будет корректироваться со временем? Игрушки надоедают, в ценности явно потеряют через несколько лет таких планов. И если официальная позиция меня не устроит - что мне мешает устроить рыночную экономику в рамках моего района и менять стейки на игрушки по цене, которая мне кажется более справедливой?