Рекурсия

Контрольные примеры.
![]()
![]()
![]()
Задача Иосифа Флавия
С именем известного историка первого века Иосифа Флавия связывают следующую задачу-легенду. В ходе иудейской войны он в составе отряда из 41 воина был загнан римлянами в пещеру. Не желая сдаваться, осажденные воины решили покончить жизнь самоубийством и разработали для этого следующую процедуру. Они выстроились в круг и, начиная отсчет с конкретной позиции, каждый третий должен был убивать себя, пока не останется ни одного человека. Математически одаренный Иосиф считал подобный конец бессмысленным и потому поставил себя и своего друга на такие позиции, что после серии из 39 самоубийств они остались вдвоем, чем и спасли себе жизнь. Что это были за позиции?
Дадим этой задаче-легенде более точную и обобщенную формулировку, освободившись от суицида. При этом будем искать рекурсивные решения двух ниже приведенных задач, различающихся завершением соответствующей процедуры. Подробнее рекурсия как метод решения практических задач обсуждается в следующем параграфе.
Задача 1. По окружности в направлении движения часовой стрелки расположены n последовательных натуральных чисел от 1 до n. При перемещении по числам 1, 2, ... каждое k-ое число (k>1) вычеркивается (удаляется). Этот процесс продолжается до тех пор, пока чисел не станет меньше k. Определить оставшиеся числа.
Задача 2. По окружности в направлении движения часовой стрелки расположены n последовательных натуральных чисел от 1 до n. При перемещении по числам 1, 2, ... каждое k-ое число (k>1) вычеркивается (удаляется). Этот процесс продолжается до тех пор, пока не останется одно число. Определить его.
A. Решение первой задачи Флавия при k=2.
Ниже рассмотрены три варианта A1-A3 решения задачи 1 при k=2, опирающиеся на разные идеи.
A1. Если n=2Чs, то после первого прохода по кругу останутся числа: 1, 3, ... 2Чs-1 и следующий проход начнется с вычеркивания числа 3. Это все равно, как если бы мы начинали с s последовательных натуральных чисел от 1 до s, но каждое уцелевшее число удваивали и результат уменьшали на 1. Отсюда, если fla1(n) - функция, решающая поставленную задачу, то fla1(1)=1 и
fla1(2Чs)=2Чfla1(s) - 1 (sі1). (16)
Аналогичные рассуждения показывают, что
fla1(2Чs+1)=2Чfla1(s) + 1 (sі1). (17)
Величины fla1(n) назовем числами Флавия. Соотношения (16) и (17) сразу же позволяют написать следующую рекурсивную программу-функцию вычисления значений fla1(n).

A2. Исследование рекуррентных соотношений (16)-(17) показывает, что
fla1(2s + q)=2Чq+1 (sі0, 0Јq<2Чs) (18)
Отсюда получаем еще один рекурсивный алгоритм для вычисления чисел Флавия (см. ниже). При этом вспомогательная рекурсивная функция power(n,0) вычисляет значение s, удовлетворяющее соотношению (18), то есть уменьшенное на 1 количество цифр двоичного разложения n, а функция fla2(n) непосредственно вычисляет число Флавия для заданного n.

![]()
A3. Еще один способ нахождения чисел Флавия дается программой-функцией flavec(v), где v=(1 2 3 ... n)T - вектор. Подавать такой вектор в качестве аргумента необязательно. Проще обращаться к flavec(v) c помощью функции fla3(n), где по заданному n генерируется соответствующий вектор v. Отметим, что в flavec(v) используется рекурсивный алгоритм непосредственного вычеркивания каждого второго числа. При этом вектор v перестраивается при каждом новом перемещении по кругу.


