乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT乙级BasicLevelPractice 1034

问题分析

题设给定两个有理数, 要求输出这两个有理数的和、差、积、商。
如果只是这样, 则问题很简单, 但是题设要求输出的每个有理数必须是最简形式.

所以本题的一个重点是如何将有理数转为题设要求的有理数.

将有理数转为最简形式

1. 如果分母是0
   • 非法值. 题设规定这种情况输出Inf.
2. 如果分子是分母的倍数
   • 整数部分为 a / b
   • 分子为 0
   • 分母为 b (虽然这种情况分子分母都不输出, 但是分母为b可以用来与分母为0的情况进行区分)
3. 如果分子不是分母的倍数
   • 求分子分母的最小公倍数 max_factor
   • 化简分子分母: a = a / max_factor; b = b / max_factor;
   • 整数部分为 a / b
   • 分子为 a % b
   • 分母为 b

有理数的加减乘除

对于有理数 a1/b1, a2/b2,
两数之和 = (a1 * b2 + a2 * b1) / (b1 * b2)
两数之差 = (a1 * b2 - a2 * b1) / (b1 * b2)
两数之积 = (a1 * a2) / (b1 * b2)
两数之商 = (a1 * b2) / (b1 * a2)

完整描述步骤

1. 获取题设输入的有理数
2. 计算并存储两个有理数的最简形式
3. 计算并存储两个有理数的和、差、积、商
4. 计算并储存和、差、积、商的最简形式
5. 打印有理数和、差、积、商的表达式

伪代码描述

1. get input of two rational: a1, b1, a2, b2;
2. convert_to_most_precise_form(a1, b1, form1);
   convert_to_most_precise_form(a2, b2, form2);
3. calculate sum, difference, product, quotient;
   convert_to_most_precise_form(a1 * b2 + a2 * b1, b1 * b2, sum);
   convert_to_most_precise_form(a1 * b2 - a2 * b1, b1 * b2, difference);
   convert_to_most_precise_form(a1 * a2, b1 * b2, product);
   convert_to_most_precise_form(a1 * b2, b1 * a2, quotient);
4. print expression of sum, difference, product, quotient:
   print form1 + form2 = sum;
   print form1 - form2 = difference;
   print form1 * form2 = product;
   print form1 / form2 = quotient;

【题目的坑】
"题目保证正确的输出中没有超过整型范围的整数"说的是化简后的数值, 化简前的数值并没有保证不超过整型范围。
所以对于静态类型语言, 比如C/C++, 用int会在某个测试点出错, 需要把类型都换成long long

完整提交代码

/*
# 问题分析
题设给定两个有理数, 要求输出这两个有理数的和、差、积、商。
如果只是这样, 则问题很简单, 但是题设要求输出的每个有理数必须是最简形式.
所以本题的一个重点是如何将有理数转为题设要求的有理数.

# 将有理数转为最简形式
1. 如果分母是0
    - 非法值. 题设规定这种情况输出Inf.
2. 如果分子是分母的倍数
    - 整数部分为 a / b
    - 分子为 0
    - 分母为 b (虽然这种情况分子分母都不输出, 但是分母为b可以用来与分母为0的情况进行区分)
3. 如果分子不是分母的倍数
    - 求分子分母的最小公倍数 max_factor
    - 化简分子分母: a = a / max_factor; b = b / max_factor;
    - 整数部分为 a / b
    - 分子为 a % b
    - 分母为 b

# 有理数的加减乘除
对于有理数 a1/b1, a2/b2,
两数之和 = (a1 * b2 + a2 * b1) / (b1 * b2)
两数之差 = (a1 * b2 - a2 * b1) / (b1 * b2)
两数之积 = (a1 * a2) / (b1 * b2)
两数之商 = (a1 * b2) / (b1 * a2)

# 完整描述步骤
1. 获取题设输入的有理数
2. 计算并存储两个有理数的最简形式
3. 计算并存储两个有理数的和、差、积、商
4. 计算并储存和、差、积、商的最简形式
5. 打印有理数和、差、积、商的表达式

# 伪代码描述
1. get input of two rational: a1, b1, a2, b2;
2. convert_to_most_precise_form(a1, b1, form1);
    convert_to_most_precise_form(a2, b2, form2);
3. calculate sum, difference, product, quotient;
    convert_to_most_precise_form(a1 * b2 + a2 * b1, b1 * b2, sum);
    convert_to_most_precise_form(a1 * b2 - a2 * b1, b1 * b2, difference);
    convert_to_most_precise_form(a1 * a2, b1 * b2, product);
    convert_to_most_precise_form(a1 * b2, b1 * a2, quotient);
4. print expression of sum, difference, product, quotient:
    print form1 + form2 = sum;
    print form1 - form2 = difference;
    print form1 * form2 = product;
    print form1 / form2 = quotient;

【题目的坑】
"题目保证正确的输出中没有超过整型范围的整数"说的是化简后的数值, 化简前的数值并没有保证不超过整型范围。
所以对于静态类型语言, 比如C/C++, 用int会在某个测试点出错, 需要把类型都换成long long

*/

#include <stdio.h>

long long find_max_common_factor(long long a, long long b)
{
    return b == 0 ? a : find_max_common_factor(b, a % b);
}

void convert_to_most_precise_form(long long a, long long b, long long *result)
{
    /*
    功能: 将给定的有理数转为最简形式
    输入: a - 分子, b - 分母, result - 最简形式存储数组, 三元组存储
    描述:
        1. 检查并存储正负号
        2. 处理特殊情况: 分母为0 -> result中的3个元素都置为0
        3. 如果分子是分母的倍数 -> result = [a / b * sign, 0, b]
            否则: result = [a / b * sign, a % b, b]
                (如果a < b, 即result[0] == 0, 用result[1]表示正负号)
    */
    long long sign = 1;
    if (a < 0)
    {
        sign = -sign;
        a = -a;
    }
    if (b < 0)
    {
        sign = -sign;
        b = -b;
    }

    if (b == 0)
    {
        result[0], result[1], result[2] = 0, 0, 0;
        return;
    }

    if (a % b == 0)
    {
        result[0] = a / b * sign;
        result[1] = 0;
        result[2] = b;
        return;
    }

    long long max_factor = find_max_common_factor(a, b);
    a = a / max_factor;
    b = b / max_factor;
    result[0] = a / b * sign;
    result[1] = a % b;
    result[2] = b;
    if (result[0] == 0)
    {
        result[1] *= sign;
    }
}

void print_item(long long *item)
{
    if (item[0] < 0 || item[1] < 0)
    {
        printf("(");
    }
    if (item[0] != 0)
    {
        printf("%d", item[0]);
    }
    if (item[1] != 0 || item[0] == 0)
    {
        if (item[0] != 0)
            printf(" ");

        printf("%d", item[1]);
    }
    if (item[1] != 0)
    {
        printf("/%d", item[2]);
    }
    if (item[0] < 0 || item[1] < 0)
    {
        printf(")");
    }
}

void print_express(long long *a, long long *b, long long *c, char operator)
{
    print_item(a);
    printf(" %c ", operator);
    print_item(b);
    printf(" = ");
    if (operator== '/' && c[2] == 0)
    {
        printf("Inf");
    }
    else
    {
        print_item(c);
    }
    printf("\n");
}

long long main()
{
    long long a1, b1;
    long long a2, b2;
    scanf("%lld/%lld %lld/%lld", &a1, &b1, &a2, &b2);
    long long form1[3] = {0};
    long long form2[3] = {0};
    convert_to_most_precise_form(a1, b1, form1);
    convert_to_most_precise_form(a2, b2, form2);

    long long sum[3], difference[3], product[3], quotient[3];
    convert_to_most_precise_form(a1 * b2 + a2 * b1, b1 * b2, sum);
    convert_to_most_precise_form(a1 * b2 - a2 * b1, b1 * b2, difference);
    convert_to_most_precise_form(a1 * a2, b1 * b2, product);
    convert_to_most_precise_form(a1 * b2, b1 * a2, quotient);

    print_express(form1, form2, sum, '+');
    print_express(form1, form2, difference, '-');
    print_express(form1, form2, product, '*');
    print_express(form1, form2, quotient, '/');
    return 0;
}