c # — Ackermann Termination: анализ первопричин

Вероятно, не нужно много объяснений того, что это такое, и это даже работает именно так, как я хочу. Моя настоящая проблема — завершение программы. Я вывел трассированные мои возвращаемые значения и вложенные циклы for, которые я использую в своей основной функции для пошагового перемещения значений. Я не вижу причин, чтобы это произошло, но программе требуется около 10 дополнительных минут после последнего прохождения через мои циклы, чтобы фактически завершиться. Хотя мои циклические индексы увеличиваются (из-за предварительной проверки), моя функция Аккермана, очевидно, не выполняет дополнительную итерацию (не то, чтобы я хотел этого в любом случае). С другой стороны, единственное логическое объяснение состоит в том, что цикл не прерывается, но если бы это было так, моя функция Акерманна должна вернуть новое значение b. Поэтому единственная другая причина, о которой я могу подумать, это то, что сборка мусора занимает слишком много времени, чтобы очистить мои структуры данных и очистить кучу памяти. Для тех, кто не знаком, идея состоит в том, чтобы реализовать то, что традиционно представляется как чрезвычайно громоздкую рекурсивную функцию, как итеративную функцию. Рекурсивный:

Даны натуральные числа m и n:
Если m = 0, вернуть n + 1; Иначе, если n = 0, вернуть Аккерманна (m — 1, 1); Еще вернем Аккермана (m — 1, Аккермана (m, n — 1)). Итеративно, идея состоит в том, чтобы использовать стек для эмуляции рекурсивных вызовов функций, чтобы вы могли использовать память из кучи и не зависеть от размера стека вызовов, что ограничивает время выполнения. Боюсь, что я пропускаю что-то в своем потоке, что вызывает эти длительные задержки между временем окончания вычислений и моментом, когда моя программа достигает точки, когда пользователь делает чистый выход.

Вот мой код:

 static void Main(string[] args)
{
ulong i, j;
i = j = 0;
for (i = 1; i <= 3; i++)
for (j = 1; j <= 15; j++)
Console.WriteLine("[{0}] Ackermann({1},{2}) = {3}", DateTime.Now, i, j, Ackermann(i, j));
Console.WriteLine("Press any key to continue...");
Console.ReadKey();
}

static ulong Ackermann(ulong a, ulong b)
{
Stack<ulong> ackStack = new Stack<ulong>();

ackStack.Push(a);
while (ackStack.Count > 0)
{
a = ackStack.Pop();
if (a == 0)
b++;
else if (b == 0)
{
ackStack.Push(--a);
b = 1;
}
else
{
ackStack.Push(--a);
ackStack.Push(++a);
b--;
}
}
return b;
}

Мысли? Заметьте, что это c #, но такое поведение также встречается в C ++, скомпилированном с MinGW.

-1

Решение

Большое спасибо Питеру Витвоэту! Оказывается, что порядок оценки в моем Writeline был всем, что было неправильно. Только после изменения стало ясно, сколько времени это добавляет к общему времени выполнения всего этого!

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector