Билетная касса, задача на рекурсию Опции

[1qsd]

Вот такая непонятная задача.

В очереди в кассу n человек (от 3 до 20). Про каждого известно, что
1) ему нужен один билет.
2) он должен купить билеты одного или двух стоящих за ним
3) дано время t1, t2, t2 покупки i-м очередником одного, двух или трех билетов.
Подсчитать минимальное время обслуживания очереди.

начало задачи есть (Ввод данных)

Program Bk;
uses crt;
var n,i,j,k: integer;
    t: array[1..20,1..3] of integer;
begin
  clrscr;
  writeln('Введите количество очередников:');
  readln(n);
  for i:=1 to n do
  begin
  writeln('Введите время ',i,' очередника ');
  for j:=1 to 3 do
  readln(t[i,j]);
  end;

  readln;
end.

а что делать дальше, не знаю...

Помогите решить пожалуйста!!

[klem4]

Надобно тестовые примеры, самому сочинять лень если честно, вот проверь это:

const
  n = 20;
  m = 3;

type
  TArray = array [1..n, 1..m] of Integer;

procedure ReadFromFile(const file_name: String;
 var arr: TArray; var size: Integer);
var
  f: Text;
begin

  assign(f, file_name);
  {$I-}
  reset(f);
  {$I+}

  if IOResult <> 0 then begin
    writeln('Cant open file'); readln; halt(1);
  end;

  size := 0;

  while not(eof(f)) do begin
    inc(size);
    read(f, arr[size, 1], arr[size, 2], arr[size, 3]);
    if not(eof(f)) then readln(f);
  end;

  close(f);

end;

procedure Print(const arr: TArray; const size: Integer);
var
  i, j: Integer;
begin
  for i := 1 to size do begin
    for j := 1 to m do write(arr[i, j]:3);
    writeln;
  end;
end;

function GetTime(A: TArray; size: Integer): Integer;
begin
  if size = 0 then GetTime := 0 else
   if (size >= 3) and (A[size, 3] < (A[size, 1] + A[size - 1, 1] + A[size - 2, 1])) then
    GetTime := A[size, 3] + GetTime(A, size - 3)
   else
    if (size >= 2) and (A[size, 2] < (A[size, 1] + A[size - 1, 1])) then
     GetTime := A[size, 2] + GetTime(A, size - 2)
    else
     GetTIme := A[size, 1] + GetTime(A, size - 1);
end;

var
  A: TArray;
  size: Integer;

begin
  ReadFromFile('ticket.txt', A, size);
  Print(A, size);
  writeln('Time = ', GetTime(A, size));
end.

тестировал на файле:

1 2 3
4 5 6
7 8 9
10 11 12

и

1 2 3
4 1 1
1 8 9
10 4 1

[1qsd]

на примерах работает

то есть первый покупает за троих (время = 3), а четвертый покупает сам за себя (время = 10)

Цитата('ticket.txt')
1 2 3
4 5 6
7 8 9
10 11 12
*********************************
второй файл тоже работает: первый покупает за себя (время = 1) + второй покупет за троих (за себя третьего и четвертого, время = 1).

Цитата('ticket.txt')
1 2 3
4 1 1
1 8 9
10 4 1
**********************************
а, например, если вводить массив
1 2 3
4 5 6
7 8 9
то выдает ответ 9, хотя должен 3 (то есть первый купил за всех троих, время = 3!!! )

еще пример:
1 2 3
4 1 6
7 8 9
4 5 1
выдает ответ 2. я так понял считалось так: первый покупает за себя (время = 1), а четвертый покупает за себя, третьего и второго (время = 1). А так считать нельзя. Четвертый может покупать только за себя; за себя и за пятого; за себя, пятого или шестого (разумеется, если бы они были).

А правильный ответ в этой матрице должен быть: первый покупает за себя (время = 1), второй покупает за себя и за третьего (время = 1), четвертый покупает тоже за себя (время = 4). В сумме 6.

[klem4]

Я считал какбы с конца, тоесть последний - это первый

еще пример:
1 2 3
4 1 6
7 8 9
4 5 1
выдает ответ 2.

У последнего покупка трех билетов займет 1, ну и остается первый, который сам себе купит за единицу.

[1qsd]

а можно сделать так, что бы первая строчка - это первый, вторая - это второй покупатель и так далее...?

[klem4]

Можно конечно, а сам не хочешь подумать как это сделать ?

[1qsd]

Переделал код под себя, числа нужно вводить вручную, протестировал на всех примерах - вроде работает

program Bk;
type
  TArray = array [1..20, 1..3] of integer;

function GetTime(A: TArray; size: integer): integer;
begin
  if size = 0 then GetTime := 0 else
   if (size >= 3) and (A[size, 3] < (A[size, 1] + A[size - 1, 1] + A[size - 2, 1])) then
    GetTime := A[size, 3] + GetTime(A, size - 3)
   else
    if (size >= 2) and (A[size, 2] < (A[size, 1] + A[size - 1, 1])) then
     GetTime := A[size, 2] + GetTime(A, size - 2)
    else
     GetTIme := A[size, 1] + GetTime(A, size - 1);
end;

var
  arr: TArray;
  n,i,j,q: Integer;

begin
  q:=1;
  writeln('Введите количество очередников:');
  readln(n);
  for i:=n downto 1 do
    begin
    writeln('Введите время ',q,' очередника  ');
    inc(q);
    for j:=1 to 3 do
    readln(arr[i,j]);
    end;

  for i := n downto 1 do begin
    for j := 1 to 3 do write(arr[i, j],' ');
    writeln;
  end;

writeln('Time = ', GetTime(Arr, n));
readln;
end.

НО!!!

если брать примеры типо:
1)
1 2 3
4 1 6
7 8 9
4 5 1 (считая первая строчка - первый очередник и т.д.)
то программа вместо 1+1+4=6 считает 3+4=7!!!

2)
3 6 7
3 2 6
4 4 4
6 8 3
программа вместо 6(из первой строчки)+4(посередине из третьей строчки)=10,
считает как 7(за первых трех)+6=13

почему-то серединные значения она не берет.

Кстати, проверил еще программу в Сообщение #2, у нее такой же глюк...

Сообщение отредактировано: 1qsd - 27.03.2007 5:55

[klem4]

Это не "глюк", просто алгоритм не верный.