Задать вопрос
Ответы пользователя по тегу Программирование
  • Как решить задачу на Поиск граничного элемента?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Если испытывать поочерёдно этажи 1, 2, 4, 8, ..., 2^K, 2^{K+1} до тех пор, пока яйцо не разобъётся, а потом уточнить значение F из промежутка 2^K..2^{K+1} бинарным поиском, количество попыток будет (2 lgF). Если слово «примерно» допускает коэффициент 2, то алгоритм подходит.

    Если в распоряжении только одно яйцо, то нет никакого другого способа, кроме как идти снизу вверх подряд, O(N).
    Если есть два яйца, первым можно идти с более грубым шагом A[1], A[2], A[3], ..., A[K], A[K+1], а вторым уточнять точное значение F из A[K]..A[K+1]. Причём шаг A[K+1]-A[K] определяет количество попыток для второго яйца, то есть суммарное количество попыток будет K+A[K+1]-A[K]. Осталось определить вид последовательности A[i], чтобы K+A[K+1]-A[K]=O(√A[K+1]).
    Собственно, чтобы достичь 2(√N), нужно первым яйцом идти с шагом (√N), то есть 1, 1+(√N), 1+2(√N), 1+3(√N), ..., а когда разобъётся на 1+(K+1)(√N), идти вторым подряд с этажа 2+K(√N).
    Ответ написан
    1 комментарий
  • Придумать метрику равномерности чтения файла?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Нам даны m_i. Равномерность предполагает, что m_i ~ k * mo. ИМХО, удобнее сразу перейти к dp_i = abs(mo-p_i) — отклонению от среднего. Чем равномернее, тем ближе dp_i к нулю в среднем.

    Если мы не хотим учитывать порядок m_i, то функция равномерности должна быть симметрична по всем аргументам.
    Вы предлагаете использовать стандартное квадратичное отклонение sqrt(average(dp_i ^ 2)). simbajoe предлагает использовать average(dp_i). В общем случае можно выписать любой момент (на числа dp_i ведь можно смотреть как на выборку некоторой случайной величины) average(dp_i^t) или, приводя к той же «размерности», power(average(dp_i^t), 1/t), где t — любой натуральный параметр. std_dev соответствует t=2.

    Кстати, если f(x) монотонно строго возрастает от 0 до 1 на [0,1], то какую-бы оценку не взяли (например, std_dev), всегда можно предложить оценку равномерности f(std_dev). Поэтому и average(dp_i^t), и power(average(dp_i^t), 1/t) одновременно подходят на должности оценки равномерности. Если Вас не устраивает результат, его можно подкорректировать при помощи такой функции f(x). Например, если std_dev обычно порядка 0 — 0.3, то sqrt(std_dev) порядка 0 — 0.5, а power(std_dev, 1/4) порядка 0 — 0.7, то есть занимает почти весь диапазон обычно. У нас нет Вашей статистики, под которую Вы хотите построить метрику, поэтому попробуйте поэкспериментировать, подбирая показатель степени.

    Есть ещё одина доступная свобода — выбор способа усреднения average, то есть не ограничиваться средним арифметическим, но и другие варианты испробовать.

    Однако есть вопрос, важен ли на порядок m_i. Зависит от задачи. Статистики [0.1, 0.2, 0.2, 0.2, 0.2, 0.1] и [0.2, 0.1, 0.1, 0.2, 0.2, 0.2] должны давать один результат или разные? Важно ли, блоки нагруженные и простаивающие идут вразброс, или они сгруппированы секциями? Для чтения файла, мне кажется, это должно учитываться. Однако, если это Вам не важно, смотрите в сторону power(std_dev, 1/t).
    Ответ написан
  • Циклы или рекурсия?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Используй то, что более удобно. Если реализация очевидна в терминах цикла, не следует использовать рекурсию. И наоборот. Так, если мыслишь решение задачи как функциональную зависимость (пусть для того же факториала), то тебе поможет рекурсия. Она позволит отделить тебе одно вычисление от другого, которое опирается только на результат первого. Впрочем, если ты четко видишь, что именно следует делать с переменными предыдущей итерации, чтоб получить следующий результат, то цикл будет организовать проще.
    Поддерживать, опять же, проще тот код, в котором четко просматривается логика (эта оценка субъективна).
    Ответь себе на вопрос: что такое факториал? «n!=n*(n-1)!, если n>1; n!=1 иначе» или «n! есть то, что получится, умножив подряд 1 на 2, на 3, на 4, ..., на n»
    Или же такой: какой вариант приходит тебе первым, если требуется просуммировать элементы в динамическом списке? Создать указатель, идти по списку до конца и прибавлять к переменной, пока указатель не станет нулевым? Или просуммировать первый элемент с суммой хвоста (если тот не пуст)?
    Для каждой задачи первый приходящий в голову вариант будет определять, к чему ты ближе, что тебе будет удобнее использовать, что будет проще читать.
    Ответ написан
    1 комментарий