G2029 [GESP202609 二级] 直角三角形 题解

知识点：递推、浮点运算、终止条件。

解题思路

从两条已知边a、b开始，以sqrt(aa+bb)生成下一条边，再把相邻两项向前推进，找到首个严格大于k的项号。

为什么正确

递推和编号始终对应题目构造过程，首次越界时即得到最早满足条件的编号。

易错点

条件是严格大于；第一、第二项要先单独判断；计算使用double。

复杂度

设生成K项，时间O(K)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double a,b,k;
    cin>>a>>b>>k;
    if(a>k) {
        cout<<1;
        return 0;
    }
    if(b>k) {
        cout<<2;
        return 0;
    }
    int i=2;
    while(b<=k) {
        double c=sqrt(a*a+b*b);
        a=b;
        b=c;
        i++;
    }
    cout<<i;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。