7. Завдання та мови для їх вирішення
Практика.
Завдання на переливання, перевіз. Логічні завдання.
Рішення логічних і логіко-арифметичних завдань
Лекція 0.2. Поняття, властивості, види запису алгоритмів
● поняття про алгоритм, його роль в обчисленнях
● алгоритмізація життєвих ситуацій
● спосіб запису алгоритму у вигляді блок-схеми
● основні властивості алгоритмів
Лекція 2. Основи алгоритмізації
План:
- Вступ (суть лекції)
- Поняття про алгоритм, його роль в обчисленнях
- Алгоритмізація життєвих ситуацій
- Спосіб запису алгоритму у вигляді блок-схеми
- Основні властивості алгоритмів
Що таке алгоритм?
"Перш, ніж що-небудь зробити, треба скласти план», - говорила Аліса з казки Льюїса Керролла. І в житті ми весь час складаємо плани наших дій, наприклад, вранці більшість з нас діє за таким планом:
встати
одягнутись
вмитися
поснідати
вийти з дому
У такому ж вигляді можна записати план для того, щоб заварити чай, зробити бутерброд з ковбасою, купити собі морозиво, вимити брудні руки, ...
В інформатиці план дій називають алгоритмом. Алгоритм складається з окремих кроків - команд. Жодну з них не можна пропустити, найчастіше ніякі команди не можна поміняти місцями (що при цьому відбудеться? Спробувати міняти «поснідати» раніше «встати», «одягтися» після «вийти», «вийти» раніше ніж «встати»).
Назва "алгоритм" походить від латинської форми імені видатного середньоазіатського математика Мухаммеда ібн Муса ал-Хорезмі (Alhorithmi), який жив у 783-850 рр.. У своїй книзі "Про індійський рахунок" він виклав правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними "стовпчиком", знайомі тепер кожному школяреві. У XII столітті ця книга була перекладена на латинь і набула широкого поширення в Європі.
Поняття алгоритму таке ж засадниче для інформатики, як і поняття інформації. Саме тому важливо в ньому розібратися. Людина щодня зустрічається з необхідністю слідувати тим чи іншим правилам, виконувати різні інструкції і вказівки.
В математиці для вирішення типових завдань ми використовуємо певні правила, що описують послідовності дій. Наприклад, правила додавання дробових чисел, рішення квадратних рівнянь і т. д. Зазвичай будь-які інструкції та правила являють собою послідовність дій, які необхідно виконати в певному порядку.
Для кожного кроку цього алгоритму можна запропонувати більш докладний план. Наприклад, для дії "поснідати":
закип'ятити чайник
зробити бутерброд
з'їсти бутерброд з чаєм
вимити посуд
І тут кожен крок, у свою чергу, теж можна розшифрувати - скласти більш докладний план. Де ж зупинитися? Відповідь проста - це залежить від виконавця - того, хто буде виконувати цей алгоритм. Треба зупинитися на такому плані, в якому виконавцю буде зрозуміло, як виконати кожен крок.
Виконавці
Що таке виконавець?
Виконавці часто зустрічаються в казках. В одній з них Іван-Царевич говорить хатинки-На-Курячих-ніжки: "Хатинка, хатинка! Встань до лісу задом, до мене передом! ". При цьому команда повинна бути задана дуже точно, щоб виконавець її зрозумів. У казці "Алі-Баба і сорок розбійників" чарівна двері відкривалися по команді "Сезам, відкрийся!". Жадібний Касим, таємно проник у печеру, забув цю фразу і не зміг вийти з печери.
І Хатинка-На-Курячих-ніжки, і чарівна двері мають багато спільного: вони вміють розуміти і виконувати деякі точно задані команди, тобто є виконавцями.
• Виконавець - це той, хто вміє розуміти і виконувати деякі команди.
Виконавця хаpактеpизующих:
• сpеда;
• cистема команд;
• відмови.
• Середа виконавця - це предмети, які оточують виконавця і з якими він працює.
• Список (або система) Команд Виконавця (СКІ) - набір команд, зрозумілих виконавцеві. Виконавець може виконати тільки ті команди, які входять в його СКІ.
Після виклику команди виконавець вчиняє відповідне елементарне
дію.
Виконавцями можуть бути
• люди: учень, робітник, вчитель, бригада;
• тварини: дресирована собака (санітар, розшукова, мисливський), кішка;
• машини: верстати, роботи, комп'ютери;
Зазвичай виконавець нічого не знає про мету алгоpітма. Він виконує всі отримані
команди, не задаючи питань "чому" і "навіщо".
Людина як виконавець відрізняється від всіх інших виконавців кількома ознаками, наприклад:
Розуміє команди в різних варіантах (наприклад "Сядь!", "Сідай!", "Сядь!").
Виконуючи команди, «додумує» їх з урахуванням свого досвіду.
Може відмовитися виконувати команду, якщо вона йому не подобається ("Їж манну кашу!", "Постріл у вікно з рогатки!"). Тобто людина має волю і відповідає за свої дії.
В інформатиці універсальним виконавцем алгоритмів є комп'ютер.
Для вирішення більшості завдань недостатньо віддати одну команду виконавцю, треба скласти для нього алгоритм - план дій, який складається з команд, які йому зрозумілі (входять в його СКІ). Таким чином, можна дати визначення алгоритму.
• Алгоритм - це точно визначений план дій виконавця, спрямований на вирішення якогось завдання. В алгоритм можна включати тільки ті команди, які є в СКІ виконавця.
Для вирішення завдання треба знати, що дано, що слід отримати і які дії і в якому порядку слід для цього виконати. Кажуть, що алгоритм приймає вихідні дані, а повертає результати. Припис, що визначає порядок виконання дій над даними з метою отримання шуканих результатів, і є алгоритм.
Це - не визначення в математичному сенсі слова, а, скоріше, опис інтуїтивного поняття алгоритму, що розкриває його сутність.
Поняття алгоритму є не тільки одним із головних понять математики, але одним з головних понять сучасної науки. Більш того, з настанням ери інформатики алгоритми стають одним з найважливіших чинників цивілізації.
Помилки при роботі виконавців
Робота виконавця не завжди проходить гладко - іноді зустрічаються помилки. Існує три види помилок виконавців.
|
"НЕ РОЗУМІЮ" (синтаксичні) |
Заданої команди немає в списку команд виконавця, і він її не зрозумів. Ймовірно, ми помилилися в запису тексту команди. |
|
"НЕ МОЖУ" (відмови) |
Виконавець зрозумів команду, але не може її виконати. Наприклад, роботу дана команда "вперед", а попереду стоїть стінка, і він не може йти. Або собаці скомандували "Сидіти!", А вона вже сидить. |
|
ЛОГІЧНІ ПОМИЛКИ |
Виконавець зрозумів команду і виконав її, але результат не той, що ми очікували. Причина цього - наша помилка в складанні завдання (алгоритму). |
Синтаксичні помилки і відмови виявляє сам виконавець. Коли ви будете працювати з комп'ютером, ви побачите повідомлення про таких помилках. Найскладніші помилки - логічні - доведеться шукати самим.
Як ввести нового виконавця?
• задати середовище виконавця;
• скласти СКІ:
• визначити, як передаються команди виконавцю (голосом, жестом, письмово, по рації або якось інакше);
• визначити, як виконавець виконує команди;
• визначити, в яких випадках виникає помилка "НЕ МОЖУ".
Старовинні задачі
Переправа. Селянину треба переправити через річку вовка, козу і капусту. Але крім людини човен вміщує лише або вовка, або козу, або капусту. Залишити на березі без нагляду вовка з козою чи козу з капустою не можна (З’їдять!). Як селянинові переправити свій вантаж?
Переправа сім'ї. Батько, мати і двоє дітей хочуть переправитися через річку. Всі вміють гребти, але човен витримує лише одного дорослого, або двох дітей. Як їм усім переправитися на інший берег?
Фальшиві монети. З 9 монет однакової гідності одна фальшива (легша). Як її знайти за два зважування за допомогою чашкових ваг без гир?
3 Посудини. У першу посудину входить 8 л, у другу - 5 л, в третю - 3 л. Першу посудину наповнено водою, а інші дві порожні. Як за допомогою цих посудин відміряти 1 л води?
У якій формі записуються алгоритми?
На практиці найпоширеніші такі форми подання алгоритмів:
• словесна (запис на природній мові);
• графічна (зображення з графічних символів);
• псевдокоду (напівформалізований опису алгоритмів на умовній алгоритмічній мові, що включає в себе як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та ін);
• програмна (тексти на мовах програмування).
Що таке словесний спосіб запису алгоритмів?
Словесний спосіб запису алгоритмів є опис послідовних етапів обробки даних. Алгоритм подається у довільному викладі природному мовою.
Наприклад. Записати алгоритм знаходження найбільшого спільного дільника (НСД)
двох натуральних чисел (алгоритм Евкліда).
Алгоритм може бути наступним:
1. задати два числа;
2. якщо числа рівні, то взяти будь-яке з них в якості відповіді і зупинитися, інакше продовжити виконання алгоритму;
3. визначити більше з чисел;
4. замінити більше з чисел різницею більшого і меншого з чисел;
5. повторити алгоритм з кроку 2.
Описаний алгоритм застосуємо до будь яких натуральних чисел і він повинен призводити до вирішення поставленого завдання. Переконайтеся в цьому самостійно, визначивши за допомогою цього алгоритму найбільший загальний дільник чисел 125 і 75.
Словесний спосіб не має широкого розповсюдження, оскільки такі описи:
• строго не формалiзуються,;
• страждають многословностю записів;
• допускають неоднозначність тлумачення окремих приписів.
Що таке графічний спосіб запису алгоритмів?
Графічний спосіб представлення алгоритмів є більш компактним і наочним порівняно зі словесним.
При графічному поданні алгоритм змальовується як послідовності пов'язаних між собою функціональних блоків, кожен з яких відповідає виконанню однієї або декількох дій.
Таке графічне представлення називається схемою алгоритму або блок-схемою. У блок-схемі кожному типу дій (введення вихідних даних, вирахування значень висловів, перевірці умов, управлінню повторенням дій, закінчення обробки і т.п.) відповідає геометрична фігура, представлена у вигляді блочного символу.
Блокові символи з'єднуються лініями переходів, визначальними черговість виконання дій. У таблиці наведено найбільш часто вживані символи.
Блок "процес" застосовується для позначення дії або послідовності дій, що змінюють значення, форму подання або розміщення даних. Для поліпшення наочності схеми кілька окремих блоків обробки можна об'єднувати в один блок. Подання окремих операцій досить вільно.
Блок "рішення" використовується для позначення переходів управління по умові. У кожному блоці "рішення" повинні бути вказані питання, умова або порівняння, які він визначає.
Блок "зумовлений процес" використовується для вказівки звернень до допоміжних алгоритмах, існуючи автономно у вигляді деяких самостійних модулів, і для звернень до бібліотечних підпрограм.
Наприклад, алгоритм Евкліда можна представити в такій формі:
Що таке псевдокод?
Псевдокод являє собою систему позначень і правил, призначену для однакового запису алгоритмів.
Псевдокод займає проміжне місце між природними і формальними мовами. З одного боку, він близький до звичайної природної мови, тому алгоритми можуть на ньому записуватися і читатися як звичайний текст. З іншого боку, в псевдокоді використовуються деякі формальні конструкції і математична символіка, що наближає запис алгоритму до загальноприйнятого математичного запису.
У псевдокоді не прийняті строгі синтаксичні правила для запису команд, властиві формальним мовам, що полегшує запис алгоритму на стадії його проектування і дає можливість використовувати більш широкий набір команд, розрахований на абстрактного виконавця.
Однак у псевдокоді зазвичай є деякі конструкції, властиві формальним мовам, що полегшує перехід від запису на псевдокоді до запису алгоритму на формальній мові. Зокрема, в псевдокоді, так само, як і в формальних мовах, є службові слова, зміст яких визначено раз і назавжди. Вони виділяються в друкованому тексті жирним шрифтом, а в рукописному тексті підкреслюються.
Єдиного або формального визначення псевдокоду не існує, тому можливі різні псевдокоди, що відрізняються набором службових слів і основних (базових) конструкцій.
Якими властивостями володіють алгоpітми?
Основні властивості алгоритмів наступні (приклад - кулінарний рецепт):
1. Зрозумілість для виконавця - виконавець алгоритму повинен розуміти, як його виконувати. Іншими словами, маючи алгоритм і довільний варіант вихідних даних, виконавець повинен знати, як треба діяти для виконання цього алгоритму.
2. Дискpетність (переривчастість, роздільність) - алгоpітм повинен пpедставляти пpоцесс pішення завдання як послідовне виконання пpосто (або pаніше визначених) кроків (етапів).
3. Визначеність - кожне пpавило алгоpитма повинно бути чітким, однозначним і не залишати місця для свавілля. Завдяки цій властивості виконання алгоpитма носить механічний хаpактеp і не тpебує ніяких додаткових вказівок або відомостей про розв'язок завдання.
4. Pезультативність (або кінцевість) полягає в тому, що за кінцеве число кроків алгоpитм або повинен пpиводитм до pішення завдання, або після кінцевого числа кроків зупинятися через неможливість отримати рішення з видачею відповідного повідомлення, або необмежено тривати протягом часу, відведеного для виконання алгоритму , з видачею проміжних результатів.
5. Масовість означає, що алгоpитм рішення завдання pозpобляєтся в загальному вигляді, тобто він повинен бути застосований для деякого типу задач, розрізняють лише вихідними даними. Пpи цьому вихідні дані можуть вибиратися з деякої області, яка називається областю застосовності алгоpитма.
Практичне Заняття 1
Алгоритмізація жіттєвої сітуації.
Приготування їжі, виконання побутового Завдання, Перехід через дорогу ТОЩО.
Практична Перевірка властивостей алгоритмом (результативність, дискретність, однозначність, скінченність).
Лінійні алгоритми.
Обрахунок площі, об'єму, значення функції і т.д.
7.2. Що таке "Виконавець алгоритму"?
Практика.
Найпростіщі завдання на алгоритмізацію. Складання лінійних блок-схем (Begin1, Begin7)
Робота з системами числення. Індивідуальні завдання.
Begin8, Begin11, Begin12, Begin20, Begin23, Begin25 (Абрамян М.Е. "Programming taskbook")
1-й місяць "Основні алгоритмічні структури"
Лекція 1. "Формальне представлення алгоритмічних структур, ч.1"
● оператор присвоювання;
● структура розгалуження;
● складні і вкладені розгалуження;
● побудова логічних умов в розгалуженях;
● логічні операції.
Базові алгоритмічні структури
Тема № 3 " Розгалуження " і тема № 4 "Цикли"
Що таке базові алгоритмічні структури?
Алгоритми можна представляти як деякі структури, що складаються з окремих базових (тобто основних) елементів. Природньо, що при такому підході до алгоритмів вивчення основних принципів їх конструювання має починатися з вивчення цих базових елементів. Для їх опису будемо використовувати мову схем алгоритмів.
Логічна структура будь-якого алгоритму може бути представлена комбінацією трьох базових структур:
слідування, розгалуження, цикл.
Характерною особливістю базових структур є наявність у них одного входу і одного виходу.
1. Базова структура "слідування". утворюється послідовністю
дій, наступних одне за іншим:
У лінійному алгоритмі команди виконуються послідовно, одна за одною. Прикладом лінійного алгоритму може служити алгоритм заварки чаю:
закип'ятити воду
сполоснути заварювальний чайник гарячою водою
насипати заварку
залити заварку окропом
закрити чайник чим-небудь теплим
почекати 5 хвилин
... тепер можна пити чай
Лінійний алгоритм переходу через дорогу:
1. Підійти до пішохідного переходу
2. Переконатися що не має машин праворуч
3. Перейти половину дороги
4. Переконатися що немає машин зліва
5. Перейти половину дороги
Що буде якщо на дорозі є світлофор?
2. Базова структура "розгалуження". Забезпечує в залежності від результату
перевірки умови (так чи ні) вибір одного з альтернативних шляхів роботи алгоритму.
Кожен з шляхів веде до загального виходу, так що робота алгоритму триватиме незалежно від того, який шлях буде обраний. Структура розгалуження існує в двох основних варіантах:
• якщо-то;
• якщо-то-інакше;
У розгалуженому алгоритмі порядок проходження команд може бути різний залежно від того, яке навколишнє оточення. Прикладом розгалуженя алгоритму може служити алгоритм переходу вулиці:
1. підійти до пішохідного переходу
якщо є світлофор, то
{
2. чекати зеленого світла
3. перейти вулицю
}
інакше
{
4. Переконатися що немає машин праворуч
5. Перейти половину дороги
6. Переконатися що немає машин ліворуч
7. Перейти половину дороги
}
Розпишемо 4 і 6 кроки детальніше.
1. підійти до пішохідного переходу
якщо є світлофор, то
{
2. чекати зеленого світла
3. перейти вулицю
}
інакше
{
4. подивитися праворуч.
Якщо машин немає, то
{
5. перейти половину дороги,
}
інакше,
{
6. чекати, поки вони проїдуть,
7. перейти половину дороги.
}
8. подивитися ліворуч,
Якщо машин немає, то
{
9. перейти дорогу до кінця,
}
інакше,
{
10. чекати, поки вони проїдуть,
11. перейти дорогу до кінця.
} }
Завдання по темі:
Розділ Boolean: 1, 2, 6, 9,16, 18, 20
3. Базова структура "цикл".
Забезпечує багаторазове виконання деякої сукупності дій, що називається тілом циклу. Основні різновиди циклів, це цикл з передумовою, цикл з пост умовою і цикл з параметром. Два останніх типи циклів ми розглянемо пізніше, а поки більш детально познайомимося з основною циклічною структурою, за допомогою якої ми в основному і будемо вирішувати завдання - цикл з передумовою (цикл типу ПОКИ).
У циклічному алгоритмі деякі дії повторюються кілька разів (в інформатиці кажуть, що виконується цикл). Виникає питання чому не можна просто багато раз підряд переписати команди, які потрібно виконувати в циклі? По-перше, це незручно, по-друге, громіздко, особливо при великій кількості необхідних повторів, а по-третє, це головне, ми не завжди знаємо заздалегідь скільки саме кроків нам доведеться виконати для конкретних значень вхідних даних. Замість цього число кроків обмеженого деякою умовою - як кажуть умовою виходу з циклу.
Приклад такого циклу - алгоритм розпилювання колоди: ми не можемо заздалегідь сказати, скільки разів нам треба провести пилкою від себе і на себе - це залежить від щільності дерева, якості пилки і наших зусиль. Однак ми точно знаємо, що треба закінчити роботу, коли чергове відпиляне поліно впаде на землю.
/* Число кроків невідомо,,
але обмеженоумовою*/
покласти колоду на козли
намітити місце розрізання
поки поліно не відвалиться
{
пиляти від себе
пиляти на себе
}
покласти поліно в стіс
Перехід через дорогу з використанням циклу:
1. підійти до пішохідного переходу
якщо є світлофор, то
{
Поки (немає зеленого світла)
{
2. стояти
}
3. перейти вулицю
}
інакше
{
4. подивитися праворуч.
Якщо машин немає, то
{
5. перейти половину дороги,
}
інакше,
{
Поки (тобто машини)
{
6. стояти
}
7. перейти половину дороги.
}
8. подивитися ліворуч,
Якщо машин немає, то
{
9. перейти дорогу до кінця,
}
інакше,
{
Поки (тобто машини)
{
10. стояти
}
11. перейти дорогу до кінця.
}
}
Програми
Людина здатна розуміти сенс команди і часто може «додумати», що від нього хотіли навіть тоді, коли команда задана неточно. Для того, щоб алгоритм був зрозумілий роботові, комп'ютеру або іншій машині, недостатньо лише написати команди, треба ще й оформити алгоритм у такому вигляді, в якому його розуміє машина, тобто записати в формальному вигляді.
У формальному записі алгоритму можна використовувати тільки ті команди, які входять в СКІ виконавця. Крім того, треба дотримуватися спеціальних правил оформлення, які дозволять виконавцю розпізнати команди і визначити послідовність їх виконання.
/* Це назва алгоритму*/
{
/ * Ця дужка позначає початок алгоритму*/
;
посадити ріпку/* команд а закінчується знаком
;*/
виростити ріпку;
намагатися витягти ріпку;
покликати Бабку; намагатися витягти ріпку;
покликати Внучку; намагатися витягти ріпку;
покликати Жучку; намагатися витягти ріпку;
покликати Кішку; намагатися витягти ріпку;
покликати Мишку; витягнути ріпку;
/* Тут алгоритм закінчується */
}
Виконавцем для цього алгоритму є дід - саме він повинен виконувати ці команди.
Правила запису алгоритмів для комп'ютерів
Алгоритм можна записати різними способами і навіть на різних мовах. Хоча при цьому виконавець може, звичайно, їх не зрозуміти. Ви знаєте, що є спеціальні види виконавців алгоритмів - комп'ютери. Вони виконують програми.
Програма - це алгоритм, записаний у формі, зрозумілій комп'ютеру.
Існують спецяльні правила запису програм для комп'ютерів. На малюнку вгорі сторінки їх характерні елементи виділені в рамках:
1.будь-який алгоритм має назву;
2.алгоритм починається з відкриваючої фігурної дужки "{" і закінчується закриваючою фігурною дужкою "}"; команди, розташовані між цими дужками, називаються тілом алгоритму;
3. в алгоритм можуть входити тільки ті команди, які є в СКІ виконавця;
4. кожна команда закінчується знаком ";", який позначає кінець команди;
5.для того, щоб нам було легше розбиратися в програмах, використовують коментарі - текстові пояснення, які починаються знаками / * і закінчуються знаками * /; виконавець не звертає уваги на коментарі в алгоритмі.
Незалежно від того, на якій мові програмування буде написана програма, алгоритм розв'язання будь-якої задачі на ЕОМ може бути складений з команд:
• проходження, включає в себе:
• присвоювання;
• введення;
• висновок;
• цикл;
• розгалуження;
• звернення до допоміжного алгоритму.
Практика.
Дано три цілих числа: A, B, C. Перевірити істинність висловлювання: «Справедливо подвійне нерівність A <B <C».
Дано три цілих числа: A, B, C. Перевірити істинність висловлювання: «Рівно два з чисел A, B, C є позитивними».
Дано два числа. Вивести більше з них.
Дано три числа. Знайти суму двох найбільших з них.
Лекція 2. "Формальне представлення алгоритмічних структур, ч.2"
● структура "цикла";
● цикл з передумовою;
● цикл з марнослівністю;
● цикл з параметром.