4775

Операторы повторения с параметром и массивы

Реферат

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

Операторы повторения с параметром и массивы. Оператор цикла с параметром. Циклические программы. Сложность циклической программы. Оптимизация циклических программ. Ограниченные типы. Сложные (составные) типы. Регулярный тип. Массивы. Пои...

Русский

2012-11-26

113 KB

4 чел.

Операторы повторения с параметром и массивы.

1.Оператор цикла с параметром.

2.Циклические программы.

Сложность циклической программы.

Оптимизация циклических программ.

3.Ограниченные типы.

4.Сложные (составные) типы.

5.Регулярный тип. Массивы.

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

7.Эффективность алгоритма по времени.

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

9.Постановка задачи сортировки.

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

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

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

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

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

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

10.Задачи и упражнения

1.Оператор цикла с параметром.

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

Для реализации циклических алгоритмов в языке Паскаль используются операторы повторения:

оператор цикла с параметром;

оператор цикла с предусловием;

оператор цикла с постусловием.

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

For <параметр> := <начальное значение> to <конечное значение> do <оператор>

или

For<параметр>:=<начальное значение> downto <конечное значение> do <оператор>

Синтаксическая диаграмма оператора цикла с параметром:

Оператор цикла

с параметром

Здесь

Имя - это имя переменной - параметра цикла;

A - начальное значение параметра цикла;

B - конечное значение параметра цикла;

Оператор - тело цикла.

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

Если начальное и конечное значения разделяет служебное слово to, то после выполнения оператора (тела цикла) параметр цикла v принимает значение Succ(v), если же разделителем начального и конечного значений служит слово downto, то параметр цикла v после выполнении тела цикла принимает значение Pred(v). В частности, если параметр v имеет тип Integer, то одновременно с выполнением тела цикла осуществляется либо присваивание v := v + 1 (to), либо   v := v - 1 (downto).  Дополнительно (принудительно) изменять значение параметра в теле цикла не рекомендуется, поскольку контроль за правильностью исполнения такого цикла очень затруднен.  Если в цикле с to начальное значение больше, чем конечное, то цикл не выполняется вообще. Аналогично, если в цикле с downto начальное значение меньше, чем конечное, цикл также не выполняется.

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

Пример 1.

Program NFactorial; var Factorial, Argument: Integer; i : Integer;

 Begin

   Write(‘ введите аргумент факториала ‘);

    Readln(Argument) ;

    Factorial := 1;

    For i := 2 to Argument do Factorial := i*Factorial;

    Writeln(Argument,’! = ‘, Factorial)

 End.

В этом примере

i - параметра цикла;

2 - начальное значение параметра цикла;

Argument - конечное значение параметра цикла;

Factorial := i*Factorial - тело цикла.

Отметим, что на входе Argument > 7 значение Factorial выйдет за пределы типа Integer и результат будет неправильным.         

В следующем примере вычисляются суммы    xn/n2,    xn/n3

Пример 2.                 n=0           n=0

Program SeriesSumma;

 Var Summa1, Summa2, x : Real;

 u1, u2 : Real;

 v : Real;

 Index, n : Integer;

Begin

Write(‘ введите x и n ‘); Readln(x, n);   {Инициализация переменных, используемых в цикле}

Summa1 := 1; Summa2 := 1;                  { суммы рядов }

 v := 1; { x^n }

 For Index := 1 to n do begin

    v := v*x;

    u1 := v/Sqr(Index);  u2 := u1/Index;

    Summa1 := Summa1 + u1;  Summa2 := Summa2 + u2;

  end;

 Writeln( ‘ S1 = ‘, Summa1,’ ‘,’ S2 = ‘, Summa2)

End.

Обратите внимание на то, что все операторы, которые необходимо выполнить в цикле, объединены в составной оператор.

Часто шаг изменения переменной, которая управляет циклом, отличен от 1, -1. Следующий пример демонстрирует применение цикла с параметром в таких вычислениях.

Пример 3. Табулирование функции вещественного переменного.

Рrogram Tabulation;

  const Pi=3.14159262;

  var MinBound, MaxBound, Step: Real;

  x, y : Real;   Coef : Real;

  i, n : Integer;

