Ответы пользователя по тегу Алгоритмы
  • Как просчитать "свободную" орбиту для своего спутника?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    eegmak, я намекаю на то, что для практически осуществимого любительского запуска вопрос "рассчитать, чтобы ни с кем не столкнуться" не стоит вообще. Если вопрос теоретический, то, насколько мне известно, носитель доставляет в заданную точку с заданным вектором скорости, а дальше берут модель сил действующих на спутник и тупо интегрируют уравнения движения по этой модели. Сложность модели варьируется в зависимости от нужной точности и ожидаемого соотношения величин действующих на него сил. Можно начать со сферической земли в вакууме, можно с эллиптической, можно добавить геоидность и вращение, добавить атмосферу, добавить действие луны и солнца…
    Ответ написан
  • Как искать значение в сбалансированном бинарном дереве?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как искать значение в сбалансированном бинарном дереве?

    Так же, как и в несбалансированном. Сбалансированность на стратегию поиска никак не влияет. Влияет логика построения дерева.

    Чтобы создать из этого сбалансированное дерево я беру элементы с индексом floor(arr.length / 2)

    С такой логикой элементы равные данному могут попасть как в левое поддерево, так и в правое. Чтобы найти их все нужно будет сканировать оба поддерева, если корень равен искомому числу.

    Ну да я нашел первый на самом верху дерева, ну а потом? Левый узел меньше тройки а правая больше, но под правым узлом есть еще тройка. По какой логике надо искать ?

    Если текущий корень больше искомого -- идти в левое поддерево, Если меньше -- идти в правое. Если равен -- то найдено, после чего идти в оба поддерева.
    Ответ написан
    3 комментария
  • Как работает данный алгоритм проверки числа на простоту и какой у него Big O??

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как работает данный алгоритм проверки числа на простоту

    Данный алгоритм работает неправильно, первая ошибка состоит в том, что происходит обращение к неинициализированным элементам массива a.
    Ответ написан
    Комментировать
  • Как поменять порядок битов в байте C?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как поменять порядок битов в байте C?

    Посмотреть какой бит стоит на каждом месте и поставить такой же на каждом новом месте?
    Можно обойтись без сдвигов. Удобно пользоваться битовыми операциями, но можно обойтись и без них. Это можно сделать одной чистой арифметикой. Для ускорения можно анализировать не отдельные биты а группы -- например по 2 или по 4 и выполнять для них замену по таблице.
    Ответ написан
    Комментировать
  • В чем логическая ошибка сигсегва?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    В чем проблема

    ну например find_index_bigger_element может вернуть -1, но ты это не проверяешь и сразу используешь полученный индекс в swap
    Ответ написан
  • Верно ли написал бинарный поиск?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Верно ли написал бинарный поиск?

    Не, неверно. Попробуй им найти 1 в массиве {0, 1}.
    Ответ написан
  • Preimage - атака нахождения прообраза. Теория + практика. Пофантазируем?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Сколько понадобится компов объединённых вместе, чтобы решить эту задачу (мою и автора вопроса по ссылке)?

    Решение этой задачи перебором идеально распараллеливается, даже в уме. Поэтому если взять N компов, решение найдётся в N раз быстрее.

    На своём ноуте с картой NVIDIA GTX 1050 Ti мне бы понадобилось около 150 лет... :)

    Соответственно, 150 таких компов справятся за год, а 1314000 таких компов -- за час.
    Ответ написан
    3 комментария
  • Предикаты. Логические предикаты. Тестирование?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    почему формула для вычисления ветвей предикатов 2^n а не 2*n, ведь количество путей ровно в два раза больше

    Количество путей удваивается на каждом предикате.

    2.По второму фото: почему самый верхний путь когда ветви разошлись на Истину и Ложь, Ложь пошла в Истину ?

    Явная ошибка на рисунке.
    Ответ написан
    Комментировать
  • Как решить задачу итеративным процессом?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    f(n) = n, если n < 3, f(n) = f(n−1) +f(n−2) +f(n−3), если n ≥ 3

    Ну, начиная с четвёртого значения равны сумме предыдущих трёх. В чем сложность?

    int f(int n)
    {
        int v[3] = {0, 1, 2};
        int i;
        if (n < 3)
            return n;
        for (i = 3; i <= n; ++i)
            v[i % 3] = v[0] + v[1] + v[2];
        return v[n % 3];
    }
    Ответ написан
    Комментировать
  • Алгоритм поворота динамического массива без доп памяти?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как можно реализовать, поворот динамического массива (матрица), без доп памяти?

    Как-то так:

    #include <stddef.h>
    #include <stdio.h>
    
    typedef int T;
    
    void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
    {
            size_t i, j, k;
    
            for (i = 0; i < m * n; ++i) {
                    T tmp0, tmp1;
    
                    for (j = 0; j < i; ++j) {
                            for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
                            }
                            if (k == i)
                                    break;
                    }
                    if (j < i)
                            continue;
    
                    tmp0 = p[i];
                    for (j = turn(m, n, i); ; j = turn(m, n, j)) {
                            tmp1 = p[j];
                            p[j] = tmp0;
                            tmp0 = tmp1;
                            if (j == i)
                                    break;
                    }
            }
    }
    
    void dump(size_t m, size_t n, T p[m][n])
    {
            size_t i, j;
    
            for (i = 0; i < m; ++i)
                    for (j = 0; j < n; ++j)
                            printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
    }
    
    size_t turn_ccw(size_t m, size_t n, size_t idx)
    {
            return (n - 1 - idx % n) * m + (idx / n);
    }
    
    size_t turn_cw(size_t m, size_t n, size_t idx)
    {
            return (idx % n) * m + m - 1 - (idx / n);
    }
    
    #define M 5
    #define N 7
    
    int main()
    {
            size_t i, j;
            T a[M][N];
    
            for (i = 0; i < M; ++i)
                    for (j = 0; j < N; ++j)
                            a[i][j] = i * N + j;
    
            rotate(&a[0][0], M, N, turn_ccw);
            dump(N, M, (T (*)[M])&a[0][0]);
            printf("\n");
            rotate(&a[0][0], N, M, turn_cw);
            dump(M, N, (T (*)[N])&a[0][0]);
    }


    turn преобразует линейный индекс элемента из оригинального массива в индекс элемента в повёрнутом массиве.
    Цикл по i переставляет цепочки элементов отображающихся друг в друга с началом в элементе i. Первый цикл по j проверяет, не был ли элемент i уже переставлен в составе более ранней цепочки. Второй цикл по j переставляет одну цепочку.
    Ответ написан
    Комментировать
  • Как сделать массив немножко отсортированным?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Есть такой массив (50 элементов):
    Задача: написать функцию которая полностью отсортирует данные максимум за 6 вызовов, с условием что за 1 вызов ни один элемент не сместиться больше чем на 5 позиций.

    Очевидно, что задача в такой постановке в общем случае неразрешима, т.к. максимальный элемент стоящий первым должен сместиться в процессе сортировки в самый конец, т.е. на 49 позиций, а 49 > 6 * 5.
    Ответ написан
    1 комментарий
  • Задача по олимпиаде?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Запишем последовательность блинов цифрами 0 (светлой стороной вверх) и 1 (тёмной стороной вверх). Назовём инверсией переход с 1 на 0 или с 0 на 1. Один переворот стопки может добавить или убавить максимум одну инверсию на границе между переворачиваемой и не переворачиваемой частями (все инверсии внутри переворачиваемой части сохраняются, только меняют знак). Следовательно минимальное число переворотов для устранения всех инверсий равно числу инверсий в исходной стопке блинов. Если первый блин лежит тёмной стороной вверх для решения задачи потребуется ещё один переворот всей стопки.
    Ответ написан
    Комментировать
  • Как написать алгоритм движения по спирали на Arduino?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    к сожалению, я не силен и был бы благодарен за помощь.

    Этот сайт работает немного по-другому. Сюда приходят с конкретными вопросами чтобы получить на них ответ.
    Я вижу следующие несколько первых вопросов для вашей задачи:
    1 какая спираль имеется в виду? (архимедова/логарифмическая/с прямыми углами/...?)
    2 как нужно управлять колёсами, чтобы заставить тележку двигаться по выбранной в п.1 спирали?
    3 как запрограммировать ардуино, чтобы она управляла двигателями тележки в соответствии с п.2?

    Определитесь с п.1 и 2 для начала, они не требуют знания ардуины. После этого разберитесь со своей схемой -- что там за двигатели, как они подсоединены к колёсам, как управляются. И если после этого останутся вопросы по п.3 -- приходите.
    Ответ написан
    4 комментария
  • Как называется алгоритм??

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как называется алгоритм??

    Быстрое возведение a в степень b. По модулю m.
    Ответ написан
    Комментировать
  • Как сравнить два числа в коде Грея?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Смысл младших битов кода Грея зависит от значения старших битов, поэтому вряд ли можно избежать перевода значения из кода Грея в обычный двоичный. Если битность кода фиксированная и небольшая, скорее всего оптимальный вариант -- перевести в двоичный код и сравнить. Если битность большая или переменная, то можно переводить и одновременно сравнивать уже переведённые биты и останавливаться на первом неравенстве. См.
    Ответ написан
  • Оптимизировать код или как выделить всю вычислительную мощность пк на его выполнение?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Скопировать исходный массив A в массив B, дополнить каждый элемент индексом в исходном массиве, отсортировать по значению элементов. Завести массив C такого же размера как исходный, заполнить его нулями.
    Сделать текущим первый элемент А.

    Начало цикла.
    Отметить в C текущий элемент. Найти в массиве B текущий элемент элемент. Просмотреть соседние элементы B и отметить в С как отсечённые все те, диапазоны которых пересекаются с текущим. Найти следующий не отмеченный элемент С, сделать его текущим, перейти к началу цикла, если все элементы C отмечены -- закончить.

    Количество действий зависит от количества пересекающихся отрезков, оно будет больше O(N log N) но меньше N^2.
    Ответ написан
    Комментировать
  • Есть ли универсальный алгоритм для задач 'Можно ли переложить 1 спичку, чтобы равенство стало верным'?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Как это сделать программно?

    Найти все возможные положения в которые можно положить спичку. Найти все допустимые фигуры из спичек. Вывести значение каждой допустимой фигуры и каждой комбинации допустимых фигур. Пройти по всем спичкам, каждую спичку переложить во все возможные положения, проверить, допустимы ли все образовавшиеся фигуры и их комбинация и вычислить значение получившегося выражения. Звучит просто, не правда ли?
    Ответ написан
    2 комментария
  • Почему в решениях с одинаковой сложностью существенная разница во времени расчета?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Почему в решениях с одинаковой сложностью существенная разница во времени расчета?

    Я отвечу на вопрос из заголовка: потому что сложность алгоритма говорит о том, как он будет вести себя при неограниченном увеличении размерностей входных данных. И больше ни о чём. Т.е. нельзя имея два линейных алгоритма сказать, что они будут работать одинаковое время. Но можно имея линейный и квадратичный алгоритм сказать, что начиная с какого-то момента линейный всегда будет работать быстрее.
    Ответ написан
    2 комментария
  • Как разобрать унарный оператор в обратной польской нотации?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    Все хорошо, но алгоритм не верно работает с унарным отрицанием.

    Он и не рассчитан на работу с унарным отрицанием.
    Как исправить?

    Проще всего -- введя для унарного отрицания специальный символ, отличный от остальных операторов.
    Иначе придётся вводить дополнительное состояние -- был ли предыдущий символ и был ли он оператором, и если так, то трактовать непосредственно следующий за ним оператор '-' как унарный.
    Ответ написан
    2 комментария
  • Не получается сортировка пузырьком. В чем проблема?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    for (b = sortArray.length; b != 1; b--){
          int1 = sortArray[b];

    Что скажете?

    Ошибка в индексации.
    Ответ написан
    3 комментария