Задача 53-г. Глупый винчестер.

Книга адресована школьникам средних и старших классов, желающим испытать себя в «олимпийских схватках». Может быть полезна студентам-первокурсникам и преподавателям информатики.

Модераторы: Oleg_D, Модераторы

Задача 53-г. Глупый винчестер.

Сообщение Paster Fob » 27.02.2013 23:03:42

Здравствуйте Олег Виленович!Что-то долго я силился понять что нужно сделать в этом задании.Значит так,начальное положение головки считаем за 0,считываем из файла сначала период проверки очереди,затем строки с цифрами это будут номера дорожек.Перемещение головки от начальной до следующей равно 1 кванту+1 квант на чтение/запись дорожек.Например нужно переместиться с 0 до 10 дорожки и с 10 до 5.Значит время передвижения головки от начальной точки до нужной дорожки и чтение/запись с них будет равно 17 квантам(15 на передвижение головки,2 на чтение/запись данных с дорожек,по 1-ому обороту на каждую).По истечении периода добавляем в очередь новые числа(дорожки) если конечно они не закончились.
Если я правильно понял задание,то исходя из выше сказанного вот что у меня получилось:
Код: Выделить всё
var
  start,track:byte;
  i,timeout,n:byte;
  que:string;
  kwant:integer;
  f:text;

begin
  assign(f,'C:\Files for Program Pascal\Disk.in');
  reset(f);
  read(f,timeout);
  readln(f);
  kwant:=0; start:=0;
  que:='';
  while not eoln(f) do begin
    read(f,n);
    que:=que+chr(n);
  end;
  readln(f);
  while length(que)>0 do begin
    track:=ord(que[1]);
    if track>start then
      for i:=start+1 to track do begin
        inc(kwant);
        if (kwant mod timeout=0) and (not eof(f)) then begin
          while not eoln(f) do begin
            read(f,n);
            que:=que+chr(n);
          end;
          readln(f);
        end;
      end
      else if track<start then
        for i:=start-1 downto track do begin
          inc(kwant);
          if (kwant mod timeout=0) and (not eof(f)) then begin
            while not eoln(f) do begin
            read(f,n);
            que:=que+chr(n);
          end;
          readln(f);
        end;
      end;
      delete(que,1,1);
      inc(kwant);
      if (kwant mod timeout=0) and (not eof(f)) then begin
        while not eoln(f) do begin
        read(f,n);
        que:=que+chr(n);
      end;
      readln(f);
    end;
    start:=i;
  end;
  close(f);
  writeln(kwant);
  readln;
end.


Проверьте правильность решения и понимания задания.
Аватара пользователя
Paster Fob
постоялец
 
Сообщения: 188
Зарегистрирован: 22.02.2011 21:53:36
Откуда: Новосибирск.

Re: Задача 53-г. Глупый винчестер.

Сообщение Oleg_D » 28.02.2013 09:18:20

1. Постановка задачи 53-Г понята правильно.

2. Сравнил решение со своим по следующему тестовому файлу:
Код: Выделить всё
100
50 10 250 30 10
20 40 20 10 60
15 10 25
51 11 251 31 11
21 41 21 11 61

У меня ответ 1410, у вас -- 1430.

3. В конце программы есть ошибочная строка:
start:=i;
Дело в том, что переменная i здесь не определена. Она используется до этого лишь в циклах for, а согласно описанию языка после выхода из цикла она может быть какой угодно.

4. В четырёх местах повторяется один и тот же фрагмент кода:
Код: Выделить всё
  while not eoln(f) do begin
    read(f,n);
    que:=que+chr(n);
  end;
  readln(f);

Напрашивается процедура. Да и с очередью работать лучше через процедуры-функции, это наглядней. В конце концов, смысл обучения не в том лишь, чтобы результат правильный получать, -- надо архитектурные навыки осваивать, без них сложные программы вам не дадутся.
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

Re: Задача 53-г. Глупый винчестер.

Сообщение Paster Fob » 28.02.2013 10:07:22

