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

;


 

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

31496. Комп’ютерна графіка. Основні поняття комп'ютерної графіки 146.89 KB
  Річ у тому що будьяке цифрове зображення на комп'ютері характеризуються набором його таких параметрів як розмір дозвіл формат і тип колірної моделі. Перераховані параметри і визначають якість растрового зображення а також розмір графічного файлу. Дозвіл зображення Растрове зображення формується з сукупності крихітних елементів званих пікселями. Якщо вдуматися то стає очевидним що чим вище дозвіл тим більшу кількість пікселів містить зображення і тим більшою кількістю деталей тобто якістю таке зображення характеризується.
31497. Інтерфейс Photoshop CS5 577.95 KB
  Інтерфейс елементи головного вікна графічного редактора При запуску dobe Photoshop ми побачимо головне вікно програми показане на мал. Мал. Інтерфейс dobe Photoshop Панель управління і головне меню У верхній частині вікна Photoshop знаходиться головне меню що містить практично всі команди для налаштування і здійснення процесу редагування зображення а також панель управління яка також призначена для налаштування і запуску безлічі функціональних можливостей програми мал. Мал.
31498. ФОНДОВИЙ РИНОК 142 KB
  Загальна характеристика фондового ринку Фондовий ринок ринок цінних паперів сукупність учасників фондового ринку та правовідносин між ними щодо розміщення обігу та обліку цінних паперів і похідних деривативів. В економічній літературі терміни фондовий ринок і ринок цінних паперів стали майже синонімами. Основними інструментами фондового ринку є цінні папери різних видів типів які формують свої сегменти: грошового ринку ринку цінних паперів ринку капіталів фондового ринку. Сучасний світовий фондовий ринок розвивається за...
31499. Фондова біржа та біржові операції 231.5 KB
  Сутність фондової біржі її види та функції Фондові біржі це спеціалізовані установи які створюють умови для постійно діючої централізованої торгівлі цінними паперами шляхом обєднання попиту пропозицій на них надання місця системи і засобів як для первинного розміщення так і для вторинного обігу цінних паперів. Вони мають працювати за єдиними правилами та за єдиною технологією електронного обігу цінних паперів визначеними Національною фондовою біржею. Виділяють декілька етапів розвитку й удосконалення фондових бірж: зміна способів...
31500. Фінансовий ринок: сутність, функції та роль в економіці країни 153 KB
  Фінансовий ринок: сутність функції та роль в економіці країни Сутність фінансового ринку необхідність і передумови його створення. Принципи та функції фінансового ринку. Структура фінансового ринку. Сутність фінансового ринку необхідність і передумови його створення Фінансовий ринок є складовою сферою фінансової системи держави.
31501. Регулювання фінансового ринку 119 KB
  Регулювання фінансового ринку Сутність принципи та напрями регулювання фінансового ринку. Рівні та форми регулювання фінансового ринку. Державне регулювання фінансового ринку України. Внутрішнє регулювання фінансового ринку.
31502. РИЗИК І ЦІНА КАПІТАЛУ 194.5 KB
  Розвиток теорій ризику. Формула Фішера що в літературі має назву ефект Фішера виглядає таким чином: Ri=RfIP де Ri ціна капіталу з урахуванням ризику процентна ставка в умовах інфляції; Rf номінальна ставка; IP інфляційна премія рівень інфляції. На вторинному ринку оцінювання фінансових активів здійснюється за допомогою їх переоцінки коригування ринкової ціни так щоб фінансовий актив певного рівня ризику забезпечував відповідний рівень доходу. Особливістю фінансового ризику є ймовірність зазнати збитків у результаті проведення...
31503. РИНОК КАПІТАЛІВ 110.5 KB
  РИНОК КАПІТАЛІВ Основи організації ринку капіталів. Кредитний ринок як складова ринку капіталів. Основи організації ринку капіталів Ринок капіталів це частина фінансового ринку де формується попит і пропозиція на середньостроковий та довгостроковий позиковий капітал. Економічна роль ринку капіталів полягає в його спроможності об'єднати дрібні розрізнені кошти і на основі цього активно впливати на концентрацію і централізацію виробництва та капіталу.
31504. Грошовий ринок 156.5 KB
  Грошовий ринок Сутність та особливості функціонування грошового ринку. Структура грошового ринку та його інструменти. Міжбанківський ринок та операції що здійснюються на міжбанківському ринку. Сутність та особливості функціонування грошового ринку Грошовий ринок у ринковій економіці це система грошових відносин на фінансовому ринку яку формують банківські та спеціальні фінансовокредитні інститути що забезпечують функціонування грошових ресурсів країни їх постійне переміщення під впливом законів попиту та пропозиції.