算法考试填数字问题

在算法考试中的最后一题，题目为：对于任意一个数字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; } 算法正确性我还没检验，请各位大神指正。最后放下代码下载地址：http://download.csdn.net/detail/xanxus46/4597909