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

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 ：

宿題か

100 ：

文字列が正しくデコードされてるか試験する、という目的の下、文字列の尤度を求めるために、
文字コードの範囲を確率変数として教師信号を用意（様々なファイルから読み込んだ文字列による）したのですが、
いまいち良い信号になりません。（正規分布に従わない）
ラテン文字帯が凄まじい数になり、ラテン文字を含めば全部尤度高い、という結果になってしまいます。
文字化けしたと思われる値（教師信号分布0の文字帯）の信号値を、より低い値にしたい（コストを大にしたい）のですが、
こういう場合、どういう風に信号を改善していけばいいでしょうか・・。

101 ：

a, b, c, d, e, zの昇順ソートされた整数配列があります。
それぞれ、1000万要素程度あり、mallocで領域を確保してあります。
a〜eの配列のそれぞれの要素から、zに含まれている要素を抜いてから、
全て結合してソートして出力したいです。
どういった方法が一番早いでしょうか？
それぞれの配列で
aとz
bとz
cとzと順番に、それぞれでa[0]とz[0]から逐一比較していって、
一致しない要素をメモリに持っておき、
最後に結合して、ソート
というのを考えましたがこれが最良なのかどうか…朝からずっと悩んでいます。

102 ：

整数かつソートされていると保証されているなら
各配列にポインターをつけて
ポインター群でいちばん小さいものをresult配列に追加してポインターをインクリメント
でいいんじゃね

103 ：

>>101
マージソートの応用でいけそうだ。
a, b, c, d, e の先頭なかから一番小さいものをとりだし result に書き出す。
ただし、それが z の先頭と等しかったら捨てる。
a〜e + z のなかで z が一番小さかったら、z の先頭を捨てる。

104 ：

なるほど

105 ：

ありがとうございます。
コーディングしてみます

106 ：

うーん…それぞれの配列がユニークじゃない時はむりか。。
すみません、全配列で要素が重複してる可能性があり、
同配列で値が重複した要素もそれぞれ一要素として扱いたい
例えば、
a={0,1,3,3,4,5,5,7}
b={3,4,5,5,5,6}
z={1,3,5,5,10}
の場合は
a'= {0,3,4,7}
b'= {4,5,6}
として、
result={0,34,4,5,6,7}
としたい・・・
やっぱ一つ一つ出して、resultに格納、最後にソートかなぁ・・・
103みたいになんとかソートを省けないか、もう少し考えてみます

107 ：

>>106
どうとでもできるとおもうけど
考えてるとおりにaからa'を出力するイテレータ(ジェネレータ)書けばいいんちゃう？
元の配列がソートされてるのにそれを利用しない手はない。

108 ：

>>106
103の「先頭なかから一番小さいものをとりだし result に書き出す。 」時に、
一番小さい数をある分だけ result に追加すれば良いだけだろ。
少しは考えれば分かるだろうけど。

109 ：

はい、今回はメモリもある程度限られた状況で
なんと言っても速度重視なので、
何パターンか考えて模索してみます。

110 ：

http://www.i.u-tokyo.ac.jp/edu/course/cs/pdf/2006computer.pdf
これの専門科目II-1 (4)がわからないんですが
方針だけでもいいので教えていただけないでしょうか？

111 ：

問題 1(100 点).
負の枝長の枝は存在するが，負の経路長のサイクルは持たない強連結な有向グラフ G = (V, E) を
考える．ここで，l(u, v) は枝 (u, v) ∈ E の長さ，d(v, w) は点 v ∈ V から点 w ∈ V への最短路長を
表すものとする．以下の問いに答えよ．
(1) グラフ G において，任意の点 v ∈ V 及び任意の枝 (u, w) ∈ E に対し，
l(u, w) + d(v, u) −　d(v, w) ≥ 0 が成り立つことを証明せよ．
(2) グラフ G において，V のすべての点 v に対して数値 s(v)が与えられているとする．さらに，
すべての枝 (u, v) ∈ E についてその長さを l(u, v) + s(u) − s(v) に変換したグラフ G を考え
る．この時，G 上において任意の 2 点 w, x 間の最短路であるパスは，G においても同じく
w, x 間の最短路であることを証明せよ．
(3) グラフ G において，v ∈ V を始点とする最短路木を求めるアルゴリズムを記述し，その計算
量を述べよ．
(4) グラフ G において，v ∈ V を始点とする最短路木が与えられている時に，別の点 w ∈ V を
始点とする最短路木を求めるアルゴリズムを記述し，その計算量を述べよ．

112 ：

手ダイクストラ法を逐次やって、既存の木と合流したら、最短経路の再計算で手が抜けるのでは？

113 ：

深さ優先探索の空間計算量って
木の最大深さm, 最大分岐数　b として O(bm) ってありますが、
一つのノードで分岐どうし順序がデータ構造のなかに定義されている、または自明であれば
O(m) になりますよね？

114 ：

ビー玉云々が何を言ってるのかよくわかりません。この例えは何か原典があるのでしょうか？
http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95

115 ：

ググり直した出典はありました読んでみます

116 ：

diffの動作原理を知る〜どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社
ttp://gihyo.jp/dev/column/01/prog/2011/diff_sd200906
これ全然理解できない・・・

117 ：

>>116
「編集距離」で検索すれば分かりやすいページがたくさん
10年位前にOCRの認識率を計測するために色々とインプリメントしたな〜

118 ：

単純なアルゴリズム（長さMとNの文字列に対して計算量MNになるアルゴリズム）の
解説をすっとばして、実用的なアルゴリズムの解説になってるなぁ。
理解するためにはまず単純なアルゴリズムの解説を探すといいと思う。

119 ：

>>116
技術評論社のサイト初めて見たけど、中々興味深い記事があるな。

120 ：

【問１】
ある点が三角形abcの中にあるかどうかを判定する簡潔な方法を俺に教えよ

121 ：

