Размещено на http://www.allbest.ru/

24

Билет 1

Жадный алгоритм и его реализация. На примере алгоритма Хаффмана.

Жадный алгоритм -- алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Алгоритм Хаффмана -- адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее время используется во многих программах сжатия данных.

Этот метод кодирования состоит из двух основных этапов:

1.Построение оптимального кодового дерева.

2.Построение отображения код-символ на основе построенного дерева.

Коды Хаффмана

Коды Хаффмана (Huffman codes) -- широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема. Мы рассматриваем данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки. Предположим, что имеется файл данных, состоящий из 100 000 символов, который требуется сжать. Символы в этом файле встречаются с частотой, представленной в табл. 16.1. Таким образом, всего файл содержит шесть различных символов, а, например, символ a встречается в нем 45 000 раз.

Таблица 1.Задача о кодировании последовательности символов.

	a	B	c	d	e	F
Частота	45	13	12	16	9	5
Код.слово фикс. длины	000	001	010	011	100	101
Код.слово перем. длины	0	101	100	111	1101	1100

для представления шести символов понадобится 3 бита: a = 000, b = 001,..., f = 101. При использовании такого метода для кодирования всего файла понадобится 300 000 битов. Для представления файла с помощью этого кода потребуется (45 · 1 + 13 · 3 + 12 · 3 + 16 · 3+9 · 4+5 · 4) · 1000 = 224 000 битов.Благодаря этому дополнительно экономится 25% объема.

В приведенном ниже псевдокоде предполагается, что C -- множество, состоящее из n символов, и что каждый из символов c ? C -- объект с определенной частотой f (c). В алгоритме строится дерево T, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из |C| листьев, после чего последовательно выполняется |C| ? 1 операций “слияния”, в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами Q, ключами в которой являются частоты f. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:

HUFFMAN(C)

1 n < |C|

2 Q < C

3 for i < 1 to n ? 1

4 do Выделить память для узла z

5 left[z] < x < EXTRACT_MIN(Q)

6 right[z] < y < EXTRACT_MIN(Q)

7 f[z] < f[x] + f[y]

8 INSERT(Q, z)

9 return EXTRACT_MIN(Q) ? Возврат корня дерева

сложность алгоритма Хаффмана (в общем случае) считается равной O(N*log(N))

Билет 2

Полный перебор

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

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

Рассмотрим примеры задач, которые можно решить этим методом.

Обход в глубину.

Рассмотрим стандартную задачу про n ферзей

Расположить n ферзей на шахматной доске nxn, так чтобы они не атаковали друг друга.

Поиск в глубину

Наиболее очевидное решение состоит в том, чтобы ставить ферзей рекурсивно на доску, пробуя все возможные способы размещения ферзя. Легко использовать тот факт, что каждый ферзь должен стоять на отдельной вертикали: на каждом шаге рекурсии, мы ищем только номер вертикали, куда можно поставить ферзя.

1 search(col)

2 если заполнены все вертикали

3 print solution and exit

4 для каждой позиции на диагонали col

5 если позиция board(row, col) не атакована

6 поставить ферзя на (row, col)

7 search(col+1)

8 убрать ферзя с (row, col)

Вызов search (0) начинает процедуру поиска. Он работает быстро, т.к. на очередном шаге расстановки ферзя, число неатакованных полей резко уменьшается.

Это - пример поиска в глубину. Алгоритм проходит все дерево решений сверху вниз до основания настолько быстро, насколько это возможно: поставив один раз k ферзей на доску, следующие ферзи будут располагаться, начиная с этой расстановки.

Поиск в глубину проверяет каждый узел в дереве поиска на выполнение некоторого свойства. Дерево поиска напоминает этот рисунок:



Алгоритм проходит дерево, идя вниз настолько, насколько это возможно, а затем возвращается назад (отходя на предыдущую вершину), делая своего рода схему дерева, поскольку некоторые узлы посещены. Дерево поиска может быть проиллюстрировано следующим образом:

Задача Ферзи (стандартная)

Требуется расставить N (6<=N<=13) ферзей на доске NxN таким образом, чтобы они не били друг друга. В выходной файл (output.txt) требуется вывести количество возможных расстановок.

В первой строке входного файла (input.txt) записано число N.

input.txt	output.txt
6	4
7	40
8	92
9	352
10	724
11	2680
12	14200
13	73712

Билет 3

Задача об одномерной оптимальной упаковке, или задача о рюкзаке, формулируется так: пусть имеется рюкзак заданной грузоподъемности; также имеется некоторое множество предметов различного веса и различной стоимости (ценности); требуется упаковать рюкзак так, чтобы он закрывался и сумма стоимостей упакованных предметов была бы максимальной.

