Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.130.31] |
|
Сообщ.
#1
,
|
|
|
Есть код реализующий сортировку стека и к нему надо сделать счетчик операций со стеком, счетчик я реализовал, но у меня есть ощущения что не правильно. Буду благодарен если укажите на ошибки и подскажите.
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. |
Сообщ.
#2
,
|
|
|
Цитата dark_siders150 @ счетчик я реализовал, но у меня есть ощущения что не правильно Если у вас есть подозрения, значит вы не до конца понимаете что пишите. Исправляйте эти моменты. 1. Зачем счётчик меняете сразу на 10, 13, 2, или 3? Что это за мистические числа? 2. Зачем делать глобальный счётчик? То есть, изначально, задача стояла сделать счётчик операций всех экземпляров классов стека? 3. Я не силён в паскале, и не знаю, есть ли в нём классы. Если нет, тогда, почему бы не инкапсулировать всё по максимуму в структуры/записи? А то слишком много "стороннего" мусора в глобальной области видимости... Когда ответите на вопросы, станет яснее что вам надо. |
Сообщ.
#3
,
|
|
|
мне одногрупник скинул пример счетчика на своей программе, которая сортирует очередь с одной головой и я по нему делал счетчик, то бишь присваивание это одна операция, если присваиваются указатели 2-3 и так далее,но у меня слишком большие цифры в счетчике
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. |
Сообщ.
#4
,
|
|
|
Что это за числа?? Что они значат?
Всё стало ещё запутаннее... Узнайте у вашего преподавателя, что ему надо за счётчик, вы делаете явно что то непонятное. Вам нужно число операций над стеком? Или число операций ассемблера? Число математических операций? Почему a^.info:=x; - дают число 2? Добавлено В вашем примере всего 6 базовых операций со стеком. Каждая операция - должна увеличивать счётчик на 1 единицу. Это всё будет называться счётчик операций со стеком. Вы же, считаете что то другое. |
Сообщ.
#5
,
|
|
|
судя по таблице к заданию мне нужно сделать счетчик операций со стеком(nop)
|
Сообщ.
#6
,
|
|
|
Цитата dark_siders150 @ счетчик операций со стеком(nop) Стек это коллекция? Если да, то просто в каждом операторе: push, pop, CreateStack, PrintStack, ClearStack, SortStack - добавить увеличение счётчика на единицы. Таким образом, совершив 4 действия над стеком: Stack := CreateStack(1000); PrintStack(Stack); SortStack(Stack); PrintStack(Stack); Мы получим в счётчике 4. Потому что действия над стеком было совершено 4 раза. По мне, всё логично. Если под стеком подрузомевается - раздел памяти, то задание становится очень проблематичным... |
Сообщ.
#7
,
|
|
|
Цитата VisualProg @ Если под стеком подрузомевается - раздел памяти, то задание становится очень проблематичным... скорее второе, так как в задании надо найти оценку трудоемкости работы алгоритма сортировки, используя О-символику. Нужно найти nop и потом еще проводить расчеты |
Сообщ.
#8
,
|
|
|
Цитата dark_siders150 @ скорее второе, так как в задании надо найти оценку трудоемкости работы алгоритма сортировки, используя О-символику Это два никак не связанных между собой задания. Я как раз, склоняюсь к тому, что от вас просили первый вариант. Никто не сможет наверняка сказать что там в машинном коде получится (нужно знать процессор, ОС, компилятор), либо делать дизасм. Это всё не похоже на учебные задания, и они вообще не несут смысла, как такового, ни в учебных целях, ни в практических... По трудоёмкости - у вас два вложенных цикла. Цитата Нужно найти nop Машинный nop? Как вы себе это представляете? |
Сообщ.
#9
,
|
|
|
Цитата VisualProg @ Машинный nop вот все задание. В рамках курсовой работы по дисциплине «Структуры и алгоритмы обработки данных» требуется программно реализовать абстрактный тип данных (АТД) в соответствии с заданием. Абстрактный тип данных должен позволять осуществлять только операции, присущие типу линейного связанного списка: получить значение первого элемента (на выходе), добавить элемент (в конец списка), удалить элемент из списка (на выходе), проверить – список пуст, обнулить (проинициализировать) список. Используя разработанный АТД и указанный набор операций, необходимо реализовать заданный алгоритм сортировки последовательности динамических элементов. Реализацию алгоритма осуществить на языке Паскаль или Си. На основе предложенной в рамках курсовой работы программы получить аналитическую оценку трудоемкости работы алгоритма сортировки, используя О-символику. Мой одногрупник счетчик сделал так как во 2м коде и ему работу зачли. |
Сообщ.
#10
,
|
|
|
Покажите, где здесь сказано хоть слово о счётчиках выполненных операций?
+ В вашем коде я не вижу абстракций. Ни хаков на абстракции, ни прямой абстракции данных. Всё конкретно, и всё уже реализовано. |
Сообщ.
#11
,
|
|
|
Цитата VisualProg @ Покажите, где здесь сказано хоть слово о счётчиках выполненных операций? В примере расчета курсовой показано что надо найти nop и расчитать С1..Сn |
Сообщ.
#12
,
|
|
|
VisualProg
nop он называет число операций |
Сообщ.
#13
,
|
|
|
Цитата MBo @ nop он называет число операций Спасибо за перевод) Тогда ТС нужно предоставлять словарь с объяснением части терминов которые он употребляет, чтобы не было недопониманий. Цитата dark_siders150 @ В примере расчета курсовой показано что надо найти nop и расчитать С1..Сn Есть подозрения, что вы хотите математическим путём выявить, насколько увеличение входной последовательности элементов стека увеличивают время сортировки/количество операций, необходимых для сортировки. Но, всё равно, звучит сомнительно... |