АЛГОРИТМЫ ТОИ-ИМ 3 базовые управляющие алгоритмические структуры Решение Цикл Последовательность Непосредственное выполнение одно- го действия за другим Действие A Действие B Действие C Проверка выполнения условия и выбор одного из альтернативных действий Организация повторяющихся действий в соответствии с заданным условием 1. Бинарный выбор - ветвление 2. Множественный выбор Условие Да Нет Условие Да 1 Действие 1 Да 2 ДаN Нет Действие 2 Действие N Действие Условие

Элементы ЯПВУ Операторы цикла Цикл while (с предусловием) Цикл: repeat-until – Pascal do-while – C (с постусловием) Цикл for (с параметром) Тело цикла выполняется n раз Тело цикла может не выполниться ни разу Тело цикла обязательно выполниться хотя бы один раз ТОИ-ИМ 2 Вход Тело цикла (оператор) Выход И - Pascal Л - C Л - Pascal И - C Условие Вход Тело цикла (оператор) Выход Ложно Истинно i = 1 (1) n Вход Тело цикла (оператор) Выход Л И Условие

Элементы ЯПВУ Цикл с параметром ТОИ-ИМ 3 Эта конструкция цикла используется в тех случаях, когда заранее известно точное количество повторов (итераций) цикла, требующееся для выполнения действия. В псевдокоде для описания цикла с параметром используется следующая конструкция: ДЛЯloop_index = initial_value ДО final_value Тело цикла ДЛЯ ВСЁ - loop_index – это переменная цикла – счётчик номера итерации (повтора) цикла, - initial_value – начальное значение переменной цикла, номер первой итерации, - final_value – конечное значение переменной цикла, номер последней итерации. Количество итераций цикла равно разности final_value и initial_value. Итерации цикла повторяются, пока параметр цикла loop_index находится в диапазоне от initial_value до final_value, можно считать, что при этом условие продолжения цикла – Истинно (И), когда параметр цикла за пределами диапазона, условие – Ложно (Л).

Элементы ЯПВУ Цикл с параметром ТОИ-ИМ 4 Работа цикла ДЛЯ: Переменная loop_index устанавливается в заданное начальное значение initial_value, При каждом прохождении (итерации) цикла переменная цикла автоматически увеличивается (уменьшается) на 1, В начале новой итерации переменная loop_index проверяется на соответствие верхнему (нижнему) пределу (final_value), При достижении переменной loop_index заданного верхнего (нижнего) предела (final_value) цикл завершается и алгоритм переходит к выполнению следующего за ДЛЯ ВСЁ действия. В виде блок-схемы эта конструкция выглядит так: В ЯП Pascal и С эта конструкция реализуется с помощью оператора for Тело цикла ДЛЯ ВСЁ И Л ДЛЯ loop_index = initial_value ДО final_value

Элементы ЯПВУ C Оператор цикла for Pascal For := To [или DownTo] Do ; где For, To [DownTo], Do – ключевые слова для, до, выполнить, - параметр цикла – переменная порядкового типа, - а, в – начальное и конечное значения (выражения) параметра цикла если To: a<b и шаг = +1; если DownTo: a>b и шаг = -1, - оператор – одиночный или состав- ной оператор. Процедура Break; - досрочный выход из цикла, Процедура Continue; - завершить текущую и начать новую итерацию. Пример: For i := 1 To n Do for ( ; ; ) ; где for – ключевое слово для, - инициализация – присваивание начального значения параметру (-ам) цикла, - условие – выражение, цикл выполняется пока оно истинно, - приращение – изменение параметра цикла при каждой итерации, - оператор – одиночный или состав- ной оператор. Принудительное завершении всего цикла или текущей итерации – операторы: break, continue, return, goto. Пример: for (i = 1; i <= n; i++) ТОИ-ИМ 5

