Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача о стеках

Автор: Murderer 3.04.2007 22:39

Даны три стека, наполненные натуральными числами и четвертый стек пустой. В четвертый стек поместить три числа, являющиеся максимальными числами в первом, втором и третьем стеке. В четвертом стеке числа расположить в порядке неубывания, а в первых трех стеках порядок расположения оставшихся чисел оставить прежним.

Т.е. я понимаю так: через пробел в программе вводится числа в первый стек и нуль завершает ввод, потом второй и соответственно третий стек. Затем программа выводит три максимальных числа из каждого стека в порядке неубывания.

Уже которую неделю парюсь и все безуспешно... Ну не могу понять я эти стеки.

Автор: klem4 3.04.2007 22:41

http://forum.pascal.net.ru/index.php?showtopic=2706&st=0&p=23592&#entry23592

Тут был ?

Автор: Murderer 3.04.2007 22:50

Там то я был... но мозг видать у меня не может понять или не хочет....

Вот алгоритм решения я знаю.
Сначала из каждого стека находим максимальный элемент. Например, берем первый элемент и записываем его в max и кидаем в 4-й стек... берем сл. элемент и сравниваем с max... если выбранный меньше max, то кидаем его в 4-й стек, а если больше max, то записываем его в max и кидаем в четвертый стек... тем самым находим максимальные элементы в каждом стеке используя 4-й стек... далее идет этап сортировки 3-х максимальных элементов в порядке неубывания... тут я уже затрудняюсь. наверное тут 4-мя стеками не обойтись... видать 5-й стек подключать надо

Автор: volvo 4.04.2007 2:23

Цитата
наверное тут 4-мя стеками не обойтись... видать 5-й стек подключать надо
Можно обойтись четырьмя...

Сначала проходишь по каждому стеку, и находишь максимум в них (простым перекидыванием данных из одного в другой, и запоминанием количества перекинутых элементов), максимум заносится в четвертый стек... А потом из 4-го выбрасываешь элементы в первые 3 (по одному в каждый), и простыми сравнениями определяешь, какой из элементов минимальный, какой средний, а какой максимальный, и заносишь их обратно в четвертый стек в соответствующем порядке...

Как у тебя стеки-то реализованы?

Автор: Murderer 4.04.2007 9:40

Вот именно что никак. У меня даже кода программного нет. Жалко что подфорум про задачи на заказ закрыли временно, а то я готов деньги отдать за решение данной задачи

Автор: klem4 4.04.2007 11:08

type

TData = Integer;

PTListItem = ^TlistItem;

TListItem = Record
data: TData;
next: PTListItem;
end;

TList = Object

head: PTListItem;

constructor Create;
destructor Destroy;

procedure Push(const data: TData);

procedure GenerateRandomList(const count, rnd: integer);

procedure PrintList;

function FindMax: Integer;


end;

constructor TList.Create;
begin
head := nil;
end;

destructor TList.Destroy;
var
H, T: PTListItem;
begin
H := head;
while (H <> nil) do begin
T := H;
H := H^.Next;
Dispose(T);
end;
end;

procedure TList.Push(const data: TData);
var
T, H: PTListItem;
begin
New(T);
T^.data := data;
T^.Next := nil;

H := Head;

if Head = nil then Head := T else begin
while (Head^.Next <> nil) do Head := Head^.Next;
Head^.Next := T;
Head := H;
end;
end;

procedure TList.PrintList;
var
H: PTListItem;
begin
H := Head;
while (Head <> nil) do begin
writeln(Head^.Data);
Head := Head^.Next;
end;
Head := H;
end;

procedure TList.GenerateRandomList(const count, rnd: Integer);
var
i: Integer;
begin
for i := 1 to count do Push(random(rnd));
end;

function TList.FindMax: Integer;
var
H: PTListItem;
max: TData;
begin
H := Head;
max := -MaxInt;
while (Head <> nil) do begin
if Head^.Data > max then max := Head^.Data;
Head := Head^.Next;
end;
Head := H;
FindMax := max;
end;

var
L: Array [1..4] of TList;
M: Array [1..3] of TData;

i, j, T: Integer;
begin
randomize;

for i := 1 to 3 do begin
L[i].Create;
L[i].GenerateRandomList(Random(5) + 1, Random(10) + 1);
writeln('List#', i);
L[i].PrintList;
M[i] := L[i].FindMax;
end;

for i := 3 downto 2 do
for j := 1 to i - 1 do
if M[j] <= M[j + 1] then begin
T := M[j]; M[j] := M[j + 1]; M[j + 1] := T;
end;

for i := 1 to 3 do L[4].Push(M[i]);

