Опция графика, выводящего прямоугольные импульсы:

Trace – Type - Step

а) Импульсы стартуют с	б) Импульсы стартуют с
максимального значения	минимального значения

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

Рис. 3.6. Вывод результата работы программы на график.

Позиция 5 закончена. Help закончен.

§12. Учебная задача

12.1. Введение

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

сти и развитого мышления) может привести к успеху:

Фаза 1. Понять существо задачи.

Фаза 2. Разработать план решения задачи. Фаза 3. Выполнить план.

Фаза 4. Оценить точность решения, а также его потенциал в качестве средства для решения других задач.

115

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

Применительно к процессу разработки программ эти фазы таковы:

Фаза 1. Понять существо задачи.

Фаза 2. Предложить идею алгоритма.

Фаза 3. Сформулировать алгоритм и реализовать его в виде программы.

Фаза 4. Оценить точность программы, а также ее потенциал в качестве средства для решения других задач.

Одно из самых распространенных заблуждений неопытных программистов: СРАЗУ садиться за ЭВМ – авось идея явится сама собой. Такое никогда не происходит. Пялиться в оболочку операционной системы или интерфейс языка программирования, не имея плана решения задачи, БЕССМЫСЛЕННО: это ВСЕГДА приводит к потерям времени и, в конечном счете, к утрате интереса к профессии.

Запомните: время, потраченное на составление программы, ОБРАТНО ПРОПОРЦИОНАЛЬНО времени, затраченному на обдумывание задачи и выработку идеи ее решения!

12.2. Общие положения

(ПРОЧИТАЙТЕ ОБЯЗАТЕЛЬНО! Не начинайте сразу программировать. Вначале придумайте АЛГОРИТМ: это сэкономит очень много времени!)

Иллюстрация общих рекомендаций по технологии решения задач (на примере решения учебной задачи)

Постановка задачи.

ДАНО: массив чисел.

ПОЛУЧИТЬ: функцию, возвращающую значение максимального элемента массива и номер позиции в массиве, на которой этот элемент записан.

Исходные данные: массив чисел M:

2.21.9

M := 0.622..352.1

116

12.3. Выполнение фазы 1 решения задачи «Понять существо задачи»

Если на массив посмотрит человек (рис. 3.7), то он сразу увидит максимальный элемент (в нашем примере 2.5) и скажет, что этот элемент расположеннапозиции№4 (счетпозиций, каквMathcad’е, снулевого, рис. 3.8).

Рис. 3.7. Исходные данные.

Рис. 3.8. Точка и позиция максимума.

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

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

Примечание: Вы уже знаете, что есть и другие, более совершенные ЭВМ, осуществляющие параллельные расчеты: SIMD и MIMD-машины, нейрокомпьютеры и др.). Но для данной задачи мы будем использовать простейшую схему последовательных вычислений.

117

12.4. Выполнение фазы 2 решения задачи «Предложить идею алгоритма»

Давайте придумаем алгоритм, который будет похож на описанный выше «человеческий» способ обнаружения максимума, но будем «показывать» машине элементы массива последовательно. Для этого полезно представить себе, что Вы – не Вы, а ЭВМ, и логика у Вас машинная, а не человеческая. Покажем машине нулевой первый элемент (рис. 3.9). Поскольку больше ничего машина «не видит», она решит, что это и есть максимум, а номер его позиции – нулевой (рис. 3.10). Предполагаемое значение максимума равно 2.2.

Рис. 3.9. Показ нулевого элемента.

Затем покажем машине первый элемент (рис. 3.11). ЭВМ «увидит», что он меньше первого и сохранит прежнее значение предполагаемого максимума (на нулевой позиции массива). О первом элементе машина «забудет» как о бесперспективном (поскольку ранее уже найден элемент, значение которого больше).

Затем покажем второй элемент (рис. 3.12). Ситуация та же: предположение о максимуме на нулевой позиции останется в силе.

Предполагаемый		Предполагаемый		Предполагаемый
		максимум		максимум
максимум

Рис. 3.10. Предположение о	Рис. 3.11. Показ первой точ-	Рис. 3.12. Показ второй
максимуме на основе показа	ки. Предполагаемый макси-	точки. Предполагаемый
нулевого элемента.	мум остается на прежней	максимум по-прежнему
	позиции.	там же.

118

Когда же мы приоткроем третью точку, ситуация изменится (рис. 3.13). Значение в этой точке оказалось больше, чем в той, которую машина держала в памяти как подозреваемую на максимум. Поэтому машина «передумает»: теперь она будет предполагать, что максимум – на третьей позиции, а значение максимума равно 2.3 (о значении 2.2 можно забыть). При показе четвертой точки (рис. 3.14) машина снова «передумает», т. к. новое значение (2.5) больше найденного ранее (2.3).

Показ пятой точки (рис. 3.15) не приведет к изменению предположения омаксимуме(значениевнейменьше, чемнайденноеранеезначение2.5).

Предполагаемый		Предполагаемый		Предполагаемый
максимум		максимум		максимум

Рис. 3.13. Показ третьей точки. Значение БОЛЬШЕ прежнего предположения о максимуме. Теперь предполагаемый максимум – на третьей точке.

Рис. 3.14. Показ четвер-	Рис. 3.15. Показ послед-
той точки. Положение	ней точки. Предположе-
предполагаемого макси-	ние о максимуме не из-
мума снова перемещает-	меняется.
ся.

Поскольку все точки исчерпаны, то машина покажет ответ (рис. 3.16): максимум – на четвертой (считая от нулевой) позиции массива, значение максимума равно 2.5.

Рис. 3.16. Окончательный диагноз максимума.

119

Теперьзаметим, чтовдействияхмашинынаблюдаетсяЦИКЛИЧНОСТЬ:

–показ ОЧЕРЕДНОГО элемента;

–сравнение его с текущим ПРЕДПОЛАГАЕМЫМ МАКСИМУМОМ:

–если:

очередной элемент меньше ПРЕДПОЛАГАЕМОГО МАКСИМУМА или равен ему, оставить предположение в силе, «забыть» об очередном элементе;

– иначе

(т. е. если очередной элемент БОЛЬШЕ предполагаемого максимума), то переопределить предполагаемый максимум, т. е считать ОЧЕРЕДНОЙ элемент новым ПРЕДПОЛАГАЕМЫМ МАКСИМУМОМ, аостаром«забыть»;

–так делать, пока не будут просмотрены ВСЕ элементы массива;

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

Таким образом, задача придумывания идеи алгоритма решена.

12.5.Выполнение фазы 3 «Сформулировать алгоритм

и реализовать его в виде программы»

Для этого используем условный язык, пригодный для записи алгоритма и чтения его человеком, но «не понимаемый» машиной. Такой язык называется метаязыком. В нём, в отличие от машинных языков, нет подробностей о вводе и выводе данных, но алгоритм записывается так, что его легко перевести на любой машинный язык.

Мы будем использовать метаязык «исполнителей», предложенный академиком А. П. Ершовым. Под исполнителем (нашей воли) понимается машина, на которой реализуется алгоритм.

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

ДАНО: массив действительных чисел M с номерами; нумерация начинается с нуля.

ПОЛУЧИТЬ: функцию max_value(M) с аргументом – массивом M, возвращающую вектор значений, нулевой элемент которого равен максимальному числу из массива M, а первый элемент равен номеру позиции, на которой размещается максимальное число из массива M.

НАЧАЛО

ПРИСВОИТЬ значение нулевого элемента массива M переменной max, которую на данной стадии работы алгоритма ЭВМ будет считать предполагаемым максимумом;

120

ПРИСВОИТЬ значение нуль переменной number_max (мы будем обозначать number_max номер позиции, на которой ЭВМ предполагает размещение максимума);

РАССЧИТАТЬ число элементов в массиве M, присвоить переменной n значение, равное числу элементов в массиве M;

ЦИКЛ ДЛЯ КАЖДОГО k = 1,…, n ВЫПОЛНЯТЬ: ПРОЧЕСТЬ k-й элемент Mk из массива M; СРАВНИТЬ его с предполагаемым максимумом max; ЕСЛИ окажется, что Mk > max, ТО

ЗАМЕНИТЬ значение max на Mk;

ЗАМЕНИТЬ значение number_max на значение k; КОНЕЦ ЕСЛИ КОНЕЦ ЦИКЛА

ПРИСВОИТЬ значение max нулевому элементу массива, возвращаемого функцией max_value(M) и значение number_max первому элементу массива, возвращаемого функцией max_value(M);

КОНЕЦ

Реализация алгоритма с помощью средств программирования

Mathcad.

	2.2			Вначале введите исходные данные (записаны слева от тек-
		1.9		ста).
		0.6		Затем выведите график (он понадобится для проверки
M :=				алгоритма). График получится как на рис. 3.7. Для его выво-
		2.3		да определите число элементов в массиве (n : = rows(M) - 1 с
		2.5		учетом нумерации в Mathcad с нулевого элемента), задайте
				диапазон изменения аргументов s : = 0 .. n (для многоточия
		2.1		используйте клавишу <точка_с_запятой>).

Затем попытайтесь составить программу без подсказок, прямо по тексту Исполнителя. В приложении 2 помещено описание программных средств Mathcad.

Если не сумеете, то используйте текст программы, приведенный ниже. Но обязательно комментируйте КАЖДУЮ строчку программы.

121