☆ いらっしゃいませ ☆
ここでは武蔵高中ＣＰＵ愛好会の、会員の有志が書く活動日誌や、当番制のレポート、その他会合議事録などを載せています。
会員ごとの活動日誌が見たい場合は、左側メニュー欄から「活動日誌○○編」というカテゴリーを開いてください。
レポートは以下のリンクからどうぞ。
- 火曜更新：Ｇ＆Ｔ『Ｃ言語入門講座』最終更新：07/26
- 金曜更新：美祢『データ構造（データを並べる、順序づける）』最終更新：08/05←NEW!
過去連載のレポート
- まだありません
今日から記念祭でした！
こんばんは、お久しぶりです。ＣＰＵ愛好会元広報係のＧ＆Ｔです。
さて、まずは半年以上に渡り活動日誌を放置してしまい申し訳ありませんでした。会内部での役職やパスワードなどの情報がスムーズに引継ぎ出来ずにこのような結果となってしまいました。誠に申し訳ございません。
で、今回記事を書いた理由なのですが
記念祭
です。
詳細はこちら（http://634anniv90.ninja-x.jp/）に書かれていますが、日程は4月28日〜30日、つまり今日から明後日までです。……はい、報告が遅れてしまいすみませんでした。
例年通りＣＰＵ愛好会も「ゲームの展示」「ＣＤ配布」「小冊子配布」を三本柱に記念祭に参加しています。急なお暇な方は是非お越しください！
では、またいつか！
データ構造 第05講「大きい順にデータを出したい」１
目次→美祢『データ構造』 目次 - 武蔵高中 ＣＰＵ愛好会 活動日誌
前回までは
要素数の分からない（あるいは処理が長引くにつれて増えていく）データを格納するための方法について学んできました。
今回からは実際に使う時に便利なデータ構造について学んでいきます。
例題
まずは例題を投下します。すぐに解説してしまうので、少し自分で考えたいという方は問題より下を見ない様に気をつけてください。
http://poj.org/problem?id=3253より
【上記URLの問題の、『プログラミングコンテスト チャレンジブック』（参考文献）による訳を引用】 農夫ジョンは、フェンスを修理するため、とても長い板からn個の板を切り出そうとしています。 切り出そうとしている板の長さはL1,L2,……,Lnであり、元の板の長さはちょうどこれの合計になっています。 板を切断する際には、その板の長さの分だけのコストがかかります。 例えば、長さ21の板から長さ5,8,8の3つの板を切り出したいとします。 長さ21の板を長さ13と8の板に切断すると、コストが21かかります。 その13の板を5と8の板に切断すると、コストが13かかります。 合計で34のコストがかかります。 最小で、どれだけのコストですべての板を切り出すことができるでしょうか。 制約 1≦n≦20,000 1≦Li≦50,000
（補足：Liとは、L1,L2,……,Lnの中の任意の１つ、という意味）
例題の解説
この時、切り出す回数は、何があろうとn-1回です。これは変わりません。同じ回数切るなら、一回一回のコストを安く収めたいですね。
ここで、問題を「L1,L2,……,Lnの板を接続して1枚にする」と読み替えましょう。また、接続するn-1回の内、LiやLiが含まれている板を使う回数を「Liの使用回数」と言うことにします。合計コストは「Liの長さ×Liの使用回数」の和で求められます。
すると、コストをできるだけ小さくしたいので、短いものほど使用回数を増やしたく長いものほど使用回数を減らしたい事が分かります。
そのためには、「各回で短い方から2枚選んでそれら接続していく」という方法が取れます。この事は、「初回に一番短い板と二番目に短い板をを使わない場合はコストが最小にならないという組み合わせがある」事から背理法（そうでない場合は不都合が発生する）により証明できます。
例えば{1,2,4,8,16,32}というLの組み合わせがあったとします。“短い方から選んでいく法”では、{1,2,4,8,16,32}→{3,4,8,16,32}→{7,8,16,32}→{15,16,32}→{31,32}→{63}となり、すべての回で「1」および「1を含むもの」、「2」および「2を含むもの」が使われています。それ以外の方法ではせっかくの短い「1」「2」の使用回数が減ってしまいますね。
という訳で、小さい方から取り出したい訳なんだ
そういう時に、「プライオリティキュー（優先度キュー）」というデータ構造が大変便利です。これは何かと言うと、「入れる順番に関わらず、取り出す時は常に最大/最小（設定によって比較の方法は異なる）の要素を取り出す」ものです。
※以下、数値の大小の代わりに「優先度の高い低い」という表現を使います。
ちなみに、単に「キュー」と言う場合は「一番先に入れた要素を取り出す」、またキューの対義語の「スタック」は「一番最後に入れた要素を取り出す」というものを指します。
しかし、ただ何も考えずにlistやvectorといった直線的な配列にデータを入れただけでは、入れるあるいは取り出す度に配列を優先度順にソート（並び替え）しなければなりません、これでは動作が重くなってしまいますよね。
ここで、優先度キューの実装によく使われるのが、「ヒープ」というデータ構造です。要するに、「データを入れた時点で最高優先度のものが一目で分かる状態にできて、しかもデータを取り出した次にも（次の次にも）最高優先度のものが割と高速に決定できる」という２つの機能を備えたものです。
↓の図の様になっています。（今回の例題では短い板を先に使いたいので、数値の低いものを“優先度の高いもの”と設定した）
ヒープでは、辺によって繋げられた上下の関係だけが意味をなします。
辺の上側に優先度の高い（今回：数値の小さい）ものが、下側に低い（今回：数値の大きい）ものが入れられています。
こういう、一番上の一個の丸を開始点（この“根”という）として、そこから下へ下へと伸びていく構造を「木」と言います。ヒープは、この内「二分木」という、「一個の丸（ノード）につき、それに繋がる下位のノード（子）は２つまでである」ものの一例です。
要素を追加する時は、まず空いてる場所にその要素を追加します。
追加した要素の方が、その親より優先度が高くなってしまっていますね。それではここを入れ替えて、親の方が優先度が高くなる様に直しましょう。
ちなみに、逆側の子（[11]25）については、元々子より優先度の高かった親（[5]22）が入れ替えによって、更に高く（10）なるので、考える必要はありません。
これでも、まだ追加した要素（[5]10）と次の親（[2]18）でも優先度関係が逆ですね、入れ替えましょう。
これで追加はできました。次は要素の取り出しを行いましょう。
「常に子より親が優先度が高い」の法則により、根が一番優先度の高い要素である事が明らかです。
まず、根の中身を消去して、仮に一番最後の（一番下の子である）要素を根の所に移しましょう。
まあ、もちろん仮の根（[0]22）が一番優先度の高いはずがありませんよね。
では、その２つの子（[1]3,[2]10）のうち、どちらかが現在一番優先度の高いものです。だから、２つの子を比べて、より優先度の高い方と仮の根を入れ替えます。
同様にして、「どちらの子よりも優先度が高い」か、「子が存在しない（一番下の子である）」という状況になるまで、入れ替えていきましょう。
ヒープの実装について
前回説明したlistの様に、ポインタを使って実装することもできます。
また、先程の図に書いた「[i]」の様に、常に子の要素番号を、「親の要素番号*2+1」と「親の要素番号*2+2」に割り当てるようにする事で、vectorでも実装できる様になります。
（図）
今回のまとめ
ヒープによる優先度キューの実装の仕組みを解説しました。次回は実際にＣ＋＋にデフォルトで実装されているpriority_queueの使い方と、今回挙げた例題の解答プログラムを書きます。
用語集
※今回、出てくる用語が多かったので並べました。
・プライオリティキュー（優先度キュー）……取り出す時は常に優先度の高い要素を取り出す。
・木……一番上位である「根」から下位へ下位へと伸びる構造。
・二分木……木の一種。一つの親につき子は２つまで。
・ヒープ……二分木の一種。親は必ず子より優先度が高い。優先度キューの実装に用いられる。
・ノード……木の要素
・根……一番上位にあるノード
・辺……ノード同士を結ぶ
・親子……辺で結ばれた上位のノードと下位のノード
参考文献
【書籍】
秋葉拓哉、岩田陽一、北川宜稔『プログラミングコンテスト チャレンジブック』（毎日コミュニケーションズ、2010年09月）
【ネット】
ソースコード探険隊「ヒープ [Heap]」http://www.codereading.com/algo_and_ds/ds/heap.html
Programming Place Plus「●C++編（標準ライブラリ） 第７章 priority_queue」http://www.geocities.jp/ky_webid/cpp/library/007.html
未確認飛行 C「priority_queue（C++STL）」http://ufcpp.net/study/stl/priority_queue.html
Ｃ言語入門講座 延期のお知らせ
筆者の体調が悪くレポートの完成が間に合わない見込みとなってしまったため、Ｃ言語入門講座第５回の掲載を数日延期させていただきます。申し訳ありません。
第５回の講座はこの記事に上書きされます。
データ構造 第04講「動的なデータ構造ってどうやってるのさ」 08/12加筆
目次→美祢『データ構造』 目次 - 武蔵高中 ＣＰＵ愛好会 活動日誌
前回までは
要素の追加に応じて、動的にメモリを確保してくれる動的配列、「vector」について学びました。
今回は、前回扱わなかった「途中に要素を挿入する関数」等を扱っていきましょう。
vectorのイテレーター
途中で要素を挿入する関数は、vectorだけではできません。理由は後で説明します。ではそれに必要なiteratorについて説明しましょう。
std::vector<int>::iterator it;
この様にして、iteratorは宣言します。iteratorというのは、ポインタに似たような働きがありますが、さらにvectorや後述のlist等と言った、「コンテナ」と称される配列的なデータ構造の上で、指す先を前後の要素に動かせられるという特長があります。どうやって使うかというと、
#include <vector> //00 int main(){ //01 std::vector<int> vi; //02 std::vector<int>::iterator vi_it; //03 //04 for(int i=0;i<12;i++){vi.push_back(i);} //05 vi_it=vi.begin()+6; //06 vi.insert(vi_it,100); //07 for(vi_it=vi.begin();vi_it!=vi.end();vi_it++){*vi_it++} //08 vi_it--; //09 vi.erase(vi_it); //10 } //11
02行目でint型動的配列「vi」を、03行目でint型動的配列のiterator「vi_it」を宣言しています。
05行目で、viの要素は{0,1,2,3,4,5,6,7,8,9,10,11}となります。
06行目で、vi_itは、「vi[0]から６つ後」、つまりvi[6]を指すようになります。（この「+」「-」の使えるのは「ランダムアクセスイテレータ」という種類のiteratorだけで。後述するlist::iterator等では+や-が使用できません。）
07行目で、vi_itの指している「vi[6]」として、２番目の引数で指定した値（100）が挿入されます。。ここで、vi[7]以降を指していたポインタ・iteratorは無効になると考えてください。なぜなら、動的配列は配列の名の通り、「要素がメモリ上に続いて並んでいる」ものなので、確保していたメモリが足りなかったら、今度は２倍ぐらいの要素が確保できる、新しいメモリの領域が確保されて、vectorの内容はそちらに移動してしまうからです。
※vi={0,1,2,3,4,5,100,6,7,8,9,10,11}
08行目では、vi.end()は、viの最後の要素「の一つ次」（実際には何も無い所）を指します。また、「vi_it++」の様に、インクリメント・デクリメントも使用できます。（list::iteratorでも、この「++」「--」は使用できます）つまり、for文は「vi[0]から１つずつ後ろを見て、最後の一つ次にならない間」つまり「viの要素数だけ繰り返す」表現です。
iteratorの内容を見る時は、「*」を使います。また、構造体・クラスをvectorの要素の型に指定した場合、そのメンバーを見る時はアロー演算子「->」を使って、「vi_it->status」の様にします。
※vi={1,2,3,4,5,6,101,7,8,9,10,11,12}
09行目では、for文の最後に「vi.end()」を指してるvi_itを、一個戻します。ここではvi[12]を指すようになります。
10行目では、vi_itの指す要素、vi[12]の中身を消します。
※vi={1,2,3,4,5,6,101,7,8,9,10,11}
vectorのiteratorの動き
vectorは配列のように、つまり下の図のようになってメモリ上にいます。
なので、内部的には「+」「++」とか「-」「--」する分だけsizeof(Type)を足し引きしていけばいいわけです。（Typeは、vector生成の時に、「<>」の中に入れた型名）
リストという考え方
配列以外にも複数のデータを順序づけてまとめる方法はあって、この「リスト」という考え方では、「ある要素は次の要素とへのポインタを持っている」という構造で順序を付けます。
特に、「前の要素へのポインタ」を持っている物を、「双方向リスト」と呼びます。双方向リストの実装であるlistを例に図にするとこんな感じです。
listにもiteratorはあります。というか、listではvectorの様に「」が使えず、iteratorを使わないと中身を見られないので、必ず使うこととなります。
図の矢印は、それぞれ、「begin()の返り値はここを指すiterator」「end()の返り値はここを指すiterator」（begin(),end()はlistのメンバ関数）、「ここを指してるiteratorに++演算を行うとこっちを指す様になる」「ここを指してるiteratorに--演算を行うとこっちを指す様になる」ことを意味します。
この図の様に、各要素は前後の要素へのポインタで繋がっていて、iteratorのポインタ部分に前後を指すポインタを代入する事で++,--演算を行っている訳です。また、listの場合には、最初の要素の一個前と、最後の要素の一個後に、空白の（要素数に数えられない）要素が用意されています。end()等に使うためでしょう。
listのiteratorは大方vectorのiteratorと同じですが、vectorの時に使えた「+」「-」は使えず、「++」「--」による移動となります。それは図を見ても何をしているのか明らかでしょう。
また、この繋ぎ方の優れている点として、「要素の挿入や削除が一瞬でできる」という点があります。例えば、「５番目の要素として新しいのを入れたい」と思ったら、
[f:id:musashi_cpu:20110806035436j:image]
「(3)→(4)」だったのを「(3)→(8)→(4)」と繋ぎ直すだけです。一瞬ですね。vectorの様な「確保してるメモリで足りるか」って考える時間が無い訳です。
しかし、iteratorの「+,-,」でほぼ直接添字を指定するという事ができないので、一概に挿入が早いとは言えないかもしれません。順番を特に気にして、最初から最後まで読んでいく風に見ていく事の多いデータをまとめる時にlistを使ってみてはいかがでしょうか。
vectorとlistの共通点
「vectorのイテレーター」の項でやった例文をlistで行うと、
#include <vector> //00 int main(){ //01 std::ist<int> li; //02 std::list<int>::iterator li_it; //03 //04 for(int i=0;i<12;i++){li.push_back(i);} //05 for(li_it=li.begin(),int i=0;i<6;i++){li_it++;} //06 li.insert(li_it,100); //07 for(li_it=li.begin();li_it!=li.end();li_it++){*li_it++} //08 li_it--; //09 li.erase(li_it); //10 } //11
こうなります。06行目（+,-が使えないので++,--をループして添字を指定する）以外は同じですね。
08/21加筆:listとvectorの相違点としては、iteratorの仕様の他に、 listにはあるpush_front(),pop_front()という関数がvectorにはないという事も挙げられます。 おそらく、vectorではbackとfrontで処理の仕方が圧倒的に違う （backなら普通に追加するけれど、frontなら全部後ろに動かしてから最初の要素として入れ込む）ためだと思います。
Ｃ++にはこの様にどれを使っても同じ名前の関数・演算子で動かせるような「STL」というものがあるので、利用すると便利でしょう。
今回の終わりに
今回学んだ、「リスト」の考え方は、プログラミングの深い世界に入るととても重要になってきます。
例えば、↓の画像の様な、各マスが６角形のマップがあるとします。これ全体を管理したい時に、二次元配列を使う方法や、一次元配列を使う方法がありますが、こういう「まっすぐ一列」と言いづらい形のものの位置を配列の添字で扱うと、間違いや混乱を招きやすいです。
それならば、各マスを「マスの情報（地形等）、左上・上・右上・右下・下・左下のマスへのポインタ」という情報の入ったクラスにする事で、リストの様にポインタで隣のマスに移るというデータ構造が出来上がります。
次回やることは、今のところ未定です。今までやったデータ構造の応用か、新たなデータ構造かのどちらかになります。
記事の完成が１週間遅れて申し訳ありませんでした。
参考
Programming Place Plus「●アルゴリズムとデータ構造編 第１２章 双方向リスト」http://www.geocities.jp/ky_webid/algorithm/012.html
C/C++ リファレンス「C++ イテレータ」http://www.cppll.jp/cppreference/iterators.html
第０４回「変数の四則演算」
今回の理解目標
- 変数の加減乗除
- 四則演算の簡略表記
- インクリメント・デクリメント
前回は変数に数値を代入する方法について解説しました。しかし、ただ数字を入れておくだけでは、正直変数の機能の一毛も使っていないといわざるを得ません。ということで今回は変数を使って四則演算をしてみましょう。
※四則演算
足し算、引き算、掛け算、割り算のこと。
変数の加減乗除
さて、加減乗除処理のうち足し算、引き算に関しては直感的に理解しやすいと思いますのでいきなりソースコードから載せてしまいます。※加減乗除
足し算、引き算、掛け算、割り算のこと。
※ソースコード
プログラミング言語で書かれたプログラムのテキストファイルのこと。
わかりやすく換言すると、人間が書いたプログラムの文字列。
「では、次のプログラムを見てください」の「プログラム」と同義。
ということで以下のソースコードを見てください。
garbage + 110; garbage - 119;
garbage変数はすでに宣言されているものとします。
見ての通り、そのままです。Ｃ言語なので最後にセミコロンはつけますがそのままです。もはや他に表現の仕様が無いほどにそのままです。
では、掛け算と割り算に関してはどうなのでしょうか。
garbage * 115; garbage / 117;
残念ながらこちらは見ての通り、というようには行かないと思います。
Ｃ言語のようなプログラミング言語においては、掛け算を表す記号は「×」ではなく「*」を、割り算の記号「÷」ではなく「/」をそれぞれ使います。
何故こんなにわけのわからないことになっているかというと、理由としては代入記号が「←」ではなく「=」が使われているのと同じです。つまり、キーボードのどこを探しても×記号や÷記号はありません。よって、代わりに「*」や「/」を使って対応したのです。
四則演算、加減乗除はこのようにして行います。また、上の例では全て「変数と定数」の間での計算しか行っていませんが、変数と変数、定数と定数の計算も行うことができます。二つ以上つなげることも可能です。
※定数
５３、８７、６３４など普通の数字のこと。
変数と違い「変わらない定まった数」という意味で定数と呼ばれる。
例としてはこんな感じになります。
int garbage = 53; int peepor = 110; garbage + peepor;
7 + 7 + 7;
さて、これで四則演算ができる……ように見えますが、実は大きな落とし穴があります。ということで次項ではそれに関して解説いたします。
値の代入
四則演算のプログラムの組み方もわかったことですし、実際にプログラムを組んで見ましょう。
ということでこのように作成しました。コンパイルも通っています。では、実行結果を見てみましょう。
……あれ？
暗算すればわかると思いますが、５３＋１１７＝１７０です。しかし、表示は５３。これはどういうことか。コンピューターが計算ミスをしたのでしょうか？ 実は、この処理では５３と出るのは当然なのです。５３、最初にgarbage変数に代入した数値です。つまり、これでは足し算はちゃんと行われていなかったということになります。
とはいっても「ちゃんと」行われていなかっただけであり、足し算自体が行われていなかったのではありません。じつは、足し算処理は行われていたのですが、足し算によって生まれた「結果」がそのまま中へと消えてしまったのです。……と抽象的なことを言われても意味がわからないかと思いますので、どうすればいいのかを示しましょう。以下のように書いてください。
garbage = garbage + 117;
どういうことなのか解説しましょう。
「garbage + 117;」と書かれただけでは、そこに値、もしgarbage変数に53が入っていたとしたら170という値が「ある」だけでしかないのです。つまりプログラム中に
170;
と書かれているのと同じことなのです。これでは何も起きるはずがありません。
そこで、足し算して得られた結果をgarbage変数に代入することによって初めてgarbage変数に数字が加算されます。
上の例のように書くと
garbage = 170;
となった、ということです。
さて、ここで「何でgarbageにgarbageが代入されてから+117されて結局ただのgarbageにならないんだ！」と思ったかたもいらっしゃるかもしれません。この理由はただ単に「=」処理が最後に行われるからです。他にもいろいろな計算記号が出てくると、厳密には最後に代入が行われるとはいえなくなってしまうのですが、少なくとも「+」「-」「*」「/」「=」の五つの記号の中では「=」が一番最後に行われるように決められているので上のようなプログラムでうまく動くわけです。
さて、プログラムを変更してもう一度実行してみましょう。
このようにコンパイルも通り、実行結果もちゃんと１７０になりました。
この法則は足し算だけではなく引き算、掛け算、割り算でもちゃんと成り立ちます。
今度こそこれで四則演算がちゃんと行えるようになったのですが、正直変数の名前を二回書くのが面倒ではありませんか？ そういうみなさんのために、Ｃ言語にはちゃんとこれを省略して表記する方法があります。
ということで次項はそれの解説となります。
簡略表記
四則演算で値を代入するときに、同じ変数名を二度も書くのは正直面倒です。Ｃ言語開発者側もそれはわかっていたようで、その変数にある数値を足したり引いたり掛けたり割ったりしたい場合は以下のような簡略表記を使うことができます。garbage += 117; garbage -= 110; garbage *= 119; garbage /= 171;
上のように、「変数名 演算子= 四則演算したい値 ;」のように書きます。
簡略しないで書くと上の例はそれぞれ
garbage = garbage + 117; garbage = garbage - 110; garbage = garbage * 119; garbage = garbage / 171
と書かれていることになります。この表記を使えば同じ変数名を二度書くという煩わしいことをしなくても済みます。
またこれは現段階では読者のみなさんにはわからないことなのですが、プログラミングにおいては「変数の値を１だけ足したい」「変数の値を１だけ引きたい」ということが多々起きます。これは普通に上の簡略表記を使っても書くことができるのですが、このような必要性に答えてＣ言語には「１だけ足す・引く」専用の簡略表記も用意されています。それが以下の例です。
++garbage; --garbage; garbage++; garbage--;
変数名の前か後ろに「++」をつけるとその変数の値が１増加、「--」をつけると１減少します。「++」の方をインクリメント、「--」の方をデクリメントと呼びます。
「何故同じ事をするのに前と後ろの両方の書き方があるんだ！ 混乱して両方に書いたらどうしてくれるんだ！」と思う方もいらっしゃると思いますが、厳密な意味ではこの二つの表記は異なっているのですが普段はそんなことを意識することも無いと思いますので、使いたくなった場合は好きなほうをお使いください。
ちなみに自分にＣ言語を教えてくださった師匠（いや先輩ですが）の話によると、記号を後ろにつけるより前につけたほうが若干処理速度が速いそうです。どうしてそうなるのか自分でも理解していませんし検証もたしかあまり結果はでなかったので小文字で書かせていただきますが。
課題
以上で今回の内容は終了となります。次回までの一週間の間以下の課題プログラムを組むことで今回の内容を復習しておいてください。１．変数を用意し、順番に「＋２」「−４」「×８」「÷２」としていったときの計算結果を表示するプログラムを作成する。（%dの後に空白を入れないと数字のつながりがわかりにくくなるので注意）
２．「++」、「--」でそれぞれ変数の数値が１ずつ変化していることを確認するプログラムを作成する。（どのようなスタイルでも良い）
３．「++変数名++」や「--変数名++」など混ぜて使ったときにどうなるのかを確かめる。
今回の課題は内容に対して数は少なめですが、その代わり一つ一つのプログラム、特に課題１が長くなるように作成しました。難しい部分もあるかもしれませんが、そういう時はこの講座を読みながらがんばってプログラムを組んでみてください。
それでは、また来週の火曜日に。
