Задача о стеках Опции

[Murderer]

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

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

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

[klem4]

Все о динамических структурах данных.

Тут был ?

[Murderer]

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

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

[volvo]

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

Можно обойтись четырьмя...

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

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

[Murderer]

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

[klem4]

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]

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

[klem4]

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

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

[volvo]

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

[klem4]

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

Добваляем ф-ю 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]

Вариант №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]

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

[Murderer]

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

Сообщение отредактировано: Murderer - 4.04.2007 19:34

[volvo]

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

  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]

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

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

[Murderer]

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

Сообщение отредактировано: Murderer - 5.04.2007 14:46

[volvo]

  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]

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

Сообщение отредактировано: Murderer - 5.04.2007 15:00

[Murderer]

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

[volvo]

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