PTA基础编程题目集 7-24约分最简分式（C++语言实现）

摘要：本文是PTA编程题"约分最简分式"的题解，涵盖题目描述、输入输出格式及C++语言实现，展示使用辗转相除法求最大公约数进行分数约分的算法。

题目描述

分数可以表示为分子/分母的形式。编写一个程序，要求用户输入一个分数，然后将其约分为最简分式。最简分式是指分子和分母不具有可以约分的成分了。如6/12可以被约分为1/2。当分子大于分母时，不需要表达为整数又分数的形式，即11/8还是11/8；而当分子分母相等时，仍然表达为1/1的分数形式。

输入格式：

输入在一行中给出一个分数，分子和分母中间以斜杠/分隔，如：12/34表示34分之12。分子和分母都是正整数（不包含0，如果不清楚正整数的定义的话）。

提示：

对于C语言，在scanf的格式字符串中加入/，让scanf来处理这个斜杠。
对于Python语言，用a,b=map(int, input().split(‘/’))这样的代码来处理这个斜杠。

输出格式：

在一行中输出这个分数对应的最简分式，格式与输入的相同，即采用分子/分母的形式表示分数。如
5/6表示6分之5。

输入样例：

66/120

输出样例：

11/20

解题思路

核心问题分析：
将给定分数约分为最简分式，即分子和分母同时除以它们的最大公约数(GCD)。约分后分子与分母互质。

算法原理：
使用欧几里得算法（辗转相除法）求两个数的最大公约数。算法核心：gcd(a, b) = gcd(b, a mod b)，反复迭代直到余数为0，此时的除数即为最大公约数。然后分子分母同除以该GCD即得最简分式。

具体计算步骤：

1. 以"分子/分母"格式读取输入的两个整数
2. 调用gcd函数计算分子和分母的最大公约数
3. 简化分子 = 原分子 ÷ 最大公约数
4. 简化分母 = 原分母 ÷ 最大公约数
5. 按"分子/分母"格式输出结果

代码流程说明

1. gcd函数定义：使用辗转相除法循环计算最大公约数
   • 当b≠0时，保存b到temp，b=a%b，a=temp继续迭代
   • b=0时返回a即为最大公约数
2. 主函数输入：使用scanf(“%d/%d”, …)格式自动跳过斜杠读取分子分母
3. 计算最大公约数：调用gcd(numerator, denominator)
4. 约分计算：分子分母分别除以最大公约数
5. 格式化输出：按"分子/分母"格式输出最简分式

代码流程图

解题流程图

代码部分实现

#include<iostream>#include<cstdio>usingnamespacestd;// 使用辗转相除法求两个数的最大公约数// 算法原理：gcd(a, b) = gcd(b, a mod b)，直到余数为0，此时的除数即为最大公约数intgcd(inta,intb){while(b!=0){inttemp=b;// 保存当前的除数b=a%b;// 用当前除数除当前被除数，得到新的余数a=temp;// 将原除数作为下一轮的被除数}returna;// 当b为0时，a即为最大公约数}intmain(){intnumerator,denominator;// 以"分子/分母"的格式输入分数，scanf中的/会被自动跳过scanf("%d/%d",&numerator,&denominator);// 求出分子和分母的最大公约数intcommon_divisor=gcd(numerator,denominator);// 分子分母同时除以最大公约数，得到最简分式intsimplified_num=numerator/common_divisor;intsimplified_den=denominator/common_divisor;// 输出最简分式cout<<simplified_num<<"/"<<simplified_den<<endl;return0;}