Пользователь пока ничего не рассказал о себе

Достижения

Все достижения (4)

Наибольший вклад в теги

Все теги (49)

Лучшие ответы пользователя

Все ответы (206)
  • Как решить задачу на сложность алгоритмов ниже?

    wataru
    @wataru
    г) не правильно подсчитано.

    Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

    Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
    Ответ написан
  • Где мне может понадобится линейная алгебра?

    wataru
    @wataru
    Нейросети, машинное обучение всякое. Там сплошные матрицы, вектора и линейные операторы.

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

    wataru
    @wataru
    Вам ДАНА матрица. Значит в программе надо
    1) прочитать числа N и M (заведите 2 переменные и прочитайте их, через cin)
    2) Завести N*M матрицу. В C++ стандартом для массивов является класс vector. Двумерный массив - это вектор векторов.
    vector<vector<int>> a(n);
    Это создаст вектор из n векторов, но они все будут пустые. Надо во время считывания ( у вас будет 2 вложенных цикла) перед считыванием i-ой строки i-ый вектор отресайзить вызвав a[i].resize(m). И далее можно будет читать a[i][j]
    3) Теперь, собственно, алгоритм. Найдите наибольший элемент. Для этого заведите 3 переменные - текущий максимум (можно инициализировать a[0][0]) и его координаты mx и my (инициализируйте нулями). Пройдитесь по матрице двумя вложенными циклами и, если текущий элемент больше максимума - перезапишите максимум и запомните текущие переменные циклов в mx и my.
    4) Теперь поменяйте местами 0-ую строку со строкой в которой максимум. Для этого одним циклом пройдитесь по столбцам (от 0 до M-1) и поменяйте местами a[0][j] и a[mx][j].
    5) Теперь то же самое, но по столбцам. Цикл от 0 до N-1 и меняйте элементы a[i][0] и a[i][my].
    6) В конце выведите матрицу двумя вложенными циклами.

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

    wataru
    @wataru
    При умножении на маленькое число всякие хитрые алгоритмы типа преобразования Фурье или Карацубы лаже медленнее тупого умножения в лоб: Просто проходитесь по большому числу от младших разрядов к старшим, умножете на маленький множитель, прибавляете перенос. Потом берете остаток от деления на базу (если множитель маленький, то быстрее будет просто вычесть несколько раз в цикле вместо модуля), а результат целочисленного деления записываете в перенос.
    Ответ написан
  • Используются ли рекурсивные алгоритмы в олимпиадах по программированию?

    wataru
    @wataru
    По заголовку: Рекурсивные алгоритмы используются очень часто.

    Если то же самое решение можно написать чисто итерационно, то так будет быстрее, но не намного. Я не помню ни одного случая, когда условное переписывание с DFS на BFS побороло бы time limit. Больше скорости можно выиграть просто развернув циклы в правильную сторону, чтобы в кэш попадать.

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

    Кроме того, рекурсивные алгоритмы часто гораздо быстрее и проще написать, что тоже весьма важно на олимпиаде.

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

    Подводя итог - не стоит как-то специально избегать рекурсивных алгоритмов, потому что они, якобы, медленнее.

    Есть только один важный момент - размер стека. Если у вас может быть 100000 рекурсивных вызовов, то в стандартный размер стека это счастье не влезет и программа упадет с runtime error. Не знаю, как сейчас, подкручен ли размер стека на этапе компиляции. Но в свое время мы всегда увеличивали размер стека в C++ через ```“#pragma comment(linker, ”/STACK:2000000“)``` или что-то подобное.
    Ответ написан