Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成28年度春季基本情報午後問9

平成28年度春季 基本情報技術者試験(FE)の午後問題9は、

に関する問題でした。

f:id:rahaema:20190303112027p:plain

プログラム例(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
********
* * * *
**  **
*   *
****
* *
**
*