Автозаправка

Степень числа

Даны два натуральных числа n и k. Требуется определить выражение, которое вычисляет kⁿ . Разрешается использовать операции умножения и возведения в степень, круглыми скобками и переменной с именем k.Умножение считается одной операцией, возведению в степень q соответствует q-1 операция. Найти минимальное количество операций, необходимое для возведения в степень n. Желательно сделать это для как можно больших значений n.

Пример. При n=5 необходимо три операции - (k*k)²*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 - функция поиска минимума двух чисел}

if (n mod p=0) and (p<>1) then opn:=Min(opn,Op[n div p]+p-1);

end;

Op[n]:=opn;

end;

....

Вдоль кольцевой дороги расположено m городов, в каждом из которых есть автозаправочная станция. Известна стоимость Z[i] заправки в городе с номером i и стоимость C[i] проезда по дороге, соединяющей i - й и (i+1)-й города, C[m] - стоимость проезда между первым и m-м городами. Для жителей каждого города определить город, в который им необходимо съездить, чтобы заправиться самым дешевым образом, и направление - «по часовой стрелке» или «против часовой стрелки», города пронумерованы по часовой стрелке.

Не будем рассматривать переборный вариант решения задачи, суть которого в проверке всех 2*m вариантов для жителей каждого города, итого - 2*m*m проверок. Введем два дополнительных массива

On, Ag: array[1..m] of record wh, qh:integer; end; .

On[i] означает, где следует заправляться (wh) и стоимость заправки (qh) жителям i-го города, если движение разрешено только по часовой стрелке. В этом случае жители города i имеют две альтернативы: либо заправляться у себя в городе, либо ехать по часовой стрелке. Во втором случае жителям города i надо заправляться там же, где и жителям города i+1, или в первом, если i=m. Итак, On[i]=min{Z[i],C[i]+On[i+1].qh}. Откуда известно значение On[i+1].qh? Необходимо найти город j с минимальной стоимостью заправки - On[j]:=(j,Z[j]). После этого можно последовательно вычислять значения On[j-1], On[j-2], ..., On[j+1]. Аналогичные действия необходимо выполнить при формировании массива Ag[i], после этого для жителей каждого города i следует выбрать лучший из On[i].qh и Ag[i].qh вариант заправки.