Сборник задач по курсу «Алгоритмы и структуры данных»

Московский государственный технический университет
имени Н.Э. Баумана
И.П. Иванов, А.Ю. Голубков,
С.Ю. Скоробогатов
СБОРНИК ЗАДА
Ч ПО КУРСУ
«АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»
Методические указания
Москва
Издательство МГТУ им. Н.Э. Баумана
2013

УДК 512
ББК 22.12
И20
Рецензент П.Г. Ключар¨
ев
И20
Иванов И. П.
Сборник задач по курсу «Алгоритмы и структуры данных» :
метод. указания / И.П. Иванов, А. Ю. Голубков, С. Ю. Скоробогатов. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2013. — 32, [4] с. :
ил.
ISBN 978-5-7038-3681-1
Приведены задачи по курсу «Алгоритмы и структуры данных»,
посвященные основным алгоритмам сортировки и поиска, а также
базовым структурам данныx, таким, как стеки, очереди, очереди с
приоритетом, связанные списки, списки с пропусками, хеш-таблицы,
бинарные деревья поиска, префиксные и суффиксные деревья.
Для студентов, обучающихся по направлению подготовки бакалавров «Прикладная математика и информатика».
Рекомендовано методической комиссией факультета «Информатика и системы управления» МГТУ им. Н.Э. Баумана.
УДК 512
ББК 22.12
ISBN 978-5-7038-3681-1
c
⃝МГТУ им. Н.Э. Баумана, 2013

ВВЕДЕНИЕ
Курс «Алгоритмы и структуры данных» закладывает фундамент, на котором в МГТУ им. Н.Э. Баумана строится программистская часть профессиональной подготовки бакалавров по
направлению «Прикладная математика и информатика».
В этом курсе студенты осваивают свой первый язык программирования и изучают основные алгоритмы и структуры данных, которые пригодятся им как в течение обучения в МГТУ
им. Н.Э. Баумана, так и в дальнейшей профессиональной деятельности.
Особенностью данного курса является его практическая направленность, т. е. основной упор делается не на получение академических знаний по проектированию и анализу алгоритмов, а на
изучение современных наработок в этой области и, что самое важное, на обязательную реализацию на языке C каждого алгоритма и
каждой структуры данных в ходе выполнения домашних заданий.
Сборник содержит 55 задач, в которых рассмотрены все алгоритмы и структуры данных, изучаемые в курсе «Алгоритмы и
структуры данных».
Курс разбит на три модуля. Домашнее задание по модулю
«Программирование на языке C» состоит из 18 задач, приведенных в разделе 1 данного сборника. Раздел 2 состоит из 21 задачи,
которые нужно решить в модуле «Сортировка, поиск и синтаксический анализ». Раздел 3 содержит 16 задач домашнего задания по
модулю «Динамические множества».

1. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ C
1.1. Сумма чисел, кратных 3 или 5
Выписав натуральные числа от 1 до 10, кратные 3 или 5, получим числа 3, 5, 6 и 9. Их сумма равна 23.
Составьте программу multiples.c, вычисляющую сумму натуральных чисел от 1 до 1000, кратных 3 или 5.
1.2. Сумма четных чисел Фибоначчи
Числа Фибоначчи — это последовательность натуральных чисел {ai}, в которой

a1 = a2 = 1,
ai = ai−2 + ai−1,
∀i > 2.
Составьте программу fibonacci.c, вычисляющую сумму четных
чисел Фибоначчи, не превышающих 4 000 000.
1.3. Наибольший палиндром
Число-палиндром читается одинаково и слева направо, и справа
налево. Наибольший палиндром, полученный путем умножения
двух двузначных чисел, равен 9009 = 91 × 99.
Составьте программу palindrome.c, вычисляющую наибольший палиндром, полученный путем умножения двух трехзначных
чисел.
4