writeln('List#4');

L[4].PrintList;

for i := 1 to 4 do L[i].Destroy;
end.

Автор: volvo 4.04.2007 14:10

klem4, список <> стек ... Вся сложность-то как раз в том, что стеке ты имеешь право только на обращение к первому элементу, все остальные тебе не доступны... Да и про доп. массивы тоже речи не было...

Автор: klem4 4.04.2007 14:19

Цитата
Вся сложность-то как раз в том, что стеке ты имеешь право только на обращение к первому элементу, все остальные тебе не доступны...


И соответственно после обращения этот элемент из стека удаляется, верно ?

Автор: volvo 4.04.2007 14:26

Смотря какую операцию вызывать... Может, удаляется (если вызывать Pop, но тогда ты его имеешь в переменной, и можешь с ним делать все, что захочешь), а может и нет - есть же еще Top, о котором все забывают почему-то (просто просмотр элемента на верхушке стека)...

Автор: klem4 4.04.2007 16:37

Вот что пока выходит:

Добваляем ф-ю Pop, изменяему процедуру Push на функцию и переписываем FindMax:

// заталкивае элемент в стек и возвращает указатель на него
function TList.Push(const data: TData): PTListItem;
var
T, H: PTListItem;
begin
New(T);
T^.data := data;
T^.Next := nil;

H := Head;

if Head = nil then Head := T else begin
while (Head^.Next <> nil) do Head := Head^.Next;
Head^.Next := T;
Head := H;
end;

Push := T;
end;

// выталкивает элемент из стека и возвращает его значение
function TList.Pop: Integer;
var
T: PTListItem;
begin
if Head <> nil then begin
T := Head;
Pop := Head^.Data;
Head := Head^.Next;
Dispose(T);
end;
end;

// ищем максимальный элемент
function TList.FindMax: Integer;
var
BACK: PTListItem;
max, temp: TData;
begin
if Head <> nil then begin
max := Pop; { берем значение 1-го элемента в стеке, выталкаваем его }
BACK := Push(max); { кладем это значение в конец стека, запоминаем адрес этого элемента }
while (Head <> BACK) do begin { пока не дошли до этого элемента }
temp := Pop; { выталкивае следующее значение }
if temp > max then max := temp; { сравниваем }
Push(temp); { заталкиваем обратно }
end;
end;
FindMax := Max;
end;


Автор: volvo 4.04.2007 16:59

Вариант №2:

type
ttype = integer;

ptitem = ^titem;
titem = object
info: ttype;
next: ptitem;

constructor init(x: ttype; nxt: ptitem);
destructor done;
end;

constructor titem.init(x: ttype;
nxt: ptitem);
begin
info := x;
next := nxt
end;
destructor titem.done;
begin end;

type
pttype = ^ttype;
tstack = object
head: ptitem;

constructor init;
destructor done;

procedure push(x: ttype);
function pop: ttype;
function top: ttype;

function empty: boolean;

procedure print;
end;

constructor tstack.init;
begin
head := nil;
end;
destructor tstack.done;
begin
while not empty do pop
end;

procedure tstack.push(x: ttype);
var p: ptitem;
begin
new(p, init(x, head));
head := p
end;

function tstack.pop: ttype;
var p: ptitem;
begin
pop := -1;
if not empty then begin
p := head;
head := head^.next;

pop := p^.info;
dispose(p, done);
end
else begin
writeln('reading from empty stack');
halt(101)
end;
end;

function tstack.top: ttype;
begin
if empty then top := maxInt
else top := head^.info;
end;

function tstack.empty: boolean;
begin
empty := not assigned(head)
end;

procedure tstack.print;
var p: ptitem;
begin
p := head;
write('(stack) <');
while assigned(p) do begin
write(p^.info, ' ');
p := p^.next
end;
writeln('>')
end;

procedure sort_stack(var st: tstack);

var changed: boolean;

procedure deface(var new_st: tstack; next: ttype);
var X: ttype;
begin
if not new_st.empty then begin
X := new_st.pop;
deface(new_st, X);
end;

if new_st.top < next then begin
X := new_st.pop;
new_st.push(next);
new_st.push(X);
changed := true;
end
else new_st.push(next);
end;

begin
repeat
changed := false;
deface(st, st.pop);
until not changed;
end;


function max_stack(var st: tstack): ttype;

var max_value: ttype;

procedure deface(var new_st: tstack; next: ttype);
var X: integer;
begin
if not new_st.empty then begin
X := new_st.pop;
if max_value < X then max_value := X;
deface(new_st, X);
end;
new_st.push(next);
end;

begin
max_value := st.top;
deface(st, st.pop);
max_stack := max_value;
end;

