Задачки на рекурсию.

[ИС]

ИСН
А тогда в моем предыдущем посте можно заменить первою процедуру на вторую и будет таже фигня ))))))))) XD
Maslov
Пасиб ) помогло )

[ИСН]

ИС в сообщении #255662 писал(а):

А тогда в моем предыдущем посте можно заменить первою процедуру на вторую и будет таже фигня )))))

Догадываюсь. Я бы тогда ещё что-нибудь ехидное сказал.

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

e2e4 в сообщении #255525 писал(а):

Не всегда сведение рекурсивного алгоритма к итерационному - простой процесс.

Ага

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

[venco]

ИСН в сообщении #255672 писал(а):

Попробуйте запрограммировать вычисление функции Аккермана без рекурсивного вызова функции.

int ackermann(int m, int n)
{
    vector<int> s;
    for ( ;; ) {
        if ( m == 0 ) {
            n = n+1;
            if ( s.empty() ) return n;
            m = s.back(); s.pop_back();
        }
        else if ( n == 0 ) {
            m = m-1;
            n = n+1;
        }
        else {
            s.push_back(m-1);
            n = n-1;
        }
    }
}

У меня лишь на треть медленнее, чем рекурсия.

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

venco в сообщении #258298 писал(а):

int ackermann(int m, int n)
{
    vector<int> s;
    for ( ;; ) {
        if ( m == 0 ) {
            n = n+1;
            if ( s.empty() ) return n;
            m = s.back(); s.pop_back();
        }
        else if ( n == 0 ) {
            m = m-1;
            n = n+1;
        }
        else {
            s.push_back(m-1);
            n = n-1;
        }
    }
}

Простите, я C не понимаю Не могли бы Вы то же самое сделать на Паскале, если Вам не трудно.

-- Ср ноя 04, 2009 21:02:23 --

Да, и вот что с ходу кажется странным: функция вроде от трёх аргументов, а у Вас их всего два. Хотя, может, это моё недопонимание, связанное с незнанием синтаксиса языка C.

[Maslov]

venco в сообщении #258298 писал(а):

У меня лишь на треть медленнее, чем рекурсия.

Формально это, конечно, не рукурсия, но фактически - все-таки немного рекурсия . Просто Вы стек вызовов вручную строите.

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

Maslov в сообщении #258307 писал(а):

Формально это, конечно, не рукурсия, но фактически - все-таки немного рекурсия . Просто Вы стек вызовов вручную строите.

Не, такое, конечно, не годится. Эмулировать стек нельзя. Давайте уж и goto запретим для полноты картины

Кстати, теоретический факт: запрограммировать вычисление функции Аккермана, используя только циклы for, невозможно

[venco]

Maslov в сообщении #258307 писал(а):

venco в сообщении #258298 писал(а):

У меня лишь на треть медленнее, чем рекурсия.

Формально это, конечно, не рукурсия, но фактически - все-таки немного рекурсия . Просто Вы стек вызовов вручную строите.

А что, кто-то обещал большего?

-- Ср ноя 04, 2009 11:05:15 --

Профессор Снэйп в сообщении #258302 писал(а):

Да, и вот что с ходу кажется странным: функция вроде от трёх аргументов, а у Вас их всего два. Хотя, может, это моё недопонимание, связанное с незнанием синтаксиса языка C.

Я взял стандартное определение: Функция Аккермана

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

Давайте более чётко поставим условие: написать вычисление функции Аккермана на классическом виртовском Паскале. В духе структурного программирования, без использования goto. Процедуры использовать можно, но рекурсия (в явном или неявном виде) не разрешается.

Считаем, что объём памяти не ограничен. Количество шагов вычисления тоже ничем не ограничивается (лишь бы оно было конечным). Переменная типа integer может принимать любые целые значения.

venco в сообщении #258328 писал(а):

А что, кто-то обещал большего?

Ну, чисто теоретически это возможно. Более того, у меня несколько лет назад один студент нечто подобное сделал (до сих пор восхищаюсь его подвигом). Он, конечно, ничего не программировал, а показал напрямую, что функция является частично рекурсивной (без применения тезиса Чёрча). В принципе, это задачи одного плана.

Речи об эффективности вообще не идёт. Вычисления могут быть значительно менее эффективными, чем с использованием рекурсии. Интересует лишь сама возхможность запрограммировать вычисления функции Аккермана без рекурсивного вызова.

-- Ср ноя 04, 2009 22:15:24 --

venco в сообщении #258328 писал(а):

Я взял стандартное определение: Функция Аккермана

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

