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

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

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

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

    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
    Заводчик кардиганов
    Если вы знаете математику - она вам будет нужна. В полном объёме ваших знаний. Если нет - вы прекрасно обойдётесь без неё. Потому что задачи вы будете выбирать в соответствии со своими возможностями.
    Ответ написан
  • Каков алгоритм и суть работы реально существующего скрипта 100% предсказания результата, загаданного человеком?

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

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

    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 покажет, перпендикуляр получился, или нет.
    Ответ написан
  • Как решить задачу про разрез(написать программу)?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала проверяете, есть ли свеча в центре. Если есть, то очевидно, нельзя (любой разрез, делящий торт пополам, проходит через центр).
    Потом для каждой свечи находите направление на неё из центра. В большинстве языков это делается вызовом функции atan2(y,x) (в предположении, что центр находится в точке (0,0)). Она выдаёт угол в радианах, лежащий в промежутке от -pi до pi.
    Сортируете углы по возрастанию: a1<=a2<=...<=an.
    Если an-a1 < pi-eps, то все свечи лежат внутри угла, меньшего pi, и разрез есть.
    Если для какого-то k a{k+1}-ak > pi+eps, то есть пустой угол, больший pi, и разрез тоже есть.

    Сложности возникают, когда an-a1 или a{k+1}-ak очень близки к pi, и надо точно проверить, больше угол, чем pi, меньше, или равен. Здесь всё зависит от жестокости авторов задачи.
    Если числа заданы, как целые, не превосходящие по модулю 10^9, то достаточно посчитать определитель x{k+1}*y{k}-x{k}*y{k+1}, и по его знаку определить, с какой стороны линия, соединяющая свечи, пройдёт от центра. Произведения укладываются в int64, и всё просто.
    Если числа целые и не превосходят 10^18, то дело хуже. Существуют алгоритмы проверки, не выходящие за int64 (специально написанный алгоритм Евклида), но возможно, что проще воспользоваться длинной арифметикой.
    Хуже всего, если координаты - вещественные числа произвольного формата. Боюсь, что тут придётся писать свой парсер - простого хорошего способа надёжно проверить, что свечи с координатами, скажем (1.2E220, 2.7E-180) и (-2.8E200, 6.3E-200) лежат строго на одной прямой, проходящей через центр, я не знаю.
    Ответ написан
  • Как узнать, является ли чмсло суммой какого-нибудь n первых чисел натурального ряда?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Считаете число D=8*S+1. Если оно оказалось полным квадратом (т.е. если взять целую часть квадратного корня из D и возвести в квадрат, то снова получится D), то ответ - да, и n=(sqrt(D)-1)/2. Иначе S искомой суммой не является.
    Ответ написан
  • Почему именно синус?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В этой задаче синус не нужен.

    double r=sqrt(x*x+y*y);
    double cf=1+10/r;
    double x1=x*cf,y1=y*cf;

    (x1,y1) - координаты искомой точки.
    Ответ написан
  • Как математически описать перебор кода из 7 цифр?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    "как минимум 2 цифры и они должны повторяться как минимум дважды"
    Если разных цифр ровно две, то ясно, что имеется в виду. А если больше? Скажем, годится ли код 1122234, в котором две цифры повторяются не менее двух раз, но две другие - нет?

    Боюсь, что годится только прямой перебор. На C это бы выглядело так:
    char s[8],stat[4];
      int i,j,k;
      s[7]='\0';
      for(i=0;i<16384;i++){
         k=i;
         for(j=0;j<4;j++) stat[j]=0;
         for(j=0;j<7;j++){
            stat[k%4]++;
            s[j]=(char)((k%4)+'1');
            k/=4;
        }
        if((stat[0]>=2)+(stat[1]>=2)+(stat[2]>=2)+(stat[3]>=2)>=2) printf("%s\n",s);
      }

    Код не проверялся.
    Ответ написан
  • Взлом шифра Вернама(одноразовый блокнот). Как сделать?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Предполагаем, что известно, на каком языке сообщения, и статистика распределения символов (а также сочетаний по 2, 3 символа...)
    Зависит от того, сколько у нас сообщений.
    Если их достаточно много, то строим статистику символа с каждым порядковым номером по всем сообщениям (символ k встретился P[k] раз). Эта статистика должна получаться из стандартной статистики L для языка как P[k]=L[k^c], где c - искомый символ. Для каждого c считаем вероятность того, что на этом месте оказался именно он, и дальше начинаем искать наиболее вероятный текст для какого-нибудь сообщения.
    Если сообщений только два, то придётся использовать распределение групп символов, смотреть, из каких сочетаний наиболее вероятно получится фрагмент из C1^C2, и дальше распутывать их с помощью каких-нибудь цепей Маркова. Не знаю, получится ли.
    Сильно облегчит дело, если сообщения - фрагменты обычных ASCII-файлов, со всеми знаками пунктуации и переводами строк. Можно воспользоваться тем, что перевод строки имеет код 0D,0A, пробел - 20, другие знаки пунктуации - от 21 до 3F, большие буквы - от 41 до 5A, маленькие - от 61 до 7A (это если текст английский. Для русского ещё лучше). Смотрим на поведение битов 40 и 20. Если в каком-то месте в разных закодированных сообщениях значения бита 40 различны, значит в некоторых это буква, в остальных - знак пунктуации. Причём, буква вероятнее в тех, в которых более частое значение. Немного похимичив, получаем разделение текстов на слова, строки и предложения. Заодно в части сообщений проявляются некоторые буквы. Дальше работаем с распределением одно-, двух- и трёхбуквенных слов. Может быть, повезёт.
    Ответ написан
  • Можно ли посчитать количество цифр в документе, в котором содержатся результаты подсчёта?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я не уверен, можно ли решить эту задачу, если документ состоит из 97 девяток.
    Ещё одна девятка будет в левом столбце таблицы. Какая-нибудь из цифр от 0 до 8 вряд ли встретится 9 раз. Так что девяток будет 98+ число девяток в последней клетке таблицы. Вот и получается:
    Если в последней клетке 0 девяток, то в ней число 98+0=98
    Если в ней одна девятка, то в ней 98+1=99
    Если в ней две девятки, то в ней 98+2=100
    Во всех случаях получаем противоречие.

    UPD. Задача решается довольно просто.
    Пусть у нас уже собрана статистика о числе разных цифр в теле документа (B[0] нулей, B[1] единиц...)
    Сразу прибавим к этим числам по единичке, чтобы учесть левый столбик.
    Оценим сверху число цифр в правой части таблицы. Например, как S=10*(log_10(B[0]+..+B[9])+2).
    Каждая цифра в полном документе встретится не более B[n]+S раз, значит, в правой части таблицы для неё будет число, лежащее от D0[n]=B[n] до D1[n]=B[n]+S.
    Прооптимизируем диапазоны D0..D1. Для этого для каждой цифры переберём все числа от D0[n] до D1[n], посмотрим количество разных цифр в каждом из этих чисел, возьмём минимальное и максимальное значение вхождений. Например, если D0[n]=997, D1[n]=1013, то в клетке, соответствующей n, 0,1 и 9 могут встретиться от 0 до 3 раз, а остальные цифры - 0 или 1 раз.
    Просуммируем полученные диапазоны по всем n - получим новую таблицу диапазонов D0n,D1n. Пересечём их с D0,D1.
    Есть 3 варианта.
    Все полученные диапазоны совпали с D0..D1. Выходим из цикла.
    Один из новых диапазонов пуст. В этой ветке решений нет, возвращаемся из функции.
    Какой-то диапазон изменился. Продолжаем оптимизировать.

    После того, как диапазоны стабилизировались, смотрим их длины. Если все они длины 1 (т.е. D0=D1), то мы нашли решение. Если нет - то берём самый короткий диапазон длины больше 1, перебираем все его значения D0[n]<=u<=D1[n], подставляем каждое из них в копию таблицы диапазонов (D0n[n]=D1[n]=u) и рекурсивно вызываем функцию оптимизации.
    Перебор оказывается небольшим, вот примеры (ncall - число рекурсивных вызовов):

    For 1 2 3 4 5 6 7 8 9 10
    0->5 1->7 2->5 3->5 4->6 5->10 6->9 7->10 8->10 9->12
    ncall=696

    For 1 1 1 0 0 0 0 0 0 0
    0->2 1->7 2->5 3->1 4->1 5->2 6->1 7->2 8->1 9->1
    ncall=486

    For 0 0 0 0 0 0 1 0 0 0
    ncall=464

    For 0 0 0 0 0 0 0 1 0 0
    0->1 1->7 2->2 3->3 4->1 5->1 6->1 7->3 8->1 9->1
    0->1 1->6 2->3 3->3 4->1 5->1 6->2 7->2 8->1 9->1
    0->1 1->6 2->4 3->1 4->2 5->1 6->2 7->2 8->1 9->1
    ncall=482

    For 3997 19995 5677 998 799996 392 7 94 8998 99985
    0->4014 1->20000 2->5679 3->1000 4->800001 5->394 6->10 7->96 8->9000 9->99994
    0->4013 1->20001 2->5679 3->1001 4->800000 5->394 6->10 7->96 8->9000 9->99994
    ncall=47356
    Ответ написан
  • По каким формулам вычислить новые координаты объекта в трёхмерном пространстве при относительном перемещении?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала вам надо чётко определить, что такое "Углы поворота объекта по всем трём осям". Поскольку повороты не коммутируют, то задание поворота несколькими углами - это всегда последовательность поворотов относительно некоторых осей на определённый угол (или поворот вокруг одного вектора - но это уже кватернионное представление). Например, углы Эйлера - последовательность поворотов относительно OZ, OX и снова OZ.
    Если у вас объект получается из базового объекта последовательностью поворотов (OX,a), (OY,b), (OZ,c) (a,b,c - углы в радианах), и есть вектор (dx,dy,dz) в локальной системе координат повёрнутого объекта, то получить сдвиг объекта на этот вектор в глобальной системе координат можно так:
    dy1=cos(a)*dy+sin(a)*dz; dz1=-sin(a)*dy+cos(a)*dz; // поворот относительно OX
    dx1=cos(b)*dx-sin(b)*dz1; dz2=sin(b)*dx+cos(b)*dz1; // поворот относительно OY
    dx2=cos(c)*dx1+sin(c)*dy1; dy2=-sin(c)*dx1+cos(c)*dy1; // поворот относительно OZ
    Тогда (dx2,dy2,dz2) - искомый вектор сдвига.
    Если углы заданы в градусах, они переводятся в радианы умножением на pi/180.
    Общее правило: преобразование координат, которое использовалось для перемещения объекта из его базового состояния в текущее - это то же преобразование, которое используется для перевода координат из текущей локальной системы координат объекта в глобальную.
    Ответ написан
  • Раз Пи бесконечно, можно сказать, что его значение меняется постоянно?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Боюсь, что нет. Если проводить аналогию с квантовой механикой, то невычисленные знаки числа пи соответствуют, скорее, "скрытым переменным", которые мы не видим, но они существуют. И проявятся когда мы их измерим. Мы сейчас не знаем, чему равна цифра числа пи с номером, скажем, 10^15, но когда мы её сосчитаем, у неё будет вполне определённое значение. И это же значение (конечно, если считать в десятичной системе) получит кто угодно в любой цивилизации в любой Вселенной, если у них есть математика, совместимая с нашей. Размерность и кривизна Вселенной значения не имеют.
    Поэтому можно сказать, что значение каждой цифры объективно существует и определено. Просто мы его ещё не знаем.
    Ответ написан
  • Сколько нужно завести друзей в Facebook, чтобы с вероятностью близкой к 100% каждый день в году поздравлять с днем рождения хотя бы одного друга?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если надо найти точную вероятность того, что все дни рождения заполнены, то формула получается сложной. Эквивалентная формулировка - найти количество M-значных чисел в системе счисления по основанию N, в которых встречаются все N цифр.
    Рассматриваем наборы из N чисел a1,a2,a3,...,aN, для которых ai>=0 и a1+a2+...+aN=M-N, и по всем таким наборам (их С(M-1,N-1), наборы с разным порядком считаются разными) считаем сумму S величин 1^a1+2^a2+...+N^aN. Тогда искомое количество чисел равно S*N!, а искомая вероятность - S*N!/(N^M).
    Приближенную вероятность, когда M заметно больше N, найти проще. Вероятность того, что в определённый день ни одного дня рождения не будет, равна (1-1/N)^M, и вероятность того, что хотя бы один день рождения будет каждый день - (1-(1-1/N)^M)^N (здесь мы считаем события независимыми, что вообще говоря, неправда). При больших N и M/N это можно оценить как exp(-N*exp(-M/N)). Если N=365, то для достижения вероятности 99% нужно 3833 друга, а для 99.9% - 4675 друзей.
    Наличие 29 февраля ещё несколько усложняет картину.
    Ответы на вопросы 1-5 при N=366: 2041, 2295, 2617, 3844, бесконечность.

    Уточнение: число S, которое получается в точном решении, это число Стирлинга второго рода S(M,N). По ссылке есть простая явная формула.
    Ответ написан
  • Как определить кривизну линии?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если надо проверить среднее отклонение от прямой, то можно посчитать матрицу ковариации:
    xm=sum(x[i])/N; ym=sum(y[i])/N;
    a=sum((x[i]-xm)^2); b=sum((x[i]-xm)*(y[i]-ym)); c=sum((y[i]-y0)^2);
    и посчитать отношение собственных значений:
    R=(a+c-sqrt((a-c)^2+4*b^2)/(a+c+sqrt((a-c)^2+4*b^2).
    Если R достаточно мало (скажем, меньше 0.01), то считаем, что это прямая.

    Если надо проверить, прямая это или дуга, то берём крайние точки (x0,y0) и (xn,yn). Пусть dx=xn-x0,dy=yn-y0.
    Считаем для всех точек
    z[i]=((x[i]-x0)*dx+(y[i]-y0)*dy)/sqrt(dx^2+dy^2), w[i]=((x[i]-x0)*dy-(y[i]-y0)*dx)/sqrt(dx^2+dy^2),
    Теперь приближаем зависимость w(z) параболой (по методу наименьших квадратов): w=A*z^2+B*z+C. Величина A пропорциональна кривизне дуги, по которой идут точки.
    Ответ написан
  • Развивается ли способность к решению нестандартных задач?

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