ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.03.2024
Просмотров: 102
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Внешне эти фазы просты, но если задача трудна, то приходится ре- шать ее с возвратами к предыдущим фазам для корректировки или даже полного пересмотра идеи решения.
Применительно к процессу разработки программ эти фазы таковы:
Фаза 1
. Понять существо задачи.
Фаза 2
. Предложить идею алгоритма.
Фаза 3
. Сформулировать алгоритм и реализовать его в виде про- граммы.
Фаза 4
. Оценить точность программы, а также ее потенциал в каче- стве средства для решения других задач.
Одно из самых распространенных заблуждений неопытных про- граммистов: СРАЗУ садиться за ЭВМ – авось идея явится сама собой.
Такое никогда не происходит. Пялиться в оболочку операционной систе- мы или интерфейс языка программирования, не имея плана решения за- дачи, БЕССМЫСЛЕННО: это ВСЕГДА приводит к потерям времени и, в конечном счете, к утрате интереса к профессии.
Запомните: время, потраченное на составление программы, ОБРАТНО
ПРОПОРЦИОНАЛЬНО времени, затраченному на обдумывание зада- чи и выработку идеи ее решения!
12.2.
Общие положения
(ПРОЧИТАЙТЕ ОБЯЗАТЕЛЬНО! Не начинайте сразу программиро- вать. Вначале придумайте АЛГОРИТМ: это сэкономит очень много вре мени!) ллюстрация общих рекомендаций по технологии решения задач ере решения учебной задачи)
ачи
АНО
: массив чисел.
ОЛУЧИТЬ
: функцию, возвращающую значение максимального элемента массива и номе на которой этот элемент записан.
ые
: массив чисел M:
-
И
(на прим
Постановка зад
Д
П
р позиции в массиве,
Исходные данн
2.2 1.9
⎛
⎜
⎜
⎞
⎟
⎟
M
2.3 0.6
⎜
⎟
⎟
:=
⎜
⎟
⎜
2.5 2.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
Когда же мы приоткроем третью точку, ситуация изменится (рис.
.13
едумает»: теперь она будет предполагать, что максимум – на трет ния
3
). Значение в этой точке оказалось больше, чем в той, которую ма- шина держала в памяти как подозреваемую на максимум. Поэтому ма- шина «пер ьей позиции, а значение максимума равно 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
120
СТЬ:
– показ
– ср
:
– если: очередной элемент меньше ПРЕДПОЛАГАЕМОГО МАКСИМУМА или равен ему, оставить предположение в силе, «забыть» об оче- редном элементе;
– иначе
(т. е. если очередной элемент БОЛЬШЕ предполагаемого мак- симума), то переопределить предполагаемый максимум, т. е считать ОЧЕРЕДНОЙ э ент новым ПРЕДПОЛАГАЕМЫМ
М
;
–
ут ен
– по кличес ать д
й. Такой зык
Мы будем использовать метаязык «исполнителей», предложенный академик овым. Под
(нашей в тся машина, на реализуется алгоритм
Исполнитель функция max_value с аргументом M (M – массив зна- чений точек с нумерацией, начиная с нулевой). Исполнитель должен со- общить пользователю значение максимального элемента массива M и номер позиции, на которой находится этот максимум.
ДАНО
: массив действительных чисел M с номерами; нумерация на- чинается с нуля.
ПОЛУЧИТЬ
: функцию max_value(M) с аргументом – массивом M
возвращающую вектор значений, нулевой элемент которого равен мак- с
ив ент
- ц
ся из
Н
ПР
нулевого элемента массива M переменной max, к
Теперь заметим, что в действиях машины наблюдается ЦИКЛИЧНО
ОЧЕРЕДНОГО элемента; авнение его с текущим ПРЕДПОЛАГАЕМЫМ МАКСИМУМОМ
лем
МАКСИМУ
так делать, пока не буд сле окончания ци
ОМ, а о старом «забыть»
просмотрены ВСЕ элем кого просмотра показ ассиве и ты массива; результат: значение х, на ко максимума и номер позиции в м схо ных данны торой расположен максимум.
Таким образом, задача придумывания идеи алгоритма решена.
12.5.
Выполнение фазы 3 «Сформулировать алгоритм
и реализовать его в виде программы»
Для этого используем условный язык, пригодный для записи алго- ритма и чтения его человеком, но «не понимаемый» машино я
называется метаязыком. В нём, в отличие от машинных языков, нет подробностей о вводе и выводе данных, но алгоритм записывается ак, что его легко перевести на любой машинный язык. т
ом А. П. Ерш которой исполнителем оли) понимае
, имальному числу из масс ии, на которой размещает
АЧАЛО
СВОИТЬ значение а M, а первый элем максимальное число равен номеру пози массива M.
И
оторую на данной стадии работы алгоритма ЭВМ будет считать предполагаемым максимумом;
ПРИСВОИТЬ значение нуль переменной number_max (мы будем обо- значать number_max номер позиции, на которой ЭВМ предполагает размещение максимума);
РАССЧИТАТЬ число элементов в массиве M, присвоить переменной n значение, равное числу элементов в массиве M;
ЦИКЛ ДЛЯ КАЖДОГО k = 1,…, n ВЫПОЛНЯТЬ:
ПРОЧЕСТЬ k-й элемент M
k
из массива M;
СРАВНИТЬ его с предполагаемым максимумом max;
ЕСЛИ окажется, что M
k
> max, ТО
ЗАМЕНИТЬ значение max на M
k
;
ЗАМЕНИТЬ значение number_max на значение k;
КОНЕЦ ЕСЛИ
КОНЕ
ае-
КОНЕЦ
Реал горитма с помощью средств программирования
Mathcad. рки точия используйте клавишу <точка_с_запятой>).
, прямо по
Ц ЦИКЛА
ПРИСВОИТЬ значение max нулевому элементу массива, возвращ ункцией max_value(M) и значение number_max первому мого ф элементу массива, возвращаемого функцией max_value(M);
изация ал
Вначале введите исходные данные (записаны слева от тек- ста).
Затем выведите график (он понадобится для прове алгоритма). График получится как на рис. 3.7. Для его выво- да определите число элементов в массиве (n : = rows(M) - 1 с учетом нумерации в Mathcad с нулевого элемента), задайте диапазон изменения аргументов s : = 0 .. n (для много
Затем попытайтесь составить программу без подсказок тексту Исполнителя. В приложении 2 помещено описание программных средств Mathcad.
Если не сумеете, то используйте текст программы, приведенный ни- же. Но обязательно комментируйте КАЖДУЮ строчку программы.
M
2.3 2.5
:=
2.2 1.9
⎛
⎞
⎜
⎟
⎜
⎜
⎟
⎟
0.6
⎜
⎜
⎜
⎟
⎟
⎟
⎝
⎠
2.1 121
Текст программы
Комментарий, см. опи-
сание Исполнителя
программы, а
такж
ния других задач»
ктор, возвра- щаем симальное число равно 2.5, раз- мещае
12.6.
Выполнение фазы 4 «Оценить точность
е ее потенциал в качестве средства для реше
После ввода протестируйте программу. Выведите ве ый функцией, и убедитесь, что мак тся на позиции 4: max_value M
( )
2.5 4
⎛
⎜
⎝
⎞
⎟
⎠
=
тесь обобщить программу так, чтобы она искала и мак поз
§13. Индивидуальные задания по части 3
чн в
ные числа в
В столбце 1 стью до 0.1 описание уч имеет вид, п
Переменной number_max присваивается нулевая пози- ение ксимуме max. Если условие выполняется – входим в конструкт if е
я рой он размещен ax
Переменной max присваивается значение нулевого элемента массива М (предполагаемый максимум) m _value M
( )
max
M
0
:=
←
ция массива М (позиция предполагаемого максимума)
Расчет числа элементов в массиве исходных данных
Цикл по номерам элементов массива, начиная с первого
Проверка условия – превышает ли текущее знач элемента массива величину предположения о ма number_max
0
←
n rows M
( )
1
−
←
M
max
>
if k
1 n
∈
for k
При выполнении условия заменяем значение мак- симума на текущее значение элемента массива, а номер – на номер позиции текущего элемента
Если услови не выполняетс – в конструкцию if алго- max
M
k
←
number_max k
←
max number_max
⎛
⎜
⎝
⎞
⎟
⎠
ритм «не заходит»
После завершения цикла вводим шаблон матрицы
(<Ctrl>+<M>) и присваиваем ее нулевому элементу зна- чение максимума, а первому – номер позиции, на кото-
А затем попытай симальный, и минимальный элемент массива M и указывала номера иций в массиве, на которых эти элементы расположены.
Общая часть всех задач
: в файле April.prn находятся данные о среднесуто ых температурах в каждые сутки апреля. Структура файла
столбце № 0 записаны даты апреля (по формату это – обыч- форма
(рис. 3.17): те с двумя позициями после десятичного разделителя). записаны среднесуточные температуры, измеренные с точно-
°С. Для того чтобы осмыслить задачу (фазы 1 и 2, см. в §12 ебной задачи), постройте график изменения температур. Он оказанный на рис. 3.18.
122
Столбец № 0: Столбец № 1:
Дата
Температура
,
Варианты
:
№ 1
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать мас- сив. В столбце № 0 должны быть даты апреля, в которые температуры были отрицательными, а в столбце № 1 – значения этих отрицательных температур. Если отрицательных температур в массиве исходных данных нет, функция должна выводить сообщение «Нет дней с отрицательной температурой».
№ 2
. Разработайте программу-функцию, аргументом которой явля тся массив дат и температур апреля. Функция должна возвращать мас
- ое атур апреля. Функция должна возвращать дату, начиная с которой сумма всех положительных температур с начала апре- ля превысит заданное значение (для примера 10
°С). Функция должна ом
№ 4
. Разработайте программу-
, аргументом которой явля- ется массив дат вращать дату, для кото им ое к 0) значе- ние отрицательной температуры. Если отрицательных температур в мас-
Рис. 3.17. Структура файла
April.prn.
Рис. 3.18. Изменение температур в апреле.
Среднесуточные градусы температуры
Цельси я
Даты апреля
-
- е
сив средних значений температур за 5-дневки (если хотите, усложните задачу, чтобы функция возвращала массив средних температур за задан н
число дней, не обязательно за 5).
№ 3
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и темпер п
очь крестьянам установить дату сева. Эта дата определяется по числу накопленных (т. е. просуммированных) положительных температур с начала апреля. Пример: для сева яровой пшеницы накопленные положи- тельные температуры должны быть не менее 10
°С. функцию и температур апрел Функция должна воз ело место самое большое (т. е. самое близк я. рой
123
сиве ункцию, аргументами которой явля- ются: (а) массив дат и температур апреля; (б) шифр дня недели, прихо- дящегося на 01.04. Шифры: 0 – воскресенье, 1 – понедельник, … , 6 – суббота. Функция должна возвращать массив дат и температур всех вос- кресений апреля.
№ 7
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать значе- ние высоты ростков помидоров, посаженных 01.04, если известна форму- ла, определяющая высоту. Высота ростков на текущую дату пропорцио- нальна корню квадратному из суммы положительных температур, накоп- ленных к текущей дате; коэффициент пропорциональности равен 1.5.
№ 8
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать значе- ние месячной (за апрель) оплаты за электроэнергию, израсходованную
Вашей сплит-системой. Сплит-система настроена на поддержание задан- ной температуры в комнате (например, на 22
°С). Расход электроэнергии в данные орционален квадрату отклонения температуры в эти спл исходных данных нет, функция должна выводить сообщение «Нет дней с отрицательной температурой».
№ 5
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать:
(а) дату, для которой имело место значение температуры, самое близкое к среднемесячной температуре; (б) среднемесячную температуру; (в) зна- чение температуры, самое близкое к среднемесячной.
№ 6
. Разработайте программу-ф сутки проп т заданной д сутки о ля ит-системы. Коэффициент пропорционально- сти равен 0.01. Стоимость 1 кВт-ч электроэнергии равна 1.1 рубля.
№ 9
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать:
(а) продолжительность дня (светлой части суток), в который имела место самая высокая за весь апрель температура; (б) дату этого дня; (в) значе- ние температуры в этот день. Указание. Продолжительность светлой час- и су т
ток внутри годичного периода изменяется по закону синуса. Мини- мальное значение (9 часов) приходится на 22.12. Максимальное значение
(15 часов) приходится на 22.06. Выведите формулу для продолжительно- сти светлой части суток и используйте ее для расчета продолжительности светлой части суток в апреле.
№ 10
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать
(а) продолжительность периода, в течение которого все температуры от текущей даты до конца апреля были положительными; (б) дату, начиная
124
№ 7
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать значе- ние высоты ростков помидоров, посаженных 01.04, если известна форму- ла, определяющая высоту. Высота ростков на текущую дату пропорцио- нальна корню квадратному из суммы положительных температур, накоп- ленных к текущей дате; коэффициент пропорциональности равен 1.5.
№ 8
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать значе- ние месячной (за апрель) оплаты за электроэнергию, израсходованную
Вашей сплит-системой. Сплит-система настроена на поддержание задан- ной температуры в комнате (например, на 22
°С). Расход электроэнергии в данные орционален квадрату отклонения температуры в эти спл исходных данных нет, функция должна выводить сообщение «Нет дней с отрицательной температурой».
№ 5
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать:
(а) дату, для которой имело место значение температуры, самое близкое к среднемесячной температуре; (б) среднемесячную температуру; (в) зна- чение температуры, самое близкое к среднемесячной.
№ 6
. Разработайте программу-ф сутки проп т заданной д сутки о ля ит-системы. Коэффициент пропорционально- сти равен 0.01. Стоимость 1 кВт-ч электроэнергии равна 1.1 рубля.
№ 9
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать:
(а) продолжительность дня (светлой части суток), в который имела место самая высокая за весь апрель температура; (б) дату этого дня; (в) значе- ние температуры в этот день. Указание. Продолжительность светлой час- и су т
ток внутри годичного периода изменяется по закону синуса. Мини- мальное значение (9 часов) приходится на 22.12. Максимальное значение
(15 часов) приходится на 22.06. Выведите формулу для продолжительно- сти светлой части суток и используйте ее для расчета продолжительности светлой части суток в апреле.
№ 10
. Разработайте программу-функцию, аргументом которой явля- ется массив дат и температур апреля. Функция должна возвращать
(а) продолжительность периода, в течение которого все температуры от текущей даты до конца апреля были положительными; (б) дату, начиная
124