1228: 华科版C语言程序设计教程(第二版)习题5.7

题目:
Description
 这天老师给小豪出了一道很简单题目放松:输入一个分数,让你求出它们的最简分数。
Input
 第一行包括一个T,表示测试数据的组数。
接下来T行每行包括一个分数。(分子分母均在int范围内)
Output
 对于每个测试样例,输出一行其最简分数。

样例:
Sample Input
3
2/6
3/1
11/36
Sample Output
1/3
3/1
11/36

思路:这个题目的核心就在于其分数约分的条件,即分子分母之间有公约数;所以可以用循环依次找公约数,找到之后用分子分母将公约数除去,直到没有公约数为止。但这个题目特别要注意的一点是找公约数时要从最大的公约数找起,即找最大公约数。因为这样每次可以将数变化的最大,使得减少循环到次数!

新技巧:对于找两个数公约数除去的这种题目,从最大的公约数找起然后除去,这样可以减少循环到次数,从而避免超时;

代码:

#include<stdio.h>

int main()
{
    int i,a,b,t;
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        scanf("%d%*c%d",&a,&b);
        int x=a,y=b;
        while(1)
        {
            int s=a%b;
            a=b;
            b=s;
            if(b==0)
                break;
        }
        printf("%d/%d\n",x/a,y/a);
    }
    return 0;
}
相关文章
相关标签/搜索