我爱学习网-上传
当前位置: 主页 > 编程 > C语言 >

C语言实例 九位累进可除数

时间:2013-04-29 21:48来源:我爱学习网 作者:布丁点儿 点击:

  求九位累进可除数。所谓九位累进可除数就是这样一个数:这个数用到1到9这九个数字组成,每个数字刚好只出现一次。这九个位数的前两位能被2整除,前三位能被3整除......前N位能被N整除,整个九位数能被9整除。

  *问题分析与算法设计

  问题本身可以简化为一个穷举问题:只要穷举每位数字的各种可能取值,按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。

  问题中给出了“累进可除”这一条件,就使得我们可以在穷举法中加入条件判断。在穷举的过程中,当确定部分位的值后,马上就判断产生的该部分是否符合“累进可除”条件,若符合,则继续穷举下一位数字;否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中,可以尽可能早的发现矛盾,尽早地放弃不必要穷举的值,从而提高程序的执行效率。

  为了达到早期发现矛盾的目的,不能采用多重循环的方法实行穷举,那样编出的程序质量较差。程序中使用的算法不再是穷举法,而是回朔法。

  *程序说明与注释

  #include<stdio.h>

  #define NUM 9

  int a[NUM+1];

  int main()

  {

  int i,k,flag,not_finish=1;

  long sum;

  i=1;

  /*i:正在处理的数组元素,表示前i-1个元素已经满足要求,正处理的是第i个元素*/

  a[1]=1; /*为元素a[1]设置初值*/

  while(not_finish) /*not_finish=1:处理没有结束*/

  {

  while(not_finish&&i<=NUM)

  {

  for(flag=1,k=1;flag&&k<i;k++)

  if(a[k]==a[i])flag=0; /*判断第i个元素是否与前i-1个元素重复*/

  for(sum=0,k=1;flag&&k<=i;k++)

  {

  sum=10*sum+a[k];

  if(sum%k)flag=0; /*判断前k位组成的整数是否能被k整除*/

  }

  if(!flag) /*flag=0:表示第i位不满足要求,需要重新设置*/

  {

  if(a[i]==a[i-1]) /*若a[i]的值已经经过一圈追上a[i-1]*/

  {

  i--; /*i值减1,退回处理前一个元素*/

  if(i>1&&a[i]==NUM)

  a[i]=1; /*当第i位的值达到NUM时,第i位的值取1*/

  else if(i==1&&a[i]==NUM) /*当第1位的值达到NUM时结束*/

  not_finish=0; /*置程序结束标记*/

  else a[i]++; /*第i位的值取下一个,加1*/

  }

  else if(a[i]==NUM) a[i]=1;

  else a[i]++;

  }

  else /*第i位已经满足要求,处理第i+1位*/

  if(++i<=NUM) /*i+1处理下一元素,当i没有处理完毕时*/

  if(a[i-1]==NUM) a[i]=1; /*若i-1的值已为NUM,则a[i]的值为1*/

  else a[i]=a[i-1]+1; /*否则,a[i]的初值为a[i-1]值的"下一个"值*/

  }

  if(not_finish)

  {

  printf("\nThe progressire divisiable number is:");

  for(k=1;k<=NUM;k++) /*输出计算结果*/

  printf("%d",a[k]);

  if(a[NUM-1]<NUM) a[NUM-1]++;

  else a[NUM-1]=1;

  not_finish=0;

  printf("\n");

  }

  }

  }

  *运行结果

  The progressire divisible number is: 381654729

  *思考题

  求N位累进可除数。用1到9这九个数字组成一个N(3<=N<=9)位数,位数字的组成不限,使得该N位数的前两位能被2整除,前3位能被3整除,......,前N位能被N整除。求满足条件的N位数。

------分隔线----------------------------

栏目列表
看看啦