平成23年秋期試験問題 午前問7

n個の正の整数 x1,x2,…,xn が並んだ線形リストを [x1,x2,…,xn] で表し,空リストは[ ]で表す。次のように再帰的に定義される関数 func(L) を,L=[1,3,2] を実引数として呼び出したとき,print文によって表示される数字はどれか。ここで,プログラム中の=は等号,:=は代入を表す。

〔関数の定義〕
  • first([x1,x2,…,xn])はx1を返す。
  • butfirst([x1,x2,…,xn])は[x2,…,xn]を返す。butfirst([x])は[ ]を返す。
  • max(x,y)は,x≧yであればxを返し,そうでなければyを返す。
func(L)
begin
 if L = [] then return 0;
 A := first(L);
 B := func(butfirst(L));
 C := max(A, B);
 print C;
 return C;
end

  • 123
  • 133
  • 223
  • 233
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
このアルゴリズムをトレースすると次のようになります。
func([1,3,2])

A :=first([1,3,2]); //A=1
B :=func([3,2]); //butfirst([1,3,2])=[3,2]
 /* 再帰呼出し1 start */
 A := first([3,2]); //A=3
 B :=func([2]); //butfirst([3,2])=[2]
  /* 再帰呼出し2 start */
  A := first([2]); //A=2
  B :=func([]); //butfirst([2])=[]
   /* 再帰呼出し3 start */
   L = [] return 0; //再帰呼出し2のBに0が返る
   /* 再帰呼出し3 end */
  C :=max(2,0); //C=2
  print 2;
  return 2; //再帰呼出し1のBに2が返る
  /* 再帰呼出し2 end */
 C :=max(3,2); //C=3
 print 3;
 return 3; //呼び出し元関数のBに3が返る
 /* 再帰呼出し1 end */
C :=max(1,3); //C=3
print 3;
return 3;

end
print文で出力される数字を順番にすると「233」になります。

Pagetop