跳至正文

每日一题——1447. 最简分数

1447. 最简分数

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。

  • 1 <= n <= 100

判断最简的条件就是分子分母的最大公约数为1

所以这里就要提到gcd函数了 也就是最大公约数函数

题解用的三目看不太懂 不过道理都差不多

我这里写了个辗转相除的递归 会比较好理解一点

例如1/2

那么分子为1 分母为2 这俩的最大公约数就是1

public class Solution {
    public IList<string> SimplifiedFractions(int n) 
    {
        IList<string> ans = new List<string>();
        for (int down = 2; down <= n; down++)
        //分母从2开始
        {
            for (int up = 1; up < down; up++)
            //分子从1开始 
            {
                if (GCD(up, down) == 1) 
                {
                    ans.Add(up + "/" + down);
                }
            }
        }
        return ans;
    }

    public int GCD(int a, int b) 
    {
        if(a%b == 0)
        {
            return b;
        }
        else
        {
            return GCD(b,a%b);
        }
    }
    //最大公约数 辗转相除法
}

 

发表评论

您的电子邮箱地址不会被公开。