Ответы пользователя по тегу Алгоритмы
  • Как найти из 4 чисел, где 3 равные между собой одно не равное, за один раз?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Надо уточнить - что считать, операции сравнения, или условные операторы. Считать написанные операции/операторы, или выполняющиеся.
    Возможные варианты решения:
    return a==b ? (a==c ? d : c) : (a==c ? b : a);
    int X[4];
    return X[(X[0]==X[2])+2*(X[0]==X[1])];

    int f(int p,int q,int r){
      return p==r ? q : p;
    }
    int g(int a,int b,int c,int d){
      return a==b ? f(c,d,a) : f(a,b,c);
    }

    int x=a^b,y=a^c;
    x=(x|-x)>>31; y=(y|-y)>>31;
    return ((a^b^c^d)&x&y)^((b^d)&x)^((c^d)&y)^d;

    (в последнем вообще нет сравнений и условных операторов).
    Ответ написан
  • Как на основе расстояния Левенштейна вывести промежуточные слова?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Достаточно для каждого элемента массива запоминать последовательность действий - "как мы сюда попали". Например, в виде строки с 4 командами - "вставили символ X", "удалили символ X", "заменили X на Y" (X и Y могут совпадать).
    Если вторая строчка была "ABCD", то массив, соответствующий начальному состоянию D2, будет выглядеть так:
    {"","iA","iAiB","iAiBiC","iAiBiCiD"} - это команды, переводящие пустую строку в различные начальные подстроки этой второй строки.
    По мере пересчёта массивов строки будут удлиняться, и в итоге мы получим некоторую строку с командами, переводящими строку1 в строку2. Например, для перевода ASTRA в STARKA это может быть "dArSSrTTiArRRiKrAA".
    Дальше можно выполнить несколько первых команд и игнорировать остальные. Увеличивая число выполненных команд, получим промежуточные строки: ASTRA, STRA, STARA, STARKA
    Ответ написан
  • Как можно найти вершинное покрытие графа за линейное время, если граф является деревом?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Рекурсия.
    Для каждого поддерева ищем два покрытия: P - минимальное покрытие вообще, и Q - минимальное покрытие, содержащее корень. Пусть T - наше дерево, X - его поддеревья, растущие из детей корня. Тогда
    Q(T)=1+sum(P(X))
    (корень включён, все рёбра, идущие к нему, учтены, в поддеревьях можно выбирать любые покрытия)
    P(T)=min(Q(T),sum(Q(X)))
    (либо корень не включён - и надо брать покрытия поддеревьев, содержащие корни, либо взять уже построенное покрытие Q).
    Для листьев P=0, Q=1.
    Ответ написан
  • Как избавится от царапин на изображении?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если времени не жалко, то можно попробовать так:
    - берём все пары точек, находящихся на разных сторонах квадрата
    - каждую такую пару соединяем отрезком, и считаем среднюю яркость на нём (это примерно то же, что и преобразование Хафа, только более специализировано для задачи. И гораздо дольше)
    - получается функция от двух переменных. Ищем её максимум - это самая яркая царапина.
    - просматриваем параллельные прямые в окрестности, ищем ширину пика (ширина царапины)
    - заменяем точки на найденной царапине линейной интерполяцией ближайших точек, лежащих за её пределами. Или просто помечаем точки полосы как некорректные, и идём дальше.
    - убираем этот пик на двумерной функции, переходим к следующему максимуму.
    - после того, как удалили 10 (или 50, или 100) царапин, показываем картинку, и спрашиваем, продолжать ли.
    - если продолжать - пересчитываем функцию заново.
    Основным вопросом будет "как считать ширину пика". Я не знаю, надо смотреть конкретные графики.
    Ответ написан
  • Нужно преобразовать номерную емкость из одного формата в другой, кто может подсказать алгоритм?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Хорошая задача. На C# это бы выглядело так:
    long x0=9266070005,x1=9266099923;
                long n=1;
                x1++;
                while(x0<x1) {
                    if(x1-x0<n) n/=10;
                    else if((x0/n)%10==0 && x1-x0>=10*n) n*=10;
                    else{
                        Console.Write("{0}, ",x0/n);
                        x0+=n;
                    }
                }

    Можно ли это хорошо переписать на PHP, не знаю.
    Ответ написан
  • Как определить координаты тела, если оно движется по эллипсу?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Звезда не в центре, а в фокусе эллипса. Всё, что вам нужно знать (кроме ориентации эллипса в пространстве) - это то, что секторная скорость планеты постоянна. Ещё потребуется период обращения T и момент, когда планета проходила перигелий.
    Дальше просто. Пусть (a,b) - полуоси эллипса, звезда в фокусе (c,0), где c=sqrt(a^2-b^2), планета в точке X=(a*cos(x),b*sin(x)). Площадь сектора, "заметённого" планетой, равна S(x)=(a*b*x-c*b*sin(x))/2, а сектор, который она проходит за год - S(T)=a*b*pi. Поэтому, в точке X планета оказывается в момент t(x)=T*(x-c*sin(x)/a)/(2*pi). Решать уравнение, чтобы получить t(x), придётся численно.
    Ответ написан
  • Нужен эвристический алгоритм заполнения таблицы или существует обычный?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сразу можно сказать, что число столбцов в таблице - L=M*(N-1)/2+1, число строк - K=M*L/N. Оба этих числа должны быть целыми.
    В частном случае, когда N=q+1, M=2*(q+1), где q - простое число или степень простого, матрицу построить можно, в ней каждая строка будет встречаться дважды, а верхняя (и нижняя) половинка матрицы будет матрицей инцидентности конечной проективной плоскости. В остальных случаях - боюсь, что нужна эвристика, или вообще полный перебор. Всё-таки, это получается задача о покрытии - надо покрыть удвоенный набор рёбер полного графа с L вершинами непересекающимися графами с N вершинами. Свойство "в каждом столбце M ячеек" выполнится автоматически.
    Ответ написан
  • Как найти максимальное значение без ?/switch/if?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно с битовыми операциями, в расчёте на 32-битную архитектуру:

    var arr=new int[]{1,2,3,4,5,6,98,65,190};
        int max=arr[0];
        foreach(int x in arr){
            int y=max-x;
            max-=y&(y>>31);
        }
    Ответ написан
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Задача о рюкзаке, даже о двух :)
    Заводите массив M[0..S/3,0..S/3] (можно битовый, но лучше побольше - чтобы хранить обратные ссылки). В нём будут отмечены элементы M[a,b], такие, что из уже просмотренных элементов текущего набора можно выбрать непересекающиеся подмножества с суммами a и b.
    Когда приходит очередной элемент x - выполняете M[a,b]=M[a,b] | M[a-x,b] | M[a,b-x] для всех a,b начиная с конца (с больших a,b). Если при этом 0 сменился на 1 - помечаете в массиве обратных ссылок, из какого элемента вы сюда попали.
    Сложность - O(n*S^2). Можно ли сделать лучше, не знаю.

    Вот вариант кода - но он печатает только два множества. Как напечатать третье, разберётесь.
    spoiler
    static void Main(string[] args) {
                int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
                int S=0;
                foreach(int x in dat) S+=x;
                if(S%3!=0) {
                    Console.WriteLine("-1"); return;
                }
                S/=3;
                int[,] M=new int[S+1,S+1];
                M[0,0]=-1;
                foreach(int x in dat) {
                    for(int a=S;a>=0;a--) {
                        for(int b=S;b>=0;b--) {
                            if(M[a,b]==0) {
                                if(a>=x && M[a-x,b]!=0) M[a,b]=x;  // back by set1
                                else if(b>=x && M[a,b-x]!=0) M[a,b]=-x;  // back by set2
                            }
                        }
                    }
                }
                if(M[S,S]==0) {
                    Console.WriteLine("-1"); return;
                }
                int u=S,v=S;
                string res1="",res2="";
                while(u!=0 || v!=0) {
                    if(M[u,v]>0) {
                        res1+=" "+M[u,v]; u-=M[u,v];
                    } else {
                        res2+=" "+(-M[u,v]); v+=M[u,v];
                    }
                }
                Console.WriteLine(res1);
                Console.WriteLine(res2);
            }

    Ответ написан
  • Существует ли какой-нибудь алгоритм склонения существительных во множественном числе?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно было бы как-то так:
    static int pres,qres;
    static int[] A;
    static int M=10;
    
    bool Find1(int p,int q){
      if(A[q]-A[p]==M){ 
        pres=p; qres=q;
        return true;
      }
      if(A[q]-A[p]<M || q-p<2) return false;  
      int k=p+(q-p)/2;
      if(Find1(p,k) || Find1(k,q)) return true;
      return Find2(p,k,k+1,q);
    }
    
    bool Find2(int p1,int q1,int p2,int q2){  // p1<=q1<p2<=q2
      if(A[p2]-A[q1]>M || A[q2]-A[p1]<M) return false;
      if(A[p2]-A[p1]==M){
        pres=p1; qres=p2; return true;
      }
      if(A[p1]==A[q1] && A[p2]==A[q2]) return false;
      if(A[q1]-A[p1]>A[q2]-A[p2]){
        int k=p1+(q1-p1)/2;
        return Find2(p1,k,p2,q2) || Find2(k+1,q1,p2,q2);
      }else{
        int k=p2+(q2-p2)/2;
        return Find2(p1,q1,p2,k) || Find2(p1,q1,k+1,q2);
      }
    }

    (функция Find1 ищет пару в одном фрагменте, Find2 - в двух непересекающихся фрагментах). Но я совершенно не представляю, какая получится сложность. Не исключено, что O(n*log(n)). Зато рекурсия используется по назначению :)
    UPD. Немного поправил условия - здесь часто лучше сравнивать не индексы, а сами элементы.
    Ответ написан
  • Что не так с алгоритмом для поиска наибольшей неубывающей подпоследовательности?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
    Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
    [1,2,7,8,9]
    [1,2,5,6]
    [1,2,3]
    [1,2]
    [1]
    Любая из этих последовательностей может быть началом правильного ответа.
    Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
    Для примера [1,2,7,8,9,5,6,3] получаем
    d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
    (значение -1 используется для обозначения ситуации "нет такого индекса").
    Ответ написан
  • Как решить задачу об огурцах?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Нужно многоугольник делить делителями. Координаты делителей относительные. Например это может быть процент или расстояние от первой точки многоугольника. Пока это неважно.

    На самом деле, это очень важно.
    Если под "делителем" вы имеете в виду отрезок, каждый конец которого определяется как точка, делящая какой-то уже построенный отрезок в определённом (известном и неизменном) отношении, то задачу решить можно.
    На примере вашего 5-угольника. Пусть его вершины - ABCDE, заданные по часовой стрелке, AB - верхняя сторона. Пусть первый (самый левый) делитель PQ, точка P делит отрезок AB в отношении 3:7, точка Q делит отрезок DE в отношении 6:4. Точка R (левый конец внутреннего делителя) делит отрезок PQ тоже в отношении 6:4.
    Запишем:
    P = 0.7*A + 0.3*B
    Q = 0.4*D + 0.6*E
    R = 0.4*P + 0.6*Q
    Здесь сложение и умножение точек выполняется покоординатно, и если точка K делит отрезок MN в отношении m:n, то мы пишем K=M*(n/(m+n))+N*(m/(m+n)).
    Подставив P и Q в последнее уравнение, получим R=0.28*A+0.12*B+0.24*D+0.36*E - выражение координат этой точки через координаты вершин исходного пятиугольника. Таким образом, для каждой точки достаточно хранить n чисел - коэффициенты в этом выражении.

    При других определениях координат точек придётся хранить и обрабатывать всё дерево вычислений, там держать данные на одном уровне не получится.
    Ответ написан
  • Необходим найти совпадающие участки в двух битовых массивах, как это сделать?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Думаю, что вам поможет суффиксный массив. Если объединить исходные строки (вставив между ними пробел) и построить для полученной строки суффиксный массив, то ответ будет на одном из переходов индекса из одной строки в другую. Надо только найти (или поддерживать) длину совпадающего фрагмента на переходах.
    Ответ написан
  • Возможно упростить алгоритм?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Как-нибудь так? Правда, это C#, но разница должна быть небольшая.

    public static String moveLetters(String a) {
            int L=a.Length;
            char[] chars = new char[L];
            for(int x=0;x<L;x++) chars[x]=a[x==1 ? L-L%2-1 : x-2*(x%2)];
            return new String(chars);
    }
    Ответ написан
  • Как запрограммировать нахождение стационарного распределения методом Гаусса?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Переписываете первые 3 строчки в виде
    p1*(0.1967-1) + p2*0.4561 + p3*0.3321 + p4*0.2982 = 0
    p1*0.0750 + p2*(0.0553-1) + p3*0.1986 + p4*0.0325 = 0
    p1*0.2239 + p2*0.4863 + p3*(0.0291-1) + p4*0.3382 = 0

    Четвёртая не нужна - она является их линейной комбинацией.
    Добавляете к ним строчку
    p1*1+p2*1+p3*1+p4*1=1
    Получаете квадратную систему линейных уравнений. Решаете её методом Гаусса на любом известном вам языке - и всё.
    Ответ написан
  • Как аппроксимировать синусоиду по трем параметрам?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если X идёт с равномерным шагом, то МНК не нужен.
    Сначала сводите задачу к Y=a+d*sin(X)+f*cos(X).
    Довольно очевидно, что a=sum(Y)/n (поскольку sum(sin(X))=sum(cos(X))=0).
    Далее, умножаете обе части исходной формулы на sin(X):
    sum(Y*sin(x))=a*sum(sin(X))+d*sum(sin(X)^2)+f*sum(sin(X)*cos(X))
    Выполняются условия sum(sin(X))=sum(sin(X)*cos(X))=0, sum(sin(X)^2)=n/2 (если n > 2). Отсюда d=sum(Y*sin(X))*2/n. Аналогично, f=sum(Y*cos(X))*2/n.
    Ответ написан
  • Как привести формулу к виду КНФ?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Считать значение формулы при заданных значениях переменных научились? Если да - перебираете все наборы значений (a_1,...,a_n) (их всего 2^n), считаете для каждого значение формулы, и если получился 0 - добавляете в формулу очередную дизъюнкцию ((x_1 xor a_1) or (x_2 xor a_2) or ... or (x_n xor a_n)).
    Ответ написан