Ю3.20

Задача: Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]x = \sqrt[p]{a}[/latex] по рекуррентному соотношению Ньютона: 

[latex]x_{n+1}=\frac{1}{p}*\left[(p-1)x_{n}+\frac{a}{x_{n}^{p-1}}\right][/latex]  [latex]x_{0} = a[/latex]

Сколько итераций надо выполнить, чтобы для достижения заданной погрешности [latex]\varepsilon[/latex] выполнялось соотношение:

[latex]\left|x_{n+1}-x_{n}\leq\varepsilon\right|[/latex]?

Тесты:

[latex]a[/latex] [latex]p[/latex] Значение корня [latex]x[/latex] Значение корня [latex]x[/latex], подсчитанного с помощью соотношения Количество итераций
57 5  2.24479 2.24479  18
16 2 4 4 5
230 2  15.1658  15.1658 7
9 3  2.08008 2.08008  7

Код на С++: 

Код на Java:

 

 

Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn,  подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.

UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.

Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации:

  1. Когда степень чётна;
  2. Когда степень не чётна;

Ситуация 1 : Проведя несложный анализ  можно заметить, что [latex]{a}^{p}[/latex] можно представить в виде

[latex](a^{\frac{p}{2}})^{2}[/latex].

Ситуация 2: В этой ситуации необходимо перейти в степень [latex]p-1[/latex], которая является чётной.

[latex]a^{p}=a^{p-1} * a[/latex]

И в результате получим алгоритм, который работает за [latex]O(\log n)[/latex].

 

Проверить правильность работы программы можно здесь (UPD):  http://ideone.com/VBLGKO

 

Марченко Філіп Олександрович
Марченко Філіп Олександрович

Latest posts by Марченко Філіп Олександрович (see all)

4 thoughts on “Ю3.20

  1. То, что могло сойти для первокурсника на втором уже не допустимо.
    Вы в программе на С++ и Javа используете функцию возведения в степень, которая может решить исходную задачу без всякого рекуррентного соотношения.
    Т.е. нужно решить обе задачи, используя только четыре арифметические задачи.