Выбор представления данных (ВПД)

Основы алгоритмизации

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

Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принять называть формальным исполнителем.

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

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

Свойства:

1. Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в систему команд исполнителя.

2. Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных шагов). Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

3. Определенность (детерминированность) – каждое правило алгоритма должно быть четким, однозначным. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

4. Результативность Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определённый результат. Вывод о том, что решения не существует - тоже результат.

5. Массовость – алгоритм должен решать любую задачу из того класса задач, для решения которых он разработан. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Например, алгоритм решения квадратного уравнения должен решать любое квадратное уравнение.

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

Процедура подготовки и решения задачи на ЭВМ - достаточно сложный и трудоемкий процесс, состоящий из следующих этапов:

Анализ задачи;
Разработка и обоснование алгоритма;
Выбор и обоснование наборов тестов;
Описание разрабатываемых алгоритмов;
Выбор представления данных;
Кодирование программы(написание программы на языке программирования);
Тестирование и отладка;
Составление отчета;

Анализ - это исследование объектов или явлений, путем изучения составляющих его элементов.

Анализ задачи позволяет установить:

Что является входом и выходом будущего алгоритма, при этом следует явно описывать класс входных данных.

Выделить основные решения между входными и выходными данными.

Выделить модули необходимые для выполнения задачи и определить методы их решений.

Класс входных данных определяется наложением ограничений. Определение отношений между входными и выходными данными определяется математической постановкой решаемой задачи. Содержание постановки задачи - это определение правильности конечных результатов, т.е. чем содержательней и правильнее поставим задачу, тем больше вероятность, что программа будет написана правильно, т.е. она будет делать то, что от нее требуется.

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

Что дано?
Что требуется?
Какие результаты будут считаться правильными?
Какие данные будут считаться допустимыми?

В разделе Дано - Перечисляются все исходные данные.

В разделе Требуется - Перечисление всех выходных данных с указанием их названий и математического обозначения.

В разделе 3 - Устанавливается система математических утверждений, связывающая входные и выходные данные с объяснением каждой записи.

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

Сценарий работы программы

Сценарий представляет собой описание внешних формул при выполнении программы.

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

Требования к сценарию:

Простота, т.е.:
подсказка на экране
сложно сделать ошибку
фиксация кадра - смена кадра должна происходить не сразу
обычно любая операция должна выполняться после запроса
В сценарии описываются:
форма ввода исходных данных
форма вывода результатов
контроль прохождения программы и промежуточного результата при отладке и если это необходимо

Пример:

Сценарий программы нахождения наиболее удаленных точек.

На экран выводится: Введите общее количество точек
В ответ пользователь вводит число N
N раз на экране повторяется:

Введите координаты i-ой точки x="

Ввод координаты Xi ;

К выведенной строке дописывается Y=

Ввод Yi

На экране выводится наиболее удаленные друг от друга точки с координатами (<Xa>,<Ya>) и (<Xb>,<Yb>)

Данный сценарий не включает контроля ограничения на входные данные.

Выбор представления данных (ВПД)

ВПД - является одним из важных этапов представления программы. В одних случаях ВПД является решающим и определяет алгоритм. Данные можно разделить на три типа:

Входные данные
Промежуточные
Выходные данные

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

Для описания алгоритмов существует множество способов. Основные способы описания следующие:

- словесный;

- алгоритмический язык;

- блок-схема;

- псевдокод.

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

Иначе говоря, блок-схема служит для графического изображения структуры алгоритма. Любая блок-схема содержит набор геометрических фигур или блоков. Последовательность действий указывается с помощью стрелок, соединяющих отдельные блоки.

Основные блоки, используемые при изображении блок-схем:

Функциональный блок.

Логический блок.

Блок, обозначающий операции ввода-вывода.

Блок, обозначающий начало или конец алгоритма.

Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции):

- следование;

- ветвление (полное и не полное);

- повторение (цикл с предусловием или постусловием);

- вход;

-выход.

Каждая базовая структура имеет один вход и один выход. Схемы основных базовых алгоритмических структур:

Следование Повторение (Цикл )

Оператор

Тело ц.

Ветвление (полное)

Условие

Да Нет

Действие 2

Действие 1

Выбор (оператор switch)

Выражение

Нет

…………………….

Дата добавления: 2020-12-12; просмотров: 212; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!