Общая характеристика этапов решения задачи с использованием ЭВМ

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

Общие сведения об алгоритмах

2.1.1. Свойства алгоритмов и способы их задания

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

Само слово «алгоритм» происходит от латинской формы написания имени великого математика IX века Аль Хорезми (Muhammed ibn Musa al Horesmi), который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами, а в дальнейшем это понятие стало использоваться для обозначения последовательности действий, приводящих к решению поставленной задачи. Сейчас с помощью алгоритмов решаются не только вычислительные, но и многие другие задачи.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся следующие.

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

2. Результативность. Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов. Если же способ получения последующей системы величин из какой-либо заданной не даёт результата, то должно быть указано, что надо считать результатом алгоритма.

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

4. Дискретность. Алгоритм — процесс последовательного получения величин, идущий в дискретном времени (по шагам) по определённой схеме и известным правилам.

5. Элементарность шагов. Описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений. Можно сказать, что алгоритм — это задание, которое нужно исполнить. Утверждения и вопросы могут быть использованы в алгоритмах только как подчиненные предложения в составе предписания.

Наиболее простой и универсальной формой представления алгоритма является словесное описание, которое содержит записанную на естественном языке (точнее, на подмножестве естественного языка) последовательность предписаний. Выполнение алгоритма предполагается в естественной последовательности, то есть в порядке записи. При необходимости изменить порядок выполнения предписаний в явной форме указывается, какое предписание надлежит выполнить следующим. Если необходимо такой алгоритм записать на бланке, то рекомендуется придерживаться следующих правил, облегчающих переход от алгоритма к программе:

1) каждое предписание записывается с новой строки;

2) после предписания ставится точка с запятой;

3) если предписание не поместилось в одной строке, то его можно продолжить на следующей строке без каких-либо знаков переноса.

Такую словесную запись алгоритма называют псевдокодом (ПCK), подчеркивая этим ее промежуточное положение между нашей естественной речью и понятным для компьютера языком программ. Достоинством псевдокодов является их универсальность, а к недостаткам можно отнести малую наглядность записи. Наглядностью обладает другая форма записи — графическая схема алгоритмов (ГСА), или блок-схема. Такая схема представляет собой графический документ, который дает представление о порядке работы алгоритма. Здесь предписания имеют вид различных геометрических фигур, а последовательность выполнения операций отображается с помощью линий, соединяющих эти фигуры. Условные обозначения, применяемые при составлении граф-схем алгоритмов, и правила выполнения определены в ГОСТ 19.701-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

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

Таблица 1

Описание условных графических обозначений (УГО),

Используемых в СА

Наименование	Обозначение	Функции
Данные		Символ отображает данные, носитель данных не определен. Используется для обозначения операций ввода и вывода данных
Процесс		Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации). Используется для обозначения операций присваивания

Продолжение табл. 1

Наименование	Обозначение	Функции
Предопределенный процесс		Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов, которые определены в другом месте (в подпрограмме, модуле). Используется для обозначения неэлементарных блоков (процедуры, функции)
Подготовка		Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы). Может быть использован для обозначения заголовка цикла
Решение		Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути. Используется для обозначения оператора условного перехода или оператора варианта
Граница цикла		Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от типа цикла
Соединитель		Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение

Продолжение табл. 1

Наименование	Обозначение	Функции
Терминатор		Символ отображает выход во внешнюю среду и вход из внешней среды. Используется для обозначения начала или окончания алгоритма
Линия		Символ отображает поток данных или управления. Направления справа налево и снизу вверх обозначаются стрелками. Используется для соединения символов в алгоритме
Параллельные действия		Символ отображает синхронизацию двух или более параллельных операций
Пунктирная линия		Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используется для обведения аннотированного участка при записи комментариев
Комментарий		Символ используется для добавления описательных комментариев или пояснительных записей с целью объяснений или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры

Символы могут быть вычерчены в любой ориентации, но предпочтительной является горизонтальная ориентация. Внутрь символа помещают обозначения или описания операций. Направления линий связи слева направо и сверху вниз считаются стандартными, и линии связи изображаются без стрелок, в противоположном случае — со стрелками. В операционные блоки (процесс, ввод-вывод и подпрограмма) входит и из них исходит только одна линия связи. В блок проверки условий (ветвление) входит одна, а выходит не менее двух линий, около которых записываются результаты проверки условий. Из начальной вершины исходит одна линия связи, в конечную вершину также входит одна линия связи. Линии могут соединяться одна с другой, но не могут разветвляться. Символы ГСА могут быть отмечены идентификаторами или порядковыми номерами. Идентификатор представляет собой букву или букву с цифрой и должен располагаться слева над символом.