Begin

 Write(‘Введите пределы табулирования ‘); Readln(MinBound, MaxBound);

 Write(‘Введите шаг табулирования ‘); Readln(Step);

 n := Round((MinBound - MaxBound)/Step);

 x := MinBound;   Coef := 1/Sqrt(Pi);

 for i := 0 to n do  begin

   y := Coef * exp(-Sqr(x)/2);

   writeln(‘ x = ‘,x,’ y = ‘,y);

   x := x + Step

 end;

End.

Программа табулирует функцию y=1/ e-x2/2 в интервале значений [MinBound, MaxBound] с шагом Step. Обратите внимание на то, что перед входом в цикл вычисляется N - верхняя граница параметра цикла, а в теле цикла вычисляется следующее значение х.

Пример 4.

program Alfabet;

 Var Letter : char;

 Begin

  For Letter := ‘z’ downto ‘a’ do Write(Letter, ‘,’)

 End.

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

2.Циклические программы. Сложность циклической программы. Оптимизация циклических программ.

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

Сложность Tц простейшей циклической программы, содержащей арифметический цикл, определяется формулой Tц = NTb где N - количество повторений цикла, Tb - сложность тела цикла.  Если арифметический цикл завершается нормально, то N = |Ord(MaxVal) - Ord(MinVal)|, где MaxVal, MinVal - нижняя и верхняя границы параметра. Таким образом, оптимизация программы по времени заключается в уменьшении сложности тела цикла и (если это возможно) уменьшении количества повторений цикла.

Для оптимизации тела цикла используют следующие приемы:

Предварительное (вне цикла) вычисление подвыражений, значение которых не меняется в цикле. Например, в программе Tabulation до входа в цикл вычислено значение Coef=1/Sqrt(Pi);

Использование соотношений, связывающих переменные, изменяющиеся в цикле, для вычислений одной из них через другие. В программе SeriesSumma переменные u1 и u2 - члены ряда - определены как функции от x, i:

u1(x, i) = xi / i2;   u2(x, i) = xi / i3;

Поэтому имеет место равенство u2*i = u1, которое используется для вычисления u2.

3.Ограниченные типы.

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

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

Ограниченный

тип

Например:

а) Type Day = 1..30; - ограничение на тип integer;

б) Digit = ‘0’..’9’; - ограничение на тип char;

в) Type Weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

Workday = Monday .. Friday; -  ограничение на скалярный тип Weekday.

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

Пример 5.

Program Time_Table;

 Type Weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

        Workday = Monday .. Friday;

   Var i : Workday;

 Begin

   For i := Monday to Friday do

    Case i of

      Monday: Writeln(‘физика‘, ’информатика‘, ’история’);

     Tuesday, Friday: Writeln(‘мат. анализ‘,’педагогика‘, ‘английский’);

     Wednesday, Thursday: Writeln(‘физика ‘,’алгебра‘,’информатика’)

   end

End.

4.Сложные (составные) типы.

В языке Pascal реализован механизм определения сложных (составных) типов данных. Новый тип данных определяется как структурированная совокупность данных-компонент стандартных или ранее определенных типов. Поскольку типы компонент могут также составными, можно строить сложные иерархии типов. Методы стуктурирования данных в языке позволяют строить массивы, записи, множества и файлы. Эти методы называют статическими, поскольку их описание осуществляется предварительно. Более сложные структуры можно создавать динамически - в процессе выполнения программы - с помощью ссылок.  При изучении сложных типов основное внимание уделяется способам конструирования данного и способам доступа к компонентам данного.

5.Регулярный тип. Массивы.

Значениями регулярного типа являются массивы. Массив - это наиболее распространенная структура данных. Во многих языках программирования (Fortran, Algol-60, Basic) это единственный явно определенный сложный тип.

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

<имя типа> = Array [< тип индекса>] of <тип компоненты>;

Регулярный 

тип

Примеры:

а) Type LinearTable = Array [0..100] of Integer;

б) type Word = Array [1..20] of Letter;

Letter = ‘a’..’z’;

Order = Array [Letter] of Integer;

в) type Matrix = array [1..N] of array [1..M] of Real;

В примере в) M и N - константы целого типа. Обратите внимание на то, что значения типа Matrix - M*N матрицы - определяются как массивы, компонентами которых, в свою очередь, являются массивы из вещественных чисел.

