例题3-5 生成元 UVa1583

算法竞赛入门经典（第2版）第3章 数组和字符串

例题3-5 生成元 UVa1583

感悟。

0、查看书中代码，对if(ans[y]==0||m<ans[y])心存疑虑。着手跟踪

if(ans[y]==0||m<ans[y]){

            if(m<ans[y])

                printf("m=%d ans[y]=%d y=%d\n",m,ans[y],y);

            ans[y]=m;

        }

打印如下：

m=99991 ans[y]=3811788 y=100028

m=99993 ans[y]=3811784 y=100032

m=99995 ans[y]=3811792 y=100036

很明显数组越界，书中ans数组范围0-100004。

建议修改如下：

if(y<=n&&ans[y]==0){

      ans[y]=m;

 }

1、隐隐感到此题，制表，查表最快，当不够坚定，瞄了一眼提示（未看代码），与所想一致，开始着手编程。

2、挺简单一道题，满心欢喜提交，竟然WA，果断查英文原题，原来输入输出格式有限制。

Sample Input

3

216

121

2005

Sample Output

198

1979

3、立马提交AC，查看书中代码比本人略胜一筹，做了本人想而未做的对应关系ans[y]=m。

附上代码：

环境Dev-cpp4.9.9.2

#include <stdio.h>

const int maxn=100000+10;

int a[maxn];

int bsum(int b){//获得整数各个位置的数字之和 

    int sum=0;

    while(b){

        sum+=b%10;

        b/=10;

    }

    return sum;

}

int main(){

    int i;

    int n;

    int T;

    for(i=1;i<=100000;i++){//制表 

        a[i]=bsum(i)+i;

    }

    scanf("%d",&T);

    while(T){

        T--;

        scanf("%d",&n);

        for(i=1;i<n;i++){//查表 

            if(a[i]==n)

                break;

        }

        if(i==n)//查无结果 

            printf("%d\n",0);

        else

            printf("%d\n",i);

    }

    return 0;

}