tower_of_hanoi_4pegs.cpp

#include <iostream>
#include <vector>
using namespace std;

size_t cunt;

void TowerOfHanoi3(size_t n, size_t src, size_t aux, size_t dest, vector<string> &towers) {
    if (n==0) { return; }
    TowerOfHanoi3(n-1, src, dest, aux,towers);
    ++::cunt; cout << towers[src] << " -> " << towers[dest] << endl;
    TowerOfHanoi3(n-1,aux,src,dest,towers); }

void TowerOfHanoi4(size_t n, size_t src, size_t aux1, size_t aux2, size_t dest, vector<string> &towers) {
    if (n==0) { return; }
    size_t k=n-round(sqrt(2*n+1))+1;
    TowerOfHanoi4(k,src,aux2,dest,aux1,towers);
    TowerOfHanoi3(n-k,src,aux2,dest,towers);
    TowerOfHanoi4(k,aux1,aux2,src,dest,towers); }

int main() {
    size_t n; cin>>n; vector<string> towers{"T1","T2","T3","T4"}; ::cunt=0;
    TowerOfHanoi4(n,0,1,2,3,towers);
    // cout << "Number of Steps: " << ::cunt << endl;
    return 0; }