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.  У якому випадку зручно використовувати оператор циклу з параметром?


 

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

16912. Порядок разработки теста в OpenOffice.org Calc 126.5 KB
  Лабораторная работа № 15 Порядок разработки теста в OpenOffice.org Calc Оборудование: ПЭВМ Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть. Тест на тему ЛИЧ...
16913. Логические функции в OpenOffice.org Calc 203.5 KB
  Лабораторная работа № 16 Логические функции в OpenOffice.org Calc Оборудование: ПК Программное обеспечение:Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть Логические функции в OpenOffice.org Calc: 1. IF Условие; Выр
16914. Создание диаграммы в OpenOffice.org Calc 120 KB
  Лабораторная работа №17 Создание диаграммы. Оборудование: ПЭВМ Программное обеспечение: OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc. Таблица 1. Запустите OpenOffice.org Calc. Сохраните...
16915. Работа с несколькими листами в OpenOffice.org Calc 89.5 KB
  Лабораторные работы № 18Работа с несколькими листами Оборудование: ПК Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Задание: 1. Запустить OpenOffice.org Calc. 2. Вычислить объем продаж в магазине То
16916. Решение практических задач в Windows EXCEL 53 KB
  Лабораторная работа № 1920 Решение практических задач. Оборудование: ПЭВМ Программное обеспечение: Windows EXCEL. Цель работы: приобретение и закрепление практических навыков работы в EXCEL Логические функции в EXCEL: ЕСЛИ Условие; Выражение
16917. Создание базы данных в Windows, Access 70 KB
  Лабораторная работа № 21 Создание базы данных Оборудование: ПЭВМ Программное обеспечение: Windows Access. Цель работы: приобретение и закрепление практических навыков работы в Access Общие характеристики MS Access. Структура базы данных Система управления базами
16918. Создание простых запросов в Windows, Access 73.5 KB
  Лабораторная работа № 22 Создание простых запросов. Оборудование: ПЭВМ Программное обеспечение: Windows Access Цель работы: приобретение и закрепление практических навыков работы в Access Выбор записей отвечающих определенному условию можно осуществить как с
16919. Создание реляционной базы данных. Разработка инфологической модели и создание структуры реляционной базы данных 133.5 KB
  Разработка инфологической модели и создание структуры реляционной базы данных Для разработки инфологической информационно-логической модели базы данных выделим три объекта: Студенты Дисциплины и Преподаватели. Типы связей между этими
16920. Формирование сложных запросов в Windows, Access 86 KB
  Лабораторная работа № 2425 Формирование сложных запросов Оборудование: ПЭВМ Программное обеспечение: Windows Access Цель работы: приобретение и закрепление практических навыков работы в Access Задание 1. Формирование сложных запросов Создайте следующие зап