Читать онлайн «Методы программирования и прикладные алгоритмы: Учебное пособие»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет аэрокосмического приборостроения Е. А. Крук, А. А. Овчинников МЕТОДЫ ПРОГРАММИРОВАНИЯ И ПРИКЛАДНЫЕ АЛГОРИТМЫ Учебное пособие Санкт-Петербург 2007 УДК 519. 68 ББК 22. 18 К84 Рецензенты: кафедра распределенных вычислений и компьютерных сетей Санкт-Петербургского государственного политехнического университета; профессор кафедры автоматизированных систем обработки информации и управления Санкт-Петербургского государственного электротехнического университета «ЛЭТИ», заслуженный работник высшей школы РФ, доктор технических наук С. А. Яковлев Утверждено редакционно-издательским советом университета в качестве учебного пособия Крук Е. А. , Овчинников А. А. K84 Методы программирования и прикладные алгоритмы: Учебное пособие/ Е. А. Крук, А. А. Овчинников; ГУАП. – СПб. , 2007. – 166 с. :ил. ISBN 5-8088-0237-7 Учебное пособие представляет собой курс лекций, многие годы чи- тающийся студентам, обучающимся по направлениям «Информацион- ная безопасность», «Информационные системы», «Информатика и вы- числительная техника» в Санкт-Петербургском государственном уни- верситете аэрокосмического приборостроения и в Санкт-Петербургском государственном политехническом университете. Предназначено для студентов специальности 090104, а также мо- жет быть использовано для самостоятельной работы при выполнении заданий по НИР. УДК 519. 68 ББК 22. 18 ISBN 5-8088-0237-7 c ГУАП, 2007 ° c Е. А. Крук, ° А. А. Овчинников, 2007  СОДЕРЖАНИЕ Предиcловие 4 1. Введение в разработку и анализ алгоритмов 6 1. 1. Вычисление веса двоичного вектора . . . . . . . . . 6 1. 2. Коды, сохраняющие разность . . . . . . . . . . . . . 12 2. Методы построения алгоритмов 18 2. 1. Этапы построения алгоритмов . . . . . . . . . . . . . 18 2. 2. Методы частных целей, подъема вверх и отрабаты- вания назад . . . . . . . . . . . . . . . . . . . . . . . . 24 2. 3. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . 43 2. 4. Методы декомпозиции и композиции . . . . . . . . . 51 2. 5.