4776

Итерационные циклы в программировании

Реферат

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

Итерационные циклы. Операторы повторения While и Repeat. Алгоритмы поиска и сортировки. Линейный поиск в массиве. Улучшенный алгоритм сортировки обменами. Бинарный поиск в упорядоченном массиве. Алгоритмы сортировки массивов (продолжение). Сортировк...

Русский

2012-11-26

77 KB

11 чел.

Итерационные циклы.

Операторы повторения While и Repeat.

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

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

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

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

Алгоритмы сортировки массивов (продолжение). Сортировка вставками.

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

1.Операторы повторения While и Repeat.

В предыдущем параграфе мы изучили оператор повторения с параметром (For).

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

Оператор цикла с предусловием определен диаграммой:

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

с предусловием

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

Пример1: Найти наименьшее натуральное решение неравенства x3 + ax2 + bx + c > 0 с целыми коэффициентами.

Очевидный алгоритм поиска решения заключается в последовательном вычислении значений Y = x3 + ax2 + bx + c для x = 1, 2, 3, ... до тех пор, пока Y  0.

Program UneqvSolution;

  Var a, b, c : Integer;

 X : Integer;  Y : Real;

Begin

   Write(‘ введите коэффициенты a, b, c : ‘); Readln(a, b, c); 

     X := 1; Y := a + b + c + 1; { Инициализация цикла }

   While Y <= 0 do begin

     X := Succ(X); { Следующее значение X }

     Y := ((X + a)*X + b)*X + c { Следующее значение Y }

   end;

  Writeln(‘X = ‘, X, ‘ Y = ‘, Y )

End.

Для обоснования этого метода требуется единственное: убедиться в том, что цикл когда-нибудь завершится, т.е. что решение неравенства существует! Заметим, что

lim (x3 + ax2 + bx + c) = +

x -> +

Поэтому при некотором x0 x03 + ax02 + bx0 + c > 0 Положим x = |a| + |b| + |c|. Тогда x3 = (|a| + |b| + |c|)x2 > |a|x2 + |b|x + c Следовательно, x3 + ax2 + bx + c > x3 - (|a|x2 + |b|x + c) > 0 Поэтому количество повторений цикла не превосходит величины |a| + |b| + |c|, что дает возможность не только обосновать завершение, но и оценить сложность программы в худшем случае.

Оператор цикла с постусловием определен диаграммой:

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

с постусловием

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

Пример 2. Найти номер наименьшего числа Фибоначчи, делящегося на 10. Последовательность Фибоначчи { F(n) } определяется рекуррентно:

F(1) = F(2) = 1,  F(n+2) = F(n+1) + F(n)

Как и в предыдущем примере, вычисляем Fn для n = 3, 4, ...  до тех пор, пока не найдем элемент последовательности, делящийся на 10. Проблема обоснования метода остается преждней: существует ли искомый элемент?

Program Fibbonachy;

  Var Fib1, Fib2 : Integer;

          Index : Integer;  Buf : Integer;

   Begin

Fib1 := 1; Fib2 := 1; Index := 2; { Инициализация цикла }

Repeat

 Buf := Fib2;

 Fib2 := Fib2 + Fib1;   { Следующее число Фибоначчи }

 Fib1 := Buf;   { Предыдущее число Фибоначчи }

 Index := Succ(Index)   { Номер числа Фибоначчи }

 until Fib2 mod 10 = 0;

Writeln(‘Номер = ‘, Index, ‘ Число = ‘, Fib2)

End.

Циклы While и Repeat называют еще итерационными циклами, поскольку с их помощью легко реализовать различного рода итерационные вычисления (вычисления, в которых каждый следующий результат является уточнением предыдущего). Условие окончания цикла - достижения отклонения реэультата Yn от Yn-1 некоторой допустимой погрешности  :

|Yn - Yn-1| <  

Пример 3 : Вычислить с заданной точностью значение корня уравнения x = cos(x) на отрезке [0 ; 1] методом деления отрезка пополам .

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

Program TransEquation;

   Const a = 0; b = 1;

          Epsilon = 1e-5;

     Var u, v, Root : Real;

          Fu, Fr : Real;

   Begin

    u := a; v := b; { инициализация цикла }

    Fu := Cos(u) - u;

    Repeat

      Root := (u + v)/2 ; { средняя точка отрезка }

      Fr := Cos(Root) - Root;

       if Fu*Fr > 0 { выбор правой или левой половины }

        then begin u := Root; Fu := Fr end

        else v := Root

     until Abs(v - u) < Epsilon;

    writeln (‘ корень= ‘, Root, ‘ с точностью ‘,Epsilon)

   End.

Для того, чтобы найти количество N повторений в цикле, заметим, что на k-том шаге цикла выполнено неравенство | v - u | = (b - a)/2k. Поэтому при наименьшем k таком, что (b - a)/2k <  цикл завершится. Нетрудно вычислить N:

    N = [ log2(b - a)/ ]     (1)

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

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

2.Алгоритмы поиска и сортировки. Линейный поиск в массиве.

Пример 4. Рассмотрим красивое решение задачи поиска данного элемента в массиве, использующее цикл While. В самом деле, вместо использования цикла For c досрочным выходом при помощи Goto можно применить цикл While:

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.

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

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

Program BublSort1;

Const n = 100;

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

         i, j : Integer;

        TempMem : Real; isOrd : Boolean;

  Begin

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

   i := n - 1;

   Repeat

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

     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;

         isOrd := False { обнаружена “засортировка” }

        end;

      i := Pred(i)

     until isOrd;

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

  End.

Этот алгоритм можно еще улучшить, если каждый следующий проход начинать не с начала (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 проход. При этом осуществится максимально возможное число сравнений. Устранить асимметрию можно, чередуя проходы вперед и назад. Реализацию этой идеи, как и дальнейшие улучшения алгоритма простыми обменами, мы предоставляем читателю в качестве упражнения.

Все улучшения рассматриваемого метода относятся к эффективности в среднем. Ни одно из них не уменьшает оценки сложности С(n) в худшем случае. (Докажите это самостоятельно!)

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

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

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

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.

Нетрудно получить оценку числа С(n) сравнений метода, применив формулу (1) примера 3. Пусть М - количество повторений цикла. Тогда

М [log2 (n)]

Поскольку на каждом шаге осуществляется 2 сравнения, в худшем случае

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

Алгоритмы сортировки массивов (продолжение).Сортировка вставками.

Еще один простой алгоритм сортировки - сортировка вставками основан на следующей идее: предположим, что первые 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.

Оценим эффективность алгоритма. Поиск места элемента A[k+1] требует, как показано выше, O(log2 k ) сравнений. Поэтому в худшем случае количество сравнений С(n) есть

C(n) = O(log2 2 ) + ... + O(log2(n-1)) + O(log2 n) = O(n log2 n)

 Сдвиг хвоста на каждом шаге внешнего цикла в худшем случае требует k перестановок. Поэтому в худшем случае

M(n) = 1 + ... + (n-2) + (n-1) = n*(n-1)/2 = O(n2)

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

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

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

   

1. [(-1)n /(2n+1)] = /4

  n=0

   

2. [(-1)n/(2n)!] = cos 1

  n=0

   

3. [(-1)n/(2n+1)!] = sin 1

  n=0

Упражнение 2. Найти сумму членов функционального ряда с заданной погрешностью .

1.sin x = (-1)n(x2n+1)/(2n+1)!

          n=0

2.ln x = (-1)n*xn / n; x>1/2

          n=1

   

3.arctg x = (-1)n x2n+1/(2n+1); |x|<1

               n=0

Упражнение 3.Найти все трехзначные члены последовательности Fn, определенной рекуррентными соотношениями:

1.F0 = 1, F1 = 1,   Fn+2 = Fn+1 + Fn  при n > 0

2. F0 = 5, F1 = 1, F2 = 1,  Fn+3 = Fn+2 + Fn+1 - Fn  при n > 0

Упражнение 4.

1.Дано рациональное число p/q. Построить его разложение в цепную дробь.

2.Построить разложение натурального числа N в произведение степеней его простых делителей.

3.Перевести целое число N в p-ичную систему счисления. Обобщить алгоритм на случай p-ичной системы счисления.

4.Известно, что если d = НОД(a,b), то существуют такие числа u, v, что d = au + bv. По a, b найти d, u, v.

5.Число N называется совершенным, если оно совпадает с суммой своих собственных делителей. (Например, 6 = 1 + 2 + 3 ). Найти все совершенные числа, не превосходящие М.

6.Найти номер наименьшего числа Фибоначчи, заканчивающего-ся 2-мя нулями. Найти само это число.

Упражнение 5.

1.Дан массив A[1..n] действительных чисел. Найти в этом массиве наименьшее положительное число.

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

3.Дан массив A[1..n] целых чисел. Отрезок индексов k .. m называется отрезком роста массива, если A[k] < A[k+1] < ... < A[m]. Найти отрезок роста максимальной длины.

Задача 1. Массив A[1..n] состоит из данных типа Color = (white, black). Составить программу сортировки массива A, которая проверяет значение (цвет) каждого элемента только один раз.

Задача 2. Массив A[1..n] состоит из данных типа Color = (white, red, black). Составить программу сортировки массива A, которая проверяет значение (цвет) каждого элемента только один раз.

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

Задача 4.Даны упорядоченные массивы A[1..n] и B[1..m] целых чисел и целое число C. Составить программу поиска таких индексов i  и  j, что  C = A[i] + B[j],  сложность которой C(n) = O(log2(n m))

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

Задача 6.

а)Реализовать арифметический цикл с помощью цикла While;

б) Реализовать арифметический цикл с помощью цикла Repeat;

в) Реализовать цикл While с помощью цикла Repeat;

г) Реализовать цикл Repeat с помощью цикла While;

д) Реализовать цикл While с помощью операторов If и Goto;

е) Реализовать цикл Repeat с помощью операторов If и Goto;

PAGE  47


While

Условие

do

Оператор

Оператор

until

Условие

Repeat

;


 

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

26951. Функции и признаки права 6.87 KB
  функции и признаки права ПРАВОсистема нормправил поведениякоторые исходят от госва выражают волю и интересы определенных слоев населения или большинства общества сформулированы в специальных гос документахнормативных актах охраняются от нарушений силой общественного мнения и мерами госпринуждения. Нарушение требований права влечет наложение мер юридической ответственности этим обеспечивается общеобязательность норм права. Специальноюридические функции это правовое регулирование общественных отношений: 1 Регулятивная...
26952. Основные теории происхождения права 8.75 KB
  основные теории происхождения права ПРАВОсистема нормправил поведениякоторые исходят от госва выражают волю и интересы определенных слоев населения или большинства общества сформулированы в специальных гос документахнормативных актах охраняются от нарушений силой общественного мнения и мерами госпринуждения.правонеотчуждаемые правапринадлежащие человеку от рожденияисточник правачеловеческая природапоэтому зны должны подстраиваться под подлинное право.Источникправовой обычай.Все остальные правом не являются.
26953. Основные правовые семьи современности 8.72 KB
  Национальноправовые системы историческая совокупность праваюридической практики и господствующей правовой идеологии отдельной страныотражающая ее социальноэкономические политические и культурные особенности.Суды общей юрисдикции рассматривают дела всех категорийпоэтому отсутствует деление права на частное и публичноенет деления права по отраслямнет кодификации норм права.ИСТОЧНИК:нормативноправовой актакт правотворчествапринятый в особом порядке строго определенными субъектами и содержащий норму права.Существенную роль при...
26954. Правовое регулирование и правовое воздействие. 7.35 KB
  ТИП ПРАВОВОГО РЕГУЛИРОВАНИЯ определенный порядок регулирования выражающий общую направленность воздействия на общественные отношения которая зависит от соотношения дозволений и запретов в праве. В основе такого регулирования лежит общее дозволение а само регулирование осуществляется при помощи конкретных запретов. В основе такого регулирования лежит общий запрет а само регулирование осуществляется при помощи конкретных дозволений.
26956. Виды правонарушений 6.48 KB
  состав Правонарушениевиновное поведение праводееспособного индивидакоторе противоречит предписаниям норм правапричиняет вред другим лицам и влечет за собой юридическую ответственность. ДИСЦИПЛИНАРНЫЙправонарушениекоторое совершается в сфере служебных отношенийи нарушаетглавным образом порядок отношений подчиненности по службе. АДМИНИСТРАТИВНЫЙправонарушениепосягающее на установленный законом общественный порядокна отношения в области исполнительной и рапорядительной деятельности органов госване связанные с осуществлением служебных...
26957. Причины правонарушений, пути их преодоления 9.63 KB
  ТЕОРИЯ ПРИРОЖДЕННОГО ПРЕСТУПНИКА есть людиобладающие определенным набором признакова потому предрасположенные к совершению преступленийт.Баснословные цены на продукты питания и промышленные товары привели к небывалому росту таких преступленийкак кражииные хищения имуществаграбежиразбои.На приобретение наркотиков и алкогольных напитков постоянно требуются немалые суммы денегчто провоцирует лицих употребляющихна совершение таких преступленийкак кражиграбежи ит. ПРОФИЛАКТИКАспециально осуществляемая деятельность по учету и...
26958. Понятие, признаки и виды юридической ответственности 12.44 KB
  Понятиепризнаки и виды юридической ответственности.Характеризуется определенными ЛИШЕНИЯМИкоторые правонарушитель должен претерпетьобъективное свойство ответственности; 3.Условиями этой ответственности являются: противоправное поведение должника возникновение убытков кредитора наличие причинной связи между поведением должника и возникновением убытков у кредитора вина должника.Административной ответственности подлежит лицо достигшее к моменту совершения административного правонарушения 16 лет.