• Какой алгоритм использовать для определения нахождения точки за границей треугольника пространства?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Если точка не на плоскости треугольника, то вам надо переформулировать задачу. Там вообще непонтяно, что значит внутри/снаружи.

    Если же оно на плоскости, то введите там систему координат (например, орто-нормируйте вектора p2-p1 и p3-p1). Получите координаты всех точек (p1 можно назначить началом координат).

    Потом придется применять формулу для плоскости. Можно воспользоваться векторными произведениями. Произведение пар векторов {p-p1, p2-p1}, {p-p2, p3-p2}, {p-p3, p1-p3} должны все давать одинаковый знак (или все <=0 или все >=0. Равенство 0 чего-то будет означать, что точка на границе).

    Или можно посчитать площади, опять же через векторное произведение. |(p2-p1)(p3-p1)| = |(p1-p)(p2-p)+(p2-p)(p3-p)+(p3-p)(p1-p)|
    Ответ написан
  • Как заставить потоки работать с классом с++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы передаете в std::thread не статический метод класса. Его нельзя передавать как обычную функцию. Его же можно вызывать только у какого-то объекта. Где thread этот объект возьмет-то?

    Есть 2 варианта - передавайте лямбду, которая будет захватывать this и вызывать у него метод объекта.
    Или, как показано тут, передавайте туда &Matrix::findNumberInRow c первым аргументом this.
    Ответ написан
    Комментировать
  • Какой алгоритм использовать для нахождение уравнения поверхности по 3 точками?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть точка p=(x,y,z) принадлежит плоскости. Пусть 3 точки - p1, p2, p3.

    Тогда вектор (p-p1) должен раскладываться на вектора p2-p1 и p3-p1.

    Т.е. определитель матрицы 3x3 из этих трех векторов должен быть нулевым.

    det {{x-p1x, p2x-p1x, p3x-p1x},
     {y-p1y, p2y-p1y, p3y-p1y},
     {z-p1z, p2z-p1z, p3z-p1z}} = 0


    Раскрываете определитель по первому столбцу и получаете
    A = det({{p2y-p1y, p3y-p1y}, {p2z-p1z, p3z-p1z}})
    И т.д.
    D = -p1x*A-p1y*B-p1z*C
    Ответ написан
  • Что думаете об этом решении задачи?

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

    Но, так-то там числа фиббоначи, не превышающие 4000000. Их таких дай бог 100. Там можно их все считать по несколько раз- вы разницу скорости работы скрипта не измерите никак.

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

    Заведите вы третью временную переменную и считайте через нее, чтобы в цикле всегда n было большим числом (m = 4*n+b; b=n; n=m). Или вообще воспользуйтесь фишками питона и делайте множественное присвоение:
    b, n = n, 4*n+b;
    Ответ написан
    8 комментариев
  • Как практически использовать теорему Колмогорова-Арнольда?

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

    Например, x*y*z вы в сумму никогда не разложите. Зато, если взять f(a,b) = a*b, то можно сделать f(x,f(y,z)).

    Это хорошо для оптимизации

    Эта суперпозиция не будет лучше для оптимизации ни с какой точки зрения.

    Практически это можно сделать так - расставьте все скобки рядом со всеми операциями в выражении. Каждая операция - это своя функция. Вот у вас и суперпозиция.
    Ответ написан
    Комментировать
  • Зачем Visual Studio нужен свой runtime?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Этот рантайм - это библиотеки для .Net

    Его пришлось запилить, когда MS сделал С# и .Net. Тупо копировать туда libc++ почему-то не решили.

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

    Оно работает в c++, только если попросить visual studio компилировать под common language runtime.
    Ответ написан
    Комментировать
  • Почему создаётся бесконечный указатель в дереве?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вот этот код создает кольцевую ссылку:
    if (left) {
            tree->left = readElement(tree);
        }


    Что вы там пытаетесь сделать? Если вы хотите прочитать элемент в дерево, то ваща readElement(tree) вернет указатель на новый корень. Если выхотите добавить в левое поддерево (и грантируете, что следующий элемент будет меньше корня), то надо добавлять в tree->left а не tree.
    Ответ написан
  • В чём разница между алгоритмами операций в дополнительных и обратных кодах?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Обратный код: !x = 2^n-1 - x.
    Дополнительный код - !x+1 = 2^n - x.

    В дополнительном коде число -x записывается как 2^n-x. Поэтому его можно просто прибавлять/вычитать/умножать - лишнее 2^n не влезает в разрядность переменной и просто будет проигнорированно.

    В обратном коде у вас есть лишнее -1, которое надо компенсировать. прибавлять при вычитании, вычитать при сложении и прибавлять множитель при умножении.

    Еще, в обратном коде никак не записать 2^(n-1), потому что число 0 представимо 2 раза в виде 00000000 и 100000000.
    Ответ написан
    Комментировать
  • Как решить, программа выдает ответ не в правильном формате?

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

    Или проверяющая программа ждет перевод строки (добавьте "\n" после вывода m).
    Ответ написан
  • Как создать свой итератор для вектора в шаблонном классе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам, собственно, надо реализовать итератор для вашего класса и возвращать итараторы в begin() и end(). Вот первая статья из гугла, в которой по шагам реализуют итератор.

    Вам надо лишь переписать операторы инкримента, чтобы пропускать элементы. Ну и аккуратно считать итератор end, чтобы последовательные инкрименты из begin не проскочили его.
    Ответ написан
    Комментировать
  • Как ускорить код?

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

    Во-вторых, как вам уже сказали - амортизационно это все будет O(s). Потому что внутренний цикл делает "лишних" операций суммарно столько, сколько l-1 на конце всех размещений. Их 0 в l^(n-1)*(l-1) размещениях, 1 в l^(n-2)*(l-1), и т.д. если все это просуммировать, то результат будет меньше l^n - количества итераций внешнего цикла.
    Ответ написан
    Комментировать
  • Как бросить луч?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вот целая статья на тему есть: https://habr.com/ru/post/533932/
    Ответ написан
    1 комментарий
  • Как сделать приложение на с++ в windows?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Эм... visual studio компилирует программу. В какой-то папочке вроде Build/release в папке проекта появится exe файл. Вот его можно запускать и даже копировать на другие компьютеры.

    Что касается библиотек, то, во-первых, для встроенных библиотек есть Visual Studio Redistributables, которые нужны многим программам и скорее всего у друга уже стоят. Если нет - то программа при запуске попросит их установить. Все ваши сторонние библиотеки можно распространять вместе с exe файлом в виде dll.

    Ну или гуглите static linking - можно настроить компилятор впендюривать все библиотеки прямо в exe файл. Тогда можно будет копировать только его.
    Ответ написан
    1 комментарий
  • Визуал студио не вызывает функцию, написанную ниже другой (read не вызывает read_hw), в заголовке обе объявлены, как исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сморите внимательно, реализации и объявления функции read_hw не совпадают - там разные типы аргументов.
    Ответ написан
    1 комментарий
  • Как найти координаты вершин треугольника вписанного в другой треугольник?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Есть много способов. Мне нравится векторный. Для каждой вершины отложите вектор длины x вдоль стороны против часовой стрелки. Потом отложите вектор длины l, перпендикулярный внутрь.

    Длину x можно найти, если посмотреть на картинку hint000 - это длина катета. При чем вам дан второй катет (l). Значит надо поделить или умножить на тангенс угла, который есть половина угла в вершине.

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

    Тут вам понадобится найти углы у нижних вершин треугольника, но это школьная задача - углы равны, их сумма плюс известный верхний дадут pi/2.
    Ответ написан
    Комментировать
  • Как из убывающей последовательности сделать возрастающую в c++?

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

    2) Разворачиваете каждую их них.

    3) ???

    4) PROFIT!

    Вот вам подсказка, как можно выделять в массиве убывающие последовательности.
    start = 0;
    while (start < n) {
      end = start;
      ПОКА (start..end+1 - убывающая последовательность) {
        ++end;
      }
      // start..end - убывающая последовательность.
      start = end+1;
    }


    Развернуть кусок с i по j можно одним циклом while. Меняйте местами 2 крайних элемента и тогда останется развернуть кусок с i+1 по j-1.
    Ответ написан
    Комментировать
  • Можете помочь применить lower_bound и upper_bound в С++?

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

    надо ускорить программу с помощью lower_bound и upper_bound,


    Ну вот посмотрите на эти самые lower_bound и upper_bound в документации. Они как раз находят первое и за-последним включение заданного числа, если оно в упорядоченном массиве встречается. Если числа там нет, то они оба будут указывать на первое большее заданного число.

    Функции возвращают итераторы. Чтобы преобразовать их в индексы, можно воспользоваться std::distance, чтобы узнать расстояние до начала массива. Там по ссылкам выше прямо примеры есть, которые все это делают.
    Ответ написан
  • Как реализовать функцию копирования бит со смещениями в src и/или dst и не кратным 8 количестве бит?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Самое эффективное - использовать какой-нибудь SSE (гуглите shift bits sse. Лучше всего, мне кажется, подойдет _mm_slli_epi64). Но там очень много кода и случаев будет. Придется отдельно разбирать случаи сдвига влево и вправо, отдельно вычленять биты, которые SSE операция при сдвиге бы потеряла и записывать куда надо.

    Следующий по эффективности вариант - это читать в int64_t, и там сдвигать биты. Придется сначала из переменной доставать старшые/младшие 1-7 бит и писать их отдельно, потом сдвигать биты и записывать куда надо. Используйте memcopy для чтения/записи 64-ех бит. Еще можно ускорить, если отдельно обработать первые несколько байт до 64-битного выравнивания, и потом придется еще обрабоать отдельно лишние 0-7 байтов в конце, если их количество не делится на 8.
    Ответ написан
  • Как зашифровать алгоритм внутри программы?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Никак.

    Вы можете только усложнить реверс инжениринг. Самый эффективный способ, если не очень важна производительность, то можно реализовать собственную виртуальную машину с кучей похожих, но немного разных инструкций, и реализовывать алгоритм на ней. Надо еще впихнуть в алгоритм всяких неважных действий, типа тут прибавить 5 к числу, оно потом в алгоритме умножается на 2, потом вычесть 8 и 2. Можно написать транслятор с простого скриптового языка на ЭТО, иначе вы и сами запутаетесь.

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

    Тут та же проблема, с которой копирасты пытаются бороться: алгоритм - это информация. И если он, таки, исполняется на компьютере пользователя вы никак не можете ему запретить его смотреть, копировать или модифицировать.

    Единственный достаточно надежный способ - это выполнять алгоритм на сервере и выдавать клиенту лишь его результат. Но это совсем не то, что вы имеете ввиду.
    Ответ написан
    6 комментариев
  • Как это быстро сделать?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Перебирайте буквы от младших к старшим: a,k, d,b,z, e...

    Проверяйте правильность суммы поциферно справа на-лево как можно раньше.

    Т.е. после перебора a уже можно проверить, что (a+a+a) % 10 = a. Потом, после k надо проверить (ka+ka+ka)%100 = ka, после dbz можно проверить третью цифру.

    Можно немного соптимизировтаь, есл ине считать (ка+ка+ка)%100, а помнить, какой там перенос из младшей цифры и проверять уже только (k+k+k+carry1)%10 = k, carry2 = (k+k+k+carry1)/10; Потом проверить, что (d+b+p + carry2)%10 = z и т.д.

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

    Следующее улучшение - не перебирать буквы s, z, e и r, а сразу считать, какими они должны быть, чтобы сумма сходилась. С s и z все тривиально, а для e и r надо чуть-чуть математики.

    Это надо аккуратно выписать уравнения вида (e+a+e+carry2)%10=a.

    Тут надо применить свойства модуля: 2e %10=-carry2 % 10, Тут для e есть 2 решения, если carry2 четно: (10-carry2)/2, (20-carry2) / 2

    Но это улучшение не сильно ускорит.
    Ответ написан