最近在网上看到个小学四年级的数学题，用1~8这8个数字构成两个四位数，每个数字只能使用一次，要求其中一个四位数是另一个四位数的4倍，求出这两个数。算了一会，没得啥子思路，感觉要试很多次才搞得出来，索性就编个程序算。解决这个问题的主要方向就是排列组合的问题，列出所有的组合，然后将字符数组转换为数字，找出符合关系的数字即为答案。
计算出来有两组答案，7452=1863*4,5472=1368*4。
根据百度文库里面有一篇文章讲解字符排列组合的算法，如
a
ba ab
cba cab bca acb bac abc
......以此类推。此算法就是利用上一次排列的结果，根据新加入的元素插入的位置来组织数据在内存中的存放。例如第三排我们是根据第二排的结果，将c插入到组合的第一个，第二个，第三个位置才产生了第三排的结果，这样的算法就很有规律了。
从上面的分析我们可以看出，该算法在写程序时就是要使用递归来实现，根据上一层的结果来做当前的计算。既然是递归，我们肯定先需要一种base情况，我们就用字符数量为2的就行，这时直接用四个赋值就可以完成递归初始化情况的。
对于递归情况相较而言稍微麻烦一点。首先我们要申请足够的内存来存放数据，对于n个不同的字符进行排列组合，有n！种不同的情况，对于每一种情况需要n个字节来存放，所以为存放最终结果我们需要申请n！*n个字节的内存，而上一次的结果是一段（n-1）！*（n-1）个字节，接下来要做的就是内存数据的复制和新数据的插入。
为了完成复制和插入，我们将会好好利用/和%两个运算。针对复制和插入的过程就是对新申请的内存的一个一个的赋值，我们利用下标访问的方法进行操作（设下标为j），利用if（j/n!==k）（k代表新数据插入位置）的结果确定的j值（满足该条件的j值是一段数值，且连续），表明这一段内存中的数据，新数据都插入到第k个位置。找到了该段内存之后，我们就要决定里面哪些值赋新数据，哪些进行copy。我们再用if（j%n！==k）即判断该下标的位置是否是插入新数据，如果不满足就进行内存copy，将PreResult里的东西copy过来。
全部代码如下：
#include <stdlib.h> #include <malloc.h> #include <iostream> using namespace std; #define LEN 8 char str[LEN]={'1','2','3','4','5','6','7','8'}; //unsigned int value[LEN]={1,2,3,4,5,6,7,8}; char* test(char* source,unsigned int n); unsigned int ChartoInt(char* original); void main() { char* p; unsigned int n; unsigned int j; unsigned int length=1; cin>>n; for(j=1;j<n+1;j++) { length=length*j; } p=test(str,n); for(unsigned int i=0;i<length;i++) { if( ChartoInt(p+i*8+0)==4*ChartoInt(p+i*8+4) ) cout<<ChartoInt(p+i*8+0)<<ChartoInt(p+i*8+4); } //for(int i=0;i<n*length;i++) //{ // cout<<*(p+i); //} //cout<<*p<<*(p+1)<<*(p+2)<<*(p+3)<<*(p+4)<<*(p+5)<<*(p+6)<<*(p+7)<<*(p+8)<<*(p+9)<<*(p+10)<<*(p+11)<<*(p+12)<<*(p+13)<<*(p+14)<<*(p+15)<<*(p+16)<<*(p+17); while(1); } char* test(char* source,unsigned int n) { unsigned int i;//to be used in caculate n! unsigned int length=1;//the new memory to allocate unsigned int j;// to be used in classify the positon to insert new data unsigned int k; unsigned int count; char* CurrentMemory; //char* PreSource; char* PreResult; //char* PreSource=&source[0]; if(2==n)//this is the base condition { CurrentMemory=(char*)malloc(sizeof(char)*4); *CurrentMemory=*(source+1); *(CurrentMemory+1)=*source; *(CurrentMemory+2)=*source; *(CurrentMemory+3)=*(source+1); return CurrentMemory; } else //this is the recursive condittion { for(i=1;i<n+1;i++)//to caculate n! { length=length*i; } CurrentMemory=(char*)malloc(sizeof(char)*n*length);//allocate the memory needed to use PreResult=test(source,n-1); for( k=0 ; k<n ; k++ )//k is to be used in define which block have the same position to insert the new data { unsigned int num=0; for(j=0;j<length*n;j++)//j is the number of each data { if(j/length==k)//in each block what we should do,我们找到在第k个位置插入新数据的块，是满足这个if语句的，然后我们针对这块数据进行操作。这一大串for循环找到的东西就是满足条件的下标，但是并没有做任何操作。 { if(j%n==k)//要插入新数据的位置 { CurrentMemory[j]=source[n-1]; } else//需要从上一次的结果中复制数据到新开辟的内存中来 { CurrentMemory[j]=PreResult[num]; num++; } } } } free(PreResult); return CurrentMemory; } } unsigned int ChartoInt(char* original) { unsigned int Result; Result=(unsigned int)((*original)-0x30)*1000+ (unsigned int)((*(original+1))-0x30)*100+ (unsigned int)((*(original+2))-0x30)*10+ (unsigned int)((*(original+3))-0x30); return Result; }