練習問題

練習問題 1: Ring Buffer

バッファに対して、データを入れる put() 関数と値を取り出す get() 関数を使っているとします。で、ring buffer というのは、固定サイズの buffer の先頭とラストをつないで使うことで、効率的に put()/get()を実現する機構です。空の buffer から get() しようとしたり、満杯の buffer に put() しないかぎり、繰り返し何度でも使うことができます。

で、一応途中までつくってあります(こちら)。皆さんは、get() 関数の方を完成させてみてください。こちらの課題は、必ず自分で解いておくこと。

余談ですが、いまのままでは、容量を完全に使いきってはいません。もし、完全に使いきるにはどうすべきか考えてみるとちょっとおもしろいです。

練習問題 2

2001年度の ACM プログラミングコンテスト函館予選大会の国内予選問題から、長方形を見つけようという問題。 5x5 の長方形があるので、その中で、"1" が長方形状に並んでいる場所をみつけ、最大の長方形の面積を答えるという問題です。

余力のある人は解いてみましょう。そんなに難しくないはずです。こんな問題が 2-3 問解ければ国内予選突破はOKでしょう。

とりあえず、ファイル入出力回りをつくってあるので(findRec.c)、int calcRecArea(map_t map);の中を完成させてみましょう。使い方は、

     findRec  filename

で、filename のところは、A0.txt, A1.txtを使ってみてください。

2001.11.12/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp