最大公因子(栈和队列)

最大公因子(栈和队列)

时间: 1ms        内存:1000M

描述:

   已知求两个正整数mn的最大公因子的过程用自然语言可以表述为反复执行如下动作:第一步:若n等于零,则返回m;第二步:若m小于n,则mn相互交换;否则,保存m,然后将nm,将保存的m除以n的余数送n。将过程存入队列中。

输入:

4 6

输出:

12

示例输入:

5 7

示例输出:

35

提示:

参考答案(内存最优[748]):

#include <stdio.h> 
int main() 
{ 
    int a,b,m,n,i,j; 
    while(scanf("%d %d",&a,&b)==2) 
    { 
        i=a; 
        j=b; 
        while(b!=0) 
  
        { 
            m=a; 
            a=b; 
            b=m%b; 
        } 
                  
       n=(i/a)*j; 
       printf("%d\n",n); 
        
    } 
    return 1; 
} 

参考答案(时间最优[0]):

#include <stdio.h> 
int main() 
{ 
    int a,b,m,n,i,j; 
    while(scanf("%d %d",&a,&b)==2) 
    { 
        i=a; 
        j=b; 
        while(b!=0) 
  
        { 
            m=a; 
            a=b; 
            b=m%b; 
        } 
                  
       n=(i/a)*j; 
       printf("%d\n",n); 
        
    } 
    return 1; 
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注