Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Pascal > Счетчик количества операций со стеком


Автор: dark_siders150 28.03.18, 10:39
Есть код реализующий сортировку стека и к нему надо сделать счетчик операций со стеком, счетчик я реализовал, но у меня есть ощущения что не правильно. Буду благодарен если укажите на ошибки и подскажите.

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    uses
      SysUtils;
    type
      tItem = ^pItem;
      pItem = record
        n : Integer;
        x : tItem;
      end;
     
    type
      tStack = record
        Items : tItem;
        Empty : boolean;
      end;
     var
     t,t1,t2: TDateTime;
    ch:int64;
    function NewStack : tStack;
    var
      Stack : tStack;
    begin
      Stack.Items := nil;
      Stack.Empty := True;
      NewStack := Stack;
      ch:=ch+5;
    end;
     
    procedure Push(n : Integer; var Stack : tStack);
    var
      tmp : tItem;
    begin
      New(tmp);
      tmp^.n := n;
      tmp^.x := Stack.Items;
      Stack.Items := tmp;
      Stack.Empty := False;
      ch:=ch+10;
    end;
     
    function Pop(var Stack : tStack) : Integer;
    var
      res : Integer;
      tmp : tItem;
    begin
      if Not Stack.Empty then
        begin
          tmp := Stack.Items;
          Stack.Items := Stack.Items^.x;
          Stack.Empty := Stack.Items = nil;
          res := tmp^.n;
          Dispose(tmp);
          ch:=ch+13;
        end;
      Pop := res;
      ch:=ch+2;
    end;
     
    function CreateStack(n : Integer) : tStack;
    var
      Stack : tStack;
    begin
      Stack := NewStack;
      while n > 0 do
        begin
          Push(Random(200)-50, Stack);
          Dec(n);
          ch:=ch+3;
        end;
      CreateStack := Stack;
      ch:=ch+3;
    end;
     
    procedure PrintStack(Stack : tStack);
    var
      tmp : tItem;
    begin
      tmp := Stack.Items;
      if Stack.Empty then
        Write('Стек пуст!')
      else
        while tmp <> nil do
          begin
            Write(#32, tmp^.n); tmp := tmp^.x;
            ch:=ch+2;
          end;
          ch:=ch+3;
      WriteLn;
    end;
     
    procedure ClearStack(var Stack : tStack);
    begin
      while Not Stack.Empty do Pop(Stack);
      ch:=ch+2;
    end;
     
    procedure SortStack(var Stack : tStack);
    var
      swap : Boolean;
      tmpStack : tStack;
      n1, n2 : Integer;
    begin
      if Stack.Empty then Exit;
      tmpStack := NewStack;
      repeat
        swap := False;
        n1 := Pop(Stack);
        while Not Stack.Empty do
          begin
            n2 := Pop(Stack);
            if n1 > n2 then
              begin
                Push(n2, tmpStack); swap := True;
              end
            else
              begin
                Push(n1, tmpStack); n1 := n2;
              end;
              ch:=ch+2;
          end;
        Push(n1, Stack);
        while Not tmpStack.Empty do
          Push(Pop(tmpStack), Stack);
          ch:=ch+3;
      until Not swap;
      ch:=ch+3;
    end;
     
    var
      Stack : tStack;
    begin
      Stack := CreateStack(1000);
      writeln('Не отсортированный стек');
      PrintStack(Stack);
      t1:=now;
      writeln('отсортированный стек');
      SortStack(Stack);
      PrintStack(Stack);
      ClearStack(Stack);
      t2:=now; t:=t2-t1;
      writeln('Время сортировки: ',FormatDateTime('hh:mm:ss.zzz',t));
      write('количество операций со стеком: ',ch);
      readln;
    end.

Автор: VisualProg 28.03.18, 10:56
Цитата dark_siders150 @
счетчик я реализовал, но у меня есть ощущения что не правильно

Если у вас есть подозрения, значит вы не до конца понимаете что пишите. Исправляйте эти моменты.

1. Зачем счётчик меняете сразу на 10, 13, 2, или 3? Что это за мистические числа?
2. Зачем делать глобальный счётчик? То есть, изначально, задача стояла сделать счётчик операций всех экземпляров классов стека?
3. Я не силён в паскале, и не знаю, есть ли в нём классы. Если нет, тогда, почему бы не инкапсулировать всё по максимуму в структуры/записи? А то слишком много "стороннего" мусора в глобальной области видимости...

Когда ответите на вопросы, станет яснее что вам надо.

Автор: dark_siders150 28.03.18, 11:03
мне одногрупник скинул пример счетчика на своей программе, которая сортирует очередь с одной головой и я по нему делал счетчик, то бишь присваивание это одна операция, если присваиваются указатели 2-3 и так далее,но у меня слишком большие цифры в счетчике
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    program Project4;
     
    {$APPTYPE CONSOLE}
     
    uses
      SysUtils;
     
    type ochered=^Rec;
         Rec=record
         info:    integer;
         next:    ochered;
         end;
    var
    head, head1:  ochered;
    n, i, j, z, k,  y, x, x1: integer;
    t,t1,t2: TDateTime;
    ch: int64;
     
    procedure push(var head:ochered; x:integer);  // 6
    var a:        ochered;
    begin
        new(a);                                //+1
        a^.info:=x;                            //+2
        a^.next:=head;                         //+2
        head:=a;                               //+1
        ch:=ch+6;
    end;
     
    procedure pop(var head:ochered; var x:integer);  //8+
    var a, p:     ochered;
    begin
       a:=head;  p:=head; ch:=ch+3;          //+2
           while a^.next<>nil do begin       //+2
             p:=a; a:=a^.next; ch:=ch+4;     //+3
           end;
       x:=a^.info; p^.next:=nil;             //+4
       dispose(a);                           //+1
       ch:=ch+5;
    end;
     
    function empty(head:ochered): boolean;    //2
    begin
       empty:=head=nil;                      //+2
       ch:=ch+2;
    end;
     
    procedure iniz(var head:ochered; var n:integer);  //1+
    var x, i:      integer;
    begin
       for i:= 1 to n do begin
          x:=Random(501)+300;             //+3
          push(head,x);                   //+6
          ch:=ch+9;
       end;
    end;
     
    BEGIN
    ch:=0; //счетчик
    write('Enter the number of items: ');
       readln(n);
       t1:=now;
       head := nil;
    iniz(head,n);
    head1:=nil;
    ch:=ch+6;
     
    For i:= 1 to n-1 do
      For j:= n downto i+1 do begin
        if not empty(head1) then begin  //+3
          head:=head1;                    //+1
          head1:=nil;                     //+1
          ch:=ch+2;
        end;
        ch:=ch+1;
        For z:=1 to j-2 do begin   //1+
           pop(head,y); push(head1,y);//+6+8+
        end;
        ch:=ch+2;
        pop(head,x); pop(head,x1); // 16+2*
        If x>x1 then begin       //+1
          push(head1,x); push(head1,x1);
        end //+12
        else begin
          push(head1,x1); push(head1,x);
        end; //+12
        ch:=ch+1;
        If j<n then begin                    //+1
            For k:= 1 to n-j do begin      //1+
              pop(head,y); push(head1,y);       //+6+8
            end;
            ch:=ch+1;
        end;
        ch:=ch+1;
    end;
     
    For i:= 1 to n do begin
      pop(head1,x);
      writeln('stack[',i,'] = ',x);
      ch:=ch+1;
    end;
    ch:=ch+1;
    t2:=now; t:=t2-t1;
    writeln;
    writeln('Your time: ',FormatDateTime('hh:mm:ss.zzz',t));
    writeln('Num of operations: ',ch);
    readln;
     
      try
        { TODO -oUser -cConsole Main : Insert code here }
      except
        on E: Exception do
          Writeln(E.ClassName, ': ', E.Message);
      end;
     
    end.

Автор: VisualProg 28.03.18, 12:12
Что это за числа?? Что они значат?
Всё стало ещё запутаннее... Узнайте у вашего преподавателя, что ему надо за счётчик, вы делаете явно что то непонятное. Вам нужно число операций над стеком? Или число операций ассемблера? Число математических операций? Почему a^.info:=x; - дают число 2?

Добавлено
В вашем примере всего 6 базовых операций со стеком. Каждая операция - должна увеличивать счётчик на 1 единицу. Это всё будет называться счётчик операций со стеком. Вы же, считаете что то другое.

Автор: dark_siders150 28.03.18, 12:34
судя по таблице к заданию мне нужно сделать счетчик операций со стеком(nop)

Автор: VisualProg 28.03.18, 14:04
Цитата dark_siders150 @
счетчик операций со стеком(nop)

Стек это коллекция? Если да, то просто в каждом операторе: push, pop, CreateStack, PrintStack, ClearStack, SortStack - добавить увеличение счётчика на единицы. Таким образом, совершив 4 действия над стеком:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    Stack := CreateStack(1000);
    PrintStack(Stack);
    SortStack(Stack);
    PrintStack(Stack);


Мы получим в счётчике 4. Потому что действия над стеком было совершено 4 раза. По мне, всё логично.

Если под стеком подрузомевается - раздел памяти, то задание становится очень проблематичным...

Автор: dark_siders150 28.03.18, 14:16
Цитата VisualProg @

Если под стеком подрузомевается - раздел памяти, то задание становится очень проблематичным...

скорее второе, так как в задании надо найти оценку трудоемкости работы алгоритма сортировки, используя О-символику. Нужно найти nop и потом еще проводить расчеты

Автор: VisualProg 28.03.18, 14:29
Цитата dark_siders150 @
скорее второе, так как в задании надо найти оценку трудоемкости работы алгоритма сортировки, используя О-символику

Это два никак не связанных между собой задания. Я как раз, склоняюсь к тому, что от вас просили первый вариант. Никто не сможет наверняка сказать что там в машинном коде получится (нужно знать процессор, ОС, компилятор), либо делать дизасм. Это всё не похоже на учебные задания, и они вообще не несут смысла, как такового, ни в учебных целях, ни в практических...
По трудоёмкости - у вас два вложенных цикла.

Цитата
Нужно найти nop

Машинный nop? Как вы себе это представляете?

Автор: dark_siders150 28.03.18, 14:32
Цитата VisualProg @
Машинный nop

вот все задание. В рамках курсовой работы по дисциплине «Структуры и алгоритмы обработки данных» требуется программно реализовать абстрактный тип данных (АТД) в соответствии с заданием. Абстрактный тип данных должен позволять осуществлять только операции, присущие типу линейного связанного списка: получить значение первого элемента (на выходе), добавить элемент (в конец списка), удалить элемент из списка (на выходе), проверить – список пуст, обнулить (проинициализировать) список. Используя разработанный АТД и указанный набор операций, необходимо реализовать заданный алгоритм сортировки последовательности динамических элементов.
Реализацию алгоритма осуществить на языке Паскаль или Си.
На основе предложенной в рамках курсовой работы программы получить аналитическую оценку трудоемкости работы алгоритма сортировки, используя О-символику.
Мой одногрупник счетчик сделал так как во 2м коде и ему работу зачли.

Автор: VisualProg 28.03.18, 14:40
Покажите, где здесь сказано хоть слово о счётчиках выполненных операций?
+ В вашем коде я не вижу абстракций. Ни хаков на абстракции, ни прямой абстракции данных. Всё конкретно, и всё уже реализовано.

Автор: dark_siders150 28.03.18, 15:12
Цитата VisualProg @
Покажите, где здесь сказано хоть слово о счётчиках выполненных операций?

В примере расчета курсовой показано что надо найти nop и расчитать С1..Сn

Автор: MBo 28.03.18, 16:44
VisualProg

nop он называет число операций

Автор: VisualProg 29.03.18, 06:42
Цитата MBo @
nop он называет число операций

Спасибо за перевод) Тогда ТС нужно предоставлять словарь с объяснением части терминов которые он употребляет, чтобы не было недопониманий.

Цитата dark_siders150 @
В примере расчета курсовой показано что надо найти nop и расчитать С1..Сn

Есть подозрения, что вы хотите математическим путём выявить, насколько увеличение входной последовательности элементов стека увеличивают время сортировки/количество операций, необходимых для сортировки. Но, всё равно, звучит сомнительно...

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)