VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
348(1): 333 2019/02/21(木)00:07 ID:JBRYA9bz(1/4)調 AAS
通りがけ順は、左の子がある限り、ドンドン降りていく
左の子から上に上がったら、そのノードを記録して、右の子へ降りる
右の子へ降りたら、また左の子がある限り、ドンドン降りていく
350(3): 333 2019/02/21(木)00:10 ID:JBRYA9bz(2/4)調 AAS
それを再帰を使わずに実装していることなんて、あるかな？
漏れは、思いつかない
アルゴリズムのスレで聞いたら、どうかな？
354: 333 2019/02/21(木)08:40 ID:JBRYA9bz(3/4)調 AAS
順位キュー(優先度付きキュー、priority queue)は、ダイクストラ・A* で使っている。
確か、2分ヒープと同じで、最小値だけがtop に来る。
他のノードの関係は、保証されないのだったかな？
>>321
の図で説明すると、
まず、4に来るとキューに、[4, 2, 6] を追加すると、[2, 4, 6]となる
削除しないで、peek だけすると、最小は2なので、2へ行き、[1, 3] を追加すると、[1, 2, 4, 6, 3]となる
そこでpeekすると、最小は1なので、1へ行き、追加するものはないので、
1をpop して、peekすると、最小は2なので、2へ戻り、
2をpopして、peekすると、最小は3なので、3へ行き、追加するものはないので、
3をpopして、peekすると、最小は4なので、4へ戻り、追加するものはないので、
4をpopして、peekすると、最小は6なので、6へ行き、[5, 7] を追加すると、[5, 6, 7]となる
そこでpeekすると、最小は5なので、5へ行き、追加するものはないので、
5をpopして、peekすると、最小は6なので、6へ戻り、
6をpopして、peekすると、最小は7なので、7へ行き、追加するものはないので、
7をpopすると、キューが空
プログラミング・コンテスト・チャレンジブック、第2版、2012
言語は、C++で、ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる
355(1): 333 2019/02/21(木)08:56 ID:JBRYA9bz(4/4)調 AAS
2分ヒープ(BinaryHeap)は、
優先度つきキュー (順位キュー、priority queue)や、
ダイクストラ法 (Dijkstra's Algorithm)で使っているけど、
ここで、JavaScript の配列を使って、2分ヒープを作っている。
http://jsdo.it/michihito/bGH5
PushObj, PopObj を見たけど、再帰は使っていない！
追加・削除の計算量はともに、O(log n) です
確か以前も、このスレで、このアルゴリズムに改良点があるとか、ピラフに指摘されたはず
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.028s