Комбинаторные алгоритмы предназначены для выполнения вычис-
лений на различного рода объектах, возникающих в прикладных ком-
бинаторных задачах и при исследовании дискретных математических
структур. Необходимость разработки эффективных, быстрых комби-
наторных алгоритмов уже давно не вызывает сомнений. На практике
нужны не алгоритмы, а хорошие алгоритмы в широком смыс-
ле. Одним из основных критериев качества алгоритма является время,
необходимое для его выполнения.
Разработке и анализу вычислительной сложности комбинаторных
алгоритмов над классическими комбинаторными объектами посвящено
настоящее учебное пособие. Наряду с теоретическими знаниями даётся
описание таких важнейших алгоритмов, приводится их строгое обосно-
вание и детально изучается асимптотическая сложность рассматривае-
мых алгоритмов. Мы познакомим читателя с широким кругом понятий
и сведений из дискретной математики, необходимых практикующему
программисту. Пополним запас примеров нетривиальных алгоритмов
над объектами дискретной математики существенно обо-
гатить навыки самостоятельного конструирования алгоритмов и сфор-
мировать мышление, позволяющее использовать методы дискретного
анализа при разработке эффективных алгоритмов для решения прак-
тических задач и оценке их сложности.
Для понимания материала учебного пособия требуется знание ос-
новных понятий и фактов из дискретной математики и математической
логики. Читатель должен обладать минимальным опытом программи-
рования, каждый изучаемый алгоритм снабжен понятным псевдокодом,
позволяющим реализовать рассматриваемый алгоритм на доступном
языке программирования. При изучении отдельных тем используются
основы математического анализа и теории вероятностей.
ответ все этапы технологии решения задачи на компьютере на примере конкретной задачи.
1. Постановка задачи. Дано N кубиков, на которых написаны разные буквы. Сколько различных N -буквенных слов можно составить из этих кубиков (слова не обязательно должны иметь смысл)?
Искомую целочисленную величину обозначим буквой F. Тогда постановка задачи выглядит так:
Дано: N.
Найти: F.
2. Математическая формализация. Получим расчетную формулу. Сначала рассмотрим несколько конкретных примеров. Имеются два кубика с буквами «И» и «К». Ясно, что из них можно составить два слова:
ИК КИ.
Добавим к ним третью букву, «С». Теперь число разных слов будет в три раза больше предыдущего, т. е. равно 6:
ИКС КИС ИСК КСИ СКИ СИК.
Если добавить четвертую букву, например «А», то число слов возрастет в четыре раза и станет равным 24:
Объяснение:
// Внимание! Если программа не работает, обновите версию!
begin
var n:=ReadInteger('Количество строк/столбцов в матрице:');
Writeln('*** Исходная матрица [',n,',',n,'] ***');
var a:=MatrRandom(n,n,-99,99);
a.Println(4); Writeln(4*a.ColCount*'-');
var j:=0;
var nr:=ArrFill(n,False);
foreach var c in a.Cols do begin
var s:=c.Where(x->x>0);
if s.Count>0 then begin
var min:=s.Min;
var k:=c.Where(x->x>min).Count;
nr[j]:=k>3; j+=1
end
end;
Writeln('*** Результирующая матрица ***');
for var i:=0 to n-1 do
if nr[i] then a.SetCol(i,a.Col(i).Select(x->(x>0?x div 2:x)).ToArray);
a.Println(4)
end.
Пример
Количество строк/столбцов в матрице: 10
*** Исходная матрица [10,10] ***
-12 16 82 17 61 -19 -54 30 -27 77
72 -88 64 -50 85 16 3 -90 72 69
-26 22 27 -72 -83 23 -39 -56 -6 87
2 -56 -4 -43 -15 -31 75 85 -96 -7
42 -17 67 55 32 74 28 -92 -81 -97
-44 80 -50 81 -8 66 89 55 0 -61
-79 -97 -64 -15 -25 28 15 7 64 17
41 17 -93 -20 -72 91 54 71 -5 -57
95 -47 -74 -8 32 22 94 15 64 19
-20 -79 -15 65 -28 39 -52 -18 -20 -96
*** Результирующая матрица ***
-12 16 82 17 61 -19 -54 15 -27 38
36 -88 64 -50 85 8 1 -90 72 34
-26 22 27 -72 -83 11 -39 -56 -6 43
1 -56 -4 -43 -15 -31 37 42 -96 -7
21 -17 67 55 32 37 14 -92 -81 -97
-44 80 -50 81 -8 33 44 27 0 -61
-79 -97 -64 -15 -25 14 7 3 64 8
20 17 -93 -20 -72 45 27 35 -5 -57
47 -47 -74 -8 32 11 47 7 64 9
-20 -79 -15 65 -28 19 -52 -18 -20 -96