• Почему сложность алгоритма (n+2n+3n+…+n⋅n) = O(n³)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Я так понял, вопрос в том, почему O(n+2n+...+n^2) = O(n^3)?

    Выписывать тут алгоритм для подсчета суммы в скобках вообще бессмыслено. Его сложность никак не связана с искомой. Это как для поиска длины строки, состоящей из цифр, считать их сумму или пытаться прочитать их как число. Ну бред же.

    Надо применить математику, ибо O() - это математический объект. Как вам уже сказали, надо подсчитать сумму арифметической прогрессии в скобках и получится кубический многочлен от n. Далее, по свойствам, О-большое, это будет кубическая сложность.
    Ответ написан
    Комментировать
  • Как изменить одновременно 10к+ совпадений строки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Любой нормальный редактор Через функцию find-replace all заменит сколько угодно строк в файле. Даже чертов notepad.exe справляется без проблем! Чем вы там вообще пользуетесь?
    Может вы там пытаетесь сначала список всех изменений посмотреть? Тогда может быть редактору плохеет все изменения показывать. Но какая-нибудь кнопочка replace all должна отработать без проблем.ы

    Чтобы в коде это все можно было менять быстро, заведите переменную, которую везде подставляйте вместо 1*multiplier. А вообще, похоже, что этот код уже сделан гибким - просто измените значение multiplier.
    Ответ написан
    7 комментариев
  • Как умно распараллелить вложенный цикл OpenMP?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Внешний цикл по итерацийм не распараллелить, потому что каждая итерация зависит от предыдущей.

    Внутри можно циклы по i объединить все в один.

    Ну и параллельте цикл по i через pragma omp for.
    Ответ написан
  • Как правильно реализовать алгоритм бинарного поиска?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, лучшее решение тут - это использовать структуру данных "бор", а не запускать бинарный поиск по сортированным строкам. Да, в конце-концов, какой-нибудь встроенный ассоциативный массив или словарь в вашем языке программирования может быть эффективнее вашего ручного бинарного поиска.

    Но если вам по заданию надо бинпоиск использовать, то у вас там следующие ошибки в реализации:
    - постоянное преобразование к toLowerCase - это ОЧЕНЬ неэффективно. Один раз все приведите к lowerCase и работайте только с этим. Можно эти ключи схоранить в новых полях.
    - когда вы нашли совпадение, можно делать из цикла break.

    Вы не сможете бинпоиском найти все объекты. Он может найти только один. Самый левый, самый правый, или как повезет - зависит от реализации.
    Вам надо запустить два бинпоиска последовательно. Один будет искать минимальный элемент, больше равный искомому (lower_bound), а второй бинпоиск будет искать максимальный элемент строго больший искомому (upper_bound). Пусть ваши бинпоиски возвращают индекс в массиве list. Эти две функции будут отличаться только в одном месте - там будет < и <= соответсственно.
    Ответ к задаче будет в массиве list по индексам от lower_bound (включительно) до upper_bound (не включительно). Может быть и так, что lower_bound == upper_bound, если искомого элемента в массиве нет и ответ будет пустым.
    Ответ написан
    2 комментария
  • Нейросети, пакеты, библиотеки, откуда такая сложность?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В общем-то, все просто, если у вас нейронов штук 100. Ну 1000 - тогда решение с помощью массивов и сработает, хоть и тормозить будет.

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

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

    Плюс сложность возникает, если вы хотите строить нейросети более абстрактно. Потому что руками задавать, что вот у вас 10000 нейронов, и первый связан с пятым, триннадцатым и еще вот этими 1000 - невозможно никак. Поэтому вводятся всякие слои и куча других абстракций, чтобы все это можно было в кучу собрать в 100 строчек кода, а не в 100 миллионов. Плюс куча абстракций чтобы можно было тренировать сети разными алгоритмами и все было гибко.

    Именно поэтому все эти универсальные библиотеки такие страшные.

    А decimal не работает, потому что у него не хватает точности. Плюс float работает быстрее ибо реализован аппаратно.
    Ответ написан
    4 комментария
  • Какое решение уравнения x^3 + y^3 = z^3 в дробных числах?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Решений в рациональных и целых числах нет: Великая теорема ферма.

    А в иррациональных - берете вообще любые x, y и по ним считаете z. Все.
    Например, x=10, y=1, z= 1001^(1/3)
    Или x = 20^(1/3), y= 7^(1/3), z=3
    Их континуум этих решений (бесконечно много).
    Ответ написан
    24 комментария
  • Как правильно реализовать алгоритм Дейкстры в Python с применением ООП?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это все ссылки. Вершина хранит ссылки на ребра, ребра хранят ссылки на вершины. Поэтому эта вложенность не страшна. Она - головная боль сборщика мусора (так называется часть менеджера памяти, которая освобождает ненужную больше память).

    Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

    В вашем подходе, чтобы получить соседнюю вершину надо взять ребро и посмотреть, какая их двух вершин не та изначальная. Или можно хранить только ориентированные ребра и все неориентированные придется раздваивать.
    Ответ написан
    Комментировать
  • Как решить задачу комивояжера с магией?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если свитков и точек интереса немного, то можно решать обходом в ширину на расширенном графе.

    Вершина в новом графе характеризуется четверкой чисел: (m, x, y, k) - m - маска уже посещенных интересных точек, x, y - координаты клетки, k - сколько свитков осталось. Ребра в графе хранить не надо, а стоит их рассчитывать на лету. Всегда можно пойти в 4 соседние стороны. При этом x, y, пересчитываются, k не меняется. Маска m получает новый бит, если конечная точка - одна из интересных (через битовое or. Если бит уже был установлен, он не меняется). Если k>0 - то можно телепортироваться. Перебирайте все x', y' в пределах 8 клеток от изначальной. Маска m получает новый бит, если конечная точка интересная. k уменьшается на 1.

    Вот по этим четверкам с заданными ребрами запускайте обход в ширину из точки (0, x_start, y_start, N). Как только доходите до точки с маской включающей все интересные точки - вы нашли кратчайший путь.

    Чтобы восстановить ответ вам надо для каждой четверки хранить, каким методом вы в нее попали (использовали ли свиток из какой-то точки, или просто пришли из соседней). Надо аккуратно пересчитывать предыдущую четверку в пути. Или можно тупо хранить для каждой четверки предыдущую четверку в пути.

    Это будет за O(W^2*H^2*N*2^M), если W,H - размеры поля, N - количество свиков, M - количество интересных точек.
    Ответ написан
  • Как вызвать появление меню в splitbutton?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если стоит visual studio, там есть утилита spy++. Она мониторит виндовые сообщения, приходящие выбранному окну.

    Запустите ваше приложение, натравите на него spy++, ткните в кнопку, чтобы появилось меню, и смотрите, какие сообщения и с какими параметрами приходят. Потом повторите их же в коде через postMessage.
    Ответ написан
    Комментировать
  • При выводе на экран список сокращается. Как сделать чтоб выводился весь список?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    pd.options.display.max_rows = 1000 перед выводом.
    Ответ написан
    3 комментария
  • Как сделать рекурсивную функцию, которая находит сумму нечетных элементов динамического массива на C?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Ошибка в том, что вы проверяете на четность сами элементы, а не их индексы. Вы суммируете нечетные числа. Если надо каждое второе число брать, то проверяйте на четность n.
    Ответ написан
  • Не знаете как можно исправить ошибки на с++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам надо описать конструктор Ball без параметров. Например:
    Ball() x(0), y(0), r(0), vx(0), vy(0) {}

    Потому что new Ball[n] Создает n объектов, но конструктора по умолчанию (без параметров) у класса Ball нет. Обычно его генерирует компилятор сам, но только если вы не указали никаких своих конструкторов. А new не знает, какие числа передавать в качестве x, y, r и т.д.

    Смотрите правило трех.
    Ответ написан
    Комментировать
  • Как конвертировать steady_clock::time_point в system_clock::time_point и наоборот?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Достоверно - никак.
    Можно попробовать получить значение двух часов рядом и взять разницу между ними как сдвиг. Но тут будет какая-то минимальная ошибка из-за задержки между двумя вызовами. И, если пользователь поменяет часовой пояс в настройках системы, system_clock скакнет на несколько часов, поэтому надо по уму делать эту операцию каждый раз, когда вы хотите перевести одни часы в другие. И это дорого.

    Вообще, если вам надо эти двое часов переводить в друг друга, то вы что-то не так делаете.
    Ответ написан
    Комментировать
  • Как можно передать структуру в printf, а к переменным её обращаться из шаблона?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Во встроенный printf вы это не добавите никак. Придется писать собственную обертку и там парсить строку формата.
    Так, чтобы это работало со всеми структурами, у которых есть член int a - нужны шаблоны, да. Гуглите variadic template, но это мрак и ужас. В любом случае это будет весьма громоздкий и непонятный код.

    Но раз уж у вас C++, то вы вместо printf используйте cout. Переопределите operator<< для ostream и вашей структуры и выводите через cout << *s1.

    Да, тут не получится в каждом конкретном месте вызова менять формат вывода, он будет одинаков везде - но так ли вам это нужно, чтобы городить костыли с printf?
    Ответ написан
    Комментировать
  • Как сделать перестановку с повторением в C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Надо руками реализовывать nextpermutation, оно же алгоритм Нарайаны.

    Вот есть статья на хабре, даже с кодом, правда на go.

    Но сам алгоритм там простой, без труда переведете на си++.
    Ответ написан
    9 комментариев
  • Ошибка вывода списка C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    cout умеет сам по себе выводить только базовые типы: int, char, string, и т.д.

    Ошибка об этом и говорит, что никто не реализовал оператор << для списка.

    Если вы хотите выводить список, вам надо руками реализовать этот вывод. Циклом пройдитесь по всем элементам и выводите их, разделяя пробелами или чем вам там надо.

    еще можно перегрузить оператор << для списка, тогда код в main останется без изменения, но тот же самый цикл придется все равно написать в операторе.
    Ответ написан
    Комментировать
  • Как сделать масштабирование правильно?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Считайте сдвиг так, чтобы точка в центре (или под курсором мыши) оставалась неподвижна.

    Т.е. у вас будут приотображентии не только константы растяжения, но и сдвига.
    Ответ написан
  • Какая временная сложность у простого алгоритма вычисления факториала (О большое)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Линейная сложность и там и там.
    Ответ написан
    Комментировать
  • Пишет что повредил кучу? Чего?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Это ошибка работы с памятью. Или выход за границы массива, или неправильная работа с указателями. Использование после free, или не выделение памяти.

    Чтобы исправить, надо аккуратно посмотреть за каждым указателем, где просиходит malloc, где указатель используется, какого размера там память и нет ли выхода за границы массива.
    Ответ написан
    Комментировать
  • Как обращаться к динамическому массиву, инициализированному в классе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Figure** figure_colletion = new Figure * [this->collection_size];


    Вот тут в конструкторе вы заводите локальную переменную (с тем же именем, что и член класса) и что-то с ней делаете. Она "затенняет" член класса. А вот figure_colletion, к которому вы обрашаетесь в методе select_new_figure() - это уже член класса, который вы нигде не выделили и ничем не заполнили.

    Поэтому любой уважающий себя стиль форматирования кода подразумевает, что члены класса должны быть приватными и как-то по особому именоваться (например, заканчиваться на "_", или начинаться с "p") тогда бы вы этой ошибки не совершили. Еще можно включить предупреждения при компиляции.

    И еще, писать в методах this-> перед каждым обращением к члену класса не обязательно.
    Ответ написан
    1 комментарий