Тема 4. Цикли

Цикли

У мові Pascal розрізняють три оператори циклу:

              1) з передумовою;

              2) з післяумовою;

              3) з параметром.

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

В циклах відбувається перевірка деякої умови і в залежності від результату цієї перевірки відбувається або вихід з циклу, або повторення виконання тіла циклу. Якщо перевірка умови відбувається перед виконанням блоку операторів, то такий цикл називається циклом з передумовою (цикл "while"), а якщо перевірка проводиться після виконання тіла циклу, то це цикл з післяумовою (цикл "repeat").

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

1.       Цикл з передумовою    While <логічний вираз> do <оператор>;

Оператор після do буде виконуватися доки логічний вираз приймає істинне значення (True). Його істинність перевіряється щоразу перед черговим повторенням оператора циклу, який буде виконуватися доти, поки логічне вираз істинний. Як тільки логічний вираз приймає значення неправда (False), здійснюється перехід до оператора, наступного за while.

Істинність виразу перевіряється до виконання оператора, тому якщо логічний вираз із самого початку буде мати значення неправда (False), то оператор не виконається жодного разу. Варто пам'ятати, що після ключового слова do дозволяється використовувати тільки один оператор. Якщо потрібно виконати кілька операторів, то використовується складений оператор (begin ….. end;).

Приклад:

 X:=10;

While x>0 do x:=x-1;

            2.   Оператор циклу з післяумовою відрізняється від попередньою тим, що:

1)умова перевіряється після одного виконання операторів тіла циклу (таким чином гарантується хоча б одне виконання тіла циклу);

2) критерій припинення циклу полягає в тому, що значення логічного виразу приймає значення істинне; а якщо значення хибне, то даний цикл повторюється. Тіло циклу повторюється до тих пір, поки умова не стане істинна.

            Repeat

                        <серія операторів>

            Until   <логічний вираз>;

Приклад:

 X:=10;

Repeat   x:=x-1; write(‘x=’,x) until x=0;

3. Оператор циклу з параметром використовується в тих випадках, коли число повторень циклу може бути визначене перед початком циклу. Крім цього цикли з параметром дозволяють задавати автоматично зміну значень деякої змінної і використовувати це значення в тілі циклу.

For <змінна>:=<початкове значення> to <кінцеве значення> do <оператор>;

For <змінна>:=<кінцеве значення> downto <початкове значення> do <оператор >;

Діапазон задає зміну значень змінної і кількість повторень тіла циклу. Діапазон–це відрізок з одного із впорядкованих типів. Якщо між виразами стоїть службове слово (to), то значення змінної буде зростати в процесі роботи; при (downto) – спадати. <змінну> називаються лічильником або параметром циклу.

Приклад:

For x:=10 downto 1 do  write(‘x=’,x);

При використанні даного оператора слід пам’ятати:

1)      параметр циклу повинен мати впорядкований тип;

2)      початкове і кінцеве значення діапазону повинні мати такий тип, як і параметр циклу ;

3)  після закінчення циклу значення параметру циклу рівне кінцевому виразу діапазону.

Приклади використання циклів

Приклад 1. Обчислити суму

WHILE	REPEAT	FOR
Фрагмент програми обчислення суми: i:=1;S:=0; while i<=10 do   begin     S:=S+i;     i:=i+1;   end;	i:=1;S:=0; repeat     S:=S+i;     i:=i+1; until i>10;	S:=0; For i:=1 to 10 do   S:=S+i;

Приклад 2.  Протабулювати функцію y=sin x, де х є [0,2П] з кроком П/2.

x:=0; while x<=2*pi do   begin     y:=sin(x);     writeln(y);     x:=x+pi/2;   end;

x:=0; repeat     y:=sin(x);     writeln(y);     x:=x+pi/2; until x>2*pi

Приклад 3. Ввести 8 цілих чисел і знайти їх суму.

s:=0; i:=1; while i<=8 do   begin     read(a);     s:= s+a;     i := i+1;   end;

s:=0;  i:=1;  repeat     read(a);     s:= s+a;     i := i+1;  until i>8;

