Сегодня на уроке информатики обсуждали алгоритм быстрого возведения в степень. антон был внимателен и запомнил, что алгоритм нужен для того, чтобы сократить количество операций умножения при вычислении a^n. вместо n−1 умножения, которые получаются если просто вычислить произведение a⋅a⋅a⋅…⋅a (n сомножителей) можно получить гораздо меньшее число, если действовать так: если n кратно 2, то найдем сперва a^n/2, а потом умножим a^n/2 на себя если n не кратно 2, то найдем a^n–1, а потом умножим на a. например, чтобы вычислить a^10 хватит четырех умножений: сначала найдем a^2=a⋅a, потом a^4=a^2⋅a^2, потом a^5=a⋅a^4, и, наконец, a^10=a^5⋅a^5. антон также запомнил, что самые "плохие" случаи для этого алгоритма — когда n на 1 меньше точной степени двойки. теперь ему интересно узнать для какого-нибудь большого "плохого" n, а сколько умножений нужно, чтобы возвести a в степень n с этого алгоритма. антону, определите, сколько умножений сделает алгоритм для вычисления 2^n, где n= 2^13–1.
#include <iostream>
using namespace std;
int main() {
setlocale(LC_ALL, "");
int N = 10;
int max = -9999999;
int sum = 0;
int choise = 0;
int arr[N] = {0};
cout << "Введите 10 значений: ";
for(int i = 0; i<N; ++i) {
cin >> arr[i];
}
cout << "Введите действие (1 - +, 2 - макс. значение, 3 - колво отр. значений)";
cin >> choise;
if(choise==1) {
for(int i = 0; i<N; ++i) {
sum+=arr[i];
}
cout << endl << "Сумма: " << sum;
}
if(choise==2) {
for(int i = 0; i<N; ++i) {
if(arr[i]>max) {
max = arr[i];
}
}
cout << endl << "Макс. знач: " << max;
}
if(choise==3) {
for(int i = 0; i<N; ++i) {
if(arr[i]<0) {
++sum;
}
}
cout << "Колво отр. знач: " << sum;
}
if(choise!=1&&choise!=2&&choise!=3) {
cout << "Введите корректное значение.";
}
return 0;
}
ЯП: С++ | можно не писать std:: , если использовать пространство имен: using namespace std;
#include <iostream>
int main() {
const int SIZE = 10;
int regim, sum, max, count;
int arr[SIZE];
for (int i = 0; i < SIZE; i++)
{
std::cin >> arr[i]; // вводим элементы массива
std::cout << arr[i] << "\t"; // выводим массив в консоль
}
std::cin >> regim;
if ((regim > 0) && (regim < 4))
{
if (regim == 1)
{
for (int i = 0; i < SIZE; i++)
{
sum += arr[i]; // или sum = sum + arr[i];
}
std::cout << "Сумма элементов массива = " << sum << std::endl;
}
else if (regim == 2)
{
max = arr[0];
for (int i = 0; i < SIZE; i++)
{
if (max < arr[i])
max = arr[i];
}
std::cout << "Максимальный элемент в массиве = " << max << std::endl;
}
else
{
for (int i = 0; i < SIZE; i++)
{
if (arr[i] < 0)
count++;
}
std::cout << "Число отрицательных элементов в массиве = " << count << std::endl;
}
}
else
std::cout << "Доступен только 1-3 режим!" << std::endl;
return 0;
}