Математическая постановка задачи

Пусть задано конечное множество предметов , для каждого известна ценность (стоимость) c_i и определен обьем a_i. Имеется рюкзак объема B. Требуется упаковать рюкзак так, чтобы общая ценность упакованных предметов была наибольшей и их общий обьем не превосходил B. Традиционно полагают, что - целые неотрицательные числа.

Введем двоичные переменные :

§ x_i = 1, если предмет выбран для упаковки,

§ x_i = 0 в противном случае.

Тогда задача о рюкзаке сводится к следующей задаче линейного целочисленного программирования с булевыми переменными: найти такие значения переменных , при которых достигается максимум суммы

(1.1)

и выполняется ограничение

 (1.2)

Суть метода динамического программирования

В основу метода динамического программирования положен принцип оптимальности, сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения».

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

Рассматривается следующая общая задача. Имеется некоторая физическая система, в которой происходит какой-то процесс, состоящий из n шагов. Эффективность процесса характеризуется некоторым показателем W, который называют выигрышем. Пусть общий выигрыш W за все n шагов процесса складывается из выигрышей на отдельных шагах

(2.1)

где w_i -- выигрыш на i-м шаге. Если W обладает таким свойством, то его называют аддитивным критерием.

Процесс, о котором идет речь, представляет собой управляемый процесс, т.е. имеется возможность выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге. Это решение называется шаговым управлением. Совокупность всех шаговых управлений представляет собой управление процессом в целом. Обозначим его буквой U, а шаговые управления -- буквами . Тогда

Шаговые управления в общем случае не числа, а, как правило, векторы, функции и т.п.

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S. Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s₀ -- начальное и s_w -- конечное.

Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений , и каждому шаговому управлению , соответствует -- состояние, в которое процесс попадает из s_i в результате использования шагового управления u. Пусть процесс находится в начальном состоянии s₀. Выбор переводит процесс в состояние s₁ = у(s₀,u₁), выбор -- в состояние s₂ = у(s₁,u₂) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

(2.2)

(2.3)

конечны и U_s для различных s не пересекаются.

В общем виде задача динамического программирования формулируется следующим образом: найти такую траекторию процесса, при которой выигрыш (2.1) будет максимальным.

То управление, при котором достигается максимальный выигрыш, называется оптимальным управлением. Оно состоит из совокупности шаговых управлений

(2.4)

Тот максимальный выигрыш, который достигается при этом управлении обозначим W_max:

W_max = max_U{W(u)}. (2.5)

Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем.

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса -- присваивание переменной x_i значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака -- вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i-м шагом понимается величина

(2.6)

при этом s₀ является начальным состоянием, которому соответствует величина b -- исходная грузоподъемность рюкзака.

Управление на i-м шаге означает присваивание двоичной переменной x_i значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления u_i, устанавливающего x_i = 1, определяется условием

(2.7)

Далее везде вместо переменных будем использовать соответствующие управления . Тогда формулы (2.6), (2.7) примут следующий вид:

(2.8)

(2.9)

Шаговый выигрыш можно определить как . Поэтому

(2.10)

Требуется найти оптимальное управление , при котором величина выигрыша (2.10) обращается в максимум.

Уравнение Беллмана для задачи о рюкзаке

Пусть к началу -шага остаточная грузоподъемность равна s. Оптимальное управление определяется следующим образом:

§ если , то последний предмет можно положить в рюкзак, что соответствует оптимальному управлению

;

§ иначе .

Ясно, что оптимальный условный выигрыш на -ом шаге составит

Рассмотрим -й шаг. Предположим, что остаточная грузоподъемность равна . Если на этом шаге выбрать управление , то на начало последнего шага останется вес . Тогда выигрыш двух последних шагах будет равен

Нужно найти такое , при котором этот выигрыш максимален

где максимум берется по всем допустимым управлениям -- управлениям, для которых верно ограничение (2.9). Напомним, что может принимать лишь два значения: 0 или 1.

Рассуждая далее аналогичным образом, приходим к рекуррентному уравнению

(2.11)

которое позволяет для любого -го шага вычислить условный оптимальный выигрыш и найти соответствующее ему условное оптимальное управление . Здесь -- значение, при котором достигается максимум в (2.11).

К достоинствам метода динамического программирования следует отнести

§ сравнительную простоту расчетов, удобство их алгоритмизации (целевая функция и функции ограничений могут быть линейными и нелинейными, целочисленными и нецелочисленными, заданными аналитически и таблично).

§ независимость от вида исходных данных.

Недостатки метода

§ большой объём промежуточной информации;

§ большой объём вычислительной работы.

При увеличении числа ограничений типа (2.9) множество состояний процесса может быть слишком велико для проведения практических расчетов даже с использованием компьютера. Именно этим обстоятельством в первую очередь определяется сфера применения динамического программирования.

Метод динамического программирования относят к рекуррентным методам, поскольку он позволяет построить оптимальное решение с помощью рекуррентного уравнения Беллмана (2.11). Таким образом можно говорить о рекурсивном характере метода. Метод динамического программирования допускает две реализации: табличную и рекурсивную. Традиционно этот метод излагается с использованием таблиц. Поэтому его также называют табличной техникой или программированием на основе массивов.

Реализации метода динамического программирования для задачи о рюкзаке

Табличная реализация и её сложность

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

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

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

Поэтому процедура решения задачи динамического программирования обычно разворачивается от конца к началу. Вначале планируется последний n-ый шаг. При этом делаются разные предположения о том, чем закончился предпоследний (n ? 1)-шаг. Для каждого из этих предположений следует найти условное оптимальное управление на n-ый шаг. «Условное» потому, что оно выбирается исходя из условия, что предпоследний шаг закончился так-то и так-то. Далее, «пятясь назад» оптимизируется управление на (n ? 1)-м шаге и т.д., пока не будет достигнут первый шаг.

Предположим, что все условные оптимальные управления и условные оптимальные выигрыши найдены для всего «хвоста» процесса. Далее выполняется построение не условно оптимального, а просто оптимального управления и вычисление не условно оптимального, а просто оптимального выигрыша W_max.

Таким образом, при построении оптимального решения многошаговый процесс «проходится» дважды:

§ сначала -- от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши на оставшийся «хвост» процесса;

§ после -- от начала к концу, когда выписываются уже готовые рекомендации и находится оптимальное управление.

Из этих двух этапов оптимизации наиболее важным и трудоемким является первый этап. Второй практически не требует дополнительных вычислений.

Запишем принципиальную структуру обоих этапов оптимизации с помощью общих формул. Введем некоторые обозначения. Пусть

§ W_i(s) -- условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i-го шага и до конца. Считаем, что процесс в начале i-го шага находится в состоянии s;

§ U_i(s) -- условное оптимальное управление на i-м шаге, которое, совместно с оптимальным управлением на всех последующих шагах, обращает выигрыш «хвоста» в максимум.

Определим условный оптимальный выигрыш W_i(s) и условное оптимальное управление U_i(s) для всех шагов .

Рассмотрим i-й шаг процесса. Предположим, что в результате (i ? 1) предыдущих шагов процесс оказался в состоянии s и на i-м шаге выбрано шаговое управление u_i. Получаемый на этом шаге выигрыш w_i зависит как от состояния s, так и от примененного управления u_i, т.е.

(3.1)

Кроме того, имеется некоторый выигрыш на всех оставшихся шагах. Согласно принципу оптимальности, будем считать, что он максимален. Чтобы найти этот выигрыш, необходимо знать следующее состояние -- состояние перед (i + 1)-м шагом. Это новое состояние определяется так:

(3.2)

Найдем теперь выигрыш, который получается на всех шагах, начиная с i-го, если на i-м шаге применено любое (не обязательно оптимальное) управление u_i, а на всех последующих -- оптимальное управление. Этот выигрыш обозначим через . Тогда можно записать

алгоритм хаффман беллман компьютер

Или, учитывая (3.2),

(3.3)

Далее, следуя принципу оптимального управления, надо выбрать такое управление u_i = U_i, при котором величина (3.3) максимальна и достигает значения

(3.4)

Управление, в котором достигается максимум в (4.4), и есть условное оптимальное управление U_i(s) на i-м шаге, а сама величина W_i(s) -- условный оптимальный выигрыш на всех шагах, начиная с i-го и до конца. В уравнении (3.4) функции w_i(s,u_i) и $у(s,u_i) известны. Неизвестными остаются функции W_i(s) и W_{i + 1}(s).

Формула (3.4) называется основным рекуррентным уравнением динамического программирования (или уравнением Беллмана). Она позволяет определить функцию W_i(s) через следующую за ней по порядку функцию W_{i + 1}(s).

Условный оптимальный выигрыш на последнем шаге W_n(s) можно найти так:

(3.5)

Управление U_n(s), при котором достигается максимум выигрыша (3.5), является условным оптимальным управлением на последнем шаге.

С помощью формулы (3.5) и основного рекуррентного уравнения (3.4) можно, одно за другим, построить всю цепочку условных оптимальных управлений и условных оптимальных выигрышей.

Оптимальное управление можно создать следующим образом.

§ Выполним подстановку начального состояния s₀ в формулу для условного оптимального выигрыша W₁(s) и условного оптимального управления U₁(s₀). В результате получим

§ Далее определим следующее состояние процесса, в которое оно попадает под управлением

§

§ Исходя из состояния , находим , и т.д. Таким образом, получаем цепочку

(3.6)

На этом процесс оптимизации заканчивается выигрышем W_max = W₁(s₀). Из описания процедуры оптимизации следует, что для метода динамического программирования целочисленность исходных данных решаемой задачи не является обязательной. Главное, чтобы число шагов, состояний и управлений было конечно.

Рассмотрим итерационную реализацию метода динамического программирования на конкретном числовом примере. Результаты расчетов будем вносить в табл. 3.1

Пример 3.1.

Имеется 3 предмета и рюкзак, способный выдержать 50 кг. Первый предмет весит 10 кг и стоит 60 у. е. Второй предмет весит 20 кг и имеет стоимость 100 у. е. Третий предмет весит 30 кг и стоит 120 у. е. Требуется оптимально заполнить рюкзак предметами, не превысив его веса.

Таблица 3.1

s	i=3	i=2	i=1
0	0 0	0 0	0 0
10	0 0	0 0	1 60
20	0 0	1 100	0 100
30	1 120	0 120	1 160
40	1 120	0 120	1 180
50	1 120	1 220	0 220

Поскольку грузоподъёмность рюкзака и веса предметов кратны 10, в табл. 3.1. всего лишь шесть строк, соответствующих возможным значениям остаточной грузоподъёмности рюкзака. Здесь i -- номер предмета для упаковки. Согласно алгоритму начинаем заполнять таблицу с последнего предмета (т. е. идем в обратном порядке). Последний предмет весит 30 кг. Следовательно, он будет помещен в рюкзак, если . Тогда U₃(s) = 1 и W₃(s) = c₃ = 120.

Далее, чтобы вычислить значения U_i(s) и W_i(s) для , требуется строить для каждой пары вспомогательные таблицы.

Табл. 3.2 демонстрирует вычисление величин U₂(s), W₂(s) для s = 30 по формуле (2.11). Соответственно ищутся величины U₁(s), W₁(s) для по той же формуле.

Таблица 3.2

30 ? a2u	c2u	W3(30 ? a2u)	c2u + W3(30 ? a2u)
30	0	120	120
10	100	0	100

Итак, метод динамического программирования дает следующее оптимальное управление процессом укладки рюкзака

с оптимальным выигрышем у. е.

Оценим сложность решения задачи о рюкзаке методом динамического программирования. Наиболее трудоёмким является первый этап процедуры поиска оптимального решения. Этот этап сводится к построению основной таблицы (табл. 3.1). Чтобы найти значения для первого шага, требуется 2B ресурсов. Для вычисления любой пары элементов U_i(s),W_i(s), где , основной таблицы приходится формировать вспомогательную таблицу типа 4.2. Построение основной таблицы для общего случая задачи о рюкзаке будет зависеть от множества состояний рюкзака, а также от количества управлений и количества предметов. То есть асимптотическая функция сложности принимает вид:

(3.7)

где -- мощность множества управлений, в нашей задаче оно состоит из 0 и 1, а -- мощность множества состояний (2.2) (наихудший случай для в задаче о рюкзаке это число, равное размерности рюкзака, то есть B). Значит, для формирования вспомогательных таблиц t(n) = 8B(n ? 1). Таким образом, приходится вычислять 2B + 8B(n ? 1) элементов, что составляет O(Bn).

Рекурсивная реализация и её сложность

Рекурсивность метода динамического программирования позволяет реализовать его в виде рекурсивной процедуры. Эта рекурсивная процедура определяется рекуррентным соотношением, которое следует из основного функционального уравнения Беллмана (2.11):

(3.8)

Билет 4

Динамическое программирование.

Эта тема будет самой объемной, поскольку около половины задач решаются с помощью динамического программирования.

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

· количество параметров;

· значения параметров.

В качестве параметров будем рассматривать целые неотрицательные числа.

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

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

Пример #1.

Найти самую тяжелую монету из 10 монет. Для формализации задачи определим функцию "Самая тяжелая монета", аргументами которой являются количество монет (10) и масса каждой из монет. Пока нас не интересует конкретный вид этой функции, для нас важнейшим фактором является факт, что она дает правильное решение. Для данной задачи можно рассмотреть 9 подзадач, которые имеют меньшее значение аргументов:

· "Самая тяжелая монета" из 1 монеты,

· "Самая тяжелая монета" из 2 первых монет,

· "Самая тяжелая монета" из 3 первых монет,

· ...

· "Самая тяжелая монета" из 9 первых монет.

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

