Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

Даны два натуральных числа n и k. Требуется определить выражение, которое вычисляет kn . Разрешается использовать операции умножения и возведения в степень, круглыми скобками и переменной с именем k.Умножение считается одной операцией, возведению в степень q соответствует q-1 операция. Найти минимальное количество операций, необходимое для возведения в степень n. Желательно сделать это для как можно больших значений 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 - функция поиска минимума двух чисел}

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 вариант заправки.




Поделиться с друзьями:


Дата добавления: 2014-11-28; Просмотров: 686; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.