Программирование на Паскале. Выпуск 13
Очень долго не выходила эта рассылка: что-то маловато времени стало в сутках. Хотя в гостевой книге удавалось отвечать на некоторые вопросы. В последнем выпуске рассылки "Решение практических задач на Паскале", я анонсировал свои планы делать выпуски, ориентируясь на Free Pascal. Я веду курс программирования на языке высокого уровня. И начиная с этого учебного года стал делать это на Free Pascal. Сделал первый вариант лабораторных работ, который к осени размещу на нашем сайте. Тогда же, видимо, и рассылку "ту" буду вести на этом замечательном варианте Паскаля. Эту рассылку решил ориентировать по-прежнему на "старый, добрый" Turbo Pascal. Язык хорош, компилятор надежен, фирменная среда разработки программ проста в работе, имеется справка на русском языке, есть много книг и сайтов, посвященных программированию на Turbo Pascal. И, наконец, во многих учебных заведениях, преподавание ведут на этом языке.
И хотя описано, по-моему, все, может что и я внесу ...
В гостевой книге была просьба вычислить корни забавного уравнения, функция которого:
Решить не могу от того, что это не уравнение – отсутствует правая часть. Если правая часть равна нулю и корни нужно искать только действительные, то легко убедиться, что корень только один и он равен нулю. Все остальные корни могут быть только комплексными (имеются корень четной степени от отрицательного числа).
Однако автор сути вопроса так и не объяснил: нужно ли искать корни такого уравнения программно и каким методом. Дело в том, что если корни ищем в программе, то нужно использовать один из численных методов поиска корней уравнений. Для этих методов характерно следующее:
Раз решить нельзя, то решил сейчас просто показать, как это выражение вычислить с помощью рекуррентной функции. Рекуррентной называется такая, которая вызывает саму себя. Способ не самый эффективный, поскольку очень быстро расходуется стек программы: при каждом вызове подпрограммы в особую область памяти, выделенной операционной системой программе и называемой стеком, записывается адрес инструкции, которая будет выполнена после завершения работы подпрограммы, а также параметры, передаваемые подпрограмме. Освобождение этой памяти происходит только при выходе из подпрограммы. Поэтому, если при вызове подпрограммы в стек заносится M байт, а размер стека N, то после K вызовов, примерно равном N/M – программа прекратит работу. Переполнение стека очень опасно.
"Примерно равно" из-за того, что не только Ваша подпрограмма расходует стек, но и неявный, без Вашего участия, вызов системных подпрограмм.
Если добавить к этому недостатку еще и время, расходуемое на вызов подпрограммы, то получим одни недостатки. Однако есть примеры, когда без рекуррентных подпрограмм приходится писать много и малопонятно. Данные случай к таким не относится. Просто захотелось ...
Я привожу также пример вычисления выражения с помощью цикла.
Код программы, решающей задачу (комментарии ниже):
{$N+}
{$M 65520, 0, 0}
function GetRoots(x: Extended; pow: Integer;
const maxPow: Integer): Extended;
begin
if pow >= maxPow then GetRoots := exp(1/pow*ln(x))
else GetRoots := exp(ln(x + GetRoots(x, pow+1, maxPow))/pow)
end;
{Переменные нужны только для цикла, в рекурсивных вычислениях не используются}
var r, z: Extended;
p, maxP: Extended;
BEGIN
WriteLn(GetRoots(5, 2, 5)); {2322 - максимальное значение maxPow}
{решение задачи с помощью цикла}
z:=5; maxP:= 29292393;
r:= exp(ln(z)/maxP);
p:=maxP -1;
while p >= 2 do begin
r:= exp(ln(z+r)/p);
p:=p - 1
end;
WriteLn(r);
END.
Работа программы тестировалась в Borland Pascal 7.0 в реальном режиме работы. В защищенном будет отличаться директива
управления памятью, она должна иметь вид
Первой стоит директива, предписывающая использовать математический сопроцессор. Это нужно для того, чтобы использовать тип вещественных чисел Extended. Вторая директива – директива управления памятью. Первая цифра задает размер стека программы. Здесь максимально возможное в Borland Pascal 7.0 значение. Две другие – начало и конец "кучи", области памяти, где программа может размещать свои данные. Нам она не нужна. А ограничивать и ее нужно из-за того, что общая память, выделяемая программе фиксирована.
Рекуррентной функции GetRoots передается значение переменной x, знаменатель степени pow, и максимальное значение степени (n в формуле в самом начале). Функция работает так: если pow >= maxPow, то просто вычисляется значение корня степени pow числа x.
Поскольку в Turbo Pascal (не путайте: язык Turbo Pascal, а компилятор Borland Pascal) нет функции для вычисления корней больше 2, то используется такая формула: корень n степени от x = exp(n*ln(x)).
Если же значение pow меньше maxPow, то имени функции присваиваем значение exp(ln(x + вызов самой себя со степенью pow на 1 больше))/pow). При этом выполнение этого "экземпляра" функции прекратится (точнее, отложится на время), код ее будет вызван еще раз с новым значением pow.
Чтобы убедиться в этом, в меню Debug выберите пункт Call stack (показать стек) и выполняйте программу по шагам, нажимая клавишу F7. При каждом нажатии будут появляться новые строки вызова функции с новым параметром pow.
Когда дойдем до конечного значения pow, значение функции GetRoots наконец-то будет вычислено (в окне стека Вы увидите, что одна строка с GetRoots исчезнет). Это значение будет подставлено в значение предыдущего вызова. Оно тоже будет вычислено. Это значение будет подставлено ... и так до тех пор, пока не дойдем до самого первого вызова функции GetRoots. В окне стека все это будет прекрасно видно.
В скобках после WriteLn(GetRoots(5, 2, 5)); указано максимальное значение степени, которое еще не вызывает переполнение стека.
В конце приводится решение той же задачи с помощью цикла. Если в качестве переменной цикла использовать вещественное число, то значение максимальной степени может быть огромным, что и показано. Однако, это уже не так интересно :))
Темой следующего выпуска хочу сделать поиск слов в строке символов. Тоже была серия вопросов в гостевой ...