Задать вопрос
  • Как найти угол поворота объекта (компьютерная графика)?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    1) строите границы Г1, Г2.
    2) для каждой считаете:
    - центр масс (x0,y0)
    - три интеграла: a11=int((x-x0)^2), a12=a21=int((x-x0)*(y-y0)), a22=int((y-y0)^2)
    - собственные значения m1,m2 (m1 < m2) и собственные вектора v1,v2 матрицы ((a11 a12) (a21 a22)).
    Пусть это было вычислено для Г1, а для Г2 получается m1', m2', v1', v2'.
    Если искажений при повороте нет, то m1=m1', m2=m2'. Угол поворота определяется углом z между v1 и v1' (но надо сообразить, в какую сторону). К сожалению, он определён с точностью до 180 гр - так что надо будет как-нибудь сравнить варианты поворота на z и на z+180, и выбрать лучший. Допустим, что это z.
    Осталось найти точку, при повороте вокруг которой на угол z точка (x0,y0) переходит в (x0',y0'). Проще всего записать это в комплексных числах: p0=x0+i*y0, p1=x0'+i*y0', f=exp(i*z). Если искомый центр c, то f*(p0-c)=p1-c, откуда c=(p1-f*p0)/(1-f).
    И всё. Ничего сложного, первый курс ангема...
    Ответ написан
    Комментировать
  • Каков физический смысл модуля при модульном возведении в степень?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Ну, например. Проводите вы какие-нибудь сложные вычисления, например, считаете определитель большой матрицы методом Гаусса. Получилось какое-то маленькое значение, но ошибка при вычислениях могла накопиться большая, и вы не уверены, 0 это или, скажем, 1 (у исходной матрицы коэффициенты целые). Что делать? Посчитать по какому-нибудь модулю. Если повезло и в процессе не пришлось делить на 0, то результат по этому модулю окажется правильным, и если получился не 0 - то значит, и вещественное число было ненулевым. Если же по нескольким разным модулям получились нули, то с большой вероятностью определитель действительно нулевой.
    Модулярная арифметика может пригодиться для перемножения многочленов или больших чисел с помощью быстрого преобразования Фурье. Или для каких-нибудь расчётов, когда вообще неважно, чему равны числа, лишь бы они были ненулевыми и независимыми. В общем, случаи редкие, но когда они встречаются, неплохо бы об этом приёме знать.
    А, да, ещё была "многомодульная геометрия" - когда с помощью модулярной арифметики проверяли, равны ли радиусы двух сфер. Хотя это олимпиадное программирование...
    Ответ написан
    Комментировать
  • Как переводить дробные числа с двоичной системы в 10 в с++?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно сделать так. Завести две переменные: double x=0, y=0.
    Читать строку слева направо. Если пришла цифра b=='0' или '1', то выполнить x=2*x+b-'0'; y*=2;
    Если пришла запятая - присвоить y=1. В конце, если y ненулевой, то поделить x на y.
    Например,
    для строки 101 : x=5, y=0. Ответ 5.
    101,101 : x=45, y=8. Ответ 45/8=5.625
    101, : x=5, y=1. Ответ 5.
    ,101 : x=5, y=8. Ответ 5/8=0.625.
    Ответ написан
    1 комментарий
  • Генерация всех позможных вариантов заполнения квадратной матрицы N-м числом графов. Алгоритм..?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если мы возьмём любую цепочку, проходящую через все точки (например, змейку или спираль), и разрежем её на куски всеми возможными способами, а потом часть кусков ещё и развернём, у нас уже получится примерно 2^(N^2)/3 вариантов. Уже при N=7 перечислить их нереально (при N=6 их всего 10 миллиардов - это не так много). Но поскольку исходных цепочек (проходящих через все точки) много, а кроме того, не все конфигурации можно получить разрезанием одной цепочки, вариантов будет ещё больше.
    Алгоритмы - как рекурсия, так и перебор состояний клеток - не очень сложные. В обоих случаях нужно искать разбиение на неориентированные цепочки, а потом всеми способами задавать их направление.
    В случае перебора состояний (он проще) делаем так. Замечаем, что у каждой клетки есть 10 возможных состояний - 4 для конца цепочки (направления, куда из этой клетки цепочка идёт), 4 для клетки, где цепочка поворачивает, и 2 для клетки, через которую она проходит прямо. Кроме того, есть ограничения: цепочка не может упираться в стенку, и общее ребро двух соседних клеток либо пересекается цепочкой с каждой стороны, либо нет. Ну, и не должно быть циклов.
    Алгоритм получается таким. Перебираете клетки матрицы по строкам. Для каждой очередной клетки смотрите состояние её соседей, и получаете список возможных состояний самой клетки - их не более трёх. В случае, если есть состояние, которое соединяет две соседние цепочки, надо пройтись по ним - проверить, не являются ли они концами одной цепочки (если да - получится цикл, а он запрещён). Теперь подставляем в клетку по очереди все допустимые состояния, и рекурсивно вызываем функцию перебора для следующей клетки. Когда дойдём до конца - фиксируем найденное разбиение.
    Ответ написан
    Комментировать
  • Как найти расстояние от центра до стороны повернутого прямоугольника?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если его повернули на угол a, то
    A1=min(A/abs(cos(a)),B/abs(sin(a))),
    B1=min(B/abs(cos(a)),A/abs(sin(a))).
    Если приходится делить на 0, то результат деления считается равным бесконечности, а значение минимума - второму числу.
    Ответ написан
    1 комментарий
  • C# - Как лучше работать с XSD-схемами?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Есть программа xsd.exe, которая генерирует C# классы из xsd-файла. Можно запускать её перед сборкой проекта - всё сделает. Правда, как поступить с двумя схемами, не очень понятно (читать одной, а если выдала ошибку - то другой?)
    Ответ написан
    Комментировать
  • Из чего состоит core programming languge?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Должна быть минимальная библиотека ввода-вывода. Реализованная в виде операторов языка (как в бейсике или брейнфаке) или функций (как в Си). Альтернативный вариант - наличие ассемблерных вставок и/или возможности вызова "системных" функций.
    Если в языке не предусмотрен динамический захват памяти, то потребуются функции, позволяющие взять память у системы и потом вернуть.
    Остальное можно реализовать уже в терминах самого языка.
    Ответ написан
    Комментировать
  • Как правильно решать линейные уравнения методом Гаусса?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    1) Да, можно прибавлять любую строку, умноженную на любой коэффициент, к любой другой строке.
    2) Нужно сделать так, чтобы во всех клетках (a,b), где a > b остались нули. Тогда матрица примет треугольный вид.
    Например, из системы
    x + y + z = 1
    2*x + 3*y - z = 2
      -x + y + 2*z = 0

    получится
    x + y + z = 1
        y - 3*z = 0
            9*z = 1

    После этого найти последовательно z, y, x
    3) Можно, но вам не понравится. Надо считать миноры (определители матриц (N-1)*(N-1)). Но это будет уже не метод Гаусса.
    Ответ написан
    Комментировать
  • Реализация вращения через кватернион. Где ошибка?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Получилось (-0.41,-7.31,-1.00). Почему вы считаете, что это неправильно? Простейшие независимые проверки не показывают ошибок.
    Ответ написан
  • Как легче всего решить матрицы?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Все задачи на работу со столбцами. Читаете, что бывает с определителем, когда столбец умножается на число, когда столбец прибавляется к другому, когда два столбца меняются местами, когда все элементы столбца оказываются нулевыми. И решаете, что применить.
    Ответ написан
    Комментировать
  • Подойдет ли ноутбук для программирования?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Подойдёт. Не будете отвлекаться на игры. Вот только если вдруг придётся программировать какую-нибудь числодробилку, требующую много памяти, то будет очень грустно.
    Ответ написан
    Комментировать
  • Как сгенерировать все слова из букв, заданной длины?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    void PrintAllWords(string alphabet,int length){
      PrintAllWords(alphabet,length,"");
    }
    void PrintAllWords(string alphabet,int length,string prefix){
      if(length==0) Console.WriteLine(prefix);
      else foreach(char c in alphabet) PrintAllWords(alphabet,length-1,prefix+c);
    }
    Ответ написан
    Комментировать
  • Как преобразовать определенные биты в числе?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если номер позиции pos, число разрядов len, а число, которое надо изменить - x, то ответом будет
    x | (((1 << len) - 1) << pos)
    Ответ написан
    1 комментарий
  • Какой алгоритм использовать для поиска кратчайшего пути в ненаправленном графе через все вершины?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Гамильтонов путь тут ни при чём - ведь нет запрета проходить одну вершину дважды? Но это в чистом виде задача коммивояжера. Тоже входит в класс NP. Точное решение будет слишком долгим, надо искать приближённые.
    Ответ написан
    3 комментария
  • Не правильная конвертация из float в int C#?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Не воспроизвелось. Написал так:
    static int Val1(){
                float val = 0.94f;
                return (int)(val*100);
            }
            static int Val2() {
                float val = 0.94f;
                float val1 = val*100;
                return (int)(val1);
            }

    Обе функции вернули 94. Как у вас получилось 93?
    Ответ написан
  • Перегрузки методов без дублирования кода в C#?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Пишу общий метод (возможно, со слегка другим набором параметров), который вызываю из каждой из перегрузок. Впрочем, чаще удаётся обойтись вызовом второго метода из первого.
    Ответ написан
    Комментировать
  • Реальное и воображаемое комплексного числа в степени комплексного числа?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    3-i*4 = exp(ln(5)-i*arctg(4/3)+i*2*pi*k)=exp(1.6094379-i*0.9272952+i*2*pi*k)
    (3-i*4)^(2+i)=exp((1.6094379-i*0.9272952+i*2*pi*k)*(2+i))=
    =exp(4.146171042-i*0.24515252+12.56637*i*k-6.283185*k)=
    =(61.30217-i*15.336867)/exp(2*pi)^k
    Ответ из учебника не получается ни при каком k.
    Ответ написан
    Комментировать
  • Как сделать подбор слов из словаря чтобы получилась заданная фраза (анаграммы)?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Многомерная задача о рюкзаке.

    Допустим, у нас есть фраза "aaabbc" и словарь
    aab
    abb
    abc
    bbcc
    aac

    Для фразы считаем, сколько раз в ней встретилась каждая буква. Буква 'a' встречается na=3 раза, буква 'b' - nb=2 раза, буква 'c' - nc=1 раз.
    Заводим битовый массив B с размерностями 0..na, 0..nb. 0..nc (в нашем примере это 24 бита). В элемент (0,0,0) кладём 1, в остальные 0.
    1000 0000
    0000 0000
    0000 0000

    Теперь перебираем слова из словаря. Для каждого слова считаем количество каждой буквы в нём (для aab это ma=2,mb=1,mc=0), и строим массив B1, в котором B1[a,b,c] = B[a,b,c] | B[a-ma,b-mb,c-mc] (для отрицательных индексов считаем значения нулевыми). В нашем случае получится
    1000 0000
    0010 0000
    0000 0000

    Продолжаем для остальных слов. После добавления каждого слова проверяем элемент B[na,nb,nc]. Если он ненулевой - мы нашли вариант (правда, помним из него только последнее слово - остальные восстановим на следующих проходах). Вариант запомним, элемент B[na,nb,nc] обнулим.
    У нас получится:
    abb=(1,2,0)
    
    1000 0000
    0010 0000
    0100 0000
    
    abc=(1,1,1)
    
    1000 0000
    0010 0100
    0100 0001

    Первый вариант есть - он кончается на "abc". Обнуляем B[3,2,1] и продолжаем.
    Слово bbcc=(0,2,2) можно не рассматривать, в нём mc > nc.

    aac=(2,0,1)
    
    1000 0010
    0010 0100
    0100 0001


    Нашли второй вариант - кончается на "aac". Слова в словаре кончились.

    Теперь надо построить фразу "aab" из словаря
    aab
    abb

    и фразу "abb" из словаря
    aab
    abb
    abc
    bbcc

    Теоретически, это можно делать одновременно - но придётся отслеживать несколько индеков. И обнулять их уже нельзя, надо смотреть, не пытаются ли в них записать 1 (даже если там уже было значение 1).
    Если на массив у вас есть 2 ГБ памяти, а разных букв не более 26, то этого хватит на фразу из 39 букв (худший случай - когда 13 букв встречаются по 1 разу, а 13 по 2 раза).
    Ответ написан
    Комментировать
  • Зачем нужно знать машинный код?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В последний раз мне машинный код понадобился совсем недавно, когда я захотел посмотреть, во что компилируется функция из C#. Дебагером пользоваться нельзя - он даёт неоптимизированный код. Поэтому фрагмент кода пришлось вытаскивать прямо в программе (два прыжка по стеку - и я в окрестности точки вызова). Напечатать фрагмент в 16-ричном виде легко, а как его оттуда перетащить в какой-нибудь дизассемблер - неясно. Пришлось поднимать таблицы кодов и разбирать самому.
    Ответ написан
    2 комментария
  • Тау расстояние Кенделла?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В первой расстановке 0 идёт раньше 1 (0, 3, 1...), а во второй - позже (1, 0, 3...) Поэтому их "относительный порядок" разный. Для пар 0,3 и 0,6 порядок одинаковый - в обеих расстановках 0 идёт и раньше 3, и раньше 6.
    "Почему выбраны именно эти пары?" - потому что в остальных порядок одинаковый.
    Ответ написан
    Комментировать