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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Угу. Туда же попадут "автор", "автохтон", "автобиография", "автомат"... А уж слова с приставками... По хорошему, надо разделять слова на приставку, корень (корни), суффикс и окончание, для чего желательно знать, как минимум роль слова в предложении (и то может не помочь, попробуйте разобрать "Косил косой косой косой" - да, тот самый заяц на поляне, да ещё и коса кривая.
    Но если так хочется - строите дерево, где каждый уровень - следующая буква слова, а в узлах и листьях стоят счётчики количества слов. Для слов "автомобиль", "авто" и "автострада" получаем:
    .                   +-м(1)-о(1)-б(1)-и(1)-л(1)-ь(1)
    .а(3)-в(3)-т(3)-о(3)+
    .                   +-с(1)-т(1)-р(1)-а(1)-д(1)-а(1)
    Затем обходим дерево, там где сумма счётчиков в дочерних узлах не равна счётчику в родительском - заканчивается слово, а разность между суммами даёт количество этих слов в тексте.
    Ответ написан
    Комментировать
  • Как наиболее эффективно проверить вхождение последовательности в массиве?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если надо проверить именно на непрерывную последовательность - то это поиск подстроки на алфавите x,y,z,...
    Ответ написан
    Комментировать
  • Хранение хэшей в mysql и потребление памяти. Какой алгоритм выгодней?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    1. Хранить можно по разному. Можно, например, разбить таблицу на 2n таблиц по первым битам хэша (table_00, table_01, ... table_ff).
    2. Хэш, как таковой, не гарантирует однозначного отображения, то есть вполне вероятен вариант, когда две разные строки будут иметь один и тот же хэш. Для n-битного хэша перебор 2n/2 строк выдаст два одинаковых значения хэша с вероятностью 63% (парадокс дней рождения). По таблице можете оценить, какая вероятность коллизии будет для вашего количества строк при разной длине хэша.
    Ответ написан
    Комментировать
  • Как составить все возможные комбинации размещения 10 яблок на 21 тарелке?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Условие неполное. Считаются ли яблоки уникальными или одинаковыми? Какое максимальное количество яблок может лежать на одной тарелке?
    Ответ написан
    Комментировать
  • Как из польской нотации получить АСТ дерево?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    последовательно читаем выражение, для каждой лексемы по её типу:
    число -> создать ноду (ЧИСЛО, значение), положить её на стек;
    унарный оператор -> снять со стека ноду (потомок), создать ноду (УНАРНАЯОПЕРАЦИЯ, тип, потомок), положить новую ноду на стек;
    бинарный оператор -> снять со стека две ноды (потомок1 и потомок2), создать ноду (БИНАРНАЯОПЕРАЦИЯ, тип, потомок1, потомок2), положить новую ноду на стек;
    функция -> снять со стека N нод по числу аргументов функции (потомок1,... потомокN), создать ноду (ФУНКЦИЯ, имя, потомок1,... потомокN), положить новую ноду на стек;

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если речь идёт об абстрактной математике, то надо рассматривать представление плавающего типа (float, double, long double) в конкретной архитектуре. В большинстве случаев используется IEEE 754-1985. Скажем, для float32 в нормализованной форме точность - то есть единица младшего разряда мантиссы - в зависимости от экспоненты может быть от 1.175494351×10−38 до 3.402823466×1038.

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для разбиения на две группы задача сводится к задаче о рюкзаке с весом рюкзака равным половине общего веса камней и ценностью камней равной их весу.
    Ответ написан
    2 комментария
  • Как написать алгоритм для для поиска кратчайшего расстояния?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Тогда придётся повторно пересматривать вершины если для них нашёлся более короткий путь.
    Пример:
    .  A  B  C
    A  -  4  1
    B  4  -  1
    C  1  1  -

    Начальная точка A (A = 0). Строим пути из A (B = 4, C = 1), добавляем их в очередь. Строим пути из B (С = 1). Строим пути из C (B = 2). И снова надо перестраивать пути из B, поскольку до него нашёлся более короткий путь.
    Поэтому у Дейкстры и используется сортированная очередь, тогда не возникает необходимости в повторном просмотре точек.
    Ответ написан
  • Найти количество чисел заданного порядка, модуль разницы соседних цифр которых не больше 1

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    У вас уже неправильно, для двузначных будет (10, 11, 12, 21, 22, 23, 32, 33, 34...).
    Модуль разницы:
    myglbyq.png
    Верхнюю оценку получить легко, 10*3(n-1), а вот точное число посчитать по формуле скорее всего не получится, 0 и 9 портят всю картину.
    Ответ написан
  • Вывод 3 чисел, которые в сумме дают число n

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Не должны повторяться перестановки - значит для каждого множества слагаемых {a, b, c} можно найти множество {a', b', c'}, образованное перестановкой элементов исходного множества, такое, что a'<=b'<=c'. Значит каждый следующий вложенный цикл должен начинаться не с 1, а со значения итератора предыдущего цикла.
    ---
    Подумал ещё:
    При условии a<=b<=c, a+b+c=n значение a не может быть больше n/3, иначе b либо c будут б̶о̶л̶ь̶ш̶е меньше, чем a.
    Значение b не может быть больше, чем (n-a)/2, иначе c будет б̶о̶л̶ь̶ш̶е меньше b.
    Значение c будет равно (n-a-b).
    Итого, получаем
    int n = Integer.parseInt(reader.readLine());
    for (int i = 1; i <= n/3; i++) {
        for (int j = i; j <= (n-i)/2; j++) {
            System.out.println("Числа " + i + " + " + j + " + " + (n-i-j));
        }
    }
    Ответ написан
    2 комментария
  • Как осуществить поиск функции по известным значениям?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если заранее неизвестен хотя бы общий вид функции, то, по моему, проще дизассемблировать программу и разобраться в вычислениях, чем пытаться определить взаимозависимости между 50 параметрами. Например, для такой функции двух переменных
    oohphsl.png
    зависимость от y сильно проявляется только в малой области значений x в районе x=b. А ведь функция может быть и кусочно-непрерывной, например
    lf3t5yz.png
    Ответ написан
  • Как осуществить поиск функции по известным значениям?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    По известному набору точек можно лишь предположить вид функции, например набор (-1, 0), (0, 0), (1, 0) может принадлежать как прямой y=0, так и синусоиде y=sin(πx) или полиному y=x3-x. Обычно вид функции выбирается из физической модели процесса, для которого получены данные.
    Ответ написан
    Комментировать
  • Как реализовать метод эластичной сети?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если знаете английский, почитайте эту статью
    Ответ написан
    Комментировать
  • Существует ли стандартный алгоритм для расчета огибающей семейства кусочно-линейных функций?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    К каждой линии добавляются точки (x1; 0) и (xn; 0) (проекции крайних точек на ось X), получается полигон. Дальше алгоритм сложения полигонов.
    Ответ написан
    3 комментария
  • Доверительный интервал

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    С лотереей, если её правила за это время не менялись, оценка 2/(365*3) будет достаточно точной.
    С листовками всё гораздо сложнее - надо оценивать репрезентативность выборки, то есть насколько точно 50 человек, получивших листовки, соответствуют той аудитории, среди которой будут розданы все листовки и целевой аудитории, на которую они расчитаны.
    Ответ написан
    Комментировать
  • Какой метод преобразования температуры в цвет используется в тепловизорах?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Выбирается палитра и ей в какое-либо соответствие (например линейное) ставится диапазон температур.
    Ответ написан
  • Покритикуйте, пожалуйста, мой нубо-код (алгоритм нахождения наибольшего общего делителя 2ух чисел, c#)

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    while (second != 0) {
        reminder = first % second;
        first = second;
        second = reminder;
    }
    nod = first;
    Ответ написан
    Комментировать
  • Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    На C++
    #include <iostream>
    #include <vector>
    #include <set>
    #include <time>
    
    std::set<std::string> subSeqs;
    struct _element {
        char digit;
        int  count;
    };
    std::vector<_element> elemSeq;
    
    void recurse(std::vector<_element>::iterator elemRest, std::string subSeqHead) {
      bool fin = (elemRest+1 == elemSeq.end());
        for (int i = 0; i <= elemRest->count; i++, subSeqHead += elemRest->digit)
            if (fin)
                subSeqs.insert(subSeqHead);
            else
                recurse(elemRest+1, subSeqHead);
    }
    
    void main(void)
    {
      int i;
      _element element;
      std::string initialSeq = "1234567890123";
    
        std::cout << "Initial sequence: " << initialSeq << "\n";
    
        clock_t start = clock();
    
        element.digit = initialSeq[0];
        element.count = 1;
        for (i = 1; i < initialSeq.length(); i++) {
            if (element.digit == initialSeq[i])
                element.count++;
            else {
                elemSeq.push_back(element);
                element.digit = initialSeq[i];
                element.count = 1;
            }
        }
        elemSeq.push_back(element);
    
        recurse(elemSeq.begin(), "");
    
        clock_t finish = clock();
    
        i = 0;
        std::cout << "Elements: (";
        for (std::vector<_element>::iterator t = elemSeq.begin();
                                                    t != elemSeq.end(); t++) {
            if (i++ != 0)
                std::cout << ", ";
            std::cout << "{'" << t->digit << "', " << t->count << "}";
        }
        std::cout << ")\n";
        std::cout << subSeqs.size()-1 << " unique subsequences\n";
        std::cout << "Calculation time " << finish-start << " clicks, ";
        std::cout << ((float)(finish-start))/CLOCKS_PER_SEC << " sec\n";
    /*     for (std::set<std::string>::iterator t = subSeqs.begin();
                                                    t != subSeqs.end(); t++) {
            std::cout << *t << "\n";
        } */
    }

    Результаты:
    Initial sequence: 8246
    Elements: ({'8', 1}, {'2', 1}, {'4', 1}, {'6', 1})
    15 unique subsequences
    Calculation time 0 clicks, 0 sec
    ================================================================
    Initial sequence: 88885
    Elements: ({'8', 4}, {'5', 1})
    9 unique subsequences
    Calculation time 0 clicks, 0 sec
    ================================================================
    Initial sequence: 12345678901234567890
    Elements: ({'1', 1}, {'2', 1}, {'3', 1}, {'4', 1}, {'5', 1}, {'6', 1}, {'7', 1},
     {'8', 1}, {'9', 1}, {'0', 1}, {'1', 1}, {'2', 1}, {'3', 1}, {'4', 1}, {'5', 1},
     {'6', 1}, {'7', 1}, {'8', 1}, {'9', 1}, {'0', 1})
    1043455 unique subsequences
    Calculation time 4383 clicks, 4.383 sec
    ================================================================
    Initial sequence: 11223344556677889900
    Elements: ({'1', 2}, {'2', 2}, {'3', 2}, {'4', 2}, {'5', 2}, {'6', 2}, {'7', 2},
     {'8', 2}, {'9', 2}, {'0', 2})
    59048 unique subsequences
    Calculation time 187 clicks, 0.187 sec
    Ответ написан
    3 комментария
  • Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Несколько сократить количество вариантов при переборе можно сгруппировав подряд идущие одинаковые цифры. Скажем для (1 1 1 2 1 1) получим исходный набор ((1, 3), (2, 1), (1, 2)). После этого рекурсивно его перебираем.
    функция рекурсия(набор, результат) {
        если набор пуст {
            если результат уникален { 
                добавить результат в список уникальных
            }
        }
        ((цифра, количество), следующий_набор) = набор;
        для i от 0 до количество {
            рекурсия(следующий_набор, результат+(цифра i раз));
        }
    }
    рекурсия(исходный_набор, '');

    Первый шаг рекурсии даст варианты '', '1', '11' или '111'. Второй шаг к каждому из них допишет '' или '2'. Третий шаг к каждому из 8 получившихся вариантов допишет '', '1' или '11'. То есть вместо 26 = 64 вариантов для поиска уникальности получим 4*2*3 = 24.
    Чем больше будет в исходной последовательности групп подряд идущих одинаковых цифр тем больше будет выигрыш. Если таких групп нет, то упрёмся в полный перебор.
    Ответ написан
    1 комментарий
  • Сколько существует различных уникальных подпоследовательностей из последовательности цифр длиной N?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    В общем случае получается только полный перебор, количество всех подпоследовательностей = 2n-1
    Ответ написан
    4 комментария