lyh20021209
2022-01-24 23:04
采纳率: 76.9%
浏览 54
已结题

一道PAT1062 最简分数 测试用例运行超时

img


我的思路是:先通分,这里通分是把三个分母全部乘起来,然后会有一个分子的上界和下界。例如7/18 13/20 12 通分后有7/18=1680/4320 13/20=2808/4320 而对于任意的正整数x,都有x/12=360*x/4320。那么这个360x就要在1680和2808之间。那么x的最小值就是1680/360+1=5 最大值就是2808/360=7。在确定了上下界后,只要循环一次,看一下哪些是最简分数,输出即可
代码如下:


import java.io.*;
public class Main {
    private int num1;

    public Main(int num1){
        this.num1=num1;
    }

    private boolean hasGCD(int num2){//求是否有除了1之外的公约数的方法
        while(num1!=num2){
            if(num1>num2) num1=num1-num2;
            else num2=num2-num1;
        }
        if(num1!=1) return true;
        else return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String[] num=br.readLine().split(" ");
        String[] N1M1=num[0].split("/");
        String[] N2M2=num[1].split("/");

        int N1=Integer.parseInt(N1M1[0]),M1=Integer.parseInt(N1M1[1]);
        int N2=Integer.parseInt(N2M2[0]),M2=Integer.parseInt(N2M2[1]);
        int K=Integer.parseInt(num[2]);

        int min=N1*M2*K,max=N2*M1*K;//通分后分子的最小值最大值
        int minK=min/(M1*M2)+1,maxK=max/(M1*M2);//约分后分子的最小值最大值

        int temp;
        if(minK>maxK){
            temp=maxK;
            maxK=minK;
            minK=temp;
        }//这一段是为了防止前一个分数比后面一个分数大的情况,刁钻的测试用例

        String result="";
        for(int i=minK;i<=maxK;i++){
            if(!new Main(i).hasGCD(K)) result+=i+"/"+K+" ";//没有公约数就拼接上去,最后打印再去尾部空格
        }

        System.out.print(result.trim());
    }
}

这段代码进去测试点2运行超时了,具体问题在哪里?

img

1条回答 默认 最新

相关推荐 更多相似问题