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).


 

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

38848. ДИПЛОМНОЕ ПРОЕКТИРОВАНИЕ 231.5 KB
  Оно проводится в целях выполнения квалификационной работы проекта соответствующей государственным требованиям к уровню подготовки инженера систематизации и закрепления знаний по образовательнопрофессиональной программе совершенствования умений их применения для решения задач в области мостостроения. Следует иметь в виду что основную ответственность за правильность принятых в проекте технических решений и всех данных несёт студент автор дипломного проекта. Темы дипломных проектов как правило соответствуют одному из направлений:...
38849. Курсовые и дипломные работы по теории обучения иностранным языкам: практические рекомендации для студентов вузов 592 KB
  Романовская Курсовые и дипломные работы по теории обучения иностранным языкам: практические рекомендации для студентов вузов Учебнометодическое пособие по теории обучения иностранным языкам Ульяновск 2008 ББК 81. Курсовые и дипломные работы по теории и методике обучения иностранным языкам: практические рекомендации для студентов вузов : учеб. Даются рекомендации по поиску и изучению литературы написанию теоретической части планированию и проведению эмпирического исследования подготовке и проведению защиты дипломной работы. Для студентов...
38850. Эстетическое воспитание подростков на занятиях по художественному текстилю на примере серии работ «Флора» в технике холодный батик 1.24 MB
  ИСТОРИКОКУЛЬТУРОЛОГИЧЕСКИЙ АСПЕКТ СТАНОВЛЕНИЯ И РАЗВИТИЯ ХУДОЖЕСТВЕННОЙ РОСПИСИ ТКАНИ И ЕЁ ТРАНСФОРМАЦИЯ В СОВРЕМЕННОМ ТВОРЧЕСТВЕ. История возникновения и развития художественной росписи ткани в странах Азии и Европы10 Исторические аспекты развития художественной росписи ткани России20 1.3 Роль художественной росписи ткани в современном декоративно прикладном искусстве в контексте моды как культурного феномена и ее связи с современным искусством росписи...
38851. Обучающая подсистема для лабораторного исследования характеристик замкнутых САУ в среде интернет 4.57 MB
  В данном дипломном проекте рассматривается обучающая подсистема для лабораторного исследования характеристик замкнутых САУ в среде интернет. В экономической части дается техникоэкономическое обоснование разработки Обучающей подсистемы для лабораторного исследования характеристик замкнутых САУ в среде интернет с помощью частотных критериев устойчивости проводится расчет ее сметной стоимости и стоимости эксплуатации Содержание.1 Описание предметной области по характеристикам замкнутых САУ.
38852. Фотокаталітичне очищення стічних вод від біогенних елементів 5.96 MB
  Представлено та описано технологічну схему очищення стічних вод від біогенних елементів фотокаталітичною технологією за допомогою солей Ti(IV) та Zr(IV). Виконано розрахунок і вибір основного та допоміжного обладнання у відповідності з задоною продуктивністю установки. Надано його характеристику.
38854. Створення та редагування таблиць у текстовому редакторі Word 327.5 KB
  Поняття таблиць Word Таблиці дуже часто зустрічаються в діловій кореспонденції однак існує деяка думка що створювати і редагувати таблиці в текстових процесорах украй складно. Word дозволяє вставляти таблиці з текстовою і графічною інформацією будьякого. Приклад таблиці До того як у Word зявилася можливість створювати таблиці користувачі робили це за допомогою табуляції чи абзацних відступів. Звичайно таблиці можна створювати таким чином але це досить незручно.
38855. Забезпечення стабільного функціонування ОЕС України в умовах недостатності маневрових потужностей 4.98 MB
  Вибір засобів обмеження перенапруг та високочастотних загороджувачів Для захисту обладнання від атмосферних та комутаційних перенапруг встановлюємо розрядники та обмежувачі перенапруг: ЛЕП330 кВ сторона ВН БТ ОПН330У1 сторона НН БТ РВМ15У1 сторона НН АТВП РВРД10У1 Для забезпечення нормальної роботи зв’язку та приладів РЗА встановлюємо на ЛЕП високочастотні загороджувачі [5]: 330кВ ВЗ125005У1 2.14 Розрахунок грозозахисту ВРУ330 кВ Вихідні дані для розрахунку: висота блискавковідводу: h=40м; розрахункова...