我要招人

去企业版

首页 > 试题广场 >

连分数

[编程题]连分数

热度指数：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

算法知识视频讲解

WZ111G

其实本质就是个辗转相除：

#include<bits/stdc++.h>

#define endl '\n'

#define all(qwq) qwq.begin(), qwq.end()

#define rall(qwq) qwq.rbegin(), qwq.rend()

using namespace std;

using ll = long long;

using pii = pair<int, int>;

using pll = pair<ll, ll>;

using uii = unordered_map<int, int>;

const int MOD = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const ll INF2 = 0x3f3f3f3f3f3f3f3f;

void solve() {

ll p,q;

cin>>p>>q;

ll cnt=0;

auto f=[&](auto&& f,ll u,ll v)->void{

ll a=u/v;

ll b=u%v;

if(b!=0){

if(v%b!=0){

cout<<a<<"+1/{";

cnt++;

f(f,v,b);

}

else{

cout<<a<<"+1/";

f(f,v,b);

}

else{

cout<<a;

for(ll i=0;i<cnt;i++) cout<<"}";

}

};

cout<<p<<"/"<<q<<" = ";

f(f,p,q);

cout<<endl;

}

int main() {

ios::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

int T;

cin >> T;

while (T--) solve();

return 0;

}

发表于 2026-03-08 22:39:32 回复(0)

pandaC222

我们按照题意模拟即可：

#include<bits/stdc++.h>
using namespace std;
void solve(){
    long long p,q;
    cin>>p>>q;
    cout<<p<<"/"<<q<<" = ";
    if(p%q==0){
        cout<<p/q<<"\n";
        return;
    }
    vector<long long> a;
    while(q){
        a.push_back(p/q);
        long long r=p%q;
        p=q;
        q=r;
    }
    cout<<a[0];
    for(int i=1;i<a.size()-1;i++){
        cout<<"+1/{";
        cout<<a[i];
    }
    cout<<"+1/"<<a[a.size()-1];
    for(int i=1;i<a.size()-1;i++) cout<<"}";
    cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin>>T;
    while(T--) solve();
}

发表于 2026-03-08 09:36:50 回复(0)

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)

牛客203596504号

这道题主要考的是递归：
我们假设p/q=x+1/y，那么显然x就是商(p/q)，如果整除就完结了，1/y就是余数(p%q)除以q。
接下来我们按照相同方式把y展开，y是1/y的倒数，所以它是q除以p%q
整个过程就是个辗转相除，除到它俩的公约数就必然整除，所以一定是有限的。
题目到此已解决，但是要注意输出格式的要求：
表达式最外层是没有花括号的，最后整除输出的那个整数也是没有花括号的。

发表于 2026-03-08 02:44:38 回复(0)

提交观点

问题信息

难度：

4条回答 3收藏 18浏览

连分数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题