文章

36

粉丝

0

获赞

5

访问

24.4k

头像
最简真分数 题解:算法上感觉对了,但是AC不了
P1180 北京大学/北京航空航天大学机试题
发布于2024年3月25日 09:00
阅读数 946

#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 VIP
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;
}

 

赞(0)

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

2024年3月26日 12:35
snake VIP
2024年3月25日 10:18

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

赞(0)

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