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


 

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

82234. Wir lesen gern. Ми охоче читаємо 38.5 KB
  Мета: Узагальнення та систематизація знань учнів, навчання монологічного та діалогічного мовлення в межах даної теми, тренування навичок аудіювання, навчання виразному читанню та віршованому перекладу поезії класиків німецької літератури. Розвивати мовленнєві, інтелектуальні та пізнавальні здібності учнів.
82235. Социально-гуманитарные науки (СГН) как феномен, зародившийся на Западе, его общечеловеческое значение 34.93 KB
  Предпосылки науки создавались в древневосточных цивилизациях Египте Вавилоне Индии Китае Древней Греции в форме эмпирических знаний о природе и обществе в виде отдельных элементов зачатков астрономии этики логики математики и др. а в тех реальных общественноисторических социокультурных факторах которые еще не создали объективных условий для формирования науки как особой системы знания своеобразного духовного феномена и социального института в этом целостном триединстве . Таким образом в античный и средневековый периоды...
82236. Субъект, объект и предмет познания в социально-гуманитарных науках. Проблема межпредметных связей 48.72 KB
  Субъект социально-гуманитарного познания это специально подготовленный ученый или группа ученых которые изучают различные сферы общества продукты духовной деятельности человека. В социально-гуманитарных науках субъект всегда включен в объект исследования в его познавательной деятельности всегда присутствует как рациональные так и бессознательные моменты познания. Субъект в социально-гуманитарных науках играет огромную роль так как он определяет: предмет и методы исследования способы интерпретации полученного знания объективность и...
82237. Науки о природе и науки об обществе (их сходства и отличия): современные трактовки и проблемы 39.22 KB
  Шаги в развитии проблемы классификации наук предпринятые в частности Вильгельмом Дильтеем 1833-1911 привели к отделению наук о духе и наук о природе. В работе Введение в науки о духе философ различает их прежде всего по предмету. Предмет наук о природе составляют внешние по отношению к человеку явления.
82238. Конвергенция естественнонаучного и социально – гуманитарного знания в неклассической науке, эволюция и механизмы взаимодействия 42.89 KB
  Представители философия жизни Дильтей Ницше Зиммель Бергсон утверждают что жизнь первичная реальность органический прцесс для познания которого нужны интуиция понимание вживание вчувствование. Предмет социального познания культурно значимая индивидуальная действительность. Признается возможность объективного познания культурноисторических и соц явлений. Соцгум познание признается частным видом научного познания подчиняющимся общим научным закономерностям.
82239. Применение общенаучных достижений в социально-гуманитарном познании. Междисциплинарные связи и научная картина мира в социально-гуманитарных науках 34.93 KB
  Социальногуманитарные науки как и наука в целом всегда создают целостные картины общества. Научная картина общества это целостная система знаний которая объясняет основные законы возникновения и существования окружающей социальной действительности и систематизирует конкретные знания полученные в различных областях социальногуманитарных наук. Она представляет собой своеобразную модель общества включающую в себя общие понятия принципы гипотезы прежде всего обществознания которые сформулированы в терминах обыденного языка и...
82240. Индивидуальный и коллективный субъекты, формы их существования. Включённость сознания субъекта, его системы ценностей и интересов в объект исследования СГН 40.74 KB
  Означает ли сказанное что мы должны признать футбольную команду самостоятельным субъектом деятельности И не означает ли такое признание что мы приписываем собственную деятельность ее сознательно или стихийно сложившиеся надындивидуальные условия регулятивные механизмы и результаты некоему мифологическому субъекту вполне подобному Абсолютной Идее Гегеля действующей посредством живых людей Такова например позиция Э.Если мы не хотим впасть в какуюто туманную мистику или мифологию в понимании общества то можно ли вообще видеть в нем...
82241. Коммуникативная рациональность. Роль традиций, ценностей, образцов интерпритации и предрассудков (Г.Гадамер) в межсубъектном понимании и смыслополагании 38.92 KB
  Что такое понимание Можно ли рассматривать понимание только как знание наравне с эмпирическим и теоретическим знанием Несомненно понимание является знанием но знанием особенным имеющим специфические черты которые существенно отличают его от других видов знания. Так прежде всего необходимо рассматривать понимание как осмысление как выявление и реконструкцию смысла. Таким образом главной задачей герменевтики становится истолкование и понимание текстов. Дильтей полагает что главным методом данных наук является понимание.
82242. Методологические функции «предпосылочного знания» и регулятивных принципов в науке 34.35 KB
  Одновременно произошло уточнение понимания природы социальности и исследования в сфере философии науки должны раскрывать как и в каких формах социальный и культурно-исторический моменты входят в содержание знания и влияют на способы и результаты познавательной деятельности. Сегодня найдены реальные вполне адекватные формы и опосредующие механизмы такого воздействия в частности выявлена роль идеалов и норм философско-мировоззренческих предпосылок и оснований научного знания. Через них принимая форму ценностного сознания социальная и...