假设有标注了 1, 2, 3, …, n 各个数字的 n 张卡片。当第 1 张卡片的 数字为 k 时，则把前 k 张卡片逆向排序，并一直重复这个操作。举个例 子，当 n ＝ 6 时，如果由“362154”这个序列开始，则卡片的变化情况 如下。

这种情况下，卡片顺序一共变化 8 次后就无法继续变化了。

求使卡片顺序变化次数最多的 n 张卡片的顺序以及最大的变化次数。

 

1.顺序暴力递归思路：使用C++生成n位数的全排列，按照题意暴力模拟即可。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
int fun(int a[],int deep);//求该数组翻转多少次后第一个数为1

int tempList[99];
int maxList[99];
int maxi = 0;

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
      for(int i = 0;i<n;i++){
        tempList[i] = arr[i];//临时数组存储此时的全排列
      }
      int b = fun(tempList,0);//获得该排列翻转的次数，保存给b
      if(b > maxi){//如果b大于此时最大的数
        maxi = b;//最大的翻转次数更改为b
        for(int i = 0;i<n;i++){
            maxList[i] = arr[i];//存储翻转次数最多的数组更新
        }
      }
    }while(next_permutation(arr,arr+n));//获得下一个排列
}

int fun(int a[],int deep){
    if(a[0]==1){
        return deep;//如果第一个数是1的时候，返回结果
    }
   else{
    reverse(a,a+a[0]);//翻转数组的前a[0]个数
    fun(a,deep+1);//调用递归且deep+1，deep是我们的翻转次数
   }
}

int main(){
    int t;
     while(scanf("%d",&t)){
     if(t>=2 && t < 10){
     maxi = 0;
     int a[t+10];
     for(int i = 0;i<t;i++){
        a[i] = i+1;
     }
      all_permutation(a,t);
      printf("array is :");
      for(int i = 0;i<t;i++){
        printf("%d ",maxList[i]);
      }
      printf("\n");
      printf("max count = %d\n",maxi);
     }
     else{
        printf("please input number of 2~9!\n");
     }
     }
}

 

2.倒推优化递归思路：首先，数组的全排列需要第一个数是1，其次当一个数组中第i个数字是i的时候，这个数组一定有递推的上一步，否则这个数组就是最初情况。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
void fun(int a[],int n,int deep);//递归函数

int tempList[99];//存储临时数组
int maxList[99];//存储变化次数最多的数组结果
int maxi = 0;//存储变化的最大次数

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do
    {
        if(arr[0] == 1)
        {
            for(int i = 0; i<n; i++)
            {
                tempList[i] = arr[i];
            }
            fun(tempList,n,0);
        }
    }
    while(next_permutation(arr,arr+n));
}

void fun(int a[],int n,int deep)//递归函数
{
    if(deep > maxi){//获得最大翻转次数且存储此时的数组
        maxi = deep;
        for(int i = 0;i<n;i++){
            maxList[i] = a[i];
        }
    }
    for(int i = 1;i<n;i++){
        if(a[i]==i+1){//如果数组的第i个数等于i+1（因为数组从0开始）
            reverse(a,a+i+1);//翻转前i个数
            fun(a,n,deep+1);//开始递归，deep+1
            reverse(a,a+i+1);//翻转回去
        }
    }
}

int main()
{
    int t;
    while(scanf("%d",&t))
    {
        if(t>=2 && t < 10)
        {
            maxi = 0;
            int a[t+10];
            for(int i = 0; i<t; i++)
            {
                a[i] = i+1;
            }
            all_permutation(a,t);
            printf("array is :");
            for(int i = 0; i<t; i++)
            {
                printf("%d ",maxList[i]);
            }
            printf("\n");
            printf("max count = %d\n",maxi);
        }
        else
        {
            printf("please input number of 2~9!\n");
        }
    }
}