ぼくのかんがえたさいきょうの(ry
ある点をdとすると、
abc＝abd+acd+bcd（面積）
どうやって実装するのかはシラネ

122 ：

・重心とその点を結んで各辺と交わるかどうか調べる

123 ：

いや結ぶのは三角形の一点でいっか

124 ：

0 < ↑ab・↑ap かつ 0 > ↑ab・↑bp かつ
0 < ↑bc・↑bp かつ 0 > ↑bc・↑cp かつ
0 < ↑ca・↑cp かつ 0 > ↑ca・↑ap ならば、点pは△abcの中。
なお、計算に無駄がある。

125 ：

ごめん、嘘。でもベクトルの内積の符号を調べる方法で良かったはず。

126 ：

0 > (↑ab・↑ap)(↑ac・↑ap) かつ
0 > (↑bc・↑bp)(↑ba・↑bp) かつ
0 > (↑ca・↑cp)(↑cb・↑cp)

127 ：

class Triangle
{
public Point PointA { get; set; }
public Point PointB { get; set; }
public Point PointC { get; set; }
public bool PointIsInsideOfThis(Point target)
{
return 宿題か(target);
}
}

128 ：

目視で確認が一番簡素

129 ：

>>121
これ？
http://upload.wikimedia.org/wikipedia/ja/math/3/2/f/32f967328ca04765e6804a07e6d1dbc7.png

130 ：

ヘロンの式だな

131 ：

A. ありがとうございました

132 ：

1. VRAMに三角形を描画して中を赤とかで塗る
2. 点に対応するアドレスの値を読み、背景色か赤か判定
BASICならたぶん2行で書ける

133 ：

えらい無駄が多いな

134 ：

□□
□ ・ □
　 □ 　□□
　 □
こういうコーナーができたときに、「・」の場所は塗り潰せないからアウトだな。

135 ：

>>134
詰め碁か？
二眼確保で安泰型にみえてしまうのだが？

136 ：

一発なら>>126
もしくは２点から特定の角度範囲内
何度も判定するなら>>132みたくマップを作ったほうがいいな
>>134
塗りつぶしを自作すれば可能

137 ：

アンチエイリアスつきの塗りつぶし三角形を計算で出そうとすると
http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=ana.html

138 ：

>>137 これすげー。出版しろよ。

139 ：

wikiの内容とは何の関係もないんだな

140 ：

ただのアフィじゃねーか
Rよ

141 ：

このコードじゃ出版できないぜ〜

142 ：

ワイルドだろぉ〜？

143 ：

ダイクストラ法のwikipediaでの説明が日本語と英語のページで全然違うんだけど
なぜ？

144 ：

公用語の違いかな

145 ：

書いた人が違うから

146 ：

不特定多数が編集するから
あまり信用ならない
悪意ある改変とかマイナーな記事なら修正される機会も少ないだろうし

147 ：

>>146
そういう思い込みを吹き込むのは如何なものか。

148 ：

「いくらなんでもwikipを書き換えるなんてことはしないだろう」という思い込み

149 ：

どこか１サイトの情報だけ見ようとするからダメなんだよ
個人サイトでもその人の勘違いや間違いで誤った事が書かれてることもあるし
wikipedia含めいくつかのサイトで情報見比べることが大事

150 ：

>>143
翻訳記事じゃないんだから構成が違っていて当然だが、何か問題でも？

151 ：

Wikipediaとか
2chで信者とアンチが争ってるようなカテゴリーの記事だと改変されまくり
Wikipediaと、Wiki以外のサイトの最低2つは情報見ろよゴミカスRと思う

152 ：

基地外コテｷﾀｰ

153 ：

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1488984684
お願いします

154 ：

英語が読めないアホはどうぞインチキ情報に騙されてくださいねｗ

155 ：

概要の、まずビー玉と紐を用意し・・・
擬似コード
こんな説明でわかるやつ天才や

156 ：

trieすら自力実装できない自分の頭に悪さに絶望してます
死んだ方がいいですか?

157 ：

うん。

158 ：

プログラミングの才能がないと、いくら努力しても土方止まり
他の才能を持っている分野で頑張った方がいいよ
アルゴリズムの説明すると、すぐ理解する後輩がすげーと思ったら、
まわりの大半がそうだった。死にたい。

159 ：

培養菌の数をカウントするのってどうやるんだろう？
画像から直径と中心を判別するには？

160 ：

>>159
羊と狼を数えるアルゴリズム
http://www2c.comm.eng.osaka-u.ac.jp/~alcon2009/overview.php

161 ：

コロニーだから丸？
輪郭抽出→クロージング→オープニング→連続してるのを数える

162 ：

>>159
単純に色の違うピクセル数をカウントして１ピクセルあたりいくらってのをかけてやるんじゃダメ？

163 ：

大きさの異なる円が２つ以上重複していてもカウントできなくちゃダメだろ

164 ：

サメガメの判定で処理負荷が問題になる状況ってどんなだよ。しかも揚げ足取りで揉めてるし。

165 ：

亀

166 ：

ほとんど重複だから
輪郭の一部である弧から直径と中心を拾うアルゴリズムかな・・・
で、どうやるの？

167 ：

OpenCV を使う。
というか画像処理スレの話題。

168 ：

>>137の一部がカラパイアに載ったぜ〜

169 ：

本人いたのかいな

170 ：

円の内部（円周上を含む）に点を指定した数だけ打ちたい
それぞれの点の距離を最大化するように打つにはどうすればいい？

171 ：

最適化問題むずかしす

172 ：

n=1 どこでも
n=2 2点を繋ぐ線分が円の中心を通るような円周上の2点
n=3〜6 円に内接する正n角形の頂点
n=7 円に内接する正6角形の頂点と円の中心
n>=8 これの求め方を教えてってこと

173 ：

予想としては
同心円の円周上に点を取っていくことになる

174 ：

なかなか面白い問題

175 ：

正三角形による円充填になりそう。

176 ：

１．円内にランダムに点をばらまく。
２．全ての点についてそれぞれ最近傍の点を見つける
３．その点から離れる方向に移動。移動量はXXX。
４．３の移動量の総和が閾値以下になるまで２へ戻って繰り返す。
みたいなのを考えたんだけど移動量はどうすればいいか

177 ：

充填問題の一種だろうな。
http://ja.wikipedia.org/wiki/%E7%90%83%E5%85%85%E5%A1%AB#.E5.86.86.E5.85.85.E5.A1.AB
に
1940年、マジャル人数学者 László Fejes Tóth は、六方格子が正規も非正規も含めたあらゆる円充填の中で最も高密度であることを証明した。
とあるが参考になるだろうか。

178 ：

>>176
1番目と2番目に近い点と自身で正三角形を作るように移動してはどうか
移動量と移動方向が決まる

179 ：

>>176
振動しまくって終わる予感。

180 ：

http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html

181 ：

球ならどうなんの？
４次元以上なら？

182 ：

>>176
単純に (距離)^-2 の斥力がはたらくようにしてみた
http://www.dotup.org/uploda/www.dotup.org3139871.png
円周部の密度が高くなってしまう

183 ：

>>182
それって再近傍の点からの斥力？
全ての点から r^-2 の斥力を受けたらどうなるかね。

184 ：

>>183
すR
全ての点からの斥力にしてる

185 ：

毎ターン、各点の再近傍の点からの距離の平均を求め、その平均値との差の二乗に比例して引力／斥力を受けたらどうなるだろうか。

186 ：

>>182
円周部から中心方向に移動する力が働かないからかな

187 ：

点Aの座標 P(A)
点Aと点Bの2点間距離 D(A,B) = D(B,A)
点の集合 Z = {A,B,C, ....}
D(a,b) ≧ D(c,d) ∧ P(x)≠P(y) [x≠y; ∀x,y∈{a,b,c,d}; ∀a,b,c,d∈Z;]
を満たすZを求める

188 ：

>>182
円周部を端点じゃなくて無限にしてみたらどうだろう

189 ：

>>187
定式化がめちゃくちゃじゃないの？
例えば4点でそれを満たすユークリッド平面上の点の例があるの？

190 ：

>>188
無限に飛んでいくだけだな

191 ：

逆に考えるんだ。
http://mathnokai.seesaa.net/image/hex_circle.gif
こういう正三角形のメッシュを考えて、
ちょうど求める数の頂点が円内部に入るように、円の半径と中心を動かすんだ。

192 ：

>>191
点の数が多いときは圧倒的によさそう

193 ：

常に格子点に来るわけじゃないと思うけど

194 ：

何が？

195 ：

最適解が

196 ：

>>191
ちょうど数をとっても隙間ができる
その分まだ距離は広がれる

197 ：

いや、無理だろ

198 ：

>>191の場合、４，５，６のケースで>>172と違いがでてくる
8以上でも不都合があるかもしれん

199 ：

>>176で粒子法もどきでFA

200 ：

外縁部は円周上にへばりつかせて残りを内部にばらけさせるほうがいい

201 ：

>>190
いや
無限遠という意味ではなく
無限循環？的な意味だった
「無限だけど閉じた宇宙」
みたいな
専門用語知らんのですまそ

202 ：

>>196
無理。外周で幾つか点を動かせるかも知れんが、内部は動かせない。

203 ：

>>191
8個の場合円はどこにどの大きさで取るの？

204 ：

円に内接する、正六角形に正三角形を一つたした、↓の図形の頂点が解になるだろうな。
　＿＿＿
／　＼／
＼＿／
これより頂点間距離が大きいのがあったら提示してくれ。

205 ：

隙間だらけじゃん
http://www.dotup.org/uploda/www.dotup.org3142869.png
例えばこれらの点をこう動かせばどの点との距離をとっても広がるか変わらないかだね
狭まる箇所は無いね

206 ：

存在しないファイル。

207 ：

すまんうｐし直した
http://www.dotup.org/uploda/www.dotup.org3142891.png

208 ：

>>207
一番下の二つの頂点も動かさないと、距離変わらないぞ。
そして全部動かした後で、距離が広がってるかも確認してくれ。

209 ：

>>204
その図形を円に内接させた状態で、外周に近い一部の頂点は更に円周方向に移動できそうだよ。
要は>196か。
でもまぁ、>176で闇雲に求めるよりも>176の1で与えるべき初期値としてはいいのか。

210 ：

最小距離を最大化すればいいという考え方と
全ての点の組み合わせの距離の総和を最大化するという考え方の違いか

211 ：

帰ったら俺も作ってみるか

212 ：

>>208
下二つも広げられるよ

213 ：

>>204
正七角形の頂点＋中心点

214 ：

>>170これは何に使うアルゴリズムなのかな

215 ：

サンプリングとか？

216 ：

どんなＮ角形も三角形に分割できるわけで２点の距離を同じにするなら近隣の３点を結ぶと正三角形になるような形が理想的だが
どんな２点でも等距離である必要はなく、すべての点の中で２点間距離が最小となる距離を円の範囲内で最大化するって問題だから
単純に正三角形の敷き詰めからの切り抜きでは実現できないってことか
ある正円Rがあり
Rの内側と円周上に合わせてＮ個の点が存在し
Ｎ個の点のうち任意の２点間の距離Ｄp [p=1,2,...,N*(N-1)/2]と定義したとき
Min(Dp)を最大にするＮ個の点の位置を求める

217 ：

？

218 ：

>>215
ずばり正解

219 ：

このスレにいる連中のレベルを調査か

220 ：

そして有望そうな奴はバシバシスカウト

221 ：

サンプリングなら >>191 でも正方格子でもいいんじゃないかと思った

222 ：

有望そうなのって居る？

223 ：

正三角形とか正方形メッシュで
中心と半径を探すアルゴリズムってどうやるの？

224 ：

点の重心求めて最遠点までを半径にすりゃいいんじゃね？

225 ：

最近距離の２点を見つける
その２点だけ自身を除くすべての点からの斥力方向へ移動（移動量は２番目に距離の短いものより１以上長くなるよう）
点が円の外側へ移動しようとするとき、円自体を移動させすべての点が円内に収まるようにする
でやってみたがダメだった

226 ：

>>223
もしかして >>159 なのか
つくづく問題を説明する気のない人だｗｗｗ
シャーレ上の培養菌のコロニーの数と半径を求めよ
サンプル画像
http://www.dotup.org/uploda/www.dotup.org3146244.png
黒線がシャーレ
ピンクの部分が培養菌のコロニーである
コロニー同士は重なる場合もある
って感じじゃないの？

227 ：

>>224
点の重心って？

228 ：

>>226
いや全く別人
流れ見てて気になっただけ

229 ：

別人だったか

230 ：

すみません、質問です：
voronoi分割のクラスライブラリは、どこかにありますでしょうか？
色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz

231 ：

スレ違い

232 ：

エエｴｴェェェｪ(略
しかし別スレに移動したら、マルチあっちいけと叩かれるだけ。
このスレでお願いしますOTL

233 ：

片山議員は参加者に囲まれながら、「民主党政権になってから、生活保護の不公平が見逃すことができないところに来ている。
外国人の不正受給に関しても、まずは日本人の、真面目に義務を果たしている人が優先。
今は特に、韓国なんてすごく豊かなんですから」と持論を展開し、
「私に対してもいろいろ嫌がらせがあったが、どこから来ているかはわかるんですよね。私たちの日本を愛するマグマの方が強いことを教えよう。
日本が正直者が報われる、本当に強い国にもう1度なれるように、私たちががんばりましょう」
と呼びかけると、参加者からは大きな拍手が起こった。
http://www.j-cast.com/2012/07/01137691.html?p=all
http://www.j-cast.com/images/2012/news137691_pho01.jpg
http://www.j-cast.com/images/2012/news137691_pho02.jpg
前
http://engawa.2ch.net/test/read.cgi/poverty/1341150152/
http://engawa.2ch.net/test/read.cgi/poverty/1341153256/

234 ：

>>230
> 色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz
なぜBoost.Polygon.Voronoiではダメなのか
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm を見てもわからない。
せめてBoost.Polygon.Voronoiが動作しない環境を挙げるべきでは。

235 ：

>>232
マルチした以上しかたない
２ｃｈで質問したいなら半年ＲＯＭれ

236 ：

>170
・中心(0,0)、半径1の単位円として一般性を失わない
・1点を (-1, 0)と決め打ちしても一般性を失わない
この条件下で、最近傍の点との距離を dist とした場合に n 点詰め込む処理を用意して、
dist に対して二分探索を行った。
詰め込む処理はある点を追加した時に、
1) その点を中心とした半径 dist の円と単位円の交点
2) その点を中心とした半径 dist の円と、今まで追加してきた各点を中心とする半径 dist の各円との交点
を次の候補として探索した。
n = 20 辺りから急激に遅くなる。
似た問題で http://en.wikipedia.org/wiki/Circle_packing_in_a_circle があってその結果と比べると大体合ってそうな感じ。
http://ideone.com/fOz4R

237 ：

勢い込んで書いてからあれだけど
>210
>最小距離を最大化すればいいという考え方と
>全ての点の組み合わせの距離の総和を最大化するという考え方の違いか
で、最小距離を最大化した場合(あるいは >216 の定式化の場合)で、総和が最大になるかは分かんないね。

238 ：

>>234
HEW。
テンプレート構文を対応していないので、STLも使えません。
>>235
マルチしていません。

239 ：

スレ違いつってんだろが
失せろゴミ

240 ：

Voronoiのデータ構造とアルゴリズムについてでそ。
脳に障害があるの？239はｗｗｗ

241 ：

↑池沼

242 ：

回答が返って来ない所でうだうだとするより、他所に行った方が良くないか？

243 ：

↑オマのうだうだジャマ。てか、それがオマエの存在そのものｗｗｗｗｗ

244 ：

クラスライブラリの場所を尋ねるスレだったのかここ

245 ：

>>238
スレ立てるまでもない質問はここで 120匹目
http://toro.2ch.net/test/read.cgi/tech/1341099441/

246 ：

と言うよりこのスレで質問することが妥当であることを示す一言でもあればよかったのにね
『特殊なアルゴリズムのためこのスレの方が一番詳しいんじゃないかとここで質問いたしました』とかさ

247 ：

意外や意外に妥当なvoronoiクラスライブラリが無かったので来ました。
・アルゴリズム事典に無かった
・Javaアプレットは小型のものがあったがC++やC言語が無い
・既存の演算やBoostで出来ちゃうから無い？
ネットにソースが散在してると思っていたんですが。。。

248 ：

>>247
アプレットがあるならそれをベースにすればいいだろ。
物乞いしたいのなら、スレ違いだってばさ。

249 ：

いろんな環境で動作させたいんなら環境依存の少ないJavaのそのライブラリ使えばええやん

250 ：

Javaの奴ってこれだろ？
Lee Byron ≫ Else ≫ Mesh ? A Processing Library
http://www.leebyron.com/else/mesh/

251 ：

Voronoi diagram - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Voronoi_diagram
外部リンクでも辿って探せや

252 ：

本当に物乞いするだけなら、スレじゃなくてググルするだけだし。
どちらかというと、検索結果があれ？となって、他の人がどういう対応なのか知りたかったのです。
>>248
それは不可能じゃないですが、だから、C++な人の通常の方針が知りたくて。
自分が見つけたリンクは、
Javaは　ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/normal/index.html
その他は　ttp://gihyo.jp/dev/serial/01/geometry/0012
といった感じです。
が、上のレスに貼られたリンクに入ってみます。

253 ：

voronoiで、先ず、ある点の一番近くの点と結ぶのは、全部やる方法もありますし、工夫する方法も分かります。
その次の、あるドロネー辺の２等分垂直線同士の交点座標を取得方法も分かります。

が、しかしドロネー辺が無数にあると、計算時にどれ活かすか難しくないですか？？？

254 ：

それと、ある点に対して出来上がるvoronoiが何角形かも不明だし、
関係している線分と関係してない線分とか、線分で領域が閉じてるか、
とか、簡単に分かるのかなぁ？
実際の図を描けば分かっても、プログラムだと１次元的に見えますよねぇ。

255 ：

連投すみません（連投の最後）：
ある点の一番近くの点と結ぶのは全部やる方法、じゃダメですよね。
余分に結ぶと余分に線分が出来て、余分に多角形化しちゃうし。
どうもvoronoiの認識が足りないので、そちらを勉強してみます。
もしくは、高度なポリゴンクラスライブラリを持っていれば簡単に解決なのか？＿？
チラ裏となってきたので、一旦消滅します。レスはずーっと読み続けますが。

256 ：

まとめると、「自分で実装する気はないからライブラリ教えろや！」

257 ：

ライブラリが存在しないケース
・アルゴリズムの再現自体が不可能
・複雑なプログラムになり相応のコストがかかるため、無料提供が無いが有償提供ならある
・アルゴリズム自体の知名度や有用度が低いため手を付ける者が少なくライブラリ化してない
・あまりにも簡単で単純なアルゴリズムのため、わざわざライブラリにして提供するまでもない

258 ：

？

259 ：

どうも、いきなりボロノイを実装するのではなく、
＞ボロノイ〜逐次添加法
＞ボロノイ〜再帰二分法
といった手法が定石みたいでつね。
それらでググったら、多少ひっかかってきますたｗ
ttp://suuri.ics.kagoshima-u.ac.jp/lectures/easywin/docs/voronoi/Voronoi.h
ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/index.html
ttp://i-health.u-aizu.ac.jp/CompuGeo/2011/exercises.html
理解して修正できるコンパクトなものにしたいでつ。

260 ：

さっきから日本語サイトばかり

261 ：

英語サイトもみっけ：
ttp://www.koders.com/c/fid17552685298283A6BFE8B1CBCC2D3E9A35C58C16.aspx
ttp://www.leebyron.com/else/mesh/
ttp://www.codeforge.com/s/0/alghorothm-for-voronoi
ttp://www.geocities.co.jp/SiliconValley-PaloAlto/4089/voronoi.html

262 ：

おまえなんでここにメモってんの？ここにメモる必要ないだろ

263 ：

おまえなんでここ監視して余計なこと言ってんの？ここで発言する必要ないだろ

264 ：

>>261>>263
失せろゴミ

265 ：

（笑）

266 ：

空間ってか直方体を8つごとに分けていって
8分木の形にしたデータ構造の,一部の葉だけが選択されていて,それらの葉の接続関係
を求めるってどうすればできますか？
葉に対応する直方体の面同士が接していれば接続しているとしたいのですが
階層がちがうのの扱いがよくわかりません。。。

267 ：

？

268 ：

点の絶対座標から、その点を含むノードのアドレスを出せるよう、ノードのアドレスを工夫する。
（ここで言うアドレスとは、root->node[0]->node[1]->node[4] における (0,1,4) のようなもの）
で、選択されたノードの中心座標 (x,y,z) から (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz) （復号任意）を含むノードのアドレスを得る。

