C趣味程序(二)(07)

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:44:32

2.1.1 求两个整数a,b(a>b)最大公约数与最小公倍数
2.1.2 求多个整数的最大公约数与最小公倍数



2.1 最大公约数与最小公倍数
    试求若干个书籍正整数的最大公约数与最小公倍数。
    为方便表述，记：
        (a1,a2,...,an)为n个正整数a1,a2,...,an的最大公约数；
        {a1,a2,...an}为n个正整数a1,a2,...,an的最小公倍数。

2.1.1 求两个整数a,b(a>b)最大公约数与最小公倍数
算法分析如下：
    求两个整数a,b(a>b)的最大公约数通常采用“辗转相除”法；
    1)a除以b得余数r；若r=0，则b为所求的最大公约数。
    2)若r!=0，以b为a,r为b，继续1)。
    注重到任两整数总存在最大公约数，上述辗转相除过程中余数逐步变小，相除过程总会结束。
    两整数a,b的最小公倍数与最大公约数有如下简单关系： {a,b}(a,b)=ab
    因而由求得的最大公约数即可根据上式求得最小公倍数。
    在实际设计中，直接按最大公约数与最小公倍数的定义来实施，显得更为直观，也更为方便。
按“辗转相除法”设计，程序代码如下：
#include<stdio.h>
void swap(int *,int *);
void main()
{
    int a,b,m,n,r;  
    printf("输入正整数a,b:");
    scanf("%d,%d",&a,&b);
    if(a<b) swap(&a,&b);
    m=a;n=b;r=a%b;
    while(r!=0)
    {
        a=b;b=r;
        r=a%b;
    }
    printf("( %d, %d ) = %d\n",m,n,b);
    printf("{ %d, %d } = %d\n",m,n,m*n/b);
}
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
程序运行结果如下：
输入正整数：a,b 90,108
(108,90) = 18
{108,90} = 540

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

2.1.2 求多个整数的最大公约数与最小公倍数
对于3个或3个以上整数，最大公约数与最小公倍数有以下性质：
    (a1,a2,a3)=((a1,a2),a3)
    (a1,a2,a3,a4)=((a1,a2,a3),a4),...
    {a1,a2,a3}={{a1,a2},a3}
    {a1,a2,a3,a4}={{a1,a2,a3},a4},...
    应用这一性质，要求n个数的最大公约数，先求出前n-1个数的最大公约数t,再求第n个数与t的最大公约数。求n个数的最小公倍数也一样。这样递推实现求多个整数的最大公约数与最小公倍数。
程序代码如下：
#include<stdio.h>
int gy(int,int);
int gb(int,int);
void main()
{
    int a,b,c,d,i=2;
 int aa[10];
    printf("n个整数的最大公约记为(a1,a2,...an)\n");
    printf("n个整数的最小公倍记为{a1,a2,...an}\n");
    printf("n个整数逐个从键盘输入，以-1终止\n");
    printf("首先输入两个数a,b\n");
    scanf("%d,%d",&a,&b);
    c=a;
    d=a;
    aa[0]=a;aa[1]=b;
    while(b>0)
    {
        c=gy(c,b);        /*调用最大公约数函数*/
        d=gb(d,b);        /*调用最小公倍数函数*/
        printf("输入下一个整数(输入-1结束)：to b:  ");
        scanf("%d",&b);
        aa[i]=b;
        i++;
    }
    printf("(");
    for(i=0;aa[i]!=-1;i++)
       printf("%d,",aa[i]);
    printf(") = %d\n",c);
    printf("{");
    for(i=0;aa[i]!=-1;i++)
       printf("%d,",aa[i]);
    printf("} = %d\n",d);
}
int gy(int x,int y)
{
    int c; 
    for(c=x;c>=1;c--)
    {
        if((x/c==(float)x/c)&&(y/c==(float)y/c))
            break;
    }
    return c;
}
int gb(int x,int y)
{
    int d;
    for(d=x; d<=x*y;d+=x)
    {
        if(d/y==(float)d/y) break;
    }
    return d;
}
程序运行结果如下：

说明：
    对n(n>=3)个整数，不存在最大公约与最小公倍的积等于这n个整数之积的性质。因此不能套用2个整数的性质，以防出错。

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

上一篇：{实例}C趣味程序(二)(06) 人气:5110
下一篇：{实例}C趣味程序(二)(08) 人气:5287

C语言程序设计视频教程