s:=0; for i:=1 to 8 do   begin     read(a);     s:= s+a;   end;

Гуржій, Карташова, Лапінський, Руденко  “Інформатика, 8 клас ”    ст. 273-276

Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач” ст.80-86

Д/з 1: № 189(1,2,5), 191(2,6), 195(2,3), 197(1,2,4), 201(1,2), 202(2), 203(1), 242, 245  (Караванова “Інформатика”)

Д/з 2 (вкладені цикли): №272(1,2),  273(1,2),  276 (Караванова “Інформатика”), (вивести таблицю множення одноцифрових чисел)

Тема 3. Умовний оператор

Умовний оператор

If <вираз логічного типу> then <оператор> [else <оператор>];

Вираз в квадратних дужках [else <оператор>] може бути відсутнім, тоді говорять про скорочену форму умовного оператора. Читається розгалуження так:

 Якщо логічний вираз істинний, то виконується оператор1, інакше виконується оператор2.

Після then, else маємо право писати лише один оператор, якщо є потреба в більшій кількості, то в Pascal вводиться поняття складеного оператора. Це послідовність операторів, розділених (;), яка закріплена в операторну дужку : begin … end.

Обчислити у по формулі y := cos(x) ^2 , якщо х є (0,2),інакше обчислити у по формулі y := 1-sin(x ^2)    

program exam1;

var x,y: real;

begin  writeln('введіть значення x');read(x);

           if (x>0)and(x<2) then y := sqr(cos(x))            {обчислення за першою формулою}

                else y := 1-sin(sqr(x));     {обчислення за другою формулою}

           writeln('при x =', x, '  y = ', y)

end.

Обчислити z по формулі z := (x+5) ^9+ y^2, якщо х>0 і y>0.    

program exam2;

var x,y,z: real;

begin  read(x,y);

           if (x>0)and(y>0) then z := …   ;         {обчислення z}

           writeln(z)

end.

Гуржій, Карташова, Лапінський, Руденко  “Інформатика, 8 клас ”    ст. 260-268

Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач” ст.57-63

Д/з 1 : № 96(1,4), 99, 109, 113, 122 (Караванова “Інформатика.)

Д/з 2 : № 126(1,2,3), 127(1,3), 140(4,5) (Караванова “Інформатика.)

Тема 2. Вирази

Вирази

Розглянемо такі типи виразів:

1.      Дійсні

Ввести значення двох дійсних змінних. Обчислити їхню суму та різницю.

program  Examp1;

var a,b,s,r :real;

begin   writeln('введіть два дійсні числа'); read(a,b);

           s:= a + b;  r:= a - b; 

           writeln('результати s=', s, ' r=', r:5:2);     {на число r виділяється 5 позицій,

                                                                                                                    з них 2 - на дробову частину}

end.

Ввести значення довжини  кола L. Обчислити радіус цього кола і площу круга, обмеженого цим колом.

program  Examp2;

var L,s,r :real;

begin         

      writeln('введіть довжину кола');  read(l);

       r:=l/(2*pi);     {знаходження радіуса, використано стандартну функцію pi}

       s:=pi*sqr(r); {знаходження площі}

      writeln(‘коло довжини ‘, l ,’ має радіус ’, r ,’ та площу ’, s)

end.

2.      Цілочислові

Знайти суму цифр двоцифрового числа.

program  Examp1;

var c,c1,c2,s: integer;

begin          writeln(' введіть ціле двоцифрове число'); read(c);

      c1:= c div 10;                      {знаходження  першої цифри}

      c2:= c mod 10;                 {знаходження другої цифри}

      s:= c1 + c2;                         {обчислення суми цифр}

      writeln('сума цифр числа ', c, '  дорівнює  ',s);

end.

3.      Логічні

Логічній змінній t присвоїти значення true , якщо цілочислова величина k ділиться без остачі на 7 і false у протилежному випадку. Вивести значення t.

program  log1;

var k: integer; t: boolean;

begin

      writeln('введіть ціле число');  read(k);

      t:= k mod 7 = 0;  writeln('t=',t)

end.

