Задания для курсовых работ по дисциплине «Структуры и

алгоритмы компьютерной обработки данных»

В каждом из приведенных ниже вариантов курсовой работы требуется:

1) Выбрать и описать способ разработки алгоритма: "прицип разделяй

и властвуй", динамичестое программирование и т.д.

2) Доказать правильность алгоритма.

3) Оценить эффективность/сложность алгоритма.

4) Доказать универсальность алгоритма.

Таким образом, вместе с программой Вы начинаете писать пояснение, в нем Вы отмечаете все мысли, которые приводят Вас к решению поставленной задачи. Пусть самое первое решение, которое Вы придумаете, будет не совсем оптимально, в последствии Вы поместите новый алгоритм как модифицированную версию предыдущего, и покажете, за счет чего происходит выигрыш. Любой алгоритм должен быть обоснован и доказана его правильность любым известным для Вас способом: WP, доказательство от противного или просто логическая цепочка. При анализе рекурсивной программы возникает, как обычно, два вопроса:

а) почему программа заканчивает работу?

б) почему она работает правильно, если заканчивает работу?

Затем Вы пытаетесь оценить сложность алгоритма. Если для Вашего алгоритма это оказывается не так просто, начинаете с оценки сверху. Экспоненциальная сложность алгоритма, как конечного, не приемлема, если Вы не докажете, что это наилучший результат из возможных. Универсальность алгоритма должна заключаться в том, что при небольшой модификации он был бы способен решить более глобальную задачу, чем перед Вами поставлена, т.к. при попытке сдачи почти наверняка будет предложена задача на модификацию, а если модификация потребует от Вас полного переписывания программы, то такой результат будет оценен соответствующе.

Задача на модификацию не предполагает изменения в корне условия, но предполагает, например, что Ваша программа никак не завязана на размер массивов, на количество итераций в цикле и т.п.

Последнее условие придумано искусственно и в большинстве задач возможно могло быть не обязательным, но поставлено специально для увеличения навыков практического программирования у студентов.

1. Дана последовательность, состоящая из 2N натуральных чисел.

Известно, что все числа этой последовательности можно разбить на пары таким образом, что сумма чисел во всех парах будет одинаковой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары 1+99=77+23.Напишите программу, которая по такой последовательности определяет, можно ли эту последовательность разбить на пары таким образом, чтобы произведение чисел во всех парах было одинаковым.

2. На планете Олимпия очень популярна такая головоломка. На столе последовательно лежат N стопок разноцветных карточек. За один ход можно снять верхние карточки одного цвета с произвольного количества размещенных рядом стопок. Написать программу, которая будет вычислять минимальное количество ходов, необходимое для того, чтобы снять все карточки на столе.

3. Треугольник задан на плоскости координатами своих вершин:

(X1,Y1), (X2,Y2), (X3,Y3). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах. Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10-4.

4. С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии "Майбуття" к одной из школ города (к какой - неважно), а также соединить линиями электропередач некоторые школы между собой. Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником "Майбуття", либо с одной из тех школ, которые имеют надежное электроснабжение. Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения; стоимость схемы равняется сумме стоимостей соединений пар школ). Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.

5. Для транспортирования материалов из цеха А в цех В используется конвейер. Материалы упаковываются в одинаковые контейнеры и размещаются на ленте один за одним в порядке изготовления в цехе А. Каждый контейнер имеет степень срочности обработки в цехе В.

Для упорядочивания контейнеров по степени срочности используют накопитель, который находится в конце конвейера перед входом в цех В. Накопитель работает пошагово, на каждом шаге возможны следующие действия: накопитель перемещает первый контейнер из ленты в цех В;

накопитель перемещает первый контейнер из строки в склад (в складе каждый следующий контейнер помещается на предыдущий); накопитель перемещает верхний контейнер из склада в цех В. Написать программу, которая по последовательности контейнеров определит, можно ли упорядочить их по степени срочности пользуясь описанным накопителем.

6. Задана последовательность чисел от 1 до N, каждое из которых встречается ровно один раз. Назовем ее эталонной. Заданы еще несколько наборов последовательностей, которые нужно сравнить с эталонной. Степенью правильности последовательности(СПП) называется максимальное количество чисел, которые идут в ней в том же порядке, что и в эталонной при вычеркивании других. Напишите программу, определяющую степень правильности последовательности.

7.Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2,..., An}. Необходимо составить цепочку максимальной длины по правилу (Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak). При образовании этой цепочки любая пара может быть использована не более одного раза.

8. Задача состоит в написании программы оптимизации лифта. Желаемый этаж каждого из пассажиров задается в начале поездки. Далее лифт должен решить, на каких этажах он будет останавливаться. Число остановок лифта не должно превышать k, при этом этажи нужно выбрать так, чтобы свести к минимуму полное число этажей, которое нужно пройти людям вверх или вниз. Можно считать, что лифт знает, сколько человек выходит на каждом этаже. Стоимость подъема на один пролет равна стоимости спуска. Если однозначного решения не существует, предпочтение отдается минимально возможному этажу.

Лифт не обязан останавливаться на этажах, указанных пассажирами.

9. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Напишите программу, позволяющую ответить на вопрос: «Можно ли перезнакомить их всех между собой?» (Незнакомые люди могут познакомиться только через общего знакомого).

10. Имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров. Напишите программу, позволяющую ответить на вопрос: «Можно ли разложить все открытки по конвертам, так, чтобы в каждом конверте было по одной открытке?».

Замечание. Открытки нельзя складывать, сгибать и т.п., но можно помещать в конверт под углом. Например, открытка с размерами сторон 5:1 помещается в конверты с размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с размерами 4:1, 10:0.5, 4.2:4.2.

11. Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся а) по pебpам б)по веpшинам.

12. Во время своей работы алгоритм сжатия данных методом "сортировки блока" применяет к блокам данных; преобразование, которое определяется следующим образом. Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, т.е. если S=a1a2...aN, где ai-i-ый символ строки S, то