Ackermann.hh

Go to the documentation of this file.

 
#ifndef __ACKERMANN_HH__
#define __ACKERMANN_HH__
 
#include "Stack.hh"
#include <climits>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
 
class Akm_t
{
private:
    std::string _name;
 
    static int Ackermann(int m, int n);
 
    static int AckermannLoop(int m, int n);
 
    static void AkmInit() { Akm_deep = deep_max = 0; }
 
    static int Akm_deep; 
    static int deep_max; 
 
public:
    Akm_t(std::string name = "name") : _name(name) {}
 
    ~Akm_t() = default;
 
    static void Akm_loop(int x, int y);
 
    static void Akm_rec(int x, int y);
};
 
// 静态数据成员需要在类外定义和初始化
int Akm_t::Akm_deep = 0;
int Akm_t::deep_max = 0;
 
void Akm_t::Akm_loop(int x, int y)
{
    AkmInit();
 
    clock_t t;
    int result;
 
    t = clock();
    result = AckermannLoop(x, y);
    t = clock() - t;
 
    printf("\nAckermannLoop(%i, %i) = %i\n", x, y, result);
    printf("AckermannLoop(%i, %i) took %ld clicks (%f seconds).\n", x, y, t, ((float)t) / CLOCKS_PER_SEC);
}
 
void Akm_t::Akm_rec(int x, int y)
{
    AkmInit();
 
    clock_t t;
    int result;
 
    t = clock(); // Returns the processor time consumed by the program.
    std::cout << "\nCurrent call:\n";
    result = Ackermann(x, y);
    std::cout << "Current deep: " << std::scientific << std::setw(10) << std::left << Akm_deep << " Max deep: " << std::setw(10) << deep_max;
    std::cout << "\nRecursion terminated.\n";
    t = clock() - t;
 
    printf("\nAckermann(%i, %i) = %i\n", x, y, result);
    printf("Ackermann(%i, %i) took %ld clicks (%f seconds).\n", x, y, t, ((float)t) / CLOCKS_PER_SEC);
}
 
int Akm_t::Ackermann(int m, int n)
{
    static time_t begTime = time(nullptr);
 
    if (++Akm_t::Akm_deep > Akm_t::deep_max)
    {
        ++Akm_t::deep_max;
        std::cout << "Max deep: " << std::setw(10) << std::left << std::setw(10) << Akm_t::deep_max << "Time(s): " << std::defaultfloat << difftime(time(nullptr), begTime) << '\r';
    }
    // std::cout << "Current deep: " << std::setw(10) << std::left << Akm_deep << " Max deep: " << std::setw(10) << deep_max << '\r';
    // printf("m = %-10.7g n = %-10.7g\r", (float)m, (float)n);
    // std::cout << "m = " << std::setw(10) << std::left << m << "n = " << std::setw(10) << std::left << n << '\r';
    if (!m)
    {
        --Akm_t::Akm_deep;
        return n + 1;
    }
    if (!n)
    {
        --Akm_t::Akm_deep;
        return Ackermann(m - 1, 1);
    }
 
    int midVal = Ackermann(m, n - 1);
 
    --Akm_t::Akm_deep;
    return Ackermann(m - 1, midVal);
}
 
int Akm_t::AckermannLoop(int m, int n)
{
    time_t begTime = time(nullptr);
 
    struct SnapShotStruct
    {
        int m;
        int n;
        int stage;
    };
 
    int retVal;
 
    Stack::seqStack<SnapShotStruct> SnapShotStack;
    SnapShotStruct currentSnapshot{m, n, 0};
    SnapShotStack.push(currentSnapshot);
 
    std::cout << "Current top:\n";
    while (!SnapShotStack.isEmpty())
    {
        currentSnapshot = SnapShotStack.top();
        SnapShotStack.pop();
        if ((Akm_t::Akm_deep = SnapShotStack.size()) > Akm_t::deep_max)
        {
            ++Akm_t::deep_max;
            // std::cout << "m = " << std::setw(10) << std::left << currentSnapshot.m << "n = " << std::setw(10) << currentSnapshot.n << " Current deep: " << std::setw(10) << Akm_deep << " Max deep: " << std::setw(10) << deep_max << '\r';
            std::cout << "Max deep: " << std::setw(10) << std::left << std::setw(10) << Akm_t::deep_max << "Stack size(kB): " << std::setw(10) << SnapShotStack.elemMem() / 1024 << "Time(s): " << difftime(time(nullptr), begTime) << '\r';
        }
        // printf("m = %-10.7g n = %-10.7g\r", (float)currentSnapshot.m, (float)currentSnapshot.n);
        switch (currentSnapshot.stage)
        {
        case 0:
        {
            if (!currentSnapshot.m)
            {
                retVal = currentSnapshot.n + 1;
                continue;
            }
 
            if (!currentSnapshot.n)
            {
                SnapShotStruct newSnapshot{currentSnapshot.m - 1, 1, 0};
                SnapShotStack.push(newSnapshot);
                continue;
            }
 
            currentSnapshot.stage = 1;
            SnapShotStack.push(currentSnapshot);
            SnapShotStruct newSnapshot{currentSnapshot.m, currentSnapshot.n - 1, 0};
            SnapShotStack.push(newSnapshot);
            continue;
        }
        break;
 
        case 1:
        {
            SnapShotStruct newSnapshot{currentSnapshot.m - 1, retVal, 0};
            SnapShotStack.push(newSnapshot);
            continue;
        }
        break;
        } // switch
    }     // while
 
    std::cout << "Current deep: " << std::scientific << std::setw(10) << std::left << std::setw(10) << Akm_t::Akm_deep << " Max deep: " << std::setw(10) << Akm_t::deep_max << "Stack size(kB): " << std::setw(10) << SnapShotStack.elemMem() / 1024;
    std::cout << "\nStack's cleared.\n";
    return retVal;
}
 
#endif