Problem K: 最小公倍数与最大公约数
Description
输入两个整数,求它们的最大公约数与最小公倍数。
Input
输入两个整数
Output
第一行输出最大公约数; 第二行输出最小公倍数;

分析:
求最大公约数采用辗转相除的方法。
ex:
有两整数a和b:

① a%b得余数c

② 若c=0,则b即为两数的最大公约数

③ 若c≠0,则a=b,b=c,再回去执行①

例如求27和15的最大公约数过程为:

27÷15 余12 15÷12余3 12÷3余0 因此,3即为最大公约数
最大公倍数计算公式为a*b/最大公约数
个人答案,代表题目答案,未优化
#include <stdio.h>

int main()
{
int n,a,b,c,d,e,min,max;
min =0;
max = 0;

while(scanf("%d%d",&a,&b)!=EOF)
{
if(a>b) c = b;else c = a;
for(int k = c-1;k>=1;k--)
{
if(a%k ==0 && b%k ==0)
{
min = k ;
break;
}
}
if (b%c ==0&& a%c ==0) min=c;
for(int g =1;g!=0;g++)
{
if(g % a ==0 && g%b==0)
{
max = g;
break;
}
}
printf("%d %d\n",min,max);
}
}
优化后的答案
#include <stdio.h>

int main()
{
int a,b,c,temp; //c为最大公约数,temp为输入两数的乘积
while(scanf("%d%d",&a,&b)!=EOF)
{
temp = a*b;        
c = a % b;
while (c!= 0)
 {
 a=b;
 b=c;
 c=a%b ;
 }
printf("%d %d",b,temp/b);
}
return 0;
}

买火车票时经常会碰到找钱问题。售票员手中有50、20、10、5、1元的钱币,你知道怎么找钱才能使找回的零钱张数最少吗?
Input
多组测试数据,输入需要找钱的钱数
Output
输出按下面格式: 第一行输出"change:",然后是你要找的钱 以下几行按面值从大到小输出要找的张数,格式如下:50 yuan: 1,如果1张也没有就不需要输出
Sample Input
76
Sample Output
change:76
50 yuan: 1
20 yuan: 1
5 yuan: 1
1 yuan: 1
#include<stdio.h>
int main(void)
{
    int sum1,sum2,sum3,sum4,sum5,ch,i;
    while(scanf("%d",&ch)!=EOF)
    {
        sum1=sum2=sum3=sum4=sum5=0;
        if(ch==0)
        printf("change:%d\n",ch);
        else if(ch!=0)
      {
          printf("change:%d\n",ch);
        for(i=0; ;i++)
        {
            if(ch>=50)
            {sum1++;ch=ch-50;}
            else if(ch>=20)
            {
                sum2++;ch=ch-20;
            }
            else if(ch>=10)
            {
                sum5++;ch=ch-10;
            }
            else if(ch>=5)
            {
                sum3++;ch=ch-5;
            }
            else if(ch>=1)
            {
                sum4++;ch=ch-1;
            }
            else if(ch==0)
            break;
        }
        if(sum1!=0)    
        printf("50 yuan: %d\n",sum1);
        if(sum2!=0)
        printf("20 yuan: %d\n",sum2);
        if(sum5!=0)
        printf("10 yuan: %d\n",sum5);
        if(sum3!=0)
        printf("5 yuan: %d\n",sum3);
        if(sum4!=0)
        printf("1 yuan: %d\n",sum4);
      }
    }
 return 0;    
}

2020-11-17_142339.png

标签: Notes

添加新评论