Ответы пользователя по тегу Программирование
  • Как найти из 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
    Заводчик кардиганов
    Применяется при поиске корня функции делением отрезка пополам. Для любой последовательности знаков f(x) для середин отрезка мы получаем некоторое число - корень уравнения. Конечно, в действительности мы делаем только конечное число шагов и получаем число из конечного множества, но сам факт, что метод работает, а корень существует, основан, в том числе, на континуальности отрезка. Если бы у нас были только рациональные числа, то уравнение x^2=2 корня бы не имело, и мы не имели бы права сказать, что мы находим его с нужной точностью.
    Ответ написан
  • Когда ооп быстрее процедурного?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Про РНР не знаю, скажу на примере С/С++.

    Если виртуальными функциями не пользоваться, то C и C++ дадут одинаковую эффективность.
    Если пытаться один и тот же код, требующий run-time полиморфизма написать на C и на C++, то, вероятнее всего, код на C++ будет эффективней. Потому что у вас не хватит терпения аккуратно заполнять и использовать таблицы виртуальных функций, и получится код с большим количеством case, а то и if/else по тегам объектов. В конечном итоге, можно будет написать программу на C, эквивалентную программе на С++ (а потом её соптимизировать), но она будет сложной, непонятной, и практически нерасширяемой: добавление нового полиморфного метода в систему типов (с модификацией всех таблиц и всех методов, работающих с тегами) будет мучением.
    Ответ написан
  • Стоит ли читать WEB-программисту книгу "Д.Е Кнут искусство программирования"?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Видимо, задан ряд (в данном случае: -3, 6, -9, 12, -15, ...), и какое-то N. Надо найти сумму и произведение первых N элементов.
    В данном случае при N=4 сумма будет -3+6-9+12=6, а произведение - 1944.
    При N=5 сумма равна -9, а произведение -29160.
    Ответ написан
  • Как определить координаты тела, если оно движется по эллипсу?

    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
    Заводчик кардиганов
    Можно было бы как-то так:
    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
    Заводчик кардиганов
    Чтобы найти точку "в плоскости", вам нужно задать в ней систему координат. То есть, выбрать точку начала координат O(x0,y0,z0) и два базисных вектора X=(x1,y1,z1) и Y=(x2,y2,z2). Судя по тому, что вы говорите про "декартову систему координат", векторы должны быть единичной длины и перпендикулярны друг другу.
    Добавляете к системе вектор Z, параллельно которому идёт проектирование. Из условия непонятно, рассматриваете вы только ортогональную проекцию, или общий случай параллельной проекции.
    В случае ортогональной всё просто - не нужно даже возиться с матрицами:
    вектор Z вычисляется как векторное произведение X и Y, но он нам не нужен вообще: если проектируемая точка P имеет координаты (x,y,z), то её проекция Q будет иметь координаты (в системе координат плоскости)
    x'=(P-O,X)=(x-x0)*x1+(y-y0)*y1+(z-z0)*z1
    y'=(P-O,Y)=(x-x0)*x2+(y-y0)*y2+(z-z0)*z2.
    В случае косоугольной проекции вычисления сложнее - надо умножать вектор (P-O) на матрицу, обратную к матрице, составленной из X,Y,Z. И там главное не запутаться, где строки, а где столбцы.
    Ответ написан
  • В чем разница между Ассемблером и Компилятором?

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

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

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

    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.
    Ответ написан
  • C# заменит ли Java?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Возможно, что и никогда - вряд ли многие захотят переходить с Java на C#, равно как и с C# на Java.
    Когда появился C# (в 2003 году), мы перевели на него проект с С++ без колебаний и без особых проблем. С тех пор не жалеем. Идеи переносить его на Java даже не возникало.
    В этом году понадобилось запустить одну из программ проекта на встроенном компьютере с Linux - тоже пошла почти сразу (под Mono). Причин переходить на Java или возвращаться на С++ не возникло.
    Но возможно, что у тех, кто пишет на Java, точно так же не возникает причин переходить на C#.
    Ответ написан
  • Как задать массив с целыми и вещественными числами?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Не bouble, а double.
    В описании массива пишете
    double *arr2;
    а в инициализации -
    arr2=new double[n];
    Если поменять тип только в одном месте, будет ошибка.
    Ответ написан
  • Можно ли в Си инициализировать счетчик массива не последовательными значениями?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Вы хотите цикл, чтобы его счётчик пробегал значения из массива?
    Ничего не получится, придётся писать так:
    int f[F] = {1,12,3,5};
        for (int i=0; i<F ; ++i){
             int v=f[i];
             ...
        }

    (правда, это не совсем С - в С переменные v и i пришлось бы описывать раньше).
    В каком-нибудь С# для этого есть цикл foreach.
    Ответ написан