69132

Алгоритмічна конструкція повторення. Цикл з передумовою, постумовою, лічильником. Переривання циклу

Лекция

Информатика, кибернетика и программирование

У заголовку циклу зазначається умова завершення циклу а тіло циклу являє собою блок операторів що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією.

Украинкский

2014-09-30

83.5 KB

9 чел.

Лекція 9. Тема:Алгоритмічна конструкція повторення.

                          Цикл з передумовою,постумовою,лічильником. Переривання циклу.

План:

1. Алгоритмічна конструкція повторення

2. Цикл із передумовою

3. Цикл із постумовою

4. Цикл із лічильником

5. Переривання циклу

1. Алгоритмічна конструкція повторення

У розглянутих вище прикладах усі оператори виконувалися не більше одного разу. Проте часто постає потреба виконати один і той самий оператор декілька разів. Для цього застосовують оператори циклів, що реалізують алгоритмічну конструкцію повторення. Цикл складається із заголовка та тіла. У заголовку циклу зазначається умова завершення циклу, а тіло циклу являє собою блок операторів, що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією. Якщо умова завершення хибна, то тіло циклу виконується ще раз, якщо істинна, то виконання циклу припиняється і здійснюється перехід до виконання наступного за циклом оператора. Замість умови завершення циклу може перевірятися її заперечення — умова продовження, хибність якої призводить до припинення виконання циклу, а істинність — до продовження. Змінні, значення яких модифікуються в тілі циклу і впливають на істинність умови завершення, називаються параметрами циклу. Виконанню будь-якого циклу має передувати ініціалізація його параметрів.

У мові Pascal є три різновиди операторів циклу: оператор циклу з передумовою, оператор циклу з постумовою та оператор циклу з лічильником. Вибір того чи іншого оператора циклу для розв'язання певної алгоритмічної задачі здійснюється залежно від типу умови завершення циклу. Цикли з передумовою розглянуто в розділі 3.2.1, цикли із постумовою - в розділі 3.2.2, а цикли з лічильником — у розділі 3.2.3. Нарешті, у розділі 3.2.4 обговорюються допоміжні засоби керування циклами — процедури break і continue.

2. Цикл із передумовою

Насамперед визначимо відмінні риси, що вирізняють цикл із передумовою з-поміж інших циклічних операторів. У циклі з передумовою перша перевірка умови продовження циклу відбувається ще до першого виконання його тіла. Це означає, що за деяких значень параметрів циклу його тіло може не виконатися жодного разу. Саме за цією ознакою під час розв'язання певних задач віддають перевагу циклу з передумовою над циклом із постумовою. З іншого боку, і цикл з передумовою, і цикл із постумовою застосовують лише у тому випадку, коли кількість повторень є невідомою до початку виконання циклу - в іншому разі використовують цикл із лічильником. Отже, наведемо синтаксис оператора циклу з передумовою:

while <умова продовження циклу> do <оператор>;

Тут whi 1 є <умова продовження циклу> do є заголовком циклу, <оператор> - його тілом. Тіло циклу може бути операторним блоком і містити в собі будь-які оператори: циклу, вибору,присвоєння тощо. Умова продовження циклу повинна бути виразом булевого типу. Оператору циклу з передумовою відповідає блок-схема, що зображена на рис.

Блок-схема циклу з передумовою

Оператор циклу з передумовою виконується за таким алгоритмом. Спочатку обчислюється умова продовження циклу, що записана в його заголовку. Якщо вона істинна, то виконується тіло циклу, інакше виконання циклу припиняється. Після виконання тіла циклу буде знову перевірена умова його продовження. Чергування виконання тіла циклу та перевірки умови продовження триває доти, доки умова не стане хибною.

Приклад

Розглянемо задачу перевірки натурального числа на простоту. Як відомо, число я є простим, якщо воно ділиться лише на одиницю та на себе, тобто його додатними дільниками є лише числа 1 і я, інакше я вважається складеним числом. Отже, в алгоритмі перевірки числа на простоту повторюються такі дії: перевірка подільності числа п на дільник k та вибір наступного дільника шляхом збільшення k на одиницю. Таким чином, алгоритм є циклічним. Очевидною умовою продовження циклу є умова k < п. Оскільки на одиницю ділиться будь-яке число, то найменше значення параметра циклу k дорівнюватиме 2. Неважко побачити, що перебір всіх п - 2 чисел, від 2 до п - і, є недоцільним, оскільки значення найбільшого дільника складеного я не може перевищувати величини -Jn. У такому разі достатньо перебрати лише цілі числа від 2 до |_Vn J (символами \_х J позначатимемо цілу частину числа х).