Примеры цикла for Блок-схема алгоритма: Вычислить сумму целых положительных чисел от 1 до N Элементы ЯПВУ ТОИ-ИМ 6 Начало Вычисление суммы натурального ряда от 1 до N Конец Запросить " Введите N = " Получить N S = S + ind ИЛ S = 0 Вывести "Сумма = ", S ДЛЯ ВСЁ Ввод числа N Начальное значение суммы S Цикл суммирования Вывод результата ДЛЯ ind=1 ДО n

Примеры цикла for Program Sum; var i, n, s : Integer; begin Write('Введите N = '); ReadLn (n); (* Ввод числа *) s := 0; (*Начальное значение суммы*) For i := 1 To n Do (*Цикл суммирования *) s := s + i; (* Вывод результата *) WriteLn ('Сумма = ', s); End. Вычислить сумму целых положительных чисел от 1 до N #include int main () { int i, n, s=0; printf ("Введите n = "); scanf ("%d",&n); /* Ввод числа */ /* Цикл подсчета суммы */ for (i = 1; i <= n; i++) s = s + i; /* Вывод результата */ printf("Сумма = %d\n", s); return 0; } Задание на дом на цикл for: 1. Дано натуральное число, найти сумму его делителей. Вывести все делители и их сумму на печать. 2. Напечатать таблицу значений функции Y=X 2 +1 во введенном диапазоне 3. Вывести на экран таблицу степеней двойки от нулевой до 20-й. Нарисовать рамки таблицы и отформатировать её содержание (прижать числа к правой границе столбцов). Нарисовать блок-схему алгоритма и написать программы на Pascal и С Элементы ЯПВУ CPascal ТОИ-ИМ 7

Элементы ЯПВУ Цикл с предусловием ТОИ-ИМ 8 Эта конструкция используется для выполнения цикла, условие завершения которого описывается в заголовке (в начале) цикла. В псевдокоде для описания цикла с предусловием используется следующая конструкция: ПОКА условие P истинно Тело цикла ПОКА ВСЁ - условие P – логическое условие продолжения цикла (терминальное условие). Конструкция ПОКА – это цикл с предусловием, т.е. условие проверяется до выполнения действий тела цикла. Замечания: а) поскольку условие проверяется в начале цикла, то чтобы задать корректное условие необходимо выполнить определённую логическую обработку данных до проверки условия, б) стандартный способ прервать цикл ПОКА – сделать условие ложным; это означает, что в теле цикла должны выполняться какие-то операции изменяющие условие цикла, иначе цикл может стать бесконечным. Принудительное завершении всего цикла или текущей итерации – операторы безусловного перехода : break, continue, return, goto.

Элементы ЯПВУ Цикл с предусловием ТОИ-ИМ 9 Работа цикла ПОКА: 1. Проверяется логическое условие Р, 2. Если условие Р истинно, один раз выполняются действия (операции) заданные в теле цикла, затем выполняется переход к началу цикла и повторно проверяется условие, 3. Если условие Р по-прежнему истинно, снова повторяется тело цикла, 4. Если условие Р ложно, управление передаётся к действию, следующему за ключевыми словами ПОКА ВСЁ, и тело цикла больше не выполняется. В виде блок-схемы эта конструкция выглядит так: В ЯП Pascal и С эта конструкция реализуется с помощью оператора while Тело цикла ПОКА ВСЁ Л И ПОКА условие P истинно ?

Элементы ЯПВУ Цикл с предусловием ТОИ-ИМ 10 Использование счётчика итераций как условия цикла ПОКА При необходимости выполнить тело цикла определённое количество раз организуется счётчик итераций (повторов) цикла – переменная, значение которой увеличивается на единицу после каждого выполнения тела цикла. Это переменная используется в логическом выражении условия цикла Р. Перед началом цикла задаётся начальное значение переменной-счётчика, а в теле цикла это значение увеличивается на единицу (до оператора ПОКА ВСЁ) при каждой итерации цикла. Использование в качестве условия цикла ПОКА заключительной записи (сигнальной метки) или признака конца файла. Если необходимо обработать в цикле неизвестное заранее количество элементов (например, список, количество записей в котором неизвестно), то счётчик итераций цикла использовать не получиться. Часто в конце данных находиться заключительная запись или сигнальная метка – это особая запись или значение, размещённое в конце данных, она означает конец данных и должна содержать значение, которое чётко отличается от других обрабатываемых данных. Возможен также случай, когда идёт обработка данных размещённых в файле на внешнем устройстве (магнитном диске, флешке и др.). При это сигнальная метка не требуется, так как в каждом файле при его создании или изменении последним символом добавляется маркёр конца файла – EOF – End of File. В качестве условия цикла тогда можно использовать одно из равнозначных выражений: ПОКА ещё данные ПОКА ещё записи ПОКА есть записи ПОКА не EOF С такими условиями цикла все действия между операторами ПОКА и ПОКА ВСЁ будут повторяться, пока не будет сделана попытка прочесть данные после символа EOF. Когда это произойдёт, программа получит сигнал, обозначающий что данных в файле больше нет и условие ПОКА – ложно.

Элементы ЯПВУ C Оператор цикла while Pascal While Do ; где - While и Do – ключевые слова пока и выполнить, - условие – выражение логического типа, - оператор – одиночный или составной оператор. while ( ) ; где - while – ключевое слово пока, - условие – выражение, - оператор – одиночный или составной оператор. ТОИ-ИМ 11

Примеры цикла while Блок-схема алгоритма: Вычислить 25! Элементы ЯПВУ ТОИ-ИМ 12 Начало Конец Запросить " Введите k = " Получить k p = p * n ИЛ p = 1, n = 1 Вывести "Факториал = ", p ПОКА ВСЁ Ввод числа k Установить начальные значения p и n Цикл вычисления факториала Вывод результата Вычисление факто- риала заданного числа k n = n + 1 ПОКА n <= k

Элементы ЯПВУ C Оператор цикла while Pascal Примеры Вычислить значение 25! Program Factorial; Var n, k : Integer; p : Real ; (* n – переменная цикла, k – число факториала, p - значение факториала *) Begin Write('Введите число факториала k'); ReadLn (k); (* Ввод числа факториала *) p := 1; n := 1; (* Начальные значения *) While (n <= k) Do Begin (* Вычисление факториала *) p := p * n; (* Приращение переменной цикла *) n := n + 1; End; WriteLn('Значение факториала p = ', p:10); End. #include int main () { int n, k; float p; /* n – переменная цикла, k – число факториала, p - значение факториала */ printf ("Введите число k = "); scanf ("%d",&k); /* Ввод числа */ p = 1; n = 1; /* Начальные значения */ while (n <= k) { /* Вычисление факториала в цикле */ p = p * n; /* Приращение переменной цикла */ n++; } printf ("Значение факториала p = %G\n ",p); return 0; } ТОИ-ИМ 13

Элементы ЯПВУ Цикл с постусловием ТОИ-ИМ 14 Эта конструкция используется для выполнения цикла, условие завершения которого проверяется в конце цикла. Таким образом, действия тела цикла выполняются до проверки условия продолжения итераций цикла. В псевдокоде для описания цикла с предусловием используется следующая конструкция: ПОВТОРЯТЬ Тело цикла ПОКА условие P истинно [ как вариант – ложно] - условие P – логическое условие. В разных языках программирования (ЯП) логика условия цикла может различаться: в одних ЯП цикл завершается когда условие ложно (С/С++), в других когда – истинно (Pascal). Конструкция ПОВТОРЯТЬ-ПОКА обеспечивает выполнение алгоритма запрограммированного в теле цикл до проверки условия, таким образом, действия тела цикла будут обязательно выполнены хотя бы один раз. Принудительное завершении всего цикла или текущей итерации – операторы безусловного перехода : break, continue, return, goto.

