Задать вопрос
  • Как поменять местами ноды стека/односвязного списка?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Ну да, вам придется рассматривать отдельный случай - когда они идут подряд. Проверяйте, что а вдруг min->next == max. Нарисуйте картинку из четырех точек before_min, min, max, max->next со стрелочками до помены и после. Смотрите у каких трех вершин ссылки поменяются и как. Запишите это в коде.

    Еще есть случай max->next == min, но его можно рассмотреть вместе с предыдущим - просто в этом случае поменяйте месами указатели min и max (а также before_min и before_max). Тогда код для прошлого случая сработает. Вам же в момент помены без разницы, какая вершина максимум, а какая минимум. Вам надо только 2 заданные вершины поменять местами.
    Ответ написан
  • Как вычислить сумму бесконечного ряда, используя смешанный способ и общую формулу для вычисления члена ряда. Как найти рекуррентную формулу?

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

    Пусть f(x) - ваш ряд. Тогда f'(x) = sum (-1)^n x^(2n-2) / (2n+1)

    Чтобы совсем избавиться от знаменателя надо бы, чтобы степень была 2n+1. Можно этого добиться, домножив все на x^3. Потом можно опять взять производную.

    (x^3 f'(x))' = sum (-1)^n x^2n = sum (-x^2)^n = 1/(1+x^2)

    Теперь назад проинтегрировав это можно получить:
    x^3 f'(x) = arctg(x)+C

    При x=0 слева 0 - значит C=0.

    f'(x) = arctg(x) / x^3

    Отсюда можно найти f'(x): Зайдите на wolframalpha и введите integrate arctg(x)/x^3 dx (не могу дать прямую ссылку с запросом на wolfram, потому что мат-фильтр почему-то срабатывает на ссылку и не дает отправить ответ).

    Чтобы найти константу, придется подставить, например, x=1 и найти сумму ряда a_n = (-1)^n/(4N^2-1). Это какой-то известный сходящийся рад, похоже. Опять, посмотрите на wolframalpha, введите там sum (-1)^n/(4*n^2-1), n=0 to infinity. В итоге получится, что там константа тоже 0.

    Вот и получится, что f(x) =- (x^2 * arctan(x) + arctan(x) + x) / (2x^2)
    Ответ написан
    Комментировать
  • Как найти неизвестные параметры функции, зная ее значения?

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

    Аналитически, как в методе наименьших квадратов, приравнять производные по n и k к 0 похоже не очень получается. Придется использовать какой-то численный метод минимизации функции. Например, градиентный спуск или метод ньютона. Если похоже, что функция имеет множество локальных минимумов, то будет работать что-то более хитрое, как например, метод отжига.
    Ответ написан
    Комментировать
  • Как перегрузить оператор += для двух массивов?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас нет проблем с перегрузкой. У вас там проблема с логикой программы. Для начала объясните себе, что хранит в себе класс Array (зачем там 2 массива a и b?), что должен делать опреатор += для двух экземпляров Array?
    Ответ написан
    Комментировать
  • Как написать кастомный findIndex с бинарным поиском?

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

    Второй вариант - функция должна возвращать 1, если первый элемент строго меньше второго.

    Тогда равнество можно сделать так: !f(a,b) && !f(b,a). А второе условие просто заменяется на один вызов функции.
    Ответ написан
    7 комментариев
  • Как разложить поворот вокруг произвольной оси на повороты вокруг ортов СК объекта?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    180-градусов вдоль оси вдоль зеленой детальки (вправо), а потом 90 градусов вдоль оси перендикулярной деталькам (ось к нам). Ну или в обратном порядке - сначала 90 градусов вдоль перпендикулярной оси, потом 180 вдоль продольной оси (вверх).
    Ответ написан
  • Как вставить определенное слово в строку в необходимом мне месте?

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

    Во-первых, зачем вам структура из четырех строк? Зачем вам массив из нее на 1000 элементов.

    Вот это вообще что за хрень?
    for (i; i < 1; i++) {

    Вас этот цикл из одной итерации нисколько не напрягает?

    Далее, в задании четко сказано
    Разработать функцию, которая вставляет в предложение заданное слово. Новое слово должно стать в предложении n-м (n задается как третий параметр функции)


    Т.е. вам надо взять одну функцию, и вызвать ее 3 раза с передавая туда то 1, то 2, то 5, а не писать 3 Poshuk'а.

    Далее, во всех ваших функциях вы обращаетесь к list[] по разным индексам, но у вас только один первый элемент массива вводится (опять, нахрена вам целый массив структур, если в задаче дано ровно 3 строки и одно слово?!)

    Ну и последнее, логика искомой функции должна быть такой: Проходимся по переданной строке, считатем, сколько пробелов встретили. Как только встречаем пробел с заданным номером, сдвигаем все символы за этим пробелом вправо на длину вставляемого слова, потом копируем слово в пустое место.

    Чтобы сдвигать символы в строке вам надо сначала найти ее длину, потом с длина+k циклом пройтись назад до крайнего сдвигаемого индекса и присваивать текущему символу значение символа по индексу i-k.
    Ответ написан
    Комментировать
  • Как завершить все потоки сразу после завершения одного из потоков в си, используя толлько pthread_detach и pthread_join?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вызвать exit какой-нибудь, то программа завершится и система прибъет все потоки.
    Ответ написан
  • Почему можно обратиться к объекту через указатель со значением nullptr?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Метод класса под капотом - это функция, котрой помимо прописанных параметров передается указатель на объект. В вашем случае передается nullptr. Но сама функция не обращается к объекту, да у него и членов-то с данными никаких нет. Поэтому все более менее работает. Но это UB и могло и не повезти. Из-за оптимизаций компилятор мог бы что-то сломать.

    P.s. сказанное выше не относится к виртуальным функциям. Там указатель на функцию храниться в vtable в экземпляре класса и вызов через nullptr скорее всего упадет.
    Ответ написан
    Комментировать
  • Как сделать сортировку двухмерного массива по столбцам?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Работайте с массивом как с одномерным. Занумеруйте его так: первые индексы - это первый столбец сверху вниз. Потом идут индексы с ячейками второго столбца и т.д.

    Вам осталось по одному числу - индексу в этом виртуальном одномерном массиве получать индексы исходного двумерного массива.

    Номер столбца будет i / M, Где M - количество строк. Номер строки будет i % M.

    Вам надо только написать алгоритм сортировки одномерного массива и везде, где там идет обращение к [i], вам надо сделать [i % M][i / M].
    Ответ написан
  • Как использовать socket в gcc на windows?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вы используете cygwin для компиляции, то можно и линуксовый socket использовать. Будет чуть менее эффективно из-за фактически эмуляции posix api.

    Ну или, если через visual studio компилируете, то используйте winsocket API
    Ответ написан
    Комментировать
  • Как решить задачу по математике с помощью python?

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

    Сначала решите уравнение, при какой величине вклада X доход от бумаги и от банковского вклада будет одинаков?

    1.1X+2000 = 1.12X

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

    От питона вам надо уметь выполнять действие 4 раза:
    for i in range(0, 4):

    Сравнивать 2 значения и делать в зависимости от этого разные действия.
    if a < b:
      foo
    else:
      bar


    Ну, вряд ли вы не знаете, еще надо уметь присваивать переменные и выполнять арифметику - умножение и сложение.
    Ответ написан
    Комментировать
  • Почему в СТЕКЕ разрешается выделять достаточно мало памяти?

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

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

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

    А так, для ускорения выделения памяти есть, например, аллокаторы на стеке: Заводится локальный массив и специальный менеджер памяти вместо выделения ее в куче, выделяет куски из этого массива. Но их не используют для хранения больших объемов данных по первой причине - это очень расточительно по памяти.

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

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

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

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

    Когда для каждой точки вы знаете где ее прошлое и следующее положение, у вас задача найти минимум функции
    sum_i (xp_i-xp'_i)^2+(yp_i-yp'_i)^2, где
    xp' = xn*cosa - yn*sina + dx
    yp' = xn*sina + yn*cosa + dy.

    Тут (xp, yp) - координаты i-ой точки в прошлом кадре, (xn, yn) - координаты в следующем кадре, cosa,sina,dx,dy - неизвестные. Берете производные по dx, dy и a приравниваете к 0. Получаете 3 уравнения с 3 неизвестными. Их двух первых элементарно выразить dx, dy через cosa/sina. Подставив в последнее вы получите уравнение вида cosa^2 A + sina cosa B + sina^2C + D = 0. Можно домножить D на cosa^2+sina^2, потом поделить все на sin^2 и решать квадратное уравнение относительно тангенса. Потом через арктангенс найти решение.

    Если изменения от кадра к кадру могут быть большими, то надо минимизировать чуть чуть другую функцию:

    sum_i min_j ((xp_j-xp'_i)^2+(yp_j-yp'_i)^2) - для каждой точки берем минимум по всем возможным прообразам и это суммируем. Поскольку оно уже не диффиренцируемо, придется использовать какой-то более хитрый метод оптимизации по dx, dy, a.
    Ответ написан
    Комментировать
  • Почему после вызова Message Box, GetKeyState() не считывает состояние клавиши?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Диалоговое окно-то появляется?

    Я подозреваю, что MessageBox возвращает 0, что происходит происходит при ошибке:
    If the function fails, the return value is zero.


    Поэтому цикл while завершается. Т.е. проблема не с GetKeyState, а логикой программы.
    Ответ написан
  • Как реализовать copy on write class?

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

    Нужен счетчик ссылок на буфер. Перед записью проверяйте, что счетчик равен 1. Иначе копируете данные и в текущем объекте заменяете указатель на новый буфер.

    Счетчик должен храниться где-то вместе с буфером и является частью умного указателя.

    Можно использовать std::shared_ptr - там уже этот счетчик реализован (use_count).
    Ответ написан
    Комментировать
  • Как копировать список в си (C)?

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

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

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

    Если надо как-то нормировать нагрузку, то тут возникает задача назначения, которая может решаться алгоритмом максимального потока минимальной стоимости. Можно вводить штрафы на перегрузку каждого человека и тогда алгоритм может выдавать документы не ближайшим людям, у которых мало работы.
    Ответ написан
    Комментировать
  • Какой паттерн, как организовать структуру проекта для разных форматов пикселей RGB и YUV?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Я бы посоветовал делать абстракцию не на уровне пикселя, а на уровне картинки. Ибо так можно оптимальнее организовывать расположение пикселей в памяти да и обрабатывать изображение быстрее. Вместо функции, которая для каждого пикселя проверяет, а что там у него брать R или Y, используют функции, которым передается plane - один канал. Что там конкретно R, G, Y, V - обычно не важно. Если вы ищете контур или сглаживаете изображение, то работа идет абсолютно одинаково в каждом канале.

    В качестве примера можно посмортреть вот тут или тут.
    Ответ написан
    Комментировать
  • Что делать если при отладке сработала точка останова по исключению?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    char str = 0, *pStr = &str;

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

    Надо выделять память под строку. Или статический массив, или malloc.
    Ответ написан
    Комментировать