【数据结构与算法】学习笔记-《算法笔记》-17【分数的表示、化简和输出】

分数的表示

//分数的表示 struct Fraction { int up, down;//分子与分母 };

分数的化简

分数的化简应该满足三项原则：

当分母为负数时，分子与分母同时取反；当分数为零时（分子为零时），分母必为1；分子分母没有除了1以外的公约数（同除最大公约数）。 //求最大公约数 int gcd(int a, int b) { return !b ? a : gcd(b, a%b); } //分数的化简 Fraction reduction(Fraction result) { //原则一 if (result.down < 0) { result.down = -result.down; result.up = -result.up; } //原则二 if (result.up == 0) result.down = 1; //原则三 else { int d = gcd(abs(result.up), abs(result.down)); //这里一定要记得取绝对值 result.down /= d; result.up /= d; } return result; }

分数的输出

有以下注意点：

输出分数前，要对其进行化简；如果分母为1，说明该分数是整数，一般直接输出分子；如果分子的绝对值大于分母，说明是假分数，要以带分数的形式输出；以上均不满足是说明分数是真分数，按原样输出即可。 //分数的输出 void showFraction(Fraction r) { //原则一：先进行化简 r = reduction(r); //原则二：如果是整数 if (r.down == 1) printf("%d", r.up); //原则三：如果是假分数 if (abs(r.up) > abs(r.down)) { int a = r.up / r.down; r.up = abs(r.up) % r.down;//注意这里的绝对值 printf("%d %d/%d\n", a, r.up, r.down); } }

注意：由于分数的乘法和出发过程中可能使分子或分母超过int型表示范围，因此一般情况下，分子和分母应到使用long long型存储。