算法考试填数字问题

在算法考试中的最后一题，题目为：对于任意一个数字n，我们有一个长度为2n的数组，我们需要把1~n个数填入这个数组里2次。填入数字的规则如下：当填入数字n时，另一个n必须与当前的n距离为n，例如两个1之间要夹着一个数字，两个2之间要夹着两个数字，如此类推，直到把2n个空格填满。现在我们要设计一个算法，我们求出n个数字的所有排列方式。
我的算法思想如下：既然两个n之间的距离为n，我们应该从n开始填入，因为n可以填入的位置最少，为1~n-1，而当n填入数组之后，n-1可以选择填入的位置的个数也为n-1，如此类推，1可以填入的位置的个数也为n-1。讲到这里，大家应该我所采用的算法就是深度遍历树，就像遍历一个文件夹里所有的文件一样。废话不多说，下面贴代码。
#include<iostream>
using namespace std;
int *array=NULL;
int size=0;
void input(int n);
void output();
//初始化数组里面不大于n的位置
void init(int * a,int n){
for(int i=0;i<size;i++)
{
if(a[i]<=n)
a[i]=0;
}
}
int main(){
cout<<"please input your number:"<<endl;
int n;
cin>>n;
size=2*n;
array=new int[size];
init(array,n);
input(n);
//output();
}
//往数组里面填入数字n，begin为允许开始填入的位置
void input(int n){
if(n==0)
return;
for(int i=0;i<size-n-1;i++){
init(array,n);
if(array[i]==0&&array[i+n+1]==0){
array[i]=n;
array[i+n+1]=n;
if(n==1)
{
output();
}
input(n-1);
}else
continue;
}
}
}
void output(){
cout<<"output the array:"<<endl;
for(int i=0;i<size;i++){
cout<<array[i]<<"\t";
}
cout<<endl;
}
 

补充：综合编程 , 其他综合 ,