Program Port;
{Задание: Для погрузки контейнеров на судно, чтобы обеспечить равномерную
загрузку, их необходимо разделить на две половины так, чтобы их массы
были приблизительно равны... Число контейнеров четное. Вывести на экран
номера контейнеров и полученную массу с каждой стороны. Масса контейнера
вводится вручную}
Const
Max_Kontejnerov=100; {максимальное число контейнеров на судне}
Max_Storona=Round(Max_Kontejnerov/2); {максимальное число контейнеров с
одной стороны}
Type
Perem_Storon=array [1..Max_Storona] of Byte;
Var
N,i,j: Byte; {число контейнеров размещаемых на судно, переменные цикла}
Mas: array[1..Max_Kontejnerov] of Integer;
Storona_1, Storona_2, Podxod, Podxod_1: Perem_Storon;
Sum_1, Sum_2, Raznost: LongInt;
{----------------------------------------------------------------------------}
Procedure Pods4et(Kod_dostypa:Byte;
Storona_1:Perem_Storon;
Var Storona_2, Podxod, Podxod_1: Perem_Storon;
Var Sum_1, Sum_2, Raznost: LongInt);
{Процедура подсчета суммы и запоминания вариантов}
Var
i,j,k: Byte; {переменные цикла, счетчик}
Flag1: Boolean;
Vrem_Sum_1, Vrem_Sum_2: LongInt; {временные суммы}
Begin
{Обнуление переменных}
k:=1;
Vrem_Sum_1:=0;
Vrem_Sum_2:=0;
{Определяем для 2-й стороны элементы, не входящие в 1-ю сторону}
For i:=1 to N do {Общее число контейнеров}
Begin
{Обнуление переменных}
Flag1:=False;
{Число входящих контейнеров}
For j:=1 to N do
If Storona_1[j]=i then {Если данный номер уже имеется}
Flag1:=True;
{Если при проверке не выявлено совпадений}
If (Flag1=False) and (k<N+1) then
Begin
Storona_2[k]:=i;
Inc(k);
End;
End;
{Подсчет временных сумм}
For i:=1 to Trunc(N/2) do
Begin
Vrem_Sum_1:=Vrem_Sum_1+Mas[Storona_1]; {подсчет суммы 1-й стороны}
Vrem_Sum_2:=Vrem_Sum_2+Mas[Storona_2]; {подсчет суммы 2-й стороны}
End;
{Если выполняется для случая с кодом 0 или 1}
If (Kod_dostypa=0) or
((Kod_dostypa=1) and (Raznost>Abs(Vrem_Sum_1-Vrem_Sum_2))) then
Begin
{Расчет комбинации}
Sum_1:=Vrem_Sum_1;
Sum_2:=Vrem_Sum_2;
Raznost:=Abs(Sum_1-Sum_2);
{Копируем один массив в другой}
For i:=1 to Trunc(N/2) do
Begin
Podxod:=Storona_1;
Podxod_1:=Storona_2;
End;
End;
End;
{----------------------------------------------------------------------------}
Begin
{Обнуление переменных}
Sum_1:=0;
Sum_2:=0;
Raznost:=0;
{Запрашиваем количество контейнеров}
WriteLn;
WriteLn('Максимальное число контейнеров, размещаемых на судне: ', Max_Kontejnerov);
WriteLn('Вводимое число контейнеров должно быть четным.');
Write('Введите число контейнеров, размещаемых на судне: ');
ReadLn(N);
{Проверяем правильность ввода:
- число контейнеров должно быть меньше Max_Kontejnerov;
- вводимое число контейнеров должно быть четным}
If (N<Max_Kontejnerov) and (int(N/2)*2=N) and (N>0) then
Begin
{Запрашиваем массы контейнеров}
WriteLn('Введите массы контейнеров в тоннах.');
For i:=1 to N do
Repeat
Write('Введите массу в тоннах контейнера № ',i,' ');
ReadLn(Mas);
Until Mas>0;
{Задаем начальную комбинацию для сторон}
For i:=1 to Trunc(N/2) do
Storona_1:=i;
{Подсчет первой комбинации контейнеров}
Pods4et(0,Storona_1, Storona_2, Podxod, Podxod_1, Sum_1, Sum_2, Raznost);
{Перебор всех возможных вариантов с повторением}
Repeat
If Storona_1[Trunc(N/2)]<N then {последнее число не достигло максимума}
Inc(Storona_1[Trunc(N/2)])
Else {последнее число достигло максимума}
If Storona_1[Trunc(N/2)]=N then
For i:=Trunc(N/2)-1 downto 1 do
If Storona_1<(N-(Trunc(N/2)-i)) then
Begin
Inc(Storona_1);
For j:=i+1 to Trunc(N/2) do
Storona_1[j]:=Storona_1+j-i;
Break;
End;
{Подсчет новой комбинации контейнеров}
Pods4et(1,Storona_1, Storona_2, Podxod, Podxod_1, Sum_1, Sum_2, Raznost);
Until Storona_1[1]=Trunc(N/2)+1;
{Вывод результатов работы программы на экран}
WriteLn;
WriteLn('РЕЗУЛЬТАТ ВЫЧИСЛЕНИЙ:');
WriteLn;
Write('Номера контейнеров 1-й стороны: ');
{Вывод номер контейнеров 1-й стороны}
For i:=1 to Trunc(N/2) do
Write(Podxod,' ');
WriteLn;
WriteLn('Сумма тонажа 1-й стороны: ', Sum_1);
{Вывод номеров контейнеров 2-й стороны}
Write('Номера контейнеров 2-й стороны: ');
For i:=1 to Trunc(N/2) do
Write(Podxod_1,' ');
WriteLn;
WriteLn('Сумма тонажа 2-й стороны: ', Sum_2);
WriteLn;
WriteLn('Для завершения работы программы нажмите клавишу Enter');
ReadLn;
End
Else{либо нечетное количество контейнеров, либо превышает максимальное число}
Begin
WriteLn('Максимальное число контейнеров не должно превышать: ', Max_Kontejnerov);
WriteLn('Число контейнеров должно быть четным.');
ReadLn;
End;
End.
Комбинаторика, оптимизация программы
Код:
Проблема заключается в том, что при вводе большого числа контейнеров программа очень долго начинает думать или совсем зависает. Может быть кто нибудь подскажет другой вариант алгоритма работы пограмы?