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,bmap(int, input().split(‘/’))这样的代码来处理这个斜杠。输出格式在一行中输出这个分数对应的最简分式格式与输入的相同即采用分子/分母的形式表示分数。如5/6表示6分之5。输入样例66/120输出样例11/20解题思路核心问题分析将给定分数约分为最简分式即分子和分母同时除以它们的最大公约数(GCD)。约分后分子与分母互质。算法原理使用欧几里得算法辗转相除法求两个数的最大公约数。算法核心gcd(a, b) gcd(b, a mod b)反复迭代直到余数为0此时的除数即为最大公约数。然后分子分母同除以该GCD即得最简分式。具体计算步骤以分子/分母格式读取输入的两个整数调用gcd函数计算分子和分母的最大公约数简化分子 原分子 ÷ 最大公约数简化分母 原分母 ÷ 最大公约数按分子/分母格式输出结果代码流程说明gcd函数定义使用辗转相除法循环计算最大公约数当b≠0时保存b到tempba%batemp继续迭代b0时返回a即为最大公约数主函数输入使用scanf(“%d/%d”, …)格式自动跳过斜杠读取分子分母计算最大公约数调用gcd(numerator, denominator)约分计算分子分母分别除以最大公约数格式化输出按分子/分母格式输出最简分式代码流程图是否开始定义gcd函数参数a和bb不等于0?辗转相除更新a和b返回a主函数输入分子分母调用gcd求最大公约数分子除以最大公约数分母除以最大公约数输出最简分数结束解题流程图输入分数形式的分子分母提取分子a和分母b调用辗转相除法求最大公约数当b不等于0时计算余数ra更新为bb更新为rb为0时a即为GCD新分子等于原分子除以GCD新分母等于原分母除以GCD输出最简分数形式代码部分实现#includeiostream#includecstdiousingnamespacestd;// 使用辗转相除法求两个数的最大公约数// 算法原理gcd(a, b) gcd(b, a mod b)直到余数为0此时的除数即为最大公约数intgcd(inta,intb){while(b!0){inttempb;// 保存当前的除数ba%b;// 用当前除数除当前被除数得到新的余数atemp;// 将原除数作为下一轮的被除数}returna;// 当b为0时a即为最大公约数}intmain(){intnumerator,denominator;// 以分子/分母的格式输入分数scanf中的/会被自动跳过scanf(%d/%d,numerator,denominator);// 求出分子和分母的最大公约数intcommon_divisorgcd(numerator,denominator);// 分子分母同时除以最大公约数得到最简分式intsimplified_numnumerator/common_divisor;intsimplified_dendenominator/common_divisor;// 输出最简分式coutsimplified_num/simplified_denendl;return0;}