蓝桥杯——既约分数（c语言）

大家好，欢迎来到IT知识分享网。

目录

一、题目描述

二、思路分析

1、分析题意：

2、解题思路：

三、算法实现

四、算法改进

一、题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。

例如  1/7 , 3/4 , 1/8 都是既约分数。

请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1和 2020）？

运行限制

• 最大运行时间：2s
• 最大运行内存: 128M

二、思路分析

1、分析题意：

最大公约数是1；分子和分母都是1——2020之间的整数，包括（1,2020）。

明确：

1、最大公约数为1，这两个数的约数各自不一定只有1。

2、求最大公约数为1的两数，分子分母一定不相等（分子分母都为 1例外），两数相等，其本身就是公约数。

2、解题思路：

1、需要遍历吗？ 分子开始，遍历分母，然后分母开始，遍历分子？

       确定分子，然后遍历分母，判断是否有最大公约数，如果有count+2；因为只要有一组分子分母符合，那么分子分母互调也符合，所以count+2。

2、如何判断两数之间只有最大公约数？

      分母都除以分子的全部约数，判断能不能整除，能则不是。

有个问题：

1、确定分子，遍历分母，每个分子，分母都从1开始遍历吗？

     想：这样与我们设置的结构会有重复。

解决办法：如果每次分母遍历从分子的下一个数开始，是否可以呢，并且不会重复？

     这样不会重复，同时解决了分子分母不能相等的问题，不过最后结果count需要再加1，因为分子分母都为1满足。

三、算法实现

#include<stdio.h> main() { int i=0,j=0; int count=0; for(i=1;i<2020;i++) { int app[2020]={0}; //在循环中定义一个数组存放分子每一次的约数 int m=0,k=0; for(int k=2;k<=2020;k++) //判断分子的约数 { if(i%k==0) { app[m]=k; m++; } } for(j=i+1;j<=2020;j++) //判断分母 { for(k=0;k<m;k++) { if(j%app[k]==0) break; } if(k==m) //k==m,说明分子的约数，分母都不能整除 count=count+2; //每一组加2，分子分母可以互调 } } printf("%d",count+1); // 注意；count+1，分子分母都为1的情况 }

四、算法改进

求最大公约数可以用辗转相除法，也是欧几里得算法，

算法中也就是用递归函数实现

每一次用两数中的大数，除以小的数，直到a%b=0时，返回的b即是之间的最大公约数。

 6%16=6   

继续执行   辗转 （16,6）

16%6=4  

继续执行   辗转（6,4）

6%4=2 

继续执行  辗转（4,2）

4%2=0       最大公约数b=2

算法实现：

int app(int a,int b) { if(a%b==0) return b; else return app(b,a%b); } 

#include<stdio.h> int app(int a,int b) { if(a%b==0) return b; else return app(b,a%b); } int main() { int i,j,sum=0; for(i=1;i<=2020;i++) { for(j=1;j<=2020;j++) { if(app(i,j)==1) //判断分子分母的最大公约数是否为1 { sum++; } } } printf("%d",sum); return 0; }

执行结果：