Сведение задачи к подзадачам

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

При этом для решения исходной задачи может потребоваться решение одной или нескольких подзадач.

Билет 5

Реализация стека.Реализация очереди

Стек (stack) - это динамическая структура данных с последовательным доступом. Доступ к элементам стека осуществляется следующим образом, элементы из стека можно доставать только в порядке, обратном порядку добавления их в стек.

Примерами стеков могут служить:

1. обыкновенная детская пирамидка: большое колечко, которое было надето раньше, нельзя снять, не сняв маленькое, которое было надето позже;

2. железнодорожный тупик: вагон нельзя выгнать из тупика, не выгнав предварительно вагон, который был загнан позже;

3. труба с одним запаянным концом, куда помещают разноцветные бочонки.

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

Работа стека организована по принципу LIFO (Last In First Out) - последним пришел, первым ушел.

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

Приведем пример реализации неограниченного стека целых чисел основанного на односвязном списке.

Содержание файла stack.h:

#ifndef STACK_H

#define STACK_H

#include <iostream.h>

#include <malloc.h>

/*

** Класс "Стек целых чисел" на основе односвязного списка

*/

typedef int stackdata; // элемент стека

// изменяя это объявление вы легко

// можете получить стек других типов

// например, структур, классов, символов.

// элемент односвязного списка

struct listitem

{

stackdata data; // данные

listitem* next; // указатель на следующий элемент списка

};

// Класс исключений для CStack

class EStack

{

private:

char* msg; // сообщение об ошибке

public:

EStack(const char* errmsg) { msg = strdup(errmsg); }

~EStack() { free(msg); }

const char* getmsg() { return msg; }

};

class CStack

{

private:

listitem* head; // голова односвязного списка

public:

CStack(); // конструктор

CStack(const CStack&); // конструктор копирования

~CStack() { clear(); } // деструктор

bool empty() const { return head==0; } // стек пуст?

// здесь применена так называеся технология inline

// везде где будет стоять вызов метода empty()

// компилятор вместо вызова процедуры "вшьет" данный код

// в место вызова. Это увеличивает производительность,

// т.к. на вызов любой подпрограммы требуется дополнительное время.

// Однако не следует злоупотреблять inline подстановкой - ее нужно

// использовать только для маленьких функций/методов.

CStack& clear(); // очистить стек

CStack& push(const stackdata& data); // добавить элемент в стек

stackdata pop(); // извлечь элемент из стека

const stackdata& see() const; // посмотреть элемент в вершине стека

CStack& operator = (const CStack&); // оператор присваивания

friend ostream& operator << (ostream&, const CStack&);

// Оператор вывода стека в поток

};

// конструктор стека

CStack::CStack()

{

head = 0;

}

CStack::CStack(const CStack& stack)

{

head = 0;

*this = stack;

}

CStack& CStack::clear()

{

while(head)

{

listitem* temp = head->next;

delete head;

head = temp;

}

return *this;

}

CStack& CStack::push(const stackdata& data)

// Этот метод добавляет указанный элемент в вершину стека и

// в качестве результата возвращает ссылку на экземпляр стека.

// В принципе можно было бы просто обойтись void. Но

// тогда был бы невозможен следующий вызов:

// stack2 = stack1.push(10)

// или такой:

// stack1.push(1).push(2).push(3)

//

// Также обратите внимание на то, как объявлен параметр data:

// const stackdata& data, т.е. по ссылке

// В нашем случае (стек целых чисел) это лишнее, т.к. никакого

// выйгрыша от этого нет. Но если вы захотите сделать стек из более

// рерурсоемких структур, то имеенно так и нужно делать, т.к.

// иначе при вызове метода будет создаваться копия объекта (структуры,

// класса, и т.п.)

{

listitem* item = new listitem;

item->data = data;

item->next = head;

head = item;

// Здесь мы выделили память под новый элемент односвязного

// списка, скопировали данные, и сделали новый элемент списка

// его головой - вершиной стека.

return *this;

}

stackdata CStack::pop()

// Извлекает элемент из вершины стека

// Если стек пуст, то генерирует исключительную ситуацию

{

if(empty()) throw (EStack("Stack is empty"));

listitem* old = head;

head = head->next; // сдвигаем вершину стека

stackdata data = old->data;

delete old; // удаляем старую вершину

return data;

}

const stackdata& CStack::see() const

{

if(empty()) throw (EStack("Stack is empty"));

return head->data;

}

CStack& CStack::operator = (const CStack& stack)

