プログラミング演習(I科)対策

• なかなかにプログラミングに慣れてない人にはハードな課題が連発されているので、自分の勉強も兼ねてページにまとめていくことにする。

• 難易度を5段階でつけてみることにしました。-- 2011-11-23 19:05:20

  • 1……これが解けないようだと、単位取得は危うい。
  • 2……基本的な問題。演習時間内に解けるようにしたい。
  • 3……標準的問題。これが解けるレベルなら単位はおそらく出るだろう。
  • 4……応用的問題。良い成績を狙うのであればこの問題は解けるようにしておきたい。
  • 5……発展的問題。頭の柔らかさが必要。秀を狙うなら解けるようにしたい。
• プログラミングできる人からすれば、アレな難易度の付け方に思われるかもしれないが、みんながみんなプログラミングをしっかり勉強しているわけではないのでだいたいこのあたりのランク付けが妥当と思われる。

05B

• 難易度 2
• 括弧の対応がとれているかどうかを再帰を使わずに判定するプログラム。

標準入力から文字列(78字以内)を受け取って、()と{}の二種類の括弧について全て対応しているかどうかを判定するプログラムをつくれ。
対応している場合はyesを印字。していない場合はnoを印字する。

方針

• stackの復習と言っているぐらいなんだから、まずstackを実装しましょう。
• 括弧の対応だけを調べればいいので、括弧とヌル文字以外は無視しても構わない。
• 文字列を先頭から順番に調べて、開き括弧に到達したら、対応する閉じ括弧をstackにpushする。

  • これを例えばa+{(2-...という文字列に実施すれば、

• 上のような感じでスタックが積まれることになる。

• 引き続き文字を調べて、閉じ括弧を見つけたとする。
  • その閉じ括弧がスタックに積まれている閉じ括弧と一致していればちゃんと括弧が対応しているとわかる。
  • 違う種類なら括弧が対応していないとわかる。→即座にnoと出力して終了すれば良い。
• 最期まで調べてstackに残りがあれば、閉じ括弧のほうが少ない、すなわち対応する括弧がなかったということだからやっぱりnoを印字して終了してしまえばいい。

05C

• 難易度 5
• 05Bを再帰を使って実装。stackは使えない。

標準入力から文字列(78字以内)を受け取って、()と{}の二種類の括弧について全て対応しているかどうかを判定するプログラムを再帰的関数でつくれ。
対応している場合はyesを印字。していない場合はnoを印字する。

方針

• とりあえず文字列を前から順番に調べる。
  • 開き括弧が来たとき
    • 括弧の次の位置からcheckを再帰的に呼び出し(括弧の中に括弧が入ってるかを調べるため)
      • 括弧が対応していたら閉じ括弧の次の位置から再び調査を再開
      • 対応していなければ分類を3にして即座にその位置をreturn
      • 分類が3ならそのまま返ってきた値をreturn
        • 再帰から返ってきたとき分類が3ならそれ以上処理を続ける必要がない、だからそのままreturnしまくって戻る
  • 閉じ括弧が来たとき
    • 開き括弧の前に閉じ括弧が来るケースがある
      • このケースに対応するためとりあえず分類を2にして、アドレスをreturnする
  • それ以外が来たときはスルーすれば良い
• 文字列を最後まで調べきれた=括弧が全部対応している!
  • 分類が2になっているケースがあるので、分類を1に戻して適当な値をreturn

05D

• 難易度 4
• ある一定の金額を支払うときにどのような組み合わせが可能かを計算する問題。

Y円の料金を1000円札、500円硬貨、100円硬貨、50円硬貨、10円硬貨をつかって支払う場合の組み合わせの数を求めるプログラムを作成せよ。
ここで、標準入力から支払金額を与えるものとし、支払いに利用可能な札及び硬貨はいくらでもあるものとする。
またYは10円以上100000円以下の10の倍数と考えて良い。

方針

• Y円の金額を払うのにどれだけの組み合わせが取れるのか一寸考えてみる。
  • Y円払うのに1000円を一枚も使わないケース、一枚使うケース、二枚使うケース、……、n枚使うケースを考えることができる。(nはY-1000nが0以上となるような最大のn)
  • それぞれ1000円札で払ってしまうと、Y円、Y-1000円、Y-2000円、……、Y-1000n円残る。
  • 残った額を今度は1000円を使わずに残りの通貨だけで支払うことを考える。
  • これを繰り返すとだんだん支払いに使える通貨は減っていって、ついに10円硬貨しか使えなくなる。
    • 10円硬貨だけで支払う方法は1とおりである。
  • 以上の組み合わせの計算は再帰で書くことができる。
  • ただ普通に再帰すると糞遅い(いいマシンでも100000計算するには10秒弱ぐらいかかる)ので、工夫がちょっと必要。
    • 動的計画法とかメモ化再帰とかでググろう。
  • 再帰は糞遅い……関数を呼び出すという操作が実はものすごく時間のかかる作業
    • だから通論で再帰の外し方をやったりするわけです。
    • ただ、再帰は数学的に問題にアプローチするときには有効な方法。
    • 僕は再帰は嫌いです。

90A

• 難易度 1
• 何と今回は90回目扱い
• 復習回ということで出席メールだけでした
• 今までのを提出できてないひとはそれをやってだしてもよい
• 出席メールの問題は簡単だった

自分の学籍番号の下3桁をvとする。引数nを受け取りn個のvで初期化されたint型の値n個分のメモリ領域を作る関数myidsを作成せよ。
またmyidsを使って長さ100の配列aを作成し、100番目の要素を出力せよ。

• mallocの使い方を思い出せば良い。
  • mallocでn個のint型のメモリ領域を確保するには引数をどのようにすればよいか……
• これが時間内に解けないようだと、正直今からちゃんと勉強しないと通論あたりを落とすような気がする(演習は友達に見せてもらえばなんとかなるだろうけど)。

06A

• 難易度 2
• 組み合わせを再帰を使って計算する問題。再帰の常套。
• 漸化式はプリントに書いてあるとおりであるので、基本的にはこの漸化式をそのままreturn文にすれば良い。
  • ただこれだと再帰が止まらなくなっていつかセグメンテーションフォルトを起こすので、初期条件として幾つかの条件を定める必要がある。
  • 具体的には漸化式で計算できないような状況について、if文とreturn文を使って関数内で定義してやれば良い。

06B

• 難易度 4
• 06Aから再帰をスタックを使って外す。
• プログラミング通論でやったと思うが、再帰というのはスタックを使って実現している。
  • 関数の中で関数を再帰的に呼び出すと、その呼び出した場所と元々の関数で使われてた変数をスタックに保存するということが行われる。
  • こうすれば、ひと通り関数を実行し終わって戻ってきたときにスタックに保存した情報をポップしてくれば、元通り続きを実行できる、という仕組みになっている。
  • つまりこのスタックに積んで……というところを自前でやってしまえば再帰は必要ない。
  • それを実際にプログラミングしてみなさい、というのがこの課題。
• とりあえずnとmをポップしてくる。
  • 条件によって挙動を変える。
  • 再帰に対応するのはスタックへのプッシュ。
  • 単純なreturnは変数への代入として表現できる。

06C

• 難易度 3
• 再帰における各ローカル変数の挙動を調べる問題。
• 再帰で具体的にどのような処理が行われているかの理解を問うている問題。
• 06Bで書いたとおり、再帰では変数をスタックに積んでいくという処理を行なっている。んで、具体的にスタックの中身がどうなっているのかを書きなさいというのがこの問題。
• 頭で考えるのも面倒くさいので、プリントのfiv(I2クラスはfibらしい)関数の「この時点での様子」で適当に変数をprintfつかって出力してみるのが良い。
  • あとはそれと例とをニラメッコして自分の手で作ってみよう。
• 自分でスタックを実装して全部プログラムにやらせる方法もあるけどCでこんなプログラムを書くのは糞面倒臭いのでやめておきました。

06D

• 難易度 4

  • 難易度3になりました -- alstamber 2011-11-28 18:42:56

• 再帰的に図形を分割して、四分円の面積を求める問題。
• 基本的にはプリントに書いてあるとおり。
  • まず正方形を分割します
  • それぞれの正方形についてAとBの条件を満たしているかを判定します
    • 満たしていれば面積を返して終わり
    • 満たしていなければもういっちょ分割
  • 面積が定数EPSILONより小さくなったら面積をゼロとして糸冬了
  • こうして出てきた面積を全部合計すれば、π/4ぐらいになるはず
• Aの判定は右上の点から原点までの距離が1未満、Bの判定は左下の点から原点までの距離が1より大きい、で可能
• 実はまだこのプログラム書いていないのでなんともいえないが、実質難易度 3ぐらいかもしれない。
  • 3ぐらいでした
  • プログラムは上の通りに書けばいいだけで、あとは要件を満たすようにEPSILONを調整するだけ

07A

• 難易度 3
• 分割統治法の問題。
• そもそも分割統治法とは何か、がわかっていない人がクラスの様子を見ていると多いようである
• ある配列から最大値と最小値を普通に前から順番に調べて求めることを考える。
  • 前から順番に調べて最大値、もう一回前から順番に調べて最小値、とデータがn個なら2n回の調査が必要になってしまう。
    • 効率悪い。
  • そこで、配列を半分ずつに切っていって、2個になったところで、比較する。
    • 比較の回数が減って、動きが速くなる。
    • 分割の結果1個になってしまったら、とりあえず最小値かつ最大値ってことにしておけば良い。
  • そして分割したのを今度は元にもどしていく。
    • 元にもどすときに、比較をして最大値と最小値を決めていく。
    • これを最後までやれば、最終的な最大値と最小値が求まる。

07B

• 難易度 3
• 07Aと問題の傾向は同じ。07Aが解ければおそらく解ける。

07C

• 難易度 4
• 六角形あたりを描いてみると、まず三角形をひとつ切り出したときに残りの部分が1つか2つになる。
  • それぞれについて再帰的に同じ処理、すなわち三角形を切り出す処理を行う。
  • 繰り返せばいつかはすべてを三角形に分割できる
  • 三角形を三角形に分割する方法は何通りあるだろうか？
• カタラン数でググれ

07D

• 難易度 5
• 用語を使うと、このプログラムの入力は重みのついた隣接行列と呼ばれるものである。
  • それぞれの駅に番号を振って、例えばn番目とm番目の駅がつながっているときはその距離を表す数字をn行m列目に、つながっていないときは-1をn行m列目に入れていると考えればわかりやすい。
  • nとmはつながっていて、互いに行き来できるから、n行m列目とm行n列目は同じ数になる(対称行列)
  • 1行目からスタートして、-1でないところを潰し、その駅の行に行って再帰的に最初から繰り返す……ということをすれば一筆書きのパターンは計算できる(多分)。
• -1でないところを前から順番に探す→-1じゃないところを発見したらそこを-1にして再帰的に経路を探索→戻ってきたら-1にしたところをもとに戻す
  • バックトラッキングっぽいことをしている
  • とりあえず通ったところを潰していって、行き詰まったら引き返して、また別のルートを探索する。
    • 引き返すときに、引き返したルートを潰したのをもとに戻すのを忘れない。
  • 行き詰まるところまでいった経路＝一筆書きのルートなので、その時の長さをそれまでの最大値と比較。
    • それまでの最大値より大きければ更新。

08A

• 難易度 3

08B

• 難易度 3

08C

• 難易度 4

08D

• 難易度 4