128 lines
3.8 KiB
C#
128 lines
3.8 KiB
C#
using System;
|
|
using System.Numerics;
|
|
using System.IO;
|
|
using System.Diagnostics;
|
|
|
|
namespace Ackermann_Function
|
|
{
|
|
class Program
|
|
{
|
|
static void Main(string[] args)
|
|
{
|
|
int _m = 0;
|
|
int _n = 0;
|
|
Console.Write("m = ");
|
|
try
|
|
{
|
|
_m = Convert.ToInt32(Console.ReadLine());
|
|
}
|
|
catch (Exception)
|
|
{
|
|
Console.WriteLine("Please enter a number.");
|
|
}
|
|
Console.Write("n = ");
|
|
try
|
|
{
|
|
_n = Convert.ToInt32(Console.ReadLine());
|
|
}
|
|
catch (Exception)
|
|
{
|
|
Console.WriteLine("Please enter a number.");
|
|
}
|
|
//for (long m = 0; m <= 10; ++m)
|
|
//{
|
|
// for (long n = 0; n <= 10; ++n)
|
|
// {
|
|
// DateTime now = DateTime.Now;
|
|
// Console.WriteLine("Ackermann({0}, {1}) = {2}", m, n, Ackermann(m, n));
|
|
// Console.WriteLine("Time taken:{0}", DateTime.Now - now);
|
|
// }
|
|
//}
|
|
|
|
DateTime now = DateTime.Now;
|
|
Console.WriteLine("Ackermann({0}, {1}) = {2}", _m, _n, Ackermann(_m, _n));
|
|
Console.WriteLine("Time taken:{0}", DateTime.Now - now);
|
|
File.WriteAllText("number.txt", Ackermann(_m, _n).ToString());
|
|
Process.Start("number.txt");
|
|
Console.ReadKey();
|
|
}
|
|
public class OverflowlessStack<T>
|
|
{
|
|
internal sealed class SinglyLinkedNode
|
|
{
|
|
private const int ArraySize = 2048;
|
|
T[] _array;
|
|
int _size;
|
|
public SinglyLinkedNode Next;
|
|
public SinglyLinkedNode()
|
|
{
|
|
_array = new T[ArraySize];
|
|
}
|
|
public bool IsEmpty { get { return _size == 0; } }
|
|
public SinglyLinkedNode Push(T item)
|
|
{
|
|
if (_size == ArraySize - 1)
|
|
{
|
|
SinglyLinkedNode n = new SinglyLinkedNode();
|
|
n.Next = this;
|
|
n.Push(item);
|
|
return n;
|
|
}
|
|
_array[_size++] = item;
|
|
return this;
|
|
}
|
|
public T Pop()
|
|
{
|
|
return _array[--_size];
|
|
}
|
|
}
|
|
private SinglyLinkedNode _head = new SinglyLinkedNode();
|
|
|
|
public T Pop()
|
|
{
|
|
T ret = _head.Pop();
|
|
if (_head.IsEmpty && _head.Next != null)
|
|
_head = _head.Next;
|
|
return ret;
|
|
}
|
|
public void Push(T item)
|
|
{
|
|
_head = _head.Push(item);
|
|
}
|
|
public bool IsEmpty
|
|
{
|
|
get { return _head.Next == null && _head.IsEmpty; }
|
|
}
|
|
}
|
|
public static BigInteger Ackermann(BigInteger m, BigInteger n)
|
|
{
|
|
var stack = new OverflowlessStack<BigInteger>();
|
|
stack.Push(m);
|
|
while (!stack.IsEmpty)
|
|
{
|
|
m = stack.Pop();
|
|
skipStack:
|
|
if (m == 0)
|
|
n = n + 1;
|
|
else if (m == 1)
|
|
n = n + 2;
|
|
else if (m == 2)
|
|
n = n * 2 + 3;
|
|
else if (n == 0)
|
|
{
|
|
--m;
|
|
n = 1;
|
|
goto skipStack;
|
|
}
|
|
else
|
|
{
|
|
stack.Push(m - 1);
|
|
--n;
|
|
goto skipStack;
|
|
}
|
|
}
|
|
return n;
|
|
}
|
|
}
|
|
}
|