求九位累进可除数。所谓九位累进可除数就是这样一个数:这个数用到1到9这九个数字组成,每个数字刚好只出现一次。这九个位数的前两位能被2整除,前三位能被3整除......前N位能被N整除,整个九位数能被9整除。
*问题分析与算法设计
问题本身可以简化为一个穷举问题:只要穷举每位数字的各种可能取值,按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。
问题中给出了“累进可除”这一条件,就使得我们可以在穷举法中加入条件判断。在穷举的过程中,当确定部分位的值后,马上就判断产生的该部分是否符合“累进可除”条件,若符合,则继续穷举下一位数字;否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中,可以尽可能早的发现矛盾,尽早地放弃不必要穷举的值,从而提高程序的执行效率。
为了达到早期发现矛盾的目的,不能采用多重循环的方法实行穷举,那样编出的程序质量较差。程序中使用的算法不再是穷举法,而是回朔法。
*程序说明与注释
#include
#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
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整除*/
}