C趣味程序(二)(13)同構(gòu)數(shù)

2.8 同構(gòu)數(shù)
     正整數(shù)n若是它平方數(shù)的尾部，則稱n為同構(gòu)數(shù)。例如，6是其平方數(shù)36的尾部，76是其平方數(shù)5776的尾部，6與76都是同構(gòu)數(shù)。
     試求指定位數(shù)的同構(gòu)數(shù)序列。
    1、算法分析：
     對指定范圍內(nèi)的每一個整數(shù)a，求出其平方，判斷a是否是其平方的尾部，通常有以下方法：
     通過字符串子串比較找出同構(gòu)數(shù)。
     為了求更高位數(shù)的同構(gòu)數(shù)，可應用同構(gòu)數(shù)的以下性質(zhì)：一個m位同構(gòu)數(shù)的尾部m-1位數(shù)也是一個同構(gòu)數(shù)。道理很簡單，a是一個m位數(shù)，a的平方數(shù)尾部的m-1位僅由a尾部的m-1位決定而與a的位無關(guān)。
     易知一個同構(gòu)數(shù)有三個：1,5，6，則二位同構(gòu)數(shù)的個位數(shù)字只可能是1,5，6這三個數(shù)字。
     根據(jù)這一思路，我們可應用遞推求出多位同構(gòu)數(shù)串。
    2.求指定區(qū)間內(nèi)的同構(gòu)數(shù)
    程序代碼如下：
    #include
    #include
    #include
    char *right(char *ms,int len); /*截取一個字符串尾部長為len個字符的子串*/
    void main()
    {
     long a;
     int len;
     char as[10];
     char ms[20];
     printf("求[1,10000]中的同構(gòu)數(shù)：\n");
     for(a=1;a<=10000;a++)
     {
     ultoa(a,as,10); /*數(shù)a轉(zhuǎn)換為字符串，存入as*/
     len=strlen(as);
     ultoa(a*a,ms,10);
     if(strcmp(as,right(ms,len))==0) /*比較字符串a(chǎn)s與ms長為len的子串是否相等*/
     printf("%s 其平方為 %s\n",as,ms); /*相等就是同構(gòu)數(shù)，輸出結(jié)果*/
     }
    }
    char *right(char *ms,int len) /*截取字符串尾部長為len子串的函數(shù)*/
    {
     int i,j;
     for(i=0;i<(signed)strlen(ms);ms++);
     for(j=0;j     return ms;
    }