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

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

05B

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

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

方針

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

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

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

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

05C

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

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

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秒弱ぐらいかかる)ので、工夫がちょっと必要。
    • 動的計画法とかメモ化再帰とかでググろう。
  • 再帰は糞遅い……関数を呼び出すという操作が実はものすごく時間のかかる作業
    • だから通論で再帰の外し方をやったりするわけです。
    • ただ、再帰は数学的に問題にアプローチするときには有効な方法。
    • 僕は再帰は嫌いです。