データ構造とアルゴリズム総合

1 ：2012/03/21 〜 最終レス ：2012/10/29

データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

2 ：

【参考サイト】
アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

3 ：

アンチエイリアスつきのブレゼンハム線を教えれ

4 ：

ブレゼンハムってサブピクセルレンダに応用してうまみなんてないだろ

5 ：

純粋関数型言語のためのデータ構造
Purely Functional Data Structures
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Purely Functional Data Structures
http://www.amazon.co.jp/dp/0521663504
Purely Functional Data Structures読書会議事録
http://wiki.haskell.jp/Workshop/ReadPFDS/
20分でわかる Purely Functional Data Structures
http://www.kmonos.net/pub/Presen/PFDS.pdf

6 ：

角Aから角Bに時計まわりに方向転換するとき途中で角Cを向くか真偽値を返すkaku(A,B,C)をくれ
（ラジアンで指定　一周以上はしない　kaku(π*30, -π*20+3, 4)ならfalse）

7 ：

こいつなんで偉そうなの

8 ：

bool kaku(double a, double b, double c)
{ return b <= c && c <= a; }
「kaku(π*30, -π*20+3, 4)ならfalse」は論理エラー。

9 ：

>>8
２πnラジアン=0ラジアン（nは整数）である事を利用して
a-bとa-cを0以上2π未満に正規化し、a-bの方が大きければtrueです。
ちなみにkaku(π*30, -π*20+3, 4)=kaku(0, 3, 4)はtrueです。

10 ：

falseじゃね?

11 ：

>>10
0ラジアンを右とするとπ/2ラジアンは上、πラジアンは左、3π/2ラジアンは下です。
kaku(0, 3,4)は、0ラジアン(右)から時計回りに3ラジアン(左より少し上)まで方向転換し、
途中で4ラジアン(左下)を向くからtrueです。
kaku(0, 3,4)=kaku(2π, 3,4)だから、
|aからbへの時計まわりの移動量|=|bからaへの反時計回りの移動量|=a-b=2π-3
|aからcへの時計まわりの移動量|=|cからaへの反時計回りの移動量|=a-c=2π-4
2π-3>2π-4なのでtrueです。

12 ：

>>11
× 　a-b=2π-3、 a-c=2π-4
○　a-b≡2π-3 (mod 2π)、 a-c≡2π-4 (mod 2π)

13 ：

ム板民と数学人間でY軸方向の符号が違うから差が出るな

14 ：

だいたいの感じでコーディングしてみた。
動くかは知らん。
bool kaku (double a, double b, double c)
{
　　double na = fmod(a, PI*2.0);　　if (na < 0.0) na += PI * 2.0;
　　double nb = fmod(b, PI*2.0);　　if (nb < 0.0) nb += PI * 2.0;
　　double nc = fmod(c, PI*2.0);　　if (nc < 0.0) nc += PI * 2.0;
　　// 時計まわりの方向がプラス回転
　　if (nb < na) nb += PI * 2.0;
　　if (nc < na) nc += PI * 2.0;
　　return (nc <= nb);
}

15 ：

□□□□□□□□□　・右の図の□を■にしてすべての■をつなげたい
□■□■□■□■□　・毎回違う結果にしたい
□□□□□□□□□　・無駄がないようにしたい
□■□■□■□■□　・輪にならないようにしたい
□□□□□□□□□　・よろしこ
□■□■□■□■□
□□□□□□□□□
□■□■□■□■□
□□□□□□□□□

16 ：

□□□□□□□□□
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□■□□□□□□　・これはありか
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□□□□□□□□

17 ：

つ ローグライクのダンジョン生成参考

18 ：

何というか・・・宿題スレでやれ

19 ：

ジオロケーションのアルゴリズムで相談をお願いします。
データレコード
struct
{
float　　x；
float　　y；
String　buffer;
};
が数千件あるテーブルがあるとします。
その中からユーザーの座標(float ux. float ,uy)の半径 R(float)以内にある
データレコードのbufferを取り出すにはどうすれば一番効率が良くなるでしょうか？
テスト段階での条件では
範囲としては関東全域
Rの値は最大 100m
サーバー側のクロックは
CPUクロック：3GB
使用可能メモリ：6GB〜10GB
レコードの平均使用容量：112byte
クライアント側はAndroidを利用してサーバーからへ座標を渡して、情報をリクエスト、
また新しい情報をポストするのみになります。
送受信にはUDPパケットの使用を考えています。
また挿入や削除がしやすいというのが第一の条件となっています。
なのでデータはすべてメモリ上におき、テキストエディタみたくギャップバッファと地域の細分化、リンクドリストを
複合的に持ち合わせて、定期的にＤＢへのアップデートを行っていこうと考えております。
以上を踏まえてどなたかアドバイスなどをいただけないでしょうか？

20 ：

>>19
素人なりに考えた。
全データを100m四方のグリッドで分割しといて(ハッシュででも)、
ユーザ座標含めた隣接9グリッドについてのみ計算する。
件数も少ないし計算も複雑でないから、複雑な枝刈りはあんま意味ないとおもう。
てか数千件ならふつうに総当りでもいけそう。
じぶんがつくるなら、サーバは起動時とユーザシグナル受信時にDBから読むだけで
データ管理とは分離させる。

21 ：

>>20
なるほど
参考になります。
ではデータはグリッドごとということして挿入、削除をすればいいということですね
ありがとうございます。

22 ：

>>19
kd-treeがいいんじゃないかな。
フォトンマッピングでぐぐると、近傍のフォトン探索とかの使用方法が出てくると思う。

23 ：

>>22
フォトンマッピングですね
調べてきます。
ありがとうございます。

24 ：

>>16
なしだぜ

25 ：

>>15はアイちゃん

26 ：

>>15
>無駄がないようにしたい
下記のように■同士を最短距離でつなげたいという意味ですか？
□□□□□□□□□　・右の図の○を■にしてすべての■をつなげたい
□■○■○■○■□　・毎回違う結果にしたい
□○□○□○□○□　・輪にならないようにしたい
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□□□□□□□□□
これで全ての■がつながるなら24個の○のうち最低15個が■ですね。
15個の■と9個の□で全ての■をつなげた時は輪はありません。
以下の手順で全ての組み合わせが求まります。
１　24個の○のうち15個を■、9個を□にした順列を順番に走査する。
２　今調べている順列に上下左右が□の■があればボツ。
順列を再帰呼び出しで作り、
1〜9個目の□の位置を決めるごとにその上下左右の■を調べ、
■の上下左右が全て□だったらその枝の走査を打ちきると効率的です。

27 ：

面白そうな問題なんだが、
>>26の言うように「無駄がないように」の意味があいまいなんだよね。
>>26のような解釈でOKなのか、それとも探索に無駄がないようにという意味なのか。

28 ：

>>26
そうその○の位置だけ変えるって意味だぜ
探索はどうやってもいいぜ
それだと2組に分かれる可能性があるぜ
あと15個以下でも全部繋げられるから輪になるかもだぜ

29 ：

■
■　・これが孤立しているケース
■

30 ：

>>28
>それだと2組に分かれる可能性があるぜ
確かにボツにする条件が不十分ですね。
それに15個を○から●にして2組以上になったら必ず輪ができます。
最後に全部つながったか確認する必要があります。
□□□□□□□□□
□■●■●■●■□
□●□●□○□○□
□■●■●■●■□
□●□○□○□○□
□■●■●■●■□
□○□○□○□○□
□■●■●■●■□
□□□□□□□□□
>あと15個以下でも全部繋げられるから輪になるかもだぜ
左上の■に残りの15個の■を●でつなげていくと考えてください。
1個の○を●にした時に左上に新たにつながる■は高々1個だけです。
だから全部の■をつなげるには最低15個の●が必要です。
1個の○を●にした時に輪ができたら新たにつながる■はありません。
だから15個の●だけで全部つながったら輪はありません。

