Ответы пользователя по тегу Алгоритмы
  • Виртуальное хеширование?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Английский там простой. Даже чересчур простой (что не удивительно, учитывая, что это писали французы) - и в результате этого упрощения существенные детали скрылись или потерялись.
    Общая идея понятна: мы вычисляем номер корзины при хешировании как K=C%N (где C - значение hash key), а когда корзина переполняется, увеличиваем для неё N в 2 раза, и перекидываем часть элементов (для которых C%(2*N)!=K) в корзину с номером K+N. У корзины как-то запоминаем актуальное для неё значение N=N0*2^j (точнее, запоминаем j).
    Дьяволы, как обычно, прячутся в деталях, и эти детали при первом прочтении мне понять не удалось:
    - до переполнения в корзине может храниться более одного элемента. Где они хранятся? Для них сразу зарезервировано место, или где-то есть место для хранения списка?
    - Что они делают при увеличении N? Неужели удваивают размер всей таблицы? Или каким-то образом отводят место только для новых корзин - потомков переполнившихся?
    Не знаю, какая у Вас цель, но я бы в этот момент придумал какую-нибудь схему, рещающую эти вопросы (вероятно, представил бы корзины в виде бинарного дерева, где пути влево-вправо определяются битами в последовательности остатков C%(N*2^j)), не пытаясь разобраться в статье дальше. Но если нужно разобраться именно в этом алгоритме - придётся его читать.
    Кстати, какого года статья? По общему впечатлению (и по датам цитируемых работ), это где-то 1979-1985 гг. Не забывайте, что тогда "640 КБ хватало всем"!
    Ответ написан
    1 комментарий
  • Как получить нужное число, который получается в результате сложения чисел из указанного массива?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В вашем примере каждое из чисел, кроме 5, делится на предыдущее. Поэтому, до определённого момента - пока осталось заплатить не меньше 10 руб, и в кошельке есть купюры не меньше 10 - можно пользоваться "жадным" алгоритмом - брать самую большую купюру, которая меньше остатка стоимости товара.
    Допустим, что остались только монеты по 1,2,5 руб. Если есть хотя бы одна монета 1 руб - то платить пятирублёвой монетой безопасно, даже если останется нечётная цена - то набрать её рублём и двушками удастся. Если есть две монеты по 5 руб, и осталось заплатить не меньше 10 - смело тратьте одну из них. Вторую тратить подождите, это может быть опасно.
    В конце концов у вас останутся только пятачки и двушки, причём либо пятачков не более одного, либо осталось заплатить меньше десятки. Смотрите. Если надо заплатить нечётную сумму: если пятачков нет или надо заплатить 1 или 3 рубля - задача неразрешима. В противном случае тратите пятачок, остаётся чётная сумма.
    Пытаетесь набрать остаток двушками. Если их хватило - вы победили. Если нет, то вам подсунули неразрешимый пример...
    Если бы набор купюр и монет был из времён СССР (1,2,3,5,10,15,20,50,100,300,500,1000,2500,5000,10000), задача была бы значительно сложнее и интереснее.

    UPD. Моё решение неверно. Кто найдёт контрпример?

    Более правильный вариант.
    - если есть хотя бы одна монета в 1 руб, то работает "жадный" алгоритм - в цикле платите самой большой купюрой, которая у вас есть и не превышает остатка суммы.
    - если монеты 1 руб. нет:
    - - если сумма, которую надо набрать, нечётна, а пятачка нет, вы проиграли.
    - - если сумма, которую надо набрать, нечётна, и есть хотя бы один пятачок, вносим его. Переходим к следующему пункту.
    - - если остаток суммы, который надо набрать, чётен - объединяем пятачки в пары (и по одному пятачку платить не будем, даже если хочется). И запускаем жадный алгоритм. Если задача разрешима, то он справится.
    Ответ написан
    6 комментариев
  • Как построить сложный алгоритм на комбинаторику?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    static int sstep;
           static void FindAll(int N,int sum,int step,bool ord){
                sstep=step;
                sum/=step;
                fill(new int[N],N,sum,sum-N+1,ord);
            }
            static void output(int[] A){
                  Console.Write("{0}",A[0]*sstep);
                  for(int i=1;i<A.Length;i++) Console.Write("/{0}",A[i]*sstep);
                  Console.WriteLine();
            }
    
            static void fill(int[] A,int N,int sum,int smax,bool ord) {
                if(N==0 && sum==0) {
                    output(A);
                    return;
                }
                if(N==0 || sum<N) return;
                int smin=ord ? 1 : (sum-1)/N+1;
                N--;
                for(A[N]=smin;A[N]<=smax;A[N]++) {
                    fill(A,N,sum-A[N],ord ? sum-N+1 : A[N],ord);
                }
            }

    Задаётся A=new int[N], и вызывается fill(A,N,sum,sum-N+1,ord), где N=6, sum=300, ord - true, если с учётом порядка и false, если без учёта. Я проверял для N=5, sum=10 - там число вариантов приемлемо. Насколько я понимаю, для (6,300,true) будет примерно 21 миллиард комбинаций (Comb(299,5)), а для (6,300,false) - не меньше 30 миллионов.
    Ответ написан
  • Как распределить грузы по вагонам равномерно?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    (Про исходную задачу)
    После того, как отправили самые тяжелые грузы (которые больше средней загрузки вагона), пересчитываем среднее арифметическое, и начинаем укладывать грузы в вагоны, начиная с самого тяжелого. Возможны три стратегии.
    1) Очередной (самый тяжелый из оставшихся) груз кладём в самый пустой вагон
    2) Очередной груз кладём в самый загруженный из вагонов, в которые этот груз ещё помещается (т.е. общий вес вагона и груза не превосходит среднего арифметического)
    3) Очередной груз кладём в случайный из вагонов, в которые груз помещается.
    В стратегиях (2,3) иногда будет возникать ситуация "груз положить некуда". Тогда кладём его в самый пустой вагон, и отправляем.
    Дальше надо экспериментировать, чтобы выбрать более подходящую из этих стратегий. Интуиция тут не очень помогает.

    Если у вагона есть предел загрузки L, то груз, который не умещается даже в самый пустой вагон, оставляем до следующего поезда. При его загрузке сначала раскидываем очень тяжелые грузы, потом - оставленные от предыдущего поезда, потом - все новые.
    Ответ написан
    Комментировать
  • Расчет количества замощений прямоугольника меньшими прямоугольниками?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Здесь достаточно перебора с помощью рекурсии.
    Вам нужно заполнить прямоугольник M*N плитками размером 1*2.
    Берёте массив A[M,N], заполняете его нулями.
    Вызываете функцию Fill(A,1).
    Fill(A,k){
    Ищете первый элемент A[p,q], равный нулю.
    Если не нашли - массив заполнен, печатаете его. return.
    Если элемент A[p+1,q] существует и равен нулю, то в прямоугольник можно положить горизонтальную плитку: в A[p,q] и A[p+1,q] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p+1,q].
    Если элемент A[p,q+1] существует и равен нулю, то в прямоугольник можно положить вертикальную плитку: в A[p,q] и A[p,q+1] кладёте число k, вызываете Fill(A,k+1). Обнуляете A[p,q] и A[p,q+1].
    }
    Если бы надо было считать число способов заполнения, надо было бы смотреть в сторону динамического программирования.
    Ответ написан
  • Как сделать сортировку матрицы?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если это C++, то подойдёт такая формула:
    M[i][j]=(abs(j-i)+1)*((i+j-N+1)*(i-j)>=0)
    Если формулу хочется чисто математическую, то вместо ((i+j-N+1)*(i-j)>=0) можно написать (sign(2*(i+j-N+1)*(i-j)+1)+1)/2
    Ответ написан
    Комментировать
  • Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно решить и за линейное время (после сортировок):
    1) берём массив концов отрезков (xi,1) и (yi,-1), сортируем (не забывая, что при одинаковых первых числах сначала идут все начала отрезков, а потом все концы: так для отрезков [1,2] и [2,3] получим массив (1,1),(2,1),(2,-1),(3,-1))
    2) берём массив длиной n (число точек), заполняем его числами от 1 до n (если пишем на C-подобных языках - то от 0 до n-1). Cортируем массив, используя условие less(a,b)=(P[a] < P[b]), где P - массив точек. Получим индексы точек, отсортированные по возрастанию координат соответствующих точек.
    3) Идём по обоим массивам, сравниваем координаты. Когда проходим точку в массиве концов, то прибавляем к счётчику второй элемент. Когда достигаем координаты очередной точки из P - записываем в массив результатов значение счётчика. Не забываем, что точка P[a]=x обрабатывается после всех точек (x,1) но до всех точек (x,-1) из массива концов.
    4) Выводим массив результатов.
    Ответ написан
    2 комментария
  • Каким будет время работы построения кучи?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    О(N*log(N)). Для каждого из последних N/2 элементов нужно примерно по log(N) операций.
    Вот построить кучу, переставляя элементы уже заполненного массива, можно за O(N) операций.
    Ответ написан
    5 комментариев
  • Как расположить функции в порядке увеличения скорости роста?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    f4 - это sqrt(n) или sqrt(5)? А то в разных местах по-разному.
    Если предположить, что sqrt(n), то в вашем ответе не на месте функция f1. Она растёт гораздо медленнее, чем вы думаете.
    Ответ написан
    1 комментарий
  • Как найти все комбинации символов?

    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 комментария
  • Как решается уравнение x^x?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Уравнение x*ln(x)=c решать проще. Можно методом Ньютона. А можно и итерациями: x_{n+1}=c/ln(x_n), сходиться должно очень быстро.
    UPD. Хотя нет, оно будет сходиться только при c>e. Метод Ньютона, всё-таки, надёжнее:
    x_{n+1}=(c+x_n)/(ln(x_n)+1)
    Ответ написан
    Комментировать
  • Как найти мантиссу десятичного числа?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Здесь "изящное" и "быстроработающее" - слегка противоречивые требования. Быстрее всего будет определить число знаков делением пополам за 3-4 сравнения:
    double mantissa(int c){
      int a=abs(c);
      int b=1;
      if(a>=100000){
        if(a>=10000000){
          if(a>=1000000000) b=1000000000;
          else if(a>=100000000) b=100000000;
          else a=10000000;
        }else if(a>=1000000) b=1000000;
        else b=100000;
      }else{
        if(a>=100){
          if(a>=10000) b=10000;
          else if(a>=1000) b=1000;
          else a=100;
        }else if(a>=10) b=10;
      }
      return (double)c/b;
    }

    но такой код трудно назвать красивым.
    Лучше всего был бы цикл, но не с делением, а с целочисленным умножением на 10. Но там надо следить за переполнением.

    Можно, конечно, и через float. Но там после вычисления порядка надо будет возвести 10 в нужную степень, а функция pow может оказаться для этого слишком долгой.

    double mantissa(int a){
    	if(a==0) return 0;
    	float f=a;
    	int b=((*(int*)&f&0x7fffffff)-0x40cd3ed7)/0x019a7daf;
    	double d=a*pow(0.1,b);
    	if(fabs(d)>=10) d/=10;
    	return d;
    }
    Ответ написан
    Комментировать
  • Какую кривую эффективнее построить на множестве [0; 1] - Безье, нецелочисленную степенную или гиперболу?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если надо, чтобы кривую можно было провести через любую точку квадрата, то гипербола, пожалуй, лучше. Уравнение выглядит привлекательно: (a^2-1)*x*y+(x-a^2*y)=0, найти значение a для любой точки, через которую проходит кривая, несложно. Немного сложнее её нарисовать, чтобы точки были расположены с нужной густотой.
    Я думал над чем-нибудь вроде y^a+(1-x)^a=1, но оно вряд ли подойдёт, хоть и симметрично: семейства кривых при a<1 и a>1 получаются не симметричными друг другу.
    Ответ написан
  • Как составить все возможные комбинации размещения 10 яблок на 21 тарелке?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    На C это бы выглядело так:
    int k=21,m=10,s,h;
    	for(s=(1<<m)-1;s<(1<<k);){
    		printf("%x ",s);
    		h=s&-s;
    		s+=h;
    		s+=(s&-s)/(2*h)-1;
    	}
    	printf("\n");

    Печатаются числа, единички в двоичной записи которых образуют маску занятых тарелок.
    Ответ написан
    Комментировать
  • Какой выбрать алгоритм для решения задачи?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если есть память N*2^N, где N - число городов, то можно воспользоваться динамикой по набору пройденных городов плюс последнему городу, где оказался коммивояжер. Для каждого такого сочетания запоминаем минимальное количество топлива, которое потребовалось, чтобы добраться до этой ситуации и город, из которого приехали в последний город. Потом для всех ситуаций проезжаем из последнего города по всем рёбрам, и попадаем в ситуации, где посещённых городов на 1 больше. Снова для каждой находим оптимальный (по топливу) путь, по которому мы туда попали... и так, пока топливо не кончится. После чего проходимся по всему списку, и смотрим, где больше собрано призов.
    До 20-25 городов должно работать разумное время. Дальше придётся искать эвристики.
    Ответ написан
    Комментировать
  • Найти количество чисел заданного порядка, модуль разницы соседних цифр которых не больше 1

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Формула, несомненно, существует. Правда, в ней будут присутствовать корни многочлена (z^5-6*z^4+10*z^3-z^2-6*z+1)*(z^5-4*z^4+2*z^3+5*z^2-2*z-1) (неразрешимого в радикалах), и выписать её совсем не просто. Но, при большой необходимости, возможно.
    Впрочем, если в формуле может присутствовать матрица, то ответ такой:

    (1 1 1 1 1 1 1 1 1 1)*(M^(n-1))*transpose(0 1 1 1 1 1 1 1 1 1),

    где M - матрица 10х10, в которой в клетках (m,n), для которых abs(m-n)<2, стоят единицы, а в остальных клетках - нули.
    Ответ написан
  • Сколько треугольников на картинке?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Без априорной вероятности тут тяжело. Одно наблюдение (или любое число наблюдений) может уточнить вероятность той или иной ситуации, но определить её с нуля не сможет.
    Например, в случае лотереи. Одно дело, когда вы считаете, что вероятность выигрыша может быть любой, скажем, от 1/100 до 1/1000, причём вероятности этих значений примерно одинаковы. Тогда, после своих наблюдений, вы можете сказать, что вероятность, скорее всего, близка к 1/550, и даже определить распределение этой вероятности. Другое дело, когда вы знаете, что в лотерее может быть вероятность выигрыша только 1/200, 1/500 или 1/1000, но не знаете, в какую из лотерей играете (хотя шансы на то, что вам подсунули каждую из них, равны). Тогда ваши наблюдения покажут, что вероятность, скорее всего, 1/500 (а вовсе не 1/550 - так как такого исхода в списке не было).
    Так что надо взять или придумать априорные вероятности моделей, и воспользоваться формулой Байеса.
    Ответ написан
    Комментировать
  • Как реализовать создание ортогонального массива?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Насколько я понимаю, подобные массивы описываются здесь: habrahabr.ru/post/187882 Правда, там рассматривается частный случай - когда для каждой пары столбцов требуются все комбинации, а не только присутствующие в другом массиве. Но это не делает задачу легче.
    А ортогональность (в смысле линейной алгебры) тут вообще ни при чём.
    Ответ написан
    1 комментарий