Лекция_11_12_Алгоритмизация прикладных задач

Алгоритмизация прикладных задач

1. Алгоритмизация вычислительных процессов:
1.1. Постановка задачи
1.2. Понятие алгоритма, алгоритмизация задачи.
1.3. Основные свойства алгоритма.
1.4. Способы описания алгоритмов.

2. Виды алгоритмов и принципы их составления:
1.1. Виды алгоритмов
1.2. Линейные алгоритмы
1.3. Разветвляющиеся алгоритмы.
1.4. Циклические алгоритмы, вложенные циклы.
1.5. Комбинированные алгоритмы.

Этапы решения задачи на ЭВМ:

Содержательная постановка задачи (формулировка задачи, излагаемая в терминах конкретной области науки)
Математическая постановка задачи (формулировка задачи некоторого раздела математики)
Формализация задачи (преобразование задачи, полученной на этапе математической постановки к алгоритмической задаче)
Составление алгоритма решения задачи
Составление программы на языке программирования
Рабочий счет (решение задачи с рабочими данными на ЭВМ) и анализ результатов

Слово «алгоритм» произошло от имени арабского математика IX в. Аль Хорезми, который сформулировал правила выполнения арифметических действий

После постановки задачи осуществляется описание алгоритма

выделить величины, являющиеся исходными для задачи;
разбить процесс решения задачи на такие этапы, которые известны исполнителю и которые он может выполнить однозначно без всяких пояснений;
указать порядок выполнения этапов;
указать признак окончания процесса решения задачи;
указать во всех случаях, что является результатом решения задачи

Правила описания алгоритма решения задачи

Подготовить исходные величины – системный блок, монитор, клавиатуру, мышь, сетевой фильтр.
Подключить системный блок в сетевой фильтр и монитор.
Подключить монитор в сетевой фильтр и системный блок.
Подключить клавиатуру и мышь в системный блок.
Включить сетевой фильтр в розетку.
Включить монитор.
Включить системный блок.
Подождать, когда загрузится система
Компьютер к работе готов. Задача решена

Простейший алгоритм подключения компьютера

1. Дискретность алгоритма (решение задачи, записанное в виде алгоритма, разбито на отдельные простейшие команды, которые расположены в порядке их выполнения)

2. Определенность алгоритма. (каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для ее неоднозначного толкования и неопределенного исполнения).
3. Результативность алгоритма. (свойство алгоритма всегда приводит к результату через конечное число шагов).

4. Массовость алгоритма (каждый алгоритм, разработанный для решения некоторой задачи должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных)

Словесно-формульное описание алгоритма, т.е. описание алгоритма с помощью слов и формул.

Например: найти значение выражения: y=2a-(x+6)

Ввести значения a и х. Перейти к п. 2
Вычислить y=2a-(x+6). Перейти к п. 3.
Вывести y как результат вычисления выражения

2. Графическое описание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов – блок-схем (рассмотрим далее).
3. Способ, использующий псевдокоды, т.е. интерпретация шагов алгоритма на обычном языке, которая описывает действие команды.
Например: найти значение выражения: y=2a-(x+6)
Начало
Ввод чисел: a,x
Вычисление выражения y=2a-(x+6)
Вывод y
Конец

4. Запись алгоритма на одном из языков программирования

Выделяют четыре основных вида алгоритмов:

линейной структуры,
разветвляющейся структуры,
циклической структуры,
комбинированной структуры.

Правила построения схемы алгоритма задачи:

Выявить исходные данные, результаты, назначить им имена.
Выбрать метод (порядок) решения задачи.
Разбить метод решения задачи на этапы (с учетом возможностей ЭВМ).
Изобразить каждый этап в виде соответствующей блок-схемы алгоритма и указать стрелками порядок их выполнения.
В полученной схеме при любом варианте вычислений:
а) предусмотреть выдачу результатов или сообщений об их отсутствии;
б) обеспечить возможность после выполнения любой операции так или иначе перейти к блоку Останов
(к выходу схемы).

Блок-схема алгоритма представляет собой систему связанных геометрических фигур

Каждая фигура обозначает один этап решения задачи и называется блоком.

Порядок выполнения этапов указывается стрелками, соединяющими блоки.

Блок «Процесс»

Блок «Ввод»

Логический блок ветвления

Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно.

Задача. Определить значение уравнения Х=y+a2-zРешение:1. Исходные данные: y,a,z2. Расчет значения уравнения: Х=y+a2-z 3. Вывод значения уравнения

Блок-схема
линейного
алгоритма
с неизвестными
исходными
данными

Если в условии задачи заранее известны исходные данные, то они записываются в фигуру прямоугольника.Например: Определить значение уравнения  Х=y+a2-z, при y=2, a= 7; z=3

Блок-схема
линейного
алгоритма
с известными
исходными
данными

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

Задача. Составить алгоритм начисления стипендии согласно следующему правилу:Если количество пятерок по результатам сессии составляет 100%, то размер стипендии - 1300 руб., при количестве пятерок от 50 до 100% — 1100 руб., при количестве пятерок менее 50% стипендия составит 900 руб.

Математическая постановка задачи:

1300, если Кп = 100%
ST = 1100, если 50% ≤ Кп < 100%
900, если Кп < 50%

где ST — размер стипендии;
Кп — количество пятёрок по результатам экзаменационной сессии.

В схеме алгоритма операцию проверки условия выполняет логический блок, который изображается ромбом, внутри которого указывается проверяемое условие, и имеет два выхода: Да и Нет.
Если условие выполняется, то выходим из блока по выходу Да; если не выполняется — по выходу Нет:

Самостоятельная работа

Составить алгоритм.
Если N > T,
то S = V-T,
иначе S = W+T.

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

В схеме алгоритма операцию многократного повторения выполняет логический блок, который изображается шестиугольником, внутри которого указывается повторяющееся условие:

Например: Составить алгоритм решения значения уравнения Y=abc6/sinz, где zЄ(0,7; 1,2) Δ 0,2:

Самостоятельная работа

Составить алгоритм решения значения уравнения
U = a*cos2(wt+f), где t = 1; 3; 0,2

Алгоритмическую конструкцию, описывающую кратные циклы (т.е. когда цикл содержит внутри себя другие циклы), называют вложенными циклами

Например: Составить алгоритм для вычисления функции Y=abc6/sinz,
где a Є (-2;7) Δ 0,3 и c Є (1,5;2,5):

Самостоятельная работа

Составить алгоритм решения значения уравнения
U = a*cos2(wt+f), где t = 1; 3
f = 3; 5

Пример. Составить программу для вычисления значений функции:

где а = 2,3; b = -1,2; c = 4,2 и i Є [2;10] Δ 2

2.5. Комбинированный алгоритм, включающий в себя разветвляющий и циклический алгоритм

S =

Самостоятельная работа

Благодарю за внимание!