Задача: Для заданных [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
Зачтено, но р очевидно предполагается целым числом.
Предлагаю за дополнительные 5 баллов избавиться от функции pow() в 15-й строке, заменив её на написанную Вами функцию быстрого возведения в целую степень.
Принято.
— «Стандартные» функции в latex кодируют так \sin, \cos, \log и т.п.
То, что могло сойти для первокурсника на втором уже не допустимо.
Вы в программе на С++ и Javа используете функцию возведения в степень, которая может решить исходную задачу без всякого рекуррентного соотношения.
Т.е. нужно решить обе задачи, используя только четыре арифметические задачи.
Зачтено.
Вот более лаконичный вариант для возведение в натуральную степень.
Но Ваш должен работать быстрее.