計算機プログラミングＩ試験（萩谷）

1998/7/28

1.

次のプログラムの出力を書け。（10 点）

program pointer(output);
type pinteger = ^integer;
var j : integer;
　　q : pinteger;

　procedure update(i : ingeter; p : pinteger);
　begin
　　i := p^ + i ; p^ := p^ + i
　end;

begin
　j := 1;
　new(q); q^ := 10;
　update(j, q);
　writeln(j); writeln(q^);
end.

2.

次は、クイック・ソートを行なうプログラムである。ただし、n=5 なので、ソートされるデータの数は 5 個である。手続き sort が呼び出されるたびに、その引数を出力している。（ソートした結果は出力していない。）

program quicksort(input, output);
　const n = 5;
　var a : array[1..n] of integer; i : integer;

　procedure sort(p, q : integer);
　　var i, j, x, w : integer;
　begin
　　writeln('sort(',p:1,',',q:1,');');
　　i := p ; j := q ; x := a[(p+q) div 2];
　　repeat
　　　while a[i] < x do i := i + 1;
　　　while x < a[j] do j := j - 1;
　　　if i <= j then
　　　begin
　　　　w := a[i]; a[i] := a[j]; a[j] := w ;
　　　　i := i + 1; j := j - 1;
　　　end
　　until i > j ;
　　if p < j then sort(p, j);
　　if i < q then sort(i, q);
　end;
begin for i := 1 to n do read(a[i]);
　　　sort(1, n);
end.

2.1.

次のそれぞれの入力に対して、プログラムの出力を書け。（各 5 点）

4 1 3 5 2
2 4 1 3 5

2.2.

n=5 ではなく、n=3*2^k-1 とする。ただし、k は 0 以上の整数とする。（2^k は 2 の k 乗を意味する。）このとき、

1 2 3 ... n

という入力が与えられたならば、sort は全部で何回呼び出されるか。（10 点）

3.

以下のプログラムにおいて、expr は前置式を入力して、ポインタとレコードから作られる木構造を返す関数である。 dim は、式の木構造と変数名を引数として、与えられた変数に関する式の字数を返す関数である。例えば、式

*+xy+zx

の変数 x に関する次数は 2 である。また、式

+**yyy**yyz

の変数 y に関する次数は 3 である。

program expr(input, output);
type nodekind = (op, va);
　　nodep = ^node;
　　node = record
　　　　　case nk : nodekind of
　　　　　　　op : (o : char; left, right : nodep);
　　　　　　　va : (v : char)
　　　　　end;

function expr : nodep;
　var ch : char; p, p1, p2 : nodep;
　begin
　read(ch);
　　if ('x' <= ch) and (ch <= 'z') then begin
　　　new(p, va); p^.nk := va; p^.v := ch;
　　　expr := p
　　end else if (ch = '+') or (ch = '*') then begin
　　　p1 := expr;
　　　p2 := expr;
　　　new(p, op); p^.nk := op; p^.o = ch;
　　　p^.left := p1; p^.right := p2;
　　　expr := p
　　end else expr := nil
　end;

function dim(p : nodep, x : char) : integer;
begin
　if p^.nk = op then begin
　　　　【a】
　end else if p^.nk = va then begin
　　　　【b】
　end
end;
　　..

【a】と【b】の部分を完成せよ。

4.

以下は、チェス板の角のマス目から始め、ナイトの動きを繰り返して、すべてのマス目を一回ずつ訪れる手順を一つだけ求めるプログラムである。

program knighttour(output);
var board : array[1..8,1..8] of boolean;
　　tour : array[1..64,1..2] of integer;
　　i, j : integer;

　function find(i, j : integer) : boolean;
　var f : boolean;
　　　k, x, y, z : integer;
　begin
　　if board[i,j] = false then begin
　　　board[i,j] := true;
　　　tour[n,i] := i ; tour[n,2] := j;
　　　if n = 64 then begin
　　　　for k := 1 to 64 do write('(',tour[k,1]:1,',',tour[k,2]:1,') ');
　　　　writeln;
　　　　find := true
　　　end else begin
　　　　f := false;
　　　　for x := -2 to 2 do
　　　　　if x <> 0 then
　　　　　　for z := 0 to 1 do begin
　　　　　　　y := (z*2 - 1) * (3 - abs(x));
　　　　　　　if (f = false) and (1 <= i+x) and (i+x <= 8) and
　　　　　　　　　　　　　　　　 (1 <= j+y) and (j+y <= 8) then
　　　　　　　　f := find(【a】, i+x , j+y)
　　　　　　end;
　　　　find := 【b】
　　　end;
　　　board[i,j] := 【c】
　　end else find := 【d】
　end;

begin
　for i := 1 to 8 do for j := 1 to 8 do board[i,j] := false;
　if find(1, 1, 1) then writeln('found')
　else writeln('not found')
end;

ちなみに、このプログラムを実行すると次のような出力結果が得られる。（改行は適当に追加した。）

　　(1,1) (2,3) (1,5) (2,7) (3,5) (1,4) (2,2) (3,4) (1,3) (2,1) (3,3) (1,2)
　　(2,4) (1,6) (2,8) (3,6) (1,7) (2,5) (3,7) (1,8) (2,6) (3,8) (4,6) (5,4)
　　(4,2) (6,1) (5,3) (3,2) (4,4) (5,2) (3,1) (4,3) (5,1) (7,2) (6,4) (4,5)
　　(5,7) (7,8) (8,6) (6,5) (8,4) (7,6) (8,8) (6,7) (4,8) (5,6) (6,8) (4,7)
　　(5,5) (7,4) (8,2) (6,3) (7,1) (8,3) (7,5) (8,7) (6,6) (5,8) (7,7) (8,5)
　　(7,3) (8,1) (6,2) (4,1)
　　found

4.1.

【a】【b】【c】【d】に入るべき式を求めよ。（各 5 点）

4.2.

次の文の働きについて説明せよ。特に、x と y の関係を述べよ。（10 点）

y := (z*2 - 1) * (3 - abs(x));

5.

次のことがらについて簡単に（数行で）説明せよ。（各 5 点）

変数引数
二分探索木
モンテカルロ法
ガウスの消去法

Presented by KHK.