РЕКУРРЕНТНОСТЬ И РЕКУРСИЯ

Читайте также:

Прямая и косвенная рекурсия

Рекуррентные объекты, соотношения, функции. Среда - Рекуррентность (объекты, модели). Средства реализации - рекурсия (процедуры, функции). Рекурсия - определение некоторого объекта через себя. Таковыми могут быть числовые функции (n!), комбинаторные объекты (дерево, путь), геометрические объекты (кривая Пеано), определения в программировании (ЦБЗ, идентификатор, арифметическое выражение) и пр. В каждом случае требуется конкретизация определения. Так, например, рекурсивное определение функции - способ ее задания, когда искомое значение определяется через значение этой функции в некотором наборе предшествующих точек (при соответствующем определении предшествования), в динамическом программировании рекурсивно определяется траектория.
Выражение объекта (в частности функции) через подобные является рекуррентным соотношением. Очень удобно записывать рекуррентное соотношение используя рекурсивную функцию или процедуру (т.е. функцию или процедуру, тело которой содержит обращение к ней же (прямо или косвенно)).
Рекурсия часто используется при доказательстве (метод мат. индукции) и в расчетах (причем часто доказательство по индукции соответствует конструктивному алгоритму расчета).
Рекурсия практикуется не только в математике, но там нередко счи- тается дурным тоном ("масло масляное"). В конструктивной математике, логике в программировании рекурсия - естественный способ определения, например,
<целое без знака>::=<цифра>|<цифра><целое без знака>
В программировании и алгоритмизации особую роль играет рекуррентно определяемый линейный список:
<линейный список>::=<пусто>|<звено>|<звено>,<линейный список>
Таким образом, эффективно определяются весьма полезные в моделировании линии на графах, различной породы деревья и прочие универсальные средства моделирования.
В некоторых случаях равнозначны и эквивалентны по наглядности рекурсивное и не рекурсивное (итеративное) определения, скажем,

n! = n * (n-1)! n! = 1 * 2 *... * n

в других представляется более естественным (числа Фибоначчи) или менее привычным (конечное кардинальное число). В любом случае, рекурсивное определение важно как средство построения бесконечного множества объектов на основе конечного множества исходных (общность алгоритмов).
Будучи средством моделирования рекурсия применяется и в описании алгоритмов и программ, представляя собой синхронный встроенный интерпретатор структуры моделируемого объекта. Поскольку все программирование условно складывается в виде двух разделов - структур данных и операций, в таком же виде рекурсия проникает и в языки программирования (записи или составные данные как структуры и рекурсивные функции или процедуры как операции). Существуют языки программирования, полностью построенные на рекурсии (LISP). Рекурсивные вычисления лучше использовать, когда в постановке задачи рекурсия присутствует в явном виде.
В общем виде рекурсивную программу P или функцию можно представить в виде некоторой композиции T множества операторов S не содержащих P и самой P. P = T (S,P)

Если некоторая процедура содержит явную ссылку на себя, говорят о явной рекурсии, через другие - косвенную. Появление рекурсивных процедур стало возможным при динамическом распределении памяти. Вызов рекурсивной процедуры требует выделения памяти под локально определяемые в этой процедуре объекты, таким образом формируется стек где хранятся данные, участвующие во всех вызовах процедуры, при которых на не завершила работу. Стек разбит на фрагменты, представляющие собой блоки последовательных ячеек. Каждый вызов процедуры использует фрагмент стека, длина которого зависит от вызываемой процедуры, из этих областей памяти доступна только последняя. Выход из рекурсивной процедуры означает освобождение последней элемента стека с полной утратой локальной информации. Кроме локальных переменных в этом стеке также хранится информация о "точке выхода" - команде процедуры, который будет передано управление.
Некоторые полезные выводы.
1) Рекурсивная функция или процедура соответствует организации транслятором языка программирования стека обращений и локальных данных процедур. От рекурсивной процедуры можно избавиться, организовав этот стек "вручную" (не забывая "точку выхода", если в теле процедуры имеется несколько обращений к ней) но это не всегда оправдано по затратам памяти и времени и, почти всегда, по сложности устройства программы. Совсем плохо дело в случае косвенной рекурсии, когда записи стека различные в зависимости от очередного обращения.
2) Чтобы "стек" экономно расходовал память, не следует вводить в теле рекурсивной процедуры много локальных переменных, всегда не желательно определять массивы. Во избежание непредсказуемых последствий в теле рекурсивной процедуры не следует определять глобальные переменные но следует внимательно следить за зонами действия идентификаторов.
3) Рекурсивная процедура может порождать неограниченные вычисления, поэтому при ее проектировании следует провести теоретические расчеты возможной глубины рекурсии (и требуемой памяти) а при отладке программы позаботиться об идентификации уровня рекурсии, например, используя глобальную переменную Level=0, увеличивая ее значение на единицу при входе в подпрограмму или функцию и уменьшая на единицу при выходе. Чаще всего такой параметр имеется в модели программируемого процесса. Другой вывод - желательно, чтобы рекурсивная процедура имела единственный выход, например, структуру:

P = If (b) Then P P(n) = If (n>0) Then P(n-1) P = T(S,If (b) Then P) P(n) = T(S,If (n>0) Then P(n-1))

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

A(m, n) = A(m-1, A(m, n-1)) A(m, 0) = A(m-1, 1); A(0, n) = n + 1

Рекомендации по устранению (не применению рекурсии)
1. Случай единственного обращения к процедуре

------ нет ------ ------нет P: ¦ b ¦-------- P': ¦ S ¦---¦ b ¦--- -------да ------- -------да ---v-- ------ ---v-- ¦ S ¦---¦ P ¦ ¦ P' ¦ ------- ------- ------- WHILE (b) { S, P } S; WHILE (b) { P',S }

2. Случай многократной активизации одного и того же обращения.

1 n n Fn = ----- ((1+#5)/2) - (1-#5)/2)) 2 #5 F[n+2] = F[n] + F[n+1] F0=0; F1=1; WHILE (N>0) INT F (INT N) { F=F0+F1; F0=F1; F1=F0; N--;} { IF (N<2) RETURN 1 В этом примере проделано следующее ELSE RETURN F(n-1)+F(n-2); } 1) Изменен порядок расчетов (от 1 к N) 2) Организован круг перестановки значений --------------- --------------------- ---------------- ¦ F1 = f2 = 1 ¦------->¦ Fn-1 + Fn-2 --> Fn ¦--->¦ Fn-1 --> Fn-2 ¦ ---------------- --------+------------- ----------+------ чередование переменных "по кругу" ^ -------------- ¦ - часто используемый прием программир. --------¦ Fn --> Fn-1 ¦<----- --------------- В общем виде рекуррентные числовые последовательности записываются ввиде: Xn = f (n, Xn-1,..., Xn-k) X0 = a0,..., Xk-1 = Ak-1Вычисление элементов таких последовательностей требует вращения k+1 значения.Иногда в вычислении удобно Xn выразить через Xn-m. Более общий вариант - однородные линейные рекеуррентные соотношения спостоянными коэффициентами может быть аналитически решена в общем виде: Xn = A1 Xn-1 + A2 Xn-2 +.... + Ak Xn-k n k k-1 n-k Xn= C*r ==> C (r - A1 r -... - Ak) r = 0 Далее решается уравнение и подбираются требуемые коэффициенты. Если для вычисления функции требуется конечное (ограниченное) количестводругих значений, эти найденные значения функции следует хранить(это не проходит, увы в случае функции Аккермана - там требуемое количествозначений не поддается простой оценке) Свойства рекурсивных объектов в программировании: 1. Обычно существует хотя бы один выход из р.с. в описании: ---- ---- ------- ---- P(n): ¦ S ¦->¦ C ¦->¦P(n-1) ¦->¦ F ¦--> (n!) n - просчетов ----- --+-- -------- ----- -------------------> ---- ---- ------- ------- ---- P: ¦ S ¦->¦ C ¦->¦P(n-1)¦->¦P(n-2)¦->¦ F ¦--> (Fn) ----- --+-- -------- -------- ----- Fn - просчетов --------------------------> ---- ---- ------- ---- ---- P: ¦ S ¦->¦ Q ¦->¦P(n-1)¦->¦ C ¦->¦ F ¦--> Раскраска графа ----- --^-- -------- --v-- ----- ------------------ Чаще всего это связано с монотонным изменение м параметра. Хотя это не обязательно: (Г 2) (Пример - рекурсивная игра, Г = () она может длиться бесконечно) (-2 Г) Другой пример - магистраль в развитии системы (бесконечен без выбора) При решении таких задач используется другой аппарат. 2. При реализации алгоритма с рекурсией возникает стек параметров и локально определенных переменных. Не следует создавать лишние. 3. Проблема использовать или нет рекурсивную процедуру решается в каждом случае индивидуально. Косвенную рекурсию лучше реализовать рек.процедурой. Сложнее дело обстоит с вычислением рекуррентных массивов (массивов,элементы которых связаны некоторыми рекуррентными соотношениями). С[i,j] = C[i-1,j-1] + C[i-1,j] y[i,j] = y[i-1,j] - y[i-1,j-1] C[i,0]=C[i,i]=1 - треугольник Паскаля y[0,j]=f(Xj) - конечные разности 1 j=0, 1, 2, 3 исходные знач. исхо- \¦. i=0.... i=0 дные 1 ¦ \ иско- | / | / | / \¦.->. i=1 мые... i=1 зна- 1 ¦ \ \ значе-| / | / чения \¦.->.->. i=2 ния.. i=2 1 ¦ \ \ \ | / \¦.->.->.->..... искомые. i=3 j=0, 1, 2, 3... Как правило, для вычисления одного или ряда значений двухмерногорекуррентного массива достаточно одномерного. Следует только внимательноотследить очередность расчета значений с применением диаграммы. Нередко задачи, связанные с рекуррентными массивами появляются приработе с полиномами (их производными), при аппроксимации функций. Пример. Полином Pn(x)= a0 * (x-a1) * (x-a2) *... * (x-an) (1) можнопредставить в виде Qn(x) = A0*x^n + A1*x^n-1 + An-1*x +... + An (2)не используя дополнительного массива памяти. Действительно, полагаяC[k,0:k] - коэффициенты полинома P{k}(x)= a0 * (x-a1) * (x-a2) *... * (x-ak) в форме (2)получим, что C[0,0] = a0; С[n,0:n] соответствует Qn, а алгоритмпересчета С[k,0:k] --> С[k+1,0:k+1] сводится к формуле С[k+1,j] = - С[k,j] * a[k+1] + C[k,j+1], где C[k+1,k+1] содержитa[k+1]. Таким образом, один такт пересчета представляет собой цикл --------------- ------------- k --> k+1: ¦b=a[j]; a[j]=0 ¦----¦ Цикл jek:1 ¦--------- ---------------- -------v------ ----------+------- ¦ a[j]-=a[j-1]*b ¦ ------------------- Более сложные примеры связаны с применением более громоздкихструктур данных. Пример - задача линейного раскроя. Z(Y) = MAX { Z(Y-Aj)+Cj | Aj <= Y } активные значен. -T---------------------T=============T----------------------------- 0 не требуются ¦Y-Amax Y-1¦ Y неизвестны L Задача плоского раскроя. Задача поиска кратчайшего расстояния. Задача с 0-1 переменными (простейший алгоритм Балаша), задача опокрытии и прочие задачи комбинаторного (переборного) характера. Алгоритм построения Гамильтонова контура. 1. Свойства Гамильтоновых линий (коневой обход, при каких m,nрешетка m*n имеет гамильтонов цикл). 1.1. Любой полный граф содержит Гамильтонов путь. 1.2. Если |Г(i)| + |Г(i)|>= m-1, то существует Гамильтонова цепь. 1.3. Если |Г(i)| + |Г(i)|>= m, то существует Гамильтонов путь. ------------- ----------------------- -------------- ¦ Gam(i,lev) ¦ -->¦ lev=0; New[V]=0 ¦->¦ Gam(i0,lev) ¦-> -------------- ¦ New[i0]=1; Rem[i0]=0 ¦ --------------- ------------------------ ------ нет ---------нет---------- -------------- ----------->¦Lev=m¦---->¦New[i]=1¦-->¦New[i]:=1¦->¦Цикл jeГ(-,i)¦->¦New[i]=0 ¦-> ---+---да ----+----- ----------- -------+------- ----------- ---v- нет V да -------v------ ¦i=i0¦--------->+--------> ¦ Gam(j,Lev+1)¦ ---T--да & ¦ rem[j]=i ¦ ----v---- ¦ --------------- ¦Use(Rem)¦-------- ---------- Алгоритм построения Эйлерова обхода. 1. Свойства Эйлерового обхода (Эйлеров обход, теорема Эйлера) 1.1. Связный граф имеет Эйлеров неориентированный замкнутый обход<===> степени всех вершин четны. 1.2. Связный граф имеет Эйлеров ориентированный замкнутый обход<===> полустепени захода и исхода всех вершин равны. 1.3. Связный граф имеет Эйлеров неориентированный незамкнутый обход<===> степени всех вершин кроме двух четны. ------------ --------- да ------- да ¦i=i0 ¦-----+------>¦ Г(i)=0 ¦------------->¦ St=0 ¦---> ¦St=0 St1=0¦ ^ -----+----нет ---+----нет ------------- ---+-- -------v--------- -----v----- ¦ i=j +<-¦jeГ(i); j -> St ¦ ¦ j -> St1 ¦ ---^--- ¦Г(i)-=j; Г(j)-=i¦ ¦ i <- St ¦ ¦ ------------------ -----+------ ------------<-----------------------

Семестр 2. Задачи лаборатороного задания 1 (рекуррентные соотношения).
1. Найти n-ю производную f(x) = exp(-x*x/2), построив для f(n)(x) рекуррентное соотношение.

2. Найти n-ю производную f(x) = exp(a*x*x+b*x+c), построив для f(n)(x) рекуррентное соотношение.
3. Подсчитать числа Бернулли Bk: B0 = 0, при k>0 B0 + C(1,k+1) B1 + C(2,k+1) B2 +... + C(k,k+1) Bk=0 Заполнить ими массив b[0:k].
4. Вычислить конечные разности в интерполяционной формуле Гаусса. Задан массив Y[-n:n] = C[0,-n:n], в нем же подсчитать C[0,0], C[1,1], C[1,2], C[2,3], C[2,4],..., C[n,2n-1], C[n,2n] если C[i,k] = C[i,k-1] - C[i-1,k-1]
5. Вычислить конечные разности в интерполяционной формуле Стирлинга. Задан массив Y[-n:n] = C[0,-n:n], в нем же подсчитать

C[0,0], (C[0,1]+C[1,1])/2, C[1,2], (C[1,2]+C[2,3])/2, C[2,4], (C[2,4]+C[1,5])/2,........................ (C[n-1,2n-1]+C[n,2n-1]), C[n,2n] если C[i,k] = C[i,k-1] - C[i-1,k-1]

6. Вычислить конечные разности в интерполяционной формуле Бесселя. Задан массив Y[-n:n] = C[0,-n:n], в нем же подсчитать

(C[0,1]+C[1,1])/2, C[1,1], (C[1,2]+C[2,2])/2, C[2,3], (C[3,4]+C[3,4])/2, C[3,5],........................ (C[n-1,2n-2]+C[2n,2n-1]), C[n-1,2n-1], если C[i,k] = C[i,k-1] - C[i-1,k-1] 7. Элементы треугольной матрицы удовлетворяют соотношению C[i,k] = C[i,k-2] + C[i,k-1] + C[i-1,k-1], (ie0:n, ke0:i) C[i,-1] = 0, C[i,0] = y[i] (ie0:n). Записать в массив y элементы нижней строки С 8. Элементы треугольной матрицы удовлетворяют соотношению C[i,k] = C[i,k-1] + C[i-1,k-1] + C[i-1,k-2], (ie0:n, ke0:i) C[i,-1] = 0, C[i,0] = y[i] (ie0:n). Записать в массив y элементы нижней строки С 9. Элементы прямоугольной матрицы С[0:m,0:n] удовлетворяют соотношению С[i,k] = C[i,k-1] + C[i-1,k-1] В массив Z[0:m+n] записаны элементы нулевого столбца и нулевой строки С[m,0], C[m-1,0],...C[0,0], C[0,1],...., C[0,n] Требуется там же получить строку m и столбец n. С[m,0], C[m,1],...C[m,n], C[m-1,n],...., C[0,n] 10. Полином, представленный в виде Pn(x) = d0 + d1*(x-z0) + d2*(x-z0)(x-z1) +... + dn*(x-z0)(x-z1)...((x-zn-1) Представить в виде Pn(x) = d0 + d1*x + d2*x*x +... + dn*x^n и обратно. 11. Вычислить значение полинома Pn(x) = d0 + d1*x + d2*x*x +... + dn*x^n с вещественными коэффициентами в комплексной точке x = c + id. 12. Полиномы Лежандра со старшим коэффициентом равным 1 определяются так: L0(x) = 1, L1(x) = x Lk(x) = x * Lk-1(x) - (k-1)**2/((2k-3)(2k-1)) * Lk-2(x) k>2 Вычислить Ln(x).

Семестр 2. Задачи лаборатороного задания 2

(Более сложные рекуррентные соотношения)

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

1. Составить программу решения линейной задачи раскроя. 2. Составить программу для решения плоской задачи раскроя. 3. Составить программу для поиска кратчайшего пути на графах 4. Используя рекурсивную процедуру решить задачу о ранце. 5. Используя рекурсивную процедуру решить задачу с 0-1 переменными. 6. Используя схему динамического программирования решить задачу поиска Sum { Aj * Xj * Xj | je1:n } ----> Max (Min) Sum { Xj | je1:n } = b Xj >= 0 7. Используя схему динамического программирования решить задачу поиска Sum { Fj (Xj) | je1:n } ----> Max (Min) Sum { Xj | je1:n } = b Xj >= 0 где Fj = функция определенного класса. 8. Используя схему динамического программирования решить задачу поиска П { Fj (Xj) | je1:n } ----> Max (Min) Sum { Xj | je1:n } = b Xj >= 0 где Fj = функция определенного класса. 9. Используя рекурсивную процедуру проанализировать решение головоло-мок вида пример на сложение РЕШИ + ЕСЛИ + СИЛЕН(SEND + MORE = MONEY) 10. Используя схему динамического программирования решить задачу о покрытии. 11. Используя рекурсивную процедуру проанализировать возможность обходашахматной доски размерности m*n ходом коня, начиная с заданного поля. 12. Построить Эйлеров обход связанного графа. 13. Построить Гамильтонов обход связанного графа. 14. Используя рекурсивную процедуру решить задачу о коммивояжере. 15. Задана очередность запуска деталей в задаче об m станках. Требуется

определить раннее время завершения выполнения всех работ.

15 Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков.

· Число — некоторая абстрактная сущность, мера для описания количества.

· Цифры — знаки, используемые для записи чисел.

Цифры бывают разные: самыми распространёнными являются арабские цифры, представляемые знаками от нуля (0) до девяти (9); менее распространены римские цифры, их можно встретить на циферблате часов или в обозначении века (XIX век).

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

· позиционные;

· непозиционные;

· смешанные.

Позиционные системы счисления подробно рассмотрены ниже, после краткого обзора смешанных и непозиционных систем.

Денежные знаки — это пример смешанной системы счисления.

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

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

При переводе удобно пользоваться таблицей степеней двойки:

Таблица 4. Степени числа 2

n (степень)

Пример. Число перевести в десятичную систему счисления.

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

При переводе удобно пользоваться таблицей степеней восьмерки:

Таблица 5. Степени числа 8

n (степень)

Пример. Число перевести в десятичную систему счисления.

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

При переводе удобно пользоваться таблицей степеней числа 16:

Таблица 6. Степени числа 16

n (степень)

Пример. Число перевести в десятичную систему счисления.

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

Пример. Число перевести в двоичную систему счисления.

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

Пример. Число перевести в восьмеричную систему счисления.

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

Пример. Число перевести в шестнадцатеричную систему счисления.

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

Пример. Число перевести в восьмеричную систему счисления.

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

Пример. Число перевести в шестнадцатеричную систему счисления.

Дата добавления: 2015-01-30; просмотров: 220 | Поможем написать вашу работу | Нарушение авторских прав

Предыдущая 1 2 3 4 5 6 7 8 9 101112 13 Следующая

lektsii.net - Лекции.Нет - 2014-2025 год. (0.015 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав