Warning: include(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include_once(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82

Warning: include_once(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82
Реализация рекурсивных и рекуррентных алгоритмов | Учебники

Главная > Mathematica 8 > Реализация рекурсивных и рекуррентных алгоритмов


Реализация рекурсивных и рекуррентных алгоритмов

Реализация рекурсивных и рекуррентных алгоритмов
Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:
scn[x_, n_] := Sin[x]^n + Cos[х]^n
scn[l, 2]
1
scn[x, 2]
1
scn[x, n]
Cos[x]n+ Sin[x]n
В этом простейшем примере результат вычислений есть возвращаемое функцией sen значение — численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.
Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри ее тела, а рекуррентность — получение результата на данном шаге по результатам вычислений на предшествующих шагах.
Рассмотрим, как это делается, с помощью описанных выше функций. Классический пример реализации рекурсивного алгоритма — вычисление факториала путем задания функции, в теле которой есть обращение к ней же самой:
f[n_] :=n*f[n-1];f[0]=l;f[1]=1;
Полезно, однако, обратить внимание на возможность явного задания результата для конкретных значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная с n=2 и выше, в соответствии с классическим определением факториала.
Для реализации рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или FixedPoint. В следующих примерах показано вычисление
квадратного корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции newtonS:
newtonS [x_] := N[ 1/2 ( х + 5/х )]
Nest[newton5, 1.0, 5]
2.23607
NestList [newtonS, 1.0, 5]
{1., 3., 2.33333, 2.2381, 2.23607, 2.23607}
FixedPoint [newtonS, 1.0]
2.23607
FixedPointList [newtonS, 1.0]
{1., 3., 2.33333, 2.2381, 2.23607, 2.23607, 2.23607, 2.23607}
FixedPointList [newtonS, 1.0, SameTest -> (Abs[#l- #2] < 10.A-4 &)]
{1., 3., 2.33333, 2.2381, 2.23607, 2.23607}
Обратите внимание на то, что функции Nest и FixedPoint дают единственный конечный результат, тогда как функции NestList и FixedPointList возвращают еще и все промежуточные результаты итераций. Последний пример иллюстрирует остановку вычислений по заданной погрешности, равной 10 -4 .
Далее зададим функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения f(x) при начальном значении х 0 = а, по следующим формулам:
x0=a;
xn=xn-1-f(xn-1)/f'(xn-1)
Эту функцию можно записать следующим образом:
newtoniter[f_, x0_, n_] :=Nest[(# — f [#]/f'[#]) &, N[x0] , n]
Тогда вычисления корня из выражения е^x — 2 с начальным приближением х 0 = 0.5 при числе итераций n можно организовать с помощью функций Nest и NestList:
newtoniter [Function [ {х} , Ехр[х] — 2.0], 0.5, 5]
0.693147
newtoniter [Function [ {х }, Ехр[х] — 2.0], 0.5, #] & /@ Range [5]
{0.713061, 0.693344, 0.693147, 0.693147, 0.693147}
newtoniterl[f_,x0_,n_] := NestList[ (#-f [#] /f ‘ [#] ) &,N[x0] , n]
newtoniterl [Function [{x} , Exp[x] — 2.0], 0.5, 5]
{0.5, 0.713061, 0.693344, 0.693147, 0.693147, 0.693147}
В первом случае возвращается только окончательный результат, а в других — еще и все промежуточные. Функция FixedPoint позволяет осуществлять итерации
до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:
newtonfp[f_, х0_] := FixedPoint[ (# — f [#]/f'[#]) &, N[xO]]
newtonfp[Function[{x} , Exp[x] — 2.0], 0.5]
0.693147
Более сложные примеры функционального программирования мы рассмотрим позже, при описании создания пакетов расширения систем Mathematica.
Пример программирования графической задачи
Графические задачи составляют значительную часть задач, решаемых с помощью Mathematica. С точки зрения программирования эти задачи не имеют особой специфики. Большая часть из них сводится к заданию функции, описывающей график, и применению одной из многочисленных графических функций системы с соответствующими опциями и директивами.
На рис. 10.1 показано задание функции GrayCode и ее графическое представление, полученное с помощью встроенной функции ListPlot.
В качестве следующего примера рассмотрим задачу на построение сложного графика функции Мандельброта. Пример задания соответствующей функции MandelbrotFunction и применения графической функции DensityPlot для наглядного визуального представления функции MandelbrotFunction на комплексной плоскости представлен на рис. 10.2.
Еще более сложную и любопытную задачу демонстрирует рис. 10.3. Здесь задана функция JuliaFunction, которая представляет одну из моделей деления клеток. На этом же рисунке показано построение множества графиков, дающих прекрасное визуальное представление данной функции.
Разумеется, приведенные примеры далеко не исчерпывают всего многообразия графических возможностей языка программирования систем Mathematica.
Использование процедур
 
В основе процедурного программирования лежит понятие процедуры и типовых средств управления — циклов, условных и безусловных выражений и т. д. Процедурный подход — самый распространенный в программировании, и разработчики Mathematica были вынуждены обеспечить его полную поддержку. Однако программирование систем Mathematica и в этом случае остается функциональным, поскольку элементы процедурного программирования существуют в конечном счете в виде функций.
Процедуры являются полностью самостоятельными программными модулями, которые задаются своими именами и отождествляются с выполнением некоторой последовательности операций. Они могут быть заданы в одной строке с использованием в качестве разделителя символа «;» (точка с запятой). Вот пример задания однострочной процедуры, отождествленной с именем г:
r = (1 + х)^2; r= Expand[г]; r — 1
2Х+Х2
Обратите внимание на то, что в теле процедуры символ г используется как вспомогательная переменная. Эта процедура возвращает символьное выражение
Expand[ (1+х)^2] — 1.
В общем случае в теле процедуры могут находиться произвольные выражения, разумеется, с синтаксисом, присущим языку программирования системы. Процедура может не возвращать никаких значений, а просто выполнять определенный комплекс операций. Область записи подобных элементарных процедур ограничена ячейкой (строкой) ввода.
Для задания процедуры со списком локальных переменных {а, b,…} и телом ргос может использоваться функция Module [ {а, b,…} ,ргос]. С применением этой функции мы столкнемся позже.
Для создания полноценных процедур и функций, которые могут располагаться в любом числе строк, может использоваться базовая структура — блок:

  • Block [{x, у,…}, procedure] — задание процедуры с декларацией списка локальных переменных х, у,…;
  • Block[{x = х0, у=у0,…}, procedure] — задание процедуры с декларацией списка переменных х, у,… с заданными начальными значениями.

Пример использования базовой структуры:
g[x_] := Block[{u}, u = (1 + х)^2; u = Expand[u] ] g[а + b]
l+2a+a2+2b+2ab+b2
u
u
u = 123456; g[2]
9
u
123456

Обратите внимание: последние действия показывают, что переменная и, введенная в тело базовой структуры, является действительно локальной переменной, и присвоение ей символьного выражения (1 + х) ^ 2 в теле блока игнорируется вне этого блока. Если переменная и до применения в функции была не определена, то она так и остается неопределенной. А если она имела до этого некоторое значение (в нашем случае — 123 456), то и по выходе из процедуры она будет иметь это значение.

Статьи по теме

Комментарии запрещены.