题目描述给定一个有理数分子和分母均为整数分母为正将其展开为连分数形式。连分数定义为[b0;b1,b2,…,bn]b01b11b2⋯1bn [b_0; b_1, b_2, \ldots, b_n] b_0 \cfrac{1}{b_1 \cfrac{1}{b_2 \cdots \cfrac{1}{b_n}}}[b0​;b1​,b2​,…,bn​]b0​b1​b2​⋯bn​1​1​1​其中b0b_0b0​为整数bkb_kbk​k0k 0k0为正整数且为了唯一性要求bn1b_n 1bn​1当n0n 0n0时。输入包含若干对整数分子、分母对每个有理数输出其对应的连分数展开。输入格式输入包含若干行每行两个整数aaa和bbb分别表示分子和分母。输入直至文件结束。输出格式对于每个有理数输出一行格式为[b0;b1,b2,...,bn]其中各项为连分数系数。若分子为000则b00b_0 0b0​0且后续无项。样例输入43 19 1 2样例输出[2;3,1,4] [0;2]题目分析连分数展开可通过欧几里得算法实现。对于有理数a/ba/ba/bb0b 0b0有ab⌊a/b⌋a mod bb \frac{a}{b} \lfloor a/b \rfloor \frac{a \bmod b}{b}ba​⌊a/b⌋bamodb​令b0⌊a/b⌋b_0 \lfloor a/b \rfloorb0​⌊a/b⌋余数ra mod br a \bmod bramodb。若r0r 0r0则展开结束。否则将br\frac{b}{r}rb​继续展开得到后续系数。这个过程等同于反复进行带余除法直到余数为000。该算法自然产生满足bn1b_n 1bn​1的唯一展开因为最后一个非零余数对应的商必定大于111当n0n 0n0时。若分子为000则b00b_0 0b0​0且展开结束。解题思路采用循环实现连分数展开步骤确定如下步骤1\texttt{1}1. 读入分子aaa和分母bbb。步骤2\texttt{2}2. 输出左括号[然后输出b0a/bb_0 a / bb0​a/b整数除法。步骤3\texttt{3}3. 令aa mod ba a \bmod baamodb。若a0a 0a0则直接输出右括号]并换行结束该有理数的处理。步骤4\texttt{4}4. 否则输出分号;然后进入循环。在循环中每次交换aaa和bbb输出a/ba / ba/b此时aaa为原分母bbb为原余数然后更新aa mod ba a \bmod baamodb。若a0a 0a0则退出循环否则输出逗号,并继续循环。步骤5\texttt{5}5. 循环结束后输出右括号]换行。该算法时间复杂度和欧几里得算法一致为O(log⁡min⁡(a,b))O(\log \min(a,b))O(logmin(a,b))空间复杂度O(1)O(1)O(1)。代码实现// Continued Fractions// UVa ID: 834// Verdict: Accepted// Submission Date: 2016-12-02// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intnumerator,denominator;while(cinnumeratordenominator){cout[numerator/denominator;numerator%denominator;boolprintCommafalse;while(numerator0){if(printComma)cout,;else{cout;;printCommatrue;}swap(numerator,denominator);coutnumerator/denominator;numerator%denominator;}cout]\n;}return0;}总结本题利用欧几里得算法将有理数展开为连分数输出的系数序列自动满足唯一性条件bn1b_n 1bn​1。输出格式固定第一项为整数部分后跟分号和逗号分隔的后续项。算法直接在欧几里得过程中输出商无需额外处理特殊情况。该解法简洁且完全确定适用于任意有理数。