1 Этапы решения задач с использованием ЭВМ (стр. 1 )

1 ЭТАПЫ РЕШЕНИЯ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ЭВМ

Понятие «решение задачи» при использовании ЭВМ включает в себя гораздо больше, чем просто вычисления. В процессе подготовки задач к решению с помощью ЭВМ можно выделить ряд этапов:

1) формулировка задачи в терминах некоторой прикладной области знания (математики, физики, экономики и т. д.);

2) формализация задачи, построение математической или информационной модели;

3) выбор метода решения формализованной задачи (включая определение информационных технологий и (или) средств программной обработки данных);

4) разработка проекта решения или алгоритма;

5) тестирование и отладка программы;

6) передача программы в эксплуатацию.

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

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

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

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

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

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

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

2 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

Метод решения представляет собой формализованное описание способа решения поставленной задачи.

2.1 Основные требования

Основными требованиями, предъявляемыми к методам решения задач, являются следующие:

1) метод решения должен обеспечивать получение верных результатов для любых допустимых исходных данных;

2) структуры и типы данных, используемые в методе, должны быть допустимыми в программировании;

3) описание метода должно быть точным, понятным и однозначным;

4) метод должен обеспечивать рациональное решение задачи.

2.2 Способы описания методов решения задач

Существует несколько способов описания методов решения задач:

1) математическое описание (с помощью математических терминов, формул, определений и т. д.);

2) словесное описание (с помощью кратких, но ясных формулировок );

3) графическое описание (с помощью рисунков, графиков, геометрических построений и т. д.).

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

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

2.3 Классификация методов решения задач

Методы решения задач подразделяются на специализированные и универсальные (табл.2.1).

Таблица 2.1 - Классификация методов решения задач

Универсальные	Специализированные
1. Пошаговая детализация (последовательное уточнение, разбиение задачи на подзадачи, «разделяй и властвуй»), т. е. каждая подзадача решается отдельно, а затем они соединяются вместе.	1. Метод перебора (перебирая элементы, значения, выполняем необходимые действия). Пример. Найти количество нулевых элементов массива Х.
2. Сведение одной задачи к другой, уже решенной (например, задача нахождения минимума среди N элементов сводится к задаче нахождения минимума среди двух элементов).	2. Метод накопления. Пример. Найти сумму элементов массива Х.
3. Метод последовательных приближений (например, решение задачи нахождения суммы бесконечного ряда). Пример. Вычислить Замечание При заданном n задача решается методом накопления.
4. Другие методы.

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

Метод восходящего проектирования предусматривает «сборку» основного алгоритма из отдельных модулей, выполняющих вспомогательные функции и разработанных независимо друг от друга.

3 ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМА

3.1 Определение алгоритма

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

Происхождение термина «алгоритм» связывают с именем великого узбекского математика и астронома аль-Хорезми (жившего в IX веке), который в основополагающих трудах по арифметике и алгебре разработал, в частности, правила выполнения четырех арифметических действий над многозначными десятичными числами. В дальнейшем термин «алгоритм» стали использовать вообще для обозначения последовательности действий, приводящей к решению любой проблемы. Умение решать задачи определенного типа (не обязательно математические) всегда означает владение соответствующим алгоритмом.

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

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

Один шаг выполнения алгоритма называется оператором или командой.

3.2 Свойства алгоритмов

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

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

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

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

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

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

3.3 Способы задания алгоритмов

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

Существующие способы записи алгоритма можно классифицировать следующим образом:

- словесный;

- графический;

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

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

Графический способ ( блок-схема, R-схема ) – графическое изображение логической структуры алгоритма. Используемые геометрические фигуры ( блоки ) имеют определенную форму в зависимости от характера операции.

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

Правила записи алгоритмов с использованием графических способов и алгоритмического языка приведены в приложении Б.

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

Рассмотрим на примере решения одной и той же задачи несколько способов задания алгоритма.

Пример3.1. Составить алгоритм поиска меньшего из двух чисел a, b.

Словесный способ.

Шаг 1. Задать числовые значения величин a, b.

Шаг 2. Если a<b, то y положить равным а, иначе y положить равным b.

Шаг 3. Вывести значение y.

Шаг 4. Конец.

Графический способ (рис.3.1, 3.2).

 

Рисунок 3.1- Блок-схема алгоритма решения задачи

Рисунок 3.2 - R-схема алгоритма решения задачи

Учебный ( школьный ) алгоритмический язык.

алг минимальное из двух

арг а, b

рез у

нач

если а<b

то у:=а

иначе у:=b

все

кон

4 Эффективность алгоритма

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

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

- оценка точности решения задачи;

- оценка вычислительной сложности решения;

- оценка затрат времени на решение задачи;

- оценка объема используемой памяти.

Иногда выбирается некоторый интегральный критерий, включающий комбинацию оценок.

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

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

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

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

При реализации алгоритма на ЭВМ существенным критерием оценки эффективности алгоритма считается экономное расходование памяти.

Рассмотрим пример решения задачи обмена значений переменных А и В с точки зрения различных критериев эффективности.

Алгоритм, эффективный с точки зрения экономии памяти:

А:=А+В

В:=А-В

А:=А-В

Алгоритм, эффективный с точки зрения быстродействия:

Р:=А

А:=В

В:=Р

Следует отметить, что погоня за эффективностью алгоритма не должна наносить "ущерба" ясности алгоритма.

Рассмотрим пример нахождения минимального значения для двух переменных А и В.

Алгоритм, эффективный с точки зрения быстродействия и компактности записи:

MIN:=(A+B-abs(A-B))/2

Обычный алгоритм (менее компактный, но более наглядный):

алг минимальное из двух

арг A, B

рез MIN

нач

если A<B

то MIN:=A

иначе MIN:=B

все

кон

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

5 основные типы алгоритмов

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

5.1 Алгоритмы линейной структуры

Алгоритмы линейной структуры – алгоритмы, в которых операторы выполняются последовательно друг за другом в порядке, заданном схемой алгоритма. Такой порядок выполнения называется естественным.

Команды линейных алгоритмов записываются следующим образом:

а) школьный алгоритмический язык:

<Оператор 1>

<Оператор 2>

. . .

< Оператор N>

б) блок-схема (рис.5.1);

< Оператор 1 >

< Оператор 2 >

. . .

< Оператор N >

Рисунок 5.1 - Блок-схема линейного алгоритма

в) R-схема:

< Оператор 1>

< Оператор 2>

. . .

< Оператор N>

К линейным операторам относятся:

- присваивание;

- ввод;

- вывод;

- вызов вспомогательного алгоритма.

5.1.1 Оператор присваивания

Оператор присваивания позволяет изменить значение некоторой переменной.

Формат оператора:

<имя переменной>:=<выражение>

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

Пример 5.1.

Оператор присваивания	Комментарии
a:=3;	В переменную а заносится значение 3.
s:='a'+'b';	Переменная s получает значение 'ab'.
f:=a=b;	В переменную f заносится выражение логического типа (результат сравнения a и b).
x:=x+1;	Значение переменной х увеличивается на 1.
x+1:=x;	Неверная запись оператора присваивания (слева от знака присваивания вместо имени переменной записано выражение).

5.1.2 Оператор ввода

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

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

В остальных случаях оператор ввода записывается следующим образом:

а) блок-схема (рис. 5.2);

 

Рисунок 5.2 - Блок ввода в блок-схемах

б) R-схема (рис. 5.3).

 

Рисунок 5.3 - Блок ввода в R-схемах

Замечание. Список ввода может содержать только переменные.

5.1.3 Оператор вывода

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

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

В остальных случаях оператор вывода записывается следующим образом:

а) блок-схема (рис. 5.4);

 

Рисунок 5.4 - Блок вывода в блок-схемах

б) R-схема (рис. 5.5).

Рисунок 5.5 - Блок вывода в R-схемах

Список вывода может содержать: переменные, константы (в том числе строкового типа), выражения (пример на рис.5.6).

 

Рисунок 5.6 - Пример оператора вывода

5.2 Разветвляющиеся алгоритмы

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

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

Условный оператор записывается следующим образом:

а) школьный алгоритмический язык:

если <Условие> то

<Оператор(ы) 1>

иначе < Оператор(ы) 2>

все

если <Условие> то

< Оператор(ы) >

все

б) блок-схема (рис. 5.7);

в) R-схема (рис.5.8).

 

а) б)

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

Для полной формы записи при соблюдении условия необходимо выполнять действия, определенные операторами 1; при несоблюдении условия выполняется операторы 2.

Если используется сокращенная форма, то в случае соблюдения условия выполняются операторы, записанные после служебного слова «то». При несоблюдении же условия выполняется следующая после данного оператора команда.

Следует отметить, что блок-схема, в отличие от всех остальных способов записи алгоритма, позволяет реализовать два вида неполных условных операторов (см. рис.5.7).

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

Команды выбора записываются следующим образом:

а) школьный алгоритмический язык:

полная форма оператора

выбор

при <Условие 1>: <Оператор(ы)1>

при <Условие 2>: < Оператор(ы)2>

…

при <Условие N>: < Оператор(ы)N>

иначе < Оператор(ы)N+1>

все

сокращенная форма оператора

выбор

при <Условие 1>: < Оператор(ы)1>

при <Условие 2>: < Оператор(ы)2>

…

при <Условие N>: < Оператор(ы)N>

все

б) блок-схема (рис. 5.9);

а)	б)

Рисунок 5.9 - Блок-схема полной (а) и сокращенной (б)

форм оператора выбора

в) R-схема (рис. 5.10).

выбор

<Условие1>:<Оператор1>

<Условие2>:<Оператор2>

. . .

<Условие N>:<Оператор N>

иначе

<Оператор N+1 >

а)

выбор

<Условие1>:<Оператор1>

<Условие2>:<Оператор2>

. . .

<Условие N>:<Оператор N>

б)

Рисунок 5.10 - R-схема полной (а) и сокращенной (б)

форм оператора выбора

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