Рекурсия (стр. 10 из 12)
равна 1?
Решение. Хотя данная строка и начата со слова “решение”, ответа на поставленный вопрос мы не знаем и, по-видимому, на сегодняшний день его не знает никто. Более того, неизвестно, для любого ли nproblem(n) вычисляется за конечное число шагов. Рассмотренную задачу называют 3×n+1 проблемой. Мы включили её в список задач для того, чтобы обратить внимание читателя на следующий факт. Достаточно простые с виду рекурсивные определения функций могут таить в себе глубокие проблемы, решения которых лежат совсем не на поверхности. Тем не менее, конкретные вычисления problem(n) при разных n приводят к одному и тому же значению, равному 1. Ниже приведена рекурсивная программа для проверки истинности утверждения “problem(n)=1” при значениях n из диапазона k1..k2.
Контрольные примеры.
6. Задача Иосифа Флавия
С именем известного историка первого века Иосифа Флавия связывают следующую задачу-легенду. В ходе иудейской войны он в составе отряда из 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, а затем уже обращающуюся kflave(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)=3fla6(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.