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

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

• 難易度を5段階でつけてみることにしました。-- alstamber 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
• 組み合わせを再帰を使って計算する問題。再帰の常套。

06B

• 難易度 4
• 06Aから再帰をスタックを使って外す。

06C

• 難易度 3
• 再帰における各ローカル変数の挙動を調べる問題。
• 再帰で具体的にどのような処理が行われているかの理解を問うている問題だろう。

06D

• 難易度 4
• 再帰的に図形を分割して、四分円の面積を求める問題。