Сравните бинарный алгоритм возведения в степень, метод
степенного дерева и метод множителей для значений n из
интервала от 1 до 100.
Написать на паскеле или с++

Предыдущий
вопрос Следующий
вопрос

Для сравнения бинарного алгоритма возведения в степень, метода степенного дерева и метода множителей для значений от 1 до 100 можно написать следующий код на C++:

#include <iostream>
#include <chrono>
using namespace std;
int binaryExponentiation(int x, int n) {
int res = 1;
while (n > 0) {
if (n % 2 == 1) {
res *= x;
}
x *= x;
n /= 2;
}
return res;
}
int powerTree(int x, int n) {
if (n == 0) {
return 1;
} else if (n % 2 == 0) {
int temp = powerTree(x, n/2);
return temp*temp;
} else {
int temp = powerTree(x, n/2);
return temp*temp*x;
}
}
int primeFactors(int x, int n) {
int res = 1;
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
n /= i;
x *= x;
}
res *= x;
}
if (n > 1) {
res *= x;
}
return res;
}
int main() {
for (int i = 1; i <= 100; i++) {
auto start = chrono::high_resolution_clock::now();
cout << "Binary Exponentiation for " << i << ": " << binaryExponentiation(2, i) << endl;
auto end = chrono::high_resolution_clock::now();
cout << "Time taken: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << "ns" << endl;
start = chrono::high_resolution_clock::now();
cout << "Power Tree for " << i << ": " << powerTree(2, i) << endl;
end = chrono::high_resolution_clock::now();
cout << "Time taken: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << "ns" << endl;
start = chrono::high_resolution_clock::now();
cout << "Prime Factors for " << i << ": " << primeFactors(2, i) << endl;
end = chrono::high_resolution_clock::now();
cout << "Time taken: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << "ns" << endl;
}
return 0;
}

Этот код сначала определяет функции для бинарного алгоритма возведения в степень, метода степенного дерева и метода множителей. Затем в цикле от 1 до 100 вызываются эти функции для различных значений n, и выводятся результаты работы этих алгоритмов, а также замеряется время выполнения каждого из них.

Таким образом, можно сравнить эффективность различных методов возведения в степень для значений от 1 до 100.