Комбинаторные алгоритмы предназначены для выполнения вычис-
лений на различного рода объектах, возникающих в прикладных ком-
бинаторных задачах и при исследовании дискретных математических
структур. Необходимость разработки эффективных, быстрых комби-
наторных алгоритмов уже давно не вызывает сомнений. На практике
нужны не алгоритмы, а хорошие алгоритмы в широком смыс-
ле. Одним из основных критериев качества алгоритма является время,
необходимое для его выполнения.
Разработке и анализу вычислительной сложности комбинаторных
алгоритмов над классическими комбинаторными объектами посвящено
настоящее учебное пособие. Наряду с теоретическими знаниями даётся
описание таких важнейших алгоритмов, приводится их строгое обосно-
вание и детально изучается асимптотическая сложность рассматривае-
мых алгоритмов. Мы познакомим читателя с широким кругом понятий
и сведений из дискретной математики, необходимых практикующему
программисту. Пополним запас примеров нетривиальных алгоритмов
над объектами дискретной математики существенно обо-
гатить навыки самостоятельного конструирования алгоритмов и сфор-
мировать мышление, позволяющее использовать методы дискретного
анализа при разработке эффективных алгоритмов для решения прак-
тических задач и оценке их сложности.
Для понимания материала учебного пособия требуется знание ос-
новных понятий и фактов из дискретной математики и математической
логики. Читатель должен обладать минимальным опытом программи-
рования, каждый изучаемый алгоритм снабжен понятным псевдокодом,
позволяющим реализовать рассматриваемый алгоритм на доступном
языке программирования. При изучении отдельных тем используются
основы математического анализа и теории вероятностей.
Var
S:longint;
i:integer;
A:byte;
Begin
S:=0;
Repeat
Read(A);
if (A mod 2 <> 0)and(A mod 7 = 0) then S:=S+A;
Until A = 0;
WriteLn('S = ',S);
End.
Теперь объяснение каждой строки:
Var
S:longint;
i:integer;
A:byte; // В эту переменную будет вводится число с клавиатуры. Тип Byte может принимать значения от 0 до 255. Поэтому его как раз хватит.
Begin
S:=0; // Тут будет храниться сумма, поэтому переменную следует сперва обнулить.
Repeat // далее начинается цикл
Read(A); // эта команда каждый раз считывает с клавы число, и записывает его в переменную A.
if (A mod 2 <> 0)and(A mod 7 = 0) then S:=S+A; //тут проверяется 2 условия, и если они выполняются - к переменной S прибавляется значение переменной А
1 условие: число нечётно, то есть остаток от деления его на 2 не равен нулю (A mod 2 <>0)
2 условие: Число кратно 7, то есть делится без остатка на 7, то есть остаток от деления равен нулю (A mod 7 = 0)
Until A = 0; // Цикл повторяется до тех пор, пока введённое с клавы число не будет равно нулю (A = 0)
WriteLn('S = ',S); // Тут выводится искомая сумма
End.