Элементы ЯПВУ Цикл с постусловием ТОИ-ИМ 15 Работа цикла ПОВТОРЯТЬ-ПОКА: 1. Один раз выполняются действия (операции) заданные в теле цикла, 2. Проверяется логическое условие Р, 3. Если условие Р истинно [ложно], выполняется переход к началу цикла и снова выполняется тело цикла, 4. Снова проверяется условие Р, если оно по-прежнему истинно [ложно], то снова повторяется тело цикла, 5. Если условие Р становиться ложно [истинно], то управление передаётся к действию, следующему за проверкой условиях ПОКА, и тело цикла больше не выполняется. В виде блок-схемы эта конструкция выглядит так: В ЯП Pascal эта конструкция реализуется с помощью оператора repeat-until; в языке С – do-while Л [И]Л [И] И [Л]И [Л] ПОВТОРЯТЬ Тело цикла ПОКА условие P истинно ?

Элементы ЯПВУ C Операторы Pascal Цикл repeat-until Цикл do-while Repeat Until ; где - Repeat и Until – ключевые слова повторять и пока, - операторы цикла – произвольная последовательность операторов, - условие – выражение логического типа. В этой конструкции при несколь- ких операциях в теле цикла – операторные скобки не требуются, но разрешены. do while ( ); где - do и while – ключевые слова выполнять и пока, - оператор – одиночный или составной оператор, - условие – выражение. ТОИ-ИМ 16 Обратить внимание!!! В цикле repeat-until (Pascal) логика повторения итераций цикла противоположна логике повторения остальных циклов Pascal и С: если условие Ложно – цикл повторяется, если Истинно – происходить выход из цикла.

Примеры цикла r epeat-until и do-while Блок-схема: Определить, является ли введенное с клавиатуры целое число простым Элементы ЯПВУ ТОИ-ИМ 17 ТО Начало Конец Запросить " Введите n = " Получить n r = n % d ЕСЛИ r <> 0 d = 2 Вывести " простое." ПОВТОРЯТЬ Вывод результата Ввод числа n d = d + 1 И Л ЕСЛИ ВСЁ 1 1 ТО ЕСЛИ d = n Вывести "Число n – " ЕСЛИ ВСЁ Вывести " не " ИНАЧЕ Является ли введенное с клавиатуры целое число простым Начинаем с делителя равного 2 Остаток от деления на d Цикл про- должается пока остаток не равен 0 Если раздели- лось не наце- ло, то переход к следующему кандидату в делители Цикл поиска делителей числа n Есть ли де- лители кро- ме 1 и d=n? ИНАЧЕ ПОКА r <> 0

Элементы ЯПВУ C Операторы Pascal Цикл repeat-until Цикл do-while Примеры Определить, является ли введенное с клавиатуры целое число простым Program Simple number; Var n, d, r : Integer; (* n – проверяемое число, d – текущий де- литель, r – текущий остаток от деления *) Begin Write('Введите целое число n = '); ReadLn (n); d := 2; (* Сначала делим на 2 *) Repeat (* Остаток от деления на d *) r := n mod d; (* n не разделилось нацело на d *) If r <> 0 Then d := d + 1; Until r = 0; If d = n Then WriteLn (n, ' – простое число') Else WriteLn (n, ' – не простое число'); End. #include int main () { int n, d, r; /* n – проверяемое число, d – текущий делитель, r – текущий остаток от деления */ printf ("Введите целое число n = "); scanf ("%d",&n); d = 2; /* Сначала делим на 2 */ do { r = n % d; /* Остаток от деления на d */ if (r != 0) d = d + 1; /* не нацело */ } while ( r != 0); if (d == n) { printf(" - %d",n); printf("простое число\n"); } else { printf("%d",n); printf("не простое число\n"); } return 0; } ТОИ-ИМ 18