31 ：

・開始点の■を決める
■
A
■B■　　　
C
■
・次に繋がる点をリストアップ　　
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
■□■
.A　　B
■■■E■　　
.C　　D
■□■
・次に繋がる点をリストアップ　　
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
・再帰

32 ：

勤務表作成アルゴリズム募集。
ExcelVBAで勤務表を作ろう
http://toro.2ch.net/test/read.cgi/tech/1329803312/

33 ：

勤怠表はアルゴリズムってより
対象者向けインターフェースの推敲が難しいからな
ライン工相手に出勤退勤毎にキーボード叩けなシステムとかアホ過ぎるし

34 ：

タイムカードをがっちゃんがっちゃん押したらUSBでPC等につながって自動管理、とかの機械ありそう

35 ：

あながち馬鹿に出来ない
押し忘れとか、日付が変わってから退社とか、
３交替の夜勤とか
下手なものを作ると出勤か？退勤か？すら後で分からなくなるｗ

36 ：

>>31
エクセルで作ったぜ〜
http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=mei.xls

37 ：

>>34
うちのは無線LANで飛ばしてるお

38 ：

うん

39 ：

タンピンリャンペーコーを判別せよ

40 ：

まず雀頭１と順子４つになっているか確認
その後１９字牌がないがチェック　ない場合成立
二杯口は順子をグループ化してふたつどういつかチェックすればいいんでね
平和だけどタンヤオって時点で役牌じゃない＆二杯口も前提条件だから
両方が成立したとき自動的に成立
タンピンリャンペーコーを判定する専用ならこういうやり方でいいんでね

41 ：

