Комбинаторные алгоритмы решения школьных задач по информатике

Рис.3.7. Технические характеристики

Для того, чтобы исключить возможное влияние операционной системы на время выполнения вычисления, был проведен численный эксперимент, результаты которого представлены в таблице 1.

Таблица 3. Время вычисления факториала 1000

Порядковый номер вычисления	Время вычисления, сек
1	2,446
2	2,448
3	2,426
4	2,451
5	2,441
6	2,442
7	2,442
8	2,443
Среднее время вычисления	2,442

 

Таким образом, программа вычисляет факториал 1000 в среднем за 2,442 секунды.

Пожалуй, самой сложной  для реализации, является операция деления и нахождение остатка  от деления двух больших чисел. Методы соответствующие данным операциям  были названы delenie (BigInteger, BigInteger) и ostasok_delenie (BigInteger, BigInteger) соответсвенно. В основе лежит принцип деления «столбиком». Пример работы алгоритма приведен на рисунке 3.8.

Рис. 3.8. Операция деления и нахождение остатка от деления

Ход алгоритма следующий: сравниваем делитель с делимым, прибавляя поразрядно по одной цифре к делителю в случае, если получившийся делитель меньше делимого, при этом в частное записываем 0. На рисунке 8 видно этот этап: 2<7985, в частное записываем 0, затем 21<7985, в частное записываем 0, и так далее пока не поменяется знак неравенства 21367>7985. После этого запускается цикл по нахождению следующей цифры частного. На каждом шаге делитель прибавляется на величину равную самому делителю, пока он не станет больше либо равен нашему промежуточному делимому, т.е. 21367. Шаг цикла, на котором выполнится данное условие, и будет искомой цифрой для частного. Затем вычитаем из промежуточного делимого полученное в ходе цикла число и получаем промежуточный остаток. Так как он точно меньше делителя (в связи с предыдущими условиями), добавляем к нему следующую не задействованную цифру делимого и переходим к первому шагу алгоритма. Алгоритм считается выполненным, если получается остаток, меньший делителя и не осталось ни одной незадействованной цифры делимого. В зависимости от задачи, метод возвращает либо частное, либо остаток от деления.

Для удобства пользователей  был введен еще один метод vishislenie(), который предоставляет возможность выполнять вышеперечисленные арифметические операции с двумя или одним большим числом путем простого ввода необходимого для вычисления выражения. Пример работы данного метода приведен на рисунке 3.9.

факториал большой число перемножение

Рис. 3.9. Режим вычисления выражений

3.3. Сложение и вычитание двух больших чисел

Программа сложения и вычитания больших  чисел

program PascalGuru; 

{сложение + вычитание БОЛЬШИХ  чисел в формате STRING} 

Function CompLong(s1,s2:string):integer; {функция CompLong сравнивает две строки как большие числа}

var

a,len1,len2,i:integer;

b:boolean;

begin

a:=0;

b:=true;

len1:=length(s1);

len2:=length(s2);

if len1>len2 then begin a:= 1; b:=false; end;

if len1<len2 then begin a:=-1; b:=false; end;

if b then

for i:=1 to len1 do

begin

if Ord(s1[i])-48>Ord(s2[i])-48 then begin a:= 1; break; end;

if s1[i]<s2[i] then begin a:=-1; break; end;

end;

CompLong:=a;

end; 

{--- функция вычитания ---}

function minus(s1,s2:string):string ;

   var i,len,c,x:integer;

   a,b:array[1..1000] of integer;

   rez:string;

   begin

   c:=0;

   len:=length(s2);

   for i:=1 to len do

   b[len-i+1]:=Ord(s2[i])-48;

   len:=length(s1);  

   for i:=1 to len do

   a[len-i+1]:=Ord(s1[i])-48;

   if Complong(s1,s2)<0 then begin

   Write('-');

   len:=length(s2);

   for i:=1 to len do begin

   x:=a[i];

   a[i]:=b[i];

   b[i]:=x;

   end;

   end;

   for i:=1 to len do

   begin

   c:=c+a[i]-b[i]+10;

   a[i]:= c mod 10;                       {результат будет храниться в массиве a}

       if c < 10 then c:=-1 else c:=0;

       end;

   while (a[len]=0) and (len>1) do len:=len-1;

   rez:='';

   for i:=len downto 1 do

        begin

       str(a[i],s1);

       rez:=rez+s1;

       end;

   minus:=rez;

end;

{--- конец функции вычитания  --- }

{функция сложения}

function plus(s1,s2:string):string ;

   var a,b:array[1..100] of integer;

   len,i,c:integer;

   rez:string;

   begin

   c:=0;

   len:=length(s1);                      {разбиение строк в элементы массивов}

   for i:=1 to len do

   a[len-i+1]:=Ord(s1[i])-48;

   len:=length(s2);

   for i:=1 to len do

   b[len-i+1]:=Ord(s2[i])-48; 

   if length(s1)>length(s2) then len:=length(s1)

   else len:=length(s2);

   for i:=1 to len do

   begin

   c:=c+a[i]+b[i];         {переменная c будет в дальнейшем использоваться для переноса числа в следующий ряд}

   a[i]:=c mod 10;         {результат сложения запишем в массив а}

   c:=c div 10;

   end;

   if c>0 then begin

   len:=len+1;

   a[len]:=c;

   end;

   rez:='';

   for i:=len downto 1 do

       begin

       str(a[i],s1);

       rez:=rez+s1;

       end;

   plus:=rez;

end;

{--- конец функции  сложения --- } 

var c1,c2:string;

    znak:char;

begin

writeln(plus('154527452243563888500','100000020') );

writeln(minus('526','126') );

end.  

 

4. Комбинаторные алгоритмы.  Сочетание

4.1. Генерация сочетания по его номеру

Алгоритм

Идея алгоритма состоит  в том, чтобы каким-нибудь образом  пронумеровать все сочетания  из n по k, то есть поставить в соответствие каждому числу i из диапазона 0≤i<C(n,k) (где C(n,k) – это число сочетаний из n по k) заранее определённое сочетание.

Итак, сначала определим  отношение порядка на множестве  сочетаний из n по k. Для наглядности  будем записывать сочетания в  формате «список из bool». Наше отношение порядка будет лексикографическим.

Имеем два сочетания, a=(a₁, a₂, … , a_n-1, a_n) и b=(b₁, b₂, … , b_n-1, b_n), a_i и b_i (1≤i≤n) принимают значения 0 или 1, причём суммы a₁, a₂, … , a_n и b₁, b₂, … , b_n равны k. Сочетание a предшествует сочетанию b (a<b), если a₁=b₁, a₂=b₂, … a_m-1=b_m-1, a_m<b_m для некоторого m: 1≤m≤n.

Для наглядности расположим, например, все сочетания из 7 по 3 в указанном порядке.

(0, 0, 0, 0, 1, 1, 1) (0, 0, 0, 1, 0, 1, 1) (0, 0, 0, 1, 1, 0, 1) (0, 0, 0, 1, 1, 1, 0) (0, 0, 1, 0, 0, 1, 1) (0, 0, 1, 0, 1, 0, 1) (0, 0, 1, 0, 1, 1, 0) (0, 0, 1, 1, 0, 0, 1) (0, 0, 1, 1, 0, 1, 0) (0, 0, 1, 1, 1, 0, 0) (0, 1, 0, 0, 0, 1, 1) (0, 1, 0, 0, 1, 0, 1) (0, 1, 0, 0, 1, 1, 0) (0, 1, 0, 1, 0, 0, 1) (0, 1, 0, 1, 0, 1, 0) (0, 1, 0, 1, 1, 0, 0) (0, 1, 1, 0, 0, 0, 1) (0, 1, 1, 0, 0, 1, 0) (0, 1, 1, 0, 1, 0, 0) (0, 1, 1, 1, 0, 0, 0) (1, 0, 0, 0, 0, 1, 1) (1, 0, 0, 0, 1, 0, 1) (1, 0, 0, 0, 1, 1, 0) (1, 0, 0, 1, 0, 0, 1) (1, 0, 0, 1, 0, 1, 0) (1, 0, 0, 1, 1, 0, 0) (1, 0, 1, 0, 0, 0, 1) (1, 0, 1, 0, 0, 1, 0) (1, 0, 1, 0, 1, 0, 0) (1, 0, 1, 1, 0, 0, 0) (1, 1, 0, 0, 0, 0, 1) (1, 1, 0, 0, 0, 1, 0) (1, 1, 0, 0, 1, 0, 0) (1, 1, 0, 1, 0, 0, 0) (1, 1, 1, 0, 0, 0, 0)

