跳到主要内容

千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2022年8月実施 専門 A5

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

次の Pascal プログラムについて答えよ。

program a5(output);
label 9999;
const size=10;
var queue: record elements: array[1..size] of integer;
                  head,tail,count: integer end;
procedure clearqueue;
begin with queue do begin head:=1; tail:=1; count:=0 end end;
procedure enqueue(val: integer);
var i: integer;
begin with queue do begin
  if count>=size then goto 9999;
  if tail>size then begin
    for i:=1 to count do elements[i]:=elements[head+i-1];
    head:=1; tail:=1+count
  end;
  elements[tail]:=val; tail:=tail+1; count:=count+1
end end;
function dequeue: integer;
begin with queue do begin
  if count<=0 then goto 9999;
  dequeue:=elements[head]; head:=head+1; count:=count-1
end end;
function emptyqueue: boolean;
begin emptyqueue:=(queue.count=0) end;
procedure test;
var i: integer;
begin clearqueue;
  for i:=1 to size do enqueue(i);
  for i:=1 to size div 2 do write(dequeue);
  for i:=1 to size div 2 do enqueue(size-i);
  for i:=1 to size do write(dequeue);
  writeln(emptyqueue)
end;
begin test; 9999: end.
  1. 実行時の出力を記せ。
  2. 配列の末尾の次を先頭とする循環配列を用い、データ移動なしで同じ返り値系列を与えるよう enqueue、dequeue を書き換えよ。

题目描述​

对题中数组队列程序：(1) 写出输出值；(2) 把队列改为循环数组，重写入队、出队，避免搬移元素，并使任意调用序列的返回结果保持一致。

Kai​

(1) 出力される値を順に区切って示すと

1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 TRUE

最初の五回の出隊後は 6,7,8,9,106,7,8,9,10 が残り、その後 9,8,7,6,59,8,7,6,5 が末尾に追加される。最後の十回の出隊で空になる。実際の空白幅と真偽値の表記は Pascal 処理系の既定の出力形式に従う。

(2)

procedure enqueue(val: integer);
begin with queue do begin
  if count >= size then goto 9999;
  elements[tail] := val;
  tail := tail mod size + 1;
  count := count + 1
end end;

function dequeue: integer;
begin with queue do begin
  if count <= 0 then goto 9999;
  dequeue := elements[head];
  head := head mod size + 1;
  count := count - 1
end end;

head から循環順に count 個の要素が論理的な待ち行列を表し、tail は次の追加位置を表す。この不変条件は初期化、入隊、出隊で保存されるので、満杯・空の判定も含めて元のプログラムと同じ動作となる。

本页目录