Просте зведення числа в ступінь N – це N – 1 умножений в циклі. А множення – це дорога, трудомістка операція…
Формулювання даного завдання така:
- написати функцію зведення в ступінь X ** N, але так, щоб для цього було потрібно мінімальне число операцій множення);
- постарайтеся контролювати і включити в висновок число потребовавшихся для обчислення умножений.
P.S. логіка такого рішення не моя, а знаменитого гуру Чарльза Ентоні Хоара (Чарльз Ентоні Річард Хоар), я тільки записав кодом його рішення:
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 38 39 40 41 42 43 | #include <assert.h> #include <iostream> using namespace std; double power(double a, int n, int& m) { assert(n > 0 || (a != 0.0 || n != 0)); switch (n) { case 0: return 1; case 1: return a; default: { double a2 = power(a, n / 2, m); if (n & 1) { m += 2; return a * a2 * a2; } else { m++; return a2 * a2; } } } } int main() { setlocale(LC_ALL, "rus"); double e, r; int n, m; while (true) { cout << "что возводить? : "; cin >> e; cout << "в какую степень? : "; cin >> n; m = 0; r = power(e, n, m); cout << e << "**" << n << "=" << r << ", число умножений " << m << endl << endl; } return 0; } |
І ось кілька зразків виконання, то що повинно вийти:
Цей приклад ще раз показує міць рекурсії як методу обчислень. Спробуйте записати цей алгоритм в ітераційної техніки (циклами) … а ще краще – пояснити потім комусь як цей записаний алгоритм працює.
Любіть рекурсию!
Для N ^ 15 досить 5 умножений. Ваш результат – 6.
І все таки 6. п'ять – це з розподілом, а ця операція ще затратнее (якщо N не ступінь двійки).