Задача 8.
Ввести три числа а,b,с.
1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c].
2). Можно ли представить число а таким образом, чтобы
,
где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует.
|
Решение задачи 8.
Рассмотрим сначала случай, когда a, b, c, xi - натуральные.
1) Разбивка на слагаемые.
Если a<c, то задача неразрешима, если a лежит на [c,d], то задача решена.
Пусть a>d. Минимальное число слагаемых будет тогда, когда каждое из слагаемых будет как можно больше. Введем функцию ceil(x)=k+1, если k<x<=k+1, k - целое. Покажем, что в случае, если разложение существует, то необходимо ceil(a/d) слагаемых.
Пусть k=ceil(a/d). Если мы возьмем k слагаемых по d, то превышение над a будет p=k*d-a. Каждое из k слагаемых мы можем уменьшить не более чем на d-c. Количество уменьшаемых слагаемых должно быть n=ceil(p/(d-c)). Если n>k, то разложения не существует (слагаемых, которые надо уменьшить, больше, чем у нас есть, другими словами, a div c = a div d, и a mod c <> 0, a mod d <> 0). Если n<=k, то L, L=p div (d-c), слагаемых уменьшаем на (d-c), одно слагаемое - на p mod (d-c), остальные остаются без изменений (равными максимальному).
Если a, b, c, xi - целые, то алгоритм практически не изменяется.
2) Разбивка на сомножители.
Метод решения этой задачи аналогичен использованному при решении задачи о нахождении максимальной по длине возрастающей подпоследовательности введенной последовательности (см. задачу 20 главы "Рекуррентные соотношения и динамическое программирование").
Опять будем рассматривать только случай a>d.
Обозначим через L упорядоченное по возрастанию множество делителей числа A, лежащих на отрезке [c,d], количество делителей не превышает 2*SQRT(A) (если a=f*g, то f<=SQRT(a), g>=SQRT(a), всего разных f - не более SQRT(a), столько же и разных g). Пусть L1 минимальный элемент из L, a L2- максимальный. В массив S[1..k] занесем по возрастанию все делители числа a (включая и само число a=S[k]), начиная с минимального элемента из L. Из утверждения выше следует, что k<=2*SQRT(A)+1.
Будем искать минимальную по длине последовательность элементов массива S, ведущую из множества L в число a=S[k] такую, что каждый последующий элемент последовательности при делении на предыдущий дает частное, принадлежащее множеству L, и нулевой остаток.
Заведем массивы B[1..k] и C[1..k]. В B[i] будем заносить индекс последующего элемента в подпоследовательности минимальной длины, ведущей из S[i] в S[k] (B[i]=0, если в a из S[i] попасть невозможно), в C[i] будет храниться число элементов в этой минимальной последовательности (отметим, что мы рассматриваем только такие последовательности, у которых частное от деления последующего члена последовательности на предыдущий принадлежит множеству L, а остаток от деления нулевой).
Сначала во все элементы C, кроме последнего, занесем какое-нибудь большое число, например 2*A. Если C[i]=2*A, то будем считать, что последовательности элементов, идущей от S[i] к S[k], пока не обнаружено.
После заполнения матриц A и B мы находим минимальную длину цепочки, ведущей из множества L в число a.
for i:=1 to k-1 do C[k]:=2*A; {последовательности нет}
C[k]:=1; {последовательность из одного элемента A}
B[k]:=0; {предыдущего элемента нет}
for i:=k-1 downto 1 do
for j:=i+1 downto k do
if (S[j] div S[i] >=L1) and {частное S[j]/S[i]}
(S[j] div S[i] <=L2) and {принадлежит L, и}
(S[j] mod S[i] =0) {остаток нулевой}
then if C[i]>C[j]+1 {если длина обнаруженной}
then begin {сейчас подпоследовательности,}
{идущей от S[i] к S[k], меньше, чем}
C[i]:=C[j]+1; {ранее найденная, то кор ректируем длину и индекс следующего элемента}
B[i]:=j
end;
i:=1; min:=2*A; j:=0;
while S[i]<=L2 do
begin
if C[i]< min
then begin
min:=C[i]; {корректируем минимум}
j:=i; {сохраняем индекс первого элемента}
end;
i:=i+1
end;
if j=0
then writeln('Разложения не существует')
else begin
writeln('Разложение:');
write(A[j]);
for i:=1 to min-1 do
begin
P:=j;
j:=B[j];
write(A[j]/A[p]) {распечатка сомножителя}
end
end
В случае, если a, c, d, xi - целые, в массив S помещаем в порядке возрастания модуля все делители числа A, начиная с минимального элемента в L. Далее - аналогично.
|