Надрукувати true, якщо x належить проміжку (a,b) і false - у протилежному випадку.

program  log2;

var a,b,x: real;  t: boolean;

begin

    writeln('введіть проміжок (a,b)');  read(a,b);

    writeln('введіть дійсне число');  read(x);

    t:= (x>a) and (x<b);  writeln('t=',t)

end.

Гуржій, Карташова, Лапінський, Руденко  “Інформатика, 8 клас ”                                     ст. 240-254

Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач”     ст.37-42, 57-58

Д/з :

Дійсні вирази : № 50, 51, 54, 78 (а, б)    

(Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач”   ст. 54 )

Цілочислові вирази :

1.      Знайти суму крайніх цифр введеного трицифрового числа.

2.      Знайти останню цифру цілої частини та другу цифру дробової частини введеного дійсного числа.

Логічні вирази : № 82 

Тема 1. Програмування

Програмування

Зі сторінки      petriv.ho.com.ua/algo/         Ви можете скопіювати програмне середовище АЛГО, яке спеціально розроблене для вивчення основ програмування.

Підручники:

1.      Гуржій, Карташова, Лапінський, Руденко  “Інформатика, 8 клас ”

(виданий в бібліотеці ЛФМЛ 8-ому класу)

2.      Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач”

chashuk.edukit.volyn.ua/Files/downloads/Караванова_777.pdf

3.      Сайт :   http://pascal.org.ua

Основні поняття мови. Структура програми. Сталі та змінні величини

Гуржій, Карташова, Лапінський, Руденко  “Інформатика, 8 клас ”                                     ст. 227-236

Караванова “Інформатика. Основи алгоритмізації та програмування. 777 задач”     ст. 23-30, 42-45

Загальна задача динамічного програмування

Загальна задача динамічного програмування

Після розгляду найтиповіших задач динамічного програмування, простіше  сформулювати його основні ідеї. Почнемо із формулювання загальної задачі динамічного програмування в алгоритмічних термінах.

Нехай розв'язується деяка задача S. Для її розв'язання зада­ні вхідні дані S_o, що надалі оброблятимуться. У результаті за­стосування до цих вхідних даних розробленого оптимізаційного алгоритму U її буде перетворено у вигляд S_n. Процес виконання алгоритму можна представити як деяку функцію W(U), що дає кілька варіантів розв'язків. Оскільки задача динамічного програмування є задачею оптимізаційною, то серед усіх отриманих варіантів відповідей треба вибрати найкращий W*(U).

Методика розв'язування задач динамічного програмування бу­ла запропонована Р.Беллманом у 1955 р. і полягає в наступному.

Задача, що розв'язується, розбивається на окремі етапи. Як видно на конкретних прикладах, такими етапами є: ок­ремі зони, що утворюють відстань між двома населеними пунк­тами при прокладанні дороги; окремі підприємства при визна­ченні ефективного вкладення інвестицій у промислову галузь; почерговий розгляд окремих предметів під час відбору найдо­рожчих і одночасно найлегших серед них при обмеженні на їх сумарну вагу.

Кожний з етапів є окремою підзадачею поставленої загаль­ної задачі і розв'язується одним і тим самим розробленим оптимізаційним алгоритмом. Однак вибір розв'язків кожної на­ступної підзадачі залежить від розв'язків попередньої, і тому їх можна назвати залежними. Будемо вважати, що на першому етапі вхідна інформація S_o перетворюється алгоритмом U у вигляд S1. Тепер при виконанні наступного етапу вхідними даними для нього буде вже S1. При цьому застосування алго­ритму на даному етапі може дати багато варіантів розв'язків w₁(u), серед яких ми вибираємо ті, які надалі приведуть до найкращого кінцевого результату, тобто є перспективними. Позначимо їх w*₁(u). Аналогічно будуть перетворюватися вхідні дані на наступних етапах S₂, ..., S_n-1. Отже, оптимізація всієї задачі зводиться до визначення оптимальних результатів застосування розробленого алгоритму w*_i(u) на кожному окре­мому етапі.

P. Беллманом був сформульований принцип оптимальності: якою не була б інформація, що обробляється, перед черговим етапом необхідно вибрати стратегію на поточному етапі так, щоб виграш на цьому етапі плюс оптимальний виграш на всіх наступних етапах був максимальним.

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

Таким чином, згідно з принципом Беллмана розв'язування задачі динамічного програмування доцільно починати з визначення оптимального розв'язку на останньому n-му етапі. Для того, щоб знайти цей розв'язок, необхідно зробити різні передбачення щодо закінчення передостаннього етапу. Така стратегія, що вибрана при певних передбаченнях про те, як може закінчитися попередній етап, називається умовно оптимізаційною стратегією. Тобто принцип оптимальності вимагає знаходити на кожному етапі умовно оптимальну стратегію для будь-якого з можливих результатів попереднього етапу.

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

Таким чином, проходячи послідовно всі етапи з кінця до початку, можна визначити максимальне значення виграшу з n кроків.

Щоб знайти оптимальну стратегію, тобто визначити шуканий розв'язок задачі, необхідно пройти всю послідовність етапів у зворотному порядку. Теоретично ця послідовність виглядає так: на першому етапі в якості оптимальної стратегії необхідно взяти знайдену умовну оптимальну стратегію. На другому етапі визначити стан інформації S1*, яка отримується для задачі в результаті вибору умовної оптимальної стратегії и*_1. Цей стан визначає знайдена умовна оптимальна стратегія и(0)_2, яку тепер вважатимемо оптимальною і т. д. У результаті цього знаходимо розв'язок задач, тобто максимально можливий виграш та оптимальну стратегію U*, що включає в себе умовну оптимальну стратегію на окремих етапах: U* = (и*₁, и*₂, ... , и*_n).

Зробимо ще одне зауваження: у будь-якій задачі динамічно­го програмування «початок» і «кінець» можна поміняти місця­ми. Це повністю рівнозначне описаній вище методиці щодо ви­конуваних розрахунків, однак при такому підході виникають незручності щодо пояснення ідеї методу: простіше аргументу­вати, посилаючись на умови, що «вже склалися» до початку да­ного кроку, ніж на ті, які ще «попереду» цього кроку. По суті, обидва підходи абсолютно рівносильні і досить умовні. При­кладом цього може служити перша розглянута задача про прокладання найвигіднішого шляху між двома пунктами. Ми її розв'язували від пункту А до пункту В, а можна було навпа­ки. При цьому результуюча відповідь була б однаковою.

У кожній розглянутій задачі визначалася оцінка ефектив­ності роботи розробленого для її розв'язання алгоритму. І справді, оцінку менше ніж О(пт) для задач динамічного про­грамування отримати неможливо, оскільки у кращому разі нам доводиться хоч один раз обробляти кожний елемент таб­лиці розмірністю п*т. Але трапляються й об'ємніші щодо часу виконання задачі. З цим ми ознайомилися в задачі про роз­поділ ресурсів. Ученими доведено, що максимальною оцінкою ефективності роботи алгоритмів, які базуються на методі ди­намічного програмування, можна вважати О(пт log(nm)).

Критерії застосування задач динамічного програмування

Як розпізнати задачу динамічного програмування?

Насамперед варто зазначити, що найкращим критерієм «впізнавання» задач динамічного програмування є власний значний досвід у розв'язуванні таких задач. Разом з тим, можна дати й деякі поради.

Спочатку треба розглянути питання про можливість роз­биття задачі на етапи, що найчастіше міститься вже у форму­люванні самої задачі, як, наприклад, дослідження (аналіз) фінансування одного підприємства по роках або кількох окремих підприємств в економічних задачах. Але іноді таке розбиття необхідно робити штучно, як, наприклад, у задачі про прокладання найвигіднішого шляху. Кількість етапів у задачі найчастіше визначається так само в умові задачі. Якщо ж їх до­водиться визначати самостійно, то необхідно орієнтуватися на тип змінних, обумовлених у задачі, на критерії визначення кінцевого результату. Не можна забувати, що в разі збіль­шення кількості етапів значно зростає об'єм розрахунків, що у свою чергу впливає на загальний час виконання алгоритму.