Внутри соединителей ставятся номера (координаты) блоков к которым или от которых идут линии связи. Вместо номера (координат) может быть поставлен некоторый (один и тот же в обоих соединениях) идентификатор (рис. 5).

Рис. 5. Применение соединений

Недостатком графических схем алгоритмов является громоздкость. Для решения специальных задач, например проектирования вычислительных устройств, применяются другие способы задания алгоритмов, такие, как логические (операторные) и матричные схемы. Их достоинствами являются компактность и простота дальнейшей формализации, а недостатком — малая наглядность.

Базовый набор структур

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

• последовательной (линейной) структуры (рис. 8, а);

• ветвящейся структуры (рис. 8, б).

• циклической структуры (рис. 8, в).

Рис. 8. Базовый набор структур:

а — последовательная (линейная) структура;

б — ветвящаяся структура; в — циклическая структура

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

Begin

if (NOT B1) AND (NOT B3) then N: =1 else

if (NOT B1) AND (NOT B2) AND B3 then N: =2 else N: =3;

case N of

1: S1;

2: S2;

3: S3;

end;

End.

Важно отметить, что к моменту вычисления N должны быть определены значения В1, В2, ВЗ.

В качестве еще одного примера использования ветвлений рассмотрим составление алгоритма для вычисления функции f в зависимости от конкретных значений х, а, b:

Первое приближение алгоритма будет иметь вид, показанный на рис. 12.

Рис. 12. Первый этап составления алгоритма

Анализ этого алгоритма показывает, что все его блоки, кроме блока 5, являются элементарными. Возможный вариант дальнейшей детализации блока 5 представлен на рис. 13. Все блоки второго этапа детализации являются элементарными, поэтому составление алгоритма практически закончено.

Рис. 13. Второй этап составления алгоритма

На заключительном этапе производится сборка алгоритма, т.е. содержимое рис. 13 помещается на рис. 12 вместо блока 5. Данный этап здесь не показан, при желании можно выполнить его самостоятельно.

Цикл с заданным условием продолжения работы (цикл-ПОКА)

Логика работы такой структуры описывается схемой, показанной на рис. 14, а.

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

Рис. 14. Структура цикл-ПОКА: а — развернутая схема цикла; б — запись в псевдокодах; в — компактная схема цикла

Рассмотрим применение циклической структуры этого типа на простом примере: составить алгоритм печати таблицы значений х, х², sin(x) и 1/х при изменениях х от 1 с шагом 0.1, пока выполняется условие х< 10.

Составим алгоритм в виде псевдокодов:

1. Начало;

2. Список данных:

х, fl, f2, f3 — вещественный;

3. х: =1;

4. Цикл-ПОКА (х < 10);

5. fl: =x²; f2: =sin(x); f3: =l/x;

6. Вывод(х, fl, f2, f3);

7. x: =x+0.1;

8. Конец-цикла 4;

9. Конец.

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

Таблица значений

Память	Условие	Вывод
х=1, 4, 7, 10, 13	1> 10нет	1 1
f1 = 1, 16, 49, 100	4> 10 нет	4 16
	7> 10 нет	7 49
	10> 10 нет	10 100
	13> 10 да

Отметим, что при х = 10 результатом проверки 10 > 10 является ответ «нет» и тело цикла выполняется последний раз. При х = 13 условие окончания цикла выполняется, и управление передается оператору, стоящему в строке 7 алгоритма.

Логические алгоритмы

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

1.3.1. Задача " Поиск пути в лабиринте"

Эта задача восходит к греческой мифологии, в которой Тезею, оказавшемуся в лабиринте, где обитал Минотавр, необходимо было выбраться из лабиринта. Решить данную задачу ему помогла Ариадна (А), дав ему клубок ниток, один конец которых держала она сама. По мере углубления Тезея в лабиринт клубок разматывался; наматывая потом нитки, Тезей благополучно вернулся к выходу.

Рассмотрим задачу поиска пути в лабиринте в общем случае.

Представим лабиринт в виде конечной системы площадок, от которых расходятся коридоры, причём каждый коридор соединяет две площадки (будем называть их смежными); возможно существование таких площадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками). Геометрически лабиринт можно представить в виде системы точек А, В, С, ..., изображающих площадки, и совокупности отрезков АВ, ВС, ..., изображающих коридоры, которые соединяют определённые пары данных точек (рис. 1.16). Смежными являются, например, площадки В и С, К и М и т. д., а тупиковыми – площадки A, D, I, J.

Рис. 1.16. Геометрическое представление лабиринта

Будем говорить, что площадка Y достижима из площадки X, если существует путь от X к Y через промежуточные коридоры и площадки. Точнее: либо X и Y - смежные площадки, либо существует последовательность площадок Х1, Х2, ..., Хn таких, что X и Х1, Х1 и Х2..., и т.д., и, наконец, Хn и Y являются смежными. Отметим, что если Y достижима из X, то она достижима и посредством простого пути, т.е. такого пути, в котором каждая площадка (а тем более и каждый коридор) проходится лишь один раз. Например, путь ABCD является простым, а путь ABCFECD – нет.

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

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

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

1.3.2. Задача " Ханойские башни"

Эта задача формулируется следующим образом. Имеется три стержня, на одном из которых (назовём его занятым) находятся диски разных диаметров, расположенные на стержне в порядке убывания диаметров снизу вверх, второй стержень назовём свободным, а третий – вспомогательным. Требуется, производя одиночные перемещения дисков, переместить всю " стопку" дисков с занятого стержня на свободный, используя вспомогательный стержень; при этом на любом шаге диски должны быть расположены на каждом стержне в порядке убывания их диаметров (рис 1.17).

А В С

Рис. 1.17. Ханойские башни

Таблица 1.5

Шаг
А	4-1	4-2	4, 3	4, 3		4, 1	4, 1		Æ	Æ		2, 1	2, 1		Æ	Æ
В	Æ	Æ		2, 1	2, 1		Æ	Æ		4, 1	4, 1		4, 3	4, 3	4-2	4-1
С	Æ			Æ			3, 2	3-1	3-1	3, 2			Æ		1	Æ

В табл. 1.5 приведен результат решения задачи для случая четырех дисков. Здесь А – занятый в начальный момент (нулевой шаг) стержень, В – свободный, а С – вспомогательный стержень. Цифрами обозначен " номер" диска, причём большему номеру соответствует больший диаметр. Отметим, что в середине процесса решения в качестве вспомогательного выступает то стержень А, то стержень С.

Видно, что процесс перемещения стопки дисков можно разбить на четыре фазы:

1-я фаза – шаги 1-8, в результате которой самый нижний диск оказывается на свободном стержне;

2-я фаза – шаги 9-12; второй по величине диск оказывается на свободном стержне;

3-я фаза – шаги 13 и 14; переносят предпоследний диск на свободный стержень;

и 4-я фаза – шаг 15 – заключительный этап, в результате которого диск с наименьшим диаметром переносится на свободный стержень с уже упорядоченными по убыванию дисками.

То есть, к началу каждой фазы на вспомогательном или занятом стержне собирается стопка дисков, затем в течение данной фазы самый нижний диск стопки перемещается на свободный стержень (в табл. 1.5 номера этих дисков подчёркнуты).

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

В качестве примера решения задачи «Ханойские башни» можно привести следующий НЕ рекурсивный алгоритм. Если обозначить номера стержней не буквами а цифрами «0», «1» и «2», пронумеровать диски от нуля до N-1 (N – кол-во дисков на занятом стержне), то можно использовать следующее соотношение: на i-ом ходе переносится диск номер k со стержня номер ((-1)^N-k*t mod 3) на стержень номер ((-1)^N-k*(t+1) mod 3). Следуя такой последовательности перемещения дисков задача будет решена за 2ⁿ-1 перемещений. При этом для нахождения чисел t и k воспользуемся теоремой: любое натуральное число i единственным образом представимо в виде i=(2t+1)*2^k, где t и k - целые (т.е. как произведение нечетного числа на некоторую степень двойки). Если i – это очередной ход, то соответственно по указанной формуле для него определяются значения целых чисел t и k. В данном, одном уравнении присутствуют два неизвестных. Однако пользуясь тем, что числа t и k обязательно целые и единственные для натурального числа i, нетрудно построить алгоритм для нахождения их значений.

Отметим также, что в зависимости от того четным или нечетным будет количество дисков на занятом стержне, в качестве вспомогательного и свободного будут выступать соответственно либо стержни «1», «2» либо «2», «1», т.е. стопка будет перемещена либо на первый либо на второй диск. Однако, так или иначе стопка N дисков будет перемещена согласно установленным правилам на один из не занятых стержней (либо на первый (B) либо на второй стержень (C)).

Заключение

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

2. Для организации разветвлений и циклов могут быть использованы различные операторы; выбор того или иного оператора в конкретном случае остаётся за программистом.

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