269 ：

>>268
どうもです^o^

270 ：

ミスった。
> (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz)
ここ普通に (x±dx, y, z) (x, y±dy, z) (x, y, z±dz) だ。
dx, dy, dz はまあ、直方体のサイズとかでも。

271 ：

>>255
http://www.pi6.fernuni-hagen.de/publ/tr198.pdf

272 ：

質問させてください
C++スレから誘導してもらいました
スレチでしたら誘導頂けると幸いです。
O表記法についてなのですが、イマイチ理解できていません。
授業にて以下7つのルールを定義されたのですが
各々について具体的な数字の入った例をいただけませんでしょうか
#数学の勉強が足りないのかもしれませんが、具体的な数字があれば理解できると認識しています。
#宿題ではないのですが、以降のテストで以下ルールを適用しながらアルゴリズムの証明を行う問題が出題される予定です。
1). if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n))
2). if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)) then f(n) + g(n) ∈ O(h(n))
3). an^k ∈ O(n^k)
4). n^k ∈ O(n^k+j) for any j
5). if f(n) = cg(n) then f(n) ∈ O(g(n))
6). loga n ∈ O(logb n) O(logn)
7). loge n ∈ O(loge n)
お手数ですがよろしくお願いします。

273 ：

いやです

274 ：

>>272
ggrks

275 ：

雑多な質問スレっていろいろあるのに
何故このスレに誘導されたのだろうか

276 ：

>>272
ランダウの記号 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

277 ：

>>272
オーダー記号って普通は等号使ってn=O(n)とか書くんじゃないかな
それはともかく数字があれば理解できるって神だな。
関数の極限の話だし。

278 ：

ヒープソートでなぜ再帰？〜日本語版ウィキペディアの問題点と最強最速のヒープソート〜
http://www.dreamhope.net/soliloquies/HeapSort/

279 ：

>>278
この人頭悪いね
>同じコンピュータ環境で、Linux GCC環境では2,500,000件程度のデータを取り扱いできるのに対し、
>Windows BCC環境ではその10分の１の258,000件程度が最大です。
>LinuxがWindowsよりも10倍性能が良いのか、GCCがBCCより10倍性能が良いのかはわかりませんが、
>この性能差には驚きました。
そりゃ
int dat[DC+1]; //データ格納用配列
のようにスタックに巨大な配列を取ればそのうちスタックオーバーフローするって
更にスタックオーバーフローは都合の悪い事にエラーが出ずに結果だけおかしくなる事が多い
ちゃんとソートされているのか結果を見たのかな(ヒープ4だけは見ているようだけど)
Linuxはスタックが足りなくなると自動的に拡大してくれるので問題が出ない
ヒープに取れば同じ事
速度が4倍〜13倍も違うのはよく分からない
ちなみにEclipse CDT + gcc4.6.1でやってみたがbccやvcと速度的には大差なかった
スケジューリングの問題かな？

280 ：

スタックオーバーフローは最近はSEGVで落ちるんじゃね？
ウィキペディアの記事も微妙だが、そのウェブページもいろいろと頭悪いという
ことについては同意。

281 ：

>>280
Linuxは拡張しきれないスタックを要求した時はSEGVで落ちるけど
Windowsは黙って変な結果を出して終了するか、暴走するかどちらか

282 ：

ランダウの記号って名前があったのか
知らなかった

283 ：

Mac も
> 黙って変な結果を出して終了するか、暴走するか

284 ：

VCのデバッグならスタックオーバーフローを検出して止まるので
リンカのオプションからスタックサイズを改めて指定しなおす事になる
この時に一度ビルドをクリーンしないと単にリンクし直すだけでは
スタックオーバーフローエラーは止まらないようだ

285 ：

＞そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。
・・・ナゼ

286 ：

自己顕示欲の強そうな人だね
他の記事も読んだけど首を傾げすぎて首が疲れた
データベースは毎回自分で実装した方がいいらしいよ 目から鱗だわ

287 ：

最適化を語るのにオプションを明示しないとか、
データ量を語るのにオプションを明示しないとか、
処理速度を語るのに環境を明示しないとか、
10〜20年くらい前から知識が更新されていないんじゃないだろうか。

288 ：

>>285
批評に晒されたくないチキンハートなんでしょ。

289 ：

出回ってる書籍が古いものばかりだからね
図書館で借りようものなら１０年〜２０年昔の本だって当たり前のように陳列されてる

290 ：

�@区間スケジューリング問題＜＝ｐ　点カバー問題
�A独立集合問題＜＝ｐ　区間スケジューリング問題
この２つについて
(i)Yes　(ii)No　(iii)「これが解ければP=NP問題が解決できるので不明」
のいずれかで答え、その簡単な説明も与えよ。
という問題の答えを教えて下さい

291 ：

C/C++の宿題片付けます 158代目
http://toro.2ch.net/test/read.cgi/tech/1339338438/

292 ：

すっげえ宿題でるんだな
俺が通ってた大学での「データ構造とアルゴリズム」ってまんまの名前の授業あったけど
宿題に出たのがせいぜい一般的なソートアルゴリズムいくつかををjavascriptで書けとかそういうレベルだったよ

293 ：

なんでjavascriptなの？なんかその大学に興味があるんだけど
今時は大学でjavascriptでアルゴリズム書かせるのか

294 ：

schemeの代替

295 ：

web限定用語で教育するってのはちょっとナンセンスかと

296 ：

「web限定用語」ってすごい表現だなw
プログラミング言語を「用語」って言うのはどこのマヌケ業界だろう？

297 ：

web限定言語で教育するって凄い大学だな

298 ：

逆にCとかJavaみたいな一般のプログラマにとって中途半端に使えない、
実用的でない言語なんて教えたところで意味無いでしょ。

299 ：

じゃあpythonでいいだろ
少なくともアルゴリズムの授業でjavascriptってのは学生がかわいそうだ

300 ：

>>298
いや相手は情報系の学生だぞ？
CもJavaもダメな奴がどうやって情報科学を学ぶわけ

301 ：

>>298
世界が狭すぎ
あなたがどういうバックボーンなのか知りたいわ

302 ：

情報系っていうのはプログラマ養成施設じゃないよ。
専門学校か他の工学系と勘違いしてないか？

303 ：

情報系でCもJavaも教えない大学があるのか？
それまともな大学じゃないだろ
そんなカリキュラムが存在するならマジで教えて欲しい 聞いたこと無いから
プログラマ養成機関じゃないからこそCで本質に切り込むんじゃないの
専門学校みたいなプログラマ養成機関こそがPHPとかJavascriptを教えるんでしょ
まあそれはさておき、アルゴリズムの概念を教えるのにJavascriptを使う大学はおかしいよ絶対に
それも否定する？

304 ：

まともな大学生ならCは自習で既に学んでるから大学ではいちいち教えない

305 ：

アルゴリズムの本質は言語によって変わらない

306 ：

「アルゴリズムの本質は言語によって変わらない」
それはわかるけどさ、だからといって
「アルゴリズムの本質は言語によって変わらないからJavascriptで教えます」
はおかしいでしょう　普通の感覚じゃ考えられない
言語実装に関係のない本質を教えるんであれば、なおのこともっと汎用的な普遍的な言語でやるべきじゃない

307 ：

そうかい

308 ：

その感覚はわからなくもないが感覚じゃなく理屈で説明してくれ。

309 ：

アルゴリズムの授業だからJavascriptなんじゃなくて
別の理由で決まったんだろ

310 ：

10年前とは違うからな。javascriptを取り巻く環境は随分改善した。
ブラウザ間の互換性であるとかデバッグ環境はすでに十分な領域に達している。

311 ：

>>305
8-QueenをCOBOLで書くようにという宿題がでるらしいと聞いたら
その授業は取らない。

312 ：

そうかい

313 ：

8-Queenとアルゴリズム全般、COBOLとJavascriptじゃ違いすぎるな

314 ：

いい加減スレ違い

315 ：

そうかい

316 ：

JavaScriptをウェブ専用とか思ってるバカがプログラマのわけないだろw

317 ：

そうかい

318 ：

ECMAScript は Web 専用じゃないけど Javascript は Web 専用とか、そういう揚げ足取りなのかもね。

319 ：

言語は手段でしかない

320 ：

javascriptはクロージャを学ぶのに悪くない

321 ：

>>319
このスレの住人が口にすると迫力あるな。

322 ：

そうかい

323 ：

VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。

324 ：

誰のＰＣにでも入ってて使えるプログラム言語だからという理由でjavascriptを指定してたよ
別にHTMLファイルにするとかじゃなくて
アルゴリズムを再現したコードをメールに添付して送信するみたいな宿題だった
ちなみに情報が専門の学科は無い大学だったのでそういうことに

325 ：

