1)подсчитайте сложность алгоритма перемножения двух натуральных чисел "столбиком" при условии , что одно из них состоит из n , а второе - из m десятичных цифр. 2)постройте эффективный алгоритм возведения числа x в степень n=152.

Запишіть речення, зробіть повний синтаксичний розбір речення.
Яке слово складається з семи однакових літер?

1) Чтобы подсчитать сложность алгоритма перемножения двух натуральных чисел "столбиком", нам нужно рассмотреть количество операций умножения, которые нужно выполнить.

Предположим, что первое число состоит из n десятичных цифр, а второе число - из m десятичных цифр. Для выполнения перемножения "столбиком", нам нужно умножить каждую цифру первого числа на каждую цифру второго числа.

Количество операций умножения можно оценить следующим образом:

- Первая цифра первого числа нужно умножить на каждую цифру второго числа. Всего это будет m операций умножения.
- Вторая цифра первого числа также нужно умножить на каждую цифру второго числа. Из-за того, что умножение на вторую цифру происходит в следующий разряд, количество операций умножения увеличивается на m-1.
- Третья цифра первого числа нужно умножить на каждую цифру второго числа. Количество операций умножения увеличивается еще на m-2.
- И так далее, пока мы не учитываем все цифры первого числа.

Итого, общее количество операций умножения можно посчитать следующим образом:

m + (m-1) + (m-2) + ... + 1

Это арифметическая прогрессия. Чтобы найти сумму арифметической прогрессии, мы можем использовать формулу:

S = (n/2)*(2*a + (n-1)*d)

где S - сумма прогрессии, n - количество элементов в прогрессии, a - первый элемент прогрессии, d - разность между элементами прогрессии.

В нашем случае:

n = m
a = m
d = -1

Таким образом, общее количество операций умножения:

S = (m/2)*(2*m + (m-1)*(-1))
= (m/2)*(2*m - m + 1)
= (m/2)*(m + 1)

Таким образом, сложность алгоритма перемножения двух натуральных чисел "столбиком" при условии, что одно из них состоит из n, а второе - из m десятичных цифр, равна O(m^2).

2) Чтобы построить эффективный алгоритм возведения числа x в степень n=152, мы можем использовать метод быстрого возведения в степень.

Этот метод основан на следующем наблюдении: для любого числа x и нечётного положительного числа n, x^n можно представить как x * (x^(n-1)). То есть, чтобы возвести число в нечётную степень, мы можем сначала возвести его в степень на единицу меньшую, а затем умножить на само себя.

Таким образом, чтобы возвести число x в степень 152, мы можем следовать следующему алгоритму:

1. Если n равно 0, вернуть 1, так как любое число в степени 0 равно 1.
2. Если n чётное, вычислить y = (x^(n/2)) и вернуть y*y. Здесь используется рекурсия: сначала возводим x в половинную степень n/2, а затем умножаем результат на самого себя.
3. Если n нечётное, вычислить y = (x^((n-1)/2)) и вернуть x*y*y. Здесь сначала возводим x в степень на единицу меньшую (n-1)/2, а затем умножаем результат на самого себя и на x.

В результате выполнения этого алгоритма, мы будем разбивать степень n на меньшие степени, пока не дойдём до степени 0, и затем будем собирать результаты умножения в обратном порядке, пока не получим итоговый результат x^n.

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

Вы можете реализовать этот алгоритм на любом языке программирования, например, на Python:

```python
def power(x, n):
if n == 0:
return 1
elif n % 2 == 0:
y = power(x, n // 2)
return y * y
else:
y = power(x, (n - 1) // 2)
return x * y * y

x = 2 # Возведение числа 2 в степень 152
result = power(x, 152)
print(result)
```

В этом примере мы возводим число 2 в степень 152, используя рекурсивную функцию power. Результат будет равен 4, sept2021уже (2^152).

Этот алгоритм имеет сложность O(log n), так как на каждом шаге мы уменьшаем степень вдвое, пока не достигнем степени 0.