アルゴリズム (全82問中29問目)

No.29

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

このアルゴリズムをトレースすると次のようになります。
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」になります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop