Лабораторная работа №2
Цель работы:
-
Изучить функции создания списков;
-
Изучить организацию консольного интерфейса к спискам;
-
Повторить методы сортировки;
Теоретические сведения:
Используйте материалы лекций за первый семестр изучения языка С++ и любую дополнительную литературу.
Лабораторное задание:
Решите следующие задачи:
Задача №1: Общество защиты тунцов (ОЗТ) имеет базу данных с записями результатов самого последнего голосования законодателей по законопроектам об охране тунцов. База состоит из двух списков имён законодателей, в которых названы goodguys и badguys. Соответственно все законодатели после проведения голосования заносятся в соответствующий их выбору список, независимо от того где были раньше, если в голосовании не участвовал - отношение не изменяется.
Программа управляется командами:
-
F - законодатель голосовал правильно;
-
U - законодатель голосовал неправильно;
-
? - определить статус законодателя;
-
N - ввести имя нового законодателя;
-
E - конец ввода списка законодателей.
Примечание: Начинается программа с запроса имени и выполняется до тех пор, пока не нажата E. Выбор F или U завершает работы с текущим законодателем.
Задача №2: Рассмотрим многочлен вида p(x)=c1*x^e1+c2*x^e2+.......+cn*x^en, где e1>e2>.....>en>=0.
-
Такой многочлен можно представить в виде связного списка, где каждая ячейка имеет 3 поля: ci,ei,next. Для описанного представления многочленов напишите программу их дифференцирования.
Примечание: реализуйте дифференцирование как метод класса.
Задача №3: Разработайте реализацию очереди с двусторонним доступом ( извлекать и добавлять элементы можно с обеих сторон ).
Примечание: Реализуйте простую очередь и дополните её операциями вставки в начало и извлечения с конца.
Задача №4 Напишите программу для слияния двух отсортированных списков.
Примечание: Операции вставки в список изначально сортирует список.
Задача №5*: Задача о ранце: имеется целевое значение t и конечное множество положительных целых весов w1,w2,...,wn. Необходимо определить, можно ли из множества весов выбрать такой их набор, чтобы их сумма точно равнялась величине t.
Примечание: Попробуйте реализовать с помощью рекурсии и с помощью стека.