ちなみな自分語りになるが
学科名的には電子情報工学科となってて情報系の授業を期待して入学したものの
（ちゃんと調べずに願書出した俺が悪いのだが）
情報とは名ばかりで情報系の授業はほとんど開講されず
電子系、特に半導体系の授業ばかりしかなかった
その大学わが母校はもう存在してないけどね

326 ：

本当ただの自分語りだな

327 ：

寂しい奴なんだろう。

328 ：

>その大学わが母校はもう存在してないけどね
津波で流されたのね

329 ：

つまり本格的な情報科学系の授業では無かったという事の証左だよな
まあ非情報系の学生だったらブラウザで誰でも実行環境が整うからあえてJavascriptでやるっていう意味もわかる気がする

330 ：

VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。

331 ：

なんでこんな頭の悪いのがこのスレにいるんだ？

332 ：

若者の 2ch 離れが進んでいるな

333 ：

2点が与えられたときその2点を結ぶ単純な経路（同じ頂点を通らない経路）
が2つ以上存在するかを判定するアルゴリズムと計算量を述べよ。
深さ優先探索とかでしょうか？

334 ：

宿題は宿題スレへ

335 ：

失礼しました

336 ：

>>331
どっちのこと？

337 ：

おそらく自問自答だろう

338 ：

二分探索木の平均高さが　O(logN) の証明ってどういう風にやるんでしょうか？
アルゴリズムイントロダクションに書いてあるらしいのですが見当たりません。どのあたりでしょうか？

339 ：

>>338
2分探索の構造がわかれば少し考えればわかることだよ

340 ：

>>338
木 T が平衡なら、そのまま height(N) = 1 + height(N/2) で O(logN)でしょ。分割統治法

341 ：

手元の本にありましたのでもういいです。
お騒がせしました

342 ：

宿題は宿題スレへ

343 ：

3つのくっついてる円にこれまたくっついて囲まれてる円の半径を
求めるアルゴリズムってどうすればいい？

344 ：

３つの円はどういうくっつき方？
３つの円の半径はばらばら？
○○○
　 ○
　○○

345 ：

宿題は宿題スレへ
http://blogs.yahoo.co.jp/oka_yadokary/29892416.html

346 ：

343は外接・内接という言葉も知らなそうな雰囲気で困る。

347 ：

>>344
くっつき方は下の方
円の半径はバラバラ

348 ：

２本（３本）の双曲線の交点が共通接円の中心か

349 ：

互いに接する３つの円　に外接する円の半径の求め方？

350 ：

３つの円すべてと接する外接円は無理じゃね

351 ：

デカルトの円定理
http://aozoragakuen.sakura.ne.jp/taiwa/taiwaNch03/enteiri/node2.html

352 ：

にしてもスレチ。

353 ：

アルゴリズムでも何でもないなコレ

354 ：

プリムのアルゴリズムのヒープ版って
(E+V) log (E) ≒ Elog(E)ってあるけど　(E+E) log (E) ≒Elog(E) が正しいと思う
挿入か削除のどっちも Elog(E) でしょ　最悪全枝を一回ずつ挿入と削除する必要があるんだから

355 ：

王様は王様でも頭が三つある王様はな〜んだ

356 ：

三頭王

357 ：

キングギドラ

358 ：

大学の課題で二分探索木の高さを調べる実験とその結果を調べる実験が出たのですが
どうしたらいいですか

359 ：

そのようにプログラムを作って結果を表示すればいいのでは？

360 ：

宿題は宿題スレへ

361 ：

ほんとこういう質問するガキがムカつく
どうすればいいですか？って何だよ
そんな曖昧な質問で答えられると思ってんのかカスが
どこの底辺大学だか知らないが学費が無駄

362 ：

>>358
擬似乱数から最大の低周波成分を除くアルゴリズムを考案する。最大の低周波成分を除く操作を
繰り返すごとに２分探索木の高さが次第に平坦化することを実験・観察する。

363 ：

教授に不正してる奴がいたと報告しとく

364 ：

乱数が独立なら、Huffman木を作るといいよ！

365 ：

ハッシュのチェイン法の同一エントリのチェインの長さに制限があるやつはなんていうんだっけ？

366 ：

特にない

367 ：

半開きハッシュと名付けた

368 ：

こないだから宿題貼り付ける奴がちらほらいるが
そのどれも分からなかった俺は才能が無さ過ぎた

369 ：

>>361
黙れバカw
空気読んで答えやがれ

370 ：

↑お前が馬鹿

371 ：

馬鹿には無理

372 ：

>>370
>>371
バカはお前ら
お前らのパッパラパーなアルゴリズムでさっさと俺様を笑わせやがれ

373 ：

馬鹿には無理

374 ：

>>373
お前には無理と言うことかw

375 ：

>>374
お前が馬鹿

376 ：

　　　　　＿＿＿＿
　　　 ／∵∴∵∴＼
　　 /∵∴∵∴∵∴＼
　　/∵∴∴,（・）（・）∴|
　　|∵∵／　　 ○　＼|
　　|∵ /　　三　|　三　|　　／￣￣￣￣￣
　　|∵ |　　　＿_|＿_ 　|　＜　うるせー馬鹿！
　　 ＼|　　　＼＿/　／　　＼＿＿＿＿＿
　 　 　 ＼＿＿＿_／

377 ：

どーでもいい。

378 ：

入力された内容は次のとおりです。
■件名： 日本のロボットトレーディングサイト「カブロボ」について
■ご意見・ご感想：
ロボットトレーディング、あるいはアルゴリズム取引トレーダーについて、少しは知識を得ました。その現状について知ったところ、やはり憂慮すべき事態だったため、意見申し上げます。
「カブロボ」というサイトを知りました。そのサイトについての意見です。政府として、このようなサイトを支援していただきたく思います。
アルゴリズム取引トレーダーとしては、株だけでなく、債券、為替取引にも当然対応するべきであります。
また、株、債券、為替取引は、現実に存在する二百か国以上の国や地域を網羅する必要があります。
それが賢いアルゴリズム取引トレーダーのするべきプログラムであり、
たった三百銘柄の仮想取引では、日本の投資家を育てるのに不適切だと思われます。海外銘柄を扱わないアルゴリズム取引トレーダーに魅力を感じません。
扱う銘柄を、全世界の株、債券、為替をすべて網羅する上級者向けのカブロボを立ち上げることを希望いたします。

379 ：

>>375
バカw

380 ：

>>324
その学科何年か前は違う名前じゃなかった？

381 ：

>>378
当事者が遊びで作ってるものに政府が金なんか出す訳ないだろ

382 ：

ぷよぷよのAIを作っているんですが窒息死します
どうすればいいですか

383 ：

ぷよぷよで強いAIってどうすんの？
http://toro.2ch.net/test/read.cgi/tech/1336825232/

384 ：

>>383
こんなスレあったんですか
ありです

385 ：

ﾌﾟｯ

386 ：

ﾖｯ

387 ：

ﾌﾟｯ

388 ：

ﾖｯ

389 ：

O(N)

390 ：

ｵﾅﾗﾌﾟｰ

391 ：

ガベージ・イン／ガベージ・アウト：
善き人々が悪しきプログラムに手を染める時
http://practical-scheme.net/trans/gigo-1997-03-j.html

392 ：

ハッシュだけどチェイン法＞開番地法なんだよね？でなければ溢れを気にする必要はないからね
ハッシュのチェインの長さに制限があるやつの削除、参照の計算量の解析ってどっかにない？

393 ：

「チェイン法＞開番地法」
この意味は何？

394 ：

参照、追加、削除の計算量です

395 ：

A>B　はAのほうが良い、ってことで

396 ：

>>392
> 長さに制限があるやつ
って何よ。
ハッシュ値が衝突した要素を格納するためのコンテナの計算量でいいんじゃないの？

397 ：

ハッシュ法って、均したらまともな実装ならO(1)にならにゃいかんのでは？

398 ：

アルゴリズム考えてもらえませんか。
恥ずかしながら、一応自分の考えたのも載せます。
ただ、絶対もっとスマートな解法があると思うのでよろしくお願いします。
ちなみに言語は PHP です（＞＜）
【問題】
整数が二つ入った配列がいくつかあります。(配列の配列)
これは何らかの数列の範囲を表しています。
最初の数字が範囲の開始位置、二つ目の数字が範囲の長さ。
例えばこんな具合です。
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);
------------- 長いので続きます --------------

399 ：

---続き---
抽象的に書くとこうなりますか。
$data = array(
array( a1, b1 ),
array( a2, b2 ),
--- 中略 ---
array( an, bn ),
);
a1からanは昇順にソート済みです。
同じ値の場合もあります。
b1からbnは1以上で不定です。
$data は、ある数列の 0番目から3スパン、2番目から1スパン、4番目から2スパン...という意味です。
ただし、この $data は範囲の重複の可能性があります。
実現したいアルゴリズムは、この $data が示す範囲を重複のない形で再定義することです。

400 ：

---続き---
例えばそれを実装した関数を linearize とした場合、
$newData = linearize( $data );
の結果は、
array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);
でなくてはなりません。

