zhangjinxuan 发表于 2022-9-21 19:15:36

【C++板块提升计划】求平方根的6种方法 C++

本帖最后由 zhangjinxuan 于 2023-1-9 14:26 编辑

一：枚举法
思路：设置变量i = 0，如果 i * i > n ,退出循环，否则i++
时间复杂度：O(n ^ 0.5)
代码：
int solve(int number) {
        int i = 0;
        for (; i * i < number; ++i);
        if (i * i == number) //完全平方数特殊处理
                return i;
        return i - 1;
}
缺点：只支持整数，时间复杂度高，不太推荐
优点：适合初学者

二：二分法
思路：使用二分答案求出平方根
时间复杂度： O(log2 n)
代码：
int solve1(int number) {
        int l = 1, r = number;
        while (l + 1 != r) {
                int mid = (l + r) / 2;
                if (mid * mid <= number)       
                        l = mid;
                else
                        r = mid;
        }
        return l;
}
缺点：只支持整数，比较难懂
优点：时间复杂度低，较推荐

三：小数二分法
思路：在二分答案上做一些改动，使支持小数
时间复杂度：O(log2 n)
double solve2(double number) {
        double l = 1, r = number;
        while (fabs(l * l - number) > 0.00001) {
                double mid = (l + r) / 2;
                if (mid * mid <= number)       
                        l = mid;
                else
                        r = mid;
        }
        return l;
}
缺点：虽说是O(log2 n),但某些较大数据可能超时
优点：支持小数，精度较高，较推荐

四：牛顿迭代算法
思路：使用牛顿迭代算法，求出平方根，但因为是大学学的算法，这里不赘述
时间复杂度：O(1)
double solve3(double number) {
        double x = 1;
        for (int i = 1; i <= 30; ++i) //可以自定义，最好在20以上，数字越高精度越高
                x = (x + number / x) / 2;
        return x;
}
缺点：太大数据精度可能丢失，理解难
优点：代码简单，精度较高，时间复杂度低，个人推荐

五：牛顿迭代算法+二分（借鉴于CSP-J2022初赛）
思路：牛顿迭代算法加二分，可以减少迭代时循环次数，时间复杂度略显提升
时间复杂度：O(log2 n)
代码：
int __sqrt1(int number) {
        int l = 1, r = number;
        while (l + 1 != r) {
                int mid = (l + r) / 2;
                if (mid * mid <= number)       
                        l = mid;
                else
                        r = mid;
        }
        return l;
}
double solve4(double number) {
        double x = __sqrt1(number);
        for (int i = 1; i <= 10; ++i) //有二分的辅助，循环次数可以适当减少，最好10以上
                x = (x + number / x) / 2;
        return x;
}
缺点：代码长，有时候聪明反被聪明误，效率并没有提升，而且更不好理解了，不太推荐
优点：精度高，效率还行，

六：cmath
思路：cmath库 sqrt(n) 一行解决（注，需要导入cmath)
代码：
sqrt(n);
优点：代码短,效率高，懒人福音
缺点：真挑不出毛病...

zhangjinxuan 发表于 2022-9-21 19:43:32

怎么还这么冷清...

hveagle 发表于 2022-9-21 19:52:10

冷清
NO NO NO
热情

hveagle 发表于 2022-9-21 19:54:13

本帖最后由 hveagle 于 2022-9-21 19:55 编辑

   冰
火火火

等于

   水

柿子饼同学 发表于 2022-9-21 20:10:02

平方根我只会 sqrt , 当然也只用 sqrt {:10_256:}
顺便说一句 , 这是 math 库的 , 不是 stl 哦

柿子饼同学 发表于 2022-9-21 20:10:46

哈哈哈哈今年初赛就用的二分和牛顿迭代

zhangjinxuan 发表于 2022-9-21 20:53:05

本帖最后由 zhangjinxuan 于 2022-9-21 21:09 编辑

柿子饼同学 发表于 2022-9-21 20:10
哈哈哈哈今年初赛就用的二分和牛顿迭代

雀食

呵呵，要不标上转载？

但是代码的确是自己写的哦

zhangjinxuan 发表于 2022-9-21 20:55:05

hveagle 发表于 2022-9-21 19:52
冷清
NO NO NO
热情

谢谢^_^

tommyyu 发表于 2022-9-21 21:01:31

柿子饼同学 发表于 2022-9-21 20:10
哈哈哈哈今年初赛就用的二分和牛顿迭代

确实，我当时想了好久{:10_266:}

zhangjinxuan 发表于 2022-9-21 21:07:08

tommyyu 发表于 2022-9-21 21:01
确实，我当时想了好久

哇塞，你也普及组?

其实我那道题，只扣了1.5

tommyyu 发表于 2022-9-21 21:07:46

zhangjinxuan 发表于 2022-9-21 21:07
哇塞，你也普及组?

普及和提高都报了

zhangjinxuan 发表于 2022-9-21 21:08:18

本帖最后由 zhangjinxuan 于 2022-9-21 21:11 编辑

tommyyu 发表于 2022-9-21 21:07
普及和提高都报了

牛人{:10_275:}

柿子饼同学 发表于 2022-9-21 21:20:23

zhangjinxuan 发表于 2022-9-21 20:53
雀食

呵呵，要不标上转载？


这当然没事

柿子饼同学 发表于 2022-9-21 21:20:54

zhangjinxuan 发表于 2022-9-21 21:07
哇塞，你也普及组?

其实我那道题，只扣了1.5

哈哈我没扣

zhangjinxuan 发表于 2022-9-21 21:22:28

柿子饼同学 发表于 2022-9-21 21:20
哈哈我没扣

真是人外有人，天外有天，佩服佩服~

柿子饼同学 发表于 2022-9-21 21:47:09

zhangjinxuan 发表于 2022-9-21 21:08
牛人

不不不 , 你也很厉害
复赛冲啊

高山 发表于 2022-9-21 21:55:15

做的不错哦

zhangjinxuan 发表于 2022-9-22 07:19:27

高山 发表于 2022-9-21 21:55
做的不错哦

感谢滋磁
页: [1]
查看完整版本: 【C++板块提升计划】求平方根的6种方法 C++