Задачи на обращение функций являются достаточно распространенными. Иногда возникает вопрос об обращении функций, заданных посредством алгоритмов. Пусть, например, относительно параметра xÎX
решается уравнение вида f(x)=a при некотором известном рекурсивном алгоритме f и заданной величине aÎY, где X и Y - множества. Тогда знание обратной для f рекурсивной функции g(y) (yÎY) сразу же позволило бы решить исходное уравнение: f(x)=a, g(f(x))=g(a), x=g(a). Поэтому умение “обратить” алгоритм является хотя и непростым, но достаточно полезным и эффективным подспорьем в решении задач рекурсивными методами. Реальное использование данной опорной схемы проводится так. Алгоритм (программа) решения исходной задачи A нам неизвестен или не устраивает по причине сложности, громоздки или плохой эффективности. Однако для какой-либо из обратных для A задач удается построить алгоритм R её решения. В некоторых случаях простые рассуждения, приводящие к незначительным косметическим изменениям R, позволяют получить конкретный алгоритм для A. Но по сути этих рассуждений и изменений вряд ли можно дать какие-либо общие рекомендации, ибо они жестко связаны с содержанием рассматриваемой задачи, выбором для неё обратной задачи и алгоритма R её решения. Многое здесь зависит от того, какую из обратных для A задач мы выбрали. Рассмотрим пример.A. Пусть у возвратной последовательности (
an) (n = 0, 1, …), определяемой соотношениемa
n = t0 × an-3 + t1 × an-2 + t2 × an-1 (n = 3, 4, …), (4)известны коэффициенты
t0, t1, t2 и три конкретных последовательных члена am=a, am+1=b , am+2=g (m³0). Требуется определить три начальных члена (4), то есть элементы a0, a1, a2.В каком-то смысле обратную для
A задачу нахождения общего члена an (n=0, 1, …) возвратной последовательности (4) по известным коэффициентам t0, t1, t2 и начальным членам a0, a1, a2 ранее мы уже решали. Более точно обращение A формулируется так.B. Пусть у возвратной последовательности (
an) (n=0, 1, …), определяемой соотношением (4) известны коэффициенты t0, t1, t2; начальные члены a0=a , a1=b , a2=g и зафиксировано целое неотрицательное число m. Требуется определить три последовательных члена (4), то есть элементы am, am+1, am+2.Будем считать, что коэффициенты
t0, t1, t2 и последовательные члены от m-го и далее заданы соответственно векторами: t = (t0 t1 t2)T и v = (a b g )T. Тогда, как нетрудно видеть, решением задачи B может служить следующая рекурсивная функция:
(5)
где v × t - скалярное произведение векторов
v и t. Контрольный пример. Ниже в таблице 5 приведено нескольких начальных членов конкретной возвратной последовательности:Таблица 5.
|
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
… |
|
a(n) |
1 |
3 |
1 |
6 |
5 |
16 |
20 |
47 |
71 |
145 |
… |
Для неё
v = (1 3 1)T и t = (-1 2 1)T . Вычислим с помощью функции rev(m, v, t) при m=7 три последовательных члена a(n):v := (1 3 1)T, t := (-1 2 1)T, m := 7, rev(m, v, t)T = [47 71 145].
Теперь опираясь на (5) попытаемся построить программу-функцию решения исходной задачи. Перепишем (4) в виде
a
n-3 = (1 / t0) × (-t1 × an-2 - t2 × an-1 + an)Если в этом соотношении величины
an-2, an-1 и an считать известными, то фактически оно предоставляет нам возможность последовательно вычислять значения an-3, an-4, … a0, и, тем самым, найти вектор (a0 a1 a2)T. Для этих целей можно использовать незначительную модификацию рекурсивной программы-функции (5), где необходимо сделать следующие изменения. Вместо вектора коэффициентов t = (t0 t1 t2)T в соответствии с (3) взять вектор t = (1 / t0) × [-t1 -t2 1]T, а при декомпозиции учитывать, что последовательно вычисляются члены с уменьшающимся (а не с увеличивающимся) значением индекса. Это позволяет для решения задачи A предложить рекурсивную функцию a(m, v, t ) вида:
v := [47 71 145]T, m := 7, t := (-1 2 1)T,
t := (1 / t0) × [-t1 -t2 1]T, a(m, v, t )T = [1 3 1].
