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

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

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

Автор: Гость_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), т.к. элемент, который вошел последним, выйдет первым blink.gif

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

Автор: 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 если очередь пуста(по-моему - а может когда переполнение??


это алгоритм? lol.gif

Автор: Гость_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 элемента, вот и получается бурда lol.gif

Автор: Гость_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 smile.gif )
НО!
я думаю что вообще-то все можно было решить с помощью функций и процедур из 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

Ну Вы же свои посты-то хоть читайте! angry.gif

Цитата
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

angry.gif Если

Цитата
2 недели ... и то не охотно.


то нельзя. Я могу помочь с решением, но писать ЗА кого-то да еще с такими запросами - :no:

Автор: Altair 12.11.2004 11:27

:P
Абалдеть rolleyes.gif
он еще и не доволен...
Гость_Boris, вам уже решили задачу, если хочется ее модернезировать
то делайте это сами...

volvo, не сервер запросов ведь smile.gif

Автор: Гость_Boris 12.11.2004 12:39

Ну а как этц цифру 0 преоразовать в символ и добавить к ней символы?

Автор: APAL 12.11.2004 15:36

Как-как - читай встроенный HELP.
Если с английским туго - скачай русскоязычную версию хелпа.
Если и качать не хочется - воспользуйся поиском по форуму. angry.gif