Luftmensch

用户名：8965

访问量：5677

签　名：

等　　级
排　　名	1513
经　　验	2826
参赛次数	0
文章发表	53
年　　龄	18
在职情况	学生
学　　校	南京工程学院
专　　业	软件工程

　　自我简介：

76_105_89_105_110_103

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1504: 蓝桥杯算法提高VIP-勾股数（o(n2)的写法）

　　作者: Luftmensch　　　　发表时间：2022-02-18 19:04:43 浏览：92　|　评论：0　

原题链接：蓝桥杯算法提高VIP-勾股数

:tw-1f4d7:**解题思路：**
进一步精确a,b,c的范围，可与缩短时间
**a<333,   因为a的值最小，三个数的平均值是333**，如果a大于了333，三个数之和也会大于1000；
**b<500，因为b小于c,如果b大于了500，那么c也必须大于500**，三个数之和显然会大于1000；
**c<a+b,因为三角形两边之和大于第三边**
经过范围的改进时间也大大缩小，可见下图
![](/image_editor_upload/20220218064710_28282.jpg)
 :tw-274e:具体代码：（是对的，但不建议）
```c
#include<stdio.h>
int  main()
{   
    for (int i = 3; i < 333; i++)
    {
        for (int j = i; j < 500; j++)
        {
            for (int k = j; k < i + j; k++)
            {
                if ((i + j + k <= 1000) && (i * i + j * j == k * k))
                    printf("%d %d %d\n", i, j, k);
            }
        }           
    }
       return 0;
}

```
但是三重循环的时间复杂度O（n3）,如果能降到O（n2），时间会再次降低
![](/image_editor_upload/20220218070048_49597.jpg)
具体方法：求ab的平方和，判断其根号是否为整数
:tw-2705:具体代码：
```c
#include<stdio.h>
#include<math.h>
int main()
{
    for (int i = 3; i < 333; i++)
    {
        for (int j = i; j < 500; j++)
        {
            if (sqrt(i * i + j * j) == (int)sqrt(i * i + j * j))
            {
               int k = sqrt(i * i + j * j);
                if (i+j+k<=1000)              
                    printf("%d %d %d\n", i, j, k);             
            }
        }
    }
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Luftmensch

TA的其他文章

你可能喜欢

C语言考试练习题_排列（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1504: 蓝桥杯算法提高VIP-勾股数（o(n2)的写法）

评论区

精彩推荐

点我有惊喜！你懂得！

本人酷爱递归实现很多问题，这里也是

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

P1000 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

马拦过河卒（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

Luftmensch

TA的其他文章

你可能喜欢

C语言考试练习题_排列 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1504: 蓝桥杯算法提高VIP-勾股数（o(n2)的写法）

评论区

精彩推荐

点我有惊喜！你懂得！

本人酷爱递归实现很多问题，这里也是

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

P1000 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

马拦过河卒 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言考试练习题_排列（C语言代码）

　　评论区

马拦过河卒（C语言代码）

C语言训练-斐波纳契数列（C语言代码）