var
st_arr: array[1 .. 4] of tstack;
i, j: integer;

begin
for i := 1 to 3 do begin
st_arr[i].init;
for j := 1 to random(10) + 10 do
st_arr[i].push(random(1000));
end;

st_arr[4].init;
for i := 1 to 3 do begin
writeln('#', i); st_arr[i].print;
st_arr[4].push(max_stack(st_arr[i]));
end;

sort_stack(st_arr[4]);
writeln('#4'); st_arr[4].print;
end.

Автор: Murderer 4.04.2007 21:44

Спасибо вам огромное! Не ожидал. А как сделать так, чтобы в программе числа вводить? А то вылетает программа

Автор: Murderer 4.04.2007 23:33

Простите. Просто я начинающий в паскале и сейчас его упорно изучаю. Куда элементы стека вводить? Подскажите пожалуйста!

Автор: volvo 4.04.2007 23:46

В той программе, которую я тебе привел, в стек заносятся случайные числа, причем их количество тоже случайно... Если хочешь вводить самостоятельно -

  for i := 1 to 3 do begin
st_arr[i].init;
for j := 1 to random(10) + 10 do
st_arr[i].push(random(1000));
end;


замени на

  for i := 1 to 3 do begin
st_arr[i].init;
k := random(10) + 10;
writeln('stack #', i, ' -> ', k, ' elements ...');
for j := 1 to k do begin
write(' -> '); readln(X); st_arr[i].push(X);
end;
end;
и опиши еще переменные k, X рядом с i, j ...

А чтобы увидеть результаты выполнения программы, перед последним End. добавь ReadLn ...

Автор: Murderer 5.04.2007 0:47

Цитата(volvo @ 4.04.2007 22:46) *

А чтобы увидеть результаты выполнения программы, перед последним End. добавь ReadLn ...

Этому меня еще в школе обучили. Я потом вспомнил. Спасибо!


Автор: Murderer 5.04.2007 18:45

А вот в приведенной программе как сделать так, чтобы не код задавал количество элементов в стеках, а самому в программе вводить нужное тебе количество элементов?
Я попробовал убрать строчку с рандомом где k. У меня не вышло. Друзья тоже не смогли это сдлеать.

Автор: volvo 5.04.2007 18:57

  for i := 1 to 3 do begin
st_arr[i].init;
write('stack #', i, ': size = '); readln(k);
writeln('enter ', k, ' elements ...');
for j := 1 to k do begin
write(' -> '); readln(X); st_arr[i].push(X);
end;
end;
?

Автор: Murderer 5.04.2007 19:00

Да, я видать глупость сморозил. Я хотел просто вместо 10-ки какую-нибудь переменную ввести... Но программа в таком случае не запускалась

Автор: Murderer 5.04.2007 19:44

Все равно не выходит! Что мне исправить, чтобы в программе я сам вводил нужное мне количество элементов?

Автор: volvo 5.04.2007 21:12

Так... Давай договоримся, ты присоединяешь СВОЮ программу (в смысле, ту, с которой работаешь), а мы ее смотрим... Только в Аттаче, чтобы не надо было ничего копировать никуда, просто откомпилировать и посмотреть, почему и КАК именно она у тебя не работает...

Автор: Murderer 11.04.2007 21:35

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

Автор: volvo 11.04.2007 21:38

Предыдущее сообщение ты проигнорировал?

Хорошо, задам вопрос по другому: исправить ГДЕ? Полную программу приаттачь, а то непонятно, что у тебя собственно не работает. Если делал все, что тебе написали, должно работать...

Автор: Murderer 11.04.2007 21:59

Извини Вольво! Просто очень надо, а я не силен в таких задачах... Вот программа, которая при запуске просит, чтобы я ввел 5 элементов в каждом стеке... я могу сделать, чтобы 6 вводил, 7 и даже 8, но суть в том, чтобы я нужное мне число элементов вводил в программе, а не в КОДе.


Прикрепленные файлы
Прикрепленный файл  STEK_11.PAS ( 2.55 килобайт ) Кол-во скачиваний: 196

Автор: Murderer 11.04.2007 22:36

Там что исправить надо?

Автор: Lapp 16.06.2007 17:15

Цитата(Murderer @ 11.04.2007 18:59) *

чтобы я нужное мне число элементов вводил в программе, а не в КОДе.

Замени строчку:
  k := random(1) + 5;
на такие две:
Write('Введите количество элементов: ');
ReadLn(k);

Кстати, random(1) всегда железно равно нулю. Если хочешь получать случайные числа в диапазоне от 0 до n, используй random(n+1)