Задача про мост

[Sparky]

еще раз спасибо, теперь буду реализовывать

[Serge_Bliznykov]

Самое смешное, что чуть ниже в этом самом п.4 приведен пример, когда этот алгоритм оптимального решения не даёт!

Ага. Забавно!
И, что характерно. В качестве оптимального подходит тот алгоритм, который я описывал с самого начала - самый быстрый переводит всех по очереди.
Как вариант можно вычислить время согласно алгоритму два самых быстрых и два самых медленных и сравнить со временем, вычисленным по формуле (мой пост #2) - и выбрать оптимальный из этих двух...
а вообще надо бы почитать алгоритм Роте, надеюсь, что у меня базисных знаний математики хватит, чтобы его понять...

[Sparky]

вот такая программа у меня получилась:

program bridge;

{$APPTYPE CONSOLE}

uses
  SysUtils;

//==============================================================================
//      описание типов и переменных
//==============================================================================
type
  human = record
    xod:integer;
    status:boolean; //false-не перешел true-перешел
  end;

var
  people:array[1..10] of human;
  left_min_1:integer; //список тех кто ушел направо
  left_min_2:integer; //список тех кто ушел направо
  left_max_1:integer; //список тех кто ушел направо
  left_max_2:integer; //список тех кто ушел направо
  rigth:integer; //список тех кто ушел налево
  i:integer;
  n:integer;
  f_out:text;
  sum:integer;
//==============================================================================
//      процедуры и функции
//==============================================================================
procedure read_data();  //процедура ввода данных
var
  f_in:text;
begin
  assign(f_in,'D:\КМБ\Языки программирования\практика\pascal\bridge\input.txt');
  reset(f_in);
  readln(f_in,n);
  for i:=1 to  n do
  begin
    read(f_in,people[i].xod);
    people[i].status:=false;
  end;
  close(f_in);
end;

function cheak():boolean; //проверка наличия человек на левой стороне true-есть false-нет
var
  j:integer;
  res:boolean;
begin
  res:=false; //изначально думаем что на левом никого нет
  j:=1;
  while((j<=n)and(res=false)) do
  begin
    if(people[j].status=false) then res:=true //находим оставшегося на левом и выходим
    else  inc(j); //ищем дальше
  end;
  cheak:=res;    
end;

function search_min(k:integer;storona:integer):integer;  //поиск самого быстрого (с какого начинаем, какая сторона)
var
  test:boolean;
begin
  test:=false;
  if (storona=0) then //если с левой стороны то проверяем status на false и ++
  begin
    while((test=false)and(k<=n)) do
    begin
      if(people[k].status=false) then test:=true
      else inc(k);
    end;
  end
  else if (storona=1) then //если с правой стороны то проверяем status на true и --
  begin
    while((test=false)and(k<=n)) do
    begin
      if(people[k].status=true) then test:=true
      else inc(k);
    end;
  end;
  search_min:=k;
end;

function search_max(k:integer):integer;  //поиск медленного слева
var
  test:boolean;
begin
  test:=false;
  while((test=false)and(k>=1)) do
    begin
      if(people[k].status=false) then test:=true
      else dec(k);
    end;
  search_max:=k;
end;

//==============================================================================
//      главная программа
//==============================================================================
begin
  read_data();

//==============================================================================
//      подготовка результируещего файла
//==============================================================================
  assign(f_out,'D:\КМБ\Языки программирования\практика\pascal\bridge\output.txt');
  rewrite(f_out);
  sum:=0;
//==============================================================================
//      проверка на быстрое решение
//==============================================================================
  if(n=0) then  //если 0 то выводим сообщение
  begin
    writeln(f_out,'введите n больше 0');
  end
  else if(n=1) then //если 1 то выводим его время
  begin
    people[1].status:=true;
    writeln(f_out,'>',people[1].xod);
    writeln(f_out,'time: ',people[1].xod);
  end
  else //начинаем вычисления
  begin
    while(cheak()=true) do  //если кто-нибудь остался на левом берегу
    begin
//==============================================================================
//      1.берем 2 быстрых переводим на правый берег
//==============================================================================
      left_min_1:=search_min(1,0);  //самый быстрый
      left_min_2:=search_min(left_min_1+1,0); //второй быстрый

      people[left_min_1].status:=true;
      people[left_min_2].status:=true;

      writeln(f_out,'>',people[left_min_1].xod,' ',people[left_min_2].xod);

      sum:=sum+people[left_min_2].xod;

[Sparky]

//==============================================================================
//      проверяем остался ли кто-нибудь и переводим самого быстрого обратно
//==============================================================================
      if (cheak()=false) then break //выходим если никого нет
      else  //возвращаем самого быстрого
      begin
        rigth:=search_min(1,1);  //самый быстрый
        people[rigth].status:=false;
        writeln(f_out,'<',people[rigth].xod);
        sum:=sum+people[rigth].xod;
      end;
//==============================================================================
//      находим 2 медленных и переводим
//==============================================================================
      left_max_1:=search_max(n);  //самый быстрый
      left_max_2:=search_max(left_max_1-1); //второй быстрый

      people[left_max_1].status:=true;
      people[left_max_2].status:=true;

      writeln(f_out,'>',people[left_max_1].xod,' ',people[left_max_2].xod);

      sum:=sum+people[left_max_1].xod;
//==============================================================================
//      проверяем остался ли кто-нибудь и переводим самого быстрого обратно
//==============================================================================
      if (cheak()=false) then break //выходим если никого нет
      else  //возвращаем самого быстрого
      begin
        rigth:=search_min(1,1);  //самый быстрый
        people[rigth].status:=false;
        writeln(f_out,'<',people[rigth].xod);
        sum:=sum+people[rigth].xod;
      end;
    end;
    writeln(f_out,'time: ',sum);
  end;
  close(f_out);
end.

Но вот при входных данных 1 100 100 100 она работает не оптимально, как уж говорилось. Но вот как сделать так чтобы все работало оптимально я не знаю.[/CODE]

[Serge_Bliznykov]

Роте ни читали? Вот и уменя тоже руки никак не дойдут...

а если использовать то, что я выше предложил?

Как вариант можно вычислить время согласно алгоритму два самых быстрых и два самых медленных и сравнить со временем, вычисленным по формуле (мой пост #2) - и выбрать оптимальный из этих двух...

т.е. время прохода по одному алгоритму есть. Для второго просто по формуле посчитать. И брать наименьший.

[Sparky]

хм надо попробовать, спасибо

[Stilet]

Папа может перейти его за 1 минуту, мама — за 2, сынишка — за 5, а бабушка — за 10 минут. У них есть один фонарик, а мост выдерживает только двоих. За сколько минут все они смогут его перейти при лучшей организации своего движения?

Папа ведет бабулю - 10 мин
Возвращается - 11 мин
Отдает фонарь маме, она и сын переходят - 16
Мама возвращается назад - 18
Ведет папу - 20
Итого 20 минут.

Я не ошибаюсь?

[Serge_Bliznykov]

Нет, Виталий, не так..
Вы зря не почитали всё обсуждение, которое растянулось на две страницы.

Тот алгоритм, который я предлагал в начале (ошибочно считая, что он даёт всегда оптимальное решение) - один самый быстрый по очереди переводит всех остальных:

(время будут писать сразу итоговое, если Вам так кажется удобнее ):
Папа ведёт маму - 2 мин
Папа возвращается - 3 мин
Папа ведёт сынишку - 8 минут
Папа возвращается - 9 мин
Папа ведёт бабушку - 19 минут

но есть и другой способ (я его условно называю Самые Быстрые + Самые Медленнные)
Папа ведёт маму - 2 мин
Папа возвращается - 3 мин
он отдаёт фонарик Сын и Бабушка идут вместе - 13 минут
Мама возвращается - 15 минут
Папа и мама идут - 17 минут

[Stilet]

зря не почитали

Ошибаешся. Прочитал, но по формулам не многое понял. Но всетки те 40 и 33 минут многовато, вот и подумал что 20 мин как раз им хватит чтоб успеть к зомбоящику.

[Vago]

Sparky, Вот Вам запрограммированный алгоритм этого самого немца. Паскаля я не знаю, но, думаю, - переведёте. Питон, как и Си, начинает нумерацию эл-тов массива с нуля. Массив времён (t[]) должен быть упорядочен по неубыванию.

#!/usr/bin/python
# -*- coding: cp1251 -*-

from numpy import array

t = array( [1, 2, 5, 10], dtype = int )
#2 t = array( [1, 2, 10, 10, 15], dtype = int )
#3 t = array( [1, 100, 100, 100], dtype = int )
n = len( t )

tTotal = 0

def PrintTimesAndIncreaseTotal( t0 ):
    global tTotal
    tTotal += t0
    print "t = ", t0, " tTotal = ", tTotal


def Forward( k1, k2 ):
    print "Forward: #%d( %d ) & #%d( %d )" % (k1+1,  t[k1], k2+1, t[k2]),
    PrintTimesAndIncreaseTotal( t[k2] )


def Back( k ):
    print "Back: #%d( %d )" % (k+1, t[k]),
    PrintTimesAndIncreaseTotal( t[k] )


while n >= 4 :
    t1 =   t[0] + 2 * t[1]   + t[n-1]
    t2 = 2*t[0] +     t[n-2] + t[n-1]

    if t1 < t2:
        Forward( 0, 1 )
        Back( 0 )
        Forward( n-2, n-1 )
        Back( 1 )
    else:
        Forward( 0, n-1 )
        Back( 0 )
        Forward( 0, n-2 )
        Back( 0 )

    n -= 2

if n == 3:
    Forward( 0, 2 )
    Back( 0 )

Forward( 0, 1 )

#