Блок-схеми алгоритмів

Блок-схеми алгоритмів

Проблемне запитання: Як швидко порахувати суми: 2+4+6+..+ 2k = ? (сума перших парних натуральних чисел); 1+3+5+..+ 2к -1 = ?  (сума перших непарних натуральних чисел); 1+2+3+4+..+ k =   ?  (сума перших натуральних чисел); 12+22+32+42+..+ к2 =  ? (сума квадратів перших натуральних чисел); 1∙2 + 3∙2 + 3∙4 + 4∙5 + 5∙6 + … + к(к+1) =?; 13+23+33+43+..+ k3 =    (сума кубів перших натуральних чисел); Отже, може попросити допомоги у комп'ютера! А це значить шукати   алгоритми для сумування!

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

Графічне зображення базових  алгоритмічних структур.

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

Просте слідування

Слідування означає, що дії повинні виконуватись послідовно одна за одною.

Лінійний алгоритм – алгоритм, в якому всі вказівки виконуються одна за одною і не містить розгалужень та повторень.

Приклад

Алгоритм знаходження суми S трьох чисел a,b,c.

Розгалуження

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

Умова - це будь-яке твердження, яке або виконується або не виконується, тобто можна дістати одну з двох відповідей: «так» або «ні». Блок-схемою це можна зобразити так:

Якщо умова виконується, то виконується серія команд 1 (гілка так), якщо умова не виконується, то виконується команд 2 (гілка ні). Після виконання серії команд виконавець переходить до наступної команди після команди розгалуження.

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

Можливий випадок, що у випадку невиконання умови не потрібно виконувати ніяких дій. Тоді використовується скорочена форма розгалуження («Якщо-то»).

Блок-схема структури «якщо-то»

Приклад

Алгоритм обчислення модуля:

Приклад

Повторення(цикл)

Часто зустрічаються такі задачі при виконанні яких потрібно виконувати одні і ті самі дії декілька разів. Тоді кажуть, що така структура команд називається циклічною, або утворена структура «повторення».

Цикл – це форма організації дій, за якою одна і та сама послідовність дій виконується кілька разів доти, поки виконується деяка умова. Серія команд, що виконується декілька разів без змін при кожному проході циклу, називається тілом циклу.

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

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

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

Приклад

Алгоритм підрахунку суми N перших натуральних чисел. Суму позначимо через S, через і – черговий доданок. Спочатку S=0, оскільки ще суми не знаходили, i=1 (перше натуральне число). Щоб знайти суму, то потрібно до попередньої суми додати наступний доданок: S=S+i. Для отримання наступного числа потрібно попереднє збільшити на одиницю: i=i+1. Виконання циклу продовжується до тих пір, поки i<=N.

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

1. 2+4+6+..+ 2k = k(k+1)   (сума перших парних натуральних чисел);
2. 1+3+5+..+ 2к -1 = k²   (сума перших непарних натуральних чисел);
3. 1+2+3+4+..+ k = 0,5* k(k+1)  (сума перших натуральних чисел);
4. 1²+2²+3²+4²+..+ к² =  k(k+1)(2k+1)/6 (сума квадратів перших натуральних чисел);
5. 1∙2 + 3∙2 + 3∙4 + 4∙5 + 5∙6 + … + к(к+1) = k(k+1)(2+k)/3 ;
6. 1³+2³+3³+4³+..+ k³ =  k²(k²+1)/3  (сума кубів перших натуральних чисел);

Принципи структурного програмування

Алгоритми, у яких використовується тільки структура «слідування», називаються  лінійними.

Алгоритми, в основі яких лежить структура «розгалуження», називаються алгоритмами з розгалуженнями.

Алгоритми, в основі яких лежить структура «повторення», називають циклічними.

На практиці алгоритми розв’язування складних задач містять у собі всі три типи базових структур алгоритмів. Розглянуті принципи конструювання алгоритмів називають принципами структурного програмування.

Практичні завдання раджу не ігнорувати. Теорія без практики не запам'ятовується  і не ефективна. Тільки читаючи статті і виконуючи різноманітні задачі можна досягти найкращого ефекту від опанування мови програмування.

Вправа 1-1. «Побудова математичної моделі»

1)      В шкільну їдальню привезли m кг картоплі, а буряків в n раз менше. Скільки всього овочів привезли до шкільної їдальні ? Запишіть формулу.

2)      Присадибна ділянка має форму прямокутника, довжиною a см і шириною b см. Знайти чверть площі присадибної ділянки. Запишіть формулу.

3)      Контрольну роботу на “10”-“12” написали n  учнів, “7”-“9” – m учнів, “4”-“6” – k учнів. Визначити, у  скільки разів менше учнів написали на “4”-“6”, ніж на “7”-“12”.  Запишіть формулу.

4)      Знайти корені рівняння типу: ax=b.  Запишіть формули та умови на усі випадки.

5)      Знайти корені рівняння: ax²+bx+c=0. Запишіть формули та умови на усі випадки.

6)      Знайдіть площу кільця, яке створене двома кола із спільним центром і радіусами R та r. Запишіть формули та умови на усі випадки.

Вправа 1-2. «Алгоритм та його властивості»

1. Записати алгоритм обчислення виразу: y=(x³+2x+1)/(4x²-x+1). Складіть блок-схему та умови на усі випадки.
2. Записати алгоритм додавання багатоцифрових чисел. 
3. Складіть блок-схему для обчислення площі трапеції.
4. Складіть блок-схему алгоритму розв’язування задачі: якщо подарунок не перевищує N гривень, то купити цей подарунок і квіти, в іншому випадку купити тільки подарунок.
5. Складіть блок-схему для знаходження суми квадратів перших 50 натуральних чисел.

Вправи до  теми «Алгоритми та алгоритмічні структури»

1)      На одній книжкові полиці X книг, а на іншій – 10. Складіть блок-схему алгоритму обчислення кількості книг на двох полицях разом.

2)      Запишіть речення у вигляді умови:

a)      число а додатне;

b)      число х не більше 10;

c)      чи належить точка з координатами (x,y) осі ординат.

3)      Знайдіть значення величини P після виконання команди розгалуження, якщо значення величини а дорівнює:

a)      3

b)      2

c)      1

4)      Підберіть значення величини х, при якому умови: виконуються; не виконуються.

a)      x>=3;

b)      x<=0.

5)      Знайдіть значення величини C після виконання команди розгалуження, якщо значення величини m дорівнює:

a)      8

b)      7

c)      2

6)      Складіть алгоритм визначення типу хімічного розчину за реакцією лакмусового папірця.

7)      Складіть блок-схеми алгоритмів для знаходження значення y:

a)   

b)  

8)      Складіть алгоритм наповнення водою 25-літрової діжки за допомогою 3- літрової банки. Скільки разів треба виконати команди в циклі? Скільки літрів види переллється через край діжки?

9)      Які значення будуть мати змінні X та Y після виконання таки блок-схем:

a)    

б)  

10)  Складіть блок-схеми для обчислення суми:

a)      Знайти суму перших 50 натуральних чисел;

b)      Знайти суму значень натурального ряду чисел від 10-го по 70-е.

c)      Знайдіть суму парних двоцифрових  натуральних чисел.

11)  Є 10-20 деяких предметів. Два гравці по черзі беруть предмети, але не більше половини за один раз. Складіть алгоритм, який описує стратегію виграшу в грі в цьому випадку, коли програє той хто візьме останній предмет.

12) Скласти блок-схему алгоритму Евкліда знаходження найбільшого спільного дільника.

Перш ніж роз'яснити, в чому полягає суть алгоритму Евкліда, ми доведемо одну лему.

Лема. Нехай а і b – натуральні  числа і r – остача (лишок)  від ділення а на b. Тоді  найбільший спільний дільник чисел а і b  рівний найбільшому спільному  дільникові чисел b і r, тобто 

НСД(а, b) = НСД(b, r).

Доведення. Оскільки r - остача від ділення а на b, то ми можемо написати:

а = bq+r,

де q – деяке ціле число. Нехай с – деякий спільний дільник чисел а і b. Так як

r = а – bq,

то r  теж ділиться на c, тобто c є cпільним дільником чисел b і r.

Назад, нехай c' – деякий спільний дільник чисел b і r. Тоді число

а = bq + r

теж ділиться на c', тобто c' є cпільним дільником чисел а і b. Таким чином, числа а і b мають такі ж спільні  дільники, що і числа b і r. Це означає, що

НСД(а, b) = НСД(b, r).

Доведена лема і служить основою алгоритму для отримання  пар чисел за допомогою трьох автоматів. 

Для пояснення  алгоритму Евкліда ми розглянемо наступний приклад.

Приклад алгоритму Евкліда. Знайти НСД(645, 381).

Рішення. Розділимо (із залишком) 645 на 381. Ми отримаємо;

645 = 381*1+264.

По доведеній лемі НСД(645, 381) = НСД(381, 264). Значить, треба знайти (381, 264); ми помічаємо, що числа стали трохи менше. Розділимо (із залишком) 381 на 264. Ми отримаємо:

381 = 264*1 + 117.

По лемі НСД (381, 264) = НСД (264, 117). Значить НСД (645, 381) =  НСД (264, 117), отже залишається знайти (264, 117). Ми бачимо, що числа стало ще менше. Розділимо (із залишком) 264 на 117. Ми отримаємо:

264=117*2 + 30.

По лемі НСД (264, 117) = НСД (117,30). Значить НСД (645, 381) = НСД (117, 30), і залишається знайти НСД (117, 30). Розділимо (із залишком) 117 на 30. Ми отримаємо:

117 = 30-3 + 27.

По лемі НСД (117, 30) = НСД (30, 27). Значить НСД (645, 381) = НСД (30, 27). Далі

30 = 27-1+3.

По лемі НСД (30, 27) = НСД (27, 3). Значить НСД (645, 381) = НСД (27, 3). Далі

27=3-9 + 0,

т.   е.   27   ділиться    на   3.    Значить,   найбільший   спільний дільник чисел 27 і 3 рівний 3, тобто (27, 3) = 3. Таким чином, НСД(645, 381) = 3, тобто необхідний найбільший cпільний  дільник знайдений.