Если внимательно посмотреть на эти сочетания, то в их порядке  легко проследить рекуррентную зависимость.

Рассмотрим первый элемент сочетаний. Сначала идут все сочетания, в которых он равен 0, потом – все, в которых он равен 1. Причём порядок следования сочетаний в обеих этих подгруппах повторяется – в каждой подгруппе сначала идут сочетания, в которых второй элемент – 0, а потом – в которых он равен 1 и т.д.

Количество сочетаний, в которых первый элемент равен  нулю, равно числу сочетаний из n-1 по k, а количество сочетаний, в  которых первый элемент равен  единице, равно числу сочетаний  из n-1 по k-1 (ответ на вопрос, почему так происходит, описан в примечании ко второму свойству биномиального коэффициента). Итак, если номер сочетания меньше числа сочетаний из n-1 по k, то первый элемент множества не входит в данное сочетание, иначе – входит.

Обобщая вышесказанное, приходим к следующему алгоритму.

Входные данные: CombNumber – номер сочетания, n, k – размер входного множества и размер сочетания, Src – входное множество (последовательность), из которого выбирается сочетание, Dest – выходное множество, в которое в результате работы алгоритма будет записано сочетание.

Выходные данные: сочетание, записанное в Dest.

1. Если k=0 или k=n, то это тривиальный случай. При k=n включаем все оставшиеся элементы из Src в Dest. При k=0 всё уже сделано.
2. Если CombNumber≥C(n,k), то *Dest ← *Src (записываем элемент в выходную последовательность), Dest ← Dest+1 (переходим к следующему элементу выходной последовательности), k ← k-1, CombNumber ← CombNumber-C(n,k).
3. Src ← Src+1, n ← n-1.
4. Перейти к шагу 1.

Оценка временной  сложности

Данный алгоритм в значительной степени использует вычисление биномиального коэффициента, поэтому его эффективность зависит от эффективности вычисления биномиального коэффициента. Максимальное количество итераций равно n (минимальное - k). Кроме того, используется k операций присваивания. Есть также незначительные операции типа инкремента и вычитания целых чисел. Их также не более n.

Предположим, что в  качестве алгоритма вычисления биномиального  коэффициента используется первый описанный  в статье алгоритм (использующий дополнительную память). Его временная сложность равна O(nk), если требуемое значение C(n,k) не вычислялось до момента вызова, и O(1), если оно уже находится в кэше.

Тогда при вычислении C(n,k), исходя из алгоритма, все остальные  требуемые значения биномиального коэффициента также вычисляются. То есть, по сути, биномиальный коэффициент необходимо вычислить всего один раз, во все последующие вызовы значения извлекаются из кэша.

Таким образом, временная  сложность всего алгоритма выбора случайного сочетания составляет O(nk), если кэш не заполнен, и O(n), если он заполнен нужными нам биномиальными коэффициентами.

Забегая вперёд, скажем, что при наличии заполненного кэша описываемый алгоритм более  эффективен, чем алгоритм генерации  сочетания методом случайной  перестановки. То есть, если он вызывается многократно (например, хотя бы 5-10 раз), можно получить выигрыш в производительности (заполнение кэша окупается). Если же необходимо сгенерировать всего одно сочетание, то, конечно, лучше применить алгоритм генерации случайного сочетания методом случайной перестановки.

Реализация

Описание функций

Функций, относящихся  к данному алгоритму, достаточно много, но не следует пугаться –  все они однотипные.

Описание функций, реализующих алгоритм генерации сочетания по его номеру

