Часть 1. Задачи на структуры данных
Замечание. При реализации алгоритмов использовать динамические структуры данных – списки, деревья, таблицы.
1. Составить программу поиска в ширину в графе. Составить программу поиска в глубину в графе. Граф представлен матрицей смежности.
Прикладная задача.
В. Липский «Комбинаторика для программистов».
2. Составить программу перехода от представления графа матрицей смежности к представлению графа списками инцидентности.
Прикладная задача.
В. Липский «Комбинаторика для программистов».
Задача коммивояжера.
3. Составить программу работы с многочленами. Хранить коэффициенты – в динамических списках. Если аi коэффициент равен 0, его можно не хранить. Например, для P(x) = 50x40–3x8+x можно хранить только три значения.
Функциональность может быть следующей:
1) вычисление значения в точке х;
2) вычисление коэффициентов производной;
3) вычисление значения производной;
4) сложение, вычитание многочленов;
5) построение графиков;
6) проверка равенства многочленов.
4. Составить программу поиска кратчайших путей от данной вершины ко всем остальным в орграфе. Граф представлен матрицей смежности (матрицей весов дуг).
Прикладная задача.
В. Липский «Комбинаторика для программистов».
5. Составить программу построения лабиринтов.
Ч. Уэзерелл «Этюды для программистов».
6. Составить программу работы с таблицами со случайным перемешиванием (хеш-таблицами) в варианте с открытым перемешиванием.
Прикладная задача.
Лебедев В.Н. «Введение в системы программирования».
П. Холл «Вычислительные структуры. Введение в нечисленное программирование».
7. Составить программу работы с таблицами со случайным перемешиванием (хеш-таблицами) в варианте с таблицами переполнения.
Прикладная задача.
Лебедев В.Н. «Введение в системы программирования».
П. Холл «Вычислительные структуры. Введение в нечисленное программирование».
8. Составить программу работы с линейным однонаправленным упорядоченным списком (поиск, запись, удаление, замена, объединение).
Прикладная задача.
Лебедев В.Н. «Введение в системы программирования».
Дж. Фостер «Обработка списков».
9. Составить программу работы с линейным двунаправленным упорядоченным списком (поиск, запись, удаление, замена, объединение).
Прикладная задача.
Лебедев В.Н. «Введение в системы программирования».
Дж. Фостер «Обработка списков».
10. Составить программу работы с кольцевым списком (поиск, запись, удаление, замена, объединение).
Прикладная задача.
Лебедев В.Н. «Введение в системы программирования».
Дж. Фостер «Обработка списков».
11. Составить программу для реализации древовидной структуры (генеалогическое дерево).
П. Холл «Вычислительные структуры. Введение в нечисленное программирование».
12. С помощью шаблона класса «стек», разработанного самостоятельно, написать калькулятор с операциями сложения, вычитания, деления, умножения, возведения в степень.
13. Составить программу сложения, вычитания и умножения разреженных прямоугольных матриц. Разреженной называется матрица большой размерности, большинство элементов которой нулевые. Хранятся только ненулевые элементы в виде списка.
14. Прикладная задача – составить программу на тему «Календарь знаменательных дат».
15. Моделирование системы массового обслуживания.
Прикладная задача – моделирование системы техосмотра транспорта на основе очередей с приоритетами.
16. Моделирование системы массового обслуживания.
Прикладная задача – моделирование системы профосмотра в поликлинике на основе очередей с приоритетами.
17. Моделирование системы массового обслуживания.
Прикладная задача – моделирование работы банка.
Пусть в банке n кассиров. Посетитель заходит в банк в некоторое время t1, желая осуществить некоторую финансовую операцию. Эта операция может потребовать для своего выполнения некоторого времени t2. Если кассир свободен, то он немедленно начинает обслуживание посетителя, и тот покинет банк сразу же после завершения операции, то есть во время t1 + t2. Общее время, проведенное посетителем в банке, равно продолжительности выполнения финансовой операции t2. Может случиться так, что все кассиры окажутся заняты обслуживанием посетителей, пришедших в банк ранее. В этом случае к окошку каждого кассира образуется очередь. Посетитель становится в конец самой короткой очереди и ждет завершения обслуживания посетителей, стоящих впереди него. После этого он может приступить к выполнению своих дел. Посетитель покидает банк через t2 единиц времени после достижения им окна кассира. В этом случае время, проведенное им в банке, есть t2 плюс время, проведенное в очереди.
Необходимо узнать, каково среднее время, проводимое посетителем в банке.
18. Составить программу – экомодель «Волчий остров».
Ван-Тассел.
19. Составить программу – экомодель «Мыши и пшеница».
Гудман, Хидетниеми.
20. Составить программу для раскладывания пасьянсов.
Колода – дек, стопки – стек.
Ч. Уэзерелл. «Этюды для программистов».
21. Составить программу для игры в карты, например, в дурака.
Колода – дек, стопки – стек.
22. Составить программу «Карточные гадания».
Колода – дек, стопки – стек.
Игры. Энциклопедический сборник. Сост. Черноземцев В.А. Чел., 1995.
23. Составить программу «Угадай слово» («Балда»).
24. Составить программу игры в кроссворды. Еще лучше – составление кроссвордов.
25. Реализация ортогонального списка.
Реализовать мультисписок (не менее трех полей указателей, не менее 3-х полей данных – целые числа и строки символов).
Прикладная задача:
26. Составить программу «Мешанина» (тест на внимание):
а) анаграммы;
б) воспроизвести на экране расположение ряда геометрических фигур.
27. Составить игровую программу «Угадай-ка». На поле 4*4 (5*5 или более) в произвольном порядке выстраиваются простые геометрические фигуры (4-12 видов). Затем расклад закрывается, и игроку предлагается по памяти восстановить расположение фигур, за что начисляются очки.
28. Составить программу – игрушку:
а) «Меткий охотник»;
б) «Куры»;
в) «Война на море»;
г) «Звездная война».
29. Прикладная задача – составить тестирующую программу:
а) по психологии;
б) по этике;
в) по культуре общения;
В городе расположены n автобусных остановок, обозначенных числами из N={1,2,....,n}. Имеется R автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении:
М1={I11,I12,...,I1m1},
М2={I21,I22,...,I2m2},
.....
Mr={Ir1,Ir2,...,Irmr},
где Ijk натуральное.
Написать программу, которая по заданным номерам остановок I и J определяет наиболее быстрый путь перемещения пассажира из остановки I в остановку J с использованием имеющихся маршрутов автобусов при условии, что время движения между соседними остановками у всех маршрутов одинаково и в 3 раза меньше времени изменения маршрута. Кроме того, автобусы могут двигаться в обоих направлениях.
Задача.
Матрица размера N*M определяет некоторый лабиринт. B матрице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.
Необходимо определить, можно ли
а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.
б) то же, но человека можно выводить через любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.
Задача.
Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть подчиненные и начальники, причем справедливы правила: подчиненные моего подчиненного – мои подчиненные, начальники моего начальника – мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника только один непосредственный начальник.
Для того чтобы получить лицензию на предпринимательскую деятельность, необходимо получить подпись первого чиновника – начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать «визы», т.е. подписи некоторых своих непосредственных подчиненных и взятку – известное количество долларов. Для каждого чиновника известен непустой список возможных наборов «виз» и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов виз и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
Ограничения: N<100. Количество наборов для каждого чиновника не превосходит 15.