Алгоритмы
С.П. Минеев.
Понятие алгоритма
Алгоритм
— это метод
(способ) решения задачи,
записанный по
определенным правилам,
обеспечивающим
однозначность его
понимания и механического
исполнения при всех
значениях исходных
данных.
Исполнитель алгоритма
Исполнитель
алгоритма –
человек или устройство (в
частности, процессор
компьютера), умеющий
выполнять определённый
набор действий. Исполнитель
является средством
реализации алгоритма.
Алгоритмы в жизни
человека
Распорядок
дня
Рецепты
План
работы
Инструкции по
использованию
…
Любую деятельность
человека можно описать с
помощью алгоритмов
Алгоритмы в жизни
человека
Вопрос: Как заставить человека
решать или выполнять какую либо
задачу какую-либо задачу, если
человек не знает как?
Ответ: Научить!
1.Выбрать способ решения задачи
2. Рассказать как реализовать
способ. Понятно и доступно!
3. Человек (исполнитель) решает
задачу строго в соответствии с
выбранным методом.
Алгоритм и компьютер
Вопрос: Как заставить компьютер
решать или выполнять какую либо
задачу какую-либо задачу ?
Ответ: Научить!
1.выбирают способ (метод, порядок)
решения задачи и изучают его во
всех подробностях;
2. описывают исполнителю
(компьютеру) выбранный метод в
абсолютно понятном для него виде;
3. исполнитель решает задачу
строго в соответствии с методом.
Выбор способа решения
задачи
Способ
решения задачи должен
быть известен (из практики,
здравого смысла из литературы)
Главная трудность: из
нескольких методов выбрать
такой, который в наибольшей
степени отвечал бы некоторым
требованиям, например,
минимальная трудоемкость,
максимальная эффективность и т.д
Описание выбранного
метода
выделить величины, являющиеся
исходными для задачи;
разбить процесс решения задачи на
такие этапы, которые известны
исполнителю и которые он может
выполнить однозначно без всяких
пояснений;
указать порядок выполнения этапов;
указать признак окончания процесса
решения задачи;
указать во всех случаях, что является
результатом решения задачи.
Свойства алгоритма
1. Дискретность алгоритма.
Свойство алгоритма, означающее,
что процесс решения задачи,
определяемый алгоритмом,
расчленен на отдельные
элементарные действия (шаги) и
соответственно алгоритм
представляет последовательность
указаний, команд, определяющих
порядок выполнения шагов
процесса.
Свойства алгоритма
2. Определенность алгоритма.
Это свойство означает, что каждая
команда алгоритма (предписание,
выдаваемое на каждом шаге)
должна быть понятна
исполнителю, не оставлять места
для ее неоднозначного толкования
и неопределенного исполнения.
Описание алгоритма должно быть
таким, чтобы его мог выполнить
любой грамотный пользователь.
Свойства алгоритма
3. Результативность алгоритма.
Свойство алгоритма, состоящее в
том, что он всегда приводит к
результату через конечное,
возможно, очень большое число
шагов.
Свойства алгоритма
4. Массовость алгоритма.
Это свойство заключается в том,
что каждый алгоритм,
разработанный для решения
некоторой задачи, должен быть
применим для решения задач
этого типа при всех допустимых
значениях исходных данных.
Языки
программирования
Алгоритм
Язык программирования
Языки программирования:
-Бэйсик
-Паскаль
-Си ++
Программа - Запись алгоритма на
языке программирования
Программирование – процесс
перевода алгоритма на язык
программирования
Возможности
компьютера
1) Компьютер может работать с
числовыми значениями
- постоянными величинами,
которые во время решения задачи
не меняют своих значения: 3,14, 2,
31
- переменными, которые во время
решения задачи могут менять свои
значения: а, B, Z
2) Компьютер может рабоать с
текстовыми величинами: «Привет»,
«Компьютер»
Возможности
компьютера
3) Компьютер может считывать
конкретные значения исходных
величин с различных устройств
ввода и помещать каждое из
них в ячейку, выделенную для
соответствующей переменной
Записывается командной «Ввод»:
Ввод X, Y, А
Возможности
компьютера
4) Компьютер может вычислять значения
величины по заданной формуле,
содержащей знаки любых
арифметических операций, ряда
элементарных функций типа ln x, |x| , sin
x и т.д.,
Пример записи такой операции: Y:=3*ln
Х+В2.
Подобная операция называется «операция
присваивания» и в общем виде
записывается так:
x:= а,
где x — переменная; а —
арифметическое выражение,
переменная или текст. Z:=5,1;
Д:="КОЛЯ".
Возможности
компьютера
5) Компьютер может печатать на
бумаге или выводить на экран
монитора значения величин или
любой текст.
Операции «Вывод» или «Печать»
и записывается: Вывод A, Y, Z
Возможности
компьютера
6) Компьютер может переходить
от одного этапа решения задачи
к любому другому.
Операция называется «Переход».
В ней указывается номер этапа,
к которому нужно перейти.
Например:
Перейти к п. 6
Возможности
компьютера
7) ЭВМ может сравнивать значения
двух выражений на предмет
проверки условий: <, >, = и т.д. и
в зависимости от результатов
проверки выбирать один из двух
возможных вариантов
дальнейших действий.
Записывается :
Если X>Y , то Y:=X2,
иначе Y:=Х 3.
Подобную операцию называют
Условный переход (Ветвление)
Возможности
компьютера
8) Компьютер может повторять
операции указанное число раз.
Пример:
Повторить 10 раз:
У:=x+1
Конец повторения
Подобную операцию называют
Цикл
Способы описания
алгоритмов
1) Словесно-формульное
описание алгоритма, т.е.
описание алгоритма с помощью
слов и формул. Это наиболее
простой способ.
Кулинарный рецепт — пример
описания словесноформульного алгоритма.
Способы описания
алгоритмов
Пример. Найти корни уравнения
Ax2 + Bx + C = 0
1. Ввести величины A, B, C.
2. Вычислить дискриминанту по
формуле
D = B2 - 4 A C.
3. Если D < 0, то действит. корней
нет.
4. Если D > 0, то идти к п. 5.
5.
6.
7.
Вывести значения X1 и X2.
Закончить.
Способы описания
алгоритмов
2. Графическое описание
алгоритма
Схема алгоритма представляет
собой систему связанных
геометрических фигур.
Каждая фигура обозначает один
этап процесса решения задачи и
называется блоком.
Порядок выполнения этапов
указывается стрелками,
соединяющими блоки.
Способы описания
алгоритмов
Операция присваивания
изображается
прямоугольником:
D := B2 - 4 A
C.
Способы описания
алгоритмов
Операции Ввод и Вывод
изображаются
параллелограммом:
Ввод A,B,C
Вывод X1,X2
Способы описания
алгоритмов
Операция Условный переход
изображается ромбом; блок
имеет два выхода — Да и Нет
нет
D<0
да
Способы описания
алгоритмов
Начало процесса решения
задачи обозначается блоком
Начало.
Завершение процесса решения
задачи обозначается блоком
Останов
Начало
Остано
в
Способы описания
алгоритмов
Начало
Ввод A, B, C
D = B2 - 4 A C
НЕТ
D<0
Да
X1 = (- B - D ) / 2 A
X2 = (- B +
Действительных
корней нет
D )/2A
Вывод X1, X2
Конец
Способы описания
алгоритмов
Описание алгоритма на
алгоритмическом языке
(алгоязыке). Алгоритмический
язык — это средство для записи
алгоритмов в аналитическом
виде, промежуточном между
записью алгоритма на
естественном (человеческом)
языке и записью на языке
компьютера (языке
программирования)
Способы описания
алгоритмов
программа корни
переменные a,b,c,d,x1,x2
ввод (a,b,c)
d:=кв.корень(b)-4*a*c
если d<0 тогда
вывести «нет корней»
иначе
x1:=(-b-sqrt(d))/2*a
x2:=(-b+sqrt(d))/2*a
вывести «x1=,x1», «x2=
»,x2)
конец если
Конец программы.