namespace Combinatorics {   // Функция, генерирующая  сочетание в формате "список  из bool" по его   // порядковому номеру   template<typename Integer, class RandomAccessIterator,     class GetBinomialCoefficientFunc>   void CombinationFromNumberBool(Integer CombNumber, Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class RandomAccessIterator>   void CombinationFromNumberBool(Integer CombNumber, Integer k,     RandomAccessIterator First, RandomAccessIterator Last);     // Функция, генерирующая сочетание в формате "список из bool" по его   // порядковому номеру   // В отличие от  предыдущей функции, на итератор не накладывается   // требование быть  итератором произвольного доступа   template<typename Integer, class OutputIterator,     class GetBinomialCoefficientFunc>   void CombinationFromNumberBool(Integer CombNumber,     Integer n, Integer k,     OutputIterator Dest,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class OutputIterator>   void CombinationFromNumberBool(Integer CombNumber,     Integer n, Integer k,     OutputIterator Dest);     // Функция, генерирующая сочетание в формате "подмножество" по его   // порядковому номеру   template<typename Integer, class RandomAccessIterator,     class OutputIterator, class GetBinomialCoefficientFunc>   void CombinationFromNumber(Integer CombNumber, Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     OutputIterator Dest,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class RandomAccessIterator,     class OutputIterator>   void CombinationFromNumber(Integer CombNumber, Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     OutputIterator Dest);     // Функция, генерирующая сочетание в формате "подмножество" по его   // порядковому номеру   // В отличие от  предыдущей функции, на итератор не накладывается   // требование быть  итератором произвольного доступа   template<typename Integer, class InputIterator, class OutputIterator,     class GetBinomialCoefficientFunc>   void CombinationFromNumber(Integer CombNumber, Integer n, Integer k,     InputIterator Src, OutputIterator Dest,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class InputIterator, class OutputIterator>   void CombinationFromNumber(Integer CombNumber, Integer n, Integer k,     InputIterator Src, OutputIterator Dest);     // Функция, генерирующая  случайное сочетание в формате  "список из bool"   // по его порядковому номеру   template<typename Integer, class RandomAccessIterator,     class GetBinomialCoefficientFunc, class RandomNumberGenerator>   void RandomCombinationFromNumberBool(Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     RandomNumberGenerator& RandomFunc,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class RandomAccessIterator>   void RandomCombinationFromNumberBool(Integer k,     RandomAccessIterator First, RandomAccessIterator Last);     // Функция, генерирующая случайное сочетание в формате "список из bool"   // по его порядковому  номеру   // В отличие от  предыдущей функции, на итератор не накладывается   // требование быть  итератором произвольного доступа   template<typename Integer, class OutputIterator,     class GetBinomialCoefficientFunc, class RandomNumberGenerator>   void RandomCombinationFromNumberBool(Integer n, Integer k,     OutputIterator Dest,     RandomNumberGenerator& RandomFunc,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class OutputIterator>   void RandomCombinationFromNumberBool(Integer n, Integer k,     OutputIterator Dest);     // Функция, генерирующая  случайное сочетание в формате  "подмножество"   // по его порядковому номеру   template<typename Integer, class RandomAccessIterator,     class OutputIterator,     class GetBinomialCoefficientFunc, class RandomNumberGenerator>   void RandomCombinationFromNumber(Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     OutputIterator Dest,     RandomNumberGenerator& RandomFunc,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class RandomAccessIterator,     class OutputIterator>   void RandomCombinationFromNumber(Integer k,     RandomAccessIterator First, RandomAccessIterator Last,     OutputIterator Dest);     // Функция, генерирующая случайное сочетание в формате "подмножество"   // по его порядковому  номеру   // В отличие от  предыдущей функции, на итератор  не накладывается   // требование быть  итератором произвольного доступа   template<typename Integer, class InputIterator,     class OutputIterator, class GetBinomialCoefficientFunc,     class RandomNumberGenerator>   void RandomCombinationFromNumber(Integer n, Integer k,     InputIterator Src, OutputIterator Dest,     RandomNumberGenerator& RandomFunc,     GetBinomialCoefficientFunc& GetBinomialCoefficient);     template<typename Integer, class InputIterator, class OutputIterator>   void RandomCombinationFromNumber(Integer n, Integer k,     InputIterator Src, OutputIterator Dest); } // namespace Combinatorics