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


 

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

5856. Индивидуальная предпринимательская деятельность 49.5 KB
  Индивидуальная предпринимательская деятельность обладает ограниченными возможностями и распространяется в основном на мелкий бизнес. Для более или менее крупного дела приходиться соединять усилия нескольких лиц, переходить к коллективному п...
5857. Специальные основные системы метода сил 127 KB
  Специальные основные системы метода сил 1. Статически неопределимые фермы Фермы, применяемые в строительстве, строго говоря, всегда статически неопределимы в силу жесткости узлов. Мы будем понимать под статически неопределимой фермой ее расчетную сх...
5858. Рациональные основные системы метода сил для рам 103.5 KB
  Рациональные основные системы метода сил для рам. Решение статически неопределимых рам методом сил вручную оказывается довольно громоздким, с обилием вычислений и проверок. При этом выбор основной системы предопределяет объем вычислений и характер р...
5859. Основы метода сил 97.5 KB
  Основы метода сил Основные понятия о статически неопределимых стержневых системах. Их свойства. Методы расчета. Статически неопределимыми стержневыми системами назовем такие, для расчета которых недостаточно одних уравнений равновесия. Другими с...
5860. Внедрение стратегии 260 KB
  Внедрение стратегии. Необходимость предпринимательских качеств. Суть проблемы. В середине 1950–х годов американская промышленность столкнулась с крупными неприятностями. Спрос на продукцию некоторых компаний стабилизировался его не мог...
5861. Великие итальянские художники эпохи возрождения 67 KB
  Великие итальянские художники эпохи возрождения. Народы Европы стремились к возрождению сокровищ и традиций, утраченных из-за бесконечных истребительных войн. Войны уносили с лица земли и людей, и то великое, что люди создавали. Идея возродить...
5862. Схема внутрицехового электроснабжения до 1000 в 1.46 MB
  Сети напряжением до 1 кВ служат для распределения электроэнергии внутри цехов промышленных предприятий, а также для питания некоторых ЭП, расположенных за пределами цеха на территории предприятии. Цеховые электрические сети напряжением до ...
5863. Виды конституций по порядку изменения и отмены 77 KB
  По способу изменения и внесения поправок конституции делятся на две группы: жесткие и гибкие. Эти два понятия теснейшим образом связаны с классификацией конституций на писанные и неписанные. Деление конституций на писаные и неписаные достат...
5864. Управление манипуляторами промышленного робота 448.5 KB
  Управление манипуляторами промышленного робота Если динамические уравнения движения манипулятора заданы, целью управления манипулятором является выполнение им движений в соответствии с заданным рабочим критерием. Проблема управления манипулятором в ...