На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
Название темы должно быть информативным !
Прежде чем задать вопрос, воспользуйтесь Поиском. и проверьте в FAQ (ЧАВО) Паскаля
Чтобы получить вразумительный ответ, подробно опишите проблему: что надо сделать, что не получается и номер ошибки (если есть), которую выводит компилятор.
Для вставки кода ваших программ используйте, пожалуйста, кнопку СODE=pas или выпадающий список СODE для других языков (подсветка синтаксиса).
[!] Как правильно задавать вопросы | Руководство по языку B.Pascal 7 & Objects/LR | Borland Pascal. Руководство пользователя
Модераторы: volvo877
  
> Счетчик количества операций со стеком
Есть код реализующий сортировку стека и к нему надо сделать счетчик операций со стеком, счетчик я реализовал, но у меня есть ощущения что не правильно. Буду благодарен если укажите на ошибки и подскажите.

ExpandedWrap disabled
    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.
Цитата dark_siders150 @
счетчик я реализовал, но у меня есть ощущения что не правильно

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

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

Когда ответите на вопросы, станет яснее что вам надо.
Сообщение отредактировано: VisualProg -
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
мне одногрупник скинул пример счетчика на своей программе, которая сортирует очередь с одной головой и я по нему делал счетчик, то бишь присваивание это одна операция, если присваиваются указатели 2-3 и так далее,но у меня слишком большие цифры в счетчике
ExpandedWrap disabled
    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.
Что это за числа?? Что они значат?
Всё стало ещё запутаннее... Узнайте у вашего преподавателя, что ему надо за счётчик, вы делаете явно что то непонятное. Вам нужно число операций над стеком? Или число операций ассемблера? Число математических операций? Почему a^.info:=x; - дают число 2?

Добавлено
В вашем примере всего 6 базовых операций со стеком. Каждая операция - должна увеличивать счётчик на 1 единицу. Это всё будет называться счётчик операций со стеком. Вы же, считаете что то другое.
Сообщение отредактировано: VisualProg -
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
судя по таблице к заданию мне нужно сделать счетчик операций со стеком(nop)
Сообщение отредактировано: dark_siders150 -
Цитата dark_siders150 @
счетчик операций со стеком(nop)

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

ExpandedWrap disabled
    Stack := CreateStack(1000);
    PrintStack(Stack);
    SortStack(Stack);
    PrintStack(Stack);


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

Если под стеком подрузомевается - раздел памяти, то задание становится очень проблематичным...
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
Цитата VisualProg @

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

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

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

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

Машинный nop? Как вы себе это представляете?
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
Цитата VisualProg @
Машинный nop

вот все задание. В рамках курсовой работы по дисциплине «Структуры и алгоритмы обработки данных» требуется программно реализовать абстрактный тип данных (АТД) в соответствии с заданием. Абстрактный тип данных должен позволять осуществлять только операции, присущие типу линейного связанного списка: получить значение первого элемента (на выходе), добавить элемент (в конец списка), удалить элемент из списка (на выходе), проверить – список пуст, обнулить (проинициализировать) список. Используя разработанный АТД и указанный набор операций, необходимо реализовать заданный алгоритм сортировки последовательности динамических элементов.
Реализацию алгоритма осуществить на языке Паскаль или Си.
На основе предложенной в рамках курсовой работы программы получить аналитическую оценку трудоемкости работы алгоритма сортировки, используя О-символику.
Мой одногрупник счетчик сделал так как во 2м коде и ему работу зачли.
Покажите, где здесь сказано хоть слово о счётчиках выполненных операций?
+ В вашем коде я не вижу абстракций. Ни хаков на абстракции, ни прямой абстракции данных. Всё конкретно, и всё уже реализовано.
Сообщение отредактировано: VisualProg -
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
Цитата VisualProg @
Покажите, где здесь сказано хоть слово о счётчиках выполненных операций?

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

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

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

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

Есть подозрения, что вы хотите математическим путём выявить, насколько увеличение входной последовательности элементов стека увеличивают время сортировки/количество операций, необходимых для сортировки. Но, всё равно, звучит сомнительно...
CyberLock | BloodBath-LAN
Немного творчества - альбом ArtMetal [Metal, Instrumental, Orchestral]
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script Execution time: 0,1473 ]   [ 19 queries used ]   [ Generated: 25.04.18, 18:26 GMT ]