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

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

05B

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

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

方針

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

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

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

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

05C

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

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

方針

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

05D

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

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

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