Это не готовая программа,это так сказать набросок.Для того что бы показть правильно я понял задание или нет и найти логические ошибки.
А разница в результатах,это из-за этого присваивания start:=i; ?
Аватара пользователя
Paster Fob
постоялец
 
Сообщения: 188
Зарегистрирован: 22.02.2011 21:53:36
Откуда: Новосибирск.

Re: Задача 53-г. Глупый винчестер.

Сообщение Oleg_D » 28.02.2013 10:18:27

Paster Fob писал(а):А разница в результатах,это из-за этого присваивания start:=i; ?

Не знаю, я подробно не разбирался.
Для проверки составьте сначала простой тест, чтобы легко в уме считался.
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

Re: Задача 53-г. Глупый винчестер.

Сообщение bormant » 28.02.2013 11:19:12

Oleg_D писал(а):2. Сравнил решение со своим по следующему тестовому файлу:
Код: Выделить всё
100
50 10 250 30 10
20 40 20 10 60
15 10 25
51 11 251 31 11
21 41 21 11 61

У меня ответ 1410, у вас -- 1430.

Попробую разобрать тестовый пример вручную. Итак.
На 1-ю строку будет потрачено 575 квантов (перемещения 50+40+240+220+20=570, чтения 5).
При этом по условию контроллер "одновременно" с чтением с диска "следит за таймаутом, и, по истечении оного, читает следующую порцию входной очереди". То есть, каждые 100 квантов читается строка очереди. Ограничений на длину очереди не наложено.
Следовательно, уже при обработке первой строки вся очередь из 5 строк будет находиться в памяти контроллера: 2-я строка была считана на отметке 100 квантов, 3 -- 200, 4 -- 300, 5 -- 400.
На 2-ю строку очереди будет потрачено 115 квантов (перемещения 10+20+20+10+50=110, чтения 5).
На 3-ю строку очереди будет потрачено 68 квантов (перемещения 45+5+15=65, чтения 3).
На 4-ю строку очереди будет потрачено 551 квантов (перемещения 26+40+240+220+20=546, чтения 5).
На 5-ю строку очереди будет потрачено 115 квантов (перемещения 10+20+20+10+50=110, чтения 5).
Итого: 1424 кванта.

Теперь вопрос, где же ошибка/ошибки?


ps. Это самый "быстрый" вариант, если предположить, что контроллер читает очередь в моменты кратные 100 квантам только если не занят другими делами, то время увеличится.
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01

Re: Задача 53-г. Глупый винчестер.

Сообщение Paster Fob » 28.02.2013 11:33:29

Oleg_D писал(а): У меня ответ 1410, у вас -- 1430

bormant писал(а):Итого: 1424 кванта.

Oleg_D Результат работы моей программы = 1424. Не знаю почему вы написали 1430.Я писал в FPC.
Аватара пользователя
Paster Fob
постоялец
 
Сообщения: 188
Зарегистрирован: 22.02.2011 21:53:36
Откуда: Новосибирск.

Re: Задача 53-г. Глупый винчестер.

Сообщение Oleg_D » 28.02.2013 12:09:47

bormant писал(а):Итого: 1424 кванта.

Да, точно. Нашёл у себя ошибку, спасибо!
Кстати говоря, период опроса входной очереди здесь роли не играет, но он проявляется в следующей задаче об "умном" винчестере, потому и введён тут заранее.
Paster Fob писал(а):Oleg_D Результат работы моей программы = 1424. Не знаю почему вы написали 1430.Я писал в FPC.

Интересно. А я проверял в Дельфаке. Видно тот неверный оператор, что я указал, разными компиляторами по разному трактуется.
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

Re: Задача 53-г. Глупый винчестер.

Сообщение Paster Fob » 28.02.2013 12:43:03

Я написал заготовку для программы,которую привёл ранее,проверил на работоспособность.Посчитал на листке и моя программа выдала такой же результат.Затем я заглянул в ответы что бы сравнить решение,скопировал текст вашего варианта и запустил,но результат был другим.Поэтому я и создал эту тему,думая что не правильно понял задание.
Вот он конечный продукт:
Код: Выделить всё
var
  start,track:byte;
  i,timeout,n:byte;
  que:string;
  kwant:integer;
  f:text;

