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

;


 

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

49218. Проектирование транзисторных широкодиапазонных передатчиков 348.55 KB
  Задачей курсового расчета является проектирование транзисторного широкодиапазонного радиопередающего устройства обеспечивающего формирование радиосигналов заданном рабочем диапазоне частот и заданную мощность выделяемую на нагрузке в состав которого входят следующие каскады: ОКГ опорный кварцевый генератор являющийся источником высокостабильных колебаний необходимо произвести расчет принципиальной схемы автогенератора с кварцевым резонатором в цепи обратной связи; ССЧ синтезатор сетки частот формирующий из опорной частоты...
49219. Комплексное исследование системы мотивации производственного персонала в Восточно-Сибирской Региональной Дирекции железнодорожных вокзалов, вокзал станции Черемхово 147.36 KB
  Разработка и практическое применение новых мотивационных систем непосредственно на самих предприятиях позволяют привлекать новых высококвалифицированных специалистов, способных на деле управлять как малыми, так и большими коллективами, ориентируясь преимущественно при этом на индивидуальное мотивирование в соответствии с количеством и качеством труда, затраченного индивидом.
49220. Разработать микропроцессорную систему и цифровое устройство управления подачей добавок в ДСП 637.56 KB
  Задание на курсовую работу: Разработать микропроцессорную систему управления подачей добавок в ДСП. Разработать цифровое устройство управления подачей добавок в ДСП. В настоящее время имеется достаточно большое количество вариантов оснащения ДСП различными устройства подачей добавок. При этом стоит задача управления отдельными локальными потоками подачи в печь добавок.
49221. Исследование фильтрационного потока от нагнетательной скважины к эксплуатационной и исследование нерадиального установившегося движения жидкости и газов к одной скважине 279.55 KB
  ВЫЯСНЕНИЕ ВЛИЯНИЯ ФОРМЫ КОНТУРА ОБЛАСТИ ПИТАНИЯ НА ДЕБИТ СКВАЖИНЫ И РАСПРЕДЕЛЕНИЕ ДАВЛЕНИЯ В ПЛАСТЕ ИССЛЕДОВАНИЕ ФИЛЬТРАЦИОННОГО ПОТОКА ОТ НАГНЕТАТЕЛЬНОЙ СКВАЖИНЫ К ЭКСПЛУАТАЦИОННОЙ НЕРАДИАЛЬНОЕ ДВИЖЕНИЕ ЖИДКОСТИ К СКВАЖИНЕ ПРИ КРУГОВОМ КОНТУРЕ ОБЛАСТИ...
49222. Разработка устройства для сигнализации давления в 6-ти точках 159.63 KB
  Идентифицировать номер датчика и сигнал01. Начало =6;B=1 Опрос датчика Вывод в порт № датчика K=0 да нет Вывод в порт Вывод в порт B=B1 B=B1 B B нет нет да да Конец Разработать устройство для сигнализации давления в 6ти точках. Идентифицировать номер датчика и сигнал01. Реализация программы управления на языке SSEMBLER MVI D 6 Колво датчиков = 6 MVI B 1 № первого датчика For IN1 Проводим опрос OUT 2 Подаем значение в порт0 или1 MOV B Выводим номер датчика OUT 3 Выводим этот номер в порт INR B 1 CMP D Сравнение с пред...
49223. Разработка системы программно-аппаратной защиты автоматизированной системы предприятия от несанкционированного доступа 750 KB
  В данном курсовом проекте рассматривается разработка системы программно-аппаратной защиты автоматизированной системы учреждения администрации края. Это обязанность службы информационной безопасности, которая и рассмотрена в данной курсовой работе
49224. Оценка роли руководителя на примере ООО “Азия-Трак” 177 KB
  Суть обязанностей руководителя состоит в организации работы подчиненных. Это особый вид творческой деятельности, причем по мере роста сложности объекта управления и занимаемой должности, требования к творчеству увеличиваются.
49225. Виды порчи продукции и способы борьбы с ней 169.36 KB
  Вместе с тем она представляя сложный биоценоз в котором могут преобладать отдельные виды и группы микроорганизмов играет свою роль и посвоему влияет на качество пищевых продуктов. Гигиенические требования к качеству и безопасности продовольственного сырья и пищевых продуктов имеют особое значение для общества заботящегося о своих гражданах.1Порча пищевых продуктов в процессе хранения 1. устанавливающие основные требования к системе управления качеством и безопасностью пищевых продуктов на основе HCCP а также отдельные стандарты по...
49226. Разработка импульсного следящего радиодальномера 607.13 KB
  Краткие теоретические сведения о методах измерения дальности. Структурная схема канала дальности с цифровым импульсным радиодальномером. В данной курсовой работе необходимо разработать импульсный следящий радиодальномер РД цифрового Ц или аналогового А прототипа входящий в канал дальности моноимпульсного радиолокатора РЛ тактического самолета. Этот РЛ кроме измерения дальности цели должен в процессе автоматического сопровождения цели определять ее угловые координаты и радиальную скорость.