Міністерство транспорту та зв’язку України

Державний департамент з питань зв’язку та інформатизації

ДЗ “Київський коледж зв’язку”

РОБОЧИЙ ЗОШИТ

з предмету

ПРОГРАМУВАННЯ ТА АЛГОРИТМІЧНІ МОВИ

Прізвище_______________________________________________

Ім’я____________________________________________________

По батькові_____________________________________________

Група __________________________________________________

Варіант_________________________________________________

Київ 2010 р

ВСТУП

Шановний Студенте, даний зошит призначений для твоєї роботи з предмету “Програмування та алгоритмічні мови” на усіх видах заняттях і при самопідготовці до них.

Робочий зошит містить:

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

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

• Домашнє завдання, яке обов’язково потрібно виконувати.

• Тренувальні вправи, які тобі допоможуть підготуватися до будь-якої самостійної чи контрольної роботи.

• Задачі для самоконтролю. До частини цих вправ є відповіді, що допоможе перевірити правильність її розв’язання.

• Загальні відомості до практичних та лабораторних робіт.

• Завдання та методичні вказівки для самостійної роботи студента, яке обов’язково має бути виконане до наступного заняття.

• Перелік екзаменаційних питань та типових задач, які допоможуть у підготовці до екзамену

• Список літератури та довідкових джерел для самопідготовки, який подається і кінці кожного розділу.

Зошит потрібно носити на кожну пару, оскільки без нього робота на парі не можлива.

Бажаю успіхів!!!!

Розділ І. Алгоритми розв’язування задач

Лекція №1 (2 години)

Тема 1.1. Поняття алгоритму. Базові структури алгоритмів.

Опорний конспект

Алгор́итм, алгорифм (латинізов. Algorithmi, від імені узбецького математика 9 ст. аль-Хорезмі) — система правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій.

Властивості алгоритмів

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

2. Скінченність. Виконання кожного алгоритму повинно завершуватись за скінчене число кроків. При виконанні алгоритму деякі кроки можуть повторюватись.

3. Результативність. Виконання алгоритму завжди повинно приводити до певного результату (можливо, негативного). Воно не може закінчуватись невизначеною ситуацією або ж не закінчуватись взагалі. Алгоритм вказує послідовність дій по переробці даних в результати. Якщо задача немає розв’язку, то цей випадок також повинен бути врахований в алгоритмі.

4. Формальність. Виконавець відповідно до алгоритму повинен одержати результат, не вникаючи в його суть. Результат не повинен залежати від яких-небудь факторів, що не є частиною алгоритму. Команди повинні бути зрозумілі виконавцеві і входити в систему команд виконавця.

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

6. Масовість. За допомогою складеного алгоритму повинен розв’язуватись цілий клас однотипних задач.

7. Правильність. Алгоритм правильний, якщо його виконання забезпечує досягнення мети.

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

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

Способи подання алгоритмів.

1. Символьний. Символьне представлення поділяється на записи:

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

б) штучною мовою. Серед штучних мов виділяють:

1) мови програмування. У вигляді програм, написаних певною мовою програмування.

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

2. Графічний. Графічне подання алгоритмів, в свою чергу, поділяється на представлення алгоритму у вигляді:

а) блок-схем;

б) структурних схем (структурограм, діаграм, );

Базові структури алгоритмів

1. Лінійні;

2. Розгалужені (умови):

• повні;

• не повні;

Циклічні:

• з передумовою;

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

• з параметром.

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

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

• введення початкових даних;

• обчислення за формулами;

• виведення результату.

Приклад 1.

Скласти алгоритм обчислення і роздрукування значення виразу у=(Ах+В)(Сх+D).

Розв’язування:

1. Задати значення А, В, С, D, х;

2. Обчислити у = (Ах+В)(Сх+ D);

3. Надрукувати у;

4. Процес обчислення завершити.

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

Приклад 2.

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

Розв’язування:

1. Задати значення а, b, с;

2. Якщо а>=b, то d=a, інакше d=b;

3. Якщо d>=c, то y=d, інакше у=c;

4. Надрукувати значення у;

5. Процес обчислення завершити.

Для більшості обчислювальних процесів є характерним цикл.

Цикл – послідовність дій, що повторюються багато разів.

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

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

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

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

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

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

Приклад 3.

Скласти алгоритм обчислення суми цілих чисел від 1 до 100.

Розв’язування:

1. Присвоїти початкові значення S=0; х=1.

2. Поки х<=100, виконувати команди: S=S+х; х=х+1.

3. Надрукувати значення S.

4. Процес обчислення завершити.