Розглянемо будову циклу детальніше. Як сигналізувати про те, що знайшовся деякий дільник числа п? Це можна зробити за допомогою змінної логічного типу, дамо їй ім'я f 1 ag (прапорець). До початку виконання циклу присвоїмо цій змінній значення true, а в разі знаходження дільника я - значення f al se. Отже, після виконання циклу flag дорівнюватиме false, якщо дільник п знайдено (п - складене), і значенням flag залишиться true, якщо п є простим. Зауважимо, що в разі знаходження хоча б одного дільника я подальша перевірка чисел не потрібна, оскільки я тоді напевне буде складеним. Таким чином, цикл можна зупиняти не тільки по досягненні дільником k значення, а й внаслідок хибності значення змінної flag. Умова продовження циклу буде складеною: (k<=trunc(sqrt(n))) and flag (вираз trunc(sqrt(n)) дорівнює цілій частині кореня з я; функції trunc(x), sqrt(x) та інші стандартні функції розглядатимуться в розділі 4.1.3). Залишилося навести код програми та екранну копію результатів її виконання.

program ехЗ_4;

var n.k:integer:

flag:boolean;

begin

writeln ( number simplicity')

writeln (enter integer:  ');

readln(n):

k:-2:

flag:-true

while (k<=trunc(sqrt(n))) and flag do

begin

1f n mod k - 0 then flag:-false:

K:=k+1;

end:

1f flag then writeln (n. ‘is simple’) else writeln (n, ‘is not simple’):

end.

Оскільки цикл може почати роботу лише в разі істинності умови його продовження, а завершити роботу — лише в разі хибності цієї умови, то її істинність, а отже, і значення параметрів циклу, повинні змінюватися під час його роботи. В іншому разі відбудеться «зациклення», тобто виникне ситуація, коли цикл ніколи не завершує своєї роботи. У середовищі Borland Pascal 7.0 виконання нескінченного циклу, а разом із ним і виконання всієї програми переривається комбінацією клавіші Ctrl+Break.

3. Цикл із постумовою

Як і цикл із передумовою, цикл із постумовою застосовують тоді, коли кількість ітерацій циклу є невідомою до початку його виконання. Умова завершення циклу з постумовою записується після тіла циклу та вперше перевіряється після виконання операторів тіла. А отже, цикл з постумовою за будь-яких обставин буде виконано принаймні один раз — в цьому і полягає його головна відмінність від циклу з передумовою. Синтаксис оператора циклу з постумовою такий:

repeat

<оператор1>: ... <onepaтopN>;

until <умова завершення циклу>;

Тут repeat, until — зарезервовані слова, <оператор1>;...<оператор№>; - тіло циклу; <умова завершення циклу> — деякий булів вираз. Дослівно ця мовна конструкція перекладається так:

Повторювати послідовність операторів доти, доки не виконається умова.

Оператор циклу з постумовою працює за таким алгоритмом. Спочатку виконуються оператори, що входять до складу тіла циклу. Потім обчислюється умова завершення циклу. Якщо вона істинна, цикл завершує свою роботу, інакше повторюється виконання його тіла. Процеси виконання тіла циклу та перевірки умови завершення чергуються доти, доки умова не стане істинною. Зауважимо, що параметри циклу з постумовою, як і циклу з передумовою, повинні змінюватись під час його виконання так, щоб не трапилось «зациклення»

Синтаксичною особливістю оператора циклу з постумовою є те, що тіло циклу не обов'язково оточувати операторними дужками begin та end, оскільки воно розташоване між зарезервованими словами repeat та until. Символ ■*;* після останнього оператора тіла циклу також є необов'язковим, що уможливлює запис циклу із порожнім тілом. Наведемо приклад застосування даної циклічної конструкції.

Приклад

Запрограмуємо гру «вгадування числа». Програма генерує випадкове ціле число з деякого діапазону, а користувач намагається його відгадати, вводячи значення з клавіатури. Якщо число вгадане, то програма виводить повідомлення про це і завершує свою роботу, інакше спроби відгадати число повторюються. На початку виконання програми встановлюється певний «призовий фонд», що зменшується з кожною невдалою спробою користувача.

Очевидно, що процес відгадування є циклічним, оскільки повторюються такі дії, як введення числа, його порівняння із генерованим і зменшення призового фонду. Для моделювання цієї гри найзручнішою конструкцією буде саме цикл із постумовою, оскільки, по-перше, кількість спроб наперед невідома, і, по-друге, принаймні одна спроба повинна бути здійснена. Використаємо змінні для збереження «призового фонду» (prize), числа, що буде згенероване комп'ютером (у), числа, що його вводитиме користувач (х), та штрафу (penalty).

Для генерування випадкового числа використовуються дві бібліотечні підпрограми. Процедура randomi ze ініціалізує датчик випадкових чисел значенням, отриманим від системного таймера, а функція random(n) повертає згенероване цим датчиком випадкове ціле число з діапазону 0 .. я- 1. Процедуру randomize слід викликати до першого виклику функції random. Насправді згенеровані в такий спосіб числа не є випадковими з математичної точки зору, вони лише схожі на випадкові і називаються псевдовипадковими числами.

program ехЗ_5:

const penalty»10:

var x.

       у.

prize-.integer;

begin

writeln('define number.'which computer generate');
randomize; {ініціалізувати генератор випадкових чисел}

y:=random(1000):     {генерувати випадкове число з діапазону від 0 до 999}

prize:-100; repeat          {початкова "призова сума"}

repeat

writeln ('enter number');

readln(x);

if x>y then begin

        writeln ('Wrong, enter smaller');

        prize:=prize-penalty;

end:

if x<y then begin

writeln('Wrong, enter bigger');

prize:=prize-penalty;

end;

until x=y: {поки число не відгадане користувачем}

writeln (You have guessed right!'):

writeln (You have won the prize '.prize);

end.

4. Цикл із лічильником

Розглянемо задачу обчислення факторіала невід'ємного цілого числа п. Нагадаємо формулу факторіала: n! = 1 • 2 •... • (п -1) • n, де n > 0,0! = 1. Легко побачити, що n! = (n - і)! • n, тому обчислення можна звести до багаторазового виконання операції factorial :=factorial*i, де і = 2,3,..., п, а початкове значення змінної factorial дорівнює 1. Отже, задачу можна розв'язати за допомогою циклічної структури. Тіло циклу складатиметься із однієї вищезгаданої операції присвоєння, а кількість її повторень становитиме я. Таким чином, умовою завершення циклу буде виконання певної кількості ітерацій. Відстежити істинність такої умови дозволяє спеціальний різновид параметра циклу, тильних ітеращй. Лічильник - це змінна, що під час кожного повторення збільшується на одиницю. В операторі циклу з лічильником облік числа виконаних ітерацій ведеться автоматично, і тому цей оператор є зручною формою запису циклів із наперед визначеною кількістю повторень. Наведемо синтаксис оператора циклу з лічильником.

for <лічильник>:=<початкове значення> to <кінцеве значення> do <оператор>:

Тут for, to, do — зарезервовані слова («для», «до», «виконати»); <початкове значення та <кінцеве значення — вирази того самого перелічуваного типу; <лічильник — змінна перелічуваного типу, що є узгодженим за присвоюванням з типом початкового та кінцевого значення; <оператор - простий або складений оператор, що є тілом циклу. Фраза від слова for до слова do є заголовком циклу, а зазначений після слова do оператор — тілом циклу.

Виконання оператора for здійснюється за таким алгоритмом. Спочатку обчислюються та порівнюються значення виразів <початкове значення> та <кінцеве значенням Якщо початкове значення більше за кінцеве, то виконання циклу завершується, інакше лічильнику циклу присвоюється початкове значення і виконується тіло циклу. Після виконання тіла циклу порівнюється поточне значення лічильника з його кінцевим значенням, і, якщо ці значення не рівні, то поточне значення лічильника збільшується на одиницю і виконання циклу триває далі. Цикл завершує свою роботу тоді, коли поточне значення лічильника циклу стає рівним його кінцевому значенню.

Приклад  

Складемо програму обчислення факторіала цілого невід'ємного числа. Тіло циклу в цій програмі міститиме один оператор — присвоєння змінній factorial добутку її попереднього значення та поточного значення лічильника циклу. Результати роботи програми наведено на рис.

{обчислення факторіала числа}

{значення факторіала}

{вхідне число та лічильник циклу}

Program ехЗ_6:

var factorial:longint:

n.i:integer;

begin

writelnCfactorial calculation - n! '):
repeat {введення даних}

writeCenter integer number:1):

readln(n):

until n<=16;       {обмеження діапазону вхідних даних}

factorial:-1;        {початкове значення факторіала}

for i:-2 to n do  {заголовок циклу обчислення факторіала}

factorial: = factorial* i {тіло циклу}

writeln (n.'!='.factorial):      {виведення результату}

                                           end.

Допустимий діапазон вхідних значень було обмежено числом 16, оскільки функція факторіала числа дуже швидко зростає, і вже для значення п =17 величина л! перевищує найбільше допустиме значення типу longint.

Рис. Результати роботи програми ехЗ_6. Обчислення факторіала числа

5. Переривання циклу

У деяких програмах виникає потреба завершити цикл або його ітерацію передчасно. Це завжди можна зробити, ускладнивши умову завершення циклу або записавши додаткові оператори розгалуження до його тіла. Проте такі дії можуть зробити код програми надто громіздким. У мові Pascal цього ефекту можна досягти простіше, використовуючи процедури break та continue.

Передчасний вихід із циклу означає, що умова завершення циклу під час виходу з нього є хибною. Для примусового переривання циклу слід викликати процедуру break. Процедура continue здійснює пропуск усіх інструкцій, записаних за її викликом в тілі циклу. Таким чином, після виклику процедури continue завжди перевіряється умова завершення або продовження циклу. Якщо використовуються вкладені цикли, то процедура break перериває той цикл, у якому вона викликається. Після переривання внутрішнього циклу управління передається заголовку зовнішнього циклу для перевірки умови його продовження. Аналогічно працює і процедура continue: її виклик забезпечує виконання нової ітерації того циклу, в якому цей виклик здійснено.

Приклад

Як і у прикладі 3.4, розв'яжемо задачу перевірки на простоту натурального числа п, застосувавши той самий алгоритм. Але у програмній реалізації алгоритму відмовимося від логічної змінної flag, перериваючи виконання циклу в разі знаходження дільника п оператором виклику процедури break. Після завершення циклу саме значення потенційного дільника k визначатиме, чи є число складеним: якщо k-trunc(sqrt(n))+l, то оператор виклику процедури break не було застосовано жодного разу і число я є простим, інакше вихід із циклу було здійснено оператором виклику процедури break внаслідок того, що знайшовся дільник я, а отже, число п є складеним.

program ехЗ_7: var n.k:integer: begin

writeln (‘number simplicity');

writeln('enter integer:  '):

readln(n);

k:=2:  

while (k<=trunc(sqrt(n))) do

begin

if n mod k =0 then {якщо k ділить n.}

break; {сигналізуємо про це}

k:=k+l: {наступний дільник}

end:

if k=trunc(sqrt(n))+l then writeln (n.' is simple')

else writeln (n.' is not simple'):

end.

Контрольні питання

1. Алгоритмічна конструкція повторення

2. Цикл із передумовою

3. Цикл із постумовою

4. Цикл із лічильником

5. Переривання циклу


 

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

36628. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ВЫСОКОГО УРОВНЯ 1015 KB
  1 Языки программирования Языки программирования делятся на 3 основных класса как показано на рис.3 Понятие алгоритма и его свойства Алгоритм это точное предписание о выполнении в определенном порядке некоторых операций приводящих к решению всех задач данного класса. Непосредственный предшественник C язык Си с классами появился в 1979 году а в 1997 году был принят международный стандарт C который фактически подвел итоги его 20летнего развития. Если мы говорим об объектноориентированной программе то она должна создать объект...
36629. РЕИНЖИНИРИНГ БИЗНЕС-ПРОЦЕССОВ 2.09 MB
  При выстраивании системы управления и взаимодействия в одном процессе непременно придется захватить взаимодействие данного пилотного процесса с другими. Появление эффекта перетягивания одеяла когда руководитель пилотного процесса добивается регламентации и последующего выполнения совместных работ с точки зрения выгоды и преимуществ своего процесса а не всей организации. Воспользовавшись правом преимущественного создания регламентирующих документов владелец пилотного процесса может создать себе более льготные условия по обеспечению...
36630. Наплавка зуба ковша 2.5 MB
  Основным способом соединение деталей является дуговая электрическая сварка. Возможно что, совершенствование существующих способов сварки и резки металлов и их синтез дадут новый способ сварки в твердой фазе
36631. Лекции по финансам 399.5 KB
  А В Воздействует на ставка налога Социальная При помощи Д бюджета Достигается Военная Геополитика Национальная Экономическая Бюджетная Ценовая Таможенная Финансовая Денежная Кредитная Термин финансы возник в XV в. В последнее время стал применяться метод получивший название бюджета ориентированного на результат БОР. Сущность и содержание бюджета определяется функцией государства. Сущность бюджета проявляется в его функциях: Образование общегосударственного фонда денежных средств; Использование общегосударственного фонда денежных...
36632. Инкапсуляция. Уровень абстракции (программирование) 425 KB
  Компилируемые программы. Утверждается что известные визуальные средства разработки приложений Windows также компилируют программы однако это не совсем верно в действительности происходит компиляция только части программы и последующая компоновка программыинтерпретатора и Ркода в исполняемый модуль. Например Delphi не использует ни интерпретатор ни Ркод и создаёт действительно откомпилированные программы готовые для использования. Поэтому программы Delphi быстры и могут могут поставляться в виде единственного используемого модуля...
36633. Конспект сюжетного физкультурного занятия для детей старшего дошкольного возраста 34.5 KB
  Упражнять детей в подбрасывании мяча вверх двумя руками и ловле его в ходьбе отбивании мяча в ходьбе по гимнастической скамейке двумя руками ведении мяча змейкой между предметами поочередно каждой рукой добиваться ритмичности и четкости выполнения движений на каждый таг формировать чувство мяча соотносить силу удара с высотой полета мяча. Проводится комплекс общеразвивающих упражнений с мячами. В: прокатывание мяча между ладонями 6 7 раз. В: прыжки вокруг мяча в чередовании с ходьбой на месте 5x3 раза.
36634. Как устроен компьютер 50.5 KB
  Организационный момент психологический настрой 1 мин: На доске запущена презентация с загадкой: Напишу и сосчитаю ошибку укажу Я и музыку сыграю И картинку покажу Я хотя росточком мал Но большой универсал компьютер Тема нашего урока Как устроен компьютер слайд 2 Постановка целей урока 3 мин Что такое компьютер это универсальное устройство для хранения обработки и передачи информации Из каких устройств состоит компьютер системный блок монитор клавиатура мышь и др....
36635. Количество информации, как мера уменьшения неопределенности знаний 37.5 KB
  Тип урока: комбинированный Цели: Обучающая дать определение единицы измерения информации; развивающая развивать интерес к изучаемой теме логическое мышление; воспитывающая воспитывать у ребят дисциплинированность и внимательность на уроке. Тема нашего сегодняшнего занятия Количество информации как мера уменьшения неопределенности знаний. Процесс познания окружающего мира приводит к накоплению информации в форме знаний.
36636. Інструкція з безпеки праці 46.5 KB
  Тому дайте будьласка відповіді на такі питання: Назвіть основні положення кодексу законів про працю Назвіть основний закон що гарантує право громадян на безпечні та нешкідливі умови праці Що зобовязаний роботодавець забезпечити Які створює держава умови Які Ви знаєте законодавчі акти з охорони праці Активізація нового матеріалу: А темою уроку є €œІнструкція з безпеки праці€. На уроках €œВиробничого навчання€ ми застосовуємо безпосередньо отриманні знання з охорони праці адже уявлення безпеки праці і виховування вміння до...