IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Задача о стеках
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

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

Уже которую неделю парюсь и все безуспешно... Ну не могу понять я эти стеки.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

Тут был ?


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

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


Гость






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

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

Как у тебя стеки-то реализованы?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


Вот именно что никак. У меня даже кода программного нет. Жалко что подфорум про задачи на заказ закрыли временно, а то я готов деньги отдать за решение данной задачи
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






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


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






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


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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



--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Вариант №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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


Спасибо вам огромное! Не ожидал. А как сделать так, чтобы в программе числа вводить? А то вылетает программа
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

Сообщение отредактировано: Murderer -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






В той программе, которую я тебе привел, в стек заносятся случайные числа, причем их количество тоже случайно... Если хочешь вводить самостоятельно -
  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 ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

Сообщение отредактировано: Murderer -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






  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;
?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


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

Сообщение отредактировано: Murderer -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: Арслан

Репутация: -  0  +


Все равно не выходит! Что мне исправить, чтобы в программе я сам вводил нужное мне количество элементов?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гость






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

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 19:46
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name