рекурсивные функции

[nell]

Алгоритм вычисления произведения делителей числа n в виде рекурсивной функции.

[Бодигрим]

Открою тайну, известную лишь избранным: в русском языке есть такая категория, как сказуемое. Говорят, помогает высказываться яснее.

[nell]

Разработать алгоритм..........Извините, думала интуитивно понятно

[Бодигрим]

Хм, давайте начнем с формул. Чему, по-вашему, равно произведение делителей числа $n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}$?

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

Судя по названию темы, эти формулы лишь усложнят дело.

Вам что нужно: доказать рекурсивность функции, значение которой на произвольном натуральном числе равно произведению делителей этого числа?

Если нет, то разъясните подробно, что требуется. А если да, то тогда Вам несколько встречных вопросов. Что Вы знаете о рекурсивных функциях? Имеете ли право ссылаться на тезис Чёрча или Вам нужно доказывать рекурсивность по определению? Нужна ли примитивная рекурсивность или просто рекурсивности за глаза хватит?

[nell]

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

Последним вопросом в задании идет :определить к какому классу рек. ф-ий принадлежит f(n) (примитивно-рек, частично-рек. или общерекурсивна).

О тезисе Чёрча в лекциях не было ни слова, доказывали по определению.

[Руст]

Вроде очевидно, что это произведение равно $n^{m(n)}$, где $m(n)$ половина числа делителей $m(n)=\frac 12 (k_1+1)...(k_l+1),n=\prod_i p_i^{k_i}$.

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

nell писал(а):

разработать алгоритм ее вычисления.

p := 1;
for i := 1 to n do
  if n mod i = 0 then p := p*i;

Устроит?

Далее... Что Вы знаете про примитивно рекурсивные функции? Умеете ли пользоваться ограниченной минимизацией? Знаете ли, чем общерекурсивная функция отличается от рекурсивной?

[nell]

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

PS Если бы все это доходило до моего сознания, а не оставалось набором слов, я к вам бы не обращалась. Так что сильно не ругайте

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

nell писал(а):

Примитивно рекурсивная функция- такая арифм. ф-ия, которая может быть получена из простейших с помощью конечного числа применений операторов суперпозиции и прим. рекурсии, всюду определена.

Всюду определённость не входит в определение примитивно рекурсивной функции. Это свойство (которое, кстати, очень легко доказывать).

nell писал(а):

Рассмотрели эти самые простейшие ф-ии, операторы, доказывали,что сложение, арифм. вычитание, умножение, возведение в степень, знак, антизнак - примитивно рекурсивны.

Прекрасно! А теперь поехали.

Заметим, что если у нас уже есть какие-то функции, про которые мы точно знаем, что они примитивно рекурсивны, то функции, полученные из них суперпозицией или примитивной рекурсией, также примитивно рекурсивны. Действительно, раз какие-то получаются из простейших, а другие уже из них, то в конечном счёте всё получается из простейших. Энто как бы совсем очевидно. Далее...

1) Функция $g(n,i) =$ остаток от деления $n$ на $i+1$ примитивно рекурсивна. Действительно, она задаётся по схеме примитивной рекурсии

$$ g(0,i) = 0; $$

$$ g(n+1,i) = (g(n,i)+1) \cdot \mathrm{sg}(i \frac{.}{\phantom{x}} g(n,i)) $$

из функций, получаемых через базисные функции, а также функции арифметической разности, умножения и знака при помощи оператора суперпозиции.

2) Функция

$$ h(n,i) = \begin{cases} 1,&n \text{ не делится на }i+1;\\ i+1,&\text{иначе} \end{cases} $$

примитивно рекурсивна. Действительно, $h(n,i) = i \cdot \overline{\mathrm{sg}}(g(n,i)) + 1$.

3) Функция

$$ w(n,i) = \prod_{j=0}^{i} h(n,j) $$

примитивно рекурсивна. Действительно, она задаётся схемой примитивной рекурсии

$$ w(n,0) = 1; $$

$$ w(n,i+1) = w(n,i) \cdot h(n,i+1). $$

4) Остаётся лишь заметить, что интересующая нас функция равна $w(n,n)$ и, следовато, является примитивно рекурсивной (если мы, конечно, согласимся считать, что произведение делителей нуля равно единице).

Разбирайтесь!