69891

Алгоритми і форми його представлення. Основні структури алгоритмів

Лабораторная работа

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

Мета: набуття навичок побудови блоксхем при розв’язуванні алгоритмічних задач. Блоксхеми. Побудувати блоксхему. Теоретичні відомості Основні форми представлення алгоритмів: словесний опис алгоритму; графічне представлення алгоритму блоксхема; мова псевдокодів...

Украинкский

2014-10-12

572.12 KB

1 чел.

Лабораторна робота №1

Тема. Алгоритми і форми його представлення. Основні структури алгоритмів

Мета: набуття навичок побудови блок-схем при розв’язуванні алгоритмічних задач.

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

Теоретичні питання (план)

  1.  Властивості алгоритмів.
  2.  Форми представлення алгоритмів.
  3.  Блок-схеми.
  4.  Основні структури алгоритмів.

Хід виконання роботи

  1.  Ознайомтеся з основними теоретичними відомостями.
  2.  Згідно номеру свого варіанту оберіть умову задачі.
  3.  Розробити алгоритм розв’язання задачі.
  4.  Побудувати блок-схему.

Теоретичні відомості

Основні форми представлення алгоритмів:

  1.  словесний опис алгоритму;
  2.  графічне представлення алгоритму (блок-схема);
  3.  мова псевдокодів;
  4.  представлення алгоритму мовою програмування (програма).

Приклад 1. Скласти словесний опис алгоритму обчислення об’єму (V) прямокутного циліндра за радіусом(r) основи і висотою (h).

1. Початок алгоритму.

2. Ввести вхідні дані: r, h.

3. Обчислити обсяг по формулі: V=πr2 h.

4. Вивести V.

5. Кінець алгоритму.

Блок-схема – наочне графічне зображення алгоритму у вигляді стандартних блоків, з'єднаних стрільцями. Умовна позначка блоків, їхнє призначення і найменування приведені в табл. 1.1. Блок-схема читається зверху вниз, і в цьому випадку стрілки на лініях потоку можна не вказувати.

Таблиця 1.1

Умовні позначки в блок-схемах

Найменування блоку

Позначення блоку

Опис блоку

Початок/кінець

Початок або завершення алгоритму

Введення/виведення

Введення /виведення даних

Процес

Виконання арифметичних операцій

Рішення

Перевірка умови

Модифікація

Заголовок циклу

Лінії потоку

Зображення зв’язків між блоками

Внутрішньосторінковий з’єднувач

Вказівка зв’язку між перерваними лініями потоку в межах однієї сторінки

Міжсторінковий з’єднувач

Вказівка зв’язку між частинами блок-схеми, розташованими на різних сторінках

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

Лінійний алгоритм

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

Приклад лінійного алгоритму – алгоритм обчислення об’єму (V) прямокутного циліндра за радіусом (r) основи і висотою (h). Блок-схему показано на рис. 1.1. Алгоритм лінійної структури реалізується в такий спосіб. Початок обробки даних – блок 1. Для проведення обчислень здійснюється введення в блоці 2 вихідних даних (значень r і h). У блоці 3 обчислюється об’єм циліндра V. Після обчислень здійснюється виведення результату (блок 4) і зупинка (блок 5).

Рис. 1.1. Приклад лінійного алгоритму

Алгоритм розгалуження

Алгоритм розгалуження застосовується в тих випадках, коли в залежності від умови необхідно виконати одну або іншу групу дій. На рис. 1.2 показано блок-схему алгоритму, що розгалужується. Окремий випадок розгалуження – обхід, коли по гілці «ні» ніяких дій виконувати не треба (блок-схема обходу – на рис. 1.3).

Рис. 1.2. Блок-схема розгалуження    Рис. 1.3. Блок-схема обходу

Приклад 2. Обчислити значення f по одній із трьох формул – у залежності від значення x:

Блок-схема алгоритму даної задачі наведена на рис. 1.4.

Для обчислення значення f потрібно перевірити два з трьох взаємовиключних умов (для x<-1 і x>5). Після введення вхідних даних (блок 2) перевіряється перша умова x<-1 (блок 3). Якщо вона виконується, то значення f визначається по першій гілці формули (блок 4). У протилежному випадку перевіряється кожна з умов, що залишилися, (вони взаємовиключні). У даному випадку в блоці 5 перевіряється умова x>5. Якщо вона виконується, то значення f визначається по третій гілці формули (блок 6), у протилежному випадку – по другій гілці в блоці 7. У блоці 8 здійснюється виведення результату.

Рис. 1.4. Приклад алгоритму розгалуження

Циклічний алгоритм

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

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

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

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

Цикли з відомим числом повторень

Це цикли, у яких керуюча змінна змінюється у відомих межах по відомому закону. Найпростіший випадок – коли керуюча змінна i змінюється від свого початкового значення iн до кінцевого значення iк із кроком Δi. Трійка величин (iн, iк, Δі) називається параметрами циклу.

На рис. 1.5–1.7 представлені різні варіанти організації такого циклічного процесу. На рис. 1.5 показана організація циклу з післяумовою; на рис. 1.6 – циклу з передумовою; на рис. 1.7 – циклу з блоком “модифікація”. Останні дві блок-схеми еквівалентні у тому сенсі, що реалізують той самий обчислювальний процес. Тому, щоб зрозуміти, як працює блок модифікації 1.7, досить звернутися до циклу з передумовою 1.6.

Рис. 1.5. Цикл з післяумовою    Рис. 1.6. Цикл з передумовою

Рис. 1.7. Цикл із блоком «модифікація»

Якщо Δi=1, то в блоці “модифікація” значення Δi не вказують. Кількість m повторень (ітерацій) циклу обчислюється по формулі: m = [(iк - iн) / Δi + 1], де [(iк - iн) / Δi + 1] – ціла частина величини (iк - iн) / Δi.

Приклад 3. Обчислити значення функції , при 2 ≤ x ≤8, Δx = 0,4. Значення a, b, c задані.

Для розв’язання цієї задачі потрібно в циклі перебрати всі значення x від xн=2 до xк=8 із кроком Δx = 0,4 і для кожного з них отримати значення y. Різні варіанти реалізації циклічного процесу для даної задачі показані на рис. 1.8 - 1.10.

Рис. 1.8. Обчислення у (цикл ПОКИ)   Рис. 1.9. Обчислення у (цикл ДО)

Рис. 1.10. Обчислення у (цикл із блоком «модифікація»)

Цикли з невідомим числом повторень

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

Цикли з невідомим числом повторень можуть бути двох типів – із передумовою (їх також називають циклами ПОКИ) і з постумовою (цикли ДО). Блок-схеми цих циклів показані на рис. 1.11 і 1.12.

Рис. 1.11. Цикла ПОКИ (з передумовою)   Рис. 1.12. Цикл ДО (з післяумовою)

Зазначимо, що умови, які перевіряються в цих циклах, взаємопротилежні: у циклі ПОКИ перевіряється умова продовження циклу, а в циклі ДО – умова виходу з циклу.

Особливість циклу ПОКИ: якщо при першій перевірці умова продовження порушується, то тіло циклу не буде виконане жодного разу.

Особливість циклу ДО: тіло циклу завжди виконується хоча б один раз.

В обчислювальному плані ці цикли еквівалентні, тобто в алгоритмі завжди можна замінити цикл ПОКИ циклом ДО і навпаки.

Приклад 4. Обчислити значення y по формулі для x≥1, Δx=0,8. Обчислення y виконувати доти, поки значення x3 стане більше a. Визначити кількість обчислених значень y. Вивести всі значення y та їхню кількість.

Особливістю цієї задачі є те, що для організації циклу неможливо використовувати блок модифікації, тому що невідоме кінцеве значення параметра x, при якому буде досягнута умова x3>a. Блок-схема розв’язання задачі представлена на рис. 1.13.

У блоці 2 відбувається введення значень a, xн, Δx. У блоці 3 присвоюються початкові значення змінній x, лічильникові кількості повторень циклу k. У блоці 4 перевіряється умова продовження циклу: поки умова виконується, у блоці 5 обчислюються значення y, у блоці 6 виводяться значення змінних x і y, підготовлюються значення змінних x і k для наступного проходження циклу. Як тільки змінна x досягне такого значення, що x3>a, виводиться значення лічильника k (блок 8) і алгоритм завершується.

Рис. 1.13. Приклад циклу з невідомим числом повторень

Варіанти завдань

Завдання 1.

І. Розробіть алгоритм розв’язання задачі та побудуйте блок-схему. Запишіть алгоритм мовою псевдокодів.

1. Обчислити площу кругу й об’єм кулі за заданим радіусом.

2. Перерахувати швидкість вітру з «м/сек» у «м/хв» і «км/година».

3. Обчислити довжину кола і площу кругу того самого заданого радіуса.

4. Обчислити периметр і площу прямокутного трикутника за довжинами двох його катетів.

5. Обчислити катети прямокутного трикутника за заданою гіпотенузою і прилеглому до неї кутом в градусах.

6. Обчислити висоту і площу рівностороннього трикутника за заданою стороною.

7. Перерахувати масу з фунтів у грами і кілограми (1фунт = 409,5 г).

8. Обчислити швидкість автомобіля (км/година), якщо відомо пройдена їм відстань (км) і час (години плюс хвилини).

9. Перерахувати заданий обсяг файлу з кілобайтів у байти, біти і мегабайти.

10. Обчислити силу струму (в амперах) в електричному ланцюзі за відомими напругою (у вольтах) і опором (в омах).

11. Перерахувати задану температуру з градусів Цельсія (З) у градуси Фаренгейта (F) і градуси Кельвіна (ДО) за формулами: F = (9/5)C+32; K = (F+459,7)/1,8.

12. Перерахувати задану відстань з метрів у ярди і фути, якщо 1ярд = 914,4мм; 1фут = 304,8мм.

13. Перерахувати заданий кут із градусів у радіани і знайти його синус і косинус.

14. Для кута, заданого в градусах, знайти суму його синуса і косинуса.

ІІ. Розробіть алгоритм розв’язання задачі (табл.1.2) та побудуйте блок-схему.

Таблиця 1.2

№ варіанту

Завдання

Вихідні дані

1.

с=3

x=0,64

y=5,1

2.

m=0,8

t=4

a=2,25

3.

y=0,8

x=3,0

i=4,6

a=1.5

4.

a=3,1

b=1,4

d=0,06

5.

m=0,2

x=0,17

6.

g=0,91

a=3

x=1

i=2,4

7.

m=0,8

p=1,7

k=4

x=0,005

8.

k=3,7

a=2,61

x=10

9.

c=1,2

s=2

a=6

10.

t=5,6

k=2,8

x=0,7

11.

b=5,8

a=2

x=1,62

12.

y=2

m=3,25

13.

f=2,81

c=-2

14.

y=3

k=5,6

x=1,8

Завдання 2. Побудувати блок-схему, використовуючи оператор умовного переходу (табл. 1.3) та оператор варіанту (табл. 1.4). Запишіть алгоритм мовою псевдокодів.

Таблиця 1.3

№ варіанта

Зміст завдання

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

Таблиця 1.4

№ варіанту

Зміст завдання

Вхідні дані

1.

A=2

B=1.5

C=1

D=3

F=0.5

2.

C=-2

A=1.5

D=2

X=3

3.

A=5

B=1.2

Y=0.3

4.

D=2

A=3.5

X=3

I=2.3

5.

Y=1

X=2.5

A=4

B=0.4

6.

A=0.5

B=2

H=4

R=1.4

7.

P=0.6

L=2

H=5

R=4

8.

X=0.65

C=1.5

D=2

A=0.37

9.

Y=2.6

X=1.6

A=0.4

10.

A=1.5

B=2

X=0.5

11.

X=0.5

A=4.3

Y=2.6

D=0.3

12.

A=3

Y=2.7

I=2

X=1

13.

X=0.73

Y=0.4

T=2.6

14.

A=2

X=0.54

C=2.3

B=1.8

R=3

Завдання 3. І. Складіть алгоритм мовою псевдокодів і побудуйте блок-схему розв’язання задачі, використовуючи структуру циклу з передумовою і післяумовою.

ІІ. Складіть алгоритм мовою псевдокодів і побудуйте блок-схему розв’язання задачі, використовуючи структуру циклу з відомими числом повторень.

Рекомендована література

Базова

  1.  Ахо А.В. Структуры данных и алгоритмы / Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д./ М: Вильямс, 2003.— 384 с.
  2.  Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — 360 с.

Допоміжна

  1.  Исследование операций / Под ред. Дж.Моудера, С.Элмаграби. - Т. 1,2.-М.: Мир, 1981-712 с.

Інформаційні ресурси:

  1.  http://stud.zu.edu.ua/study/Metods_Optimazation/Linear_Programming.pdf
  2.  http://stud.zu.edu.ua/study/Metods_Optimazation/Metods_Optimazation_Theory.pdf

Зміст звіту

Тема роботи; умова задачі; структура основних вхідних та вихідних даних, алгоритм розв’язання задачі; блок-схема, висновки за результатами розв’язання.

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

  1.  Що розуміється під алгоритмом?
  2.  Перерахуйте основні властивості алгоритмів.
  3.  Назвіть базові конструкції алгоритмів
  4.  Які процеси описують лінійні алгоритми?
  5.  Яка основна структура написання умовного оператора? Які існують види умовних операторів?
  6.  Яка основна структура написання оператора вибору і як він працює?
  7.  Які види циклічних алгоритмів ви знаєте? У чому їх відмінність?
  8.  Як працює оператор циклу з параметром?
  9.  У якому випадку зручно використовувати оператор циклу з параметром?


 

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

51198. Цифровое управляющее устройство в контуре управления 660.15 KB
  Для отработки блока дискретизации рассмотрена система с неидеальным запаздывающим АС.1 Система неустойчива 0.4 Система неустойчива 0.1 Система неустойчива 0.
51199. Анализ влияния дискретизации на перерегулирование 55.18 KB
  Цель: сравнение результатов с идеальным и неидеальным АС на одном графике при различных h. Результаты исследования влияния т и h на уравнение с неидеальным...
51200. Анализ влияния дискретности цифровой системы управления на параметры автоколебаний в системе с релейными исполнительными органами 559.64 KB
  Определить зависимость частоты и размаха автоколебаний от величины Мупр а0 и а1 при h = 1. Определить зависимость частоты и размаха автоколебаний от величины Мупр а0 Т при h = 50. Определили зависимость частоты и размаха автоколебаний от величины Мупр а0 и а1 при различных h. Результаты исследования влияния а0 и h на уравнение моделирующее работу цифровой системы управления с релейными и...
51201. Исследование биполярного транзистора 497.57 KB
  Цель работы: изучение свойств биполярного транзистора в режиме постоянного тока и при переменном сигнале в зависимости от схемы его включения. Характеристики биполярного транзистора П306А: Тип прибора Проводимость Предельные значения параметров при Т=25С Значения параметров при Т=25С П306А pnp 80 04 10 005 535 01 60120 Схемы установок для исследования транзисторов: Рис.1 Схема с общей базой для исследования выходных статических характеристик биполярного транзистора...
51202. Разработка интерпретатора текстовой (теговой) разметки документа 148.66 KB
  Идея языков разметки состоит в том, что визуальное отображение документа должно автоматически получаться из логической разметки и не зависеть от его непосредственного содержания. Это упрощает автоматическую обработку документа и его отображение в различных условиях (например, один и тот же файл может по-разному отображаться на экране компьютера, мобильного телефона и на печати...
51203. Аналитическое моделирование дискретно-стохастической СМО 241.97 KB
  Цель: Построить граф состояний СМО . Смысл кодировки состояний раскрыть (время до выдачи заявки, число заявок в накопителе и т.д.). На схеме условно обозначены
51204. Построение аналитической и имитационной модели одноканальной СМО с неограниченной очередью и ее исследование 56.42 KB
  Цель: Имеется n-канальная СМО с неограниченной очередью. Входной поток и поток обслуживаний - простейшие с интенсивностями и соответственно. Время пребывания в очереди ограничено случайным сроком , распределенным по показательному закону с математическим ожиданием...
51206. Построение синтаксического дерева 53.35 KB
  Включить в синтаксический анализатор из лабораторной работы №.3 построение синтаксического дерева. Использовать атрибутный метод Кнута, т.е. преобразовать КС–грамматику из лабораторной работы № 3 в атрибутную грамматику добавлением атрибутов и правил построения синтаксического дерева. Расширить программу синтаксического анализатора из лабораторной работы...