Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Комбинаторика, оптимизация программы

32K
17 января 2009 года
Serj123
36 / / 11.07.2008
Написал программу:
Код:
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.


Проблема заключается в том, что при вводе большого числа контейнеров программа очень долго начинает думать или совсем зависает. Может быть кто нибудь подскажет другой вариант алгоритма работы пограмы?
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог