アルゴリズム(全101問中48問目)

No.48解説へ
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

出典：平成23年秋期　問 7

  • 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