Регулярный тип, значениями которого являются многомерные массивы (например, в) и г)), можно определять в сокращенном виде:

Type <имя> = Array [<Tип> {,<Tип>} ] of <тип компоненты>;

Например:

а) Type matrica = array [1..N,1..M] of real; б) Type Index1 = -10..10;

Index2 = 0..20;

Index3 = 0..3;

Tenzor = Array [Index1, Index2, Index3] of Real;

в) Type Labyrinth = array [1..100,1..100] of Boolean;

Типы Real и Integer не могут быть типами индексов!

Компонента переменной регулярного типа - компонента массива явно обозначается именем переменной, за которым в квадратных скобках следуют индексы; индексы являются выражениями типа индекса. Например, Table[1, i+j ], T[2*i+1, (j*j) mod i], S[Monday, Friday]. Обратите внимание на то, что в отличие от индексных выражений, границы индексов в переменных - массивах должны быть константами. Значения индексных выражений должны быть значениями типа индекса, т.е. находиться в пределах, определенных границами индексов.

Рассмотрим примеры:

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

Program ScalarMult;

 Const n = 10;

  Type Vector = array[1..n] of Real;

   Var V : Vector;   Summa : Real;   i : Integer;

 Begin

   For i := 1 to n do begin { блок чтения исходного вектора }

    Write(‘Ведите координату вектора : ‘);  Readln(V[i]);

   end;

   Summa := 0; { блок вычислений }

   For i := 1 to n do

    Summa := Summa + V[i]*V[n-i+1];

    write(‘ Результат : ‘, Summa)

  End.

Блок вычислений можно оптимизировать по времени. Заметим, что Summa вычисляется про формуле: Summa = V[1]*V[n] + V[2]*V[n-1] +...+ V[2]*V[n-1] + V[1]*V[n]. Следовательно, ее слагаемые, равноотстоящие от концов, равны. Поэтому количество повторений цикла можно уменьшить вдвое. При этом необходимо учитывать четность числа n:

{Program ScalarMult1;}

For i := 1 to n div 2 do   Summa := Summa + V[i]*V[n-i+1];

 If Odd(n)

  then Summa := 2*Summa

  else Summa := 2*(Summa + V[n div 2 + 1];

Пример 7. Программа разложения матрицы в сумму симметрической и кососимметрической матриц.

Обозначим через Mat, Sym, Assym соответственно исходную, симметрическую и кососимметрическую матрицы. Тогда   

Sym[i, j] = ( Mat[i, j] + Mat[j, i])/2

Assym[i, j] = ( Mat[i, j] - Mat[j, i])/2

Блоки ввода - вывода данных предлагаем читателю оформить самостоятельно. Используя уроки предыдущей программы, учтем свойства симметрии матриц Sym, Assym:

Sym[i, j] = Sym[j, i],  Assym[i, j] = - Assym[j, i];

Program MatrixSymmetry;

  Const n = 10;

   Type Msize = 1 .. n ;

          Matrix = Array [Msize, Msize] of Real;

     Var Mat, Sym, Assym : Matrix;

          i, j : Msize;

Begin

{блок чтения исходной матрицы}

For i := 1 to n do

  For j := 1 to i do

 { перебор всех элементов под главной диагональю }

  begin

  Sym[i, j] := (Mat[i, j] + Mat[j, i])/2;

  Assym[i, j] := (Mat[i, j] - Mat[j, i])/2;

  Sym[j, i] := Sym[i,j];  { симметрия }

  Assym[j, i] := -Assym[i, j]       {симметрия}

  end;

{блок распечатки полученных матриц}

End.

Еще один источник лишних действий - пересылки данных в массивы, сопровождающиеся вычислениями индексных выражений. Мы дважды обращаемся к Mat[i,j], Mat[j,i], Sym[i,j], Assym[i,j]. Введя несколько простых вспомогательных переменных, устраним этот недостаток:

{Program MatrixSymmetry1;}

{Var X, Y, U, V : Real;}

For i := 1 to n do

 For j := 1 to i do

 {перебор всех элементов под главной диагональю}

 begin { тело внутреннего цикла }

  X := Mat[i, j], Y := Mat[j, i];

  U := (X + Y)/2; V := U - X ;     {соотношение U + V = X}

  Sym[i, j] := U; Sym[j, i] := U;     {симметрия}

  Assym[i, j] := V; Assym[j, i] := -V {симметрия}

 end;

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

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

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

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

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

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

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

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

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

Рrogram MinItem;

 Const n = 23;

 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, Min}

 End.

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

