新技术论坛
搜索
查看: 1187|回复: 0
打印 上一主题 下一主题

[VC/C++] 【C语言讨论】C语言最大公约数三种算法

[复制链接]
  • TA的每日心情
    慵懒
    2017-1-5 23:52
  • 签到天数: 183 天

    连续签到: 2 天

    [LV.7]常住居民III

    扫一扫,手机访问本帖
    楼主
    跳转到指定楼层
    发表于 2016-3-17 19:28:38 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    求最大公约数算法


    (1)辗转相除法
    有两整数ab
    a%b得余数c
    c=0,则b即为两数的最大公约数
    ③ 若c≠0,则a=bb=c,再回去执行①
    例如求2715的最大公约数过程为:
    27÷15 1215÷12312÷30因此,3即为最大公约数

    1.     #include<stdio.h>  
    2.     void main()   /*  辗转相除法求最大公约数 */   
    3.     {   
    4.        int m, n, a, b, t, c;  
    5.        printf("Input two integer numbers:\n");  
    6.        scanf("%d%d", &a, &b);  
    7.        m=a;   n=b;  
    8.        while(b!=0)  /* 余数不为0,继续相除,直到余数为0 */   
    9.        { c=a%b; a=b;  b=c;}  
    10.        printf("The largest common divisor:%d\n", a);  
    11.        printf("The least common multiple:%d\n", m*n/a);  
    12.     }  
    复制代码
    ⑵ 相减法
    有两整数a和b:
    ① 若a>b,则a=a-b
    ② 若a<b,则b=b-a
    ③ 若a=b,则a(或b)即为两数的最大公约数
    ④ 若a≠b,则再回去执行①
    例如求27和15的最大公约数过程为:
    27-15=12( 15>12 ) 15-12=3( 12>3 )
    12-3=9( 9>3 ) 9-3=6( 6>3 )
    6-3=3( 3==3 )
    因此,3即为最大公约数
    1.     #include<stdio.h>  
    2.     void main ( )  /* 相减法求最大公约数 */  
    3.     {   
    4.        int m, n, a, b, c;  
    5.        printf("Input two integer numbers:\n");  
    6.        scanf ("%d,%d", &a, &b); m=a; n=b;   
    7.          /* a, b不相等,大数减小数,直到相等为止。*/   
    8.        while ( a!=b)   
    9.              if (a>b)  a=a-b;       
    10.              else  b=b-a;   
    11.        printf("The largest common divisor:%d\n", a);  
    12.        printf("The least common multiple:%d\n", m*n/a);  
    13.     }  
    复制代码
    ⑶穷举法
    有两整数a和b:
    ① i=1
    ② 若a,b能同时被i整除,则t=i
    ③ i++
    ④ 若 i <= a(或b),则再回去执行②
    ⑤ 若 i > a(或b),则t即为最大公约数,结束
    改进:
    ① i= a(或b)
    ② 若a,b能同时被i整除,则i即为最大公约数,
    结束
    ③ i--,再回去执行②
    有两整数a和b:
    ① i=1
    ② 若a,b能同时被i整除,则t=i
    ③ i++
    ④ 若 i <= a(或b),则再回去执行②
    ⑤ 若 i > a(或b),则t即为最大公约数,结束
    改进:
    ① i= a(或b)
    ② 若a,b能同时被i整除,则i即为最大公约数,
    结束
    ③ i--,再回去执行②
    1.     #include<stdio.h>  
    2.     void main ()  /* 穷举法求最大公约数 */  
    3.     {   
    4.        int  m, n, a, b, i, t;   
    5.        printf("Input two integer numbers:\n");  
    6.        scanf ("%d,%d", &a, &b); m=a;  n=b;   
    7.        for (i=1; i<= a; i++)   
    8.            if ( a%i == 0 && b%i ==0 )    t=i;  
    9.        printf("The largest common divisor:%d\n", t);  
    10.        printf("The least common multiple:%d\n", m*n/t);  
    11.     }   
    12.     /*  改进后的
    13.        for (t= a; t>0; t-- )     
    14.            if ( a%t == 0 && b%t ==0 )    break;  
    15.     */  
    复制代码






    高级模式
    B Color Image Link Quote Code Smilies

    本版积分规则

    手机版|Archiver|开发者俱乐部 ( ICP/ISP证:辽B-2-4-20110106号 IDC证:辽B-1-2-20070003号 )

    GMT+8, 2024-12-23 05:56 , Processed in 0.133090 second(s), 18 queries .

    X+ Open Developer Network (xodn.com)

    © 2009-2017 沈阳讯网网络科技有限公司

    快速回复 返回顶部 返回列表