1 Тема від Betterthanyou Востаннє редагувалося Betterthanyou (18.10.2014 21:12:47)

  • Звідки: Київ
  • Дата реєстрації: 16.05.2014
  • Повідомлень: 1 695
    • Репутація: 1022

Тема: Функція Акермана

Можливо зробити функцію Акермана не рекурсивно, а циклічно ? Складність з якою я зіткнувся полягає в тому що не можливо написати цикл тобто
A(0, n) = n + 1;
A(m, 0) = A(m–1, 1); при m > 0;//Потрібно безліч циклів в циклі
A(m, n) = A(m–1, A(m, n–1)); при m > 0 и n > 0.//Потрібно безліч циклів в циклі
Моя невдала спроба

int main()
{
    int m, n;
    cout << "Vvedit m ->";//3
    cin >> m;
    cout << "Vvedit n ->";//5
    cin >> n;
    while (1)
    {
        if (m == 0)
            n += 1;
        else
            if (n = 0 && m > 0)
            {
                m = -1, n = 1;
                if (m == 0)
                    n += 1;
                else
                    if (m > 0 && n > 0)
                    {
                    if (m == 0)
                        n += 1;
                    else
                        if (n = 0 && m > 0)
                        {
                        m = -1, n = 1;
                        if (m == 0)
                            n += 1;
                        else
                            if (m > 0 && n > 0)
                                m -= 1, n -= 1;
                        }
                    m -= 1, n -= 1;
                    }
            }
            else
                if (m > 0 && n > 0)
                {
            if (m == 0)
                n += 1;
            else
                if (n = 0 && m > 0)
                {
                m = -1, n = 1;
                if (m == 0)
                    n += 1;
                else
                    if (m > 0 && n > 0)
                        m -= 1, n -= 1;
                }
                    m -= 1, n-= 1;
                }
                else
                    break;
    }
    cout << m << " , " << n;
    getch();
    return 0;
}

А це рекурсивно (працююча)

int rec(int m, int n)
{
    if (m == 0)
        return n + 1;
    if (n == 0)
        return rec(m - 1, 1);
    return rec(m - 1, rec(m, n - 1));
}

int main()
{
    int m, n;
    cout << "Vvedit m ->";//3
    cin >> m;
    cout << "Vvedit n ->";//5
    cin >> n;
    cout << "Vivod = " << rec(m, n);
    getch();
    return 0;
}

Betterthanyou вебсайт

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13333

Re: Функція Акермана

Вам не в C++, а в алгоритми.
Будь-яку рекурсивну функцію можна перетворити на цикл зі стеком, і ваша - не виняток.
Ну і на Вікі є формули для цієї функції. Так, з гіпероператором на 4-му рядку (і далі).

Подякували: Arete, Betterthanyou2

koala вебсайт

3 Відповідь від Arete

  • Arete
  • Arete
  • Replace Team
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 19.07.2014
  • Повідомлень: 390
    • Репутація: 421

Re: Функція Акермана

Я теж подумав про стек, але написати сам алгоритм в мене поки що не виходить, мабуть треба з ним переспати..

Подякували: Betterthanyou1

4 Відповідь від Singularity

  • Дата реєстрації: 29.07.2013
  • Повідомлень: 673
    • Репутація: 166

Re: Функція Акермана

Напиши фукнцію яка генерить число Грехема і передай результат роботи функції в функцію Акермана.

5 Відповідь від Betterthanyou

  • Звідки: Київ
  • Дата реєстрації: 16.05.2014
  • Повідомлень: 1 695
    • Репутація: 1022

Re: Функція Акермана

Я знайшов сайт де є 5 методів для обчислення Акермана http://home.versatel.nl/vspickelen/Larg … kerman.htm але не можу вибрати самого простого метода мені всі якісь не зрозумілі наприклад цей

FUNCTION A (m, n)
DIM s(tsize + 1)

   s(0) = m
   s(1) = n: t = 1
   DO
      c = c + 1
      IF s(t - 1) = 0 THEN '  m = 0
         t = t - 1
         s(t) = s(t + 1) + 1
      ELSEIF s(t) = 0 THEN '  n = 0
         s(t) = 1
         s(t - 1) = s(t - 1) - 1
      ELSE
         s(t + 1) = s(t) - 1
         s(t) = s(t - 1)
         s(t - 1) = s(t - 1) - 1
         t = t + 1
      END IF
      IF t > d THEN
         d = t
         IF d > tsize THEN
            PRINT "failure": END
         END IF
      END IF
    LOOP UNTIL t = 0

A = s(0)
END FUNCTION

не зрозуміло що означає ось це DIM s(tsize + 1),s(0),s(1),THEN ',PRINT "failure":,LOOP UNTIL t = 0,ELSEIF
На рахунок стеку то я не зрозумів як його можна застосувати

Betterthanyou вебсайт

6 Відповідь від Ярослав Востаннє редагувалося Ярослав (22.10.2014 20:23:10)

  • Ярослав
  • Гість

Re: Функція Акермана

Наведений код написаний на Basic.
Оператор DIM "оголошує та розміщує в пам’яті місце для однієї або декількох змінних" http://msdn.microsoft.com/ru-ru/library/7ee5a7s1.aspx
Рядок DIM s(tsize + 1), скоріш за все, виділяє пам’ять для масиву s, що має кількість елементів tsize й ще один,.
s(0), s(1) - це, скоріш за все, звернення до конкретних елементів масиву.
THEN - оператор, який буде виконувати дію, якщо те що зазначене в попередньому операторі IF або ELSEIF.
PRINT "failure" - виводить рядок failure.
LOOP UNTIL t = 0 - умова, за якої буде виконуватись цикл (доки t не стане 0)
ELSEIF - оператор, який перевірить умову, що зазначена після нього, якщо умова зазначена в попередньому операторі IF або ELSEIF не справджується.

Про стек гарно написано в вікіпедії.