Основы объектно-ориентированного программирования на языке C# book | Page 34

2 Oснови алгоритмiзацiı̈
Алгоритм:
1. Покласти i рiвним n, r рiвним 0, рiвним b.
2. Пiднести до степеня i.
3. Помножити на степiнь.
4. Покласти s рiвнiй сумi r i добутку a i на степiнь.
5. Якщо i = 0, то r – результат (стоп). Iнакше покласти i = i − 1,
перейти до кроку 2.
Послiдовнiсть обчислень за алгоритмом описує вираз
a n x n + ... + a 1 x + a 0 .
Iснує також iнший алгоритм для розв’язання задач цього класу.
Вхiднi данi: тi самi, що й у попереднiй задачi.
Результат: такий самий.
Змiннi: r, x, i – цiлого типу.
Алгоритм:
1. Покласти i рiвним n, x рiвним b.
2. Покласти r рiвним a i .
3. Помножити r на x.
4. Покласти r рiвним добутку.
5. Покласти i рiвним i − 1.
6. Покласти r рiвним r + a i .
7. Якщо i = 0, то r – результат, iнакше перейти до кроку 3.
Послiдовнiсть обчислень за цим алгоритмом можна пояснити вира-
зом
(...(((a n x + a n−1 x + a n−2 )x + a n−3 )x + ... + a 1 )x + a 0 .
Такий метод обчислення значення полiнома у точцi називається
схемою Горнера.
Виразимо складнiсть дiı̈ пiднесення до степеня i як i − 1 операцiй
множення. Тодi складнiсть другого алгоритму (за схемою Горнера)
у виглядi кiлькостi операцiй додавання та множення дорiвнюватиме
2n, а для прямого алгоритму становитиме
n
X
n +1
n 2 + 3n + 2
n 2
+ 2n > 2n.
(i + 1) + n =
(n + 2) + n =
+ n>
2
2
2
i=1
34