- •Понятие алгоритма и его свойства
- •Детерминированность. Процесс применения правил к исходным данным (путь решения задачи) определен однозначно или по другому - каждый шаг однозначно определяется состоянием системы
- •Формальность - инструкции алгоритма могут выполняться формально (бездумно)
- •Определение алгоритма на основе рекурсивных функций
- •Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)
- •Правила выполнения соединений
- •Линейный алгоритм
- •Разветвляющийся алгоритм
- •Циклический алгоритм
- •Гост 19.701-90;
- •Объекты алгоритма
- •Разработать алгоритм задачи: «ввести два числа, найти их среднее арифметическое, выдать результат» Разработать алгоритм задачи: «ввести два числа, найти среднее геометрическое, выдать результат»
- •Вставить пропущенный текст в программу определения количества нечетных чисел в последовательности, вводимой с клавиатуры до тех пор, пока не будет введена единица.
- •Ввести X
- •Конец пока
Гост 19.701-90;
ТИПЫ АЛГОРИТМОВ
В теоретических основах структурного программирования доказано, что логическая структура любой программы может быть выражена комбинацией трех базовых структур. К ним относятся (см. рис.1) следование (а), ветвление (б) и повторение (в).
а) б) в)
Рис.1
Каждая структура имеет единственный вход и единственный выход. Рассмотрим составление схем алгоритмов.
6.2.
6.3.
НЕКОТОРЫЕ СОВЕТЫ ПО СОСТАВЛЕНИЮ СХЕМ
АЛГОРИТМОВ И ПРОГРАММ
В связи с тем, что составление схем алгоритмов для студентов впервые осваивающих этот прием достаточно сложный процесс, поэтому на начальном этапе следует пользоваться карандашом и резинкой. Весь процесс составления схемы алгоритма можно разбить на несколько этапов. На первом этапе можно ограничиться построением принципиальной схемы алгоритма, позднее разработать более подробную схему.
Следует сопровождать составление схемы алгоритма с заполнением таблицы идентификаторов, в которой описываются все переменные, приводится их обозначение и назначение.
Написание программ необходимо проводить в полном соответствии с разработанной схемой алгоритма.
Все операторы относящиеся к одному циклу следует сдвигать вправо, чтобы сделать программу более наглядной.
Важные места программы следует предварять подробными комментариями.
Все исправления в программе следует проводить параллельно с исправлениями в схеме алгоритма.
ЭТАПЫ РЕШЕНИЯ ЗАДАЧ С ПОМОЩЬЮ ЭВМ
Решение любой задачи на ЭВМ включает в себя основные этапы :
1) Постановка задачи, разработка математической модели;
2) Выбор метода численного решения;
3) Разработка структуры исходных данных;
4) Разработка алгоритма;
5) Реализацию алгоритма на языке высокого уровня (написание программы);
6) Отладка и тестирование программы;
7) Решение задачи и анализ результатов;
8) Документирование с учетом требований ЕСПД полученных результатов.
Объекты алгоритма
Решение любой задачи предполагает наличие реальных объектов – объектов задачи.
Например. При решении задачи о начислении зарплаты сотрудникам предприятия объектом задачи могут быть: табельный номер сотрудника, его фамилия, имя, отчество, оклад, отработанное время и т.д. При решении системы уравнений объектами задачи являются – число уравнений, коэффициенты уравнений, правые части.
Каждый объект задачи имеет свои характеристики (атрибуты). Фамилии и наименования – это строки символов, а коэффициенты уравнений, количество выпускаемой продукции – это числовые константы, представленные арифметическими выражениями или числами.
Если выполнение алгоритма возложено на ЭВМ, необходима строгая формализация задачи. Она предполагает замену объектов задачи – объектами алгоритма, которые должны наследовать их атрибуты. При разработке алгоритма могут появиться вспомогательные объекты не соответствующие никаким объектам задачи.
В практике программирования число базовых объектов невелико. Это константы, переменные массивы, файлы и некоторые другие.
Понятие константы. Например, в задаче нужно вычислить длину окружности L = π * D, здесь L и D – объекты задачи, а π – величина постоянная в любой задаче, т.е. это константа.
Константа может быть не только числом. Например, в некотором списке фамилий определяется наличие фамилии Иванов. В алгоритме фамилия – это объект, а Иванов – символьная константа.
Константа – это объект алгоритма. Каждая константа как объект алгоритма имеет фиксированный тип (арифметический, символьный или другой) и имеет фиксированное, неизменяемое в данном алгоритме значение, соответствующее ее типу. Значение константы обычно определено в условии задачи и известно до начала разработки алгоритма.
Понятие переменной. Переменная – это объект алгоритма, который имеет определенный фиксированный тип (арифметический, символьный или другой) и который в каждый момент исполнения алгоритма имеет единственное значение соответствующего типа. К моменту использования переменной в алгоритме ее значение должно быть определено. В ходе выполнения алгоритма значение переменной может изменяться.
Например, требуется вычислить и напечатать значение функции при изменении аргумента от заданного начального значения до заданного конечного значения с заданным шагом. Начальное значение, конечное значение, шаг – объекты задачи, которые в условии задачи не определены. Эти значения станут известны по ходу выполнения алгоритма: введены пользователем или получены в результате вычислений. Если не предусмотреть механизм их определения, исполнение алгоритма будет невозможно.
Имя объекта алгоритма. Каждый объект в алгоритме фигурирует под своим именем. Имя это неизменно, фиксировано и уникально. Имена для объектов устанавливает автор алгоритма. Рекомендуется выбирать мнемонические имена, которые отражают суть объекта.
Понятие массива. Массив – объект алгоритма. Во многих случаях разрозненные переменные удобно объединить в совокупность – массив, именуя все коэффициенты общим именем (именем массива) и индексами (номерами в массиве).
Индекс элемента массива позволяет обратиться к элементу массива «напрямую». По индексу массив строго упорядочен.
Массивом называется конечная упорядоченная совокупность данных одного типа, доступ к каждому осуществляется по его индексу.
В задачах используются как одномерные, так и многомерные массивы. Для указания положения элемента в двумерном массиве используют два индекса – сначала номер строки, затем номер столбца. Массивы могут быть как числовыми, так и символьными.
В любом алгоритме всегда присутствует раздел инструкций (выполнения действий), который имеет одну точку входа (НАЧАЛО) и одну точку выхода (КОНЕЦ). Закодированная форма инструкции, несущая определенный смысл называется оператором.
Рис. 7 – Пример записи алгоритм сортировки выбором с помощью блок-схемы
язык гипертекстовой разметки (HTML) Простой язык разметки, применяемый для создания независящих от платформы гипертекстовых документов. Файлы HTML являются текстовыми файлами, в которые вставлены коды (теги разметки), определяющие форматирование и гиперссылки.
язык наращиваемой разметки (XML) Язык наращиваемой разметки XML (Extensible Markup Language) предоставляет формат для описания структурированных данных. Это позволяет более точно объявлять содержимое и получать более значимые результаты поиска на нескольких платформах. Кроме того, XML делает возможным создание нового поколения веб-приложений для просмотра данных и управления ими.
Многократное исполнение одного и того же участка программы называется циклическим процессом
К эвристическим алгоритмам относятся. алгоритмы, использующие опыт экспертов
..М591
Графическое изображение цикла с постусловием является в Паскале...
Вопросы для самоподготовки
Какое условие пропущено в программе поиска наименьшего четного числа, большего заданного положительного N:
ввод N X:=0 нц пока X<N ______ X:=X+2 кц вывод Х...
Какое условие пропущено в программе, рассчитывающей количество чисел, вводимых с клавиатуры до тех пор, пока не будет введен ноль: x=0
ввод х k = 0 если x <> 0 то нц k := k+1 ввод х пока не _____ печатать k иначе печатать «k = 0» необходимо вставить условие ...
Определить А и В: А := 100 В := 10 А := А / 5 - В В := «A > B»
Определить А и В: А := 100 В := 10 А := А / 5 - В В := A > B
Определить х: А := «100» В := «10» С := «11» Х := А + В + С
Определить А и В: А := 12 В := 10 А := 2 * А - В В := А / 2
Определить Y, если x=5, A=2, B=467, C=0: ввод Х, А, В, С Y := X^A+B*sin(C) вывод Y
Определить Y, если x=3, A=2048, B=2047, C=-1: ввод Х, А, В, С Y := X^3+B*C+A вывод Y
Определить k: m := 1 k := 0 x := 10 y := 3*x нц x := x*(1+m) k := k+1 пока не x >= y кц
Определить х: x = 10 y =(x + 1)*2-x/2 если не(x > y) или не (y = 17) то x = y*2 иначе x = y+30 конец если ВЫВОД x