C趣味编程百例(08)

26.亲密数
27.自守数
28.回文数
29.求具有abcd=(ab+cd)²性质的四位数




26.亲密数
    假如整数A的全部因子(包括1，不包括A本身)之和等于B；且整数B的全部因子(包括1，不包括B本身)之和等于A，则将整数A和B称为亲密数。求3000以内的全部亲密数。
*题目分析与算法设计
    按照亲密数定义，要判定数a是否有亲密数，只要计算出a的全部因子的累加和为b，再计算b的全部因子的累加和为n，若n等于a则可判定a和b是亲密数。计算数a的各因子的算法：
    用a依次对i(i=1~a/2)进行模运算，若模运算结果等于0，则i为a的一个因子；否则i就不是a的因子。
*程序说明与注释
#include<stdio.h>
void main()
{
    int a,i,b,n;
    printf("There are following friendly--numbers pair smaller than 3000:\n");
    for(a=1;a<3000;a++)        /*穷举1000以内的全部整数*/
    {       
        for(b=0,i=1;i<=a/2;i++)    /*计算数a的各因子，各因子之和存放于b*/
            if(!(a%i))b+=i;        /*计算b的各因子，各因子之和存于n*/
        for(n=0,i=1;i<=b/2;i++)
            if(!(b%i))n+=i;
        if(n==a&&a<b)
            printf("%4d..%4d    ",a,b);     /*若n=a，则a和b是一对亲密数，输出*/
    }
}
*运行结果
    There are following friendly--numbers pair smaller than 3000:
        220..  284        1184.. 1210        2620.. 2924

-----------------------------------------------------------------

27.自守数
    自守数是指一个数的平方的尾数等于该数自身的自然数。例如：
            25²=625      76²=5776       9376²=87909376
    请求出200000以内的自守数
*题目分析与算法设计
    若采用“求出一个数的平方后再截取最后相应位数”的方法显然是不可取的，因为计算机无法表示过大的整数。
    分析手工方式下整数平方(乘法)的计算过程，以376为例：
        376                  被乘数
     X  376                    乘数
   ----------
       2256              第一个部分积=被乘数*乘数的倒数第一位
      2632               第二个部分积=被乘数*乘数的倒数第二位
     1128                第三个部分积=被乘数*乘数的倒数第三位
   ----------
     141376              积
    本问题所关心的是积的最后三位。分析产生积的后三位的过程，可以看出，在每一次的部分积中，并不是它的每一位都会对积的后三位产生影响。总结规律可以得到：在三位数乘法中，对积的后三位产生影响的部分积分别为：
        第一个部分积中：被乘数最后三位*乘数的倒数第一位
        第二个部分积中：被乘数最后二位*乘数的倒数第二位
        第三个部分积中：被乘数最后一位*乘数的倒数第三位
    将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同样问题的不同位数乘积。
    按照手工计算的过程可以设计算法编写程序。
*程序说明与注释
#include<stdio.h>
void main()
{
    long mul,number,k,ll,kk;
    printf("It exists following automorphic nmbers small than 200000:\n");
    for(number=0;number<200000;number++)
    {
        for(mul=number,k=1;(mul/=10)>0;k*=10);
                   /*由number的位数确定截取数字进行乘法时的系数k*/
        kk=k*10;      /*kk为截取部分积时的系数*/
        mul=0;        /*积的最后n位*/
        ll=10;        /*ll为截取乘数相应位时的系数*/
        while(k>0)
        {
            mul=(mul+(number%(k*10))*(number%ll-number%(ll/10)))%kk;
                 /*(部分积+截取被乘数的后N位*截取乘数的第M位)，%kk再截取部分积*/
            k/=10;               /*k为截取被乘数时的系数*/
            ll*=10;
        }
        if(number==mul)         /*判定若为自守数则输出*/
            printf("%ld   ",number);
    }
}
*运行结果
    It exsts following automorphic numbners smaller than 200000:
     0    1    5    6    25    76    376    625    9376    90625    109376

-------------------------------------------------------------

28.回文数
    打印所有不超过n(取n<256) 的其平方具有对称性质的数(也称回文数)。
*题目分析与算法设计
    对于要判定的数n，计算出其平方后(存于a)，将a的每一位进行分解，再按a的从低到高的顺序将其恢复成一个数k(如n=13，则a=169且k=961)，若a等于k则可判定n为回亠数。
*程序说明与注释
#include<stdio.h>
void main()
{
    int m[16],n,i,t,count=0;
    long unsigned a,k;
    printf("No.    number     it's square(palindrome)\n");
    for(n=1;n<256;n++)            /*穷举n的取值范围*/
    {
        k=0;t=1;a=n*n;            /*计算n的平方*/
        for(i=1;a!=0;i++)     /*从低到高分解数a的每一位存于数组m[1]~m[16]*/
        {
            m[i]=a%10;
            a/=10;
        }
    
    for(;i>1;i--)
    {
        k+=m[i-1]*t;
        t*=10;
    }
    if(k==n*n)
        printf("%2d%10d%10d\n",++count,n,n*n);
   }
}
*运行结果
        No.            number            it's square(palindrome)
        1                1                    1
        2                2                    4
        3                3                    9
        4                11                   121
        5                22                   484
        6                26                   676
        7                101                  10201
        8                111                  12321
        9                121                  14641

-------------------------------------------------------------

29.求具有abcd=(ab+cd)²性质的四位数
    3025这个数具有一种独特的性质：将它平分为二段，即30和25，使之相加后求平方，即(30+25)²，恰好等于3025本身。请求出具有这样性质的全部四位数。
*题目分析与算法设计
    具有这种性质的四位数没有分布规律，可以采用穷举法，对所有四位数进行判定，从而筛选出符合这种性质的四位数。具体算法实现，可任取一个四位数，将其截为两部分，前两位为a，后两位为b，然后套用公式计算并判定。
*程序说明与注释
#include<stdio.h>
void main()
{
    int n,a,b;
    printf("There are following number with 4 digits satisfied condition\n");
    for(n=1000;n<10000;n++)             /*四位数N的取值范围1000~9999*/
    {
        a=n/100;                        /*截取N的前两位数存于a*/
        b=n%100;                        /*截取N的后两位存于b*/
        if((a+b)*(a+b)==n)      /*判定N是否为符合题目所规定的性质的四位数*/
            printf("%d  ",n);
    }
}
*运行结果
    There are following numbers with 4 digits satisfied condition:
        2025        3025        9801