{

if (this == &stack) return *this;

// Игнорируем попытку присвоить стек самому себе

clear();

if(!stack.empty())

{

head = new listitem;

listitem* cur = head;

listitem* src = stack.head;

while(src)

{

cur->data = src->data;

if(src->next)

{

cur->next = new listitem;

cur = cur->next;

} else

cur->next = 0;

src = src->next;

}

}

return *this;

}

ostream& operator << (ostream& s, const CStack& stack)

{

listitem* item = stack.head;

while(item)

{

s << item->data << endl;

item = item->next;

}

return s;

}

#endif

Очередь (queue) - это динамическая структура данных с последовательным доступом. Доступ к элементам очереди осуществляется следующим образом: элементы из нее можно доставать только в том порядке, в котором они были добавлены в нее.

Работа очереди организована по принципу FIFO (First In First Out) - первым пришел, первым ушел.

Пример реализации очереди целых чисел на C++

Как и стек, реализуем очередь на основе односвязного списка:

/*

** Класс "Очередь"

** Слава Антонов (с) 2004

** http://slava.users.otts.ru

*/

#ifndef QUEUE_H

#define QUEUE_H

#include <iostream.h>

#include <malloc.h>

// Тип элемента очереди

typedef int datatype;

// Элемент односвязного списка

struct listitem

{

datatype data;

listitem* next;

};

class equeue

{

private:

char* msg; // сообщение об ошибке

public:

equeue(const char* errmsg) { msg = strdup(errmsg); }

~equeue() { free(msg); }

const char* getmsg() { return msg; }

};

#define EQUEUE_EMPTY "Queue is empty"

class cqueue

{

private:

listitem* head; // голова односвязного списка

listitem* tail; // хвост односвязного списка

unsigned cnt; // длина очереди (кол-во элементов в ней)

public:

cqueue();

// конструктор по-умолчанию

cqueue(const cqueue&);

// конструктор копирования

// этот конструктор вызывается в следующей ситуации:

// cqueue Q2 = Q1

~cqueue() { clear(); }

// деструктор

cqueue& clear();

// удалить все элементы очереди

unsigned getCnt() const { return cnt; }

cqueue& del();

// удалить один элемент из начала очереди

bool empty() const { return head == NULL; }

// признак пустой очереди

cqueue& push(const datatype&);

// добавить элемент в конец очереди

datatype pop();

// извлеч элемент из начала очереди

const datatype& get() const;

// посмотреть элемент в начале очереди

cqueue& set(const datatype&);

// заменить элемент в начале очереди

bool operator == (const cqueue&) const;

// оператор сравнения

bool operator != (const cqueue& q) const

{ return !(*this == q); }

cqueue& operator = (const cqueue&);

// оператор присваивания

friend ostream& operator << (ostream&, const cqueue&);

// оператор вывода

};

cqueue::cqueue()

{

head = tail = NULL;

}

cqueue::cqueue(const cqueue& q)

{

head = tail = NULL;

*this = q;

}

cqueue& cqueue::clear()

{

while(!empty()) del();

return *this;

}

cqueue& cqueue::del()

{

// если стек пуст - генерируем исключение

if(empty()) throw(equeue(EQUEUE_EMPTY));

listitem* tmp = head->next; // запоминаем указатель на

// следующий элемент очереди

delete head; // удаляем элемент...

// ...и переводим указатель на следующий элемент

if(!tmp)

head = tail = NULL;

else

head = tmp;

cnt--;

return *this;

}

cqueue& cqueue::push(const datatype& data)

{

listitem* item = new listitem;

item->data = data;

item->next = NULL;

if(!head)

{

head = item;

tail = head;

} else

{

tail->next = item;

tail = item;

}

cnt++;

return *this;

}

datatype cqueue::pop()

{

if(empty()) throw(equeue(EQUEUE_EMPTY));

datatype data = head->data;

del();

return data;

}

const datatype& cqueue::get() const

{

if(empty()) throw(equeue(EQUEUE_EMPTY));

return head->data;

}

cqueue& cqueue::set(const datatype& data)

{

if(empty()) throw(equeue(EQUEUE_EMPTY));

head->data = data;

return *this;

}

bool cqueue::operator == (const cqueue& q) const

{

if(this == &q) return true;

if(getCnt() != q.getCnt()) return false;

listitem* h1 = head;

listitem* h2 = q.head;

while(h1)

{

if(h1->data != h2->data) return false;

h1 = h1->next;

h2 = h2->next;

}

return false;

}

cqueue& cqueue::operator = (const cqueue& q)

{

if(*this == q) return *this;

clear();

listitem* item = q.head;

while(item)

{

push(item->data);

item = item->next;

}

return *this;

}

ostream& operator << (ostream& s, const cqueue& q)

{

listitem* item = q.head;

while(item)

{

s << item->data << endl;

item = item->next;

}

return s;

}

