• Не доходит до меня тема коллекций, что я не так решаю?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    А вам нужно удалить всех людей, или одного оставить?
    Во втором случае накапливаете множество имён, и если у очередного человека имя принадлежит множеству, его удаляете. Если не принадлежит - добавляете в множество имён.
    Если надо удалить всех Иванов:
    - заводите два множества: имена, которые встретились, и имена, которые встретились более одного раза.
    - в цикле по таблице: если очередного имени в первом множестве нет, добавляете его туда, а если есть - добавляете во второе множество.
    - удаляете из таблицы всех людей, имена которых есть во втором множестве.
    Ответ написан
  • Где применяется комбинаторика в информатике?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Мало применяется. В информатике она, скорее всего, понадобится в анализе сложности различных алгоритмов, выборе оптимальной стратегии перебора. В олимпиадном программировании встречается постоянно. В реальной жизни - в основном, когда комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез.
    Ещё комбинаторика может пригодиться в задачах, связанных со статистической физикой, когда через число состояний оценивается энтропия системы, а через неё - дальнейшее поведение или устойчивость. Возможно, она нужна для алгоритмов вроде сверхбыстрого умножения чисел. Но всё это очень далёкий уровень, при взгляде с которого элементарная комбинаторика уже неотличима от таблицы умножения.

    UPD. Можно вспомнить одно место, где комбинаторика требуется в обычных задачах. Это когда у нас есть множество каких-нибудь подмножеств, перестановок, слов над алфавитом, или ещё чего-нибудь, что обычно считает комбинаторика. И мы хотим по элементу этого множества найти его индекс. И наоборот.
    Задача возникает не часто, но если возникла, то без комбинаторных формул не обойтись никак.
    Ответ написан
    Комментировать
  • Почему у int и float разный диапазон?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Потому что значения int на всём промежутке идут равномерно, с шагом 1, то у float шаг между соседними значениями меняется: в окрестности единицы он примерно 10^(-7), а в окрестности миллиарда - около 100. Приблизительно можно сказать, что равномерно идёт логарифм float. За счёт этого (выигрыш в точности на малых числах, но заметный проигрыш на больших) они и расширили диапазон.
    Играясь с соотношением числа бит на мантиссу и порядок, можно менять диапазон на точность, и наоборот.
    Ответ написан
    Комментировать
  • Как и где в программировании используется математическая логика?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Математическая логика - правила вывода, системы аксиом, теории, логические системы и т.п. - практически не используется. Возможно, какая-то её часть нужна при разработке компиляторов (формализация вывода типов, доказательства допустимости оптимизаций...) и экспертных систем.
    Булева алгебра нужна гораздо чаще. Но если вы выучите и поймёте правила преобразования логических выражений, этого будет достаточно. Даже предполные классы, скорее всего, не понадобятся. Хотя, если судьба забросит в программирование ПЛИС... там всё может быть.
    Проходят ли в дискретной математике графы - не помню. Даже если да, то совсем не на том уровне (и не в том направлении), в котором они нужны в программировании.
    Что могло бы пригодиться - конечные автоматы. Они нужны более, чем в одном месте. Но, опять же, в дискретной математике могут дать, разве что, общие факты про них.
    Так что, в целом - это предмет для расширения кругозора и любителей головоломок разных уровней.
    Ответ написан
    1 комментарий
  • Интегралы и программирование?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Базисы Грёбнера гораздо нужнее. А из интегралов чаще всего достаточно знать формулу трапеций, для практических целей (если это не расчёт водородной бомбы) её хватает.
    Ответ написан
    Комментировать
  • Как найти положение камеры по трем точкам в пространстве?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Непростая задача.
    Сначала по фотографии измеряете углы между лучами, а по модели - расстояния между точками. Потом обозначаете через x,y,z неизвестные расстояния от камеры до точек (длину каждого луча), и записываете уравнения из теоремы косинусов:
    x^2-2*a*x*y+y^2=P^2
    x^2-2*b*x*z+z^2=Q^2
    y^2-2*c*y*z+z^2=R^2
    Здесь a,b,c - косинусы углов между лучами, а P,Q,R - расстояния.
    Дальше надо решить эту систему. Теоретически, она сводится к уравнению 8-й степени от одной переменной z. MAPLE смог найти этот многочлен, он занимает чуть больше экрана. Не знаю, хороший ли это вариант - может быть, и да. Можно попытаться решить систему численно - перебрать разные стартовые значения x,y,z и искать корень методом Ньютона. Но учтите, что система плохая - у неё вполне могут найтись 4 близких корня с положительными x,y,z. А могут и не найтись - тогда будут локальные минимумы. Можно перебрать расстояние x с мелким шагом. Для каждого x найти два варианта y, два варианта z, подставить их в третье уравнение, и из самой лучшей тройки начать искать решение - можно методом Ньютона, но можно и делением отрезка пополам.
    После того, как x,y,z найдены, находите положение центра камеры - как точку пересечения трёх сфер. И дальше надо найти правильную ориентацию. Это довольно противно, но должно быть не очень сложно (по сравнению со всеми предыдущими шагами).
    Ответ написан
  • Как расчитать скорость шара в момент пересечения лазерного луча?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Мяч катится по плоскости? В таком случае, если вы установите систему на высоте, равном радиусу, мяч не может задеть луч краем. Проблема будет в том, что он может пройти под углом к лучу, и свет прервётся на время, большее, чем d/v. Надо будет поставить два луча под углом друг к другу. Проще всего, если они перпендикулярны - тогда скорость определится, как d*sqrt(1/t1^2+1/t2^2). Если прямой угол невозможен, то будет получаться два ответа - один, когда направление движения мяча попадает в большой угол между лучами, и второй - когда оно попадает в малый угол.
    Если мяч летит в пространстве, то шансы, что он вообще пересечёт луч, очень малы. Но если допустить, что это происходит, то придётся взять несколько параллельных лучей (например, три, образующие полосу, с небольшим расстоянием между ними), и по отношениям времени, которое мяч их пересекает, определить, каким местом он их задел. Хотя нет, трёх мало. Мяч ведь может подлететь и параллельно плоскости этой полосы, тогда все датчики покажут одинаковое время. Лучше взять 5 лучей, образующих крестик (вершины квадрата и центр).
    И ещё 5 лучей, идущих под углом к первым, чтобы компенсировать угол пересечения лучей мячом. Итого 10 - и система сработает, только если мяч пересечёт их все.
    Ответ написан
    3 комментария
  • Как выразить член из формулы Бернулли?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    По-моему, это на центральную предельную теорему. При больших M количество дошедших порций будет иметь нормальное распределение с матожиданием P*M и дисперсией P*(1-P)*M. Вам надо подобрать M так, чтобы значение функции распределения в точке A=N*M/100 (это количество порций, которые надо получить) было не больше 1-S, где S - "наперёд заданная вероятность".
    Это можно сделать только если P > N/100. В противном случае сообщение надо отправлять одним куском. Если же P <= N/100 и при этом P < S, то задача неразрешима.
    Ответ написан
    Комментировать
  • Нужно ли программисту c#/c++ знание математики?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если вы знаете математику - она вам будет нужна. В полном объёме ваших знаний. Если нет - вы прекрасно обойдётесь без неё. Потому что задачи вы будете выбирать в соответствии со своими возможностями.
    Ответ написан
    Комментировать
  • Как повторить текущую итерацию while C#?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я бы сделал так:
    while (условие) {
        do {
            код код код код
            код код код код
        }while (условие);
    
        код код код код
        код код код код
    }


    Но это если "перезапустить текущую итерацию" не требует дополнительного кода. Если требует - поставить вместо do...while бесконечный цикл for(;;) с break незадолго до конца.
    Ответ написан
    Комментировать
  • Каков алгоритм и суть работы реально существующего скрипта 100% предсказания результата, загаданного человеком?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Задумайте число X от 103 до 997, в котором первая и последняя цифра отличаются больше, чем на 1. Запишите его в обратном порядке (получится Y), и вычтите из большего из чисел X,Y меньшее. Получится Z. Теперь найдите сумму числа Z, записанного в обратном порядке, и самого Z. Получится 1089. Это магия следующего порядка.
    Ответ написан
    Комментировать
  • Как подогнать результат имея список цифр и итоговую сумму?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    А в этом примере не будет лучше 1*33+2*1+7*1+9*1=51? Задействованы все цифры, причём в максимально возможном количестве.
    Ответ написан
  • В задаче сказано: "возрастающая конечная арифметические прогрессия из различных целых отрицательных целых чисел" - что это должно сказать решающему?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Знать не нужно почти ничего - только формулу n-го члена и суммы арифметической прогрессии.
    В этой задаче всё выражается через новый член, добавленный математиком (пусть это -b), количество членов, бывших до того (n) и шаг прогрессии d (натуральное число).
    Слегка поигравшись с формулами, получаете, что изменение разности D=n*b*(2*b+(n+1)*d). Несложно убедиться, что должно быть b>0. Всё, что вам нужно - подобрать натуральные b,d,n, чтобы условие выполнялось.
    Ответы:
    1) -5,-4,-3 (добавлено -2)
    2) не бывает: нужно, чтобы b*(2*b+13*d)=120, т.е. 120/b-2*b было положительным и делилось на 13. Понятно, что b должно быть меньше 8 и быть делителем 120. Перебирая возможные значения (это все числа от 1 до 6), получаем, что решений нет.
    3) n=15, прогрессия -19,-18,...,-5 (добавлено -4).
    В последнем случае перебираете возможные значения b*d (чем оно меньше, тем больше возможно n). Оказывается, что при b*d=1,2,3 решений нет, а при b*d=4 - есть.
    UPD. Выше сказали про "олимпиадные задачки" - боюсь, что это правда. Для олимпиадных задачек особых знаний не нужно - но нужна система знаний, чтобы быстро найти верный путь в лабиринте возможных подходов.
    Ответ написан
    Комментировать
  • Как найти известный маркер на изображении?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я для поиска таких маркеров (правда, без внешнего полукольца) начинаю с того, что для каждой точки строю "окружность" с центром в этой точке, состоящую из 20 точек (радиус может варьироваться) и проверяю, насколько она симметрична. Если средний квадрат разностей яркостей симметричных точек заметно меньше дисперсии, то это кандидат на маркер. Потом проверяю на подобие (беру окружность вдвое меньшего радиуса). Если оба критерия прошли - идёт проверка уже по площадям (опять же, проверяется симметрия, самоподобие и однородность белого и чёрного). Границы приходится распознавать только для определения центра с субпиксельной точностью (достигается точность 1/10 пикселя).
    К сожалению, процесс довольно медленный. Особенно, если заранее размер маркера неизвестен, и приходится проверять разные масштабы.
    Про яркостную границу можно предложить прогнать алгоритм, основанный на выделении границ, для нескольких порогов яркости. Какой-нибудь да сработает. Но как описать и быстро распознать ситуацию "при сканировании пройден центр маркера", я ещё не придумал.
    Ответ написан
    Комментировать
  • Существует ли алгоритм реорганизации списка оптимальный по количеству перестановок?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если есть операция IndexOf для поиска элемента, то оптимальное число перестановок достигается так (превращаем L1 в L2):
    for(int i=0;i < L1.Count;i++){
      while(L1[i]!=L2[i]){
         L1.swap(i,L2.IndexOf(L1[i]));
      }
    }

    При каждом обмене текущий элемент L1[i] ставится на то место, на котором он стоял бы в списке L2, и больше с этого места не уходит.
    Ответ написан
    2 комментария
  • Как правильно сравнить массивы и оценить их схожесть?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Существует решение, работающее в худшем случае за O(N*sqrt(N*log(N))), а в типичном - за O(N*log(N)).
    Пусть наши массивы - A и B.
    Создадим массив Q из 2*N троек, содержащих (элемент массива, индекс в массиве, какой это массив - A или B).
    Сортируем по полю "элемент массива".
    Заводим массив C длины N, в котором будем считать C[k]=число совпадений при сдвиге на k позиций.
    Просматриваем отсортированный массив Q. Для каждого значения X в нём сразу видно, сколько раз и на каких местах X встретился в массивах A и B. Пусть он p раз встретился в A (в позициях a1,a2,...,ap) и q раз - в B (в позициях b1,b2,...,bq). Если p*q < N*log(N), то за p*q операций модифицируем C, увеличивая на 1 все C[(bj-ai) mod N].
    В противном случае строим массивы из 0 и 1, содержащие маски вхождения X в A и B, и считаем с помощью быстрого преобразования Фурье их свёртку. Прибавляем её к C.
    Наихудший для этого алгоритма случай - когда в массивах примерно sqrt(N/log(N)) различных значений, которые встречаются примерно одинаковое количество раз.
    Ответ написан
    Комментировать
  • Правильно ли я понял суть кватернионов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Обычно берут кватернионы длины 1, т.е. x^2+y^2+z^2+w^2=1.
    Поворот на нулевой угол задаётся кватернионом (0,0,0,1) - направление оси (x,y,z) для него не определено, да и не нужно.
    В остальных случаях угол поворота определяется значением w по формуле
    w=cos(phi/2), где 0 <= phi <= 2*pi. То есть, чем больше угол поворота, тем меньше w. Для поворотов на 180 градусов w=0.
    Если w<0, то поворот получается на угол, больший 180 гр. Угол поворота отсчитывается против часовой стрелки, если смотреть в сторону (x,y,z). Получается, что кватернионы (x,y,z,w) и (-x,-y,-z,-w) задают один и тот же угол поворота.
    Почему так сделано - не очень важно. Главное, что суперпозиция двух последовательных поворотов описывается кватернионом, равным произведению кватернионов самих этих поворотов (в каком-то определённом порядке).
    Ответ написан
    3 комментария
  • Как найти точки на плоскости, образующие выпуклый многоугольник?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Самый простой вариант: сортируете точки по возрастанию расстояния от центра, и для каждой точки по порядку проверяете, останется ли после её добавления многоугольник выпуклым, и не окажется ли внутри многоугольника уже просмотренных, но недобавленных точек. Если всё хорошо - добавляете точку к многоугольнику. Правда, придётся с чего-то начать. Самая очевидная кандидатура - треугольник из триангуляции Делоне, содержащий центр, но его может быть дорого искать.
    Другой вариант - динамика по сторонам многоугольника. Сортируете точки по углу, выбираете отрезок (A1 A2) такой, что в треугольнике O A1 A2 нет других точек, и двигаетесь по кругу, пытаясь добавлять новые точки - A3, A4 и т.д. Для каждого варианта последней стороны A{k-1} Ak считаете наилучшее значение характеристики, которую оптимизируете (число вершин или площадь). Когда (если) многоугольник замкнётся - сравниваете его с оптимальным.
    К сожалению, придётся перебрать все стартовые стороны. Можно ограничиться теми, которые пересекаются лучом Ox - хотя бы одна такая сторона в многоугольнике должна быть.
    Оценка сложности - N^5.
    UPD. Если внешний цикл вести не по отрезку (A1 A2), а по самой правой точке строящегося контура, то сложность уменьшится до N^4.
    Ответ написан
    Комментировать
  • Самая сложная программа в мире?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Может быть, это программа для машины Тьюринга с 6 состояниями, которая выводит 3.5*10^18267 единиц и останавливается? en.wikipedia.org/wiki/Busy_beaver

    Ещё один вероятный кандидат - эмуляция игры "Жизнь" на ней самой (со скоростью 1/10000000). Там даже про язык сложно говорить.
    Ответ написан
    Комментировать
  • Как найти длину перпендикуляра с точки на отрезок?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    double L=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    double PR=(x-x1)*(x2-x1)+(y-y1)*(y2-y1);
    bool res=true;
    double cf=PR/L;
    if(cf<0){ cf=0; res=false; }
    if(cf>1){ cf=1; res=false; }
    double xres=x1+cf*(x2-x1);
    double yres=y1+cf*(y2-y1);

    В (xres,yres) будут координаты ближайшей точки отрезка, а переменная res покажет, перпендикуляр получился, или нет.
    Ответ написан