procedure PutInQue;
begin
  if not eof(f) then begin
    while not eoln(f) do begin
      read(f,n);
      que:=que+chr(n);
    end;
    readln(f);
  end;
end;

procedure GetFromQue;
begin
  delete(que,1,1);
  inc(kwant);
  if kwant mod timeout=0 then
    PutInQue;
end;

procedure ProcessQue;
begin
  while length(que)>0 do begin
    track:=ord(que[1]);
    while start<>track do begin
      if track>start then
        inc(start)
      else if track<start then
        dec(start);
      inc(kwant);
      if kwant mod timeout=0 then
        PutinQue;
    end;
    GetfromQue;
  end;
end;

begin
  assign(f,'C:\Files for Program Pascal\Disk.in');
  reset(f);
  read(f,timeout);
  readln(f);
  kwant:=0; start:=0;
  que:='';
  PutinQue;
  ProcessQue;
  close(f);
  writeln('Результат : ',kwant);
  readln;
end.
Последний раз редактировалось Paster Fob 28.02.2013 13:05:51, всего редактировалось 1 раз.
Аватара пользователя
Paster Fob
постоялец
 
Сообщения: 188
Зарегистрирован: 22.02.2011 21:53:36
Откуда: Новосибирск.

Re: Задача 53-г. Глупый винчестер.

Сообщение bormant » 28.02.2013 12:45:28

Если кому-то интересно накиданное на коленке для проверки решение (без контроля входных параметров и обработки ошибок):
Код: Выделить всё
const
  TIME_MOVE = 1;
  TIME_READ = 1;

type
  THDDState = record
    Queue: Text;
    TimeOut: Word;
    Line, Time: LongInt;
    Head: Byte;
  end;
 
procedure InitHDD(var hdd: THDDState; aQueueName: String);
begin
  FillChar(hdd, SizeOf(hdd), 0);
  with hdd do begin
    Assign(Queue, aQueueName);
    ReSet(Queue);
    ReadLn(Queue, TimeOut);
  end;
end;

procedure DoneHDD(var hdd: THDDState);
begin
  Close(hdd.Queue);
end;

procedure DeqLine(var hdd: THDDState);
var
  track: byte;
begin
  with hdd do begin
    if Line * TimeOut > Time then Time := Line * TimeOut;
    while not SeekEoLn(Queue) do begin
      Read(Queue, track);
      Inc(Time, abs(track - Head) * TIME_MOVE + TIME_READ);
      Head := track;
    end;
    ReadLn(Queue);
    Inc(Line);
  end;
end;

var
  hdd: THDDState;

begin
  InitHDD(hdd, 'hdd.txt');
  while not EoF(hdd.Queue) do DeqLine(hdd);
  WriteLn('Total: ', hdd.Time);
  DoneHDD(hdd);
end.
hdd.txt
Код: Выделить всё
100
50 10 250 30 10
20 40 20 10 60
15 10 25
51 11 251 31 11
21 41 21 11 61
Прогон:
Код: Выделить всё
Total: 1424

В отличии от симулирования поквантового течения времени это решение использует прямой подсчёт затраченного времени, для учёта таймаутов опирается на номер строки в файле.

Добавлено спустя 16 минут 25 секунд:
И вариант с отключаемой отладочной печатью:
Код: Выделить всё
{$DEFINE DEBPRINT}
const
  TIME_MOVE = 1;
  TIME_READ = 1;
{$IFDEF DEBPRINT}
  Tracing: Boolean = True;
{$ENDIF}

type
  THDDState = record
    Queue: Text;
    TimeOut: Word;
    Line, Time: LongInt;
    Head: Byte;
  end;

procedure InitHDD(var hdd: THDDState; aQueueName: String);
begin
  FillChar(hdd, SizeOf(hdd), 0);
  with hdd do begin
    Assign(Queue, aQueueName);
    ReSet(Queue);
    ReadLn(Queue, TimeOut);
    {$IFDEF DEBPRINT}
    if Tracing then WriteLn(stderr, '* Queue timeout: ', TimeOut);
    {$ENDIF}
  end;
