题目要求:
求一个9位数,该数的每一位均是1-9之间的数,但是每位上的数字各不相同.最后使得这个9位数从高位开始,前一位能被1整除,前两位能被2整除,前三位能被3整除,前四位能被4整除……一直到整个9位数能被9整除.
算法设计:
对于这类题,相信大多数人一拿到手就想到穷举所有的可能性(如果你不这样想,那你就是例外了:)呵呵).刚开始偶也想到了用9重for循环来穷举,后来想用递归能否实现呢?好,我们来结合程序说明,这样比较清晰些哈.我们用一个数组a来存储所有可能用到的数字,其中a[0]不用,后面的就依次为1-9对应数组a[1]到a[9].而后用另外一个数组b来存储已经被使用了的数字,如我们使用了数字3(数组a中的a[3],那我们就使b[3]=a[3],同时要从a中剔除3这个数以表示这个数字已经被使用了,所以就置a[3]=0.程序中还有一个深度变量depth,表示当前的深度,如刚开始的时候为1,此时depth=1,如果result=12,则depth=2,这样设置是为了便于用result对depth整除运算,免得又增加一个变量.最后到第9层深度的时候,即已经穷举到第9个数了,如果有结果则输出.
好了,大致过程说了.我们就用实例来说明程序的过程.首先depth=1,穷举a中的每一个数,所以result=1,由于result能被1整除,所以满足条件.此时1已经被使用了,所以要在b中保存这个数,并从a中剔除它,所以有b=a;a=0;然后进入下一个数字的猜测,即depth=2,由于a[1]=0了,所以此时穷举的数就是从2开始了,使得result=12,此时result也能被2整除,所以就进入第三个数的猜测.如果我们在这里改一下,使a[2]=3,则result=13就不能被2整除了,所以就要返回到上一次函数调用的位置,即getnum(depth+1);此时注意,我们已经从第2层深度返回到第一层深度了.然后执行后面的语句a=b;使刚才被剔除的数又重新回到a中来(因为这个数在第2个位置不合适,但是它又必须到其他的位置,所以要重新加入到a中来,以便其他位的穷举).呵呵,不晓得说清楚没,大家有兴趣的话,可以在纸上画一画.好了,我把程序贴出来,大家看看吧:)
源程序(编译通过)
#include < stdio.h >
int a[]={0,1,2,3,4,5,6,7,8,9}; //所有可能的数字
int b[10] ={0}; //用于临时存放已经被用了的数字
long result=0; //最后的结果
void getnum(int depth) //递归函数求解最后的结果,depth为深度,从1开始计算
{
int i;
if(depth==10)return;
for(i=1;i < 10;i++)
if(a !=0){ //穷举每一个在数组a中的可能的数
result=result*10+a;
if(result%depth==0){ //看这个求得的数是否满足整除的条件,如果是则将
b=a; //该数字放入已经使用数字的数组b中,同时使a中对?
a=0; //应位的数为0,表使用了,并从该数组中剔除.
getnum(depth+1);
a=b; //恢复被剔除的数,穷举下一个可能的数
if(depth==9)printf("%ld \n",result);
}
result/=10; //同时使结果恢复到上一个状态
}
}
void main()
{
getnum(1); //从深度为1开始穷举,即只有1位数的情况
getch();
}
最后的结果就是381654729
