スポンサーサイト

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

その22 深さ優先探索と幅優先探索編

今回はグラフの深さ優先探索と幅優先探索についてやりました。
よく聞く単語だったので、どんなものかと思っていたら、そんなものすごいものではないわけでした。

深さ優先探索は行けるところまで行く、幅優先探索は横方向に調べて行く(言葉にできないw)みたいな。
雑巾がけで言うと、真っ直ぐ往復するのが深さ優先で、ワイパーみたいに横に拭くのが幅優先、みたいな?

実装は、深さ優先は行けるところまで行く→戻る→行けるところまで(ryという再帰で、幅優先探索についてはキューを使うそうです。
節点1からスタートするとして、まず1をキューにエンキューします。
次に、1をデキューして(これが探索済みになる)、1とつながっている節点を昇順にエンキューします。
1つデキューして、それとつながっている節点を……というのを、キューが空になるまで繰り返せばOKです。

そういうわけで、二つの探索はわかったので、それを使って一筆書きの問題を。
一筆書きの解を求めるには、深さ優先探索をして、全ての道を通りきったときに最初の場所に戻っていればそれが解となります。
あー……なんか今日やったことは言葉にしづらくて困る。
とにかく、深さ優先探索と幅優先探索がどういうものかわかったよ! ってことなんです!!(結論)

↓コード

続きを読む

スポンサーサイト

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

アルゴリズム勉強記21~木編3 ヒープ木~

ヒープ木というと、親>子か親<子の木ですね。
前にヒープソートを扱ったときにもやったのですが、今回また1からやり直しました。

まあ、結局ポイントは

親の添字=子の添字÷2
左の子の添字=親の添字×2


これに尽きるみたいですね。
これされわかってればなんとかなると思います。

本に則って、ヒープを構築するshiftdown()関数を実装しました。
shiftdown()関数は、引数に ・親の位置(交換の始点)、・ヒープの大きさ、・ヒープ本体をとり、第1引数の親を然るべき位置まで下方移動させます。

まあ、別に関数化する必要はないような気もしますが、一応ww

で、最終的にできたヒープソートのコードです。
おお、これで多分ヒープソートもゼロから書けるようになった、はず。
多分3日で忘れてそうですがwww

↓コード

続きを読む

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

アルゴリズム勉強記⑳~木編2 再帰と深さごとの表示~

今回は、前回の動的なtnode型を使って、再帰によってノードを追加します。
再帰によってノードを追加するべき場所まで潜っていって、ノードを作成します。
こういう処理は再帰で書くとかなりすっきりしますね。

で、深さごとの表示とは、ルートのノードを深さ0、その子たちを深さ1、その子たちを深さ2……としていったとき、深さごとにノードを表示するというものです。

①深さlevelのノードそれぞれについて、値を表示イする。また、子がいるか調べ、いる場合はスタックに追加し、nをインクリメント
②nの値が次の深さの子の数で、スタックにはその子が積まれている。levelをインクリメント
③child=nとし、①へ戻る

という感じです。
また、オプションとして、connect構造体を使って、ノードの親を表示するようにしました。
connect構造体は、tnode*(ノード本体)、parent(親)、direct(左の子か右の子か)から成り、↑の①で、子に親の情報を持たせることができます。

まあ、深さごとに表示して何になるんだって思いますが、なんであれ巧妙な手法に多く触れるのは良いと思いますですよ。

↓ということで以下コードです。

続きを読む

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

アルゴリズム勉強記⑲~木編1 静的と動的な木~

今回からは何回か通して「木」についてやります。
木といえばフォルダなどで身近なデータ構造ですが、正直あんまり(というかほとんど)使ったことなかったです。
なんか、難しそうだな~と漠然と避けてたのかもですが、今回本に載っていたのでここでしっかりとやっておくことに。

読んでみたらこれ、……難しくなくね? 要するに、リスト構造がちょっと変形しただけじゃね? うはwww

・データ
・左の子へのポインタ
・右の子へのポインタ

から成るノードをくっつけていくだけでした。
いつだかヒープソートで木を使ったときは、なんか配列でほげほげしていたのでよくわからなかったのですがw

ということで以下コードです。
前者が静的な木で、後者が動的な木です。
後者の方が分かりやすいと思いました。ということで、これからは後者の木でやっていく予定です。


↓コード&コメ返

続きを読む

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

アルゴリズム勉強記⑱~スタック編(逆ポーランド記法)~

中置記法というのは、a + b - c * dのような普通の数式の書き方で、逆ポーランド記法とは

ab+cd*-

のような書き方です。基情でたまに見かけます。

これの解読方法は、

・オペランド(演算対象)ならスタックに積む
・演算子ならスタックから2個ポップして計算し、結果をスタックに積む

というものです。
なんというか、スラスラ計算していく感じで、↑の例なら

aとbを足して、
cdをかけて、
結果を足して

という感じで、先頭から読んでいくとそのまま計算できるという利点があるらしいです。
まあでも、やっぱり人間には中置記法の方がわかりやすいですけどね。


そこで、中置記法の式を逆ポーランド記法に直すプログラムです。
正直、アルゴリズムは何でそうなるのかよくわかってません。だめじゃん。


#include<iostream>
using namespace std;

int main()
{
int prio[256];
int i;
for(i = 0; i < 256; i++)
{
prio[i] = 3;
}
prio['*'] = prio['/'] = 2;
prio['+'] = prio['-'] = 1;
prio[0] = -1;
char stck[100], polish[100];
stck[0] = 0;

string str;
cout << "中置記法を入力:";
cin >> str;

int ptr = 0, ptr2 = 0;
for(i = 0; (unsigned)i < str.size(); i++)
{
while(prio[str[i]] <= prio[stck[ptr]])
{
cout << "polishに" << stck[ptr] << "を積んだ." << endl;
polish[ptr2++] = stck[ptr--];
}
cout << "stckに" << str[i] << "を積んだ." << endl;
stck[++ptr] = str[i];
}
while(ptr > 0)
{
polish[ptr2++] = stck[ptr--];
}

for(i = 0; i < ptr2; i++)
{
cout << polish[i];
}
cout << endl;

return 0;
}



ただし、かっこを含む式には対応しておりませんw
え、結局何を学んだんだ……? せいぜい、stck[0]に番兵を置いて処理を簡単にするとかそのくらいじゃね……?
ま、まあいいじゃん。


コメ返

続きを読む

プロフィール

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。