адача 49. Написать рекурсивную программу-функцию нахождения наименьшего десятичного натурального числа N>1, оканчивающегося цифрой q такого, что если перенести эту цифру из конца в начало N, то полученное число окажется в q раз больше N.

Решение. При q=1 решение задачи очевидно: N=11. Простым перебором последовательных натуральных чисел можно было бы подобрать число N и для q=4: N=102564. Но для других значений q подобный перебор уже практически неосуществим. Например, при q=6 искомое число содержит 58 цифр (результат получен с помощью приведенной ниже функции transfer(q)):

 N=1016949152542372881355932203389830508474576271186440677966.

 Для упрощения дальнейших рассуждений будем считать, что q=6. Пусть число N содержит n цифр и . Условие задачи можно переписать так:

Отсюда видно, как получаются отдельные последовательные цифры искомого числа N, начиная от младшей цифры и далее:

Формируемые цифры числа будем запоминать в виде последовательных компонентов вектора. Нужно понять, когда необходимо заканчивать вычисления в описанном процессе. Получающуюся на очередном этапе цифру обозначим через x, а число, переносимое в следующий разряд, - через p. Поскольку 6×x₀ = 6, то x₀ = 1. Отсюда на последнем этапе вычислений должно выполняться условие 6×x + p = 1 (x = x₁).

Учитывая сказанное, для решения исходной задачи можно предложить функции trans() и transfer(q). Дадим им краткое описание.

Функция transfer(q) передает рекурсивной функции trans(q,ot,p,x) значение параметра q задачи и начальные значения вспомогательных параметров: вектора решения (ot=id×q), цифры переноса в следующий разряд (p=0), цифры искомого числа, сформированной на данном этапе (x=q).

Рекурсивная функция trans(q,ot,p,x) реализует вычисления в точности по описанной выше схеме. Декомпозиция задачи непосредственно определяется самой схемой, а базой рекурсии является получение условий x=1 (для очередной цифры числа) и p=0 (для цифры переноса):

Контрольный пример. В приведенной ниже однострочной матрице m для компактности записи компоненты выписаны без разделителей.

 m = transfer(5)^T, m = (102040816326530612244897959183673469387755) .

Замечание. Частичную проверку правильности полученного по функциям trans(q,ot,p,x) и transfer(q) решения N можно осуществлять непосредственным умножением N на q и сравнением результата с числом, получаемым из N перенесением его последней цифры в начало. Однако, ввиду громоздкости подобных операций, лучше это делать с помощью вспомогательной функции prov(q). При вычислениях prov(q) обращается к рекурсивной функции multiq(v,q,p), осуществляющей умножение десятичного натурального числа, цифры которого представлены компонентами вектора v, на однозначное число q. Параметр p является вспомогательным и служит для запоминания цифр переноса в следующий разряд при выполнении умножения. Рекурсия осуществляется по длине вектора v. Базой рекурсии являются векторы единичной длины. Декомпозиция реализуется последовательными уменьшениями длины исходного вектора на единицу:

Контрольный пример: prov(9)=”yes”.