算法3

递归算法示例

逆序一个正整数

https://github.com/terrellhu/algorithm/blob/master/20181029/reverse.cpp

void reverse(uint64_t n)
{
    cout << n%10;
    if (0 != n/10)
    {
        reverse(n/10);
    }
    return;
}

书上的代码示例有问题，只有输出，没有递归的部分，应该是印刷错误吧。。

汉诺塔

经典的汉诺塔问题，三个规则：

1. 每次只能移动一个圆盘
2. 圆盘可以加到塔座X，Y，Z中任意一个上
3. 任何时刻都不能将一个较大的圆盘放在较小的圆盘之上

最直观的想法，塔的数据结构类似栈，即使用3个栈将1个栈的元素按原顺序移动到另一个栈

• 汉诺塔递归算法理解
  1. 不要尝试理解整个递归的具体过程
  2. 简化过程为一个简单的递归过程

#include <iostream>
#include <stack>

using namespace std;

class CTower{
public:
    string name;
    stack<int> content;
};


void hanoi(int n, CTower& x, CTower& y, CTower& z)
{
    if (n)
    {
        hanoi(n-1, x, z, y);
        y.content.push(x.content.top());
        x.content.pop();
        cout << "move " << x.name <<"." << n << " to " << y.name << endl;
        hanoi(n-1,z,y,x);
    }
    return;
}

https://github.com/terrellhu/algorithm/blob/master/20181029/hanoi.cpp
以递归的思路来理解，即1~n个盘，要将最下面的n号盘移到y塔，则先要将1~n-1个盘都移到z塔，然后将第n个盘移到y塔后，再将1~n-1个盘移回到y塔，即完成！

产生各种可能的排列

• 给定n个自然数，{0, 1, ~n-1}的集合，设计一个算法输出该集合所有可能的排列。

#include <iostream>

using namespace std;

template < class T >
void perm(T a[], int k, int n)
{
    if (k == n-1)
    {
        for (int i =0; i < n; ++i)
            cout << a[i];
        cout << endl;
    }
    for (int i = k; i < n; ++i)
    {
        T t = a[i];a[i] = a[k];a[k] = t;
        perm(a, k+1, n);
        a[k] = a[i];a[i] = t;
    }
    return;
}

int main(int argc, char** argv)
{
    if (argc < 4)
    {
        cerr << "proc number1 number2 number3..." << endl;
        return 0;
    }

    uint64_t a[argc-1] = {0};
    for (int i = 1; i < argc; ++i)
    {
        a[i-1] = strtoul(argv[i], NULL, 0);
    }
    perm(a, 0, argc-1);
}

这里虽然把代码写出来了，但是感觉还是无法真正理解递归的思想，如果来一个新题目，不一定能做出来，留个坑，后面多找一些递归的算法题来练习一下。