连分数

[编程题]连分数

热度指数：1035 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个分数可以写成如下连分数的形式：

$\frac{P}{Q}=a + \frac{1}{b+\frac{1}{c+\frac{1}{d+...}}}$

现在给你一个分数，你能否将它写成连分数。

输入描述:

首行一个正整数 ，代表测试数据的组数

接下来  行每行给出两个正整数 

保证输入的分数都可以写成有穷连分数的形式

输出描述:

每组测试数据输出一行，格式见样例

示例1

输入

输出

103/24 = 4+1/{3+1/{2+1/3}}
21/73 = 0+1/{3+1/{2+1/10}}
4/2 = 2

算法知识视频讲解

Python3

卡卡喵

import sys
for line in sys.stdin:
    data = line.split()
    break

import sys
for line in sys.stdin:
    data = line.split()
    a = int(data[0])
    b = int(data[1])

    def para_in_list(a,b):
        res = []
        if a % b == 0:
            res.append(a // b)
            return res
        while a != 1&nbs***bsp;b != 1:
            if b == 0:
                break
            res.append(a // b)
            a, b = b, (a%b)
        return res

    para = para_in_list(a,b)
    temp = ''
    if len(para) == 0:
        temp = ''
    else:
        for i in range(-1,-len(para)-1,-1):
            if -i == 1:
                temp = str(para[i])
            if -i == 2:
                temp = str(para[i]) + '+1/' + temp
            if -i >= 3:
                temp = str(para[i]) + '+1/{'+ temp + '}'
    print(f'{int(data[0])}/{int(data[1])} = {temp}')

发表于 2026-03-08 18:28:51 回复(0)