平成28年度春季 基本情報技術者試験(FE)の午後問題9は、
- フラクタル図形を描画するプログラム
に関する問題でした。
プログラム例(h28h_fe_pm9.c)
関数exists_atの動き
関数exists_atは、exists_at内から自分自身を呼び出す再帰構造になっています。階乗を計算するなど簡単なものは、再帰呼び出しをトレースしていくのも容易なのですが、少し複雑になると中々難しいですね。
今回の空欄b〜dも素直に読めば、
- 空欄b: 深さ0のときは*を描画する必要があるので1を返す。
- 空欄c: 深さがd-1のexists_at呼び出しから0が返ってきたときは0を返す。
- 空欄d: 配列patに応じた値を返す。
でいいと思うのですが、しっかりと理解するために以下の例でトレースしてみたいと思います。
print_funcからexists_at(7, 3, 3)と呼び出した場合
(1) exists_at(7/2=3, 3/2=1, 2) (2) exists_at(3/2=1, 1/2=0, 1) (3) exists_at(1/2=0, 0/2=0, 0)
と呼び出され、(3)から(2)に1が返されます。(2)において、exists_at(1, 0, 1) == 0が偽となり、pat[3%2=1][1%2=1]の値0が(2)から(1)に返されると、(1)においては、exists_at(3 ,1, 2) == 0が真となり、exists_at(7, 3, 3)は0となります。
exists_at(7, 3, 3)は計算結果が0になるときの例でしたが、exists_at(4, 3, 3)など結果が1になる場合もトレースしてみると、より理解が深まると思います。
実行結果
$ gcc h28h_fe_pm9.c && ./a.out 0 * $ ./a.out 1 ** * $ ./a.out 2 **** * * ** * $ ./a.out 3 ******** * * * * ** ** * * **** * * ** *
