• Как решить задачу на Поиск граничного элемента?

    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 комментарий
  • Как переназначить события onclick после выполнения функции?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Вы можете перенести проверку класса родителя и разделение логики present/udalitCol в сам обработчик события, поскольку при вызове доступна ссылка на элемент, по которому был произведён клик.
    // цикле без if-условия
    kompListItem[i].onclick = function() {
      if (this.parentNode.className !== 'added-to-table')
        return present.call(this);
      else
        return udalitCol.call(this);
    };


    Альтернативно, Вы можете добавить вызов init в конец функции present, но учтите, что все свободные имена этой функции (kompListItem, i) необходимо перед вызовом обновить или другим, соответствующим логике приложения образом обработать.
    Ответ написан
    Комментировать
  • Цифровые свойства объекта?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    for(k in { x: 1, y: 2 }) { ... }
    k примет значения "x" и "y" в теле.
    Поскольку массив является объектом с ключами, которые являются числами, в цикле for(k in [1, 2]) { ... } k пройдёт значения "0" и "1".
    Однако, объект-массив содержит ещё некоторые поля, например, "length", который, однако, не проходит итератор. Если я правильно помню, в ES3 это было жестко вшито в семантику языка как исключение, а в ES5 это обыгрывается тем, у полей появились атрибуты, причём поле "length" имеет дескриптор enumerable.

    В процитированном фрагменте говорится буквально следующее: слева от in не обязательно будет экземпляр Array, даже если у этого объекта есть поля "0", "1" и т.п., при этом могут быть и другие поля, которые имеют заранее неизвестные дескрипторы. И стоит быть готовым к тому, что k в цикле for(k in obj) {...} может принять строковое значение, которое нельзя привести к числу.
    Ответ написан
    Комментировать
  • Как задать диф. уравнение с разделенными переменными?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    На всякий случай,
    DSolve[x Dt[x] == y[x] Dt[y[x]], y[x], x]
    в WM8 работает.
    Ответ написан
    Комментировать
  • Собрать круг через дуги-path'?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Написано топорно. Магическая константа 70=100/sqrt(2).
    <path d="M 100 200 a 100 100 0 0 1 30 -70" stroke="blue" stroke-width="5" fill="none" />
    <path d="M 130 130 a 100 100 0 0 1 70 -30" stroke="yellow" stroke-width="5" fill="none" />
    <path d="M 200 100 a 100 100 0 0 1 70 30" stroke="blue" stroke-width="5" fill="none" />
    <path d="M 270 130 a 100 100 0 0 1 30 70" stroke="black" stroke-width="5" fill="none" />
    <path d="M 100 200 a 100 100 0 0 0 30 70" stroke="cyan" stroke-width="5" fill="none" />
    <path d="M 130 270 a 100 100 0 0 0 70 30" stroke="red" stroke-width="5" fill="none" />
    <path d="M 200 300 a 100 100 0 0 0 70 -30" stroke="yellow" stroke-width="5" fill="none" />
    <path d="M 270 270 a 100 100 0 0 0 30 -70" stroke="grey" stroke-width="5" fill="none" />
    Ответ написан
    Комментировать
  • Как привести локальный мастер к тому в гитхабе?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Сейчас от мастера сделал ветку, чтобы можно было подглядывать свои изменения.
    То есть Вы прервали rebase и сохранили ваши коммиты, голова новой ветки указывает на последний коммит?

    Как привести мастера к виду на гите?
    На гитхабе? Т.е., на центральном репозитории?
    Тогда откатить master назад (git reset master <хеш коммита, который есть локально и удаленно>) и сделать git pull.
    Ответ написан
  • Придумать метрику равномерности чтения файла?

    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).
    Ответ написан
  • Как реализуется GUI на чистом функциональном языке без состояния (например, на Haskell)?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Для любого языка имеются библиотеки, написанные на более низком уровне. Для одних языков их больше, для других — меньше.
    Как делаются библиотеки под Haskell я не знаю, но Вас интересует именно аспект, связанный с сохранением чистоты при работе с GUI. На уровне использования языка, сохранить чистоту можно, оборачивая все «нечистые» вычисления в монады, например, в IO. Удобно использовать представление, которое в математике называется категорией Клейсли, когда «нечистая» функция A -> B превращается в чистую A -> IO B. Примеры привёл egorinsk комментарием выше.
    Ответ написан
  • Теория категорий для чайника

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Розеттский камень — это путь самурая, без подготовки не осилить. К тому же, Баез, как теорфизик, склонен постоянно сравнивать категорные понятия с понятиями из реального мира. Это не для IT.
    Если что-то наглядное и в картинках, то можно почитать Голдблат «Топосы. Категорный анализ логики».
    А вообще, русской литературы маловато. Но английской довольно много. Взять, например, «Joy of cat» — многим нравится.

    Ещё, just for fun, можно посмотреть на youtube канал catsters. В частности, там очень наглядно объясняются пределы.
    Ответ написан
    Комментировать
  • Координатная сетка и расстояния в хексах?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Человек сразу выделяет три направления (см. рисунок ниже). Поэтому можно выбрать косоугольную систему координа (на рисунке: красные линии — горизонтальное направление и наклонное) с углом 60°. Тогда вдоль красных направление соотв. координата будет возрастать, а вдоль голубого — одновременно две. Расстояния между центрами будет вычислятся по формуле
    image
    Где Г — матрица Грамма этой косоугольной системы: image
    Это в случае, когда расстояния между центрами соседей 1.

    Ответ написан
    2 комментария
  • Циклы или рекурсия?

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

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Врятли моё мнение самое правильно, но так как никто более не отписался, позволю предложить следующее:

    Создавая рекурсию «в лоб» мы как бы идем вглубину. Грубая оценка говорит, что порядок будет таков: 4^(R+S), поскольку в одном пути не менее R+S ходов, каждый ход порождает 4 варианта дальнейшего движения.

    Можно использовать что-то типа поиска в ширину / Динамическое Программирование: каждой клетке приписать число путей, ведущих от левого верхнего края к ней, и заполнять по принципу от ближней к дальней. База: от первой вершины до себя 1 возможный путь. Переход: если клетку окружают клетки со значениями a1, a2, a3, a4 (не все могут быть определены, их временно зануляем), то значение клетки есть их минимум min(a1,a2,a3,a4). Оканчиваем, когда получим значение для правой нижней. Обход всех клеток потребует R*S шагов, такова же сложность алгоритма.
    Ответ написан
    1 комментарий
  • В каких проектах распределённых вычислений вы участвуете?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    GIMPS: www.mersenne.org
    бессмысленно и беспощадно, но всё же…
    Ответ написан
    Комментировать
  • центр описанной n-сферы

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Для любых двух вершин, например, 1 и 2, центр равноудален от них. Стало быть он лежит в (n-1)-мерном подпространстве, проходящем через середину отрезка x1—x2 (x1 — вектор первой вершины) и перпендикулярном ему. Уравнение такой плоскости:

    Потому что x1-x2 есть направляющий вектор ребра (нормаль к плоскости). Нижние индексы означают номер координаты, а верхние — вершины симплекса.
    Центр однозначно определяет пересечение n плоскостей. Например, выберем плоскости 1—i, где i меняется от 2 до (n+1). Тогда будет

    Получена неоднородная линейная система относительно

    которая разрешается (любым методом).

    P.S. Правильность не гарантирую. Но на неё надеюсь.
    Ответ написан
    2 комментария