FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記⑧~安定な結婚と基数変換と後置記法編~

今回は3つのテーマです。

1つ目は安定な結婚の問題というものです。
これは、同数の女性と男性がいて、それぞれの人物の「結婚したい順」が与えられたとき、浮気が発生しないような組み合わせの仕方を探す問題です。

たとえば、

AさんはXさんと結婚しているが、XさんよりもYさんが好き
YさんはBさんと結婚しているが、BさんよりもAさんが好き

という状況なら、AさんとYさんが浮気しますが、こういう組み合わせにならないようにする問題です。
詳細はhttp://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C

これを解くアルゴリズムは、wikiにも載ってますが、

・とりあえず男性Aと第一希望の女性Xを結婚させようとする
→ 女性Xが独身ならそのまま結婚
→ 女性Xが既婚で、既婚者のランク<男性Aのランクなら、離婚して結婚→既婚者は独身になり、新たな結婚相手を探す
→ 女性Xが既婚で、既婚者のランク>男性Aのランクなら、男性Aは独身のまま、第二希望へ

という作業を、独身男性がいなくなるまで繰り返すというものです。
とりあえず全員の男性が一回ずつ求婚すれば、一人の女性の相手は定まりますよね。
それを全員の女性が定まるまで繰り返すので、オーダはO(n^2) (nはペアの数)となります。

まあ、ふ~んという感じで。



2つ目のテーマは基数変換です。
ディ・モールト(非常に)基本的なことなのですが、思えばやってみたことなかったので、とりあえず書いてみました。
まあ、手計算と同じで、基数で割って余りをスタックに入れて基数で割って……の繰り返しで終わりなんですが。
まあ、なんかに使うときもくるかもしれません。



最後は後置記法です。
後置記法とは、たとえば

(a + b) * (c - d)

という計算式を、

ab+cd-*

という風に書くやり方です。
これの計算方法は、

→数値ならスタックにプッシュ
→演算子なら、スタックから2個ポップして計算し、結果をプッシュ

を繰り返して、最後にスタックに残った数値が答えになります。

事典に載ってたのは、普通の計算式を後置記法に直すプログラムだったのですが、大変そうで今日は気分が乗らなかったので、後置記法の計算式の答えを出すプログラムを書きました。

↑の作業をするだけなので、まあ特に悩むことはないですね。面倒なのでオペランドが2桁以上には対応させませんでした。なんという怠惰。


まあ、こうやって日々ちょっとずつですが学んでいけば、いつかは難しいアルゴリズムとかも理解できるようになる! ……と信じて頑張ります。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメント

Secret

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。