как можно больших
как можно больших значений n.
Пример. При n=5 необходимо три операции - (k*k)2*k.
Определим массив Op, его элемент Op[i] предназначен для хранения минимального количества операции при возведении в степень i (Op[1]=0). Для вычисления выражения, дающего n-ю степень числа k, арифметические операции применяют в некоторой последовательности, согласно приоритетам и расставленным скобкам. Рассмотрим последнюю примененную операцию.
Если это было умножение, тогда сомножителями являются натуральные степени числа k, которые в сумме дают n. Степень каждого из сомножителей меньше n, и ранее вычислено, за какое минимальное число операций ее можно получить. Итак:
opn1:=min{по всем p:1?p<n, Op[p]+Op[n-p]+1}.
Если это возведение в степень:
opn2:=min{ для всех p (?1) - делителей n, Op[n div p]+p-1}.
Результат - Op[n]=min(opn1,opn2). Фрагмент реализации:
......
Op[1]:=0;
for n:=2 to ???? do begin
opn:=n;{opn - рабочая переменная}
for p:=1 to n-1 do begin
opn:=Min(opn,Op[p]+Op[n-p]+1);{Min
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
