Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 577346)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.

Программирование в алгоритмах (304,00 руб.)

0   0
Первый авторОкулов С. М.
ИздательствоМ.: Лаборатория знаний
Страниц386
ID443308
АннотацияИскусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются необходимым дополнением курса.
Кому рекомендованоДля школьников, студентов и специалистов, серьезно изучающих программирование, а также для преподавателей учебных заведений.
ISBN978-5-93208-521-9
УДК519.85(075)
ББК22.18я7
Окулов, С.М. Программирование в алгоритмах : [учебник] / С.М. Окулов .— 7-е изд., электрон. — Москва : Лаборатория знаний, 2021 .— 386 с. — (Развитие интеллекта школьников) .— Дериватив. изд. на основе печ. аналога (М.: БИНОМ. Лаборатория знаний, 2013); Электрон. текстовые дан. (1 файл pdf : 386 с.); Систем. требования: Adobe Reader XI; экран 10" .— ISBN 978-5-93208-521-9 .— URL: https://rucont.ru/efd/443308 (дата обращения: 26.01.2022)

Предпросмотр (выдержки из произведения)

Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. <...> Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. <...> Арифметика многоразрядных целых чисел Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. <...> Арифметика многоразрядных целых чисел 9 Const MaxDig=1000;{*Максимальное количество цифр – четырехзначных. <...> MaxDig] Of Integer;{*Вычислите максимальное количество десятичных цифр в нашем числе. <...> В конечном итоге процедура должна иметь следующий вид: Procedure ReadLong(Var A:TLong); Var ch:Char;i:Integer; Begin FillChar(A,SizeOf(A),0); Repeat Read(ch); Until ch In [’0’. <...> ’9’] Do Begin For i:=A[0] DownTo 1 Do Begin{*“Протаскивание” старшей цифры в числе из А[i] в младшую цифру числа из А[i+1]. <...> Арифметика многоразрядных целых чисел A[1]:=A[1]+Ord(ch)-Ord(’0’); {*Добавляем младшую цифру к числу из А[1]. <...> Процедура вывода имеет вид: Procedure WriteLong(Const A:TLong); Var ls,s:String; i:Integer; Begin Str(Osn Div 10,ls); Write(A[A[0]]);{*Выводим старшие цифры числа. <...> Тогда программа ввода двух чисел и вывода результата их сложения будет иметь следующий вид: 11 12 Var A,B,C:TLong; Begin Assign(Input,’Input.txt’); Reset(Input); ReadLong(A);ReadLong(B); Close(Input); SumLongTwo(A,B,C); Assign(Output,’Output.txt’); Rewrite(Output); WriteLong(C); Close(Output); End. <...> Function More(A,B:TLong):Boolean; Var i:Integer; Begin If A[0]<B[0] Then More:=False Else If A[0]>B[0] Then More:=True Else Begin i:=A[0]; While (i>0) And (A[i]=B[i]) Do Dec(i); If i <...>
Программирование_в_алгоритмах.pdf
Стр.2
Стр.3
Стр.4
Стр.5
Стр.6
Программирование_в_алгоритмах.pdf
С. М. Окулов ПРОГРАММИРОВАНИЕ В АЛГОРИТМАХ 7-е издание, электронное Москва Лаборатория знаний 2021
Стр.2
УДК 519.85(023) ББК 22.18 О-52 С е р и я о с н о в а н а в 2008 г. Окулов С. М. О-52 Программирование в алгоритмах / С. М. Окулов.— 7-е изд., электрон.—М. : Лаборатория знаний, 2021.— 386 с.—(Развитие интеллекта школьников).—Систем. требования: Adobe Reader XI ; экран 10".—Загл. с титул. экрана.—Текст : электронный. ISBN 978-5-93208-521-9 Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются необходимым дополнением курса. Для старших школьников, студентов и специалистов, серьезно изучающих программирование, а также для преподавателей учебных заведений. УДК 519.85(023) ББК 22.18 Деривативное издание на основе печатного аналога: Программирование в алгоритмах / С. М. Окулов.—4-е изд.— М. : БИНОМ. Лаборатория знаний, 2013.—383 с. : ил.— (Развитие интеллекта школьников). ISBN 978-5-9963-0848-4. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации ISBN 978-5-93208-521-9 © Лаборатория знаний, 2015
Стр.3
Содержание Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Арифметика многоразрядных целых чисел . . . . . . 8 1.1. Основные арифметические операции . . . . . . . . . . . . . . 8 1.2. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2. Комбинаторные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . 27 2.1. Классические задачи комбинаторики . . . . . . . . . . . . . . 27 2.2. Генерация комбинаторных объектов . . . . . . . . . . . . . . 34 2.2.1. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2. Размещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.3. Сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2.4. Разбиение числа на слагаемые . . . . . . . . . . . . . . 58 2.2.5. Последовательности из нулей и единиц длины N без двух единиц подряд . . . . . . . . . . . 64 2.2.6. Подмножества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.2.7. Скобочные последовательности . . . . . . . . . . . . . 71 2.3. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3. Перебор и методы его сокращения . . . . . . . . . . . . . . . . 87 3.1. Перебор с возвратом (общая схема) . . . . . . . . . . . . . . . . 87 3.2. Примеры задач для разбора общей схемы перебора 89 3.3. Динамическое программирование . . . . . . . . . . . . . . . . . 106 3.4. Примеры задач для разбора идеи метода динамического программирования . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.5. Метод ветвей и границ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.6. Метод «решета» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4. Алгоритмы на графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 4.1. Представление графа в памяти компьютера . . . . . . . . 158 4.2. Поиск в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.2.1. Поиск в глубину . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.2.2. Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Стр.4
4 Содержание 4.3. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 4.3.1. Основные понятия. Стягивающие деревья . . 162 4.3.2. Порождение всех каркасов графа . . . . . . . . . . . 163 4.3.3. Каркасминимального веса. МетодДж.Краскала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 4.3.4. Каркас минимального веса. Метод Р. Прима168 4.4. Связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 4.4.1. Достижимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 4.4.2. Определение связности . . . . . . . . . . . . . . . . . . . . . 172 4.4.3. Двусвязность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 4.5. Циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 4.5.1. Эйлеровы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 4.5.2. Гамильтоновы циклы . . . . . . . . . . . . . . . . . . . . . . 177 4.5.3. Фундаментальное множество циклов . . . . . . . 179 4.6. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 4.6.1. Постановка задачи. Вывод пути . . . . . . . . . . . . 180 4.6.2. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . 182 4.6.3. Пути в бесконтурном графе . . . . . . . . . . . . . . . . . 183 4.6.4. Кратчайшие пути между всеми парами вершин. Алгоритм Флойда . . . . . . . . . . . . . . . . . 186 4.7. Независимые и доминирующие множества . . . . . . . . 188 4.7.1. Независимые множества . . . . . . . . . . . . . . . . . . . 188 4.7.2. Метод генерации всех максимальных независимых множеств графа . . . . . . . . . . . . . . . . . . . 189 4.7.3. Доминирующие множества . . . . . . . . . . . . . . . . 194 4.7.4. Задача о наименьшем покрытии . . . . . . . . . . . . 195 4.7.5. Метод решения задачи о наименьшем разбиении . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 4.8. Раскраски . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 4.8.1. Правильные раскраски . . . . . . . . . . . . . . . . . . . . . 202 4.8.2. Поиск минимальной раскраски вершин графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа . . . . . . . 207 4.9. Потоки в сетях, паросочетания . . . . . . . . . . . . . . . . . . . . 208 4.9.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . 208 4.9.2. Метод построения максимального потока в сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 4.9.3. Наибольшее паросочетание в двудольном графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Стр.5
Содержание 5 4.10. Методы приближенного решения задачи коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 4.10.1. Метод локальной оптимизации . . . . . . . . . . . . 219 4.10.2. Алгоритм Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . 222 4.10.3. Алгоритм Кристофидеса . . . . . . . . . . . . . . . . . . 225 4.11. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 5. Алгоритмы вычислительной геометрии . . . . . . . . . . 249 5.1. Базовые процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5.2. Прямая линия и отрезок прямой . . . . . . . . . . . . . . . . . . 255 5.3. Треугольник . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 5.4. Многоугольник . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 5.5. Выпуклая оболочка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 5.6. Задачи о прямоугольниках . . . . . . . . . . . . . . . . . . . . . . . . 284 5.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 6. Избранные олимпиадные задачи по программированию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 7. Заметки о тестировании программ . . . . . . . . . . . . . . . . 358 7.1. О программировании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 7.2. Практические рекомендации . . . . . . . . . . . . . . . . . . . . . . 360 7.3. Тестирование программы решения задачи (на примере) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 Библиографический указатель . . . . . . . . . . . . . . . . . . . . . . . . 382
Стр.6