401 ：

------続き------
こちらが自分が考えた関数です
function linearizedRange( $data ) {
$strage = array();
foreach( $data as $datum ) {
if( isset( $strage[$datum[0]] ) && $strage[$datum[0]] >= $datum[1] ) {
continue;
}
$strage[$datum[0]] = $datum[1];
}
foreach( $strage as $i => $v ) {
$strage[$i] = $v + $i;
}
$len = count( $strage );
if( $len > 1 ) {
$last = null;
foreach( $strage as $i => $v ) {
if( null === $last ) {
$last = $i;
continue;
}

402 ：

------続き------
すいません、予定より1レス多くなりました。
関数の続きです。これで最後です。
if( $strage[$last] >= $i ) {
if( $strage[$last] < $v ) {
$strage[$last] = $v;
}
unset( $strage[$i] );
} else {
$last = $i;
}
}
}
$data = array();
foreach( $strage as $i => $v ) {
$data[] = array( $i, $v - $i );
}
return $data;
}

403 ：

$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);
↓
array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);

404 ：

理屈がよくわからん

405 ：

できた！

function linearizedRange( $data ) {
$n = -1;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
$result[] = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
return $result;
}

406 ：

でたらめを教える悪い例

407 ：

DPでいけそう
Viterbトレリスを作って一発

408 ：

ならばこうか！
function linearizedRange( $data ) {
$n = -1;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
if ($t !== null) {
$t[1] = $dataum[0] - $t[0];
$result[] = $t;
}
$t = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
$p = array_pop($data);
$t[1] = $p[0] + $p[1] - $t[0];
$result[] = $t;
return $result;
}

409 ：

動かないコードなど無意味

410 ：

うおりゃ！スペルミス直したぞ！

function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0]+$datum[1]>$m) {
$m = $datum[0] +$datum[1];
}
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}

411 ：

動かないぞ

412 ：

括弧が一つ多かった！直したぞ！

function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0] + $datum[1] > $m) {
$m = $datum[0] +$datum[1];
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}

413 ：

>>412 さん、さっそくありがとうございますｍ（＿＿）ｍ
凄く短いコードなので感動しました(^-^)
が、どこか不具合がある模様です(-_-;)
例題の
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 5 ),
array( 5, 1 ),
array( 10, 2 ),
array( 12, 3 ),
array( 12, 4 )
);
の答えが

414 ：

Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)

415 ：

Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)

416 ：

別のデータを用いて模式図を書くとこうなります
( 0, 3 ) … データ1
( 2, 1 ) … データ2
( 4, 1 ) … データ3
( 5, 1 ) … データ4

01234567....　数列
---------------------
***___________データ1
__*___________データ2
____*_________データ3
_____*________データ4
***_**________求める答え(V)
V1 = (0,3)
V2 = (4,2)
こうしてみるとOR演算ですね

417 ：

#PHPのことはわからんのに、適当に投げてみる
#どうせどっかでエラーが出る
function linearizedRange( $data ) {
$max = $min = $data[0][0];
$result = array();
foreach( $data as $datum ) {#----
if ( $datum[0] > $max ) {#====ギャップ感知
$result[] = array( $min, $max - $min );
$min = $datum[0];
}#====
if ( $datum[0] + $datum[1] > $max ) {#====
$max = $datum[0] + $datum[1];
}#====
}#----foreach
$result[] = array( $min, $max - $min );
return $result;
}

418 ：

>>417
m(__)m
もう、ほんとうに感謝感謝感謝です。
ありがとうございます。
しかもそのまんまコピペでOKでした。
>>417 さん以外の皆様もありがとうございました。
どこか別の場所で恩返しできるといいです。

419 ：

あぁ、そうかぁ、
$result に格納するタイミングは
datum[0] > $max
のときとループを抜けた最後だけでいいわけか・・・
すごくなるほど。

420 ：

あと、元のデータが ( 開始位置, 幅 ) だったので
それをループの中でいったん終了位置を $max として求めているのですね。
ということは、元のデータを ( 開始位置, 終了位置 ) として同じコストで作成できるとするならば、
それを採択した方がより良いアルゴリズムになるのですね。
元データの取得方法を再検討してみます。m(__)m

421 ：

宿題は宿題スレって約束忘れちゃったのかおまえら

422 ：

ヒープソート、書き換わってるなw

423 ：

ホントだ

424 ：

あらゆる状況や環境を無視して質問するんだけど
STXとETXで囲まれたバイト列を取得 というとき、
<STX>unko<STX>chinko<ETX>
というならびになっちゃってるときは chinko オンリーが正解か
unko<STX>chinko が正解か、どっちがセオリーかなぁ

425 ：

最長一致にするか最短一致にするかは
セオリーというより定義の問題だ

426 ：

