[C++] 递归之全排列问题、半数集

一、递归的定义

　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个原问题相似的规模较小的问题来求解。

二、用递归求解问题的主要步骤

　　1、找出相似性

　　2、定义出口

三、递归实例

　　1、全排列问题

　　例如：

　　list[3] = {1,2,3}。

　　则全排列结果为：{1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,2,1}，{3,1,2}。

#include<iostream>
using namespace std;

void Perm(int list[], int k, int m);
void Swap(int &a, int &b);

void Perm(int list[], int k, int m)
{//产生list[k:m]的所有排列 
    if(k == m)
    {    //只剩下1个元素 
        for(int i = 0; i <= m; i++)
            cout<< list[i];
        cout<<endl;
    }
    else    //还有多个元素待排列，递归产生排列 
        for(int i = k; i <= m; i++)
        {
                Swap(list[k], list[i]);
                Perm(list, k+1, m);
                Swap(list[k], list[i]);
        }
}

void Swap(int &a, int &b)
{
    int temp = a; a = b; b = temp;
}

int main()
{
    int list[3] = {1,2,3};
    Perm(list, 0, 2);    
    return 0;
}

　　2、重复元素全排列

　　例如：

　　list[4] = {1,1,2,2}。

　　则重复元素全排列结果为：{1,1,2,2}，{1,2,1,2}，{1,2,2,1}，{2,1,1,2}，{2,1,2,1}，{2,2,1,1}。

#include<iostream>
using namespace std;

void Perm(int list[], int k, int m);
void Swap(int &a, int &b);
bool ok(int list[], int k, int i);

void Perm(int list[], int k, int m)
{//产生list[k:m]的所有排列 
    if(k == m)
    {    //只剩下1个元素 
        for(int i = 0; i <= m; i++)
            cout<< list[i];
        cout<<endl;
    }
    else    //还有多个元素待排列，递归产生排列 
        for(int i = k; i <= m; i++)
        {    //若不重复则执行 
            if(ok(list, k, i))
            {
                Swap(list[k], list[i]);
                Perm(list, k+1, m);
                Swap(list[k], list[i]);
            }
        }
}

void Swap(int &a, int &b)
{
    int temp = a; a = b; b = temp;
}

//判断元素[k..i-1]与i是否重复 
bool ok(int list[], int k, int i)
{
    if(i > k)
    {
        for(int t = k; t < i; t++)
        {
            if(list[t] == list[i])
                return false;
        }
    }
    else
        return true;
}

int main()
{
    int list[4] = {1,1,2,2};
    Perm(list, 0, 3);    
    return 0;
}

　　3、半数集

　　在自然数 n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半。

　　set(6) = {6,16,26,126,36,136}，半数集 set(n) 的元素个数。

#include<iostream>
using namespace std;

//递归算法 
int comp(int n)
{
    int ans = 1;
    if(n > 1)
    {
        for(int i = 1; i <= n/2; i++)
            ans += comp(i);
    }
    return ans;
}

/*
记忆式搜索方法
该方法用数组 a 来记录已经算过的半数集元素个数，
当输入的n在之前计算过时，则直接输出a[n]即可 
*/
int a[1001];
int comp2(int n)
{
    int ans = 1;
    if(a[n] > 0)
        return a[n];
        
    for(int i = 1; i <= n/2; i++)
        ans += comp2(i);
    a[n] = ans;
    return ans;
}

int main()
{
    int n;
    cin>> n;
    int ans = comp(n);
    cout<< ans <<endl;
    
    int ans2 = comp2(n);
    cout<< ans2 <<endl;
    return 0;
}