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

;


 

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

43002. Динамический и силовой анализ механизма 99.5 KB
  Динамический анализ механизма включает в себя определение движущего момента такого, чтобы звенья механизма двигались с заданными скоростями при заданных нагрузках и массах действующих на механизм. Формула для определения движущего момента
43003. Расчет заготовки коробчатой формы 364.5 KB
  Основной критерий оборудования − это номинальное усилие пресса. 1 операция Вырубка заготовки При вырубке круглой заготовки необходимо учитывать следующие усилия: Pвыр− усилие затрачиваемое на вырубку заготовки пуансоном; Рпрот− усилие затрачиваемое на проталкивание заготовки пуансоном через отверстие в матрице; Ртр− усилие затрачиваемое на трение отхода о пуансон. Усилие операции: Pоп = Pвыр Рпрот Ртр. Усилие вырубки заготовки: k=1113 коэффициент учитывающий притупление режущих кромок неравномерность зазора...
43004. Создание проектной базы для внедрения в отечественную строительную практику комплектной системы KNAUF, обеспечивающей "сухой" (без использования мокрых процессов) способ высококачественной отделки помещений 2.22 MB
  Сборные гипсокартонные перегородки системы KNUF применяются как внутренние ограждающие конструкции помещений с сухим нормальным и влажным режимом см. Перегородки и узлы разработанные в настоящей серии предназначены для применения в жилых общественных и производственных зданиях: любых конструктивных систем и типов; любого уровня ответственности включая повышенный; любой степени огнестойкости включая Iую степень; различной этажности с высотой зданий не более 60 м; возводимых в ветровых районах до Vго включительно;...
43005. Проектування промислового будинку, район будівництва, м.Кременчук 183.5 KB
  Опис планувальнопросторового рішення будинку. Вихідні дані Для проектування промислового будинку в завданні зазначається: район будівництва м. Перший етап: вивчення завдання методичних вказівок літератури розробка варіантів їх обємнопланувальних рішень розрахунок адміністративнопобутових приміщень вибір конструкцій виробничого цеху розробка ескізних рішень промислового будинку які затверджуються викладачем. Маркувальний план виробничого будинку.
43006. Технологическая карта на многоэтажное каркасное здание 435 KB
  Для правильного и эффективного решения всех вопросов, касающихся технологии производства монолитных и монтажных работ, выполнен оптимальный выбор методов и способов производства работ: метод производства монолитных работ - раздельный, направление развития процесса - по горизонтали вдоль здания. Здание условно поделено на две захватки, гранича которых проходит через ось 7. Монтаж стеновых панелей производится параллельно с возведение каркаса здания, с отставанием на одну захватку.
43007. Разработка направления и совершенствования логистической деятельности и процесса транспортировки в фокусном звене цепи поставок 1.02 MB
  Возникает необходимость регулирования всей системы движения товаров при этом эффективность цепи поставок определяется уровнем организационного оформления хозяйственных связей всех участников товародвижения. Изучается транспортировка в цепи поставок с целью ознакомления с логистическими особенностями отдельных видов транспорта зависимостью логистических издержек в цепи поставок от параметров транспортировки способами обоснования оптимальных схем доставки грузов методами рациональной организации перевозок основными путями повышения уровня...
43008. Организация и обслуживание банкета по поводу международного женского дня 8 марта на 50 человек 772.5 KB
  В настоящее время ресторанное хозяйство развивается по различным направлениям. Появляется большое количество ресторанов с национальной кухней, появляются новые виды предприятий ресторанного хозяйства (пабы, суши-бары), в наши дни предприятия ресторанного хозяйства оснащаются автоматизированными системами ведения счетов, появляются новые профессии (сомелье, хостесс) и, в конце концов, современное предприятие ресторанного хозяйства становится местом красивого, приятного времяпрепровождения.
43010. Расчет УНЧ на БПТ 221 KB
  Принципиальная схема каскада. Составив блоксхему усилителя выбирают принципиальные схемы входного и выходного устройств реостатноемкостные трансформаторные каскада мощного усилителя одноактный двухтактный трансформаторный бестрансформаторный каскадов предварительного усиления с прямой связью реостатный трансформаторный инверсный и т. После чего составляют принципиальную ориентировочную схему усилителя и распределяют заданные частотные искажения по цепям и каскадам вносящим эти искажения. Расчет усилителя производят начиная...