4. При организации циклов особенно важны два момента: правильное построение начала цикла и его конца. Важно также обеспечить стыковку цикла с остальной частью алгоритма или циклов друг с другом при их вложенности.

5. СА может быть представлена с разной степенью подробности. Так, предопределённый процесс, например блок ввода/вывода, может включать в себя несколько циклов; визуально фрагмент СА, включающий в себя этот блок, будет выглядеть линейным. В действительности линейными могут быть только очень простые алгоритмы или их некоторые фрагменты.

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

Массивы и работа с ними

Описание массивов

Массив — это упорядоченное множество однотипных переменных (элементов массива), объединенных общим именем и отличающихся номерами (индексами). Массивы сходны с такими понятиями в математике, как векторы и матрицы.

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

Таблица 5

Температура воздуха

Время измерения, ч			…
Температура, °С			…		17.5

Этот массив (таблица) содержит 24 элемента, пронумерованных от 1 до 24. Так, второй элемент массива имеет значение 16, а двадцать третий — 18.

Примеры таких массивов есть не только в математике. Всем хорошо известна пушкинская строка: «И тридцать витязей прекрасных...». Имен витязей и их отличительных характеристик мы не знаем. Для нас все тридцать вполне могут выступать под одним именем «Дружина». Таким образом, если у простых переменных имя относится только к одной ячейке, то у массивов одно имя обозначает множество ячеек памяти, отличающихся только номерами (индексами). Значения индексов указываются в скобках справа от имени массива и однозначно определяют положение переменной в массиве. Например:

а(1: 5) — массив (вектор) из пяти элементов: а(1), а(2), а(3), а(4), а(5);

b(1: 2, 1: 3) — массив (матрица) из шести элементов: b(1, 1), b(l, 2), b(l, 3), b(2, l), b(2, 2), b(2, 3).

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

Диапазон изменения индексов на каждой позиции определяется парой чисел — минимальным и максимальным значениями индекса, разделенными двоеточием. Если нижняя граница (минимальное значение) равна единице, то ее можно не указывать.

Длина массива равна количеству элементов в массиве.

Размерность массива — это число индексов в списке индексов. Чаще всего на практике используются одно-, двух- и трехмерные массивы, графическая интерпретация которых показана на рис. 20 и 21. Из рисунков видно, что одномерный массив (рис. 20, а)можно представить «линией», состоящей из столбцов ячеек памяти. Двухмерный (рис. 20, б)массив — это «плоскость», состоящая из строк и столбцов ячеек памяти. Трехмерный (см. рис. 21) массив — это «куб», состоящий из плоскостей, строк и столбцов ячеек памяти. Кстати, одну ячейку памяти можно в общем случае представить одномерным массивом, состоящим из одного столбца, и обращаться к ней как к Х(1).

Существуют массивы и большей размерности — четырехмерные, пятимерные и т.д. Например, в алгоритмическом языке ПЛ/1 допускается применение массивов размерностью до шестидесяти четырех. Как представить себе многомерные массивы? — Очень просто: четырехмерный массив — это «линия», состоящая, в свою очередь, из столбцов «кубов» (трехмерных массивов) или, другими словами, «линия кубов». Пятимерный массив — это «плоскость», состоящая из строк и столбцов «кубов», или «плоскость кубов». Шестимерный массив — это «куб», состоящий из плоскостей, строк и столбцов «кубов», или «куб кубов» («куб второй степени»). Продолжив градацию, можно сказать, например, что девятимерный массив — это «куб кубов кубов», или «куб кубов второй степени» («куб третьей степени»).

Рис. 20. Массивы: а — одномерный; б — двухмерный

Рис. 21. Трехмерный массив

Для того чтобы «объяснить» компьютеру, что мы будем работать с массивами, необходимо в специальном предписании «Список данных...» указать имя и границы изменения индексов массива. Предписание «Список данных» может включать в себя константы, переменные и массивы. В нем указывается, сколько ячеек памяти следует выделить в машине, чтобы записать все необходимые данные.

Например:

...Список данных:

Константы: Pi=3.14159;

Q=1.5678;

Переменные: а, b — целый;

х — вещественный;

с — символьный;

Массивы: у (1: 2, 1: 3) — вещественный;...

В разделах «Переменные» и «Массивы» желательно указать тип используемых переменных и массивов.

Выборка элементов массивов

Работа с массивами сводится к работе с его элементами. Обращение к элементам массива осуществляется с помощью переменной с индексом. Так, х(1, 5) — элемент массива х, расположенный на пересечении первой строки и пятого столбца.

Пример. Заданы два двухмерных массива х(1: 2, 1: 2) и у(1: 2, 1: 2):