7.Эффективность алгоритма по времени.

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

Программа                     Сложность                 Оценка сложности

ScalarMult       T(n) = Tb*n             T(n) =  O(n)

ScalarMult1                T(n) = Tb*n/2                  T(n) =  O(n)

MatrixSymmetry T(n) = Tb*n*(n + 1)/2      T(n) = O(n2)

MatrixSymmetry1       T(n) = Tb*n*(n + 1)/2    T(n) = O(n2)

MinElement                T(n) = Tb*n                     T(n) = O(n)

Здесь Tb - сложность тела (внутреннего) цикла. В реальных программах величина Tb зависит от многих факторов, связанных с аппаратурой, операционной системой и системой программирования. Поэтому качество алгоритма, реализованного в виде программы и не зависящее от внешних обстоятельств можно оценить функцией параметра задачи. При этом основное свойство функции оценки сложности - скорость ее роста. Для алгоритма ScalarMult эта функция растет линейно. Этот факт отражен формулой T(n) = O(n). Сложность алгоритма MatrixSymmetry оценивается квадратичной функцией. Поэтому T(n) = O(n2). (Точное определение записи О(n) дано в математическом анализе.)

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

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

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

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

Оператор имеет вид: Goto < метка >

Метка представляет собой целое число без знака, состоящее не более чем из 4 цифр. В разделе операторов каждая метка может встречаться только перед одним оператором. Каждая метка, встречающаяся в разделе операторов, должна быть описана в разделе меток.

Раздел меток определен следующей диаграммой:

Раздел меток

                     

После метки, отмечающей оператор, следует ставить двоеточие. Например:

1995 : х := х +I; 1 : read(Y);

Внимание! Действие оператора перехода внутрь сложного оператора извне не определено.

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

В качестве единственного примера программы с Goto рассмотрим задачу поиска элемента в одномерном массиве.

Пример 9.

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; goto1

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

   1:If Flag

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

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

  End.

Изящное решение этой задачи без применения Goto будет рассмотрено ниже.

9.Постановка задачи сортировки.

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

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

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

Пусть нам дана последовательность элементов 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).

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

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

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

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

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

Пример 10.

Program BublSort;

  Const n = 100;

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

         i, j : Integer;

        TempMem : Real;

 Begin

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

  For i := n - 1 downto 1 do

  For j := 1 to i do

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

    then begin

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

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

 End.

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

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

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

Поскольку алгоритм сортирует массив “на месте”, его сложность по памяти - константа.

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

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

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

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

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

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

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

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

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

  a[i+1] a[i+2]  ... a[n]      (3)

После завершения внешнего цикла получим:

  a[1]  a[2], a[2]  a[3]  ...  a[n]    (4)

т.е массив отсортирован.

Заметим, что более подробное обоснование заключается в прежде всего в доказательстве соотношений (1), (3). Это можно сделать методом математической индукции.

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

Внешний цикл выполнился 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 = O(n2)

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

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

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

Пример 11.

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

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, MinIndex : Integer;

        TempMem : Real;

 Begin

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

  For i := 1 to n - 1 do  begin

   { поиск минимального элемента }

    MinIndex := i;

    for j := i + 1 to n do

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

    {перестановка элементов}

    TempMem := a[MinIndex]; a[MinIndex] := a[i]; a[i] := TempMem

   end;

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

End.

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

Внутренний цикл осуществляет поиск минимального элемента. После выполнения оператора If имеет место соотношение  Min = Min(a[i], a[i+1], ... , a[j]), а после завершения цикла Min = Min(a[i], a[i+1], ... , a[n]). После перестановки имеем  a[i] = Min(a[i], a[i+1], ... , a[n]).

Внешний цикл управляет длиной просматриваемой части массива. После выполнения тела внешнего цикла начало массива уже отсортировано:  a[1]  a[2]  ...  a[i]

После завершения внешнего цикла получим:

a[1] a[2] ... a[n-1],   a[n-1] = Min(a[n-1], a[n]), т.е массив отсортирован.

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

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

Перестановка элементов осуществляется во внешнем цикле. Поэтому

M(n) = 3(n - 1)

Также, как и алгоритм сортировки обменами, анализируемый алгоритм устойчив. В самом деле, блок поиска минимального элемента в хвосте массива ищет минимальный элемент с наименьшим индексом, поэтому перестановки будут устойчивыми.  Можно сделать вывод, что простая сортировка выбором эффективней сортировки простыми обменами по критерию M(n). Если сортируемая последовательность состоит из данных большого размера, этот критерий может иметь решающее значение.

10.Задачи и упражнения

I.Составить программу табулирования функции z = f(x, y) в прямоугольнике [a, b]*[c, d] с шагом табуляции h и точностью 

Функция z = f(x,y)

[a, b]

[c, d]

h

1

z = ln(1 + x2  + y2)

[ -2, 3 ]

[ -1, 3 ]

0.1

10-5

2

z = sin2(2x+y)

[ -, /2 ]

[ -2, ]

0.2

10-6

3

z = exp(x2+y2)

[ -2, 2 ]

[ -2, 2 ]

0.1

10-5

4

z = 1/(tg2(x+y)+1)

[ -/2, /2 ]

[ -, ]

0.2

10-4

5

z = ln(x+sqrt(x2+y2))

[ -2, 3 ]

[ -2, 3 ]

0.1

10-5

.

II.Составить программу решения задачи и оценить ее сложность:

1.Дан массив А[1..n]. Найти сумму всех элементов A, заключенных между A[1] и A[n].

2.Дан массив А[1..n]. Подсчитать средние арифметические всех отрицательных и всех положительных его элементов.

3.Последовательность из n точек плоскости задана массивами Х[1..n] и Y[1..n] координат. Найти точку, наименее удаленную от начала координат.

4.Дан массив А[1..n]. Найти все его элементы, меньшие, чем все предыдущие.

5.Дан массив A[1..n]. Найти в этом массиве наибольшую по количеству элементов возрастающую подпоследовательность подряд идущих элементов.

6.Дан массив A[1..n], состоящий из нечетного (n = 2k+1) числа попарно неравных элементов. Найти средний по величине элемент в массиве.

7.Даны массивы А[1..n] и В[1..m]. Найти все элементы массива A, не входящие в В.

8.Даны массивы А[1..n] и В[1..m]. Найти все элементы массива A, входящие в В.

9.Дан массив A[1..n]. Величину Sij определим следующим образом:

Sii = A[i],

Sij = A[i] + A[i+1] + ... + A[j] при i < j

Sij = Sji при i > j

Найти Max Sij при 1 i, j n

III.Составить программу решения задачи и оценить ее сложность:

1.Умножить матрицу А размера m x n на вектор b.

2.Перемножить матрицы А и А’. (A’ - A транспонированная)

3.Перемножить матрицы А и B.

4.Дан массив А[1..n, 1..m]. Найти седловую точку массива или установить ее отсутствие. (Элемент двумерного массива называется седловой точкой, если он максимален в своем столбце и минимален в своей строке.)

5.Дан массив А[1..n, 1..m]. Найти столбец, сумма квадратов элементов которого минимальна.

6.Дан массив А[1..n, 1..m]. Найти все элементы А меньшие, чем все соседние. (Соседними называются элементы, индексы которых отличаются на 1).


 

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

22230. Возникновение советского государства и права 18.27 KB
  Иогп Лекция 1 Возникновение советского госва и права 1. возникновение госва 3. Политика очень важна для госва.Конечно в условиях мирного времени регулятором обществ жизни был рынок но вместо ее надо образовать государственный контроль.
22231. Анализ требований к отбору S блоков разработчиков стандарта 291 KB
  Введение в дифференциальный криптанализ Анализ требований к отбору S блоков разработчиков стандарта. Построение произвольной двухблочной характеристики обозначает левый полублок в скобках приводится вариант активизации на промежуточном цикле S блоков S7 и S8. Для того чтобы уйти от однобитного перехода на втором цикле можно взять левый полублок с битами попадающими на те же входы S блоков S блоки S5 и S6 что и использованные ранее входы  18 и 23 биты должна сохраниться идея активизации на каждом цикле не более двух S блоков. Для...
22232. Дифференциальны криптоанализ полного 16-циклового DES 279 KB
  Любая пара плайнтекстов дающая повышение промежуточных характерных XOR значений названа правильной парой. Предполагаемое изменение XOR соответствующих значений в течении шифрования правильной пары плайнтекстов в новой версии 16цикловой атаки проиллюстрировано на Рис.2 которое включает 15цикловую атаку в циклах со 2 до 16 с предшествующим новым 1ым циклом Наша цель сгенерировать без потери вероятности пары плайнтекстов чьи XOR выходы после первого цикла являются требуемыми XOR входов в 13цикловой характеристике в циклах со 2го по...
22233. Дифференциальный криптоанализ DES Атака на полный 16-цикловый DES со сложностью 219 551.5 KB
  В таблице 1 представлен фрагмент таблицы разностей для второго S блока Таблица 1 Входной Выходной XOR XOR 0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx 4x 0 0 0 0 0 6 0 14 0 6 10 4 10 6 4 4 8x 0 0 0 4 0 4 0 8 0 10 16 6 6 0 6 4 Рассмотрим ситуацию когда на входе второго S блока одной 16цикловой характеристики имеется входная разность 4x а на входе второго S блока другой 16цикловой характеристики имеется входная разность 8x. Убедимся прежде всего что и в этом случае используя известные входные пары и выходные XORы для пары S блоков...
22234. Криптографическая система 256 KB
  Замыслом который стал определяющим при формировании настоящей программы Вашей подготовки стала задача ознакомления Вас с двумя наиболее сложными в теоретическом да и практическом отношении криптоаналитическими атаками позволившими в свое время найти слабости в широко известном и все еще применяемом до настоящего времени стандарте симметричного блочного шифрования США алгоритме DES. Поэтому хотя сегодня уже шифр DES можно считать уходящим со сцены представляется целесообразным изучение принципов выполнения указанных выше...
22235. Дифференциальный криптанализ 528 KB
  Для DESподобных криптосистем различие выбирается как побитовая сумма по модулю два XOR значений двух текстов в модульной арифметике  разность пары текстов. Эта операция в дальнейшем для краткости будет обозначаться аббревиатурой из английских букв  XOR2. Данное фиксированное значение XOR входной пары правых полу блоков для F функции легко определяет свое XOR значение после расширения по формуле: EXEX = EXX. XOR с ключом не изменяет значение XOR в паре т.
22236. Введение в дифференциальный криптанализ 741 KB
  Будем говорить что X может вызвать Y с вероятностью p для F функции если p есть доля всех возможных входных пар зашифрованных всеми возможными значениями подключа в которых входной XOR F функции равен X а выходной XOR равен Y. Если в DES X  Y X переходит в Y с вероятностью p для F функции то каждая фиксированная входная пара Z Z с Z = ZZ= X образует выходной XOR F функции равный Y с той же самой долей p возможных значений подключа. Очевидно что для каждого входного XOR имеем = независимо от ключа KS. Если имеется k входных пар...
22237. Введение в дифференциальный криптанализ. Итеративные характеристики 401.5 KB
  Статистическое поведение большинства характеристик не позволяет нам искать пересечение всех ключей предложенных поддерживаемых различными парами как это мы делали в примере 6 Л2 так как пересечение обычно пустое: неправильные пары не обязательно указывают на правильный ключ как возможное значение. Однако мы знаем что правильное ключевое значение должно быть результатом всех правильных пар которые встречаются приблизительно с характеристической вероятностью с вероятностью характеристики. Все другие возможные ключевые значения...
22238. Атака на DES уменьшенный до восьми циклов 414 KB
  Введение в дифференциальный криптанализ 1 Атака на DES уменьшенный до восьми циклов Чтобы найти другие биты Эли Бихам и Ади Шамир фильтруют все пары и оставляют только те которые имеют ожидаемое значение используя при этом известные значения h и значения ключевых битов K8 входящих в S6 S7 и S8. Ожидаемое число остающихся пар есть 53. Они применяют аналогичный метод счета используя увеличенное отношение S N созданное большой концентрацией правильных пар и затем снова фильтруют пары. Неправильная пара не отвергается этим или...