Задача № 26. Решить квадратное уравнение заданного вида с параметром
Формулировка. Дано натуральное число n. Вывести на экран решения всех квадратных уравнений вида x2 + 2 ax – 3 = 0 для всех a от 1 до n.
Решение. Эта задача очень похожа на задачу 12. В принципе, ее можно было бы решить, используя код этой задачи, взяв первый и последний коэффициенты равными 1 и –3 соответственно и запустив цикл по всем a от 1 до n, умножив a на 2 во всех формулах.
Однако исследуем это уравнение математически и попытаемся оптимизировать решение:
1) Найдем дискриминант уравнения: 
Очевидно, что найденная величина неотрицательна, и, если быть точнее, то при a от 1 до n она всегда принимает значение не меньше 16 (так как при a = 1 она равна 4 * (1 + 3) = 4 * 4 = 16). Следовательно, наше уравнение всегда имеет решение, причем их два.
2) Найдем формулы корней уравнения:
Итак, формулы корней уравнения получены, и теперь только осталось вывести в цикле значения корней для всех a от 1 до n, не забыв сделать вывод форматированным (так как решения будут вещественными).
Код:
| 1. program MyQuadraticEquation; 2. 3. var 4. a, n: word; 5. x1, x2: real; 6. 7. begin 8. readln(n); 9. for a := 1 to n do begin 10. x1 := sqrt(a * a + 3) - a; 11. x2 := -a - sqrt(a * a + 3); 12. writeln('a = ', a, ', x1 = ', x1:4:2, ', x2 = ', x2:4:2) 13. end 14. end. |
Задача № 27. Вычислить значение многочлена в точке
Формулировка. Дано натуральное число n, вещественное число x и набор вещественных чисел an, an-1, ..., a0. Вычислить значение многочлена n-ной степени с коэффициентами an, an-1, ..., a0 от одной переменной в точке x.
|
|
|
Примечание: многочленом n-ной степени от одной переменной x называется выражение вида anxn + an-1 xn-1 + ... + a1 x + a0, где an, an-1, ..., a0 – коэффициенты.
Решение. Собственно, в этой задаче требуется возведение переменной x (точнее, конкретного ее значения) в некоторую степень n – 1 раз, а также n операций умножения и n операций сложения. В принципе, для полноценного решения она не требует одновременного знания более чем одного коэффициента, так как мы можем в цикле ввести коэффициент an в переменную a, умножить его на xn и прибавить полученное число к переменной результата res (которой перед входом в цикл должно быть присвоено значение 0) и повторить этот шаг для всех коэффициентов. Тогда количество операций: (1 + 2 + ... + n + 2n), что примерно соответствует асимптотической сложности O( n2).
Не занимаясь реализацией этого алгоритма, давайте оптимизируем его. Например, пусть нам дан многочлен третьей степени a3 x3 + a2 x2 + a1 x + a0. Вынесем за скобки общий множитель x при слагаемых, в которых это возможно. Получим: (a3 x2 + a2 x + a1)x + a0. Вынесем за скобки x также и в полученном выражении со скобками, в итоге получим: ((a3 x + a2)x + a1)x + a0.
Полученную форму записи называют схемой Горнера. Очевидно, что она существует для многочлена любой степени.
|
|
|
Итак, имея n = 3 и коэффициенты a3, a2, a1 и a0, мы можем посчитать его значение с помощью n операций умножения и n операций сложения, а это значит, что для вычисления требуется порядка 2 n операций и алгоритм имеет линейную асимптотическую сложность O( n), что демонстрирует очевидное преимущество перед предыдущим решением.
Посмотрим, как может выглядеть цикл, в котором вычисляется значение многочлена в точке. Для этого немного изменим представление в виде схемы Горнера, не меняя при этом значения многочлена: (((0x + a3)x + a2)x + a1)x + a0.
Теперь нам требуется n + 1 операций, однако заведя переменную res для накопления результата, которая перед входом в цикл будет равна 0, мы можем, вводя коэффициенты a3, a2, a1 и a0, посчитать значение многочлена в одном цикле:
res := 0;
for i := 1 to n + 1 do begin
read(a);
res := res * x + a
end;
Примечание: оператор read нужен нам для того, чтобы можно было вводить коэффициенты через пробел, а не через Enter.
Теперь разберем сам цикл. На первом шаге мы получаем в res значение выражения 0 x + a3 = a3, на втором – a3 x + a2, на третьем – (a3 x + a2)x + a1, на четвертом – ((a3 x + a2)x + a1)x + a0. Как видно, формула полностью восстановилась, причем вычисление идет от наиболее вложенных скобок к верхним уровням.
|
|
|
Код:
Дата добавления: 2018-10-25; просмотров: 319; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!