Я специально дал ссылку на определение функции Аккермана, которое надо использовать в задаче. Это определение из книги Роджерса "Теория рекурсивных функций и эффективная вычислимость". Вроде бы это определение из оригинальной работы самого Аккермана, хотя в последнем не уверен.

[venco]

Профессор Снэйп в сообщении #258330 писал(а):

Процедуры использовать можно, но рекурсия (в явном или неявном виде) не разрешается

Условие нечёткое, т.к. любую итерацию можно обозвать неявной рекурсией.

-- Ср ноя 04, 2009 11:40:48 --

Профессор Снэйп в сообщении #258330 писал(а):

venco в сообщении #258328 писал(а):

Я взял стандартное определение: Функция Аккермана

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

Я специально дал ссылку на определение функции Аккермана, которое надо использовать в задаче.

Это детали. Можно таким же образом и для произвольного $y$ запрограммировать.

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

venco в сообщении #258338 писал(а):

Профессор Снэйп в сообщении #258330 писал(а):

Процедуры использовать можно, но рекурсия (в явном или неявном виде) не разрешается

Условие нечёткое, т.к. любую итерацию можно обозвать неявной рекурсией.

Да нет, чёткое. Итерации, конечно, рекурсией не считаются. Под "неявной рекурсией" я понимал вот что: функция $f$ вызывает функцию $g$, а функция $g$ --- функцию $f$. Ну и тому подобные варианты. Возможно, в программировании есть какой-то специальный термин для обозначения подобной ситуации; он мне незнаком.

venco в сообщении #258338 писал(а):

Это детали.

Согласен. Их надо сразу обговорить во избежание дальнейших недоразумений. Я предлагаю взять определение функции Аккермана, изначально мною преложенное (всё-таки это ведь я задачу предложил ). Но если Вам оно очень сильно не нравится, давайте пользоваться Вашим, из Википедии. Только сразу объявляйте, каким из определений Вы пользуетесь.

[venco]

Профессор Снэйп в сообщении #258347 писал(а):

Итерации, конечно, рекурсией не считаются. Под "неявной рекурсией" я понимал вот что: функция $f$ вызывает функцию $g$, а функция $g$ --- функцию $f$. Ну и тому подобные варианты. Возможно, в программировании есть какой-то специальный термин для обозначения подобной ситуации; он мне незнаком.

Это называется "косвенная рекурсия", по английски - indirect.
С таким определением моё решение - вполне нерекурсивное.

[Maslov]

Профессор Снэйп в сообщении #258330 писал(а):

Более того, у меня несколько лет назад один студент нечто подобное сделал (до сих пор восхищаюсь его подвигом). Он, конечно, ничего не программировал, а показал напрямую, что функция является частично рекурсивной (без применения тезиса Чёрча). В принципе, это задачи одного плана.

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

[Xaositect]

Maslov в сообщении #258361 писал(а):

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

Примитивная рекурсия - это цикл for.
Оператор $\mu$ - это цикл while.

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

venco в сообщении #258353 писал(а):

С таким определением моё решение - вполне нерекурсивное.

Если я правильно понял, Вы организуете стек в виде списка...

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

Хорошо, сделаем так. Запрещается использовать динамическую память. То есть в программе должно быть изначально объявлено конечное число переменных "статического типа", под каждую из которых отведена одна-единственная ячейка памяти (способная хранить произвольное целое число). И программа по ходу работы может пользоваться только этой памятью...

Если хотите, порешайте эту задачу. Но... вообще-то хрен редьки не слаще. Внутрь безразмерной ячейки памяти можно загнать счётное число таких же безразмерных ячеек, используя теорему об единственности разложения натуральных чисел в произведение простых множителей. Или используя приём с функцией Гёделя, основанный на китайской теореме об остатках. А далее одну из ячеек можно выделить под тот же самый стек...

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

-- Чт ноя 05, 2009 00:06:17 --

Xaositect в сообщении #258363 писал(а):

Примитивная рекурсия - это цикл for.
Оператор $\mu$ - это цикл while.

Ага Причём есть такой интересной факт: любая вычислимая функция может быть представлена в виде $f(x) = l(\mu t(g(x,t)=0))$, где $l$ и $g$ --- примитивно рекурсивные функции. То есть любую вычислимую функцию можно запрограммировать так, что будет использоваться только один цикл while и какое-то конечное число циклов for (и не будет использоваться goto).

Maslov в сообщении #258361 писал(а):

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

Ну... это фольклор Возможно, где-то в каком-то учебнике это и прописано, но я его не читал.

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