Задача: Зведення числа в ступінь

Просте зведення числа в ступінь N – це N – 1 умножений в циклі. А множення – це дорога, трудомістка операція…

Формулювання даного завдання така:

написати функцію зведення в ступінь X ** N, але так, щоб для цього було потрібно мінімальне число операцій множення);
постарайтеся контролювати і включити в висновок число потребовавшихся для обчислення умножений.

P.S. логіка такого рішення не моя, а знаменитого гуру Чарльза Ентоні Хоара (Чарльз Ентоні Річард Хоар), я тільки записав кодом його рішення:

#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;
}

#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;

}

І ось кілька зразків виконання, то що повинно вийти:

3 думки про "Задача: Зведення числа в ступінь”

Цей приклад ще раз показує міць рекурсії як методу обчислень. Спробуйте записати цей алгоритм в ітераційної техніки (циклами) … а ще краще – пояснити потім комусь як цей записаний алгоритм працює.
Любіть рекурсию!

відповісти