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

;


 

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

26040. Общая структура триггеров 13.24 KB
  Информационные сигналы поступают на входы A и В ЛУ и преобразуются в сигналы поступающие на внутренние входы S и R ЯП. Управляющие сигналы на асинхронный триггер воздействуют непосредственно с началом своего появления на их входах а в синхронных только с приходом сигнала на входе C.
26041. Простые триггеры 20.11 KB
  Схема простейшего триггера построенного на инверторах В этой схеме может быть только два состояния на выходе Q присутствует логическая единица и на выходе Q присутствует логический ноль. Если логическая единица присутствует на выходе Q то на инверсном выходе будет присутствовать логический ноль который после очередного инвертирования подтверждает уровень логической единицы на выходе Q. И наоборот если на выходе Q присутствует логический ноль то на инверсном выходе будет присутствовать логическая единица.
26042. JK-триггеры 14.14 KB
  Подобно RSтриггеру в JKтриггере входы J и K это входы установки выхода Q триггера в состояние 1 или 0. Однако в отличие от RSтриггера в JKтриггере наличие J=K=1 приводит к переходу выхода Q триггера в противоположное состояние. Условие функционирования JKтриггера описывается функцией: Рисунок 51 JKтриггеры: а асинхронные; б тактируемые фронтом. Триггер JKтипа называют универсальным потому что на его основе с помощью несложных коммутационных преобразований можно получить RS и Ттриггеры а если между входами J и K включить...
26043. D-триггеры 13.79 KB
  Характеристическое уравнение триггера: Qn1=Dn. Оно означает что логический сигнал Qn1 повторяет значение сигнала установленное на входе триггера в предшествующий момент времени. Благодаря включению элемента D1 на входы RSтриггера поступают разнополярные сигналы Рисунок 47а поэтому запрещённое состояние входных сигналов исключено но время задержки распространения сигнала элемента D1 должно быть меньше чем у элементов D2 и D3 tзд. В приведённой выше схеме Dтриггера вследствие задержки распространения сигналов сигнал на выходе Q...
26044. Счётные триггеры 18.55 KB
  Функционирование триггера определяется уравнением: Из уравнения следует что Ттриггер каждый раз изменяет своё состояние на противоположное с приходом на счётный вход Т очередного тактирующего импульса длительностью tи. Этому способствует наличие перекрёстных обратных связей с выходов триггера на входы элементов D1 и D2. Для надёжной работы триггера с целью сохранения информации о предыдущем состоянии триггера в момент его переключения в схему вводят элементы задержки имеющие время задержки tз tи. Сигнал на этом входе разрешает при V=1...
26045. Сумматоры, их схемы 98.69 KB
  Сумматоры их схемы В цифровой вычислительной технике используются одноразрядные суммирующие схемы с двумя и тремя входами причём первые называются полусумматорами а вторые полными одноразрядными сумматорами. приведена таблица истинности полусумматора на основании которой составлена его структурная формула в виде СДНФ Основными параметрами характеризующими качественные показатели логических схем являются быстродействие и количество элементов определяющее сложность схемы. Быстродействие определяется суммарным временем задержки сигнала...
26046. Программированные логические матрицы(ПЛЦ) 14.64 KB
  Программированные логические матрицыПЛЦ Основная идея работы ПЛМ заключается в реализации логической функции представленной в СДНФ дизъюнктивной нормальной форме. В схеме ПЛМ приведенной на рисунке 1 ранг терма ограничен количеством входов и равен четырем количество термов тоже равно четырем. В реально выпускавшихся микросхемах программируемых логических матриц ПЛМ количество входов было равно шестнадцати максимальный ранг минтерма 16 количество термов равно 32 и количество выходов микросхемы 8. Следует отметить что полная...
26047. Большие интегральные схемы(БИС) запоминающихся устройств(ЗУ). Организация БИС ЗУ 15.67 KB
  Большие интегральные схемы БИС запоминающихся устройств ЗУ. Организация БИС ЗУ Большая интегральная схема БИС интегральная схема ИС с высокой степенью интеграции число элементов в ней достигает 10000 используется в электронной аппаратуре как функционально законченный узел устройств вычислительной техники автоматики измерительной техники и др. По количеству элементов все интегральные схемы условно делят на следующие категории...
26048. Двоичные счётчики 15.41 KB
  Двоичные счётчики Счетчик представляет собой устройство состояние которого определяется числом поступивших на его вход импульсов. Счетчики используют для подсчета числа импульсов и фиксации этого числа в заданном коде деления частоты следования импульсов формирования последовательностей импульсов и кодов управления цифровыми блоками. Двоичный n разрядный счетчик содержит n каскадносоединенных ячеек в качестве которых используют счетные Ттриггеры При поступлении входных импульсов по их спаду происходит последовательное изменение...