最简真分数题解：算法上感觉对了，但是AC不了_P1180

williams

TA的个人主页 >

文章

粉丝

获赞

152

访问

49.2k

最简真分数题解：算法上感觉对了，但是AC不了

williams

P1180 北京大学/北京航空航天大学机试题

发布于2024年3月25日 09:00

阅读数 1.8k

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>


int judge(int a,int b){
    for(int i=2;i<a;i++){
        if(a%i==0&&b%i==0) return 1; //不是最简真分数返回1
    }
    return 0;
}

int main(){
    int num,c[1000],count=0,u,temp=0;
    while(scanf("%d",&num)!=EOF){
        for(int i=0;i<num;i++) scanf("%d",&c[i]);
        
        for(int i=1;i<num;i++){  //插排进行排序
            if(c[i]<c[i-1]){
                temp = c[i];
                for(u=i-1;u>=0&&c[u]>temp;u--){
                    c[u+1] = c[u];
                }
                c[u+1] = temp;
            }
        }

        for(int i=0;i<num;i++){
            for(int j=i+1;j<num;j++){
                if(judge(c[j],c[i])==0) count++;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

登录查看完整内容

登录后发布评论

6 条评论

snake

2024年3月25日 22:06

有两个地方要修改

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>


int judge(int a,int b){
    for(int i=2;i<=a;i++){//这里是小于等于!!!
        if(a%i==0&&b%i==0) return 1; //不是最简真分数返回1
    }
    return 0;
}

int main(){
    int num;
    while(scanf("%d",&num)!=EOF){
		int c[1000],count=0,u,temp=0;//这里要放在循环里!!!
        for(int i=0;i<num;i++) scanf("%d",&c[i]);
        
        for(int i=1;i<num;i++){  //插排进行排序
            if(c[i]<c[i-1]){
                temp = c[i];
                for(u=i-1;u>=0&&c[u]>temp;u--){
                    c[u+1] = c[u];
                }
                c[u+1] = temp;
            }
        }

        for(int i=0;i<num;i++){
            for(int j=i+1;j<num;j++){
                if(judge(c[j],c[i])==0) count++;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

williams : 回复 snake：无语了，我脑子不好用了。。小细节。。

2024年3月26日 12:35

回复给：

snake

2024年3月25日 10:18

排序算法有问题，可以不用排序，也可以选择用qsort排序。

williams : 回复 snake：排序算法已经更正了，但是还是AC不了，我把样例中的几个数字顺序颠倒，输出17没问题，也不至于放进oj正确率0% 感觉挺奇怪的

2024年3月25日 14:43

snake : 回复 williams：要用多组输入，而且感觉你排序还是有点问题。

2024年3月25日 15:38

williams : 回复 snake：排序算法是王道书上的，我插排一直用的这个，之前AC题目也用的这个代码应该不会错。加了EOF也还是不行。。。很怪

2024年3月25日 16:31

回复给：