Контрольные примеры.
1. fla1(6)=5fla2(6)=5fla3(6)=5
2. fla1(11)=7 fla2(11)=7 fla3(11)=7
3. fla1(1000)=997fla2(1000)=997fla3(1000)=997
B. Решение первой задачи Флавия в общем случае.
Ниже рассмотрены два варианта B1-B2 решения задачи 1 в общем случае. Первый из них представляет прямое обобщение алгоритма из пункта A3 и реализует рекурсию по каждому вычеркнутому элементу. Во втором варианте рекурсия организована по отдельным проходам по окружности.
B1. Способ A3 решения задачи 1 при k=2 хоть и несколько громоздкий, но он достаточно просто переносится на общий случай. При этом естественно считать k аргументом функции. Тогда решение задачи дает рекурсивная программа-функция flave(v,k), где v=(1 2 3 ... n)T - вектор. Однако проще использовать для этих целей функцию fla4(n,k), формирующую по заданному целому n требуемый вектор v, а затем уже обращающуюся k flave(v,k).

B2. Приведенный ниже способ решения первой задачи Флавия отличается от предыдущего лишь способом организации рекурсии. Здесь она реализована не по каждому вычеркнутому элементу, а по отдельным проходам по окружности. Решение задачи дается программой-функцией flavmek(v,k), где v=(1 2 3 ... n)T - вектор. Однако проще использовать для этих целей функцию fla5(n,k), формирующую по заданному целому n требуемый вектор v, а затем уже обращающуюся к flavmek(v,k). Обратите внимание на используемый в fla5(n,k) метод формирования вектора v.

Контрольные примеры.
1. fla4(6,2)=5 fla5(6)=5
2. fla4(41,3)T =[16 31] fla5(11) T =[16 31]
3. fla4(1000,5)T=[563 763 802 73] fla5(1000) T=[563 763 802 73]
С. Решение второй задачи Флавия в общем случае.
Пусть функция flav(v,k), где v=(1 2 ... n)T решает поставленную задачу и пусть w - вектор, полученный из v вычеркиванием одного k-го компонента. После каждой такой операции будем организовывать рекурсивный вызов flav(w,k), прекращая вычисления тогда, когда длина вектора станет равной единице. Пусть le - длина вектора v и s=mod(k,le). Нетрудно видеть, что после одного вычеркивания получим:
w=(1 2 ... le-1)T при s=0 ,
w=(2 3 ... le)T при s=1 ,
w=(s+1,s+2,...,le,1,2,...,s-1) при s>=2 .
Поэтому функцию flav(v,k) и обращающуюся к ней функцию fla6(n,k) можно определить следующим образом:


Контрольные примеры.
fla6(10,5)=3 fla6(5,10)=4 fla6(1000,7)=404 .
13.4 Системы счисления
A. Перевод чисел из десятичной системы в p-ичную систему
Не ограничивая общности речь можно вести о неотрицательных числах.Пусть pО{2,3,…} и цифры p-ичной системы - это последовательные десятичные числа: 0, 1, ... p-1. Рассмотрим 6 конкретных задач. В трех первых из них речь идет о переводе естественным образом заданных десятичных чисел в p-ичную систему счисления. В следующих трех задачах речь идет о переводе десятичных чисел, цифры которых заданы в виде последовательных компонентов векторов, в p-ичную систему счисления. Во всех случаях результат формируется в виде вектора, компоненты которого p-ичные цифры исходного числа.
Задача 1. Составить программу-функцию перевода целых неотрицательных десятичных чисел m в систему счисления по основанию p.
Решение. Функция dec_p_i(m,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного деления. Результат формируется в виде вектора, компоненты которого p-ичные цифры m.

Контрольные примеры.
![]()
.
Замечания.
1. Если разряды p-ичного числа необходимо формировать не от старшего разряда, а от младшего и далее, то в программе dec_p_i() первый и второй аргументы функции stack() необходимо поменять местами.
2. При переводе неотрицательных десятичных чисел в конкретную систему счисления, в функции dec_p_i() достаточно иметь один аргумент. Например, перевод в двоичную систему можно осуществлять следующей программой-функцией dec_b_i(m).

Контрольные примеры.
![]()
Как мы уже отмечали при реализации функций dec_p_i(m,p) и dec_b_i(m) использован рекурсивный вариант алгоритма последовательного деления - выделения цифр p-ичной системы для целых чисел. Пояснений требуют лишь фрагменты вида identity(1)Чx. Дело в том, что функция stack() в качестве своих аргументов использует векторы или матрицы. И смысл записи identity(1)Чx состоит в превращении скаляра х в матрицу размера 1ґ1 с элементом x.
Задача 2. Составить программу-функцию перевода правильной неотрицательной десятичной дроби y в систему счисления по основанию p.
Решение. Функция dec_p_f(y,p,k) решает поставленную задачу, используя рекурсивный алгоритм последовательного умножения. Результат формируется в виде вектора с не более чем k (k=1,2,…) компонентами, которые суть p-ичные цифры числа y, начиная от старших разрядов и далее.

Контрольные примеры.
![]()
Задача 3. Составить программу-функцию перевода неотрицательного действительного десятичного числа a в систему счисления по основанию p (p=2, 3, …).
Решение. Функция dec_p(a,p,k) решает поставленную задачу, осуществляя перевод десятичного числа a в p-ичную систему счисления. Результат вычислений формируется в виде составного вектора. Компоненты этого вектора снова векторы, содержащие соответственно цифры целой и дробной частей числа a в p-ичной системе счисления. Цифры целой и дробной части a возвращаются, начиная со старших разрядов и далее. В дробной части присутствует не более чем k (k=1,2,...) цифр. При вычислениях функция dec_p() обращается к двум рекурсивным функциям dec_p_i() и dec_p_f().
![]()
Контрольные примеры.


Задача 4. Пусть m=(v0v1…vn-1)10 - целое десятичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)T . Составить программу-функцию перевода m в систему счисления по основанию p.
Решение. Функция dec_p_iv(v,p) осуществляет перевод v в p-ичную систему счисления. Результат вычислений формируется, начиная от старших разрядов и далее, в виде вектора, компоненты которого суть p-ичные цифры исходного числа. Функция dec_p_iv(v,p) отличается от ранее рассмотренной функции dec_p_i(v,p) лишь формой представления первого аргумента. Поэтому её вычисление можно свести к вычислению dec_p_i(v,p) с предварительным обращением к рекурсивной функции dv_norm(v), переводящей десятичное число из векторного представления в нормальную форму. Это и сделано ниже.

![]()
Контрольные примеры.
![]()
![]()
Задача 5. Пусть y=(.v0v1…vn-1)10 - правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)T. Составить программу-функцию перевода y в систему счисления по основанию p.
Решение. Функция dec_p_fv(v,p,k) осуществляет перевод v в p-ичную систему счисления. Результат вычислений формируется, начиная от старших разрядов и далее, в виде вектора длины не более k, компоненты которого суть p-ичные цифры исходного числа. Функция dec_p_fv(v,p,k) отличается от ранее рассмотренной функции dec_p_f(v,p,k) лишь формой представления первого аргумента. Поэтому её вычисление можно свести к вычислению dec_p_f(v,p,k) с предварительным обращением к рекурсивной функции dv_normf(v), переводящей десятичную дробь из векторного представления в нормальную форму. Это и сделано ниже.

![]()
Контрольные примеры.
![]()
![]()
Задача 6. Пусть действительное неотрицательное десятичное число a представлено двумя векторами in и fr, компоненты которых последовательные десятичные цифры, начиная от старшей и далее, соответственно целой и дробной части а. Составить программу-функцию перевода a в систему счисления по основанию p.
Решение. Функция dec_pv(in,fr,p,k) решает поставленную задачу, осуществляя перевод десятичного числа a в p-ичную систему счисления. Результат вычислений формируется в виде составного вектора. Компоненты этого вектора снова векторы, содержащие соответственно цифры целой и дробной частей числа a в p-ичной системе счисления. Цифры целой и дробной части a возвращаются, начиная со старших разрядов и далее. В дробной части присутствует не более чем k (k=1,2,...) цифр. При вычислениях функция dec_p() обращается к двум рекурсивным функциям dec_p_iv() и dec_p_fv().
![]()
Контрольные примеры.


