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

• このページに関する質問は、twitter:@alstamberまで。

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

• 難易度を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
• 後の文字ほど「先頭」に保持しなければいけないので、「頭」の後ろに継ぎ足す関数を作ればいいことがわかる。
• 詳しくは通論を見ればいいが、頭の後ろに継ぎ足すというのは
  • 頭のnextが新しく追加するノード
  • ノードのnextが元々の頭のnext
• 上の話がよくわからない人は絵を描いてみればわかるかと思う。
• 代入文の順番を間違えると正しく動かない。どの順番で代入すればうまくいくかを考える。

08B

• 難易度 3
• Aとは逆に後ろに継ぎ足していくので、リストのおしりの場所がわかってないとだめだとわかる。
• 色々とき方はあると思うが、おしりの場所と追加したい文字を引数にして、新しいお尻の場所を返す関数を作るのが楽だと思う。
  • 関数の名前をappendとでもすれば、struct node* append(struct node *hoge, elementtype fuga);
• おしりに継ぎ足すということは、それぞれのnextの指す先が何になるかを考える。
  • 元々のおしりのnextは、新しく追加されたノード
  • 新しく追加されたノードのnextは、NULL(後ろに何もないから)
• んで、返り値は新しく追加されたノードのアドレスになる。

08C

• 難易度 4
• A, Bが解けていれば、基本は同じ。
• 学籍番号を記録するリストと、アカウント名のリストを２つ作ってしまえば良い。
• 両方を記録できる1つのリストを作るのもプログラミングのいい練習になる。
  • 構造体の要素を増やせば良い。

08D

• 難易度 4
• リストを前から順番に参照し、aだけが入っているリストとbだけが入っているリストに分ける。
• 2つを合体して、前から印字。

09回は特に難しい気がします。今回こそは全部解けないかと思ったのですが、なんとか解けたので、直々考え方を忘れないうちにメモする予定。

09A

• 難易度 4

09B

• 難易度 4

09C

• 難易度 3

09D

• 難易度 5

復習回

第9回のやり方を思い出しながら、10回を先に書くことにする。
ちなみに今回からWebClassに移行したｗ

10A

• 難易度 3
• 基本的には08Bだったかあたりと同じ。
• まずリストを実装する。08回あたりを参考にすればいい。

  • ただし今回は、08回とリストの作り方が違う。ListPlayerというリストの頭の場所を入れておくポインタとリストのおしりの場所を入れておくポインタが入ってる構造体が用意されている。

  • そのためにまずリストのinit関数の書き方がちょっと違ってくる。

  • init関数はListPlayer LP_init();となって、ListPlayerという構造体を返す関数になる。

  • 構造体を返す関数を作るときの常套手段は、
    • まず作業用の構造体を作る
    • 構造体の中身を作る
    • return 作業用の構造体
  • 適当に作業用の構造体をまずつくったあと、構造体の中身のlistとtailポインタがどこを指すようにすればいいのかを考える。
    • listはmallocででっち上げたnodeを指すようにすれば良い。
    • tailも同じ。
    • nodeのnextは何をさせばよいかを考える。
• 08Bで作ったappend関数をとりあえずパチってきて、LP_addmusicに名前を変える。

  • ただしappend関数はそのまま使えない。ListPlayerを通してリストを操作しないといけない。

10B

• 難易度 3
• pコマンドの処理はプリントに書いてあるヤツをそのままパチってくればいい。
• LP_getnth()を実装しましょうと書いてあるので、それを実装する。
  • リストの場合、配列みたいにarray[i]みたいな感じで持ってこれないので、前から順番に数えてn番目のnodeのアドレスを返すのが妥当だろう。
• LP_playコマンドは、まずbeginとendをLP_getnth関数に通して、begin番目とend番目のnodeの場所を探す。
  • begin番目のnodeから順番にnextを手繰って、end番目に到達するまでそれを繰り返す。

10C

• 難易度 4
• 10Bのプログラムをまるごとパチってくる。
• LP_move関数は、begin番目とbegin-1番目とend番目とdest番目のnodeの場所をまずLP_getnth関数で探す。
  • そのあとは絵を描いて、どうやってつなぎかえれば、目的の動作をするかを考える。

10D

• 難易度 4
• 曲数が何曲でも対応できるようにするためには、dynamicに配列を確保する必要がある。

  • ListPlayer構造体の中身をまず変えなければいけない。tailは配列の場合アドレスじゃなくてただの数字(=添字)でいいからint型でいい。list本体を指すポインタは何型になるか考える。

  • init関数で何曲ぶんかの配列をmallocで確保する。
  • 曲を追加していくときに、配列が足りなくなったら配列の大きさを倍ぐらいにしてreallocする。
• play関数の実装は簡単。
• move関数の実装が難しい。
  • 「とりあえずbegin番目の要素を取り出して、一旦その要素を削除。そのあとdestの後ろに取り出した要素を挿入」という動作をendまで繰り返すという方針で解いた。
  • 要素を削除するということは、それより右側の要素を左へ一個ずつつめるということ。
  • 挿入するということは、それより右側の要素を右へ一個ずつずらした後、あいたところに代入するということ。
  • 文字列なので普通に代入してもちゃんと動かない←大事
  • 要素を左へ動かすか、右へ動かすかで微妙に挙動が変わるので、ちゃんと分岐して処理する。

重要なのは、配列を使う時とリストを使う時で計算の量が変わってくるということ。リストの場合moveはどんなに曲数が増えても一定時間で可能だが、配列だと曲数が増えれば増えるほど時間がかかる可能性が高い。
ハッシュ表を導入すれば効率が上がる可能性はある。(試してない)

11A

• 難易度2
• Selection Sort(選択ソート)をプログラミング通論の資料を読みながら実装するだけ。
• 文字列のどちらが辞書順で先に現れるかはstrcmpで調べれば良い。
  • strcmpの取扱いに気をつける。
  • どのような時にどのような返り値が返ってくるのかをぐぐるなりして調べる。

11B

• 難易度3
• Quick Sortをプログラミング通論の資料を元に完成させる。
• ただし配列の要素を入れ替えているところは、swap関数を使って書かないといけない。
• プログラミング通論では「番兵」と呼ばれるものを配列のいちばん後ろに置いている。配列の一番後ろに配列に入っている要素のどれよりも大きいと想定されるものを入れておくことで、配列の外側にiが飛び出ていかないようにしている。
  • 番兵を使ってはいけないという指定なので、番兵の代わりに条件分岐でiが飛び出ていかないように管理すればよい。

11C

• 難易度3
• Insertion Sort(挿入ソート)をプログラミング通論の資料を元に完成させる。
• ただし全部読み込んでからInsertion Sortするのではなくて、一行読み込むごとにInsertion Sortしないといけない。
  • プログラミング通論の資料丸パクリと言うわけにはいかない。

11D

• 難易度4
• プログラミング通論の資料にあった「大きいレコードをソートする」みたいなタイトルの内容が参考になる。
• cursor[i]=iとなっているような配列を用意する。
  • students[cursor[i]]とすれば、students配列のi番目にアクセスできる。
• Insertion Sortを使って、このcursorと言う配列をソートする。
  • ただしソートのときに使うのはあくまでstudents.idである。cursor配列を使って各々のstudents.idを参照するにはどうすればよいか。
• カーソルがソートできたら、そのソート結果を使ってstudents配列を入れ替える。
• 一般に構造体を入れ替える(コピーして代入し合う)のは時間がかかる処理である。カーソルで一旦ソートしてから入れ替えるという風にすると、この処理の回数を減らすことができる。

12A

• 難易度3
• 11Cの要領でInsertionを行う。
• 後ろから順番に調べていって、新しい要素を本当にそこに挿入していいかを判断する。
• もし一番前まで行ってしまったらどうする?(比較対象がない)
  • 一番前はどんな要素よりも大きい点数を持った要素をおいておけば良い(番兵)

12B

• 難易度3
• 通論のヒープソートのコードをぱくってくれば良い。
• 0から始まってるので、絵を描いて変数の開始位置を考えて変更する。

12C

• 難易度3
• Selection Sortを通論の資料を見ながら実装。
  • Selection Sortというのはどういうソート方法だったか。i番目に来る要素をどうやって探すかを考える。
• ノードのつなぎかえは、通論でやった通り。
• おそらくマージソートでも実装可能。

12D

• 難易度3
• とりあえず一番後ろに新しい要素を足す。
  • その要素の親と比較し、順番がおかしければ入れ替える。
  • 上の操作を繰り返せば良い。

今のままだと演習は半分近くが不合格らしい。鬼畜だね。

13A

• 12Aとほとんど同じ。

13B

• 2分探索

13C

• マージソート

13D

• 再生回数を保持するため、配列をタダの配列じゃなくて構造体の配列にします。
• 再生回数をキーにしてソートします。ソートの方法は好きにすれば良いと思う。
  • 再生回数が同じ時、曲名順に並べたいなら安定ソートと呼ばれるソートをする必要がある。安定ソートにはたとえばマージソートが含まれる。