Skip to content

Instantly share code, notes, and snippets.

@kobake
Created December 9, 2013 10:35
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kobake/7870267 to your computer and use it in GitHub Desktop.
Save kobake/7870267 to your computer and use it in GitHub Desktop.
Ackermann Function
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <stdarg.h>
#include <vector>
bool g_verbose = false;
// 再帰呼び出し使わない版
int Ack(int m_input, int n_input)
{
// バッファ確保
std::vector<int> vtable(1000000); // 100万個 = 4MB
int ntable = (int)vtable.size();
int* table = &vtable[0];
int* table_end = &table[ntable]; // バッファ終端
// 初期値入れる
table[0] = m_input;
table[1] = n_input;
// 終端位置
int* end = &table[2];
// ひたすら計算
while(1){
// 要素数が1以下になっていたら計算終了
int size = end - table;
if(size <= 1)break;
// 途中経過表示
if(g_verbose){
for(int i = 0; i < size - 2; i++){
printf("Ack(%d, ", table[i]);
}
printf("Ack(%d, %d)", *(end - 2), *(end - 1));
for(int i = 0; i < size - 2; i++){
printf(")");
}
printf("\n");
}
// 一番後ろの2つに注目
int m = *(end - 2);
int n = *(end - 1);
if(m == 0){
// 要素が1個減る
*(end - 2) = n + 1; // まとめる
// 終端を変更
end--;
}
else if(n == 0){
// 要素数は変わらない
*(end - 2) = m - 1;
*(end - 1) = 1;
}
else{
// 要素が1個増える
*(end - 2) = m - 1;
*(end - 1) = m;
*(end - 0) = n - 1; // 増えた分
// 終端を変更
end++;
if(end >= table_end){
printf("ERROR: Table overflow\n");
exit(1);
}
}
}
// 計算結果
if(g_verbose){
printf("%d\n", table[0]);
}
return table[0];
}
int main()
{
int ack = 0;
printf("---- Calc Ack(2, 1) ----\n");
g_verbose = true;
ack = Ack(2, 1);
printf("--\n");
printf("Ack(2, 1) = %d\n", ack);
printf("\n");
printf("---- Calc Ack(4, 1) ----\n");
g_verbose = false;
ack = Ack(4, 1);
printf("--\n");
printf("Ack(4, 1) = %d\n", ack);
printf("\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment