Ответы пользователя по тегу Программирование
  • Как правильно реализовать регулярное выражение без конечных автоматов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Как-нибудь так. Не очень эффективно, правда. И без скобок.
    static string FindReg(string src,string ptrn) {
                int LP=ptrn.Length,LS=src.Length;
                for(int i=0;i<LS;i++) {
                    int k=i;
                    bool ok=true;
                    for(int j=0;ok && j<LP;) {
                        int m=1;
                        bool plus=false;
                        char cur=ptrn[j++];
                        for(;j<LP;j++) {
                            if(ptrn[j]=='+') plus=true;
                            else if(ptrn[j]==cur) m++;
                            else break;
                        }
                        int s=0;
                        while(k+s<LS && src[k+s]==cur) s++;
                        if(s<m) {
                            ok=false; break;
                        } else if(plus) k+=s;
                        else k+=m;
                    }
                    if(ok) return src.Substring(i,k-i);
                }
                return null;
            }

    Но вообще, конечный автомат понадобится очень быстро. Уже для какого-нибудь a*b*ac без него трудно будет обойтись (если не писать страшную рекурсию).
    Ответ написан
    Комментировать
  • Как сделать сортировку матрицы?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Результат сортировки будет красивее, если делать так.
    Рекурсия:
    - делим более длинную сторону матрицы на две равные (или различающиеся на 1) части.
    - если длинная сторона была вертикальной, то сортируем элементы матрицы по y, чтобы элементы с меньшим y оказались в нижней половине, а если горизонтальной - то сортируем по x, чтобы элементы с меньшим x оказались в левой половине. Сортируем не строки-столбцы, а матрицу в целом (как одномерный массив).
    - повторяем процедуру для каждой из полученных половинок.
    Ответ написан
    Комментировать
  • Как найти все комбинации символов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Такие матрицы, судя по всему, описывают возможные бинарные операции на множестве {'a','b','c'}, т.е. функции от двух переменных из этого множества, принимающие значения в этом же множестве.
    Всего таких функций будет 3^9=19683. Поэтому достаточно перебрать числа от 0 до 3^9-1, и троичную запись каждого из них превратить в матрицу. На C# это бы выглядело так:
    char[,] matr=new char[3,3];
        for(int i=0;i<19683;i++){
            int a=i;
            for(int j=9;--j>=0;){
                matr[j/3,j%3]=(char)('a'+a%3);
                a/=3;
            }
            Process(matr);
        }
    Ответ написан
    4 комментария
  • А вы знаете стандартные структуры и алгоритмы?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если искать ответ в виде формулы - то [n*(n+2)*(2*n+1)/8]
    Там для чётных и нечётных n получаются разные серии, поэтому приходится брать целую часть (или мудрить с (-1)^n).
    Ответ написан
    Комментировать
  • В какой области программирования используется физика?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Софт для измерительных приборов и для прочих механизмов, в которых есть движущиеся части (от проекторов до роботов и космических аппаратов) - как embedded, так и на PC. Для корректного управления и корректной интерпретации показаний датчиков физика очень полезна.
    Ответ написан
    Комментировать
  • Закрасить часть фигуры "Инь-Янь" c#?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Проще всего чередовать рисование чёрным и белым - нарисовать чёрный полукруг, потом 4 круга и внешнюю окружность. Как-то так:

    private static void DrawYinYang(Graphics gr,int xctr,int yctr,int rmax,int rint,int ysmall,int rsmall) {
                Brush white=Brushes.White;
                Brush black=Brushes.Black;
                Pen BlackPen=new Pen(Color.Black,2*(rmax-rint));
    
                gr.FillPie(black,xctr-rmax,yctr-rmax,2*rmax,2*rmax,-90,180);
                gr.FillEllipse(white,xctr-rint/2,yctr-rint,rint,rint);
                gr.FillEllipse(black,xctr-rint/2,yctr,rint,rint);
                gr.FillEllipse(white,xctr-rsmall,yctr+ysmall-rsmall,2*rsmall,2*rsmall);
                gr.FillEllipse(black,xctr-rsmall,yctr-ysmall-rsmall,2*rsmall,2*rsmall);
                double rcircle=(rmax+rint)/2.0;
                gr.DrawEllipse(BlackPen,(float)(xctr-rcircle),(float)(yctr-rcircle),(float)(2*rcircle),(float)(2*rcircle));
            }

    Если же хочется именно закрасить криволинейную фигуру, надо изучать, что такое GraphicPath, и использовать FIllRegion. Но я так не пробовал.
    Ответ написан
    Комментировать
  • Проективное преобразование (поиск относительного положения точки)

    Mrrl
    @Mrrl
    Заводчик кардиганов
    А можете для какого-нибудь примера написать полученные прямую и обратную матрицы? Например, для A=M, B=N, D=K, C=(2,2) ?
    Ответ написан
  • Как построить матрицу проективного преобразования без сторонних библиотек?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Проще всего сначала построить матрицу преобразования из квадрата в 4-угольник, а потом взять обратную.
    Точки плоскости будем записывать, как принято в компьютерной графике, как строки: (x y 1) для собственной точки и (x y 0) для несобственной. Строка (c* c*y c) обозначает ту же точку, что и (x y 1) (при с!=0).
    Пусть матрица преобразования M=((a11 a12 a13) (a21 a22 a23) (a31 a32 a33)). Точка (u,v) квадрата переходит в точку (x,y) четырёхугольника, если для некоторого с!=0 выполняется
    (u v 1)*M=(c*x c*y c).
    Сначала возьмём вершину (0,0). Получим
    a31=c1*x1, a32=c1*y1, a33=c1. Видно, что мы можем взять a33=c1=1 (матрица тоже определена с точностью до пропорциональности), и у нас есть последняя строчка:
    a31=x1, a32=y1, a33=1.
    Теперь подставим остальные вершины. Получим 9 уравнений:
    a11+x1=c2*x2
    a12+y1=c2*y2
    a13+1=c2
    a11+a21+x1=c3*x3
    a12+a22+y1=c3*y3
    a13+a23+1=c3
    a21+x1=c4*x4
    a22+y1=c4*y4
    a23+1=c4
    Это квадратная система из 9 линейных уравнений. Её легко решить методом Гаусса. А можно вручную исключить все переменные, кроме c2,c3,c4, получить систему из 3 уравнений, решить каким-нибудь методом Крамера (через определители) и восстановить a11,a12,...,a23.
    Потом уже посчитать матрицу, обратную к построенной. Можно тоже через определители.
    Ответ написан
  • Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна?

    Mrrl
    @Mrrl
    Заводчик кардиганов

    На каждом отрезке от 10*n до 10*n+9 таких чисел ровно 5. Поэтому нам достаточно посчитать число таких полных отрезков, и обработать краевые отрезки. Пусть sumdig(n) - функуция, которая выдаёт остаток от деления суммы цифр n на 2. Тогда: int s0=(B/10-A/10-1)*5; int s1=(10+sumdig(A/10)-A%10)/2; int s2=(2+B%10-sumdig(B/10))/2; return s0+s1+s2;

    Ответ написан
    Комментировать
  • Какие кодотрюки вы знаете?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Недавно придумал, как считать ненулевые биты в int:

    res=0; while(a){ a&=a-1; res++;}

    Потом оказалось, что в Hacker's Delight оно уже есть.
    Ответ написан
    Комментировать
  • Интересная задача на логику?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если уж упрощать, то:

    1. Ставим на ячейку 1.
    2. A:=1
    3. A:=A*2
    4. Делаем A шагов вправо, после каждого шага записываем в ячейку 0.
    5. Делаем A шагов влево.
    6. Если в ячейке 1, идем на пункт 3.
    7. Ставим в ячейку 1 и идем вправо, считая шаги, пока не найдем 1.

    Максимальное число шагов — N*9-12 (при N>1)
    Ответ написан
  • Интересная задача на логику?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Вопрос в том, сколько у нас памяти — можем ли мы запомнить число N. А то дадут вам массив длиной в 2^2^64…
    Интересно было бы написать программу для машины Тьюринга, которая выключит свет во всем поезде.
    Ответ написан
    1 комментарий