Задача: Для заданных [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 |
Код на С++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <stdio.h> #include <math.h> using namespace std; double pow_b (double a, int n){ if (n==0) return 1; double result = 1; while (n>0) { if (n%2==0) { n/=2; a*=a; } else { n--; result*=a; } } return result; } int main () { double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность cin>>a>>p; double x=pow(a, 1/p); //подсчитываем значение double xn=a, x_prev; int i=0; while (fabs(x-xn) > eps){ //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона x_prev=xn; xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1))); i++; } cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран. return 0; } |
Код на Java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static double bPow (double a, double n){ if (n==0) return 1; double result = 1; while (n>0) { if (n%2==0) { n/=2; a*=a; } else { n--; result*=a; } } return result; } public static void main (String[] args) { Scanner sc = new Scanner (System.in); int Iterations = 0; double eps = sc.nextDouble(); double a = sc.nextDouble(); double p = sc.nextDouble(); double x = a; double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ; while (Math.abs(x_next - x) > eps) { x = x_next; x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) ); Iterations++; } System.out.println("Result: " + x_next + "; Iterations: " + Iterations); } } |
Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn, подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.
UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.
Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации:
- Когда степень чётна;
- Когда степень не чётна;
Ситуация 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
Related Images:
