4798

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

Практическая работа

Информатика, кибернетика и программирование

Техника описания ветвящихся алгоритмов Ход занятия. Задачи на взвешивания Задача. Упорядочение по весу 4-х предметов. Даны предметы A, B, C, D , весящие соответственно pA, pB, pC, pD гр. Описать алгоритм упорядочения этих предметов по весу. Поняти...

Русский

2012-11-27

142.5 KB

13 чел.

Техника описания ветвящихся алгоритмов

Ход занятия.

Задачи на взвешивания

Задача 1. Упорядочение по весу 4-х предметов.

Даны предметы A, B, C, D , весящие соответственно pA, pB, pC, pD гр. Описать алгоритм упорядочения этих предметов по весу.

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

Указания к решению.

  •  Описать входные-выходные данные задачи.  
  •  Построить дерево решений задачи.
  •  Реализовать вложенные ветвления, соответствующие построенному дереву решений.

 

Задача 2. Упорядочение по весу 5-ти предметов.  

Задача 3. Поиск фальшивой (более легкой) монеты среди 8-ми внешне одинаковых монет с помощью чашечных весов.

Задача 4. Пересечение прямоугольников

На координатной плоскости заданы координатами своих главных диагоналей 2 прямоугольника со сторонами, параллельными координатным осям:

P1 =(x1,y1, x2, y2)  P2 =(u1,v1, u2, v2)

Найти координаты главной диагонали пересечения Р1 и Р2, если это пересечение не пусто.   

Задача 5. Решение квадратного уравнения в радикалах

Разработать алгоритм и реализовать программу решения квадратного уравнения в радикалах.

Указания к решению.

Решения кв. уравнения  ax2 + bx + c = 0 в радикалах описываются формулами

X1 = (-b + D)/(2*a)  X2 = (-b - D)/(2*a)

Решения в радикалах предполагают вычисление корней по «школьным» правилам.

Алгоритм должен учитывать все те упрощения решений, которые делает школьник:

  •  D = 0 (одно решение)
  •  D – полный квадрат (уравнения имеют рациональные решения)
  •  В D выделяется нетривиальный полный квадрат (D = dD0)
  •  b = 0
  •  Знаменатель решения сокращается до 1
  •  …  …  …

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


Практическое занятие 2. Структурирование алгоритмов: Абстрактные типы данных.

Задача 1. АТД "Калькулятор"

Простейший калькулятор определим следующим образом:

Клавиатура: 0  . . . 9; + - *  / =;  . С  М+  МС  МR  MS 

Дисплей – ячейка, предназначенная для накопления результатов (сумматор)   

Дополнительная ячейка памяти M

Описать АТД, поддерживающий работу пользователя.

Задача 2. Реализация АТД "Геометрические задачи на построение"

В лекции 1 описан АТД "Геометрические задачи на построение". В задаче требуется

  •  определить структуры данных, реализующие АТ «точка», «прямая», «окружность».
  •  Определить заголовки процедур, реализующих АТ.
  •  Реализовать 2-3 процедуры.    

Задача 3. АТД "Рациональная арифметика".

Арифметика рациональных чисел должна содержать:

  •  основные арифметические операции;
  •  основные отношения (как минимум, отношения порядка);
  •  основные функции;
  •  процедуры ввода-вывода.

  


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

Операторы повторения ЯП Паскаль

For i := A to B do P

For i := A downto B do P

While U do P

Repeat P1; …; Pn until U

Бинарный алгоритм Евклида

 

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

 

Классический алгоритм Евклида можно описать следующим образом:

1.Рассмотри два числа  A и B.

2.Найди остаток R от деления большего числа на меньшее.

3.Если R = 0, то меньшее число и есть НОД(А, В)

  иначе R поставь на место большего и повтори вычисления   

 

Алгоритм 1

Function GCD( A, B: Integer):Integer;

     begin   {A > 0, B > 0}

        While (A<>0) and (B <>0) do  

 If A > B

    then A := A mod B

    else B := B mod A;

         GCD := A+B     

  {одно из чисел А, В равно нулю. Результат - второе}

    end;  

 

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

НОД(А, В) = НОД(В, А mod B)

Function GCD (A, B: Integer):Integer;

begin {A > 0, B > 0}

    If  B <> 0

       then GCD := GCD(B, A mod B)  {Аргументы меняются местами}

         else GCD := A

end;  

 

Обратите внимание на то, как меняются местами в рекурсивном вызове аргументы. Это позволяет не проверять числа на «больше -меньше». (Вопрос: почему?)


Бинарный алгоритм Евклида

Как и при «ручных» вычислениях, при вычислениях на компьютере операции mod, div требуют много времени. Поэтому важно построить алгоритм вычисления НОД, лишенный этого недостатка. Так называемый бинарный алгоритм Евклида использует только вычисления остатка и неполного частного от деления на 2 (A mod 2, A div 2), которые выполняются очень быстро (Вопрос: почему?).

 

Идея бинарного алгоритма состоит в следующем:

  •  Если оба числа четные, то их можно разделить на 2, умножив НОД на 2:

НОД(2А, 2В) = 2НОД(А,В)

  •  Если только одно из чисел четное, его можно разделить на 2:

НОД(2А, 2В+1) = НОД(А, 2В+1)

  •  Если оба числа - нечетные, из большего нужно вычесть меньшее, и разность станет четной:

НОД(2А+1, 2В+1) = НОД(2А-2В, 2В+1)

Последние два действия нужно повторять до тех пор, пока числа не равны 0

Решето Эратосфена

Как известно, натуральное число P называется простым, если оно делится только на 1 и на самого себя. Поскольку все числа делятся на 1 и на себя, эти делители называют тривиальными или несобственными. Остальные делители называют нетривиальными или собственными. Поиск собственных делителей натурального числа - одна из важных задач компьютерной арифметики. Достаточно сказать, что этой задачей занимается криптография - наука о шифровке и дешифровке («шпионских» сообщений).         

Алгоритм поиска всех простых чисел в интервале 2...N, известный как решето Эратосфена, состоит в  следующем:

1.Выписываем подряд все натуральные числа от 2 до N в последовательность А.    

2.Пусть Q - наименьшее число этой последовательности

  •  Просеиваем последовательность А через решето с шагом Q, т.е.
  •  Добавляем Q к списку уже найденных простых чисел
  •  Вычеркиваем из последовательности А все числа, кратные Q, начиная с Q;
  •  Находим наименьшее число последовательности (следующее простое число) - новое значение Q;   

Процесс просеивания начинаем с Q = 2 и повторяем до тех пор, пока последовательность А не исчерпана.

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

Если число p добавлено к списку простых, то следующее невычеркнутое число, кратное p, есть р2  ;

Поиск следующего наименьшего числа можно вести с шагом 2, если исходную последовательность начать с 3 (наименьшего нечетного простого числа);

Количество необходимых просеиваний последовательности А не превосходит числа Sqrt(N).


Посимвольный ввод натурального числа с защитой от ошибок

В реальных программах необходимо осуществлять контроль правильности ввода с клавиатуры каждого символа. В частности, при вводе натурального числа нужно контролировать:

  •  Ввод только цифр;
  •  Количество вводимых цифр (защита от переполнения).

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

Какие дополнительные требования можно предъявлять к такой процедуре?

Генерация возрастающей последовательности чисел вида akbl

Разработать алгоритм и программу, которая генерирует все числа вида akbl ,  k = 0,1,2,…         l = 0,1,2, …в порядке возрастания.

Алгоритм 2.

Function BinGCD( A, B: Integer):Integer;

        Var D:Integer;

 begin   {A > 0, B > 0}

 D:=1;

While (A mod 2 = 0) and  (B mod 2 = 0)  do begin

            A:=A div 2; B := B div 2; D := 2*D

end;  {Выделили наибольший делитель - степень 2 }

 While (A <>0) and (B <> 0) do begin

    While A mod 2 = 0 do A := A div 2;

    While B mod 2 = 0 do B := B div 2;

       If A > B then A := A - B  else B := B - A

 end;

 BinGCD := (A+B)*D

   end;  

Задача 1. Докажите, что имеет место условное соотношение

Если А > B то НОД(А, В) = НОД(А-В, В)

 Напишите программу вычисления НОД двух чисел, опирающуюся на это соотношение. 

Задача 2. Докажите, что имеет место соотношение

НОД(А, В) = НОД(В mod A, А mod B)

 Напишите программу вычисления НОД двух чисел, опирающуюся на это соотношение. 

 

Задача 3 Дробь А/В задана своим числителем А и знаменателем В (B>0). Напишите программу вычисления несократимой дроби А11, равной исходной.

 

Задача 4. Напишите алгоритм вычисления наименьшего общего кратного двух натуральных чисел.

Задача 5. Опираясь на соотношение НОД(A, B, C) = НОД(НОД(А, B), C) , напишите программу вычисления НОД(A1, A2, ..., An), где A1, A2, ..., An - последовательность натуральных чисел, заданная в виде массива.

Алгоритм 4 (Решето Эратосфена).

Program Eratosphen;

   Const N = 1000; M = 1000;

    Type Cardinal = array [3..N] of Boolean;

         Prime = array [1..M] of Integer;

       Var Grate:Cardinal;   P:Prime;

              i, j, Q, Sup :Integer;

begin

     For i := 2 to N do Grate[i] := True;   {Инициализация решета}

     For j := 1 to M do P[j] := 0;

     Q := 2;   Sup := trunc(Sqrt(N));   j := 1;

     Repeat  {Просеивание через решето}

        P[j] := Q; i := Sqr(Q);

        While i <= N do  {Исключение чисел, кратных простому числу Q }

          begin Grate[i] := False; i := i + Q end;

        Repeat Inc(Q) until Grate[Q];  {Поиск следующего простого числа }

        Inc(j)

     until Q > Sup;

     For i := Q to N do {Занесение в список простых чисел, > Sgrt(N)}

        If Grate[i] then begin P[j] := i; Inc(j) end;

     {Распечатка списка простых чисел}

end.


Практическое занятие №
3. Задачи обработки последовательностей: поиск

  •  Общая постановка задачи поиска в последовательности. АТД задачи.
  •  Поиск методом линейного просмотра.
  •  Поиск методом бинарного просмотра (бинарный поиск).

  •  Поиск элемента в массиве

Задача поиска элемента в последовательности - одна из важных задач программирования как с теоретической, так и практической точек зрения. Вот ее формулировка:

Пусть A = {a1, a2, ...} - последовательность однотипных элементов и b - некоторый элемент, обладающий свойством P. Требуется найти место элемента b в последовательности А. 

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

Например:

1. Найти максимальный элемент массива;

2. Найти данный элемент массива;

3. Найти k-тый по величине элемент массива;

Наиболее простые и часто оптимальные алгоритмы основаны на последовательном просмотре массива A с проверкой свойства P на каждом элементе. Этот метод называют линейным просмотром (поиском).

  •  Линейный поиск в массиве

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

Рrogram MinItem;

 Const n = 100;

   Var A : Array [1..n] of Real;

        Min, Item : Real;   Index, i : Integer;

 Begin

  {Блок ввода массива}

  Index := 1; Min := A[1];

  For i := 1 to n do begin

    Item := A[i];

    If Min > Item

     then begin Index := i; Min := Item end

  end;

  {Вывод значения Index}

 End.

Переменная Item введена для того, чтобы избежать повторных вычислений индексного выражения в A[i].

Для наглядного представления массива часто полезно изображать его в системе координат Индекс – Величина элемента.  

      

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

Min – текущее значение искомого элемента. Index – его номер в массиве. Перед первым шагом просмотра Min = A[1], а Index = 1. На i-том шаге A[i] сравнивается с min. Если A[i]  >  min, значение min не меняется. На рисунке изображена ситуация, в которой на j-том шаге просмотра A[j] < min, поэтому min принимает значение A[j], а Index – значение j. Просмотр заканчивается через n-1 шаг.            

Задача 1 Рассмотрите поведение этого алгоритма и его модификации в случае, когда минимальных элементов в массиве несколько и требуется найти первый, последний, а также все минимальные элементы.

Пример 2. Поиск данного элемента в массиве.

 Program Search_in_Array;

  Label  1;

  Const n = 100;

    Var A: Array[1..n] of Real;

             b: Real;   Flag: Boolean;   i: Integer;

  Begin

    {Блок чтения массива A и элемента b}

   Flag := true;

   For i := 1 to n do

      If A[i] = b then begin

         Flag := false; goto 1

   end; {прерывание цикла}

   1:If Flag

      then Writeln(‘Элемент ‘,b,’в массиве отсутствует’)

      else Writeln(‘элемент ‘,b,’стоит на’,i,’-том месте’);

  End.

Рассмотрим красивое решение этой задачи без применения оператора Goto. Это решение использует цикл While вместо использования цикла For c досрочным выходом при помощи Goto:

Program WhileSearch;

   Const n = 100;

     Var A : Array[1..n] of Real;

           b : Real; i : Integer;

  Begin

   {Блок чтения массива A и элемента b}

    i := 1;

    While (i <= n) and (A[i] <> b) do i := Succ(i);

     If i = n + 1

      then Writeln(‘Элемент‘,b,’в массиве отсутствует’)

      else Writeln(‘элемент ‘,b,’ расположен на ’,i,’ -том месте’);

  End.

Недостатком такой реализации является во-первых, использование сложного условия в цикле, во-вторых - возможно некорректное вычисление подвыражения A[i] <> b при i = n +1. Несмотря на то, что условие заведомо ложно (i <= n = False), выражение A[n+1] <> b не определено! Дополним массив A еще одним элементом: A[n+1] = b, и все недостатки легко устраняются!

Program LinearSearch;

  Const n = 101; { Размер массива увеличен на 1 }

     Var A : Array[1..n] of Real;

           b : Real;  i : Integer;

  

Begin

   { Блок чтения массива A и элемента b }

   i := 1;

   A[n] := b; { Дополнили массив “барьерным” элементом }

   While A[i] <> b do i := Succ(i);

    If i = n

      then Writeln(‘Элемент ‘,b,’в массиве отсутствует’)

      else Writeln(‘элемент ‘,b,’расположен на’,i,’-том месте’);

   End.

Рис 2. Поиск места элемента в массиве методом линейного просмотра с барьером.  

b – элемент, место которого необходимо найти. Перед 1-ым шагом просмотра в массиве устанавливают барьер: A[n] := b. На i-том шаге просмотра A[i] сравнивается с b. Алгоритм заканчивает работу при A[i] = b. Если при этом окажется, что i = n, искомый элемент в массиве отсутствует. В противном случае i - его место. Наличие барьера гарантирует корректное завершение цикла.  

  •  1.4. Бинарный поиск в упорядоченном массиве

Задача поиска существенно упрощается, если элементы массива упорядочены. Стандартный метод поиска в упорядоченном массиве - это метод деления отрезка пополам, причем отрезком является отрезок индексов 1..n. В самом деле, пусть m (k < m < l) - некоторый индекс. Тогда если A[m] > b, далее элемент нужно искать на отрезке k..m-1, а если A[m] < b - на отрезке m+1..l.

Для того, чтобы сбалансировать количество вычислений в том и другом случае, индекс m нужно выбирать так, чтобы длины отрезков k..m, m..l были (приблизительно) равными. Описанную стратегию поиска называют бинарным поиском. 

Пример 3. Поиск элемента в упорядоченном массиве.

Program BinarySearch;

  Const n = 100;

    Var A : Array[1..n] of Real;

         b : Real; Buffer : Real;

         k, l, m : Integer;

  Begin

   { Блок чтения упорядоченного массива A и элемента b }

   k := 1; l := n;

   Repeat

      m := (k + l) div 2; Buffer := A[m];

      If Buffer > b

         then l := Pred(m)  else k := Succ(m)

    until (Buffer = b) or (l < k);

    If A[m] = b

      then Writeln(‘Индекс = ‘, m)

      else Writeln( ‘Элемент не найден’)

  End.

Рис 3. Бинарный поиск в упорядоченном массиве.  

b – элемент, место которого необходимо найти. Шаг бинарного поиска заключается в сравнении искомого элемента со средним элементом A[m] в диапазоне поиска [k..l]. Алгоритм заканчивает работу при A[m] = b. Если A[m] > b, поиск продолжается слева от m, а если A[m] < b – справа от m.  При l < k поиск завершается, и элемент не найден.

Нетрудно получить оценку числа С(n) сравнений метода. Пусть М - количество повторений цикла. Тогда  М [log2 (n)] Поскольку на каждом шаге осуществляется 2 сравнения, в худшем случае  

C(n) = 2[log2 n] = O(log2 n)

При n = 1000000 алгоритм совершает максимум 40 сравнений, в то время как линейный просмотр требует всех 1000000 сравнений.     

  •  Задачи для самостоятельного решения
  1.  Дан массив А[1..n]. Подсчитать средние арифметические всех отрицательных и всех положительных его элементов.
  2.  Последовательность из n точек плоскости задана массивами Х[1..n] и Y[1..n] координат. Найти точку, наименее удаленную от начала координат.
  3.  Дан массив А[1..n]. Найти все его элементы, меньшие, чем все предыдущие.
  4.  Дан массив A[1..n]. Найти в этом массиве наибольшую по количеству элементов возрастающую подпоследовательность подряд идущих элементов.
  5.  Дан массив A[1..n], состоящий из нечетного (n = 2k+1) числа попарно неравных элементов. Найти средний по величине элемент в массиве.
  6.  Дан массив A[1..n] действительных чисел. Найти в этом массиве наименьшее положительное число.
  7.  Дан массив A[1..n] целых чисел. Найти в этом массиве наибольшее количество подряд идущих нулей.
  8.  Дан массив A[1..n] целых чисел. Отрезок индексов k .. m называется отрезком роста массива, если A[k]<A[k+1]<...<A[m]. Найти отрезок роста максимальной длины.
  9.  Элемент a[i] массива A называется барьерным, если

a[j] <= a[i]  при j < i   и  a[j] >= a[i]  при j > i

Найти все барьерные элементы массива А.

  1.  Массив A[1..n] состоит из действительных чисел, причем для любого 2 i n-1 выполнено неравенство A[i] (A[i-1] + A[i+1])/2 Составить программу поиска наименьшего и наибольшего элементов массива, сложность которой

C(n) = O(log2(n))

  1.  Даны упорядоченные массивы A[1..n] и B[1..m] целых чисел и целое число C. Составить программу поиска таких индексов i  и  j, что  C = A[i] + B[j],  сложность которой C(n) = O(log2(n m))
  2.  Дан массив A[1..n]. Тип элементов массива роли не играет. Составить программу циклического сдвига элементов этого массива на k позиций вправо. Алгоритм не должен использовать дополнительную память.
  •  1.5. Метод асинхронного просмотра

Некоторые задачи обработки массивов решаются методом, суть которого заключается в «параллельном» просмотре нескольких массивов, либо в просмотре одного массива с помощью нескольких «просматривающих» индексов, меняющих свои значения независимо. Классическая задача, эффективное решение которой достигается этим методом – задача слияния двух упорядоченных массивов.  

Пример 4. Даны упорядоченные массивы А[1..n] и В[1..m]. Построить упорядоченный массив С, содержащий как все элементы массива A, так и все элементы массива В.

Program  Merging;

Const  L = 100;

Type Vector = array[1..L]of Integer;

Var A, B, C: Vector;

   SizeA, SizeB, SizeC: Integer;

Procedure Merge(Var mA, mB, mC: Integer; var A, B, C: Vector);

      var i, j, k, l: Integer;

     begin

       i:=1; j:=1; k:=1;

       While (i <= mA) and (j <= mB) do begin

         If A[i]<=B[j]

          then begin  C[k] := A[i];  Inc(i) end

          else  begin  C[k] := B[j];  Inc(j) end;

         Inc(k)

       end;

        For l := i to mA do begin C[k] := A[l];  Inc(k)  end;

        For l := j to mB do begin C[k] := B[l];  Inc(k) end;

        mC := k-1;

      end;

 

Begin

  Inp(SizeA, A);

  Inp(SizeB, B);

  Merge(SizeA, SizeB, SizeC, A,B,C);

  Print(SizeC, C);

 End.

Рис 4. Слияние двух массивов методом асинхронного просмотра.  

Алгоритм представлен процедурой Merge. Ее параметры – размеры массивов и собственно массивы. Перед слиянием «просматривающие индексы» i, j, k устанавливаются на 1. Шаг алгоритма заключается в сравнении рассматриваемых элементов сливаемых массивов А и В.  В результирующий массив С копируется меньший из сравниваемых элементов, и соответствующие индексы инкрементируются. На рисунке показаны результаты первых 4-х шагов работы алгоритма, а также k-тый шаг. Асинхронный просмотр осуществляется, пока один из массивов не окажется просмотренным полностью. После этого в массив С переписывается «хвост» второго массива.       

Рассмотренный алгоритм в худшем случае совершает m + n сравнений, где m и n – размеры сливаемых массивов. Поэтому его сложность по времени имеет оценку  T(n, m) = O(m+n).  

  •  Задачи для самостоятельного решения
  1.  Массив A[1..n] состоит из данных типа Color = (white, red, black). Составить программу сортировки массива A, которая проверяет значение (цвет) каждого элемента только один раз.
  2.  Даны упорядоченные массивы А[1..n] и В[1..m]. Составить программу поиска всех элементов массива A, не входящих в В.
  3.  17.Даны упорядоченные массивы А[1..n] и В[1..m]. Составить программу поиска всех элементов массива A, входящих в В.
  4.  Дан двумерный массив A[1..m, 1..n], все строки которого упорядочены неубыванию. Составить программу, которая строит одномерный массив В, содержащий все элементы массива А, упорядоченные по неубыванию.
  5.  Дан одномерный массив, элементами которого являются натуральные числа. Составить программу, которая разделяет этот массив на два массива, один из которых содержит четные числа, а другой – нечетные.    


Практическое занятие № 4.  Задачи сортировки.

  •  Постановка задачи сортировки последовательности.

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

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

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

Пусть нам дана последовательность элементов a1, a2, ... , an. Элементы этой последовательности - данные произвольного типа, на котором определено отношение порядка “<<” (меньше) такое, что любые два различных элемента сравнимы. Сортировка означает перестановку элементов последовательности ak1, ak2, ... , akn   такую, что

ak1 << ak2 << ... << akn.

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

Сортировка массивов

Если последовательность a1, a2, ... , an реализована как массив a[1..n], вся она расположена в адресуемой памяти. Поэтому наряду с требованием эффективности по времени основное требование - экономное использование памяти. Это означает, что алгоритм не должен использовать дополнительных массивов и пересылок из массива a в эти массивы.

Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий с данными сортируемого типа: сравнение двух элементов (x << y) и пересылка элемента (x := y). Поэтому удобная мера сложности алгоритма сортировки массива a[1..n] по времени - количество сравнений C(n) и количество пересылок M(n).

Известные алгоритмы сортировки массивов делятся на простые и быстрые (эффективные). Независимо от принадлежности тому или иному классу, рассматриваемые здесь алгоритмы используются на практике.  

  •  Деревья решений задачи сортировки.

Задача № 1.

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

Задача № 2.

Каким может быть дерево решений для задачи сортировки последовательности из 4-х элементов: Сколько листьев у этого дерева? Какой должна быть минимальная высота этого дерева?   

Сколько сравнений должна выполнить программа для того, чтобы определить порядок расположения элементов в этой последовательности?   


  •  Простые алгоритмы сортировки.

Сортировка обменами

Основное действие сортировки обменами - сравнение двух элементов и, если результат сравнения отрицателен, перестановка их местами:

Если при i < j a[i] > a[j]

  то переставить a[i] и a[j].

В наиболее простом варианте сравниваются рядом стоящие элементы a[j] и a[j+1] :

Program BublSort;

  Const n = 100;

    Var a : array[1..n] of Real;

         i, j : Integer;  b : Real;

 Begin

  { Блок ввода массива }

  For i := n - 1 downto 1 do

  For j := 1 to i do

  If a[j] > a[j+1] then begin

     b := a[j+1]; a[j+1] := a[j]; a[j] := b end;

  { Блок вывода массива }

 End.

Алгоритм сортировки обменами  

Алгоритм BublSort  осуществляет n-1 линейный просмотр массива а. В  результате каждого просмотра наибольший элемент просмотренной части массива «всплывает» на последнее место. Первый просмотр осуществляется во всем массиве, а каждый следующий – в диапазоне, на единицу меньшем. Таким образом, правая часть массива становится упорядоченной. На рисунке эти элементы – от a[k] до a[n] - заштрихованы серым. На каждом шаге просмотра сравниваются два рядом стоящих элемента. На рисунке – это элементы a[i] и a[i+1]. Если они расположены неправильно (засортировка), алгоритм меняет их местами.

Анализ алгоритма сортировки обменами

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

Для обоснования алгоритма сортировки необходимо доказать, что алгоритм всегда (независимо от входа) завершает свою работу и его результат - упорядоченный по возрастанию массив. Оценка сложности (эффективности) алгоритма по времени заключается в нахождении C(n), M(n) в худшем случае, в среднем. Поскольку алгоритм сортирует массив “на месте”, его сложность по памяти - константа.

К другим свойствам алгоритма можно отнести свойство устойчивости. (Алгоритм сортировки называется устойчивым, если он не переставляет местами равные элементы.) Осуществим анализ алгоритма сортировки обменами.

Завершаемость

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

Корректность

Внутренний цикл алгоритма (с параметром j) осуществляет последовательный просмотр первых i элементов массива. На каждом шаге просмотра сравниваются и, если это необходимо, переставляются два соседних элемента. Таким образом, наибольший среди первых i+1 элементов “всплывает” на i+1-ое место. Поэтому после выполнения оператора If имеет место соотношение:

a[j+1] = Max(a[1], ..., a[i], a[j+1])

а после завершения цикла (i = j) имеет место соотношение

a[i+1] = Max(a[1], ..., a[i], a[i+1])

Внешний цикл (с параметром i) управляет длиной просматриваемой части массива: она уменьшается на 1. Поэтому после завершения внутреннего цикла имеет место соотношение:  a[i+1]  a[i+2]  ...  a[n] После завершения внешнего цикла получим:

а[1]  a[2], a[2]  a[3]  ...  a[n]   т.е. массив отсортирован.

Эффективность по времени

Внешний цикл выполнился n-1 раз. Внутренний цикл выполняется i раз (i = n-1, n-2, ..., 1). Каждое выполнение тела внутреннего цикла заключается в одном сравнении и, возможно, в одной перестановке. Поэтому

C(n) = 1+2+ ... +n-1 = n*(n-1)/2,       M(n)n*(n-1)/2

В худшем случае, когда элементы исходного массива расположены в порядке убывания   

C(n) = n*(n-1)/2 = O(n2), M(n)=n*(n-1)/2= О(n2)

Устойчивость

Для доказательства устойчивости достаточно заметить, что переставляются только соседние неравные элементы.

Сортировка выбором

Основное действие сортировки выбором - поиск наименьшего элемента в просматриваемой части массива и перестановка с первым элементом этой части:

For i := 1 to n - 1 do begin

 k := Индекс( Min(a[i], ..., a[n]));

 Переставить a[i], a[k]

end;


Program SelectSort;

  Const n = 10;

    Var a : array[1..n] of Real;

        i, j, MinInd : Integer;  b : Real;

 Begin

  {Блок ввода массива}

  For i := 1 to n - 1 do  begin

    MinInd := i;

    for j := i + 1 to n do

    If a[j] < a[MinInd] then MinInd := j;

b := a[MinInd];  a[MinInd] := a[i];  a[i] := b

   end;

  {Блок вывода массива}

End.

Рис 8. Алгоритм сортировки обменами  

Алгоритм SelectSort  осуществляет n-1 линейный просмотр массива а. В  результате каждого просмотра наименьший элемент просмотренной части массива меняется местами с первым элементом этой части. Первый просмотр осуществляется во всем массиве, а каждый следующий – в диапазоне, на единицу меньшем. Таким образом, левая часть массива становится упорядоченной. На рисунке эти элементы – от a[1] до a[i] - заштрихованы серым. На рисунке выделены переставляемые элементы a[i+1] и a[MinInd].

Анализ алгоритма сортировки выбором

Улучшенный алгоритм сортировки обменами

В программе BublSort цикл For используется в качестве внешнего. Это приводит к тому, что он выполняется ровно n-1 раз, даже если массив уже упорядочен после нескольких первых проходов. От лишних проходов можно избавиться, применив цикл Repeat и проверяя во внутреннем цикле массив на упорядоченность:

Этот алгоритм можно еще улучшить, если каждый следующий проход начинать не с начала (j = 1), а с того места, где на предыдущем проходе произошел первый обмен:

{LowIndex : Integer;}

Repeat

 isOrd := True; { признак упорядоченности }

 LowIndex := 1; { отрезок A[1..LowIndex] упорядочен }

 For j := LowIndex to i do

   If a[j] > a[j+1]

     then begin

       TempMem := a[j+1]; a[j+1] := a[j]; a[j] := TempMem;

        If isOrd then begin LowIndex := j; isOrd := False

     end

 end;

 i := Pred(i)

 until isOrd;

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

Сортировка вставками

Еще один простой алгоритм сортировки - сортировка вставками основан на следующей идее: предположим, что первые k элементов массива A[1..n] уже упорядочены:  A[1]  A[2] ...  A[k], A[k+1], ..., A[n]. Найдем место элемента A[k+1] в начальном отрезке A[1],...,A[k] и вставим этот элемент на свое место, получив упорядоченную последовательность длины k+1. Поскольку начальный отрезок массива упорядочен, поиск нужно реализовать как бинарный. Вставке элемента на свое место должна предшествовать процедура сдвига “хвоста” начального отрезка для освобождения места.

Program InsSort;

  Const n = 100;

     Var A : array[1..n] of Integer;

           k : Integer;    l, r, i, j : Integer;    b : Integer;

  Begin

  {Блок чтения массива A}

    For k := 1 to n-1 do begin

     b := A[k+1];

     If b < A[k]

      then begin

        l := 1; r := k; {Бинарный поиск}

       Repeat

          j := (l + r) div 2;   If b < A[j]  then r := j  else  l := j + 1;

        until (l = j);{ Сдвиг “хвоста” массива на 1 позицию вправо}   

        For i := k downto j do A[i+1] := A[i];

         A[j] := b ; { Пересылка элемента на свое место}

      end

    end;    {Блок вывода массива A}

  End.

Алгоритм сортировки вставками  

Алгоритм InsSort  осуществляет n-1 линейный просмотр массива а. В каждом просмотре ищется место элемента a[]k+1], следующего непосредственно за уже упорядоченным диапазоном массива 1..k. На рисунке этот диапазон – от a[1] до a[k] – заштрихован серым Затем элемент a[]k+1] вставляется на свое место. Вставке элемента предшествует сдвиг диапазона j..k вправо на одну позицию. Таким образом, левая, уже упорядоченная часть массива становится большей на 1 элемент. На рисунке выделены обрабатываемый элемент a[k+1] и элементы, между которыми он вставляется.  

Задача для самостоятельного решения.  

Задача 3.  Множество точек плоскости {Ai = ( Xi, Yi )} задано массивами координат X[1..n] и Y[1..n]. Выпуклой линейной оболочкой этого множества называется такое его подмножество B, что многоугольник с вершинами в точках из B является выпуклым и содержит все множество A. Составить программу поиска выпуклой линейной оболочки множества A. Оценить ее сложность.


   1          2       3      4 . . .          i . . .                        j     . . .                           n-1      n         
Индекс 

Величина

              Min                      A[i]                        A[j]   

Просмотр от первого элемента к последнему

   1      2     3    4 . . .                             i . . .                          j     . . .      n-1     n     Индекс 

Величина

          A[i]

Просмотр от первого элемента к последнему (барьеру)

Барьер: A[n]=b

            k  k+1 . . .                          m-1    m     m+1         . . .                   l-1      l              Индекс

Величина

A[m], m = (k+l) div 2

b

Поиск слева

Поиск справа

     1     2     . . .      i    i+1 . . .    mA-1 mA                                Индекс 

Величина

Массив A

Величина

     1     2    . . .           j   j+1   . . .      mB-1  mB                      Индекс

Массив B

Величина

     1   2   3    4     . . .           k   k+1      . . .                               Индекс

a1

b1

b2

a2

Массив C

Величина

      1    2    3         . . .            i    i+1      . . .             k            n-1    n          Индекс 

Массив a

Величина

      1   2     . . .    i    i+1          . . .         MinInd     . . .       n-1    n          Индекс

Массив a

Величина

      1   2     . . . j-1  j                   k  k+1          . . .               n-1  n    Индекс

Массив a

Сдвиг на 1 позицию вправо


 

А также другие работы, которые могут Вас заинтересовать

57765. Текст-переклад. Бінарний урок з інформатики та англійської мови 143.5 KB
  А зараз давайте пригадаємо пристрій, який допоможе нам друкувати текст. Називається він?(клавіатура). На клавіатурі знаходиться багато клавіш. Це алфавітно-цифрове поле (демонструється малюнок клавіатури).
57766. Перерізи многогранників. Метод слідів 712 KB
  Многогранники Опуклі многогранники Правильний многогранник Куб Паралелепіпед Піраміда Призма а у другій – нові переріз діагональний переріз січна площина.
57767. Перська держава 73.5 KB
  Мета: ознайомити учнів з особливостями зародження і функціонування держави Персії охарактеризувати діяльність найвідоміших правителів Персії: Кіра ІІ Дарія І розкрити завойовницький характер їх зовнішньої політики...
57768. Теорема Піфагора 271.5 KB
  Мета: сформулювати і довести теорему Піфагора; познайомити учнів з біографією Піфагора; вчити застосовувати теорему до розвязання задачрозвивати логічне мислення; розвивати інтерес до математики...
57769. Союз гіпотенузи та катетів. Теорема Піфагора 1.81 MB
  Тип проекту: Пізнавальний дослідницький творчий За кількістю учасників: груповий За тривалістю підготовки: короткотривалий два тижні Епіграф: Не роби ніколи того що не знаєш але вчись усьому що потрібно знати і тоді будеш вести спокійне життя.
57770. Розв’язування квадратних рівнянь та рівнянь, що зводяться до квадратних 6.68 MB
  Мета: освітня – узагальнити та систематизувати знання учнів з теми: “Розв’язування квадратних рівнянь та рівнянь, що зводяться до квадратних”; виховна – виховувати самостійність, інтерес до вивчення математики...
57771. Питание и здоровье 191 KB
  Образовательная: установить связь между особенностями питания человека и его здоровьем; пояснить значение рационального питания поддержания здорового образа жизни; познакомить с распространенными болезнями человека...
57772. Питание и здоровье 349 KB
  Базовые понятия и термины: рациональное питание норма питания энергетический баланс. Здоровье человека его трудоспособность долголетие адаптация к изменчивым условиям окружающей среды в значительной степени зависит от правильного питания. Что же является основой рационального питания Нам предстоит сегодня узнать сообщение темы и целей урока запись в тетрадь.
57773. Програмне забезпечення ПК 432.5 KB
  Актуальність теми: Комп’ютер - універсальний пристрій призначений для опрацювання інформації. Утім сам по собі комп’ютер не володіє знаннями у жодній області свого використання. Якщо ми кажемо: комп’ютер зробив мається на увазі що на комп’ютері була виконана програма яка дозволила виконати ці дії.