12/03/24 12:34:28.90
□□□□□□□□□ ・右の図の□を■にしてすべての■をつなげたい
□■□■□■□■□ ・毎回違う結果にしたい
□□□□□□□□□ ・無駄がないようにしたい
□■□■□■□■□ ・輪にならないようにしたい
□□□□□□□□□ ・よろしこ
□■□■□■□■□
□□□□□□□□□
□■□■□■□■□
□□□□□□□□□
16:デフォルトの名無しさん
12/03/24 13:08:20.62
□□□□□□□□□
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□■□□□□□□ ・これはありか
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□□□□□□□□
17:デフォルトの名無しさん
12/03/24 13:37:09.87
つ ローグライクのダンジョン生成参考
18:デフォルトの名無しさん
12/03/24 15:08:07.10
何というか・・・宿題スレでやれ
19:デフォルトの名無しさん
12/03/24 15:19:59.08
ジオロケーションのアルゴリズムで相談をお願いします。
データレコード
struct
{
float x；
float y；
String buffer;
};
が数千件あるテーブルがあるとします。
その中からユーザーの座標(float ux. float ,uy)の半径 R(float)以内にある
データレコードのbufferを取り出すにはどうすれば一番効率が良くなるでしょうか？
テスト段階での条件では
範囲としては関東全域
Rの値は最大 100m
サーバー側のクロックは
CPUクロック：3GB
使用可能メモリ：6GB～10GB
レコードの平均使用容量：112byte
クライアント側はAndroidを利用してサーバーからへ座標を渡して、情報をリクエスト、
また新しい情報をポストするのみになります。
送受信にはUDPパケットの使用を考えています。
また挿入や削除がしやすいというのが第一の条件となっています。
なのでデータはすべてメモリ上におき、テキストエディタみたくギャップバッファと地域の細分化、リンクドリストを
複合的に持ち合わせて、定期的にＤＢへのアップデートを行っていこうと考えております。
以上を踏まえてどなたかアドバイスなどをいただけないでしょうか？
20:デフォルトの名無しさん
12/03/24 15:57:37.84
>>19
素人なりに考えた。
全データを100m四方のグリッドで分割しといて(ハッシュででも)、
ユーザ座標含めた隣接9グリッドについてのみ計算する。
件数も少ないし計算も複雑でないから、複雑な枝刈りはあんま意味ないとおもう。
てか数千件ならふつうに総当りでもいけそう。
じぶんがつくるなら、サーバは起動時とユーザシグナル受信時にDBから読むだけで
データ管理とは分離させる。
21:デフォルトの名無しさん
12/03/24 16:17:15.72
>>20
なるほど
参考になります。
ではデータはグリッドごとということして挿入、削除をすればいいということですね
ありがとうございます。
22:デフォルトの名無しさん
12/03/24 16:24:15.02
>>19
kd-treeがいいんじゃないかな。
フォトンマッピングでぐぐると、近傍のフォトン探索とかの使用方法が出てくると思う。
23:デフォルトの名無しさん
12/03/24 16:31:57.56
>>22
フォトンマッピングですね
調べてきます。
ありがとうございます。
24:１５
12/03/25 10:16:52.24
>>16
なしだぜ
25:デフォルトの名無しさん
12/03/25 10:50:24.50
>>15はアイちゃん
26:デフォルトの名無しさん
12/03/25 12:25:26.16
>>15
>無駄がないようにしたい
下記のように■同士を最短距離でつなげたいという意味ですか？
□□□□□□□□□ ・右の図の○を■にしてすべての■をつなげたい
□■○■○■○■□ ・毎回違う結果にしたい
□○□○□○□○□ ・輪にならないようにしたい
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□□□□□□□□□
これで全ての■がつながるなら24個の○のうち最低15個が■ですね。
15個の■と9個の□で全ての■をつなげた時は輪はありません。
以下の手順で全ての組み合わせが求まります。
１ 24個の○のうち15個を■、9個を□にした順列を順番に走査する。
２ 今調べている順列に上下左右が□の■があればボツ。
順列を再帰呼び出しで作り、
1～9個目の□の位置を決めるごとにその上下左右の■を調べ、
■の上下左右が全て□だったらその枝の走査を打ちきると効率的です。
27:デフォルトの名無しさん
12/03/26 02:12:37.52
面白そうな問題なんだが、
>>26の言うように「無駄がないように」の意味があいまいなんだよね。
>>26のような解釈でOKなのか、それとも探索に無駄がないようにという意味なのか。
28:京霊研
12/03/26 08:55:15.92
>>26
そうその○の位置だけ変えるって意味だぜ
探索はどうやってもいいぜ
それだと2組に分かれる可能性があるぜ
あと15個以下でも全部繋げられるから輪になるかもだぜ
29:デフォルトの名無しさん
12/03/26 11:03:44.25
■
■ ・これが孤立しているケース
■
30:デフォルトの名無しさん
12/03/26 11:14:18.36
>>28
>それだと2組に分かれる可能性があるぜ
確かにボツにする条件が不十分ですね。
それに15個を○から●にして2組以上になったら必ず輪ができます。
最後に全部つながったか確認する必要があります。
□□□□□□□□□
□■●■●■●■□
□●□●□○□○□
□■●■●■●■□
□●□○□○□○□
□■●■●■●■□
□○□○□○□○□
□■●■●■●■□
□□□□□□□□□
>あと15個以下でも全部繋げられるから輪になるかもだぜ
左上の■に残りの15個の■を●でつなげていくと考えてください。
1個の○を●にした時に左上に新たにつながる■は高々1個だけです。
だから全部の■をつなげるには最低15個の●が必要です。
1個の○を●にした時に輪ができたら新たにつながる■はありません。
だから15個の●だけで全部つながったら輪はありません。
31:デフォルトの名無しさん
12/03/26 23:50:53.03
・開始点の■を決める
■
A
■B■
C
■
・次に繋がる点をリストアップ
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
■□■
.A B
■■■E■
.C D
■□■
・次に繋がる点をリストアップ
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
・再帰
32:デフォルトの名無しさん
12/03/27 15:34:05.65
勤務表作成アルゴリズム募集。
ExcelVBAで勤務表を作ろう
ｽﾚﾘﾝｸ(tech板)
33:デフォルトの名無しさん
12/03/27 18:31:43.60
勤怠表はアルゴリズムってより
対象者向けインターフェースの推敲が難しいからな
ライン工相手に出勤退勤毎にキーボード叩けなシステムとかアホ過ぎるし
34:デフォルトの名無しさん
12/03/27 19:08:39.50
タイムカードをがっちゃんがっちゃん押したらUSBでPC等につながって自動管理、とかの機械ありそう
35:デフォルトの名無しさん
12/03/28 02:17:12.79
あながち馬鹿に出来ない
押し忘れとか、日付が変わってから退社とか、
３交替の夜勤とか
下手なものを作ると出勤か？退勤か？すら後で分からなくなるｗ
36:デフォルトの名無しさん
12/03/28 08:50:46.61
>>31
エクセルで作ったぜ～
URLﾘﾝｸ(www42.atwiki.jp)
37:デフォルトの名無しさん
12/03/28 10:21:13.89
>>34
うちのは無線LANで飛ばしてるお
38:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/29 00:04:51.11
うん
39:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/29 08:31:17.45
タンピンリャンペーコーを判別せよ
40:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/29 14:11:37.90
まず雀頭１と順子４つになっているか確認
その後１９字牌がないがチェック ない場合成立
二杯口は順子をグループ化してふたつどういつかチェックすればいいんでね
平和だけどタンヤオって時点で役牌じゃない＆二杯口も前提条件だから
両方が成立したとき自動的に成立
タンピンリャンペーコーを判定する専用ならこういうやり方でいいんでね
41:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/29 15:50:35.74
>>39-40
君らみたいなのが宇宙麻雀作るんだろうな(´･ω･`)
>>40
待ちは？
42:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/29 18:18:29.52
> 風牌や三元牌で順子可能
> ドラのみ和了
> 立直後明槓
> メンタンピン一盃口が役満
> 白があっても清一色可能
> 一気通貫が役でない
これはひどい
43:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/30 10:19:59.32
宇宙麻雀ググッたけど
設定ミスで>>42とかプログラマー神すぎるだろ
44:営利利用に関するLR審議中＠詳細は自治スレへ
12/03/31 21:02:41.36
閉路を沢山含んだインバースキネマティクスって
どうやればいいの？
もう既に有名なアルゴリズムとかあるの？
45:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/01 05:42:22.57
2-正則な閉路だけ考えた場合、移動した頂点から交互に重複するまで解決していくだけだし
そこから伸びた枝は普通に解決出来ないか？
46:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/01 13:39:02.37
>>45
注意してもらいたいのは、要件は「閉路を含んだ」ではなく
「閉路を沢山含んだ」になっている点です。
例えば、以下のような格子状の関節(5*5)をもっている場合、
リアルタイムで計算させるのは結構難しいかと。
┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘
もうすでに誰か偉い人がアルゴリズムを考えていたりしないかな、と。
47:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/01 21:37:29.89
一度通った道を再び通らないようにすることだけ考えりゃいいんだから
結局は同じじゃねえの
48: ◆QZaw55cn4c
12/04/01 21:54:11.78
「薔薇の名前」のアルゴリズムは使えないか？
49: ◆QZaw55cn4c
12/04/01 22:27:20.12
>>15
ｽﾚﾘﾝｸ(tech板:187番)
50:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 06:58:39.00
>>47
もし簡単ならば、そのアルゴリズムを教えてほしい。
そしてその計算量の見積もりも。
でも、それが簡単じゃないからこそ今のIKは
軒並み「ループ無し縛り」を課している訳で。
51:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 07:54:20.67
なんでQZがいんの
52:１５
12/04/02 14:36:11.40
>>49
ありがたまきんΩ
53:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 18:42:03.65
さめがめの最適解を求めるアルゴリズムを
作ろうとしています。
□□●●□□●□●
○■●■●■●■□
○●●●□○□○●
□■●■●■●■□
■●□○□○□○●
□■●■●■●■●
■○□○□○□■□
□■●○●■●■□
■□□○□■□■■
ルール：
隣り合う２つ以上の連続した同じ種類の記号は消去できる。
重力あり。消えたら下に詰める。
連続で消せたら高得点
この仕様で、連続して消せる最大の回数を求めるのと、
完全に消去するという二つをそれぞれで考えたいのですが、
総当りだとものすごい時間がかかりそうなので、何か
数学的な理論や手法などはないでしょうか。
１）消せるブロックの集合を探す
２）ブロックを消す
３）消えたブロックの上のマスを落とす
４）１）に戻る
特に１）の部分の隣り合う２つ以上の連続した同じ種類の記号を
探すのが結構時間がかかりそうなので時間短縮する方法が
あれば教えてください。
54:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 19:42:44.37
さめがめってNP完全でしょ。
> 総当りだとものすごい時間がかかりそう
試してはいないんだな。
55:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 20:03:33.82
発散しそうもないし、先ずは試してみたらいいんじゃね。
56:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/03 10:14:52.66
消せるブロックの集合が崩れてない時に
その情報を次のターンに持ち越せば少しは軽くなるな
57:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/08 22:28:30.73
さめがめってよくフラッシュとかでもゲームあるけど、
ブロック消すところはなぜあんなに早いの？
思い浮かんだロジックだと、>>53を例にすると、
１）9x9のテーブルを２種類作る（Ａテーブル、Ｂテーブル）
２）Ａテーブルに記号別にフラグ（たとえば１～５）を埋め込む
３）たとえば左上を基点に上下左右に同じ種類の記号が
あるか調べる
４）あったらＢテーブルに消せる場所に種類のフラグを埋め込む
５）基点から３）と４）を実行して全部調べる
６）Ｂテーブルに消せるマスがあれば、同じ位置のＡテーブルのマスを空白にする
７）Ａテーブルの空白のマスを消去し、上にマスが残ってたら下に下ろす
ここまでを一瞬でやってるわけですよね？
もっと簡単にできる方法があるのかな。
58:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 00:26:59.90
1GHzのCPUで、一マスの処理が１０００命令かかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。
59:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 00:52:48.40
なんで >>58 は、1クロック1命令だと思ったんだろう
60:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 01:03:57.34
ベンチでFLOPS計測するしかないってか。
61:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 09:21:58.82
え、でも計算量って１マス検査するのに、残りの８０マスをチェックしないと
いけないから、９ｘ９のマスのチェックをするのに、
８１×（８１－１）×・・・ってなるんじゃないの？
62:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 09:38:20.91
隣り合ってるマスだけでいいだろ。
63:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 20:26:34.18
1クロック1命令、っておおざっぱな見積りでは普通に使うだろうが
64:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 21:03:02.17
>>63
いいからあなたはPentiumだけ使っててください。
65:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 22:10:30.77
大昔のBASICでは、PAINT文で塗りつぶしを行うと
塗りつぶして行く様子が目で見えてたなぁ
66:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 22:54:13.98
>>64
１クロック１命令の方がCPUとして少数派だと思うが・・・
２，３クロック１命令で見たほうが良くないか？
67:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 22:55:03.93
ごめ・・・
>>66は>>63向け
68:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 23:33:16.52
クロック周波数で性能は比較できない
69:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/09 23:36:06.57
総括すると>>63でオーダとしては妥当ってことじゃないの？
70:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 00:16:07.22
ｽﾚ違いだし、とっとと収束させるべきなんだろうけど…
>>69
>総括すると
頭おかしいのか？
71:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 00:20:24.86
オーダーは変わらない。
1命令が1クロックだろうが、100クロックだろうが変わらない。
72:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 00:30:55.57
話がかみ合ってなくてワロスｗｗｗ
73:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 00:40:56.01
1GHzのCPUで、一マスの処理が１０００クロックかかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。
これでおk。
74:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 06:50:43.40
>>68 IPC（CPI）が同じなら、クロックが倍のコンピュータなら、
周辺による遅れがなければ、倍の性能だろうが。バカか？
75:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 11:26:00.65
アルゴリズムの文脈で、計算量ってどう見積もるのか知らない奴がこのスレにいるとは
76:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 11:47:24.19
定数倍が重要なことも時にはあるだろうが
最初のレスがゲームについてなんだし
77:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 13:45:31.87
>>74
ふつー、バス速度は絶対に倍にはならないですよね…
78:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 18:16:05.89
>>62
そっか。
となれば、最大８１×４回（上下左右）チェックすればいいだけか。
さらに端っこのますは片側は壁だからもっと少ない計算量で
済むんだな。
79:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/10 23:10:48.23
>>75
見積もりといえばKKD法だよな。
80:デフォルトの名無しさん
12/04/14 19:53:09.94
スケープゴート木って、サイズ計算に時間食い過ぎるな。
かと言ってノードにサイズ情報埋め込むのは本末転倒な気がするし。
81:デフォルトの名無しさん
12/04/14 20:57:57.57
俺さ、ハッシュマップってのを思いついたんだが
82:デフォルトの名無しさん
12/04/14 20:58:49.31
車輪
83:デフォルトの名無しさん
12/04/14 21:05:42.14
八種抹粉
84:デフォルトの名無しさん
12/04/14 21:09:24.55
いらなーい
85:デフォルトの名無しさん
12/04/16 05:22:45.95
一度車輪をやらないと上を行くアルゴリズム作るのは無理
86:デフォルトの名無しさん
12/04/16 08:19:00.54
さめがめ：連続で消せたら高得点
てナニ？
87:デフォルトの名無しさん
12/04/19 11:06:37.63
イナズマの描画法をおしえれ
88:デフォルトの名無しさん
12/04/19 17:11:02.18
Ｎ
89:デフォルトの名無しさん
12/04/19 17:13:32.69
Piローダーだっけ、イナズマローダーって
90:デフォルトの名無しさん
12/04/19 17:24:40.05
>>88
Z じゃね?
91:デフォルトの名無しさん
12/04/19 17:36:25.65
picとかだね
92:デフォルトの名無しさん
12/04/19 22:52:28.58
CADで言うところのフィレット
２つの線分があり、端点の一つを共有している状態で
半径５のフィレットを行いたい
つまり、点P1(x1,y1) 点P2(x2,y2),点P1(x3,x3) で 点P2の部分をフィレットしたい
お分かりなる方がいたらおしえてください
93:デフォルトの名無しさん
12/04/19 23:14:56.11
内角に辺5のひし形作って対角を中心とした円
94:デフォルトの名無しさん
12/04/20 03:22:59.96
>>92
点と直線の距離の公式を使って垂線の長さ5の方程式を二つ立てる。
これを連立方程式として解くと円の原点候補が二つ求まる。
点P2→点P1と点2→原点候補の内積が正になる方が円の原点である。
原点を中心とした半径5の扇を描く。
>>93
菱形の辺の長さが5なら内角が直角の時以外は円の半径は5より小さくなります。
95:デフォルトの名無しさん
12/04/20 09:28:57.75
ArcTo関数か
俺なら自前でBezier2Dするねｷﾘｯ
96:デフォルトの名無しさん
12/04/21 07:11:47.54
test
97:デフォルトの名無しさん
12/04/21 07:13:42.88
2と3だけを複数回かけてある数Aにもっとも近い数を作りたーい
98:デフォルトの名無しさん
12/04/21 11:16:24.54
総当り
99:デフォルトの名無しさん
12/04/21 23:17:10.93
宿題か
100:デフォルトの名無しさん
12/04/22 21:33:27.78
文字列が正しくデコードされてるか試験する、という目的の下、文字列の尤度を求めるために、
文字コードの範囲を確率変数として教師信号を用意（様々なファイルから読み込んだ文字列による）したのですが、
いまいち良い信号になりません。（正規分布に従わない）
ラテン文字帯が凄まじい数になり、ラテン文字を含めば全部尤度高い、という結果になってしまいます。
文字化けしたと思われる値（教師信号分布0の文字帯）の信号値を、より低い値にしたい（コストを大にしたい）のですが、
こういう場合、どういう風に信号を改善していけばいいでしょうか・・。
101:デフォルトの名無しさん
12/05/11 13:57:17.81
a, b, c, d, e, zの昇順ソートされた整数配列があります。
それぞれ、1000万要素程度あり、mallocで領域を確保してあります。
a～eの配列のそれぞれの要素から、zに含まれている要素を抜いてから、
全て結合してソートして出力したいです。
どういった方法が一番早いでしょうか？
それぞれの配列で
aとz
bとz
cとzと順番に、それぞれでa[0]とz[0]から逐一比較していって、
一致しない要素をメモリに持っておき、
最後に結合して、ソート
というのを考えましたがこれが最良なのかどうか…朝からずっと悩んでいます。
102:デフォルトの名無しさん
12/05/11 14:08:02.26
整数かつソートされていると保証されているなら
各配列にポインターをつけて
ポインター群でいちばん小さいものをresult配列に追加してポインターをインクリメント
でいいんじゃね
103: ◆QZaw55cn4c
12/05/12 01:57:40.79
>>101
マージソートの応用でいけそうだ。
a, b, c, d, e の先頭なかから一番小さいものをとりだし result に書き出す。
ただし、それが z の先頭と等しかったら捨てる。
a～e + z のなかで z が一番小さかったら、z の先頭を捨てる。
104:デフォルトの名無しさん
12/05/12 02:53:22.74
なるほど
105:デフォルトの名無しさん
12/05/12 11:59:03.22
ありがとうございます。
コーディングしてみます
106:デフォルトの名無しさん
12/05/14 11:25:53.96
うーん…それぞれの配列がユニークじゃない時はむりか。。
すみません、全配列で要素が重複してる可能性があり、
同配列で値が重複した要素もそれぞれ一要素として扱いたい
例えば、
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:デフォルトの名無しさん
12/05/14 12:10:41.04
>>106
どうとでもできるとおもうけど
考えてるとおりにaからa'を出力するイテレータ(ジェネレータ)書けばいいんちゃう？
元の配列がソートされてるのにそれを利用しない手はない。
108:デフォルトの名無しさん
12/05/14 12:24:59.78
>>106
103の「先頭なかから一番小さいものをとりだし result に書き出す。 」時に、
一番小さい数をある分だけ result に追加すれば良いだけだろ。
少しは考えれば分かるだろうけど。
109:デフォルトの名無しさん
12/05/14 12:43:05.75
はい、今回はメモリもある程度限られた状況で
なんと言っても速度重視なので、
何パターンか考えて模索してみます。
110:デフォルトの名無しさん
12/05/24 20:24:10.54
URLﾘﾝｸ(www.i.u-tokyo.ac.jp)
これの専門科目II-1 (4)がわからないんですが
方針だけでもいいので教えていただけないでしょうか？
111:110の問題
12/05/24 20:27:06.66
問題 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:デフォルトの名無しさん
12/05/25 07:27:26.01
手ダイクストラ法を逐次やって、既存の木と合流したら、最短経路の再計算で手が抜けるのでは？
113:デフォルトの名無しさん
12/05/25 17:00:13.49
深さ優先探索の空間計算量って
木の最大深さm, 最大分岐数 b として O(bm) ってありますが、
一つのノードで分岐どうし順序がデータ構造のなかに定義されている、または自明であれば
O(m) になりますよね？
114:デフォルトの名無しさん
12/05/28 17:28:58.85
ビー玉云々が何を言ってるのかよくわかりません。この例えは何か原典があるのでしょうか？
URLﾘﾝｸ(ja.wikipedia.org)
115:デフォルトの名無しさん
12/05/28 17:44:51.94
ググり直した出典はありました読んでみます
116:デフォルトの名無しさん
12/06/05 00:17:18.82
diffの動作原理を知る～どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社
URLﾘﾝｸ(gihyo.jp)
これ全然理解できない・・・
117:デフォルトの名無しさん
12/06/05 09:26:36.11
>>116
「編集距離」で検索すれば分かりやすいページがたくさん
10年位前にOCRの認識率を計測するために色々とインプリメントしたな～
118:デフォルトの名無しさん
12/06/05 09:35:41.80
単純なアルゴリズム（長さMとNの文字列に対して計算量MNになるアルゴリズム）の
解説をすっとばして、実用的なアルゴリズムの解説になってるなぁ。
理解するためにはまず単純なアルゴリズムの解説を探すといいと思う。
119:デフォルトの名無しさん
12/06/05 11:11:01.86
>>116
技術評論社のサイト初めて見たけど、中々興味深い記事があるな。
120:デフォルトの名無しさん
12/06/05 11:41:07.31
【問１】
ある点が三角形abcの中にあるかどうかを判定する簡潔な方法を俺に教えよ
121:デフォルトの名無しさん
12/06/05 11:56:58.65
ぼくのかんがえたさいきょうの(ry
ある点をdとすると、
abc＝abd+acd+bcd（面積）
どうやって実装するのかはシラネ
122:デフォルトの名無しさん
12/06/05 11:58:14.51
・重心とその点を結んで各辺と交わるかどうか調べる
123:デフォルトの名無しさん
12/06/05 12:10:29.02
いや結ぶのは三角形の一点でいっか
124:デフォルトの名無しさん
12/06/05 12:14:58.41
0 < ↑ab・↑ap かつ 0 > ↑ab・↑bp かつ
0 < ↑bc・↑bp かつ 0 > ↑bc・↑cp かつ
0 < ↑ca・↑cp かつ 0 > ↑ca・↑ap ならば、点pは△abcの中。
なお、計算に無駄がある。
125:デフォルトの名無しさん
12/06/05 12:17:49.79
ごめん、嘘。でもベクトルの内積の符号を調べる方法で良かったはず。
126:デフォルトの名無しさん
12/06/05 12:38:23.40
0 > (↑ab・↑ap)(↑ac・↑ap) かつ
0 > (↑bc・↑bp)(↑ba・↑bp) かつ
0 > (↑ca・↑cp)(↑cb・↑cp)
127:デフォルトの名無しさん
12/06/05 13:04:37.41
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:デフォルトの名無しさん
12/06/05 13:39:43.07
目視で確認が一番簡素
129:デフォルトの名無しさん
12/06/05 13:49:07.51
>>121
これ？
URLﾘﾝｸ(upload.wikimedia.org)
130:デフォルトの名無しさん
12/06/05 17:15:26.77
ヘロンの式だな
131:デフォルトの名無しさん
12/06/06 10:50:47.34
A. ありがとうございました
132:デフォルトの名無しさん
12/06/06 17:46:11.37
1. VRAMに三角形を描画して中を赤とかで塗る
2. 点に対応するアドレスの値を読み、背景色か赤か判定
BASICならたぶん2行で書ける
133:デフォルトの名無しさん
12/06/06 17:49:59.95
えらい無駄が多いな
134:デフォルトの名無しさん
12/06/06 19:49:12.59
□□
□ ・ □
□ □□
□
こういうコーナーができたときに、「・」の場所は塗り潰せないからアウトだな。
135: ◆QZaw55cn4c
12/06/06 21:20:34.03
>>134
詰め碁か？
二眼確保で安泰型にみえてしまうのだが？
136:デフォルトの名無しさん
12/06/07 04:44:03.28
一発なら>>126
もしくは２点から特定の角度範囲内
何度も判定するなら>>132みたくマップを作ったほうがいいな
>>134
塗りつぶしを自作すれば可能
137:デフォルトの名無しさん
12/06/07 10:13:32.12
アンチエイリアスつきの塗りつぶし三角形を計算で出そうとすると
URLﾘﾝｸ(www42.atwiki.jp)
138:片山博文MZボット ◆0lBZNi.Q7evd
12/06/08 11:57:52.99
>>137 これすげー。出版しろよ。
139:デフォルトの名無しさん
12/06/08 13:37:48.75
wikiの内容とは何の関係もないんだな
140:デフォルトの名無しさん
12/06/08 13:57:23.20
ただのアフィじゃねーか
死ねよ
141:じゃがりきん
12/06/09 09:34:10.60
このコードじゃ出版できないぜ～
142:デフォルトの名無しさん
12/06/09 22:58:18.07
ワイルドだろぉ～？
143:デフォルトの名無しさん
12/06/10 00:39:33.38
ダイクストラ法のwikipediaでの説明が日本語と英語のページで全然違うんだけど
なぜ？
144:デフォルトの名無しさん
12/06/10 00:43:39.84
公用語の違いかな
145:デフォルトの名無しさん
12/06/10 19:25:30.28
書いた人が違うから
146:デフォルトの名無しさん
12/06/10 19:31:34.41
不特定多数が編集するから
あまり信用ならない
悪意ある改変とかマイナーな記事なら修正される機会も少ないだろうし
147:デフォルトの名無しさん
12/06/10 19:42:39.47
>>146
そういう思い込みを吹き込むのは如何なものか。
148:デフォルトの名無しさん
12/06/10 19:59:55.31
「いくらなんでもwikipを書き換えるなんてことはしないだろう」という思い込み
149:デフォルトの名無しさん
12/06/10 20:14:16.52
どこか１サイトの情報だけ見ようとするからダメなんだよ
個人サイトでもその人の勘違いや間違いで誤った事が書かれてることもあるし
wikipedia含めいくつかのサイトで情報見比べることが大事
150:デフォルトの名無しさん
12/06/10 20:34:12.90
>>143
翻訳記事じゃないんだから構成が違っていて当然だが、何か問題でも？
151:uy
12/06/11 04:31:24.08
Wikipediaとか
2chで信者とアンチが争ってるようなカテゴリーの記事だと改変されまくり
Wikipediaと、Wiki以外のサイトの最低2つは情報見ろよゴミカス死ねと思う
152:デフォルトの名無しさん
12/06/11 05:42:43.76
基地外コテｷﾀｰ
153:デフォルトの名無しさん
12/06/12 14:09:24.92
URLﾘﾝｸ(detail.chiebukuro.yahoo.co.jp)
お願いします
154:デフォルトの名無しさん
12/06/12 16:15:20.50
英語が読めないアホはどうぞインチキ情報に騙されてくださいねｗ
155:デフォルトの名無しさん
12/06/12 21:12:15.06
概要の、まずビー玉と紐を用意し・・・
擬似コード
こんな説明でわかるやつ天才や
156:デフォルトの名無しさん
12/06/17 05:10:41.60
trieすら自力実装できない自分の頭に悪さに絶望してます
死んだ方がいいですか?
157:デフォルトの名無しさん
12/06/17 05:42:29.75
うん。
158:デフォルトの名無しさん
12/06/17 05:47:14.55
プログラミングの才能がないと、いくら努力しても土方止まり
他の才能を持っている分野で頑張った方がいいよ
アルゴリズムの説明すると、すぐ理解する後輩がすげーと思ったら、
まわりの大半がそうだった。死にたい。
159:デフォルトの名無しさん
12/06/17 09:01:12.14
培養菌の数をカウントするのってどうやるんだろう？
画像から直径と中心を判別するには？
160:デフォルトの名無しさん
12/06/21 01:34:04.14
>>159
羊と狼を数えるアルゴリズム
URLﾘﾝｸ(www2c.comm.eng.osaka-u.ac.jp)
161:デフォルトの名無しさん
12/06/21 01:39:31.54
コロニーだから丸？
輪郭抽出→クロージング→オープニング→連続してるのを数える
162:デフォルトの名無しさん
12/06/21 03:30:23.41
>>159
単純に色の違うピクセル数をカウントして１ピクセルあたりいくらってのをかけてやるんじゃダメ？
163:デフォルトの名無しさん
12/06/21 09:27:55.64
大きさの異なる円が２つ以上重複していてもカウントできなくちゃダメだろ
164:デフォルトの名無しさん
12/06/22 02:20:12.99
サメガメの判定で処理負荷が問題になる状況ってどんなだよ。しかも揚げ足取りで揉めてるし。
165:デフォルトの名無しさん
12/06/22 07:32:19.63
亀
166:デフォルトの名無しさん
12/06/22 08:00:23.50
ほとんど重複だから
輪郭の一部である弧から直径と中心を拾うアルゴリズムかな・・・
で、どうやるの？
167:デフォルトの名無しさん
12/06/22 08:36:03.17
OpenCV を使う。
というか画像処理スレの話題。
168:じゃがりきん
12/06/27 13:58:41.44
>>137の一部がカラパイアに載ったぜ～
169:デフォルトの名無しさん
12/06/27 14:06:45.24
本人いたのかいな
170:デフォルトの名無しさん
12/06/28 13:15:54.50
円の内部（円周上を含む）に点を指定した数だけ打ちたい
それぞれの点の距離を最大化するように打つにはどうすればいい？
171:デフォルトの名無しさん
12/06/28 13:29:06.42
最適化問題むずかしす
172:デフォルトの名無しさん
12/06/28 13:39:35.73
n=1 どこでも
n=2 2点を繋ぐ線分が円の中心を通るような円周上の2点
n=3～6 円に内接する正n角形の頂点
n=7 円に内接する正6角形の頂点と円の中心
n>=8 これの求め方を教えてってこと
173:デフォルトの名無しさん
12/06/28 13:42:50.29
予想としては
同心円の円周上に点を取っていくことになる
174:デフォルトの名無しさん
12/06/28 13:43:23.14
なかなか面白い問題
175:デフォルトの名無しさん
12/06/28 13:46:30.74
正三角形による円充填になりそう。
176:デフォルトの名無しさん
12/06/28 13:54:51.33
１．円内にランダムに点をばらまく。
２．全ての点についてそれぞれ最近傍の点を見つける
３．その点から離れる方向に移動。移動量はXXX。
４．３の移動量の総和が閾値以下になるまで２へ戻って繰り返す。
みたいなのを考えたんだけど移動量はどうすればいいか
177:デフォルトの名無しさん
12/06/28 13:55:12.35
充填問題の一種だろうな。
URLﾘﾝｸ(ja.wikipedia.org)
に
1940年、マジャル人数学者 László Fejes Tóth は、六方格子が正規も非正規も含めたあらゆる円充填の中で最も高密度であることを証明した。
とあるが参考になるだろうか。
178:デフォルトの名無しさん
12/06/28 14:02:08.92
>>176
1番目と2番目に近い点と自身で正三角形を作るように移動してはどうか
移動量と移動方向が決まる
179:デフォルトの名無しさん
12/06/28 14:03:00.53
>>176
振動しまくって終わる予感。
180:デフォルトの名無しさん
12/06/28 14:56:24.90
URLﾘﾝｸ(hydra.nat.uni-magdeburg.de)
181:デフォルトの名無しさん
12/06/28 15:29:41.61
球ならどうなんの？
４次元以上なら？
182:デフォルトの名無しさん
12/06/28 16:17:59.04
>>176
単純に (距離)^-2 の斥力がはたらくようにしてみた
URLﾘﾝｸ(www.dotup.org)
円周部の密度が高くなってしまう
183:デフォルトの名無しさん
12/06/28 16:20:30.94
>>182
それって再近傍の点からの斥力？
全ての点から r^-2 の斥力を受けたらどうなるかね。
184:デフォルトの名無しさん
12/06/28 16:21:38.62
>>183
すまんこ
全ての点からの斥力にしてる
185:デフォルトの名無しさん
12/06/28 16:27:49.50
毎ターン、各点の再近傍の点からの距離の平均を求め、その平均値との差の二乗に比例して引力／斥力を受けたらどうなるだろうか。
186:デフォルトの名無しさん
12/06/28 16:32:57.36
>>182
円周部から中心方向に移動する力が働かないからかな
187:デフォルトの名無しさん
12/06/28 16:43:40.74
点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:デフォルトの名無しさん
12/06/28 17:24:25.85
>>182
円周部を端点じゃなくて無限にしてみたらどうだろう
189:デフォルトの名無しさん
12/06/28 17:29:54.11
>>187
定式化がめちゃくちゃじゃないの？
例えば4点でそれを満たすユークリッド平面上の点の例があるの？
190:デフォルトの名無しさん
12/06/28 18:00:35.89
>>188
無限に飛んでいくだけだな
191:デフォルトの名無しさん
12/06/28 18:05:33.70
逆に考えるんだ。
URLﾘﾝｸ(mathnokai.seesaa.net)
こういう正三角形のメッシュを考えて、
ちょうど求める数の頂点が円内部に入るように、円の半径と中心を動かすんだ。
192:デフォルトの名無しさん
12/06/28 18:48:26.53
>>191
点の数が多いときは圧倒的によさそう
193:デフォルトの名無しさん
12/06/28 23:25:07.62
常に格子点に来るわけじゃないと思うけど
194:デフォルトの名無しさん
12/06/28 23:30:50.22
何が？
195:デフォルトの名無しさん
12/06/28 23:57:54.20
最適解が
196:デフォルトの名無しさん
12/06/29 01:35:35.32
>>191
ちょうど数をとっても隙間ができる
その分まだ距離は広がれる
197:デフォルトの名無しさん
12/06/29 03:44:55.03
いや、無理だろ
198:デフォルトの名無しさん
12/06/29 03:54:38.76
>>191の場合、４，５，６のケースで>>172と違いがでてくる
8以上でも不都合があるかもしれん
199:デフォルトの名無しさん
12/06/29 04:38:18.99
>>176で粒子法もどきでFA
200:デフォルトの名無しさん
12/06/29 04:40:13.84
外縁部は円周上にへばりつかせて残りを内部にばらけさせるほうがいい
201:デフォルトの名無しさん
12/06/29 08:30:00.42
>>190
いや
無限遠という意味ではなく
無限循環？的な意味だった
「無限だけど閉じた宇宙」
みたいな
専門用語知らんのですまそ
202:デフォルトの名無しさん
12/06/29 10:50:05.35
>>196
無理。外周で幾つか点を動かせるかも知れんが、内部は動かせない。
203:デフォルトの名無しさん
12/06/29 11:22:06.93
>>191
8個の場合円はどこにどの大きさで取るの？
204:デフォルトの名無しさん
12/06/29 11:27:55.32
円に内接する、正六角形に正三角形を一つたした、↓の図形の頂点が解になるだろうな。
＿＿＿
／ ＼／
＼＿／
これより頂点間距離が大きいのがあったら提示してくれ。
205:デフォルトの名無しさん
12/06/29 12:11:49.17
隙間だらけじゃん
URLﾘﾝｸ(www.dotup.org)
例えばこれらの点をこう動かせばどの点との距離をとっても広がるか変わらないかだね
狭まる箇所は無いね
206:デフォルトの名無しさん
12/06/29 12:15:14.96
存在しないファイル。
207:デフォルトの名無しさん
12/06/29 12:21:33.24
すまんうｐし直した
URLﾘﾝｸ(www.dotup.org)
208:デフォルトの名無しさん
12/06/29 12:26:58.00
>>207
一番下の二つの頂点も動かさないと、距離変わらないぞ。
そして全部動かした後で、距離が広がってるかも確認してくれ。
209:デフォルトの名無しさん
12/06/29 12:28:41.92
>>204
その図形を円に内接させた状態で、外周に近い一部の頂点は更に円周方向に移動できそうだよ。
要は>196か。
でもまぁ、>176で闇雲に求めるよりも>176の1で与えるべき初期値としてはいいのか。
210:デフォルトの名無しさん
12/06/29 12:40:20.28
最小距離を最大化すればいいという考え方と
全ての点の組み合わせの距離の総和を最大化するという考え方の違いか
211:デフォルトの名無しさん
12/06/29 12:45:37.56
帰ったら俺も作ってみるか
212:デフォルトの名無しさん
12/06/29 14:59:49.66
>>208
下二つも広げられるよ
213:デフォルトの名無しさん
12/06/29 15:26:31.30
>>204
正七角形の頂点＋中心点
214:デフォルトの名無しさん
12/06/30 00:07:19.12
>>170これは何に使うアルゴリズムなのかな
215:デフォルトの名無しさん
12/06/30 00:10:50.60
サンプリングとか？
216:デフォルトの名無しさん
12/06/30 00:25:55.72
どんなＮ角形も三角形に分割できるわけで２点の距離を同じにするなら近隣の３点を結ぶと正三角形になるような形が理想的だが
どんな２点でも等距離である必要はなく、すべての点の中で２点間距離が最小となる距離を円の範囲内で最大化するって問題だから
単純に正三角形の敷き詰めからの切り抜きでは実現できないってことか
ある正円Rがあり
Rの内側と円周上に合わせてＮ個の点が存在し
Ｎ個の点のうち任意の２点間の距離Ｄp [p=1,2,...,N*(N-1)/2]と定義したとき
Min(Dp)を最大にするＮ個の点の位置を求める
217:デフォルトの名無しさん
12/06/30 00:34:11.07
？
218:デフォルトの名無しさん
12/06/30 01:32:33.72
>>215
ずばり正解
219:デフォルトの名無しさん
12/06/30 01:43:26.93
このスレにいる連中のレベルを調査か
220:デフォルトの名無しさん
12/06/30 01:44:13.48
そして有望そうな奴はバシバシスカウト
221:デフォルトの名無しさん
12/06/30 01:53:46.77
サンプリングなら >>191 でも正方格子でもいいんじゃないかと思った
222:デフォルトの名無しさん
12/06/30 01:55:04.81
有望そうなのって居る？
223:デフォルトの名無しさん
12/06/30 03:01:35.40
正三角形とか正方形メッシュで
中心と半径を探すアルゴリズムってどうやるの？
224:デフォルトの名無しさん
12/06/30 03:14:52.14
点の重心求めて最遠点までを半径にすりゃいいんじゃね？
225:デフォルトの名無しさん
12/06/30 03:23:51.65
最近距離の２点を見つける
その２点だけ自身を除くすべての点からの斥力方向へ移動（移動量は２番目に距離の短いものより１以上長くなるよう）
点が円の外側へ移動しようとするとき、円自体を移動させすべての点が円内に収まるようにする
でやってみたがダメだった
226:デフォルトの名無しさん
12/06/30 04:12:00.84
>>223
もしかして >>159 なのか
つくづく問題を説明する気のない人だｗｗｗ
シャーレ上の培養菌のコロニーの数と半径を求めよ
サンプル画像
URLﾘﾝｸ(www.dotup.org)
黒線がシャーレ
ピンクの部分が培養菌のコロニーである
コロニー同士は重なる場合もある
って感じじゃないの？
227:デフォルトの名無しさん
12/06/30 04:14:41.54
>>224
点の重心って？
228:デフォルトの名無しさん
12/06/30 04:16:10.16
>>226
いや全く別人
流れ見てて気になっただけ
229:デフォルトの名無しさん
12/06/30 04:31:22.77
別人だったか
230:デフォルトの名無しさん
12/07/02 16:30:54.01
すみません、質問です：
voronoi分割のクラスライブラリは、どこかにありますでしょうか？
色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz
231:デフォルトの名無しさん
12/07/02 16:51:20.09
スレ違い
232:230
12/07/02 17:04:55.20
エエｴｴェェェｪ(略
しかし別スレに移動したら、マルチあっちいけと叩かれるだけ。
このスレでお願いしますOTL
233:デフォルトの名無しさん
12/07/02 18:04:21.18
片山議員は参加者に囲まれながら、「民主党政権になってから、生活保護の不公平が見逃すことができないところに来ている。
外国人の不正受給に関しても、まずは日本人の、真面目に義務を果たしている人が優先。
今は特に、韓国なんてすごく豊かなんですから」と持論を展開し、
「私に対してもいろいろ嫌がらせがあったが、どこから来ているかはわかるんですよね。私たちの日本を愛するマグマの方が強いことを教えよう。
日本が正直者が報われる、本当に強い国にもう1度なれるように、私たちががんばりましょう」
と呼びかけると、参加者からは大きな拍手が起こった。
URLﾘﾝｸ(www.j-cast.com)
URLﾘﾝｸ(www.j-cast.com)
URLﾘﾝｸ(www.j-cast.com)
前
ｽﾚﾘﾝｸ(poverty板)
ｽﾚﾘﾝｸ(poverty板)
234:デフォルトの名無しさん
12/07/02 18:16:36.16
>>230
> 色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz
なぜBoost.Polygon.Voronoiではダメなのか
URLﾘﾝｸ(svn.boost.org) を見てもわからない。
せめてBoost.Polygon.Voronoiが動作しない環境を挙げるべきでは。
235:デフォルトの名無しさん
12/07/02 19:15:21.06
>>232
マルチした以上しかたない
２ｃｈで質問したいなら半年ＲＯＭれ
236:デフォルトの名無しさん
12/07/02 22:33:24.51
>170
・中心(0,0)、半径1の単位円として一般性を失わない
・1点を (-1, 0)と決め打ちしても一般性を失わない
この条件下で、最近傍の点との距離を dist とした場合に n 点詰め込む処理を用意して、
dist に対して二分探索を行った。
詰め込む処理はある点を追加した時に、
1) その点を中心とした半径 dist の円と単位円の交点
2) その点を中心とした半径 dist の円と、今まで追加してきた各点を中心とする半径 dist の各円との交点
を次の候補として探索した。
n = 20 辺りから急激に遅くなる。
似た問題で URLﾘﾝｸ(en.wikipedia.org) があってその結果と比べると大体合ってそうな感じ。
URLﾘﾝｸ(ideone.com)
237:236
12/07/02 22:40:36.62
勢い込んで書いてからあれだけど
>210
>最小距離を最大化すればいいという考え方と
>全ての点の組み合わせの距離の総和を最大化するという考え方の違いか
で、最小距離を最大化した場合(あるいは >216 の定式化の場合)で、総和が最大になるかは分かんないね。
238:230
12/07/03 09:11:29.66
>>234
HEW。
テンプレート構文を対応していないので、STLも使えません。
>>235
マルチしていません。
239:デフォルトの名無しさん
12/07/03 09:21:35.74
スレ違いつってんだろが
失せろゴミ
240:デフォルトの名無しさん
12/07/03 09:52:51.30
Voronoiのデータ構造とアルゴリズムについてでそ。
脳に障害があるの？239はｗｗｗ
241:デフォルトの名無しさん
12/07/03 09:54:38.21
↑池沼
242:デフォルトの名無しさん
12/07/03 11:24:00.28
回答が返って来ない所でうだうだとするより、他所に行った方が良くないか？
243:デフォルトの名無しさん
12/07/03 11:30:59.47
↑オマのうだうだジャマ。てか、それがオマエの存在そのものｗｗｗｗｗ
244:デフォルトの名無しさん
12/07/03 12:06:27.06
クラスライブラリの場所を尋ねるスレだったのかここ
245:デフォルトの名無しさん
12/07/03 12:07:08.76
>>238
スレ立てるまでもない質問はここで 120匹目
ｽﾚﾘﾝｸ(tech板)
246:デフォルトの名無しさん
12/07/03 12:13:40.25
と言うよりこのスレで質問することが妥当であることを示す一言でもあればよかったのにね
『特殊なアルゴリズムのためこのスレの方が一番詳しいんじゃないかとここで質問いたしました』とかさ
247:230
12/07/03 12:19:40.11
意外や意外に妥当なvoronoiクラスライブラリが無かったので来ました。
・アルゴリズム事典に無かった
・Javaアプレットは小型のものがあったがC++やC言語が無い
・既存の演算やBoostで出来ちゃうから無い？
ネットにソースが散在してると思っていたんですが。。。
248:デフォルトの名無しさん
12/07/03 12:28:02.45
>>247
アプレットがあるならそれをベースにすればいいだろ。
物乞いしたいのなら、スレ違いだってばさ。
249:デフォルトの名無しさん
12/07/03 12:38:35.39
いろんな環境で動作させたいんなら環境依存の少ないJavaのそのライブラリ使えばええやん
250:デフォルトの名無しさん
12/07/03 12:39:59.36
Javaの奴ってこれだろ？
Lee Byron ≫ Else ≫ Mesh ? A Processing Library
URLﾘﾝｸ(www.leebyron.com)
251:デフォルトの名無しさん
12/07/03 12:43:12.80
Voronoi diagram - Wikipedia, the free encyclopedia
URLﾘﾝｸ(en.wikipedia.org)
外部リンクでも辿って探せや
252:230
12/07/03 12:48:19.89
本当に物乞いするだけなら、スレじゃなくてググルするだけだし。
どちらかというと、検索結果があれ？となって、他の人がどういう対応なのか知りたかったのです。
>>248
それは不可能じゃないですが、だから、C++な人の通常の方針が知りたくて。
自分が見つけたリンクは、
Javaは URLﾘﾝｸ(www.ics.kagoshima-u.ac.jp)
その他は URLﾘﾝｸ(gihyo.jp)
といった感じです。
が、上のレスに貼られたリンクに入ってみます。
253:230
12/07/03 13:12:28.17
voronoiで、先ず、ある点の一番近くの点と結ぶのは、全部やる方法もありますし、工夫する方法も分かります。
その次の、あるドロネー辺の２等分垂直線同士の交点座標を取得方法も分かります。
が、しかしドロネー辺が無数にあると、計算時にどれ活かすか難しくないですか？？？
254:230
12/07/03 13:31:00.88
それと、ある点に対して出来上がるvoronoiが何角形かも不明だし、
関係している線分と関係してない線分とか、線分で領域が閉じてるか、
とか、簡単に分かるのかなぁ？
実際の図を描けば分かっても、プログラムだと１次元的に見えますよねぇ。
255:230
12/07/03 13:41:48.29
連投すみません（連投の最後）：
ある点の一番近くの点と結ぶのは全部やる方法、じゃダメですよね。
余分に結ぶと余分に線分が出来て、余分に多角形化しちゃうし。
どうもvoronoiの認識が足りないので、そちらを勉強してみます。
もしくは、高度なポリゴンクラスライブラリを持っていれば簡単に解決なのか？＿？
チラ裏となってきたので、一旦消滅します。レスはずーっと読み続けますが。
256:デフォルトの名無しさん
12/07/03 14:16:40.53
まとめると、「自分で実装する気はないからライブラリ教えろや！」
257:デフォルトの名無しさん
12/07/03 14:21:50.90
ライブラリが存在しないケース
・アルゴリズムの再現自体が不可能
・複雑なプログラムになり相応のコストがかかるため、無料提供が無いが有償提供ならある
・アルゴリズム自体の知名度や有用度が低いため手を付ける者が少なくライブラリ化してない
・あまりにも簡単で単純なアルゴリズムのため、わざわざライブラリにして提供するまでもない
258:デフォルトの名無しさん
12/07/03 14:24:57.60
？
259:230
12/07/03 14:26:39.02
どうも、いきなりボロノイを実装するのではなく、
＞ボロノイ～逐次添加法
＞ボロノイ～再帰二分法
といった手法が定石みたいでつね。
それらでググったら、多少ひっかかってきますたｗ
URLﾘﾝｸ(suuri.ics.kagoshima-u.ac.jp)
URLﾘﾝｸ(www.ics.kagoshima-u.ac.jp)
URLﾘﾝｸ(i-health.u-aizu.ac.jp)
理解して修正できるコンパクトなものにしたいでつ。
260:デフォルトの名無しさん
12/07/03 14:27:20.48
さっきから日本語サイトばかり
261:230
12/07/03 16:27:55.65
英語サイトもみっけ：
URLﾘﾝｸ(www.koders.com)
URLﾘﾝｸ(www.leebyron.com)
URLﾘﾝｸ(www.codeforge.com)
URLﾘﾝｸ(www.geocities.co.jp)
262:デフォルトの名無しさん
12/07/03 16:48:17.86
おまえなんでここにメモってんの？ここにメモる必要ないだろ
263:デフォルトの名無しさん
12/07/03 16:56:47.24
おまえなんでここ監視して余計なこと言ってんの？ここで発言する必要ないだろ
264:デフォルトの名無しさん
12/07/03 17:44:41.21
>>261>>263
失せろゴミ
265:デフォルトの名無しさん
12/07/03 17:48:18.98
（笑）
266:デフォルトの名無しさん
12/07/03 20:49:04.54
空間ってか直方体を8つごとに分けていって
8分木の形にしたデータ構造の,一部の葉だけが選択されていて,それらの葉の接続関係
を求めるってどうすればできますか？
葉に対応する直方体の面同士が接していれば接続しているとしたいのですが
階層がちがうのの扱いがよくわかりません。。。
267:デフォルトの名無しさん
12/07/03 21:00:13.81
？
268:デフォルトの名無しさん
12/07/03 21:04:32.27
点の絶対座標から、その点を含むノードのアドレスを出せるよう、ノードのアドレスを工夫する。
（ここで言うアドレスとは、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:デフォルトの名無しさん
12/07/03 21:19:16.93
>>268
どうもです^o^
270:デフォルトの名無しさん
12/07/03 22:08:59.67
ミスった。
> (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:デフォルトの名無しさん
12/07/03 23:26:29.68
>>255
URLﾘﾝｸ(www.pi6.fernuni-hagen.de)
272:デフォルトの名無しさん
12/07/11 03:06:25.48
質問させてください
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:デフォルトの名無しさん
12/07/11 10:26:48.61
いやです
274:デフォルトの名無しさん
12/07/11 10:42:54.09
>>272
ggrks
275:デフォルトの名無しさん
12/07/11 11:57:07.67
雑多な質問スレっていろいろあるのに
何故このスレに誘導されたのだろうか
276:デフォルトの名無しさん
12/07/11 12:12:31.31
>>272
ランダウの記号 - Wikipedia
URLﾘﾝｸ(ja.wikipedia.org)
277:デフォルトの名無しさん
12/07/12 04:03:56.85
>>272
オーダー記号って普通は等号使ってn=O(n)とか書くんじゃないかな
それはともかく数字があれば理解できるって神だな。
関数の極限の話だし。
278:デフォルトの名無しさん
12/07/12 07:19:45.35
ヒープソートでなぜ再帰？～日本語版ウィキペディアの問題点と最強最速のヒープソート～
URLﾘﾝｸ(www.dreamhope.net)
279:デフォルトの名無しさん
12/07/12 08:54:36.87
>>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:デフォルトの名無しさん
12/07/12 10:12:28.23
スタックオーバーフローは最近はSEGVで落ちるんじゃね？
ウィキペディアの記事も微妙だが、そのウェブページもいろいろと頭悪いという
ことについては同意。
281:デフォルトの名無しさん
12/07/12 10:21:47.95
>>280
Linuxは拡張しきれないスタックを要求した時はSEGVで落ちるけど
Windowsは黙って変な結果を出して終了するか、暴走するかどちらか
282:デフォルトの名無しさん
12/07/12 12:08:48.86
ランダウの記号って名前があったのか
知らなかった
283:デフォルトの名無しさん
12/07/12 12:51:41.81
Mac も
> 黙って変な結果を出して終了するか、暴走するか
284:デフォルトの名無しさん
12/07/12 13:50:54.97
VCのデバッグならスタックオーバーフローを検出して止まるので
リンカのオプションからスタックサイズを改めて指定しなおす事になる
この時に一度ビルドをクリーンしないと単にリンクし直すだけでは
スタックオーバーフローエラーは止まらないようだ
285:デフォルトの名無しさん
12/07/12 20:40:52.04
＞そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。
・・・ナゼ
286:デフォルトの名無しさん
12/07/12 21:20:43.48
自己顕示欲の強そうな人だね
他の記事も読んだけど首を傾げすぎて首が疲れた
データベースは毎回自分で実装した方がいいらしいよ 目から鱗だわ
287:デフォルトの名無しさん
12/07/13 16:46:26.64
最適化を語るのにオプションを明示しないとか、
データ量を語るのにオプションを明示しないとか、
処理速度を語るのに環境を明示しないとか、
10～20年くらい前から知識が更新されていないんじゃないだろうか。
288:デフォルトの名無しさん
12/07/13 16:47:09.23
>>285
批評に晒されたくないチキンハートなんでしょ。
289:デフォルトの名無しさん
12/07/13 19:20:15.32
出回ってる書籍が古いものばかりだからね
図書館で借りようものなら１０年～２０年昔の本だって当たり前のように陳列されてる
290:デフォルトの名無しさん
12/07/17 20:23:27.35
①区間スケジューリング問題＜＝ｐ 点カバー問題
②独立集合問題＜＝ｐ 区間スケジューリング問題
この２つについて
(i)Yes (ii)No (iii)「これが解ければP=NP問題が解決できるので不明」
のいずれかで答え、その簡単な説明も与えよ。
という問題の答えを教えて下さい
291:デフォルトの名無しさん
12/07/18 01:05:55.70
C/C++の宿題片付けます 158代目
ｽﾚﾘﾝｸ(tech板)
292:デフォルトの名無しさん
12/07/18 01:26:27.60
すっげえ宿題でるんだな
俺が通ってた大学での「データ構造とアルゴリズム」ってまんまの名前の授業あったけど
宿題に出たのがせいぜい一般的なソートアルゴリズムいくつかををjavascriptで書けとかそういうレベルだったよ
293:デフォルトの名無しさん
12/07/18 04:41:54.35
なんでjavascriptなの？なんかその大学に興味があるんだけど
今時は大学でjavascriptでアルゴリズム書かせるのか
294:デフォルトの名無しさん
12/07/18 10:28:38.16
schemeの代替
295:デフォルトの名無しさん
12/07/18 11:29:46.28
web限定用語で教育するってのはちょっとナンセンスかと
296:デフォルトの名無しさん
12/07/18 11:31:53.61
「web限定用語」ってすごい表現だなw
プログラミング言語を「用語」って言うのはどこのマヌケ業界だろう？
297:デフォルトの名無しさん
12/07/18 11:39:08.99
web限定言語で教育するって凄い大学だな
298:デフォルトの名無しさん
12/07/18 11:41:14.74
逆にCとかJavaみたいな一般のプログラマにとって中途半端に使えない、
実用的でない言語なんて教えたところで意味無いでしょ。
299:デフォルトの名無しさん
12/07/18 11:49:22.80
じゃあpythonでいいだろ
少なくともアルゴリズムの授業でjavascriptってのは学生がかわいそうだ
300:デフォルトの名無しさん
12/07/18 11:53:38.65
>>298
いや相手は情報系の学生だぞ？
CもJavaもダメな奴がどうやって情報科学を学ぶわけ
301:デフォルトの名無しさん
12/07/18 11:54:58.55
>>298
世界が狭すぎ
あなたがどういうバックボーンなのか知りたいわ
302:デフォルトの名無しさん
12/07/18 12:02:34.74
情報系っていうのはプログラマ養成施設じゃないよ。
専門学校か他の工学系と勘違いしてないか？
303:デフォルトの名無しさん
12/07/18 12:15:03.55
情報系でCもJavaも教えない大学があるのか？
それまともな大学じゃないだろ
そんなカリキュラムが存在するならマジで教えて欲しい 聞いたこと無いから
プログラマ養成機関じゃないからこそCで本質に切り込むんじゃないの
専門学校みたいなプログラマ養成機関こそがPHPとかJavascriptを教えるんでしょ
まあそれはさておき、アルゴリズムの概念を教えるのにJavascriptを使う大学はおかしいよ絶対に
それも否定する？
304:デフォルトの名無しさん
12/07/18 12:18:38.42
まともな大学生ならCは自習で既に学んでるから大学ではいちいち教えない
305:デフォルトの名無しさん
12/07/18 12:27:09.76
アルゴリズムの本質は言語によって変わらない
306:デフォルトの名無しさん
12/07/18 12:31:27.01
「アルゴリズムの本質は言語によって変わらない」
それはわかるけどさ、だからといって
「アルゴリズムの本質は言語によって変わらないからJavascriptで教えます」
はおかしいでしょう 普通の感覚じゃ考えられない
言語実装に関係のない本質を教えるんであれば、なおのこともっと汎用的な普遍的な言語でやるべきじゃない
307:デフォルトの名無しさん
12/07/18 12:34:34.41
そうかい
308:デフォルトの名無しさん
12/07/18 12:36:18.55
その感覚はわからなくもないが感覚じゃなく理屈で説明してくれ。
309:デフォルトの名無しさん
12/07/18 12:42:09.35
アルゴリズムの授業だからJavascriptなんじゃなくて
別の理由で決まったんだろ
310:デフォルトの名無しさん
12/07/18 12:44:52.14
10年前とは違うからな。javascriptを取り巻く環境は随分改善した。
ブラウザ間の互換性であるとかデバッグ環境はすでに十分な領域に達している。
311:デフォルトの名無しさん
12/07/18 13:00:17.42
>>305
8-QueenをCOBOLで書くようにという宿題がでるらしいと聞いたら
その授業は取らない。
312:デフォルトの名無しさん
12/07/18 13:32:43.00
そうかい
313:デフォルトの名無しさん
12/07/18 14:07:00.66
8-Queenとアルゴリズム全般、COBOLとJavascriptじゃ違いすぎるな
314:デフォルトの名無しさん
12/07/18 14:36:01.76
いい加減スレ違い
315:デフォルトの名無しさん
12/07/18 14:41:23.22
そうかい
316:デフォルトの名無しさん
12/07/18 14:59:25.90
JavaScriptをウェブ専用とか思ってるバカがプログラマのわけないだろw
317:デフォルトの名無しさん
12/07/18 15:00:37.58
そうかい
318:デフォルトの名無しさん
12/07/18 17:11:07.05
ECMAScript は Web 専用じゃないけど Javascript は Web 専用とか、そういう揚げ足取りなのかもね。
319:デフォルトの名無しさん
12/07/18 17:44:37.90
言語は手段でしかない
320:デフォルトの名無しさん
12/07/18 18:22:28.47
javascriptはクロージャを学ぶのに悪くない
321:デフォルトの名無しさん
12/07/18 18:57:27.05
>>319
このスレの住人が口にすると迫力あるな。
322:デフォルトの名無しさん
12/07/18 19:27:20.07
そうかい
323:デフォルトの名無しさん
12/07/18 20:51:20.96
VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。
324:292
12/07/18 20:56:44.84
誰のＰＣにでも入ってて使えるプログラム言語だからという理由でjavascriptを指定してたよ
別にHTMLファイルにするとかじゃなくて
アルゴリズムを再現したコードをメールに添付して送信するみたいな宿題だった
ちなみに情報が専門の学科は無い大学だったのでそういうことに
325:292
12/07/18 21:04:23.79
ちなみな自分語りになるが
学科名的には電子情報工学科となってて情報系の授業を期待して入学したものの
（ちゃんと調べずに願書出した俺が悪いのだが）
情報とは名ばかりで情報系の授業はほとんど開講されず
電子系、特に半導体系の授業ばかりしかなかった
その大学わが母校はもう存在してないけどね
326:デフォルトの名無しさん
12/07/18 21:13:34.30
本当ただの自分語りだな
327:デフォルトの名無しさん
12/07/18 21:21:22.30
寂しい奴なんだろう。
328:デフォルトの名無しさん
12/07/18 23:16:38.10
>その大学わが母校はもう存在してないけどね
津波で流されたのね
329:デフォルトの名無しさん
12/07/19 01:35:32.86
つまり本格的な情報科学系の授業では無かったという事の証左だよな
まあ非情報系の学生だったらブラウザで誰でも実行環境が整うからあえてJavascriptでやるっていう意味もわかる気がする
330:デフォルトの名無しさん
12/07/19 04:30:09.03
VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。
331:デフォルトの名無しさん
12/07/19 07:32:51.17
なんでこんな頭の悪いのがこのスレにいるんだ？
332:デフォルトの名無しさん
12/07/19 09:04:49.51
若者の 2ch 離れが進んでいるな
333:デフォルトの名無しさん
12/07/19 19:06:58.62
2点が与えられたときその2点を結ぶ単純な経路（同じ頂点を通らない経路）
が2つ以上存在するかを判定するアルゴリズムと計算量を述べよ。
深さ優先探索とかでしょうか？
334:デフォルトの名無しさん
12/07/19 19:12:15.02
宿題は宿題スレへ
335:デフォルトの名無しさん
12/07/19 19:36:47.50
失礼しました
336:デフォルトの名無しさん
12/07/19 21:33:34.33
>>331
どっちのこと？
337:デフォルトの名無しさん
12/07/19 21:44:47.18
おそらく自問自答だろう
338:デフォルトの名無しさん
12/07/20 16:42:44.97
二分探索木の平均高さが O(logN) の証明ってどういう風にやるんでしょうか？
アルゴリズムイントロダクションに書いてあるらしいのですが見当たりません。どのあたりでしょうか？
339:デフォルトの名無しさん
12/07/20 16:53:14.03
>>338
2分探索の構造がわかれば少し考えればわかることだよ
340:デフォルトの名無しさん
12/07/20 16:56:17.57
>>338
木 T が平衡なら、そのまま height(N) = 1 + height(N/2) で O(logN)でしょ。分割統治法
341:デフォルトの名無しさん
12/07/20 17:29:31.19
手元の本にありましたのでもういいです。
お騒がせしました
342:デフォルトの名無しさん
12/07/20 19:17:26.17
宿題は宿題スレへ
343:デフォルトの名無しさん
12/07/21 03:01:26.56
3つのくっついてる円にこれまたくっついて囲まれてる円の半径を
求めるアルゴリズムってどうすればいい？
344:デフォルトの名無しさん
12/07/21 03:14:49.30
３つの円はどういうくっつき方？
３つの円の半径はばらばら？
○○○
○
○○
345:デフォルトの名無しさん
12/07/21 03:24:10.91
宿題は宿題スレへ
URLﾘﾝｸ(blogs.yahoo.co.jp)
346:デフォルトの名無しさん
12/07/21 03:24:54.06
343は外接・内接という言葉も知らなそうな雰囲気で困る。
347:デフォルトの名無しさん
12/07/21 03:28:43.57
>>344
くっつき方は下の方
円の半径はバラバラ
348:デフォルトの名無しさん
12/07/21 03:47:28.98
２本（３本）の双曲線の交点が共通接円の中心か
349:デフォルトの名無しさん
12/07/21 14:31:42.96
互いに接する３つの円 に外接する円の半径の求め方？
350:デフォルトの名無しさん
12/07/21 14:32:39.99
３つの円すべてと接する外接円は無理じゃね
351:デフォルトの名無しさん
12/07/21 14:36:32.23
デカルトの円定理
URLﾘﾝｸ(aozoragakuen.sakura.ne.jp)
352:デフォルトの名無しさん
12/07/21 14:36:40.22
にしてもスレチ。
353:デフォルトの名無しさん
12/07/21 14:55:54.21
アルゴリズムでも何でもないなコレ
354:デフォルトの名無しさん
12/07/22 10:15:52.04
プリムのアルゴリズムのヒープ版って
(E+V) log (E) ≒ Elog(E)ってあるけど (E+E) log (E) ≒Elog(E) が正しいと思う
挿入か削除のどっちも Elog(E) でしょ 最悪全枝を一回ずつ挿入と削除する必要があるんだから
355:デフォルトの名無しさん
12/07/25 05:54:32.42
王様は王様でも頭が三つある王様はな～んだ
356:デフォルトの名無しさん
12/07/25 06:04:38.43
三頭王
357:デフォルトの名無しさん
12/07/25 17:58:22.97
キングギドラ
358: ◆VD2btbRbPs
12/07/25 21:41:00.81
大学の課題で二分探索木の高さを調べる実験とその結果を調べる実験が出たのですが
どうしたらいいですか
359:デフォルトの名無しさん
12/07/25 21:54:46.35
そのようにプログラムを作って結果を表示すればいいのでは？
360:デフォルトの名無しさん
12/07/26 16:24:57.70
宿題は宿題スレへ
361:デフォルトの名無しさん
12/07/26 21:29:42.06
ほんとこういう質問するガキがムカつく
どうすればいいですか？って何だよ
そんな曖昧な質問で答えられると思ってんのかカスが
どこの底辺大学だか知らないが学費が無駄
362:デフォルトの名無しさん
12/07/26 22:10:01.46
>>358
擬似乱数から最大の低周波成分を除くアルゴリズムを考案する。最大の低周波成分を除く操作を
繰り返すごとに２分探索木の高さが次第に平坦化することを実験・観察する。
363:デフォルトの名無しさん
12/07/26 22:23:02.61
教授に不正してる奴がいたと報告しとく
364:デフォルトの名無しさん
12/07/26 22:36:52.61
乱数が独立なら、Huffman木を作るといいよ！
365:デフォルトの名無しさん
12/07/27 00:41:56.00
ハッシュのチェイン法の同一エントリのチェインの長さに制限があるやつはなんていうんだっけ？
366:デフォルトの名無しさん
12/07/27 00:47:53.60
特にない
367:デフォルトの名無しさん
12/07/27 01:03:18.89
半開きハッシュと名付けた
368:デフォルトの名無しさん
12/07/27 01:38:15.37
こないだから宿題貼り付ける奴がちらほらいるが
そのどれも分からなかった俺は才能が無さ過ぎた
369:デフォルトの名無しさん
12/07/27 08:00:24.64
>>361
黙れバカw
空気読んで答えやがれ
370:デフォルトの名無しさん
12/07/27 08:13:45.67
↑お前が馬鹿
371:デフォルトの名無しさん
12/07/27 09:41:12.30
馬鹿には無理
372:デフォルトの名無しさん
12/07/27 10:18:48.93
>>370
>>371
バカはお前ら
お前らのパッパラパーなアルゴリズムでさっさと俺様を笑わせやがれ
373:デフォルトの名無しさん
12/07/27 11:49:22.94
馬鹿には無理
374:デフォルトの名無しさん
12/07/27 12:10:13.43
>>373
お前には無理と言うことかw
375:デフォルトの名無しさん
12/07/27 19:08:10.29
>>374
お前が馬鹿
376:デフォルトの名無しさん
12/07/27 19:54:35.27
＿＿＿＿
／∵∴∵∴＼
/∵∴∵∴∵∴＼
/∵∴∴,（・）（・）∴|
|∵∵／ ○ ＼|
|∵ / 三 | 三 | ／￣￣￣￣￣
|∵ | ＿_|＿_ | ＜ うるせー馬鹿！
＼| ＼＿/ ／ ＼＿＿＿＿＿
＼＿＿＿_／
377:デフォルトの名無しさん
12/07/27 20:23:22.78
どーでもいい。
378:記憶喪失した男 忍法帖【Lv=9,xxxP】
12/07/28 07:59:18.69 BE:3079593959-2BP(3)
入力された内容は次のとおりです。
■件名： 日本のロボットトレーディングサイト「カブロボ」について
■ご意見・ご感想：
ロボットトレーディング、あるいはアルゴリズム取引トレーダーについて、少しは知識を得ました。その現状について知ったところ、やはり憂慮すべき事態だったため、意見申し上げます。
「カブロボ」というサイトを知りました。そのサイトについての意見です。政府として、このようなサイトを支援していただきたく思います。
アルゴリズム取引トレーダーとしては、株だけでなく、債券、為替取引にも当然対応するべきであります。
また、株、債券、為替取引は、現実に存在する二百か国以上の国や地域を網羅する必要があります。
それが賢いアルゴリズム取引トレーダーのするべきプログラムであり、
たった三百銘柄の仮想取引では、日本の投資家を育てるのに不適切だと思われます。海外銘柄を扱わないアルゴリズム取引トレーダーに魅力を感じません。
扱う銘柄を、全世界の株、債券、為替をすべて網羅する上級者向けのカブロボを立ち上げることを希望いたします。
379:デフォルトの名無しさん
12/07/28 10:23:42.25
>>375
バカw
380:デフォルトの名無しさん
12/07/28 11:39:47.47
>>324
その学科何年か前は違う名前じゃなかった？
381:デフォルトの名無しさん
12/07/28 14:26:03.68
>>378
当事者が遊びで作ってるものに政府が金なんか出す訳ないだろ
382:デフォルトの名無しさん
12/07/28 21:18:50.51
ぷよぷよのAIを作っているんですが窒息死します
どうすればいいですか
383:デフォルトの名無しさん
12/07/28 22:12:51.40
ぷよぷよで強いAIってどうすんの？
ｽﾚﾘﾝｸ(tech板)
384:デフォルトの名無しさん
12/07/29 10:05:48.14
>>383
こんなスレあったんですか
ありです
385:デフォルトの名無しさん
12/07/31 08:19:02.42
ﾌﾟｯ
386:デフォルトの名無しさん
12/07/31 09:24:11.53
ﾖｯ
387:デフォルトの名無しさん
12/07/31 09:52:41.53
ﾌﾟｯ
388:デフォルトの名無しさん
12/07/31 21:35:14.84
ﾖｯ
389: 【大吉】
12/08/01 08:41:13.81
O(N)
390:デフォルトの名無しさん
12/08/02 10:09:55.05
ｵﾅﾗﾌﾟｰ
391:デフォルトの名無しさん
12/08/02 20:47:04.14
ガベージ・イン／ガベージ・アウト：
善き人々が悪しきプログラムに手を染める時
URLﾘﾝｸ(practical-scheme.net)
392:デフォルトの名無しさん
12/08/03 20:45:11.38
ハッシュだけどチェイン法＞開番地法なんだよね？でなければ溢れを気にする必要はないからね
ハッシュのチェインの長さに制限があるやつの削除、参照の計算量の解析ってどっかにない？
393:デフォルトの名無しさん
12/08/03 20:56:13.76
「チェイン法＞開番地法」
この意味は何？
394:デフォルトの名無しさん
12/08/03 21:49:02.14
参照、追加、削除の計算量です
395:デフォルトの名無しさん
12/08/03 22:12:44.83
A>B はAのほうが良い、ってことで
396:デフォルトの名無しさん
12/08/04 18:35:46.31
>>392
> 長さに制限があるやつ
って何よ。
ハッシュ値が衝突した要素を格納するためのコンテナの計算量でいいんじゃないの？
397:デフォルトの名無しさん
12/08/05 17:00:36.26
ハッシュ法って、均したらまともな実装ならO(1)にならにゃいかんのでは？
398:1/4
12/08/06 18:50:54.98
アルゴリズム考えてもらえませんか。
恥ずかしながら、一応自分の考えたのも載せます。
ただ、絶対もっとスマートな解法があると思うのでよろしくお願いします。
ちなみに言語は 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:2/4
12/08/06 18:52:06.84
---続き---
抽象的に書くとこうなりますか。
$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:3/4
12/08/06 18:53:22.57
---続き---
例えばそれを実装した関数を linearize とした場合、
$newData = linearize( $data );
の結果は、
array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);
でなくてはなりません。
401:4/4
12/08/06 18:56:51.88
------続き------
こちらが自分が考えた関数です
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:5/4
12/08/06 18:58:01.19
------続き------
すいません、予定より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:デフォルトの名無しさん
12/08/06 20:04:16.15
$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:デフォルトの名無しさん
12/08/06 20:09:14.78
理屈がよくわからん
405:デフォルトの名無しさん
12/08/06 20:14:28.31
できた！
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:デフォルトの名無しさん
12/08/06 20:15:48.26
でたらめを教える悪い例
407:デフォルトの名無しさん
12/08/06 20:20:34.70
DPでいけそう
Viterbトレリスを作って一発
408:デフォルトの名無しさん
12/08/06 20:23:59.40
ならばこうか！
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:デフォルトの名無しさん
12/08/06 20:25:08.27
動かないコードなど無意味
410:デフォルトの名無しさん
12/08/06 20:28:20.86
うおりゃ！スペルミス直したぞ！
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:デフォルトの名無しさん
12/08/06 20:30:11.37
動かないぞ
412:デフォルトの名無しさん
12/08/06 20:31:20.11
括弧が一つ多かった！直したぞ！
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:5/4
12/08/06 22:54:42.75
>>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:398
12/08/06 22:55:22.08
Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)
415:398
12/08/06 22:56:52.95
Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)
416:398
12/08/06 23:11:31.65
別のデータを用いて模式図を書くとこうなります
( 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:デフォルトの名無しさん
12/08/06 23:49:58.47
#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:398
12/08/07 00:47:35.30
>>417
m(__)m
もう、ほんとうに感謝感謝感謝です。
ありがとうございます。
しかもそのまんまコピペでOKでした。
>>417 さん以外の皆様もありがとうございました。
どこか別の場所で恩返しできるといいです。
419:398
12/08/07 00:53:50.40
あぁ、そうかぁ、
$result に格納するタイミングは
datum[0] > $max
のときとループを抜けた最後だけでいいわけか・・・
すごくなるほど。
420:398
12/08/07 01:03:25.12
あと、元のデータが ( 開始位置, 幅 ) だったので
それをループの中でいったん終了位置を $max として求めているのですね。
ということは、元のデータを ( 開始位置, 終了位置 ) として同じコストで作成できるとするならば、
それを採択した方がより良いアルゴリズムになるのですね。
元データの取得方法を再検討してみます。m(__)m
421:デフォルトの名無しさん
12/08/07 02:43:10.51
宿題は宿題スレって約束忘れちゃったのかおまえら
422:デフォルトの名無しさん
12/08/09 18:31:48.66
ヒープソート、書き換わってるなw
423:デフォルトの名無しさん
12/08/10 07:22:34.38
ホントだ
424:デフォルトの名無しさん
12/08/14 13:57:01.43
あらゆる状況や環境を無視して質問するんだけど
STXとETXで囲まれたバイト列を取得 というとき、
<STX>unko<STX>chinko<ETX>
というならびになっちゃってるときは chinko オンリーが正解か
unko<STX>chinko が正解か、どっちがセオリーかなぁ
425:デフォルトの名無しさん
12/08/14 14:05:59.01
最長一致にするか最短一致にするかは
セオリーというより定義の問題だ
426:デフォルトの名無しさん
12/08/14 14:06:25.67
後者。
/*foo/*bar*/ だってコメントアウトされるのは foo/*bar でしょう。
427:デフォルトの名無しさん
12/08/14 14:20:48.63
>>426
そっちの方が作るのも楽なんだけどさ
なんでわざわざ囲ってんのか という根源的なとこを思うと
chinkoオンリーが正解な気がするんだよな
428:デフォルトの名無しさん
12/08/14 15:07:33.07
>>427
プロトコル定義次第。
・<stx>で始まり、<etx>で終わるまで全てがデータ(unko<stx>chinko)
・<stx>で始まり、<etx>以外の制御コードを含まない区間がデータ(chinko)
・<stx>で始まり、<etx>以外の制御コードを無視した区間がデータ(unkochinko)
・<stx>で始まり、<etx>で終わるまでがデータだからネストを認め、内側から有効とする(chinko)(unkoはペンディング)
・<stx>で始まり、<etx>以外の制御コードが出現したらその後のデータは無効(データなし)
ちょっと考えただけでもこれだけバリエーションが作れる。
要は、エラーに対する強度の問題。
429:デフォルトの名無しさん
12/08/14 15:10:09.72
>>427
<stx>が出現したら出力インデックスを初期化するだけだから、作る手間は殆ど変わらないだろ。
430:デフォルトの名無しさん
12/08/14 15:32:23.36
>>428
STXとETXに挟まれたもの という定義なんか作った理由って
開始と終了を検知したいということなんだから、
STXまたはETXの見逃しを恐れるべきですね
ということは、STXのあとETXが来ないでSTXきちゃったのは
ETXを読み飛ばしちゃったと思った方がいいんだよな、きっと
つまり、とりあえずchinkoのみを採用すべきとすべきかなぁ
431:デフォルトの名無しさん
12/08/14 16:03:01.12
>>430
再入可能かどうかが分からないとなんとも言えないだろ
432:デフォルトの名無しさん
12/08/14 16:13:36.40
そうか。 再入可能かどうかがキモになるのか。
433:デフォルトの名無しさん
12/08/20 12:52:16.26
AVL木の回転って適当すぎない？
別に回転じゃないじゃん。
ただ引き上げてるだけで、入れ替えたりしてる時点で
回転ではないだろ。
434:デフォルトの名無しさん
12/08/20 17:32:15.47
死ねゴミ共がw
435:デフォルトの名無しさん
12/08/20 20:27:00.20
>>433
subtreeのrotationじゃなくて、nodeのrotationなんで。
「入れ替え」くらいが適切な訳だったという感じでしょうかぁ↓
436:デフォルトの名無しさん
12/08/21 09:13:13.56
バカばっかw
437:デフォルトの名無しさん
12/08/21 09:44:31.25
>>435
いいね！
438:デフォルトの名無しさん
12/08/22 00:06:18.81
お知恵をお貸しください。
xy平面上にランダムに配置された複数個の点があったとき、
それらを線で結ぶとして、結んだ結果が網の目のように見える
ようなアルゴリズムってありますでしょうか。
完全に見た目だけが目的なので自分でも要件が絞り込めて
いないのですが、網の目のように見えるための要件は
おそらく次のようなものでしょう。
・全ての点が2個以上の他の点と結ばれている
・線同士が交差しない
・近い点同士が結ばれていて、遠い点同士は結ばれない
・線で囲まれた図形は三角形ないし四角形を構成し、五角形以上にはならない
よろしくお願いいたします。
439:デフォルトの名無しさん
12/08/22 00:11:11.92
ドロネー図でggr
440:デフォルトの名無しさん
12/08/22 23:00:26.94
>439
ありがとうございます。
URLﾘﾝｸ(tercel-sakuragaoka.blogspot.jp)
↑ここを参考にして実装を進めようと思うのですが、この方法だと、
一度完成したドロネー図から点を削除して線を引きなおすには、
再度（その点を除いた点群を入力として）ゼロから作図しなおす
しか無いのでしょうか？
441:デフォルトの名無しさん
12/08/30 18:01:25.35
Ｂ木がよく分かりません。誰か簡単に説明してくれませんか？
442:デフォルトの名無しさん
12/08/30 18:23:37.01
>>441
B木は多分岐の平衡木。
ノードは最大M個のサブノードとM-1個の値を保持する。
ノードの値がM-1個を超えるとノードの分割が行われる。
443:デフォルトの名無しさん
12/08/31 00:00:52.49
2分平衡木の存在意義がゼロに
444:デフォルトの名無しさん
12/08/31 20:16:21.92
ゼロどころではない。もはやマイナスだ。
445:441
12/08/31 20:35:10.27
>442
ありがとうございます。
プログラム文がきわめて長いので、使いこなせません…。
446:デフォルトの名無しさん
12/09/01 03:33:46.99
>>445
プログラム使うだけだったら実装の細部まで理解する必要ないっしょ。
Addメソッドを呼んだらが値を追加できてGetメソッドを呼んだら値を
取得できるというようなことさえわかってればじゅうぶんっしょ。
447:445
12/09/01 23:51:43.84
>446
そうですかねえ。確かに文が400行以上あるので(コメントも含めて)、理解は無理っぽいですねえ。
二度目ですが、シェルソートが挿入ソートより速くなる理由を誰か教えて頂けませんか？
448:デフォルトの名無しさん
12/09/02 00:27:54.32
ランダムに並んだデータを挿入していくと
比較回数の期待値が挿入１回に対しソート済みデータの半分になるけど
先頭に近そうなデータから挿入していけば
比較は後ろの方の１，２回だけとなることが期待できるってことでは
449:デフォルトの名無しさん
12/09/02 00:28:30.47
１，２回だけ→ほとんどが１，２回くらい
450:デフォルトの名無しさん
12/09/02 00:43:09.47
>>447
語尾が腹立つから教えてあげない
451:447
12/09/02 01:05:24.33
>448-449
ありがとうございます。けれどやっぱり納得できないというか…。最終ソートの前で既に結構比較・交換にコストがかかってる気がして。
>450
何でですかあ？そんな事言わないで下さいよお。
452:デフォルトの名無しさん
12/09/02 06:09:50.86
>>451
あんまりふざけたこといってるとぶちぎれるゾ（ゝω・）vｷｬﾋﾟ
453:451
12/09/02 23:53:28.52
>452
怒ったらダメですう。貴方に足りないのはＣａですよお。(特に深い意味はない)
454:デフォルトの名無しさん
12/09/03 05:10:27.93
つまんね
455:デフォルトの名無しさん
12/09/03 06:29:18.19
例えば挿入ソートだと比較回数は期待値でだいたいこんな感じだろう
右から+の箇所で比較していって*に収まるイメージ(平均なので真ん中)
-----------------------------------*+++++++++++++++++++++++++++++++++++
でもシェルソートのごとく予め4つのグループに分けると比較回数がガクッと減らせる
-----------------------------------*---+---+---+---+---+---+---+---+---
さらに前段階で13のグループに分ければ比較回数が格段に減る
-----------------------------------*------------+------------+---------
いくら前段階というプロセス数が増えるとはいえ、比較や交換回数が小さいわりに
好位置へデータを移動させておくことができるから、全体としてみれば
効率が良くなるんだろう
456:453
12/09/06 16:51:56.41
>455
しかし何故そうなるのかが分かりません。
今ヒープソートを勉強してますが、これはさらに分かりません。
457:デフォルトの名無しさん
12/09/06 18:32:25.30
>>456
挿入ソートでは要素数が多くなると遠くまでテケテケと要素を1個ずつ移動せにゃならんから
超大変。シェルソートでは要素数が増えても離れた要素を交換することで遠くへ移動するときの
コストが減らせちゃうわけ。ゆえに要素数が増えるほどシェルソートが挿入ソートより
速くなるはずよ。
ヒープソートは2分木作っちゃうやつだろ、わかるだろ。
458:デフォルトの名無しさん
12/09/08 19:22:54.12
基数ソートって分かりやすいしすばらしいですね。
459:デフォルトの名無しさん
12/09/10 20:53:39.37
アルゴリズムとデータ構造の質問なんですけど、ここでいいですか？
１．2次元以上で、無限に広がるユークリッド空間があります。
２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
３．ここより先では、砂粒を追加しません。
４．空間上の任意の座標を選びます。
５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色？
安定じゃなくてもokです。
こういう状況で、良い検索アルゴリズムってありませんか？
460:デフォルトの名無しさん
12/09/10 21:04:04.91
> 安定じゃなくてもok
って、等距離に赤も黒もあった場合は、返す値は赤でも黒でも良いと言いたいのか？
461:デフォルトの名無しさん
12/09/10 21:07:23.58
1ビットごとに次元を変えていくやり方なら地図サービスとかで使われている
462:デフォルトの名無しさん
12/09/10 21:08:15.28
>>461
kwsk
463:デフォルトの名無しさん
12/09/10 21:25:53.08
>>460
あ、その通りです。安定ソートっぽい意味でした。すみません。
等距離に、または同じ座標に、赤と黒があるときは、
答えは赤でも黒でも良い、検索のたびに答えが変わっても良い、
ってことです。
あと、例えば等距離に黒が複数ある場合、答えは「黒」と返すだけでokです。
アルゴリズムがどの座標の「黒」を指したのか、
それはアルゴリズム利用者に知らせる必要はないです。
>>461
1ビットごとに？？
すみません、ちょっと想像がつきません…。
どんな仕組みなんでしょうか？
464:デフォルトの名無しさん
12/09/10 22:52:42.26
>>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:デフォルトの名無しさん
12/09/10 22:58:35.49
>>464
で？ その64ビット整数値をどうする気だよ？
466:デフォルトの名無しさん
12/09/10 23:01:13.24
砂粒座標データはどう整理された状況で提供されるのかが気になる
あるいは事前にデータを整えていいのか否かも
467:デフォルトの名無しさん
12/09/10 23:06:48.73
>>465
ソートしておけば、upper_bound lower_boundである程度漠然とした領域が拾えるだろ。
全座標の重さが平等でないと使えないやり方だけどな。
そういう想定を置けないなら諦めてR-Tree書けだな。
468:デフォルトの名無しさん
12/09/10 23:54:10.30
>>459
最近傍探索
URLﾘﾝｸ(ja.wikipedia.org)
2を一度だけ行い4を繰り返すのなら
3で同色の砂に囲まれている砂を取り除く方が効率が良いです。