Билет 6

Поиск в глубину.Рекурсивная и нерекурсивная реализация

Поиск в глубину (англ. Depth-first search, DFS) -- один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин

Рекурсивная реализация

void DFS(int v, int from)

{

if (mark[v] != 0) // Если мы здесь уже были, то тут больше делать нечего

{

return;

}

mark[v] = 1; // Помечаем, что мы здесь были

prior[v] = from; // Запоминаем, откуда пришли

if (v == finish) // Проверяем, конец ли

{

cout << "Hooray! The path was found!\n";

return;

}

for (int i = 0; i < (int)edges[v].size(); ++i) // Для каждого ребра

{

DFS(edges[v][i], v); // Запускаемся из соседа

}

}

Алгоритм просматривает каждое ребро один раз, и выполняет для каждой вершины константное число действий. Обозначая число вершин как V, а ребер -- как E, получаем, что время работы -- O(V+E).

Глубина рекурсии, в которой мы находимся, не превышает общего числа вызовов функции DFS -- числа вершин. То есть, объем памяти, необходимый для работы алгоритма, равен O(V).

Нерекурсивная реализация

void DFS()

{

stack<int> s;

s.push(start);

while (!s.empty())

{

int v = s.top();

s.pop();

for (int i = 0; i < edges[v].size(); ++i)

{

if (mark[edges[v][i]] == 0)

{

s.push(edges[v][i]);

mark[edges[v][i]] = 1;

}

}

}

}

Билет 7

Методы хранения графа.Реализация поиска в ширину

Способы представления графа в памяти компьютера

При разработке эффективных алгоритмов выбор структуры данных имеет принципиальное значение. Рассмотрим три основных структуры.

Список ребер

Наиболее очевидный способ - хранить список пар вершин, соединенных ребрами. Для его хранения необходим двумерный массив размерности Mx2 (M - количество ребер). Строка массива описывает ребро. Для взвешенных графов такой способ создает необходимость дополнительно завести массив весов ребер.

Пример для орграфа на рис.4:

Матрица смежности.

Матрица смежности A представляет собой двумерный массив размерности NxN (N - количество вершин). A[i,j]=1, если существует ребро (i,j) (дуга <i,j>), A[i,j]=0 - в противном случае. Для неориентированных графов матрица смежности симметрична относительно главной диагонали.

Для взвешенных графов значение элемента A[i,j] обычно используют для хранения веса соответствующего ребра. Для невзвешенных мультиграфов A[i,j] может содержать количество ребер, соединяющих вершины i и j.

Пример. Матрица смежности для графа на рис.7

Список связей

Третий способ - хранение списка всех ребер инцидентных каждой из вершин. Для этого необходим массив, содержащий N элементов, где N - количество вершин в графе. i-ый элемент этого массива содержит список всех ребер, смежных с i-ой вершиной (ребро представлено номером второй инцидентной ему вершины).

Пример для графа на рис. 7.

Вершина	Смежные вершины
1	2,3,4,5
2	1
3	1,4
4	1,3
5	1

Итого:

Пусть N и M - количество элементов в множествах V и E соответственно, d_max - максимальная степень вершины, тогда сравнительную характеристику вышеназванных структур удобно представить в виде таблицы:

	Список ребер	Матрица смежности	Список связей
Память	2*M	N2	2*M
Проверка смежности двух вершин	M	1	dmax
Получение списка всех вершин, смежных данной	M	N	dmax
Добавление ребра	1	1	1
Удаление ребра	M	2	2*dmax

Поиск в ширину

Поиск в ширину (обход по уровням) - один из алгоритмов обхода графа. . Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень - произвольно выбранный узел, затем - все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня.

Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q?V, то есть q - некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т. к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

Основными объектами - тремя структурами данных, задействованными в программе, будут:

· матрица смежности графа GM;

· очередь queue;

· массив посещенных вершин visited.

Две первые структуры имеют целочисленный тип данных, последняя - логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных «очередь» работает по принципу «первый пришел - первый вышел». Рассмотрим разбитый на этапы процесс обхода графа:

1. массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена;

2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);

3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;

4. если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу; иначе посещается вершина, стоящая в начале очереди, помечается как посещенная, и все ее потомки заносятся в конец очереди;

5. пункт 4 выполняется пока это возможно.

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

Для реализации алгоритма на ЯП потребуется: умение программно задавать граф, а также иметь представление о такой структуре данных, как очередь.

Код программы на C++:

Билет 8

Размещения с повторениями -- комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать. p=nm .

Реализация

Напечатать все последовательности длины k из чисел 1..n.

Решение. Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b, если для некоторого s их начальные отрезки длины s равны, а (s+1)-ый член последовательности a меньше). Первой будет последовательность <1, 1, ..., 1><n, n, ..., n>, последней - последовательность . Будем хранить последнюю напечатанную последовательность в массиве x[1]...x[k].

...x[1]...x[k] положить равными 1

...напечатать x

...last[1]...last[k] положить равными n

{напечатаны все до x включительно}

while x <> last do begin

| ...x := следующая за x последовательность

| ...напечатать x

end;

Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1)-ый - больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдется, так как по предположению x<>last), увеличить его на 1, а идущие за ним члены положить равными 1.

p:=k;

while not (x[p] < n) do begin

| p := p-1;

end;

{x[p] < n, x[p+1] =...= x[k] = n}

x[p] := x[p] + 1;

for i := p+1 to k do begin

| x[i]:=1;

end;

Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению единицы в n-ичной системе счисления.

Билет 9

Между k-элементными подмножествами N-элементного множества и возрастающими последовательностями длины k с элементами из множества целых чисел от 1 до N (сочетаниями) существует взаимно однозначное соответствие. Так, например, подмножеству [2, 6, 1, 3] соответствует последовательность чисел 1, 2, 3, 6. Таким образом, решая задачи подсчета и генерации всех сочетаний, мы решаем аналогичные задачи для k-элементных подмножеств. Лексикографический порядок на множестве последовательностей определяется так же, как и для перестановок.

Пример,

1234

1235

1236

1245

1246

1256

1345

1346

1356

1456

2345

2346

2356

2456

3456

Попробуем подсчитать количество сочетаний для данных значений N и k. Воспользуемся для подсчета числа сочетаний формулой (n>1, 0<k<n).

Подсчет всех значений Ck

N .

Const MaxN=100;

Var SmallSc:Array[0..MaxN,0..MaxN] Of LongInt;

{*Нулевой столбец и нулевая строка необходимы,

это позволяет обойтись без анализа на выход

за пределы массива.*}

Procedure FillSmallSc;

Var i,j :Integer;

Begin

FillChar (SmallSc,SizeOf(SmallSc),0);

For i:=0 To N Do SmallSc [i,0]:=1;

For i:=1 To N Do

For j:=1 To k Do

If SmallSc[i-1,j]*1. 0+SmallSc[i-1,j-1]>

MaxLonglnt Then SmallSc[i,j]:=MaxLongInt

Else SmallSc[i,j]:=SmallSc[i-1,j]+SmallSc

[i-1,j-1]; {*Умножение на 1.0 переводит

целое число в вещественное, поэтому

переполнения при сложении не происходит.

Стандартный прием, обязательный при "игре"

на границах диапазона целых чисел.*}

End;

Билет 10

В комбинаторике перестаномвка -- это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит в соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.

Научимся вычислять число перестановок для заданного значения N. Известно, что число перестановок равно факториалу числа N. Рекурсивное определение: N!=N*(N-1)!

1 1

2 2

3 6

4 24

5 120

6 720

7 5040 (Последнее число типа Integer)

8 40320

9 362880

10 3628800

11 39916800

12 479001600 (Последнее число типа Longlnt)

13 6227020800

...

30 265252859812191058636308480000000

Функция имеет ограниченную область применения.

Function Fac (k:LongInt): LongInt;

Var r,i: LongLnt;

Begin

r:=1;

For i:=l To к Do r:=r*i;

Faс:=r;

End;

Функция работоспособна при N, меньшем или равном 12.

Билет 11

Реализация универсальной сортировки на языке C.

// Универсальная сортировка, алгоритм - сортировка выбором

void __cdecl sort(

void * pBase, // Указатель на начало массива

unsigned dwCountElement, // Кол-во элементов в массиве

unsigned dwSizeElement, // Размер элемента

int(__cdecl * fn)(const void *, const void *) // Callback - функция сравнения 2-х элементов

)

{

unsigned i = 0, j = 0;

char * pStart = (char *)pBase, *pMin = (char *)pBase;

for (i = 0; i < dwCountElement - 1; ++i)

{

pMin = pStart + i * dwSizeElement;

for (j = i; j < dwCountElement; ++j)

{

if (fn(pStart + j * dwSizeElement, pMin) < 0)

{

pMin = pStart + j * dwSizeElement;

}

}

swap(pStart + i * dwSizeElement, pMin, dwSizeElement);

}

}

void swap(char * a, char * b, unsigned dwSizeElement)

{

char tmp = 0;

unsigned i = 0;

for (i = 0; i < dwSizeElement; ++i)

{

tmp = b[i];

b[i] = a[i];

a[i] = tmp;

}

Размещено на Allbest.ru

...