B. Перевод чисел из p-ичной системы в десятичную систему
Пусть pО{2,3,…} и цифрами p-ичной системы являются десятичные числа 0,1,... ,p-1. Будем считать, что рассматриваются неотрицательные p-ичные числа, а их цифры от старшего разряда и далее задаются последовательными компонентами векторов. Рассмотрим 3 конкретные задачи.
Задача 7. Пусть m=(v0v1…vn-1)p - целое p-ичное неотрицательное число, цифры которого от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)T . Составить программу-функцию перевода m в десятичную систему счисления.
Решение. Функция p_dec_i(v,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного деления. Результат формируется в естественной форме.

Контрольные примеры.
![]()
![]()
Задача 8. Пусть y=(.v0v1…vn-1)p - правильная неотрицательная десятичная дробь, цифры которой от старшей и далее заданы последовательными компонентами вектора v=(v0, v1, …,vn-1)T . Составить программу-функцию перевода y в десятичную систему счисления.
Решение. Функция p_dec_f(v,p) решает поставленную задачу, используя рекурсивный алгоритм последовательного умножения. Результат формируется в естественной форме.

Контрольные примеры.
![]()
![]()
Задача 9. Пусть действительное неотрицательное p-ичное число а представлено двумя векторами in и fr, компоненты которых последовательные p-ичные цифры, начиная от старшей и далее, соответственно целой и дробной части а. Составить программу-функцию перевода a в десятичную систему счисления.
Решение. Функция p_dec(in,fr,p) решает поставленную задачу, осуществляя перевод p-ичного числа a в десятичную систему счисления. Результат вычислений формируется в естественной форме. При вычислениях функция p_dec() обращается к двум рекурсивным функциям p_dec_i() и p_dec_f().
![]()
Контрольные примеры.
![]()
![]()
Замечание. Перевод чисел из p-ичной системы счисления в q-ичную систему (p,qО{2,3,…}) можно осуществлять через промежуточную десятичную систему.
13.5 Генераторы перестановок
Ранее в разделе 12.9 мы описали один из алгоритмов получения n! перестановок из элементов множества S={a0, a1, …, an-1}, где ak (k=0..n-1) - попарно различные действительные числа. Считая, что S={1,2,…,n}, обсудим еще несколько вариантов рекурсивных алгоритмов генерирования перестановок. Отличаются друг от друга они разными характеристиками: быстродействием, компактностью записи, количеством транспозиций при получении очередной перестановки и т.д.
A.Метод вертикальной прогонки. При S={1} имеем одну перестановку - 1. Если уже имеется последовательность перестановок из n-1 элемента {1,2,…,n-1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод вертикальной прогонки” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n-1}. В первом экземпляре в конец каждой перестановки поместим элемент n. Во втором экземпляре этот элемент поместим на предпоследнем месте и т.д. Наконец, в последнем экземпляре поместим n перед первым элементом. На рисунке 13.4 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n-1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они будут различаться друг от друга позициями элементов {1,2,…,n-1} и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то позиции элемента n в них будут разными и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.

Рис. 13.6. Генерирование перестановок методом вертикальной прогонки.
Описанный алгоритм вертикальной прогонки реализуется рекурсивной программой-функцией permut1(n):

Контрольный пример

B.Метод последовательного замещения. При S={1} имеем одну перестановку - 1. Если уже имеется последовательность перестановок из n-1 элемента {1,2,…,n-1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод последовательного замещения” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n-1}. В первом экземпляре, как и в методе вертикальной прогонки, в конец каждой перестановки поместим элемент n. В каждой перестановке второго экземпляра поменяем местами элементы n и 1. В каждой перестановке третьего экземпляра поменяем местами элементы n и 2 и т.д. Наконец, в последнем экземпляре поменяем местами элементы n и n-1. На рисунке 13.5 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n-1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они обязательно будут различаться друг от друга расположением элементов на позициях от 1 до n-1 и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то на последних позициях у них стоят разные элементы и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.

Рис. 13.5. Генерирование перестановок методом последовательного
замещения
Описанный алгоритм последовательного замещения реализуется рекурсивной программой-функцией permut2(n):

С. Перестановки в антилексикографическом порядке. На множестве P всех перестановок <x0,x1,…,xn-1> из элементов {1,2,…,n} определим два типа порядка.
Лексикографический порядок на P вводится следующим образом. Для
"(<a0,a1,…,an-1>,<b0,b1,…,bn-1>ОP) (19)
положим
<a0,a1,…,an-1> <’ <b0,b1,…,bn-1> Ы
$(k і 0) [(ak Ј bk) & "(s < k) [(as = bs)]], (20)
где символ <’ использован в качестве знака лексикографического сравнения перестановок.
Заметим, что если вместо чисел 1,2,…,n использовать буквы с естественным порядком следования их в алфавите, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре. И это справедливо для алфавитов любых языков.
Аналогично вводится и антилексикографический порядок на P. Для (19) положим
<a0,a1,…,an-1> <” <b0,b1,…,bn-1> Ы
$(k Ј n-1) [(ak > bk) & "(s > k) [(as = bs)]], (21)
где символ <” использован в качестве знака антилексикографического сравнения перестановок.
Построим рекурсивную программу-функцию, генерирующую перестановки элементов {1,2,…n} в антилексикографическом порядке. Соответствующий алгоритм может базироваться на следующих двух утверждениях, непосредственно вытекающих из определения 21.
Утверждение 1. Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно <1,2,…,n> и <n,n-1,…,1>.
Утверждение 2. Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}{q} в антилексикографическом порядке.
Головная функция permut3(n) решает поставленную задачу. В ней по значению n для рекурсивной программы-функции permu(p) формируется начальная перестановка p. В permu(p) и проводятся все вычисления. На рис. 13.6 представлен результат выполнения permut3(n) при n=3 и n=4. Для n=4 полученные перестановки расположены по столбцам.



Рис. 13.6. Генерирование перестановок в антилексикографическом порядке
D. Перестановки в лексикографическом порядке. В предыдущем разделе мы ввели понятие лексикографического порядка. Алгоритм генерирования перестановок в таком порядке и соответствующие программы-функции могут быть построены на идеях, близких к тем, которые использовались при генерировании перестановок в антилексикографическом порядке. Поэтому здесь мы ограничимся лишь приведением соответствующих функций permut(p) и permut4(n) и представим полученный по ним результат вычислений для n=3 и n=4 (см. рис. 13.7). Для n=4 полученные перестановки расположены по столбцам.



Рис. 13.7. Генерирование перестановок в лексикографическом порядке
E. Перестановки c одной транспозицией соседних элементов. В этом пункте рассматривается алгоритм генерирования последовательности перестановок U из элементов множества {1,2,…,n} такой, что любая перестановка U, кроме начальной, получается из предыдущей перестановки одной транспозицией соседних элементов. Проиллюстрируем на примере идею соответствующего алгоритма, приписываемого Джонсону [] и Троттеру []. Предположим, что для элементов {1,2,…,n-1} уже построена требуемая последовательность перестановок U. Тогда из элементов {1,2,…,n} необходимая последовательность может быть построена перемещениями элемента n между начальной и конечной позициями каждой перестановки U. При этом перемещения должны производиться попеременно вперед и назад (n-1)! раз так, как это показано на рис. 13.8.
Рекурсивная программа-функция permut5(n) реализует этот, схематично описанный, алгоритм. На рис. 13.8 приведены полученные по permut5(n) перестановки для n=3 и n=4.


Рис. 13.8. Генерирование перестановок c транспозицией соседних элементов
В заключение автор выражает признательность профессорам. Ваграменко Я.А. и Добровольскому Н.М. за консультации и советы при написании пособия.
Литература
Кнут Д. Искусство программирования для ЭBM. Основные алгоритмы: т. 1, M.: Мир, 1976.
Кнут Д. Искусство программирования для ЭBM. Получисленные алгоритмы: т. 2, М.: Мир, 1977.
Кнут Д. Искусство программирования для ЭBM. Сортировка и поиск: т. 3, М.: Мир, 1978.
Лекции лауреатов премии Тьюринга. М.: Мир, 1985.
Бауэр Ф.Л., Гнац Р., Хилл У. Информатика. Задачи и решения. М.: Мир, 1978 г.
Бауэр Ф.Л., Гооз Г. Информатика. T. 1, М.: Мир, 1990 г.
Бауэр Ф.Л., Гооз Г. Информатика. T. 2, М.: Мир, 1990 г.
Ландау Э. Основы анализа. М.: изд. Иностранной литературы, 1947.
9. www-cs-staff.stanford.edu/~knuth/taocp.html#vol4-{volume4}).