B 1062 最简分数(最大公约数、分数、交叉相乘法)

    技术2022-07-11  130

    题目

    思路

    一开始题目不是很理解,其实就是找两分数a,b间,以K为分母的分数。 需要用到分数的交叉相乘法来比大小:

    首先比较a,b,确保小的在前,大的在后;令分子从1到k开始遍历,用分子和分母的最大公约数是否为1来判别是否为最简分数。用交叉相乘法比较分数和a,b的大小;进行输出,行末不能有空格。

    AC代码

    #include<bits/stdc++.h> using namespace std; struct fraction{ int up; int down; }; int gcd(int a,int b){ if(b==0) return a; else return gcd(b,a%b); } int main(){ int k; char c; fraction a,b; cin>>a.up>>c>>a.down; cin>>b.up>>c>>b.down; cin>>k; if(a.up*b.down > a.down*b.up){ //若分数a<b,则交换a,b swap(a.up,b.up); swap(a.down,b.down); } int num[k]={0},cnt=0; for(int i=1;i<k;i++){ //利用交叉相乘法,比较i/k和a,b大小,用最大公约数是否为1判断i/k是否为最简分数 if(a.up*k < i*a.down && b.up*k > i*b.down && gcd(i,k)==1) { num[cnt++]=i; } } for(int i=0;i<cnt;i++){ if(i!=cnt-1) cout<<num[i]<<'/'<<k<<' '; else cout<<num[i]<<'/'<<k; } return 0; }
    Processed: 0.025, SQL: 9