百度&必应权4, 日IP8000. 查看详情
自助收录

使用暴力算法解决“x的平方根”问题

算法刷题2年前 (2023)更新 江南白衣
324 0 0
使用暴力算法解决“x的平方根”问题

题目:x的平方根
描述:题描述:在不使用 sqrt(x) 函数的情况下,得到 x的平方根的整数部分。
重点考察:二分法、牛顿迭代
思路:
若没有学过算法,普通人一般会优先考虑暴力算法,我们先用暴力算法试一试,下一篇文章再使用二分法牛顿迭代求解。
众所周知,x的平方根的的整数部分i一定会同时满足以下关系式:i的平方<=x,i+1的平方>x。我们使用for循环遍历1到x之间的数字,只要满足条件,即为我们要寻找的整数。

注意:如果输入的数字太大可能会导致超出int类型的最大值,可以把i定义为long类型。

上代码:

package od;

/**
 * x的平方根(暴力算法)
 * 问题描述:在不使用 sqrt(x) 函数的情况下,得到 x的平方根的整数部分。
 * 重点考察:二分法、牛顿迭代
 * 原文地址:https://www.codernav.com/2814.html
 * 更多算法详解:https://www.codernav.com
 */
public class OdTest15 {
    public static void main(String[] args) {
        int num = f(24);
        System.out.println(num);
    }

    /**
     * 分析:x的整数部分(i)一定存在以下关系式
     * i的平方 <= x 且 i+1的平方 > x
     */
    public static int f(int x) {
        for (int i = 1; i < x + 1; i++) {
            if (i * i <= x && (i + 1) * (i + 1) > x) {
                return i;
            }
        }

        return 1;
    }
}
© 版权声明

相关文章

暂无评论

暂无评论...