Определить значение: Н: = х(1, 1) • у(2, 1) + х(2, 2).

После выборки указанных элементов и выполнения операции присваивания получим: Н=14.

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

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

с: = а + b; с: = а • b; с: = а – b,

что означает соответственно суммирование, умножение и вычитание элементов массивов а и b (с одинаковыми индексами) и запись результатов в массив с.

Для того чтобы задать всем элементам массива одинаковые значения, например 5, можно записать: а: = 5, где а — массив. В дальнейшем мы будем пользоваться такой записью, чтобы сократить, упростить написание алгоритма, считая элементарными предписания: ввод и вывод всего массива, присваивание всему массиву каких-либо значений и т.д. На самом деле, за редким исключением, такие операции можно осуществить только при работе с каждым элементом массива в отдельности, используя для этого циклические операторы.

Заключение

7. Необходимо повышенное внимание уделять особым случаям, которые встречаются в данных либо в формулах (например, в алгоритме нахождения минимального числа множества – это случай, когда входное множество содержит один элемент либо оно пустое; при некоторых вычислениях возникает необходимость деления на 0 и т.п.).

Общая характеристика этапов решения задачи с использованием ЭВМ

Человечество живет в мире алгоритмов и программ. Например, все без исключения физиологические процессы — это огромная, тщательно отлаженная и сложно устроенная «библиотека» программ поведения организма. Основы алгоритмизации и программирования фундаментальны и имеют общий характер, приближающий их к основным законам математики, речи или письма. В процессе решения задачи с применением компьютера пользователь самостоятельно или с помощью специалистов проходит ряд этапов, которые показаны на рис. 1.

На всех этапах подготовки задачи к решению и при ее решении на ЭВМ необходимо учитывать особенности работы вычислительной техники:

• огромное быстродействие ЭВМ и абсолютную исполнительность:

• ограничения на объемы памяти, которые могут отводиться для записи чисел, переменных и т.п.;

Рис. 1. Этапы решения задачи на ЭВМ

• отсутствие у ЭВМ интуиции и чувства здравого смысла;

• способность ЭВМ решать только ту задачу, программу решения которой ей подготовил человек.

Рассмотрим последовательность прохождения этапов (см. рис. 1) на примере решения простой задачи.

На первом этапе формулируются условия задачи (концептуальная модель), например, в словесной форме: функция f(x) должна получить значение, равное единице, если переменная х больше нуля, и нуль, если переменная х принимает другие значения.

Для уяснения содержания задачи можно представить ее в графическом виде — отложить на числовой оси точку нуль и отметить значения переменной х, при которых функция f(x) принимает значения 0 или 1 (рис. 2).

На втором этапе производится математическая постановка задачи (математическая модель):

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

Рис. 2. Графическая интерпретация условий задачи

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

• решение задачи описывается в виде аналитических зависимостей. Для нашей задачи:

• определяются конечные (выводимые) данные и их типы. В нашем случае конечными данными (результатом решения) является значение функции f(x) целого типа.

На третьем этапе осуществляется разработка алгоритма. Алгоритмизация выступает как связующее звено между «домашними» этапами решения задачи и непосредственно общением человека с компьютером. Именно на этом этапе начинаются сложности у людей, не имеющих специальной подготовки в области программирования (поэтому значительное внимание при дальнейшем изложении материала будет уделено умению читать и составлять алгоритмы). Алгоритм решения нашей задачи показан на рис. 3.

На четвертом этапе решения задачи алгоритм переводится в программу, записанную на языке высокого уровня. Ниже приводятся программы на языках Pascal и C++, которые реализуют данный алгоритм.

Pascal:

program zadacha;

Var x: real; f: integer;

begin

Read(x); WriteLn ('x=', x); If x> 0 Then f: =l Else f: =0;

WriteLn('f=', f);

End.

C++:

# include < iostream.h>

void main (void)

{

float x; int f;

cin> > x;

cout< < " x=" < < x< < endl;

f=(x> 0)? 1: 0;

cout< < " f=" < < f< < endl;

}

Рис. 3. Алгоритм решения задачи

На пятом этапе программа вводится в память компьютера, осуществляются ее отладка и решение.

В процентном отношении время, затрачиваемое пользователем на выполнение каждого из этапов при решении задачи с помощью ЭВМ (на выполнение всех этапов положим 100%), распределяется примерно так:

– на первый этап затрачивается 5 %;

– на второй — 5 %;

– на третий — 20 %;

– на четвертый — 10 %;

– на пятый — 60 %,

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

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

Предыдущая12 3 4 5 6 7 8 Следующая