Цикл насилия мертв, итерация Ньютона - король

задняя часть
Цикл насилия мертв, итерация Ньютона - король

Здравствуйте, меня зовут Сяо Хуанг, я люблю программировать, инженер-разработчик Java в компании-единороге. Спасибо за возможность встретить в огромном море людей, Как говорится: когда ваших талантов и способностей недостаточно для осуществления вашей мечты, пожалуйста, успокойтесь и учитесь. Я надеюсь, что вы, отличные специалисты, сможете учиться со мной, усердно работать вместе и воплотить в жизнь свои собственные мечты.

Введение

Сегодня в ежедневном вопросе о силовой пряжке есть заголовок:

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

Знаменитый квадратный корень, легендарный итерационный метод Ньютона, давайте посмотрим, как он реализован в этой статье!

2. Итерационный метод Ньютона

Итерационный метод Ньютона, также известный как метод Ньютона-Рафсона, был на самом деле независимо предложен Ньютоном и Рафсоном (еще одним парнем, которого скрывало имя Ньютона).

Идея, предложенная методом Ньютона-Рафсона, заключается в следующем.Использование касательной - это линейность кривойприблизиться к этой идее.

Ньютон и Рафсон думали, как проста тангенс, как легко его изучать, поскольку тангенс можно приблизить к кривой, я могу непосредственно изучать корень тангенса.

как показано на рисунке:在这里插入图片描述

Для корней вышеуказанных функций мы знаем:x = 0

Как рассчитать с помощью метода итераций Ньютона?

  • F(x) = x * x
  • F'(x) = 2 * x

在这里插入图片描述

Во-первых, итерационный метод Ньютона найдет такую ​​точку, какx0,отx0Проведите прямую к кривой, пересекающейся в точкеA, сделай что-нибудьAКасательная пересекается в точкеx1

В этом случае мы можем получить три балла:х1, х0, А

Пусть координаты точки А(х0, х0 * х0), координаты точки x1 равны(х1, 0)

По координатам точки А и точки х1 можно найти наклон прямой:K = (x0 * x0) / (x0 - x1)

Упрощено, чтобы получить:

  • x0 - x1 = ( x0 * x0) / K
  • x0 - x1 = F(x0) / F'(x0)
  • x0 - x1 = x0 / 2
  • x1 = x0 / 2

Проделаем ту же операцию выше с точками x1 и получим:

  • x2 = x1 / 2

Мы проделаем вышеуказанные операции без ограничений, и в итоге мы получим формулу:Xn+1 = Xn / 2

Когда нет итераций, нашxзначение будет стремиться к 0

3. Квадратный корень

Как мы сказали выше, дляF(x) = x * x, окончательный результат:Xn+1 = Xn / 2

Мы думаем, для квадратного корня:x * x = num

Можете ли вы преобразовать его во что-то вроде:F(x) = x * x - num,F'(x) = 2 * x, найти пересечение этой функции

Используя метод итерации Ньютона, о котором мы упоминали выше, мы можем узнать, что:在这里插入图片描述ПредполагатьF1указать на(x0，x0 * x0 - num),x1указать на（x1，0）

но:

  • K = (x0 * x0 - num) / (x0 - x1)
  • x0 - x1 = (x0 * x0 - num) / K
  • x0 - x1 = F(x0) / F'(x0)
  • x0 - x1 = x0 / 2 - num / (2 * x0)
  • x1 = x0 / 2 + num / (2 * x0)

Повторите две точки x1 и x2 таким же образом, чтобы получить:x2 = x1 / 2 + num / (2 * x1)

получить формулу:Xn+1 = Xn / 2 + num / 2 * Xn

Проще говоря, выберите начальное значение x, выполните бесконечную итерацию и, наконец, найдите его квадратный корень.

F(x) = x * x - numСвойства выпуклой функции, окончательный результат должен быть:x = sqrt(num)

наш первыйxможно принять непосредственно заnum,потому чтоnum >= sqrt(num)

Вообще говоря, можно судить, меньше ли разница между результатами двух соседних итераций очень малого неотрицательного числа, которое обычно можно принять как1e-6или1e-7

В-четвертых, реализация кода

	public boolean isPerfectSquare(int num) {
        if(num == 1){
            return true;
        }
        double ans = num;
        double dir = num;
        while(ans * ans - dir >= 1e-6){
            ans = ans / 2 + dir / (2 * ans);
        }
        int x = (int)ans;
        return x * x == num;
    }

在这里插入图片描述

V. Резюме

Проще говоря, итерационный метод Ньютона постепенно приближается к определенному целевому значению посредством непрерывной итерации.

Тема первая:367. Эффективные идеальные квадраты

Заинтересованные друзья могут это сделать.квадратный кореньВопрос, который больше всего хочет услышать интервьюер:牛顿迭代法, наотмашь, чтобы дать ему волну процесса рассуждения, и прямо увлечь интервьюера.

Для тех, кто интересуется исходным кодом, вы можете следить爱敲代码的小黄Публичный аккаунт, ответ:Исходный код алгоритмаИсходный код алгоритма можно получить

Содержание этого выпуска находится здесь, а в следующем выпуске будетМинимальное остовное дерево (Prim, Kruskal)алгоритм.

Я Java-разработчик в компании-единороге. Надеюсь на ваше внимание. Если у вас есть какие-либо вопросы, вы можете оставить сообщение или личное сообщение и добавить меня в WeChat. До встречи в следующем выпуске!

Категории