UVa 834 Continued Fractions-北京尧图网络

题目描述给定一个有理数分子和分母均为整数分母为正将其展开为连分数形式。连分数定义为[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]b0b1b2⋯bn111其中b0b_0b0为整数bkb_kbkk0k 0k0为正整数且为了唯一性要求bn1b_n 1bn1当n0n 0n0时。输入包含若干对整数分子、分母对每个有理数输出其对应的连分数展开。输入格式输入包含若干行每行两个整数aaa和bbb分别表示分子和分母。输入直至文件结束。输出格式对于每个有理数输出一行格式为[b0;b1,b2,...,bn]其中各项为连分数系数。若分子为000则b00b_0 0b00且后续无项。样例输入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 1bn1的唯一展开因为最后一个非零余数对应的商必定大于111当n0n 0n0时。若分子为000则b00b_0 0b00且展开结束。解题思路采用循环实现连分数展开步骤确定如下步骤1\texttt{1}1. 读入分子aaa和分母bbb。步骤2\texttt{2}2. 输出左括号[然后输出b0a/bb_0 a / bb0a/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 1bn1。输出格式固定第一项为整数部分后跟分号和逗号分隔的后续项。算法直接在欧几里得过程中输出商无需额外处理特殊情况。该解法简洁且完全确定适用于任意有理数。

UVa 834 Continued Fractions

相关推荐

构建 Coding Agent 的飞轮：Feedback Loop、Benchmark、Agent Engineers

TIA博途WinCC IO域确认功能实现：防误操作实战指南

Dota2 TI小组赛瑞士轮解析：VG让一追二赢下关键战，XM滚滚游龙背后的版本逻辑

更多资讯

电工证微信里面怎么查在哪考

南安电工证报名官方报名入口在哪里找？工地太忙根本没时间复习考试

南安电工证报名多少钱？外省证能转过来吗？

水电工证考试科目电子证书查询

佛山年审电工证查询别被坑！手把手教你查电子证书流程

诸城特种作业操作证过期了不知道怎么复审延期？上岗必备全流程拆解

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？