Контрольные вопросы Задачи




Скачать 473.88 Kb.
НазваниеКонтрольные вопросы Задачи
страница3/4
ТипКонтрольные вопросы
rykovodstvo.ru > Руководство эксплуатация > Контрольные вопросы
1   2   3   4

Алгоритм 1: «Быстрая» сортировка (quicksort).

1. Выбирается опорный элемент (например, первый или случайный).

2. Реорганизуем массив так, чтобы сначала шли элементы меньшие опорного, потом равные ему, затем большие. Для этого достаточно помнить, сколько было найдено меньших (m1) и больших (m2), чем опорный и ставить очередной элемент на место с индексом m1, а очередной больший на место с индексом n-1-m2.

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

3. Если «меньшая» или «большая» часть состоит из одного элемента, то она уже отсортирована и делать ничего не надо. Иначе сортируем эти части с помощью алгоритма быстрой сортировки (то есть, выполняем для нее шаги 1-3).

Как видите, быстрая сортировка состоит из выполнения шагов 1 и 2 и рекурсивного вызова алгоритма для получившихся частей массива.

Алгоритм 2: Сортировка слиянием (merge sort).

  1. Делим массив на две части примерно одинакового размера и, если получившаяся половина массива содержит больше одного элемента, то сортируем ее с помощью сортировки слиянием. Как видите, этот пункт содержит рекурсивное обращение ко всему алгоритму в целом.

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

Алгоритм 3: Сортировка деревом (tree sort).

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

двоичные деревья поиска

Рис. 10. Двоичные деревья поиска, составленные из чисел 1, 3, 4, 6, 7, 8, 10, 13, 14.

Если для каждой вершины высота поддеревьев различается не более чем на единицу, то дерево называетсясбалансированным. Сбалансированные деревья поиска также называются АВЛ-деревьями (по первым буквам фамилий изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса). Как видно на рис. 10а показано сбалансированное дерево, на рис. 10б несбалансированное.

Заметим, что расположение чисел по возрастанию получится, если обходить эти деревья в обратном прядке.

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

Если дерево будет близко к сбалансированному, то сортировка потребует примерно n log2 n операций. Если не повезет и дерево окажется максимально несбалансированным, то сортировка займет n2 операций.

6.5. Произвольное количество вложенных циклов

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

Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n (\mathrm{c}_n^k). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:

1

2

3

for i1 := 1 to n do

  for i2 := i1 + 1 to n do

    writeln(i1, ' ', i2);

Сочетания из трех чисел (k=3) так:

1

2

3

4

for i1 := 1 to n do

  for i2 := i1 + 1 to n do

    for i3 := i2 + 1 to n do

      writeln(i1, ' ', i2, ' ', i3);

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

procedure Combinations(

  n, k: integer;

  //Массив, в котором будем формировать сочетания

  var Indexes: array of integer;

  //Счетчик глубины рекурсии

  d: integer);

var

  i, i_min: integer;

  s: string;

begin

  if d < k then

  begin

    if d = 0 then

      i_min := 1

    else

      i_min := Indexes[d-1] + 1;

    for i := i_min to n do

    begin

      Indexes[d] := i;

      Combinations(n, k, Indexes, d+1);

    end;

  end

  else

  begin

    for i := 0 to k-1 do

      write(Indexes[i], ' ');

    writeln;

  end;

end;

6.6. Задачи на графах

Графом называют графическое изображение, состоящее из вершин (узлов) и соединяющих некоторые пары вершинребер (рис. 11а).

Более строго: граф – совокупность множества вершин и множества ребер. Множество ребер – подмножество евклидова квадрата множества вершин (то есть ребро соединяет ровно две вершины).

Ребрам можно также присвоить направление. Граф в этом случае называется ориетированным (рис. 11б).

ориентированный и неориентированный графы

Рис. 11. (а) Граф. (б) Ориентированный граф.

Теория графов находит применения в самых разных областях. Несколько примеров:

  1. Логистика и транспортные системы. Вершинами будут склады с товарами или пункты назначения, а ребра – дороги, их соединяющие.

  2. Маршрутизация сетей. Вершины – компьютеры, соединенные в сеть, ребра – связи между ними. Решается задача о путях передачи данных с одного компьютера на другой.

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

  4. Электрические сети.

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

  6. И т. д.

Современная теория графов представляет собой мощную формальную систему, имеющую необозримое множество применений.

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

В программировании используются три способа хранения в памяти информации о стуктуре графов.

1) Матрицы смежности

Квадратная матрица M, где как строки, так и столбцы соответствуют вершинам графа. Если вершины с номерами i и j соединены ребром, то Mij = 1, иначе Mij = 0. Для неориентированного графа матрица, очевидно, симметрична. Ориентированный граф задается антисимметричной матрицей. Если ребро выходит из узла i и приходит в узел j, то Mij = 1, а симметричный элемент Mji = -1.

2) Матрица инцидентности

Столбцы матрицы соответствуют вершинам, а строки ребрам. Если ребро с номером i соединяет вершины с номерами j иk, то элементы матрицы Iij = Iik = 1. Остальные элементы i-й строки равны 0.

3) Список ребер

Просто набор пар номеров вершин, соединенных ребрами.

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

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

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

6.7. Фракталы

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

Классическим примером является кривая Коха, построение которой показано на рис. 12. Изначально берется отрезок прямой (рис. 12а). Он делится на три части, средняя часть изымается и вместо нее строится угол (рис. 12б), стороны которого равны длине изъятого отрезка (то есть 1/3 от длины исходного отрезка). Такая операция повторяется с каждым из получившихся 4-х отрезков (рис. 12в). И так далее (рис. 12г). Кривая Коха получается после бесконечного числа таких итераций. На практике построение можно прекратить, когда размер деталей окажется меньше разрешения экрана (рис. 12д).

процесс построения кривой коха

Рис. 12. Процесс построения кривой Коха.

Еще одним примером может служить деревце на рис. 6. Оно также содержит части, подобные всему дереву в целом, что делает его фракталом.

Фракталы, по сути, рекурсивные структуры и их построение естественно производить с помощью рекурсивных процедур.

7. Избавление от рекурсии

Любой рекурсивный алгоритм может быть переписан без использования рекурсии. Заметим, что быстродействие алгоритмов при избавлении от рекурсии, как правило, повышается. Еще одной причиной чтобы избавиться от рекурсии является ограничение на объем хранимых программой локальных переменных и значений параметров одновременно выполняющихся процедур. При очень глубокой рекурсии этот объем возрастает, и программа перестает работать, выдавая ошибку «Stack overflow» (переполнение стека).

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

Ниже представлено несколько вариантов того, как это можно сделать.

7.1. Явное использование стека

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

стек

Рис. 13. Наглядное представление стека. Push (проталкивание) – традиционное название для операции добавления данных в стек, Pop (выталкивание) – традиционное название для операции извлечения данных из стека.

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

При рекурсивных вызовах стек вызовов хранит цепочку из данных об одновременно работающих процедурах. Во всех продвинутых средах разработки эту цепочку вместе с запомненными параметрами процедур можно просмотреть во время отладки. Соответствующая команда обычно называется “Call Stack” (в Delphi ей соответствует сочетание клавиш Ctrl – Alt – S).

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

type

  //Запись для хранения параметров процедур

  Parameters = record

    //Список параметров

  end;

 

  //Стек удобно реализовать с помощью связанных списков

  //(http://www.tvd-home.ru/prog/16_4)

  PList = ^List;

  List = record

    Data: Parameters;

    Next: PList;

  end;

 

  //Описанный одновсязанный список соединим с методами

  //добавления и удаления элементов и получим стек.

  Stack = class

  private

    StackTop: PList;

  public

    //Добавление данных

    procedure Push(NewData: Parameters);

    //Извлечение данных

    function Pop: Parameters;

    //Проверка наличия данных

    function Empty: boolean;

  end;

 

implementation

 

//Добавление данных

procedure Stack.Push(NewData: Parameters);

var

  NewElement: PList;

begin

  New(NewElement);

  NewElement^.Data := NewData;

  NewElement^.Next := StackTop;

  StackTop := NewElement;

end;

 

//Извлечение данных

function Stack.Pop: Parameters;

var

  PopedElement: PList;

begin

  PopedElement := StackTop;

  StackTop := StackTop^.Next;

  Pop := PopedElement^.Data;

  Dispose(PopedElement);

end;

 

//Проверка наличия данных

function Stack.Empty: boolean;

begin

  Empty := StackTop = nil;

end;

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

1

2

3

4

5

6

7

8

9

10

11

procedure Recurs(P1: Parameters);

begin

  DoSomething(P1);

  if <условие> then

  begin

    P2 := F(P1);

    Recurs(P2);

    P3 := G(P1);

    Recurs(P3);

  end;

end;

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

procedure NonRecurs(P1: Parameters);

var

  S: Stack;

  P: Parameters;

begin

  S := Stack.Create;

  S.Push(P1);

  while not S.Empty do

  begin

    P1 := S.Pop;

    DoSomething(P1);

    if <условие> then

    begin

      P3 := G(P1);

      S.Push(P3);

      P2 := F(P1);

      S.Push(P2);

    end;

  end;

end;

Обратите внимание, что рекурсивные вызовы шли сначала для параметров P2, потом для P3. В нерекурсивной процедуре в стек отправляются сначала параметры P3, а только потом P2. Это связано с тем, что при рекурсивных вызовах в стек, по сути, отправляется недовыполненная часть процедуры, которая в нашем случае содержит вызов Recurs(P3).

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

1   2   3   4

Похожие:

Контрольные вопросы Задачи iconКонтрольные вопросы для самостоятельной работы студентов
Предмет и задачи курса отечественной истории. Сущность, формы и функции исторического знания

Контрольные вопросы Задачи iconКонтрольные вопросы тестового государственного междисциплинарного экзамена
Учеб пособие. Контрольные вопросы тестового государственного междисциплинарного экзамена. Под редакцией В. И. Козлова

Контрольные вопросы Задачи iconКонтрольные вопросы

Контрольные вопросы Задачи icon8. Контрольные вопросы
Введение ?

Контрольные вопросы Задачи iconКонтрольные вопросы
Изучение принципов гигиенического нормирования и санитарно-гигиенической оценки параметров вибрации

Контрольные вопросы Задачи iconТеория электрических цепей
Задание: изучить § 4, 5, 6 и письменно ответить на контрольные вопросы 23-26 на странице 137

Контрольные вопросы Задачи iconКонтрольные вопросы рефераты
Предмет, система, основные понятия и правовые источники дисциплины «Правоохранительные органы»

Контрольные вопросы Задачи iconКонтрольные вопросы 23
Информационные технологии: Учеб для вузов / Б. Я. Советов, В. В. Цехановский. — М.: Высш шк., 2003.— 263 с

Контрольные вопросы Задачи iconОренбург 2015 Контрольные вопросы: Организация дозиметрического контроля
«Оренбургский государственный медицинский университет» Министерства здравоохранения РФ

Контрольные вопросы Задачи iconКонтрольные вопросы Темы для сообщений
Структурная организация мк. Память и регистры мк. Ассемблер. Группа команд передачи данных

Контрольные вопросы Задачи iconКонтрольные вопросы Экзамен
Государственное автономное профессиональное образовательное учреждение «Ташлинский политехнический техникум» с. Ташла Оренбургской...

Контрольные вопросы Задачи icon§ Общие вопросы Винберг Г. Г
Винберг Г. Г. Концептуальные основы, перспективные задачи и вопросы кадрового обеспечения гидробиологических исследований // Гидробиологический...

Контрольные вопросы Задачи icon3 Литература 12 1 Контрольные вопросы. 12
Государственное учреждение "Чувашский республиканский радиологический центр" Министерства природных ресурсов и экологии Чувашской...

Контрольные вопросы Задачи iconКонтрольные вопросы и задания
«Практическая аэродинамика» для студентов заочной формы обучения профиля подготовки 25. 03. 03 Летная эксплуатация гражданских воздушных...

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

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


Руководство, инструкция по применению






При копировании материала укажите ссылку © 2018
контакты
rykovodstvo.ru
Поиск