Иванов, А.Ю. Голубков, С.Ю. Скоробогатов СБОРНИК ЗАДАЧ ПО КУРСУ «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ» Методические указания Москва Издательство МГТУ им. <...> ISBN 978-5-7038-3681-1 Приведены задачи по курсу «Алгоритмы и структуры данных», посвященные основным алгоритмам сортировки и поиска, а также базовым структурам данныx, таким, как стеки, очереди, очереди с приоритетом, связанные списки, списки с пропусками, хеш-таблицы, бинарные деревья поиска, префиксные и суффиксные деревья. <...> Раздел 2 состоит из 21 задачи, которые нужно решить в модуле «Сортировка, поиск и синтаксический анализ». <...> Раздел 3 содержит 16 задач домашнего задания по модулю «Динамические множества». <...> Сумма четных чисел Фибоначчи Числа Фибоначчи — это последовательность натуральных чисел {ai}, в которой a1 =a2 =1, ai =ai−2+ai−1, ∀i> 2. <...> Составьте программу fibonacci.c, вычисляющую сумму четных чисел Фибоначчи, не превышающих 4 000 000. <...> Пифагорова тройка Пифагорова тройка — это три натуральных числа x<y <z, удовлетворяющих соотношению x2+y2 =z2. <...> Составьте программу piphagor.c, вычисляющую пифагорову тройку, в которой x+y+z =1000. <...> Программа должна выводить в стандартный поток вывода элементы множества A∩B, отсортированные в порядке возрастания. <...> Повторяющийся элемент массива Дан целочисленный массив, размер которого не превышает 20. <...> Составьте программу repelem.c, определяющую наиболее повторяющийся элемент массива. <...> Программа должна выводить в стандартный поток вывода число повторений наиболее повторяющегося элемента. <...> Перестановка элементов массива Даны два целочисленных массива размером восемь элементов. <...> Программа должна считывать из стандартного потока ввода элементы обоих массивов, а затем выводить в стандартный поток вывода слово «yes», если массивы совпадают с точностью до перестановки элементов, и «no» — в противном случае. <...> Максимальная сумма подряд идущих элементов массива Дан целочисленный массив, размер которого не превышает 20, и число k, которое меньше или равно длине массива. <...>
Сборник_задач_по_курсу_«Алгоритмы_и_структуры_данных».pdf
УДК 512
ББК 22.12
И20
Рецензент П.Г. Ключар¨
И20
ев
Иванов И.П.
Сборник задач по курсу «Алгоритмы и структуры данных» :
метод. указания / И.П. Иванов, А.Ю. Голубков, С.Ю. Скоробогатов.
—М. : Изд-во МГТУ им. Н. Э. Баумана, 2013. — 32, [4] с. :
ил.
ISBN 978-5-7038-3681-1
Приведены задачи по курсу «Алгоритмы и структуры данных»,
посвященные основным алгоритмам сортировки и поиска, а также
базовым структурам данныx, таким, как стеки, очереди, очереди с
приоритетом, связанные списки, списки с пропусками, хеш-таблицы,
бинарные деревья поиска, префиксные и суффиксные деревья.
Для студентов, обучающихся по направлению подготовки бакалавров
«Прикладная математика и информатика».
Рекомендовано методической комиссией факультета «Информатика
и системы управления» МГТУ им. Н.Э. Баумана.
УДК 512
ББК 22.12
ISBN 978-5-7038-3681-1
МГТУ им. Н.Э. Баумана, 2013
c
Стр.2
ОГЛАВЛЕНИЕ
1. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ C........................ 4
1.1. Сумма чисел, кратных 3 или 5............................. 4
1.2. Сумма четных чисел Фибоначчи........................... 4
1.3. Наибольший палиндром................................... 4
1.4. Пифагорова тройка........................................ 5
1.5. Пересечение множеств .................................... 5
1.6. Повторяющийся элемент массива .......................... 5
1.7. Перестановка элементов массива .......................... 6
1.8. Максимальная сумма подряд идущих элементов массива . . . 6
1.9. Седловая точка в матрице ................................. 6
1.10. Обращение массива ...................................... 7
1.11. Максимальный элемент .................................. 7
1.12. Поиск делением пополам ................................ 8
1.13. Транспонирование матрицы . ............................. 9
1.14. Cтроки Фибоначчи....................................... 9
1.15. Конкатенация строк ...................................... 10
1.16. Подсчет слов в строке.................................... 11
1.17. Периодическая строка.................................... 11
1.18. Рисование рамки......................................... 11
2. СОРТИРОВКА, ПОИСК И СИНТАКСИЧЕСКИЙ АНАЛИЗ .... 12
2.1. Наибольший простой делитель ............................ 12
2.2. Делители треугольного числа.............................. 12
2.3. Длина кратчайшей суперстроки ........................... 12
2.4. Сортировка вставками..................................... 13
2.5. СортировкаШелла . . ...................................... 13
2.6. Сортировка пузырьком .................................... 14
2.7. Сортировка подсчетом сравнений. . . . . . . ................... 14
32
Стр.32
2.8. Пирамидальная сортировка................................ 15
2.9. Сортировка слиянием и вставками......................... 16
2.10. Быстрая сортировка и сортировка прямым выбором....... 16
2.11. Сортировка букв в строке ................................ 16
2.12. Поразрядная сортировка дат.............................. 17
2.13. Поразрядная сортировка целых чисел .................... 18
2.14. Периодические префиксы ................................ 18
2.15. Поиск всех вхождений подстроки (алгоритм Кнута —
Морриса — Пратта) .............................................. 19
2.16. Слово, составленное из префиксов другого слова ......... 19
2.17. Поиск всех вхождений подстроки (алгоритм Бойера —
Мура) ........................................................... 20
2.18. Расширенная эвристика стоп-символа .................... 20
2.19. Порождение языка по грамматике ........................ 21
2.20. LL(1)-грамматика ........................................ 21
2.21. Арифметическое выражение . ............................ 22
3. ДИНАМИЧЕСКИЕ МНОЖЕСТВА............................. 23
3.1. Нерекурсивная быстрая сортировка........................ 23
3.2. Кольцевой буфер .......................................... 23
3.3. Очередь с операцией Maximum............................ 23
3.4. Слияние последовательностей . . ........................... 24
3.5. Моделирование работы вычислительного кластера ......... 24
3.6. Сортировка списка вставками ............................. 25
3.7. Переворачивание списка . . . ............................... 26
3.8. Сортировка списка пузырьком............................. 26
3.9. Ранги элементов в списке с пропусками ................... 27
3.10. Ранги вершин бинарного дерева поиска................... 27
3.11. Построение сбалансированного бинарного дерева поиска . 28
3.12. Разреженный массив ..................................... 28
3.13. Лексический анализ (АВЛ-дерево). ....................... 29
3.14. Число различных подстрок . .............................. 30
3.15. Наибольшая общая подстрока ............................ 30
3.16. Лексический анализ (хеш-таблица) ....................... 31
Стр.33