end;

procedure DoneHDD(var hdd: THDDState);
begin
  Close(hdd.Queue);
end;

procedure DeqLine(var hdd: THDDState);
var
  track: byte;
begin
  with hdd do begin
    if Line * TimeOut > Time then begin
      {$IFDEF DEBPRINT}
      if Tracing then WriteLn(stderr, '* ', Line, ',', Time, ': Timeout to ', Line * TimeOut);
      {$ENDIF}
      Time := Line * TimeOut;
    end;
    while not SeekEoLn(Queue) do begin
      Read(Queue, track);
      {$IFDEF DEBPRINT}
      if Tracing then WriteLn(stderr, '* ', Line, ',', Time, ': ', Head, '->', track, ', ', abs(track - Head) * TIME_MOVE, '+', TIME_READ);
      {$ENDIF}
      Inc(Time, abs(track - Head) * TIME_MOVE + TIME_READ);
      Head := track;
    end;
    ReadLn(Queue);
    Inc(Line);
  end;
end;

var
  hdd: THDDState;

begin
  InitHDD(hdd, 'hdd.txt');
  while not EoF(hdd.Queue) do DeqLine(hdd);
  WriteLn('Total: ', hdd.Time);
  DoneHDD(hdd);
end.
На "облегчённой" очереди:
Код: Выделить всё
100
50
20 40 20 10 60
15 10 25
51 11 251 31 11
21 41 21 11 61
получается что-то вроде:
Код: Выделить всё
* Queue timeout: 100
* 0,0: 0->50, 50+1
* 1,51: Timeout to 100
* 1,100: 50->20, 30+1
* 1,131: 20->40, 20+1
* 1,152: 40->20, 20+1
* 1,173: 20->10, 10+1
* 1,184: 10->60, 50+1
* 2,235: 60->15, 45+1
* 2,281: 15->10, 5+1
* 2,287: 10->25, 15+1
* 3,303: 25->51, 26+1
* 3,330: 51->11, 40+1
* 3,371: 11->251, 240+1
* 3,612: 251->31, 220+1
* 3,833: 31->11, 20+1
* 4,854: 11->21, 10+1
* 4,865: 21->41, 20+1
* 4,886: 41->21, 20+1
* 4,907: 21->11, 10+1
* 4,918: 11->61, 50+1
Total: 969
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01

Re: Задача 53-г. Глупый винчестер.

Сообщение Oleg_D » 28.02.2013 13:30:15

Paster Fob писал(а):Вот он конечный продукт:

К сожалению, в этом решении свалены в кучу работа с очередью и подсчёт времени.
bormant писал(а):В отличии от симулирования поквантового течения времени это решение использует прямой подсчёт затраченного времени, для учёта таймаутов опирается на номер строки в файле.

Идея понятна. Действительно, задачу можно решать проще. Но здесь я целился в будущее, на более сложную задачу с "умным" винчестером, поэтому мой вариант решения реализован именно как модель винчестера. Вот моё исправленное решение.
Код: Выделить всё
var F: Text;  { входной файл,
                в первой строке - период опроса входной очереди,
                в последующих - списки запросов }
    Period: integer;        { период опроса входной очереди }
    TimeOut: integer;       { таймаут чтения входной очереди }
    Track: integer;         { текущий запрос из внутренней очереди }
    Position: integer;      { текущая позиция головки }
    ProgramResult: integer; { общее время работы программы }

{----------------------------------------------------------}
{ Постановка в очередь и извлечение из нее }

var Que: string;  { очередь }

procedure PutInQue(aTrack: integer); { Постановка в очередь }
begin
  Que:= Que + Char(aTrack);   { добавляем в конец строки}
end;

function GetFromQue: integer;  { Выбор из очереди }
begin
  if Length(Que) = 0         { если очередь пуста }
    then GetFromQue:= -1
    else begin
      GetFromQue:= Ord(Que[1]); { возвращаем первый элемент }
      Delete (Que, 1, 1);         { и удаляем его из очереди }
    end
end;

{----------------------------------------------------------}
{ Проверка истечения таймаута
и чтение очередной порции запросов из строки файла }

procedure TimeOutHandler;
var N: integer;
begin
  if TimeOut>0 then begin
    Inc(ProgramResult);    { общее время }
    Dec(TimeOut);
  end;
  if TimeOut=0 then begin
      TimeOut:= Period;
     { Если истек таймаут, читаем порцию из файла }
      if not EoF(F) then begin
        while not Eoln(F) do begin
          Read(F, N);
          PutInQue(N)
        end;
        Readln(F);
      end;
  end;
end;
{----------------------------------------------------------}
{ Обработка запроса на чтение-запись дорожки }

procedure QueryHandler(aTrack: integer);
begin
  Write(aTrack:4);
  { продвигаем головку в требуемую позицию }
  while Position<>aTrack do begin
    if Position<aTrack
      then Inc(Position)
      else Dec(Position);
    TimeOutHandler;  { таймаут чтения из файла }
  end;
  { Один квант тратим на чтение-запись }
  TimeOutHandler;    { таймаут чтения из файла }
end;

{----------------------------------------------------------}

begin   { Main }
  Writeln('a_53_4');
  ProgramResult:=0;     { Общее время }
  Position:=0;          { позиция головки }
  TimeOut:= 0;          { таймаут }
  Que:='';              { внутренняя очередь пуста }
  Assign(F, 'Disk.in'); Reset(F);
  Readln(F,Period); { в первой строке – период опроса очереди }
  repeat
    Track:= GetFromQue;   { извлекаем из внутр. очереди }
    if Track>=0
      then QueryHandler(Track)  { выполнить запрос }
      else if Eof(F)    { если входной файл пуст }
             then Break { то выход }
             else TimeOutHandler;{ а иначе отрабатываем таймаут
                                и читаем строку файла }
  until false;
  Writeln;
  Write('Result= ',ProgramResult); Readln;
end.
Последний раз редактировалось Oleg_D 28.02.2013 18:54:15, всего редактировалось 1 раз.
Причина: Ошибка в программе
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36

Re: Задача 53-г. Глупый винчестер.

Сообщение bormant » 28.02.2013 15:17:45

Oleg_D писал(а):
Код: Выделить всё
    Track:= GetFromQue;   { извлекаем из внутр. очереди }
    if Track>0
Пожалуй, имелось в виду
Код: Выделить всё
    Track:= GetFromQue;   { извлекаем из внутр. очереди }
    if Track>=0
ведь допустимые номера треков 0..255, а признак пустой очереди -1.
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01

Re: Задача 53-г. Глупый винчестер.

Сообщение Oleg_D » 28.02.2013 15:59:37

bormant писал(а):ведь допустимые номера треков 0..255, а признак пустой очереди -1.

Совершенно верно, исправляю, спасибо!

Добавлено спустя 17 часов 48 минут 3 секунды:
Oleg_D писал(а):К сожалению, в этом решении свалены в кучу работа с очередью и подсчёт времени.

Добавлю к этому ещё пару слов для новичков.
Освоив конструкции языка (операторы, типы данных и т.п.) и написав первые монолитные программы, новичок должен работать в направлении развития архитектурных навыков. Здесь я бы выделил три стадии:
1) научиться рационально выделять в программе процедуры и функции;
2) освоить рациональное разбиение программы на модули;
3) овладеть объектно-ориентированным программированием.

Что значит «рационально»? Это когда отдельные процедуры, функции, модули и объекты связаны между собой в минимальной степени (в идеале – независимы). И каждый такой блок должен выполнять лишь свою роль, и не «совать нос» в чужие дела. Пример из обихода: в доме мы пользуемся разной мебелью и бытовой техникой, можем менять её произвольно и передвигать. А теперь представьте, что кто-то вздумал сблокировать в единую неразборную конструкцию телевизор, кофеварку и кресло. А что? Удобно получается: смотришь телек, развалясь в кресле и попивая кофеёк! Или не согласны с этой идеей? Тогда не скрещивайте телевизор с кофеваркой.
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36


Вернуться в Книга "Песни о Паскале"

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

Рейтинг@Mail.ru
cron