Задать вопрос
  • Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

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

    Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].
    Ответ написан
  • Почему при сериализации uint128 сначала сериализуют hi, потом lo, а не наоборот?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Почему сериализуют так а не наоборот? Просто так принято при передаче по сети. Сериализация может использоваться и для этого, поэтому автор, наверно, сделал так.

    На самом деле - можно делать как автору библиотеки захочется. Хоть сначала все четные биты записать, потом - нечетные, хоть hi/low, хоть Low/hi, если какая-то совместимость с другими библиотеками не требуется.
    Ответ написан
    6 комментариев
  • Как узнать угол между двумя прямыми, если известны координаты через которые они проходят?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Получите 2 вектора вдоль этих прямых (если прямые заданы параметрически - вы их уже знаете, если Ax+By+C=0, то это {-B,A}). Теперь угол между двумя векторами a и b - ваш искомый угол. Тут надо вспомнить, что векторное произведение - это |a|*|b|*sin x, а скалярное - |a|*|b|*cos x. Теперь вы знаете sin и cos искомого угла (поделив скалярное/векторное произведение на длины векторов). Можно скормить эти значения atan или еще какой-то обратной тригонометрической функции. Но на практике сам угол редко нужен, нужны в вычеслениях его sin и cos, а их вы уже знаете.
    Ответ написан
    Комментировать
  • Есть ли библиотека на javascript, которая может находить сложные интегралы и брать обратную функцию?

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Большинство решений, уже предложенных тут, работают за квадрат и уже для n=10000 amount=5000 будут работать заметно долго. Конечно, вряд ли такое большое количество данных будет на клиенте, но даже при n=100, если функция выполняется часто, зачем ее делать в ~50 раз медленнее?

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

    Если хотите без splice(), то надо завести новый массив и потом скопировать в него элементы n-amount..n-1 в начало одним циклом, потом вторым циклом скопировать дальше элементы 0..n-amount-1.

    Зафиксированный вами интерфейс предполагает использование нового массива для результатов каждый раз. Но можно было бы сделать без использования много дополнительной памяти, тусуя сам массив на месте, если допустить изменение интерфейса.

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

    function gcd(a,b) {
     if (a>b) return gcd(b,a);
     return a == 0? b : gcd(b%a, a);
    }
    
    function next(i, k) {
      return i >= k ? i-k : i+n-k
    }
    
    function moveToStartInPlace(arr, k) {
      n = arr.length;
      num_cycles = gcd(k,n)
      for (i=0; i < num_cycles; ++i) {
       saved_value = arr[i];
       j = i;
       nxt = next(j, k);
       while (nxt != i) { 
         arr[j] = arr[nxt];
         j = nxt;
         nxt = next(j, k);
       }
       arr[j] = saved_value;
      }
    }


    Возможно, это не лучшая реализация - я не специалист по JS. Суть этого решения в том, что мы берем какой-то элемент и ставим на его место нужный элемент после перестановки. На освободившееся место ставим следующий элемент и так далее, пока не вернемся к начальной позиции (а мы всегда вернемся, потому что перестановки только так и работают).

    Функция next() возвращает, какой элемент должен встать на место i-ого в итоговом массиве.
    Если немного подумать, то станет понятно, что в перестановке ровно gcd(n,k) циклов, потому что в ней все прыжки делаются на +(n-k) или -k. Т,е. фактически делаются только прыжки -k(mod n). А это уже известный факт: если прыгать по массиву на +k, оборачиваясь из конца в начало, то мы вернемся в ту же точку, с которой начали и всего таких циклов будет gcd(n,k).
    Ответ написан
    Комментировать
  • Какое будет время работы алгоритма?

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

    Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).

    Ваше последнее суждение - верно.
    Ответ написан
    3 комментария
  • Реализация двусвязного списка с элементами конкретного типа?

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

    Можно в функции добавления элемента принимать указатель и размер, выделять новую память и копировать.
    Это что-то вроде вашего предложения, но работает для всех типов.

    Можно 2 функции сделать для оптимизации: одна будет копировать и вызываться должна для локальных переменных, а вторая не будет копировать, а будет брать ответственность за переданный указатель. Но тут можно легко ошибиться - при вызове второй функции надо переданный указатель сразу забыть. Иначе можно его 2 раза потом удалить, или использовать после удаления.

    Если же вы собираетесь только инты хранить - то лучше переписать список: храните не указатель на data, а сразу int.
    Ответ написан
    Комментировать
  • Карты, колода 36 карт 1 туз и одна черви?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если у вас задача - что в выбраных наугад картах есть хотя бы один туз и хотя бы одна черва, то надо найти Count(>0 червей И >0 тузов). Можно это инвертировать, считая все плохие варианты, вычев их из всех вариантов:

    Count(>0 червей И >0 тузов) = Count() - Count(0 червей ИЛИ 0 тузов)

    Дальше, COUNT(A или B) можно разложить на Count(A) + Count(B) - count(A И B).

    Финальная формула для ответа:

    Count() - Count(0 червей) - Count(0 тузов) + Count(0 червей И 0 тузов)

    Фактически, это форомула включения-исключения. Но в итоговой формеле все просто счиатать:

    Count() = C(5,36) - все варинты: сочетания по 5 из 36.

    Count(0 тузов) = С(5, 32) - нельзя брать тузы

    Count(0 червей) = С(5, 27) - нельзя брать 9 червей

    Count(0 червей И 0 тузов) = С(5, 24) - нельзя брать 9 червей и 3 оставшихся туза.

    Подсчитайте через фаториалы и сложите с правильными знаками.

    Если же задача - ровно один туз и ровно одна черва, то тут 2 варианта. Или туз-черва взят, или это две разные карты.

    В первом случае оставшиеся 4 карты - любые из 24 карт не-тузов-не-черв, т.е. эта часть - C(4,24). Во втором случае, вы берете какой-то из 3 тузов, какой-то из 8 черв и оставльные 3 карты из не-тузов-не-червей, т.е. ответ 3*8*C(3,24). Обе части просуммируйте.
    Ответ написан
    Комментировать
  • Почему я получаю неверный ответ?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
    Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
    У вас неправильное решение задачи.

    Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

    Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

    Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

    Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

    Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

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

    Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.
    Ответ написан
    4 комментария
  • Как решить этот корнеркейс в реализации алгоритма поиска мажоритарного элемента через разделяй-и-властвуй?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас неправильно в коде - надо считать count() не на всем массиве, а только между low и high.

    Тогда сложность всего алгоритма будет O(n log n). То, что у вас сейчас сделано будет иметь сложность O(n^2).

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

    Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.
    Ответ написан
    Комментировать
  • Как работает ограничение скорости в роутере при раздаче по wifi?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Детали зависят от конкретной реализации, но обычно все основано на leaky bucket.

    В целом, роутер считает, сколько байт он пропустил, и если видит, что байт слишком много в еденицу времени, лишние пакеты просто дропаются (отбрасываются без пересылки их дальше). А дальше уже источник трафика как-то подстраивается. Если трафик TCP - то отправитель замечая потери будет снижать скорость отправления пока потери не прекратятся. Если же используется UDP, и приложение не надстроило над ним каких-то rate-control механизмов, то так и будет посылать лишние пакеты, которые будут уничтожатся роутером. До него трафик будет без ограничения скорости, а дальше пойдет уже ограниченный.
    Ответ написан
    Комментировать
  • Как быстрее получить множество точек, входящих в прямоугольник?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

    R-дерево (по той же ссылке) дает гарантию по времени выполнения и знимает сравнительно мало памяти, но его долго пересчитывать, если точки двигаются или добавляются/удаляются.

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

    Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

    Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

    Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

    Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

    При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

    Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

    Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

    Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

    Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.
    Ответ написан
    Комментировать
  • Как обойти граф не зацикливаясь на связи одного узла с другим?

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

    В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

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

    Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

    При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

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

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

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

    Пересчет: f(i) = max(f(i-1), a[i-1] + f(i-k)) - тут мы или не берем последний элемент, и тогда ответ f(i-1) или берем - и тогда мы обязаны пропустить k-1 следующих элементов. База: f(i<=0) = 0.

    Можно сократить потребление памяти если считать в массиве снизу вверх и хранить только последние k элементов f[].
    Ответ написан
    Комментировать
  • В чем ошибка в коде, который расчитывает период Пизано?

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

    И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);
    Ответ написан
    Комментировать
  • Как найти все возможные комбинации чисел от 1 до n-1 чтобы их сумма была равна n?

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

    Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

    Что-то типа такого:
    void Generate(int n, int next, int sum, vector<int> taken) {
      if (next > n || sum > n) return;
      if (sum == n) {
       Output(taken);
      }
      Generate(n, next+1, sum, taken);
      taken.push_back(next);
      Generate(n, next+1, sum+next, taken);
    }
    
    ...
    
    Generate(n, 1, 0, {});


    Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

    Вариант 2 - оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

    Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

    База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

    пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
    Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

    Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

    Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

    Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).
    Ответ написан
    3 комментария
  • Какой у этого решения time и space complexity?

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

    В функции:
    - Выделяется новый массив: n операций
    - Вызывается функция для укороченного массива: F(n-1) операций
    - Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
    - Вложенный цикл по позициям: n*(n-1)! = n! повторений
    - вложенное в циклы построение новой перестановки: n*n! операций

    Итого F(n) = n + F(n-1) +n*n!

    Можно раскрыть рекурсивно и получим:
    F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
    Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
    В итоге, F(n) = O(n*n!).

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

    Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

    Это хорошая ассимптотика - для построения всех перестановок меньше нельзя.
    Однако, если вам не надо все перестановки хранить в памяти (да и для кэша, кстати) будет заметно быстрее генерировать следующую перестановку из текущей на месте, как описано тут. Хоть и с такой же ассимптотикой, этот алгоритм будет работать в несколько раз быстрее.
    Ответ написан
    Комментировать
  • Смысл и предназначение обычного бинарного дерева? Какова погрешность измерение времени программы при помощи Stopwatch'ера?

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

    Можно поддерживать его сортированным и балансированным - вот и стандартные деревья поиска, работающие за log n. Можно поддерживать свойство кучи (предки больше потомков), и у вас получается куча, на которой можно делать приоритетную очередь. Можно зафиксировать высоту дерева и класть данные только в листы, а в промежутачных вершинах считать сумму детей - так получается дерево отрезков, которое позволяет за логарифм считать сумму или максимум на любом отрезке в массиве, менять элементы, добавлять значение ко всем элементам на отрезке и много чего другого.

    Про stopwatch ничего не знаю, что это такое даже.

    А вопросы на бинарные деревья - они неинтересные и тривиальные (сколько детей? Минимально возможная высота дерева? Сколько промежуточных вершин при данном количестве детей и выстое?)
    Вопросы надо задавать про конкретную структуру данных - какие операции с ней можно выполнять и как долго они работают. Сколько памяти нужно для хранения.
    Ответ написан
    Комментировать
  • Как найти максимум в бинарном дереве Java?

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