後者。
/*foo/*bar*/ だってコメントアウトされるのは foo/*bar でしょう。

427 ：

>>426
そっちの方が作るのも楽なんだけどさ
なんでわざわざ囲ってんのか という根源的なとこを思うと
chinkoオンリーが正解な気がするんだよな

428 ：

>>427
プロトコル定義次第。
・<stx>で始まり、<etx>で終わるまで全てがデータ(unko<stx>chinko)
・<stx>で始まり、<etx>以外の制御コードを含まない区間がデータ(chinko)
・<stx>で始まり、<etx>以外の制御コードを無視した区間がデータ(unkochinko)
・<stx>で始まり、<etx>で終わるまでがデータだからネストを認め、内側から有効とする(chinko)(unkoはペンディング)
・<stx>で始まり、<etx>以外の制御コードが出現したらその後のデータは無効(データなし)
ちょっと考えただけでもこれだけバリエーションが作れる。
要は、エラーに対する強度の問題。

429 ：

>>427
<stx>が出現したら出力インデックスを初期化するだけだから、作る手間は殆ど変わらないだろ。

430 ：

>>428
STXとETXに挟まれたもの という定義なんか作った理由って
開始と終了を検知したいということなんだから、
STXまたはETXの見逃しを恐れるべきですね
ということは、STXのあとETXが来ないでSTXきちゃったのは
ETXを読み飛ばしちゃったと思った方がいいんだよな、きっと
つまり、とりあえずchinkoのみを採用すべきとすべきかなぁ

431 ：

>>430
再入可能かどうかが分からないとなんとも言えないだろ

432 ：

そうか。 再入可能かどうかがキモになるのか。

433 ：

AVL木の回転って適当すぎない？
別に回転じゃないじゃん。
ただ引き上げてるだけで、入れ替えたりしてる時点で
回転ではないだろ。

434 ：

Rゴミ共がw

435 ：

>>433
subtreeのrotationじゃなくて、nodeのrotationなんで。
「入れ替え」くらいが適切な訳だったという感じでしょうかぁ↓

436 ：

バカばっかw

437 ：

>>435
いいね！

438 ：

お知恵をお貸しください。
xy平面上にランダムに配置された複数個の点があったとき、
それらを線で結ぶとして、結んだ結果が網の目のように見える
ようなアルゴリズムってありますでしょうか。
完全に見た目だけが目的なので自分でも要件が絞り込めて
いないのですが、網の目のように見えるための要件は
おそらく次のようなものでしょう。
・全ての点が2個以上の他の点と結ばれている
・線同士が交差しない
・近い点同士が結ばれていて、遠い点同士は結ばれない
・線で囲まれた図形は三角形ないし四角形を構成し、五角形以上にはならない
よろしくお願いいたします。

439 ：

ドロネー図でggr

440 ：

>439
ありがとうございます。
ttp://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay_3958.html
↑ここを参考にして実装を進めようと思うのですが、この方法だと、
一度完成したドロネー図から点を削除して線を引きなおすには、
再度（その点を除いた点群を入力として）ゼロから作図しなおす
しか無いのでしょうか？

441 ：

Ｂ木がよく分かりません。誰か簡単に説明してくれませんか？

442 ：

>>441
B木は多分岐の平衡木。
ノードは最大M個のサブノードとM-1個の値を保持する。
ノードの値がM-1個を超えるとノードの分割が行われる。

443 ：

2分平衡木の存在意義がゼロに

444 ：

ゼロどころではない。もはやマイナスだ。

445 ：

>442
ありがとうございます。
プログラム文がきわめて長いので、使いこなせません…。

446 ：

>>445
プログラム使うだけだったら実装の細部まで理解する必要ないっしょ。
Addメソッドを呼んだらが値を追加できてGetメソッドを呼んだら値を
取得できるというようなことさえわかってればじゅうぶんっしょ。

447 ：

>446
そうですかねえ。確かに文が400行以上あるので(コメントも含めて)、理解は無理っぽいですねえ。
二度目ですが、シェルソートが挿入ソートより速くなる理由を誰か教えて頂けませんか？

448 ：

ランダムに並んだデータを挿入していくと
比較回数の期待値が挿入１回に対しソート済みデータの半分になるけど
先頭に近そうなデータから挿入していけば
比較は後ろの方の１，２回だけとなることが期待できるってことでは

449 ：

１，２回だけ→ほとんどが１，２回くらい

450 ：

>>447
語尾が腹立つから教えてあげない

451 ：

>448-449
ありがとうございます。けれどやっぱり納得できないというか…。最終ソートの前で既に結構比較・交換にコストがかかってる気がして。
>450
何でですかあ？そんな事言わないで下さいよお。

452 ：

>>451
あんまりふざけたこといってるとぶちぎれるゾ（ゝω・）vｷｬﾋﾟ

453 ：

>452
怒ったらダメですう。貴方に足りないのはＣａですよお。(特に深い意味はない)

454 ：

つまんね

455 ：

例えば挿入ソートだと比較回数は期待値でだいたいこんな感じだろう
右から+の箇所で比較していって*に収まるイメージ(平均なので真ん中)
-----------------------------------*+++++++++++++++++++++++++++++++++++
でもシェルソートのごとく予め4つのグループに分けると比較回数がガクッと減らせる
-----------------------------------*---+---+---+---+---+---+---+---+---
さらに前段階で13のグループに分ければ比較回数が格段に減る
-----------------------------------*------------+------------+---------
いくら前段階というプロセス数が増えるとはいえ、比較や交換回数が小さいわりに
好位置へデータを移動させておくことができるから、全体としてみれば
効率が良くなるんだろう

456 ：

>455
しかし何故そうなるのかが分かりません。
今ヒープソートを勉強してますが、これはさらに分かりません。

457 ：

>>456
挿入ソートでは要素数が多くなると遠くまでテケテケと要素を1個ずつ移動せにゃならんから
超大変。シェルソートでは要素数が増えても離れた要素を交換することで遠くへ移動するときの
コストが減らせちゃうわけ。ゆえに要素数が増えるほどシェルソートが挿入ソートより
速くなるはずよ。
ヒープソートは2分木作っちゃうやつだろ、わかるだろ。

458 ：

基数ソートって分かりやすいしすばらしいですね。

459 ：

アルゴリズムとデータ構造の質問なんですけど、ここでいいですか？
　 　１．2次元以上で、無限に広がるユークリッド空間があります。
　 　２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
　 　３．ここより先では、砂粒を追加しません。
　 　４．空間上の任意の座標を選びます。
　 　５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色？
安定じゃなくてもokです。
こういう状況で、良い検索アルゴリズムってありませんか？

460 ：

> 安定じゃなくてもok
って、等距離に赤も黒もあった場合は、返す値は赤でも黒でも良いと言いたいのか？

461 ：

1ビットごとに次元を変えていくやり方なら地図サービスとかで使われている

462 ：

>>461
kwsk

463 ：

>>460
あ、その通りです。安定ソートっぽい意味でした。すみません。
等距離に、または同じ座標に、赤と黒があるときは、
答えは赤でも黒でも良い、検索のたびに答えが変わっても良い、
ってことです。
あと、例えば等距離に黒が複数ある場合、答えは「黒」と返すだけでokです。
アルゴリズムがどの座標の「黒」を指したのか、
それはアルゴリズム利用者に知らせる必要はないです。
>>461
1ビットごとに？？
すみません、ちょっと想像がつきません…。
どんな仕組みなんでしょうか？

464 ：

>>463
１ビットずつ混ぜるんだよ。分かれよ。
x座標とy座標をそれぞれ32ビット整数値で表現するとして
x = { x31, x30, ... x1, x0 }
y = { y31, y30, ... y1, y0 }
だとするだろ。x31が上位ビットでx0が下位ビットな。
それを混ぜると、
z = { y31, x31, y30, x30, ..., y1, x1, y0, x0 }
という64ビット整数値になるわけだ。
地図系サービスはだいたいこんなのが多い。

465 ：

>>464
で？　その64ビット整数値をどうする気だよ？

466 ：

砂粒座標データはどう整理された状況で提供されるのかが気になる
あるいは事前にデータを整えていいのか否かも

467 ：

>>465
ソートしておけば、upper_bound lower_boundである程度漠然とした領域が拾えるだろ。
全座標の重さが平等でないと使えないやり方だけどな。
そういう想定を置けないなら諦めてR-Tree書けだな。

468 ：

>>459
最近傍探索
http://ja.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2
2を一度だけ行い4を繰り返すのなら
3で同色の砂に囲まれている砂を取り除く方が効率が良いです。

469 ：

皆様ご回答ありがとうございます。
>>467
x,yそれぞれ2bitで図を書いてみたら、なんとなく解りました。
座標は実数を想定していたのですが（説明不足ですみません）、
固定小数点数に近似すれば使えるんでしょうか。ありがとうございます。
あと、R-Treeはちょっと気になってたので、Wikipediaあたりから読んでみます。
>>468
おっしゃるとおり１〜２は1回だけ実行、4以降は繰り返し実行です。
最近傍探索は今日は寝るので明日読みます、ごめんなさい…。
>>459 をもう1回整理して書きます。
　 　１．2次元以上で、無限に広がるユークリッド空間があります。
　 　２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
　 　　 　砂粒は実数の座標を持ちます。
　 　　 　砂粒に大きさは無く、また同じ座標に複数の砂粒が重なることもあります。
　 　３．ここより先では、砂粒を追加しません。
　 　　　　１〜３は1回しか実行しません。
　 　　 　振りかけた数、各色ごとの数、n回目に振りかけた砂粒の情報（座標や色）はいつでもO(1)で調べることができます。
　 　　 　ここまでは、砂粒のコピーをとってソートしたり、時間の掛かる計算もokです。
　 　　　　１〜３で与えられたり生成した情報は、もし必要無ければこの段階までに破棄できます。
　 　４．空間上の任意の座標を選びます。
　 　５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色か返します。
　 　　　　ただし、等距離または同一座標のときは赤黒どちらを返しても良く、
　 　　　　また、後で同一の検索をしたとき答えが変わっても良いです。
　 　　　　赤黒どちらかを返すだけで、座標を返す必要はありません。
　 　６．４〜５を繰り返します。
なんかめんどくさそうですよね…。自分でも考えてみます。

470 ：

｢Ｃによるアルゴリズムとデータ構造｣(昭晃堂)って本いいですか？大学で教科書として使われてたんですが。

471 ：

その本今も持ってる
どっかにしまってあるわ
もう何年も前だから覚えてない

472 ：

平面上に複数の点があり、各点を中心とした円で塗り潰すとした場合に、
『塗られていない領域を最小』にするために、最適な相互に接する円の半径を
求めるアルゴリズムってありますか？
====以下、挫折した案====
近傍の2点間の中点を、仮りの半径の最小値として求めて順次他の点
との中点を求めいって半径の最小値を更新して、これを初期値とする。
この時点では、最小値を更新したことで、他と接することが無くなった
円が生じるので、この半径を再度増加させれば．．．
とか思ったのですが、局所的な部分しか見えていないし、そもそも
上で求めた最小値よりも、更に小さな半径とした方が適した場合も
ある様にも思います。

473 ：

>>472
こういうこと？
１．それぞれの円の半径はバラバラである
２．円と円が重なってはならない

474 ：

>>472
> 『塗られていない領域を最小』
つまり一辺の長さが l の正三角形の各頂点が与えられた場合、それぞれ半径 (l, 0, 0) の円が欲しいわけだな？

475 ：

凸計画問題として解いてしまうとか

476 ：

>>472
>>473 が条件であるとして
外周部にあたる点の半径を出来る限り大きくするのが有効に思える
他の点との距離の最小値が最大となる点で最大の円を描くようにすればよさげ

477 ：

あれか？水着の女の子の写真をうまい具合に水着部分だけ隠してあたかも裸に見えるっていうアレを作ろうとしてるのか？

478 ：

全然違うだろ・・・

479 ：

『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ - YouTube
http://www.youtube.com/watch?v=Q4gTV4r0zRs&feature=youtu.be
で、肝心のアルゴリズムってなんなのよ

480 ：

点の集合をどこから持ってくるのかな
とおもってたら
>477

481 ：

>>479
お姉さんがやってるのは総当りじゃないかな
こんなん

C言語なら俺に聞け（入門編）Part 107
http://toro.2ch.net/test/read.cgi/tech/1347156509/187
187 名前：186[sage] 投稿日：2012/09/14(金) 22:16:01.89
>>186 に一番簡単な袋小路の判定を追加してさらに倍速
http://codepad.org/k9Dw2VA5

482 ：

>>481
お、そっちのスレで盛り上がってたのか。�dクス

483 ：

>479
その高速アルゴリズムが正しいかどうか
検証するのに6年掛かるんですね判ります

484 ：

9x9までは正しい解が出せたとしても10x10でも果たして正しい解が出せたかどうかは

485 ：

任意の符号なし32bit値 Aに対して
下の関係を成り立たせる 32bit値を求めれるもの？
A = x + BitReverse(x)
BitReverseはビット逆順演算
31b ⇔ 0b
30b ⇔ 1b
　　 ・・・・
1b ⇔ 1b
0b ⇔ 31b

486 ：

よく意味が分からない

487 ：

xを0x00000000〜0xFFFFFFFFまでのAのリストを作ればいいんじゃね

488 ：

具体例で考えればいい
A=1のときのxを求める
A=2のときのxを求める

489 ：

>>486
分かりづらかったかも、すみません。
ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、
ｘの値を求めるには？
ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど）

490 ：

難しそうなアルゴリズムだ

491 ：

連投すみませんです。自分の説明に絶望した・・。
unsigned int A；
unsigned int x； // ？
A = x + reverse_bits(x);
if (A == 0x3476edc0) {
// この条件を満たすｘを求めるには・・？任意のAについてどうやって計算すればいいか・・・
}
// 1101:0010 -> 0100:1011 ビット順序反転する関数
unsigned int reverse_bits(unsigned int v){
　v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
　v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
　v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
　v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
　v = ( v >> 16 ) | ( v << 16);
　return v;
}

492 ：

>>485
無理だな。
A と X は 2^32 通り、X + Rev(X) も 2^32 通り。
ただし、X + Rev(X) はオーバーフローする分、実際の数は少ない。
よって、任意の A に対して X を求めることは無理。

493 ：

訂正。
○ X + Rev(X) は 2^32 通り以下。

494 ：

Javaならオーバーフローしない！

495 ：

下位ビットが立ってたら上位ビットも立つ形になるんだし和で非対称になったとしても最下位ビットが

496 ：

更に訂正。
○ X + Rev(X) は 2^31 通り以下。
X + Rev(X) = Rev(X) + Rev(Rev(X)) だから。

497 ：

>>492
オーバーフロー分は切り捨てて良いのですが・・・無理でしょうか？
A = (unsigned int) ( x + reverse_bits(x) );
１元１次方程式に見えるので解があるような、
いやでも無いような・・・悶々としてます。

498 ：

A = 0xFFFF FFFF みたいな形が一番、式を満たす X の数多いようだな。

499 ：

496の対称性があるから無理じゃね

500 ：

さっさと487のいうように一覧にして全数字を網羅できるかチェックすれば早いのよ！（それじゃアルゴリズムじゃありませんが＞＜）

501 ：

>>497
492,496を読んで、それでも一般には無理だと理解できない脳が怖い。

502 ：

496の言う対称性が分かればできる数字がほぼ半分しかないってことがわかる

503 ：

A=X+Rev(X)なら
Rev(X)=Yとすると
A=Y+Rev(Y)=X+Rev(X)が成り立つ
つまり同じ解を出すXが２通りあるってこと

504 ：

>>503
うーん　そうですね。
ｘとAが１対多の関係がある時点でダメなのか・・・
皆さんありがとうです

505 ：

>>503
それは間違い

506 ：

簡単のため、2ビットの場合で考えてみる。
A = 00のときX = 00
A = 01のとき解なし
A = 10のときX = 11
A = 11のときX = 01,10
解があれば解を返し、なければ解なしと出力するアルゴリズムって総当たり探索になるのかな？
それとも代数的に解けるのだろうか？

507 ：

オーバーフロー切り捨てを考慮するとなるとかなり複雑になりそう

508 ：

A=000 X=000
A=001 X=011,110
A=010 X=101
A=011 X=
A=100 X=010
A=101 X=001,100
A=110 X=111
A=111 X=

509 ：

で、これ求めて何に使うわけ？

510 ：

0ビット目だけは下位ビットからの繰り上がりで1に出来ないことから
Aの0ビット目をみて

511 ：

>>509
FFT関係だと思います

512 ：

>>510
11は解があるよ

513 ：

A=0000 X=0000
A=0001 X=
A=0010 X=1001
A=0011 X=
A=0100 X=
A=0101 X=0111,1110
A=0110 X=0010,0100
A=0111 X=
A=1000 X=1011,1101
A=1001 X=0001,1000
A=1010 X=
A=1011 X=
A=1100 X=0110
A=1101 X=
A=1110 X=1111
A=1111 X=0011,1100,0101,1010

514 ：

フーリエ変換か

515 ：

nビット整数だとnが奇数でも偶数でも全ビットが1のものを除けば対称になってる

516 ：

その対称の端のXはオールビットが0か1

517 ：

>>513
これシンプルな計算で解の有無が判定できるのかね・・・不規則に見えるが

518 ：

^ をべき乗の記号として
2^((n+1)/2) 通りチェックする方法なら分かる

519 ：

A=1111 X=0011,1100,0101,1010,0110,1001,0111,1000,0001,1110,1101,0010,1011,0100,1111,0000

520 ：

>>519
反転じゃなくて逆順だよ？

521 ：

489 デフォルトの名無しさん [] 2012/10/04(木) 21:44:05.80 ID: Be:
    >>486
    分かりづらかったかも、すみません。
    ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、
    ｘの値を求めるには？
    ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど）

522 ：

質問者は反転と逆転の違いが

523 ：

例出すのも下手
わざとやってるだろ

524 ：

解いてみた
諸事情により 31 bit まで
#module
#defcfunc bitreverse int num, int bit, local rev
repeat bit
rev=(rev<<1)|((num>>cnt)&1)
loop
return rev
#deffunc solve array result, int num, int bit, local result_num, local u_, local l, local m, local n
dim result
n=1<<((bit+1)/2)
m=(1<<bit)-1
repeat n
l=cnt
u_=(num-l)&(n-1)
x=l|bitreverse(u_, bit)
if ((x+bitreverse(x, bit))&m)=num {
result.result_num=x
result_num++
}
loop
return result_num
#global
solve result, $ff, 8
repeat stat
mes strf("%x", result.cnt)
loop

525 ：

HSP?

526 ：

アルゴリズム記述用の抽象言語みたいなのってないのかな

527 ：

32bit全探索する気か

528 ：

8bitくらいまで>>513のように羅列していって何らかの傾向や法則性が無いか確かめられたらいいんだけどな

529 ：

しょうがねぇなぁ〜
http://codepad.org/Kkm8uPyR

530 ：

>>526
片言Algol知らんのか?

531 ：

"片言Algol"でググっても何なのか出てこないんですけどー"片言Algol"って何ですかー？

532 ：

片言のAlgol

533 ：

pidgin ALGOLも知らんとは！(怒

534 ：

pidgin ・・・　混成語
他の言語と混ぜて使うってこと？よけい混乱しないか？

535 ：

>>534
ある言語の、外人 植民地人向けカタコトOKバージョン。
満州国を作ったあたりでpidgin日本語を作ってた。
語尾を「〜アル」で統一とか。
廃れてしまったがモノはちゃんと完成し、教育もされたようだ。
マンガの中国人が「〜アルよ」と言うのはその名残らしい。

536 ：

ゼンジー北京ってまだ生きてんの？

537 ：

http://codepad.org/dZ6OuG1e
ghc
f "101010" --2進
fx "12abcd"--16進
虫食い算を解く要領で１桁ずつ特定しています

538 ：

http://codepad.org/ETbL5UUF
32bitでエラーに成るのを修正
A=B+(reverse B)
rx B --> A
fx A --> B
rx "123456" -->"7c609e"
fx "7c609e" -->["7a3440","7a2c40","723450","722c50","6a3448","6a2c48","623458","622c58","5a3444
","5a2c44","523454","522c54","4a344c","4a2c4c","42345c","422c5c","3a3442","3a2c4
2","323452","322c52","2a344a","2a2c4a","22345a","222c5a","1a3446","1a2c46","1234
56","122c56","0a344e","0a2c4e","02345e","022c5e"]

539 ：

データ構造とアルゴリズムと設計パターンは、
ソフトウェア開発に必須の技術

540 ：

B木のようなプログラム文も、書けるようにならなければなりませんか？

541 ：

プログラム文という言葉は初めて見たかも

542 ：

ヒント翻訳ソフト

543 ：

>>542
翻訳ソフト使うと何が解決するの？

544 ：

というかダイクストラ法とクラスカル法の違いって何？
両方とも最小スパニング木を求める方法なのにお互い関係ないものなの？
ダイクストラで検索かけようとしても候補にクラスカルって出てこないし
逆もない。
クラスカルはプリムとセットで議論になるケースが多いけど。
誰か教えて。

545 ：

定義が違うし出力も違う。
そして、「同じものを求める二つのアルゴリズムなら関係があるはず」と言うのは思い込み。

546 ：

クラスカル、プリム・・・重み付きで、その重みが最小となる全域木を求めるAG
ダイクストラ・・・その経路までの最短キョリを求めるAG

クラスカルは全てのノードを繋ぐ
ダイクストラは最短ノードを選択

547 ：

線形探索も立派なアルゴリズム。

548 ：

AGってなんなん？

549 ：

GAなら知ってる

550 ：2012/10/29

GKなら乙