Частично рекурсивные функции - задача

[gron]

Господа, доброго времени суток.

Встала следующая задача: необходимо по заданному входному натуральному числу $N$ построить выходное натуральное число $f(N)$ , полученное удалением из десятичной записи числа $N$ всех фрагментов $123$.

Алогритм мне ясен: надо смотреть остатки от деления исходного числа на 1000, если он равен 123, то перескакиваем три разряда (делим число на 1000 нацело и дальше работаем с ним), если он не равен 123, то к числу-результату дописываем остаток от деления на 10 и переходим к следующему разряду (то есть делим исходное число нацело на 10 и далее работаем с ним).

Предикаты равенства, функции деления нацело и взятия остатка, вроде как, реализуемы (вроде как -- потому что пока этого еще не записал четко, но знаю, что это можно; меня интересует идея).

Мой вопрос в другом -- я, "не чувствуя" пока ЧРФ, не могу понять, за что зацепиться, как организовать этот самый цикл, в котором рекурсия ведется не по одной переменной, а сразу по трем (исходное число, число-результат и степень десятки, на которую надо домножать при "дописывании" к число-рузультату очередной цифры).

P.S. Задача нужна не мне, мне как раз надо попытаться объяснить её другому человеку, поэтому прошу наводок, а не решений.

Спасибо!

[Профессор Снэйп]

Чему равно $f(123)$? Нулю?

А $f(12300)$? Тоже нулю?

-- Сб фев 13, 2010 14:50:18 --

gron в сообщении #287556 писал(а):

как организовать этот самый цикл, в котором рекурсия ведется не по одной переменной, а сразу по трем (исходное число, число-результат и степень десятки, на которую надо домножать при "дописывании" к число-рузультату очередной цифры).

Стандартный приём. Называется "совместная рекурсия", сводится к примитивной кодированием троек натуральных чисел через одно число.

[gron]

Да, я тоже думал над этим, но в формулировке задачи этого, естественно, не указано. Я бы сделал функцию неопределенной на 123, и равной нулю на 12300, что логично при данной постановке задачи.

За вариант с совместной рекурсией спасибо, правда пока мало что понятно)

[Профессор Снэйп]

gron в сообщении #287587 писал(а):

За вариант с совместной рекурсией спасибо, правда пока мало что понятно)

Умножение и возведение в степень --- примитивно рекурсивные функции. Далее, $p(x) = x$-ое простое число --- также примитивно рекурсивная функция ($p(0)=2$, $p(1)=3$, $p(2)=5$ и т. д.). Далее,

$$ \mathrm{log}(x,y) = \begin{cases} 0, &y=0 \\ \max\{ i : p(x)^i \text{ делит } y \}, &y>0 \end{cases} $$

тоже примитивно рекурсивная функция. Из этих наблюдений легко доказывается

Теорема о совместной рекурсии Пусть $g_1(\bar{x}), \ldots, g_n(\bar{x}), h_1(z_1, \ldots, z_n,y,\bar{x}), \ldots, h_n(z_1, \ldots, z_n,y,\bar{x})$ --- (примитивно) рекурсивные функции и

$$ \begin{cases} f_1(0,\bar{x}) &= g_1(\bar{x}) \\ \ldots \\ f_n(0,\bar{x}) &= g_n(\bar{x}) \\ f_1(t+1, \bar{x}) &= h_1(f_1(t,\bar{x}), \ldots, f_n(t,\bar{x}),t,\bar{x}) \\ \ldots \\ f_n(t+1, \bar{x}) &= h_n(f_1(t,\bar{x}), \ldots, f_n(t,\bar{x}),t,\bar{x}) \end{cases} $$

Тогда функции $f_1, \ldots, f_n$ (примитивно) рекурсивны.

Насколько я понял Вашу идею, Вы хотели бы применить эту теорему для случая $n=3$.

P. S. А вообще-то тут совместная рекурсия не нужна. Достаточно обычной примитивной. Сначала строите функцию с номерами разрядов, которые надо учитывать, потом по ней легко задаёте нужную функцию.