Версия для печати темы
Форум «Всё о Паскале» _ Задачи _ Очереди
Автор: Гость_Boris 10.11.2004 0:04
Как видно из задания, задача будет идти о очередях.
Если кто забыл - напоминаю: основное правило очереди - первым вошёл - первым вышел!
Итак. Пусть дан одномерный массив (он задаёт количество элементов).
Задача заключается в следующем: с помощью функций put и get реализовать распечатку текста на экране.
.Например:
get(1)
get(2)
writeln(get)
writeln(get)
Причём если следующая команда get будет превышать массив, то число будет !!!!!записываться
в конец очереди (другой вариант - в начало)!!!!!!!!!!!!
пример:
put(1)
put(2)
put(3)
get
get
get ; здесь массив состоит из 2-х элементов и происходит переполнение ...
ВАЖНО:
функции имеют слежующий вид:
function put(i:integer):boolean; (возвращает false если очередь пуста(по-моему - а может когда переполнение??)
и true, если переполнения нет)
function get:integer;
Вот и всё: ПОМОГИТЕ бедному студенту.!
P.S:
Вот я написал, но при переполнении не то, совсем не то:
Код
uses crt;
const m=10;
var n:array[0..m] of integer;
i,j: integer;
procedure Init;
begin
for i:=1 to m do n[i]:=0;
n[0]:=1;
end;
function put(a:integer):boolean;
begin
put:=false;
if n[0]<=m then
begin
n[n[0]]:=a;
n[0]:=n[0]+1;
put:=true;
end;
end;
function get: integer;
begin
if n[0]>1 then
begin
get:=n[1];
n[0]:=n[0]-1;
for i:=1 to m-1 do
n[i]:=n[i+1];
end;
end;
begin
init;
clrscr;
writeln;
put(1);
put(2);
put(3);
writeln(get);
writeln(get);
put(4);
writeln(get);
writeln(get);
readln;
end.
Автор: volvo 10.11.2004 0:20
Гость_Boris
Цитата
Если кто забыл - напоминаю: основное правило очереди - первым вошёл - первым вышел!
Цитата
Причём если следующая команда get будет превышать массив, то число будет !!!!!записываться в конец очереди (другой вариант - в начало)!!!!!!!!!!!!
Вы же сами себе противоречите! До переполнения очереди - все в порядке. Но как только произошло переполнение, следующий элемент записывается первым, и тут Вы пытаетесь взять элемент из очереди... Что получилось? Нарушилось правило очереди (FIFO), т.к. элемент, который вошел последним, выйдет первым
Решите уже для себя, очередь это или какая-то другая структура данных... С очередями такой трюк не проходит...
Автор: GoodWind 10.11.2004 0:31
Цитата
Но как только произошло переполнение, следующий элемент записывается первым, и тут Вы пытаетесь взять элемент из очереди...
может при переполнении стоит сдвигать очередь вперед, тогда можно обойтись малой кровью (в смысле потеряется только передний элемент очереди) ?
Код
function put(a:integer):boolean;
begin
put:=false;
if n[0]=10 then
begin
for i:=1 to 9 do n[i]:=n[i+1];
n[0]:=9;
end;
if n[0]<m then
begin
n[n[0]]:=a;
n[0]:=n[0]+1;
put:=true;
end;
end;
вот так примерно... не знаю работает или нет, т.к. в набирал прям тут без проверки...
Автор: Гость_Boris 10.11.2004 0:32
Так вот я и прошу переделать программу!
Автор: volvo 10.11.2004 0:41
Цитата
Так вот я и прошу переделать программу!
Поймите, нельзя переделать программу, не зная точного алгоритма
Цитата
в конец очереди (другой вариант - в начало)
Цитата
возвращает false если очередь пуста(по-моему - а может когда переполнение??
это алгоритм?
Автор: Гость_Boris 10.11.2004 0:42
А функцию get тогда как переделать?
Или всё тоже самое оставить????
Добавлено (9.11.04 19:45):
Нет - ээто не алгоритм...
Конкретно: в конец очереди и false - если пусто
Автор: GoodWind 10.11.2004 0:46
Цитата
А функцию get тогда как переделать?
а разве переполненность очереди влияет на get ??
Автор: Гость_Boris 10.11.2004 1:00
Ещё как...а в принципе ... дайте подумать...наврно всё таки нет.
Буду тестить! А вы тестили? КАк ?
Автор: GoodWind 10.11.2004 1:03
Нет не тестил :no:
Предоставлю Вам сию почетную обязанность :yes:
Автор: Гость_Boris 10.11.2004 1:06
Только что тестил ...
при m=3 b
put(1) pu(2) pu(3) pu(4) get get get get
пишет
1
2
4
21463
(странные цифры вылазиют)
Автор: GoodWind 10.11.2004 1:12
дык вы пытаетесь из очереди длиной 3 элемента взять 4 элемента, вот и получается бурда
Автор: Гость_Boris 10.11.2004 1:26
Так я же и говорю: если в друг очередь больше то последний элемент затирается и на его место пишется новый (в моём примере 3 должна затереться
4). А вы как думали?
Автор: volvo 10.11.2004 1:54
Попробуйте так:
Код
const
m = 3;
var
a: array[1 .. m] of integer;
first, last: integer;
overflow: boolean;
{ инициализация очереди }
procedure init;
begin
first := 0; last := 0;
end;
function get: integer;
begin
{ при извлечении из очереди в любом случае
признак переполнения снимается... }
overflow := false;
{ извлекаем всегда первый эпемент }
get := a[1];
{ после извлечения уменьшаем количество элементов в очереди }
if last > 0 then dec(last);
{ и сдвигаем всю очередь на 1 позицию ближе к началу }
move(a[2], a[1], (m - 1)*sizeof(integer));
{ освободившееся место в конце очереди заполняем нулем }
a[m] := 0;
end;
function put(x: integer): boolean;
begin
{ устанавливаем признак переполнения - очередь считается
переполненной, если она уже была переполненной до этой
операции или если указатель конца очереди стоит на
последнем элементе }
overflow := overflow or (last = m);
{ если очередь переполнена, увеличения указатель конца
очереди не происходит, иначе - он увеличивается на 1 }
inc(last, byte(not overflow));
{ и в соответствующую ячейку пишется значение }
a[last] := x;
{ функция возвращает признак переполнения очереди }
put := overflow
end;
var
r: boolean;
begin
init; { вызывать перед началом работы с очередью... }
r := put(1);
r := put(2);
r := put(3);
r := put(4);
writeln(get);
writeln(get);
writeln(get);
r := put(5);
writeln(get);
end.
при переполнении Put возвращает True и последний элемент очереди затирается вновь введенным. Get при попытке чтения из пустой очереди возвращает 0...
Автор: Гость_Boris 10.11.2004 2:33
Спасибо..юработает.
Спасибо большое.
Добавлено (9.11.04 21:42):
Volvo, конечно ты молодец, но можно с подробнми комментариями, пожалуйста,
а то я в чужих программах не разбеоусь никогда.
Если не трудно,Volvo, напиши
Автор: volvo 10.11.2004 3:07
Гость_Boris
Комментарии к программе добавлены
Автор: Гость_Boris 10.11.2004 13:03
Thank - спасибо
Добавлено (10.11.04 14:30):
Сегодня мне сказали,что эта программа неправильная,т.к. например:
Код
const m=2
...
...
put(1)
put(2)
put(3)
writeln(get)
writeln(get)
writeln(get)
put(4)
writeln(get)
ТО ОТвет должен быть:
1
3
0
4
Автор: volvo 10.11.2004 19:47
Гость_Boris
Скажите, Вы не догадываетесь о существовании на клавиатуре F7, F8 и окна Watches? Неужели трудно было догадаться, из-за чего это происходит ??? Смотрите исправленную версию Get...
P.S. Тесты нужно давать сразу...
Автор: Гость_Boris 10.11.2004 21:07
Всё равно пишет : 1 3 4
а должен : 1 3 0 4
Автор: volvo 10.11.2004 21:28
Ну что мне, EXE выслать? Какой компилятор?
P.S. А чему М равно?
Автор: Altair 10.11.2004 21:50
ЗЫ: я так понял задача решена (раз за нее взялся volvo )
НО!
я думаю что вообще-то все можно было решить с помощью функций и процедур из FAQ'а:
Цитата
procedure QueueInit (VAR Q:TQueue); {INIT}
Function QueueEmpty(Q:TQueue):boolean; {проверка на заполненность}
Procedure OueuePush(var q:TQueue; e:TElem); {поместить в хвост}
Function QueuePop(var q:TQueue):TElem; {извлечь из хвоста}
Это все что нужно!
Автор: Гость_Boris 10.11.2004 22:43
m=3.
Вот.Можешь *.pas выложить. Но всё рвно - я же пробовал - пишет не так!Ё
Автор: volvo 10.11.2004 23:04
Гость_Boris
Ну Вы же свои посты-то хоть читайте!
Цитата
const m=2
...
...
put(1)
put(2)
put(3)
writeln(get)
writeln(get)
writeln(get)
put(4)
writeln(get)
Автор: GoodWind 11.11.2004 1:22
Цитата
const m=2
можт промазал мимо клавиши ;) :D
Автор: Гость_Boris 11.11.2004 1:59
Да, извини.
Тогда как ты написал должно получится:
1
2
0
4
Автор: volvo 11.11.2004 2:15
Гость_Boris
Код
const
m = 2;
var
a: array[1 .. m] of integer;
first, last: integer;
overflow: boolean;
procedure init;
begin
first := 0; last := 0;
end;
function get: integer;
begin
overflow := false;
get := a[1];
if last > 0 then dec(last);
move(a[2], a[1], (m - 1)*sizeof(integer));
a[m] := 0;
end;
function put(x: integer): boolean;
begin
overflow := overflow or (last = m);
inc(last, byte(not overflow));
a[last] := x;
put := overflow
end;
begin
init;
put(1);
put(2);
put(3);
writeln(get);
writeln(get);
writeln(get);
put(4);
writeln(get);
end.
Результат выводимый программой:
1 3 0 4
P.S. Проверьте правильность на бумаге, в конце концов!!!
Что еще не в порядке?
Автор: Гость_Boris 11.11.2004 14:31
It's good. I am glad. Thank all and good bye.
ПЕРВОД:
Это хорошо. Я рад. благодярю всех, и до свидания.
Автор: Гость_Boris 11.11.2004 21:25
А можно вместо этих "конечных" нулей написаит например, очередь полна:
одни вариант: вместо каждого, а второй - вместо всех
Автор: volvo 11.11.2004 21:30
Ну не выводит моя программа нули при полной очереди. Только при пустой.
Ответ - "Да, Можно".
Но у меня к Вам встречный попрос - сколько времени Вы занимаетесь программированием? Неужели даже это нельзя сделать самостоятельно?
Автор: Гость_Boris 11.11.2004 21:39
2 недели ... и то не охотно.
Ну что - можно?
Автор: volvo 12.11.2004 2:30
Если
Цитата
2 недели ... и то не охотно.
то нельзя. Я могу помочь с решением, но писать ЗА кого-то да еще с такими запросами - :no:
Автор: Altair 12.11.2004 11:27
:P
Абалдеть
он еще и не доволен...
Гость_Boris, вам уже решили задачу, если хочется ее модернезировать
то делайте это сами...
volvo, не сервер запросов ведь
Автор: Гость_Boris 12.11.2004 12:39
Ну а как этц цифру 0 преоразовать в символ и добавить к ней символы?
Автор: APAL 12.11.2004 15:36
Как-как - читай встроенный HELP.
Если с английским туго - скачай русскоязычную версию хелпа.
Если и качать не хочется - воспользуйся поиском по форуму.