>>39-40
君らみたいなのが宇宙麻雀作るんだろうな(´･ω･`)
>>40
待ちは？

42 ：

> 風牌や三元牌で順子可能
> ドラのみ和了
> 立直後明槓
> メンタンピン一盃口が役満
> 白があっても清一色可能
> 一気通貫が役でない
これはひどい

43 ：

宇宙麻雀ググッたけど
設定ミスで>>42とかプログラマー神すぎるだろ

44 ：

閉路を沢山含んだインバースキネマティクスって
どうやればいいの？
もう既に有名なアルゴリズムとかあるの？

45 ：

2-正則な閉路だけ考えた場合、移動した頂点から交互に重複するまで解決していくだけだし
そこから伸びた枝は普通に解決出来ないか？

46 ：

>>45
注意してもらいたいのは、要件は「閉路を含んだ」ではなく
「閉路を沢山含んだ」になっている点です。
例えば、以下のような格子状の関節(5*5)をもっている場合、
リアルタイムで計算させるのは結構難しいかと。
┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘
もうすでに誰か偉い人がアルゴリズムを考えていたりしないかな、と。

47 ：

一度通った道を再び通らないようにすることだけ考えりゃいいんだから
結局は同じじゃねえの

48 ：

「薔薇の名前」のアルゴリズムは使えないか？

49 ：

>>15
http://toro.2ch.net/test/read.cgi/tech/1313183984/187

50 ：

>>47
もし簡単ならば、そのアルゴリズムを教えてほしい。
そしてその計算量の見積もりも。
でも、それが簡単じゃないからこそ今のIKは
軒並み「ループ無し縛り」を課している訳で。

51 ：

なんでQZがいんの

52 ：

>>49
ありがたまきんΩ

53 ：

さめがめの最適解を求めるアルゴリズムを
作ろうとしています。
□□●●□□●□●
○■●■●■●■□
○●●●□○□○●
□■●■●■●■□
■●□○□○□○●
□■●■●■●■●
■○□○□○□■□
□■●○●■●■□
■□□○□■□■■
ルール：
　隣り合う２つ以上の連続した同じ種類の記号は消去できる。
　重力あり。消えたら下に詰める。
　連続で消せたら高得点
この仕様で、連続して消せる最大の回数を求めるのと、
完全に消去するという二つをそれぞれで考えたいのですが、
総当りだとものすごい時間がかかりそうなので、何か
数学的な理論や手法などはないでしょうか。
１）消せるブロックの集合を探す
２）ブロックを消す
３）消えたブロックの上のマスを落とす
４）１）に戻る
特に１）の部分の隣り合う２つ以上の連続した同じ種類の記号を
探すのが結構時間がかかりそうなので時間短縮する方法が
あれば教えてください。

54 ：

さめがめってNP完全でしょ。
> 総当りだとものすごい時間がかかりそう
試してはいないんだな。

55 ：

発散しそうもないし、先ずは試してみたらいいんじゃね。

56 ：

消せるブロックの集合が崩れてない時に
その情報を次のターンに持ち越せば少しは軽くなるな

57 ：

さめがめってよくフラッシュとかでもゲームあるけど、
ブロック消すところはなぜあんなに早いの？
思い浮かんだロジックだと、>>53を例にすると、
１）9x9のテーブルを２種類作る（Ａテーブル、Ｂテーブル）
２）Ａテーブルに記号別にフラグ（たとえば１〜５）を埋め込む
３）たとえば左上を基点に上下左右に同じ種類の記号が
　　あるか調べる
４）あったらＢテーブルに消せる場所に種類のフラグを埋め込む
５）基点から３）と４）を実行して全部調べる
６）Ｂテーブルに消せるマスがあれば、同じ位置のＡテーブルのマスを空白にする
７）Ａテーブルの空白のマスを消去し、上にマスが残ってたら下に下ろす
ここまでを一瞬でやってるわけですよね？
もっと簡単にできる方法があるのかな。

58 ：

1GHzのCPUで、一マスの処理が１０００命令かかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。

59 ：

なんで >>58 は、1クロック1命令だと思ったんだろう

60 ：

ベンチでFLOPS計測するしかないってか。

61 ：

え、でも計算量って１マス検査するのに、残りの８０マスをチェックしないと
いけないから、９ｘ９のマスのチェックをするのに、
８１×（８１−１）×・・・ってなるんじゃないの？

62 ：

隣り合ってるマスだけでいいだろ。

63 ：

1クロック1命令、っておおざっぱな見積りでは普通に使うだろうが

64 ：

>>63
いいからあなたはPentiumだけ使っててください。

65 ：

大昔のBASICでは、PAINT文で塗りつぶしを行うと
塗りつぶして行く様子が目で見えてたなぁ

66 ：

>>64
１クロック１命令の方がCPUとして少数派だと思うが・・・
２，３クロック１命令で見たほうが良くないか？

67 ：

ごめ・・・
>>66は>>63向け

68 ：

クロック周波数で性能は比較できない

69 ：

総括すると>>63でオーダとしては妥当ってことじゃないの？

70 ：

ｽﾚ違いだし、とっとと収束させるべきなんだろうけど…
>>69
>総括すると
頭おかしいのか？

71 ：

オーダーは変わらない。
1命令が1クロックだろうが、100クロックだろうが変わらない。

72 ：

話がかみ合ってなくてワロスｗｗｗ

73 ：

1GHzのCPUで、一マスの処理が１０００クロックかかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。
これでおk。

74 ：

>>68 IPC（CPI）が同じなら、クロックが倍のコンピュータなら、
周辺による遅れがなければ、倍の性能だろうが。バカか？

75 ：

アルゴリズムの文脈で、計算量ってどう見積もるのか知らない奴がこのスレにいるとは

76 ：

定数倍が重要なことも時にはあるだろうが
最初のレスがゲームについてなんだし

77 ：

>>74
ふつー、バス速度は絶対に倍にはならないですよね…

78 ：

>>62
そっか。
となれば、最大８１×４回（上下左右）チェックすればいいだけか。
さらに端っこのますは片側は壁だからもっと少ない計算量で
済むんだな。

79 ：

>>75
見積もりといえばKKD法だよな。

80 ：

スケープゴート木って、サイズ計算に時間食い過ぎるな。
かと言ってノードにサイズ情報埋め込むのは本末転倒な気がするし。

81 ：

俺さ、ハッシュマップってのを思いついたんだが

82 ：

車輪

83 ：

八種抹粉

84 ：

いらなーい

85 ：

一度車輪をやらないと上を行くアルゴリズム作るのは無理

86 ：

さめがめ：連続で消せたら高得点
てナニ？

87 ：

イナズマの描画法をおしえれ

88 ：

Ｎ

89 ：

Piローダーだっけ、イナズマローダーって

90 ：

>>88
Z じゃね?

91 ：

picとかだね

92 ：

CADで言うところのフィレット
２つの線分があり、端点の一つを共有している状態で
半径５のフィレットを行いたい
つまり、点P1(x1,y1) 点P2(x2,y2),点P1(x3,x3) で　点P2の部分をフィレットしたい
お分かりなる方がいたらおしえてください

93 ：

内角に辺5のひし形作って対角を中心とした円

94 ：

>>92
点と直線の距離の公式を使って垂線の長さ5の方程式を二つ立てる。
これを連立方程式として解くと円の原点候補が二つ求まる。
点P2→点P1と点2→原点候補の内積が正になる方が円の原点である。
原点を中心とした半径5の扇を描く。
>>93
菱形の辺の長さが5なら内角が直角の時以外は円の半径は5より小さくなります。

95 ：

ArcTo関数か
俺なら自前でBezier2Dするねｷﾘｯ

96 ：

test

97 ：

2と3だけを複数回かけてある数Aにもっとも近い数を作りたーい

98 ：

総当り

99 ：

宿題か

100read 1read

1read 100read
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲

懐かしのMS-DOSプログラミング (380)
Borland Developer Studio 2006 No.13 (268)
■暗号技術【ROUNDsurea】■ (542)
【Perl,Python,PHP】LL ﾊﾞﾄﾙﾛﾜｲﾔﾙ 27【JS,Ruby】 (357)
C言語をやりたいんですが (261)
MFC相談室 mfc22d.dll (304)
--log9.info------------------
三菱DVD専用スレ 2枚目 (404)
CD-Rがコンポとかカーステで聞けないのは、なぜ？ (338)
UltraISO (519)
【韓国製】LG｢GSA4040B｣その11【粗悪品】 (681)
VideoCD・DVD-Video総合スレッド (286)
【マクセル】イケショップ祭り【偽造ID？】 (630)
二度と見ないのにDVDに焼く理由は？ (216)
【国産】日本メーカーのメディア　Part1【海外産】 (533)
GigaStorage総合スレッド（DVD系） Part3 (249)
ホログラム光ディスク「HVD」容量200GBで製品化 (230)
【King of 糞メディア2003】最悪の糞メディアを選べ (289)
東芝　SD-R5002　Part10 (809)
さよならプレク。思い出をありがとう。 (217)
買ってきたDVDメディアのIDを晒すスレ -3枚目- (673)
HD-BURN対応DVD±RWドライブpart4 (407)
○○○　磁気研究所　○○○ (432)
--log55.com------------------
【NMB48】大段舞依応援スレ★8.1【まいち】
【御披露目して】ポスト山田が嫌いな奴が集まるスレその3【5分でキス写メ発覚】
チームB�U「逆上がり」公演　記録スレ
【NMB48】石塚朱莉応援スレ★17【あんちゅ】
【NMB48チームN】山尾梨奈応援スレ☆2【やまりな】
【NMB48】山本彩応援スレ★39【さや姉】
【元NMB48】 松岡知穂応援スレ☆11【ちほ！　ちーちゃん❤】
【NMB48】白間美瑠 応援スレPart11【みるるん】