06/03/07 23:25:31
アルゴリズムとデータ構造？
3:デフォルトの名無しさん
06/03/08 00:12:31
アルゴリズムは、ここのサイトがくわしくて参考になる
URLﾘﾝｸ(sidhes.hp.infoseek.co.jp)
4:デフォルトの名無しさん
06/03/08 00:18:32
クヌース先生著の聖書か？
5:デフォルトの名無しさん
06/03/08 00:21:06
はよアルゴリズムについて語れ>>1
6:デフォルトの名無しさん
06/03/08 00:36:20
よし、じゃあまずものすごいかっきてきなアルゴリズムだ。
x = x ^ y;
y = x ^ y;
x = x ^ y;
これで x と y の値がいれかわるのだ！すごい
7:デフォルトの名無しさん
06/03/08 00:39:53
>>6
URLﾘﾝｸ(www.dd.iij4u.or.jp)
8:デフォルトの名無しさん
06/03/08 00:48:55
>>6
これが真に役立つ場面ってなかなかないんだよねぇ。
俺がいままでやった中ではフィボナッチ数列を求めるプログラムぐらい。
もっともそのまんまの形じゃなくて
x = x +y;
y = x -y;
x = x -y;
こんな形をベースにして。ちなみにそのフィボナッチ数列を求めるプログラムはこんな感じ。
int x = 1;
int y = 0;
for(int i = 0; i < 10; ++i) {
printf("%d\n", x);
x = x +y;
y = x -y;
//x = x -y; この二つの行は相殺できるのでコメントアウト
//x = x +y;
}
9:デフォルトの名無しさん
06/03/08 01:04:17
さっき、国会でやった小泉兄貴凄かったです！ガチムチの嘉朗兄貴がイット連呼で
インパクにぶちこまれ首振ってました。俺も掴まされてｶﾞｾﾈﾀ食らい無様に
醜態さらしました。懲罰動議出されたときは一瞬引いたけど、兄貴の「いやなら
辞めていいんだぜ！」の一言で覚悟決め、生まれて初めて謝りました。そ
の後、幹事長・党首も晒しあげられてビンビンの冷や汗、思いっきり謝り派手に脳無し
ﾀｹﾍﾞの顔に飛ばしました。スッゲー男らしく気持ちよかったです。また行くとき
カキコして下さい！帰ってからＮＨＫのニュース見て、また感じまくってます！
10:デフォルトの名無しさん
06/03/08 02:01:06
>>8
似たようなのでユークリッドの互除方が好き
11:デフォルトの名無しさん
06/03/08 02:56:08
ネタすれの乱立ｳｻﾞｽ
12:デフォルトの名無しさん
06/03/08 05:46:38
Introduction to Algorithmsを解説してくれ……とは期待しないが、
解説してるどっかの大学のオンライン講義資料知りませんか。
13:デフォルトの名無しさん
06/03/10 15:24:31
遺伝的アルゴリズムや免疫アルゴリズムなどいろいろありますが
とっておきのを思い付きました。
「検便アルゴリズム」です。
みんなで熱く語り合いませんか。
14:デフォルトの名無しさん
06/03/10 15:27:53
quick sortで最悪のケースを避けるために
最初に粗くshell sortしておくと速くならんかな。
細かい部分はinsertion sortして。
15:デフォルトの名無しさん
06/03/10 15:39:10
>>14
marge sort使えって
16:デフォルトの名無しさん
06/03/10 15:39:46
margeじゃなくて
mergeだって
17:デフォルトの名無しさん
06/03/10 17:42:45
アルゴリズム中毒
略してアル中
18:デフォルトの名無しさん
06/03/10 17:45:53
>>17
おまい、それを言いたいためだけにこのスレたてたんか？！
19:デフォルトの名無しさん
06/03/10 18:00:17
>>13
おまいから、語ってみろよ
それはそうと、自己組織化のアルゴリズム教えてくれ
20:デフォルトの名無しさん
06/03/10 18:10:41
見つけたデータを配列の先頭に移す。
ただこれだけだ。
21:デフォルトの名無しさん
06/03/10 18:35:33
分けの分からん名前つけたがる奴ら多すぎ。
もうちょっと機能や用途を的確に表す分かり
やすいダイレクトなネーミングしろよ。
＞見つけたデータを配列の先頭に移す。
自己組織化という名前とどう関係あるのかさっぱり分からない。
一度ヒットした検索の結果を頭に持ってくるようなことは
ちょっと気が利いたやつなら普通にやるが、そういう用途
なのか？
22:デフォルトの名無しさん
06/03/10 20:16:42
絶対アル感＝あらゆる現象をアルゴリズムとして表現することの出来る能力
23:デフォルトの名無しさん
06/03/10 20:27:13
俺ゴリズム ＝ 自分で編み出したアルゴリズム。だが実は再発明。
猿ゴリズム ＝ アルゴリズムと呼ぶには、あまりにも稚拙。
24:デフォルトの名無しさん
06/03/10 21:09:59
アルゴリズマー＝アルゴリズムの考案を生業としている人。
25:デフォルトの名無しさん
06/03/10 21:13:12
調べるより再発明した方が早い場合もある。ソースが無けりゃあ
再実装はさけられないしな。
26:デフォルトの名無しさん
06/03/10 21:16:59
早いかどうかはどうでもいいな～
重要なのは楽しいかどうか
どうせ最終的にやることは変わらんしな
27:デフォルトの名無しさん
06/03/10 21:19:59
>>24
どっちかというと、アルゴリズミストという感じがするな。
>>26
調べる訓練を十分積んでないと、再発明の方が心理的に楽なんだよな。
しかしそれまでに研究されたアルゴリズム上の穴や欠点が反映されない罠。
28:デフォルトの名無しさん
06/03/10 21:22:25
【先進国アルゴリズム協会】
「先進国アルゴリズム協会」（通称：SAK）は北半球の国々による
アルゴリズムの研究を目的とした公的機関である。
世界から優秀なSEやプログラマが集められており、年に数回の学会を催している。
最近有名なのは、画像ファイルからそれがエロ画像であるかを判定するアルゴリズムである。
これにより、エロ画像掲示板等向けの巡回ソフトを開発する際に、
余計なネタ画像を避けてエロ画像のみを収集することができ、日米を中心としたIT先進国も注目している。
29:デフォルトの名無しさん
06/03/10 22:06:49
しかし、ネタ画像で十二分に性的興奮を覚える人間に対しての
不当な文化の押し付けであるとして、アジアを中心とした人権団体から非難が出ている。
これに対しSAK側は沈黙を決め込み、半ば強引な進め方が行われており、
人権団体では、日米主体のエロ文化が蔓延するのではないかと懸念している。
30:デフォルトの名無しさん
06/03/10 23:03:14
一部分に肌色のピクセルが集中していたらエロ画像の可能性が高いかな
31:デフォルトの名無しさん
06/03/10 23:18:54
グロ画像の可能性も大いに有り
32:デフォルトの名無しさん
06/03/10 23:23:11
エロ画像フィルタは既にあるが
赤ん坊の写真まで除去されてしまう
33:デフォルトの名無しさん
06/03/10 23:57:41
こっこのアルゴリズムヌケる………………………うっっ
34:デフォルトの名無しさん
06/03/11 00:00:16
↓heap sortで3回ヌケる
35:デフォルトの名無しさん
06/03/11 02:30:37
適当なスレがないのでここで聞いて見ます
あるコントロールを作ってこれは角ならその方面のサイズを
辺ならその辺を基準にした高さを
右クリックなら回転を
マウス操作で行おうとしてるんですが
マウス座標はXYなので回転後の伸縮幅の計算でわけがわからなくなってしまった
三角関数が入り組んでる状態で頭がいたいので
どっかにサンプルころがってないですかね？
あるいはスマートに共通の関数とかで処理する方法があれば教えてください
36:デフォルトの名無しさん
06/03/11 02:37:32
>>35
おまいの日本語がわかりにくい
回転移動の１次変換
URLﾘﾝｸ(www.geisya.or.jp)
37:デフォルトの名無しさん
06/03/11 02:40:37
着衣エロ、もしくは着色エロで対抗だ！
38:デフォルトの名無しさん
06/03/11 03:01:51
>>36
回転はできてます
例えば４５度左にすでに傾いていた場合、上辺をドラッグして左右辺の長さを変えるわけです
マウスの位置に上辺が来ないといけないわけですが
マウスのY座標から左上と右上の角の座標が知りたいわけです
これは単純にサイズ変更だけじゃなくて移動もしないといけません
この時に回転軸も重心を取ってるのでずれてきます
上辺がマウスに重なるように下辺は固定したまま上辺だけを移動したいのです
39:デフォルトの名無しさん
06/03/11 03:21:33
コントロールじゃなくて
ぜんぶ自前で線描画した図形にしたらどーかね
40:デフォルトの名無しさん
06/03/11 03:54:06
コントロールといっても回転なんか出来ないので全部自前の描画ですよ？
なにをゆっているのですか？
41:デフォルトの名無しさん
06/03/11 04:00:35
なんで計算できんのかわからんな
42:デフォルトの名無しさん
06/03/11 05:39:15
ではウォーミングアップからお願いします。
リストから重複要素を取り除いたリストを得るアルゴリズムをお願いします。
高速なのをお願いします。
43:デフォルトの名無しさん
06/03/11 05:52:19
>>41
じゃあもう少し要点をまとめるので答えてね
ある角度αで回転した四角形があります
左上角を(x,y)とします
上辺の中心を(x',y')とします
この中心をドラッグし移動するとマウスと上辺は交差する位置を維持します
下辺２点は固定です
この時いまマウスがいる座標を(x'',y'')とします
この座標と交差する上辺の左角の座標を求める計算式を提示してください
44:デフォルトの名無しさん
06/03/11 09:14:31
>>43
＞ある角度αで回転した四角形があります
どこを中心にどう回転したのか書いてないしな。
曖昧な情報を出してくる辺りネタとしか思えない。
もう帰っていいよ。
45:デフォルトの名無しさん
06/03/11 10:08:56
>>42-43
ほんとに聞きたいなら、その部分コード書いて、判らない所をコメントにして聞いてくれよ。
>>42 リストって言ってるのはホントのリストだな Delphi/BuilderのTListじゃないね？
ただ、どういうリストなのか構造が判るようなコードで書いてくれよ。
じゃないと単なるリストならアルゴリズムもクソもリストを全部辿るしか方法ないじゃない
>>43 判りにくい。コードで書いて
46:デフォルトの名無しさん
06/03/11 10:54:14
>>45
僕の考えた低速そうなアルゴリズムはこうです。
fun expMul nil = nil
| expMul (h::nil) = [h]
| expMul (h::rest) = h::expMul(cut(h,rest))
and cut (x,nil) = nil
| cut (x,(h::nil)) = if x=h then nil else [h]
| cut (x,(h,rest)) =if x=h then cut(x,b) else h::cut(x,b);
47:デフォルトの名無しさん
06/03/11 11:31:54
目当ての女の子画像を集めるアルゴリズムおながいします
48:デフォルトの名無しさん
06/03/11 12:20:29
>>47あ～、それ俺もすげぇ欲しい
顔で判断するのか？
49:デフォルトの名無しさん
06/03/11 13:04:15
>>47
Google イメージ検索
50:デフォルトの名無しさん
06/03/11 16:33:09
>>44
重心って書いてるじゃんｗ
ばーか
51:デフォルトの名無しさん
06/03/11 16:34:56
>>判りにくい。コードで書いて
コードで書いたらもうほとんど答えでバグ広いだけじゃんｗ
ばかじゃねーの
52:デフォルトの名無しさん
06/03/11 16:42:16
// 重心を中心に回転済みの座標
function (mouse, leftup, rightup, leftbottom, rightbottom, kakudo){
// mousex mouse.y が (leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するように
// leftup rightupを修正
// ↓
？？？？？？？？？？？
// ↑
return points
}
はいコードどうぞｗ
53:デフォルトの名無しさん
06/03/11 17:07:04
>>51
ならそれで質問者は解決するわけで、みんなハッピーだ
>>52
つまり、(leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するのは、何？
54:デフォルトの名無しさん
06/03/11 17:09:35
mousex mouse.y が
55:デフォルトの名無しさん
06/03/11 17:11:50
むしろ解答するように見せかけた釣りとしか思えないｗ
56:デフォルトの名無しさん
06/03/11 17:13:09
線分と交差するのは2次元なら線分でなければいけないよ？
57:デフォルトの名無しさん
06/03/11 17:17:42
君には一生解答できないからいいよｗ
58:デフォルトの名無しさん
06/03/11 17:18:13
>>52
引き数の型が書かれていない
mouse, leftup, rightup, leftbottom, rightbottom, はpoints として kakudoは何？
それから leftbottom, rightbottom, kakudoはこの関数の動作に関係しないなら引き数にする必要はない
関係するならその説明をしないと意味がないだろう
59:デフォルトの名無しさん
06/03/11 17:19:33
>>57
あのさ、この板でこの手の回答の半分はオレなの。
オレが答えなきゃ、回答率は半分になるよ。
60:デフォルトの名無しさん
06/03/11 17:22:31
kakudoは現在の回転角0-360
points は変化後のすべての座標の省略
形なんか好きにしろｗ
角度計算する際の常識的な形ってやつがあるだろ
使うか使わないかもわからないのかお前は？ｗ
61:デフォルトの名無しさん
06/03/11 17:26:16
常識は人によって色々だ
オレはこの手の処理をするときは角度じゃなくて sin/cos成分を引き数で渡す。 これはオレの常識
つまり、これは関数というより手続きなんだね？ それを表現してくれないといけない。
それで、入力としては mouse, leftup, rightup, leftbottom, rightbottom, kakudo
出力は何？
想像としては、
leftup, rightup, leftbottom, rightbottom の相対関係を固定して kakudoで回転させたいように思うが mouseはどういう拘束条件？
62:デフォルトの名無しさん
06/03/11 17:30:20
(leftup)-(rightup)が点(mouse)を通過する
角度reftupは９０度rightupは９０度を固定された
leftupとrightupを入れ替えて
返す
kakudoha現在の座標がその角度で回転されたものだって意味じゃぼけ
63:デフォルトの名無しさん
06/03/11 17:38:29
>>62
判った事は
mouse, leftup, rightup, leftbottom, rightbottom が点座標
kakudo が 現在の座標の回転角 ここまでは判った
現在の座標の回転角とは何？
90度というの何と何の角度？
もしかして長方形? 長方形なら2点だけでいいよね？
64:デフォルトの名無しさん
06/03/11 17:41:03
長方形だって言ってるじゃんｗ
引数の数がその後の計算に影響するとは思えないんだが
自閉症なみのこだわりですねｗ
65:デフォルトの名無しさん
06/03/11 17:45:47
いや、未熟ですまん。
じゃ、ムダな、2点を削除して
(POINT mouse, POINT p1 , POINT p2 , double kakudo) にしよう
左上p1と右下p2の kakudo で回転された 長方形があるとする。
このmouse上の点が上辺になるように 移動変換したい というのが疑問かい？
66:デフォルトの名無しさん
06/03/11 17:59:36
課題をもう少し変形する。
W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
点 mouse にWが一致するように center を平行移動して返す関数を作れ。
でいいの？水平移動優先？ 垂直移動優先？それとも最短移動距離優先？
67:デフォルトの名無しさん
06/03/11 17:59:56
そんな感じ
68:デフォルトの名無しさん
06/03/11 18:03:51
まてよ、
＞ この座標と交差する上辺の左角の座標を求める計算式を提示してください
これを翻訳すると
このmouse座標上に上左点が来るように center を設定せよ
これでいいんじゃないの？
69:デフォルトの名無しさん
06/03/11 18:05:03
>>66
は違う気がする
70:デフォルトの名無しさん
06/03/11 18:08:51
.>>68
アーぜんぜん違うｗ
回転してない長方形があって上をひっぱると上に伸びるだけね
下は固定
これはその長方形を回転させた状態のときに同じく上にひっぱるわけ
71:デフォルトの名無しさん
06/03/11 18:13:57
問題が
W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
mouse座標上に回転後の上左点が来るように center を設定せよ
だとすれば
center.MOVE(POINT(-W/2,+H/2)).ROTATE(kakudo) == mouse を解けばいい
center.MOVE(POINT(-W/2,+H/2)) == mouse.ROTATE(-kakudo)
center == mouse.ROTATE(-kakudo).MOVE(POINT(W/2,-H/2))
という答えだったけど、これは問題が違うわけね。
ちょっとまってね
72:デフォルトの名無しさん
06/03/11 18:22:21
W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
mouseを重心の位置が原点になるように回転移動逆変換する
rmouse=mouse.ROTATE(-kakudo).MOVE(-center)
問題：
rmouseのy座標の位置が上辺と一致し、下辺座標が変化しないように centerとHを変更せよ
って、事で、もう答え書く必要はないでしょ
73:72
06/03/11 18:56:01
コレでレスが無いって事は、オレやり遂げたのか？
自分を祝福したいよ。
74:デフォルトの名無しさん
06/03/11 20:56:07
その方法はすでに考えてた
その説明だけじゃたりんがね
回転演算を３回しないといけない
書いててもスマートじゃないからなんかいい方法ないものかと聞いてみただけ
75:72
06/03/11 21:17:43
ありがとう。
どっちかいうと問題が秘密で問題に到達するまでのゲームだったね。 けっこう面白かった。
問題が判らないから表現方法を模索した結果、こうなっただけで
実際のデータとしては四角形に固執せずに、任意多角形の問題として
マウスで図形を動かす＝マウスの動きに対して何を拘束して何を追従させるかという
問題と捕らえて、一般的に解かせる方がいいよ。
図形を動かす方時のコストなんてしれてるから、多少リッチにＣＰＵコストをかけさせてもいい
で、ここには単なる長方形ではなくて、この長方形にビットマップのようなものを貼り付けるんだろ？
だったら、そっちのコストがずっと大きいから
76:デフォルトの名無しさん
06/03/12 00:30:36
【エロゴリズム】
与えられた情報を湾曲させ、猥褻な情報に変換するアルゴリズム。
文字列の変換に関するエロゴリズムが多く考え出されているが、
画像や音声に関してのエロゴリズム考案にもSAKは力を入れている。
文字列変換の例：
愛されて10万戸→愛されて汁マンコ
私の父はSEです→私の乳はSEです
77:デフォルトの名無しさん
06/03/12 00:39:42
ピタゴラスイッチ
78:デフォルトの名無しさん
06/03/12 01:11:41
>>75
「アルゴリズムオタク」というスレにふさわしい回答ではないな。
どんなささいなコストも、なんらかのアルゴリズムで回避できるならしなきゃ。
79:デフォルトの名無しさん
06/03/12 05:37:04
>>76
>愛されて10万戸→愛されて汁マンコ
>私の父はSEです→私の乳はSEです
ただ下品なだけじゃん。
お前ごときがエロゴリズムを語るのは１０年早いわ！
童貞からやり直せ！
80:デフォルトの名無しさん
06/03/12 08:06:18
やり直すまでもないに一票
81:デフォルトの名無しさん
06/03/12 14:39:12
>>78
>「アルゴリズムオタク」というスレにふさわしい回答ではないな。
質問も回答もｽﾚ違いだろ阿呆。
82:46
06/03/13 11:38:46
結局僕はどうなりましたか？
83:デフォルトの名無しさん
06/03/13 11:48:15
>>46
みんなの知らない言語みたいだから、説明を入れてみたらどう？
84:デフォルトの名無しさん
06/03/13 18:16:41
head::body
はリストで、例えば
[1,2,3,4,5,6,7]とすると、
要素head=1
リストbody=[2,3,4,5,6,7]
を意味します。
nilは空リストです。
85:デフォルトの名無しさん
06/03/13 18:19:54
あ、>>47のラストの行の引数(h,rest)のところ、
正しくは(h::rest)でした。
86:デフォルトの名無しさん
06/03/13 18:54:13
>>42
結局、ソートされたデータなわけ？ ソートされてるなら先頭から順に見るだけでいいし
そうでないなら、ソートしつつ削除するような方法になると思うよ
87:デフォルトの名無しさん
06/03/14 00:25:10
何この糞スレ？
88:デフォルトの名無しさん
06/03/14 03:57:45
>>86
リストの順序を保ちたい場合は考慮されてますか？
89:デフォルトの名無しさん
06/03/14 06:47:21
>>88
そもそも リスト構造のままソートするのは効率が悪いから
リストとは別にポインタ配列としてソートする事になるだろうね
90:デフォルトの名無しさん
06/03/14 07:52:01
>>89
実装の話ではなくアルゴリズムの話の筈ですが…
91:・∀・）っ-●○◎- ◆Pu/ODYSSEY
06/03/14 17:38:49
普通に大学1回生のときに単方向リストで重複要素を除く機能つきのマージソート作った。
比較するときに同一の場合は除去すればいいだけだからソートの延長で考えればいい。
92:デフォルトの名無しさん
06/03/14 18:41:51
そういや大学のときC言語の授業で
配列とポインタの練習としてスタックとキューを実装しる、みたいな問題が出て
再配置がﾏﾝﾄﾞｸｻｰだった俺は循環キューに思いいたったわけだが、
それが俺の始めての「車輪の再発明」だった。
懐かしい。
93:デフォルトの名無しさん
06/03/14 19:23:49
【積年の】旦那にしてる密かな仕返し【恨みじゃー】
ｽﾚﾘﾝｸ(ms板)
8 名前：可愛い奥様[] 投稿日：2006/03/07(火) 11:05:23 ID:8dtluKkp
夫の歯ブラシで洗面所の排水溝掃除。
洗面所をビショビショに汚した罰だ。
20 名前：可愛い奥様[age] 投稿日：2006/03/08(水) 00:40:17 ID:pRrk6A21
前に頭きた時あって
１度だけ歯ブラシで肛門カキカキしちゃった
22 名前：可愛い奥様[] 投稿日：2006/03/08(水) 01:27:12 ID:gU5mHc7J
よかった。どこのお宅も同じようなことしてて。
24 名前：可愛い奥様[] 投稿日：2006/03/08(水) 01:36:35 ID:SSSFsTqE
そうそう、ヘンなモノはダンナのお皿へ直行だよね。
41 名前：可愛い奥様[] 投稿日：2006/03/08(水) 11:55:18 ID:sjj+/60Q
見てるだけで気が晴れるな！
皆さん、頑張ってね！
42 名前：可愛い奥様[sage] 投稿日：2006/03/08(水) 20:33:51 ID:Ju2N1s7+
年金分割が楽しみじゃのう
63 名前：可愛い奥様[] 投稿日：2006/03/10(金) 08:55:20 ID:qLfJYpJR
家族で密かにはぶっている。
男性は肉体が汚く、精神が美しい傾向がある。（気に入らない相手に肉体的攻撃を加える⇒精神的攻撃も加える男は猛者）
女は肉体が美しく、精神が汚い傾向がある。（気に入らない相手に精神的攻撃を加える⇒肉体的攻撃も加える女は猛者）
女は隠れて悪事をする。気に入らない女子を便所でボコったり、便器舐めさせたり、男の友人を使ってレイプ、仲間外れにしたり。陰口、嫉妬。
女は対人関係において、この汚い性格を隠そうとするため、外面が非常によくなる。（猫かぶり）
男性諸君は外面に騙されないように気を付けて下さい。
94:デフォルトの名無しさん
06/03/14 20:22:38
アルヲタ
95:デフォルトの名無しさん
06/03/14 22:50:49
アルゴリズム体操
96:デフォルトの名無しさん
06/03/17 13:45:22
>>91
考えられる限り高速な方法で。
普通になら作れます＞＜
97:デフォルトの名無しさん
06/03/17 16:40:31
>>96
>>89
ソートしてあればO(n)で重複を取り除けるし、
配列にリンクポインタへのポインタ相当のものを格納すればリストそのものの順序を変える必要はないし
配列ならデータの種類によっては(フラッシュソートなど)O(n)で出来るソートアルゴリズムが存在する
98:http://www.vector.co.jp/soft/win95/util/se072729.html
06/03/18 19:14:07
TextSS のWindowsXP(Professional)64bit化おながいします
もしくは64bitにネイティブ対応したテキスト置換ソフトありますか？
99:デフォルトの名無しさん
06/04/07 08:22:29
では、荒し検出アルゴリズムを。
100:デフォルトの名無しさん
06/04/07 21:47:38
100get!!
101:デフォルトの名無しさん
06/04/09 23:06:57
>>99
簡単だ
102:デフォルトの名無しさん
06/04/10 00:21:52
>>101
うｐして
103:デフォルトの名無しさん
06/04/10 02:04:26
if(名前!="デフォルトの名無しさん"){
for(;;)MessageBox("荒らしだーーーーーーー！！！！");
}
104:デフォルトの名無しさん
06/04/10 12:18:52
>>103が荒らし。
105:デフォルトの名無しさん
06/04/12 10:18:39
puts(レスの内容);
puts("これ荒らし？[y/n]");
if(getchar() == 'y') for(;;) puts("荒らしだーーーーーーー！！！！");
106:デフォルトの名無しさん
06/04/12 22:22:58
今、プログラマの数学って本を読んでるんだけど
そこに出てくるハノイの塔の再帰的処理が理解できない。
どこを繰り返し処理してるの？
パターンがある事に気付けないんだけど。
ちなみに階乗のアルゴリズムが再帰的だとは理解できます。
5!=5*4!
4!=4*3!
3!=3*2!
2!=2*1!
1!=1*0!
0!=1
107:デフォルトの名無しさん
06/04/12 22:24:34
本にはハノイの塔を解く手順、
すなわち３本の柱が左からA, B, Cとあって、
n枚の円盤を柱xから柱yへ柱zを利用して移す手順
をＣ言語で書いてある。
#include <stdio.h>
#include <stdlib.h>
void hanoi(int n, char x, char y, char z);
void hanoi(int n, char x, char y, char z)
{
if(n == 0){
//何もしない
}
else{
hanoi(n-1, x, z, y);
printf("%c->%c, ", x, y);
hanoi(n-1, z, y, x);
}
}
int main(void)
{
hanoi(6, 'A', 'B', 'C');
return 0;
}
108:デフォルトの名無しさん
06/04/12 22:33:07
解き方を見てから強いてパターンを見つけると
１回目は、必ずAとCの間でやり取りをする。
２回目は、必ずAとBの間でやり取りをする。
３回目は、必ずBとCの間でやり取りをする。
で、また１回目に戻る。
でも、例えば１回目はAとCでやり取りすることは分かっても
どっちからどっちへ円盤を移すかはどうしてアルゴリズムから分かるの？
人間は「"小さい円盤"の方から"大きい円盤"の方へ」って
目で見て判断できるけど、コンピュータはできないのに。
109:デフォルトの名無しさん
06/04/12 22:35:40
>>106
ディスクN-ディスク1をバーAからバーBに移動しようとしたとする。
その行程は、
・ディスクN-1-ディスク1をバーAからバーCに移動
・ディスクNをバーAからバーBに移動
・ディスクN-1-ディスク1をバーCからバーBに移動
と書ける。
関数形式で書くとすると、
void moveDisk(int n, Bar a, Bar b)
{
printf("ディスク%d を バー%dからバー%dに移動\n", n, a, b);
}
void hanoi(int n, Bar a, Bar b, Bar c)
{
if (n > 0) {
hanoi(n - 1, a, c, b);
moveDisk(n, a, b);
hanoi(n - 1, c, b, a);
}
}
こうなる。
Nが3辺りのときの振る舞いを自分で追ってみればよく判ると思う。
110:デフォルトの名無しさん
06/04/13 02:18:16
・n=5を解くには
|54321
|
|
↓(n=4を解く)
|5
|
|4321
↓
|
|5
|4321
↓(n=4を解く)
|
|54321
|
・n=4を解くには(以下略)
...
・n=1を解くには
111:デフォルトの名無しさん
06/04/14 22:08:53
>>99
アルゴリズムを考えるアルゴリズムがわかってないはずだから無理だとおもいまーす。
荒らすのはそのアルゴリズムかどうかもわからないんだっけ、
わかってるんだっけ？
112:デフォルトの名無しさん
06/04/14 22:12:21
日本語でおｋ
113:デフォルトの名無しさん
06/04/15 01:08:54
>>1
アルゴリズムマニアの日記
URLﾘﾝｸ(d.hatena.ne.jp)
114:デフォルトの名無しさん
06/04/16 13:12:26
だれか突撃しろ
115:デフォルトの名無しさん
06/04/16 13:58:15
は？
116:デフォルトの名無しさん
06/04/18 12:44:20
物凄い簡単なものなのかもしれませんが分からないので質問。
ｎ本のマッチがあって、一回に１～３本取れる。
自分は先手で、最後の一本をとったら勝ちになる。
必勝のアルゴリズムを教えてください。
117:デフォルトの名無しさん
06/04/18 12:55:41
残りが4の倍数になるように取る
118:デフォルトの名無しさん
06/04/18 12:57:03
残りが3i+1になるように取る
119:デフォルトの名無しさん
06/04/18 13:21:41
>>118
（ ・д・）……
120:デフォルトの名無しさん
06/04/18 13:41:09
>>118
残り7で相手が3取って終了。
121:デフォルトの名無しさん
06/04/18 13:46:24
>>120
122:デフォルトの名無しさん
06/04/18 14:57:39
マッチ棒を取った本数がポイントになるが、
最後の一本は-10点とかだったらどうだろう?
123:デフォルトの名無しさん
06/04/18 18:33:39
>>122
その場合は最後の一本を取ったら負けというルールとほぼ等しいので、
4の倍数+1になるようにすればいい。
124:デフォルトの名無しさん
06/04/18 18:42:44
>>123
たとえば、1000の棒を取る時にはどうよ？
相手がずっと3取ってたら負けね？
125:デフォルトの名無しさん
06/04/18 19:04:42
お互いに3本づつとっていって、残り６～７本あたりから勝負かな
勝ちパターン考えるのはメンドクセ
126:デフォルトの名無しさん
06/04/18 19:24:24
意外と深いな。
最後の一本をとったら負けというのなら簡単なんだけど。
127:123
06/04/18 19:47:28
>>124
すまん、マッチ棒という前提を読んだ段階で1000本は想定外だった。
128:デフォルトの名無しさん
06/04/18 20:37:04
アルゴリズム初心者には難しいのか？orz
もう少し頑張ってみます。
フローも書かないと・・・orz
129:デフォルトの名無しさん
06/04/18 21:01:01
ゲーム理論に帰着されそうな予感
130:デフォルトの名無しさん
06/04/19 10:52:29
前のターンまで同数の場合は、21を取った方が勝ちか引き分けに
なるんだけど、自分が21を取る為にそれより前のターンで本数調整
したら勝てなくなるから、結局最初の本数で決まりそう。
131:デフォルトの名無しさん
06/04/24 01:25:04
／￣￣￣￣￣￣￣＼
─ ＝ ニ /=､｡｡｡｡｡｡｡｡｡｡｡｡｡｡｡｡ｒ=､ヽ
─ ＝ニ三 （◎ ヽ-───（◎ )
ノ◎､ |＼ ＼ / ／ | /◎､
(_,ｒへ ｀ｿ /> ◎) (◎く| レ' ,ｒへ )
─ ＝ ニ ＼◎'/ ／ ＼ ヽ､◎／
ノ ／ ＼ ヽ
─ ＝ニ三 ( ◎( ) ◎)
─ ＝ ｰ､_ら ⊂､_,ｒ´
このマシンがどうして前に進むのか教えてください。
普通だったら両方から押し合いへし合いして動かない気がするのです。
132:デフォルトの名無しさん
06/04/24 07:23:34
それは、コックリさんの原理だよ
133:デフォルトの名無しさん
06/04/24 08:43:58
この場所に秘密があるんじゃないかな
URLﾘﾝｸ(maps.google.com)
134:デフォルトの名無しさん
06/04/24 17:55:54
>>133
ベームベーム？
135:デフォルトの名無しさん
06/04/25 11:18:11
右側の足は後ろ歩きすればいいんじゃね？
136:デフォルトの名無しさん
06/04/26 15:15:15
>>88
リストソートはスキップリストで決まりかな。
137:デフォルトの名無しさん
06/04/29 20:11:49
アルゴリズムの仕様を記述する言語作れないかな。
138:デフォルトの名無しさん
06/04/29 20:13:31
それ日本語でよくね？
139:デフォルトの名無しさん
06/04/29 20:20:02
いや、コンピュータで扱えるようにしたらなんかいいことあるかと思って。
たとえば実装が仕様にあってるかどうかテストできるとか。
あとアルゴリズムのデータベースつくってその言語で検索とかできないかなーと。
140:デフォルトの名無しさん
06/04/29 23:52:59
実装の検証ってどの程度のものを想定している？
それによって話は全然変わってくるんだが．
141:デフォルトの名無しさん
06/04/30 08:04:28
入力データもある程度自動生成してくれて、出力結果も検証してくれるやつ。
まあ完璧なテストは無理だけどある程度のテストはできそう。
142:デフォルトの名無しさん
06/04/30 08:08:46
それは実装の検証じゃなくて入出力の検証だよね。
ユニットテストのすごいバージョンってことでいいの？
143:デフォルトの名無しさん
06/04/30 08:20:09
入出力が正しければ実装も正しいというのは間違いですか？
まあ、確かにユニットテストのすごいバージョンです。
144:デフォルトの名無しさん
06/04/30 09:08:16
同じ入力に対して同じ出力を得られたからと言って、
アルゴリズムが同一とは限らないわけで・・・
入出力を検証しても必ずしも実装が正しいかどうかは分からないよね。
例えば安定クイックソートの実装のつもりでテストをして、
実際に実装されているのはバブルソートだったとしても出力だけでは分からないはず。
145:デフォルトの名無しさん
06/04/30 15:27:28
>>144
複雑度のテストとして、要素数の規模を変えて数回テストし、
実行時間の変化を見てくれるとか、うーん、むずかしいかな。
146:137
06/05/01 20:03:42
クイックソートもバブルソートもどちらもソートだから区別する必要は無いと考えています。
入出力の仕様の定義だけ行う言語を作るのも意味はあるかと。
そのあとどんな実装を行うかはまた別の問題ということで。
147:デフォルトの名無しさん
06/05/01 20:10:43
一階述語論理で良ければ Prolog でいいんじゃないの?
148:デフォルトの名無しさん
06/05/01 20:15:50 BE:209674728-
ソートだってアルゴリズムじゃないか。
仕様を後付けしすぎ。
149:デフォルトの名無しさん
06/05/01 20:46:10
>>146
O(n log n) のソートと O(n^2) のソートは
質的に全然違うものなので、それを記述できない言語は
アルゴリズムを記述するには不適当。
150:137
06/05/01 21:09:12
>>149
よく考えてみたらアルゴリズムを記述する言語というのが間違いでした。
私がほしかったのは問題を記述する言語とでもいいましょうか。
アルゴリズムが満たさなければいけない条件を定義したかったのです。
151:デフォルトの名無しさん
06/05/01 21:14:22
>>150
わかってねえなあ。
「O(n log n) である」 ことを 「満たさなければいけない条件」 として
書けないと、全然意味が無いんだって。
「O(n log n) でないと破綻する入力」 みたいなのを自動生成
できりゃいいけどさ、そんなのは不可能だ。
152:137
06/05/01 21:26:01
スピードに関していえばソートのような良く研究されたアルゴリズム
は最適解がわかってますが、最適解がわかってない問題もたくさんある
わけですし、それほど重要とは思っていません。
153:デフォルトの名無しさん
06/05/01 21:28:18
>>152
研究用途ならそういう結論になるかもしれないな。
だが計算量を記述できなければ実用の道をほとんど閉ざすことになる。
154:137
06/05/01 21:38:14
スピードは実装ががんばればいい話であって、仕様には関係の無い話です。
どれくらい頑張れるかは不明な場合が多いのです。
私は仕様を書いたら即動くものができるというようなことは考えていません。
実装する際に何らかの役に立てばいいと思っています。
155:デフォルトの名無しさん
06/05/01 21:48:48
アルゴリズムの仕様を記述する目的でPASCALで不足する部分は何？
156:デフォルトの名無しさん
06/05/01 22:00:19
>>154
世の中にはスピードが問題になることも多々あるわけだが。
理論上は可能、ただし、処理に１０億年掛かります、とかね。
そもそも仕様が適当すぎ。荒らしに来たとしか思えない。
157:デフォルトの名無しさん
06/05/01 22:02:12
ていうかさ、作りたければ作ればいいじゃん。
このスレ(の住人)に何を求めてるの？
158:137
06/05/01 22:14:20
>>155
原理的にＰＡＳＣＡＬでかけないものなんて無いでしょう。
もうちょっと楽にならないかなという程度のことです。
>>156
スピードを仕様に盛り込んだとしても達成できなければ意味が無いのです。
たとえばソートをO(logn)でやれといっても無理な話です。
結局できることといったら存在する実装から一番いいものを選ぶだけなんです。
>>157
まあ、一緒になって考えていただければ。
159:デフォルトの名無しさん
06/05/01 22:38:10
計算量を実装が頑張ればいい話とかいってる時点で
このひとが全然アルゴリズムを理解していないことが分かる。
160:137
06/05/01 22:45:07
ですから、私が最初にアルゴリズムといったのが間違いで、
解くべき問題を記述したいのです。
ソートには色々な計算量のソートがありますが、目的はどのソートも同じです。
その同じな部分を扱いたいのです。
161:デフォルトの名無しさん
06/05/01 22:56:44
じゃあすれ違い。
162:デフォルトの名無しさん
06/05/01 23:02:52
つーか同じソートでも目的が違うから複数のアルゴリズムがあるんだが
163:デフォルトの名無しさん
06/05/02 00:12:14
>>158
>まあ、一緒になって考えていただければ。
情報を小出しにし、わけの分からない仕様を提示し、アルゴリズムの話ですらないのに
その上、出て来た意見を片っ端から否定しといて「一緒になって」も無いだろ
164:137
06/05/02 00:16:19
お前らみたいな低脳とホントに一緒に考えられるわけねぇだろ。
リップサービスと言う言葉の意味を考えてみたらどうだ?
165:デフォルトの名無しさん
06/05/02 00:16:35
ナタク…。俺はどうしたらいい？
166:デフォルトの名無しさん
06/05/02 00:32:18
きっと>>137は
0+0=0
0+1=1
1+0=1
1+1=0
だけであらゆるプログラムを作れるんだろうな。
167:デフォルトの名無しさん
06/05/02 02:33:34
おめぇら、形式的仕様記述について知ってる事を書け
ｽﾚﾘﾝｸ(tech板)l50
こういうスレが欲しかったんだろ？ さあ逝ってきな
168:デフォルトの名無しさん
06/05/05 13:02:09
浮動小数（例えば[3バイト符号付整数] × [2のn乗|nは1バイト符合付き整数]）を、
対応する十進数（例えば[4バイトBCD] × [10のN乗|Nは1バイト符合付き整数]）
に変換するのはどうしたらいいかな。
当然、与えられた浮動小数の符合付き整数部のMSBは1に、
結果のBCDの最上位ニブルは0以外に正規化（？）されているものとする。
8ビットマイコンのアセンブラ想定でよろしく。
169:デフォルトの名無しさん
06/05/05 13:18:25
アルゴリズムもクソもそのままやるしかないでしょ
どっちかいうと実装テクニックじゃない
170:デフォルトの名無しさん
06/05/05 14:53:07
>>169
アルゴリズムとそうでないものの違いは「俺様が関心があるかどうか」
の違いではないでしょうw
171:デフォルトの名無しさん
06/05/05 14:55:27
まあ愚直にやるっきゃないのは確かっぽいが
172:デフォルトの名無しさん
06/05/05 14:56:09
8bitなら、2^N = b*10^M のテーブルを作っておいて
a*2^N = a*b*10^M とやって正規化するくらいだね
173:デフォルトの名無しさん
06/05/07 18:59:04
アルゴリズム好きとかものすんごいうらやましい。
174:デフォルトの名無しさん
06/05/07 22:05:07
逆に趣味でプログラミングやってますとかっていうヤツのなかにも
希に「そこを自分で考えるのが楽しいんだろ」ていう部分を
メーリングリストや掲示板で「どうやったらいいんでしょうか？」とかって
訊いてくるヤツのことがサッパリ理解できない。
175:デフォルトの名無しさん
06/05/08 01:00:24
>>174
そこを自分で考えるのが楽しいんだろ？
176:デフォルトの名無しさん
06/05/08 15:13:52
>>175
そういうレスを返すヤツのことがサッパリ理解できない。
177:デフォルトの名無しさん
06/05/08 15:18:44
>>173
>>113
178:デフォルトの名無しさん
06/05/11 18:47:21
ドッキングツールバーの設計をやっているけれど、
なかなかいい構造が思いつかない。
179:174
06/05/11 21:46:41
>>178
こーゆーケースは理解できるし共感できる。
180:デフォルトの名無しさん
06/05/12 12:43:47
ところでアルゴリズムを相談するスレってどこ？
181:デフォルトの名無しさん
06/05/12 19:21:09
ここでいいよ
182:デフォルトの名無しさん
06/05/25 12:15:42
あげ
183:デフォルトの名無しさん
06/06/08 07:52:46
なあ、グランドにごっちゃに人集めて、
はい背の順に整列！
って時さ、
全員がクイックソート理解してたと仮定して、その通りに整列してもらうより
普通に整列させた方が速そうじゃない？
モデル化すると、要素全てが各々同時並列的に他の任意の要素の値を知れる場合
そして要素が同時並列的に移動できる場合
184:デフォルトの名無しさん
06/06/08 08:47:32
コンピュータモデルとの一番の違いはデータの移動のコストが低いことだな。
大雑把にソートした列に、後はデータ自身が自分の入るべき場所を見つけて両側のデータに対して
スペースを作るように要求する感じかね。
オブジェクト指向のいいテストケースになりそうだが。
185:デフォルトの名無しさん
06/06/08 15:51:28
>普通に整列
脳はだいたい基数ソートみたいなことをしているんだってさ
186:デフォルトの名無しさん
06/06/08 17:05:29 BE:69876566-#
「普通に整列」の手順を考えてみる。
周りのオブジェクト全部をみて整列する人はまずいない。
だいたい自分がどのくらいの序列になるか予想して、整列の初期には近くにいる数人の
オブジェクトのうち同じくらいの序列になる物同士で小グループを形成し、グループ内での
序列を決定した後に他の小グループと合体、境界付近を調整する。
小グループ同士が合体したあとにオブジェクトが余っている場合も、自分の序列がどれくらい
かを予想してそこに近い部分集合の中から自分の序列を決定する。
つーわけで、段階的にマージソートと挿入ソートを同時多発的にやっているような気がする。
187:デフォルトの名無しさん
06/06/08 18:33:14
>>186
>同じくらいの序列になる物同士で小グループを形成し
これがマージソートと根本的に違うところ．
簡単のため小グループとして「背の低いグループと背の高いグループ」
を取って，それぞれで再帰的に計算してやることにする．
マージソートだと，それぞれをソートした結果をマージするときに
前半のトップと後半のトップを比較して云々とやらないといけなくて，
マージの部分の計算量が O(n) になり，合計として O(n log n) になる．
しかし，「普通に整列」の場合は前半のほうが後半よりも小さいと
わかっているので単純にくっつければよく，マージの部分の計算量が O(1) ですむ．
その結果，合計として O(n) でソートできるようになる．
188:187
06/06/08 18:37:48
スマソ，長々と書いていながら誤読してた．
自分の経験から小さい人は前，大きい人は後ろに行って，そこでソート
をやってるもんだと思いこんでいた．
その逆の近くに居る人たちから結合することを考えていたのか．申し訳ない．
＃多分それでも「合体」の部分で適当にオラクルが利いて O(n) になるとは思うが
189:デフォルトの名無しさん
06/06/08 21:38:20
自分がどの程度の背の高さになるかは把握してるとするなら、
最初の移動は粒度の荒いバケツでバケツソートってことになる。
バケツ内での並び替えはどうやってるんかな。
100人の場合と1000人の場合で実験してみないとなんともいえないが・・・
190:デフォルトの名無しさん
06/06/09 00:23:26
だんだんバケツが小さくなる
191:デフォルトの名無しさん
06/06/09 07:50:53
マジレスすると、
１）全生徒はそれぞれ「自分及び他人が（同年代の中で）どの程度の背の高さか」を感覚的に知っている。恐らくはクラスの背の順等の経験から。１０％程度の粒度で。
２）全生徒はそれぞれ個別に（＝同時に）自分が特定の他者より高いか低いかを判断してそれらしい位置に移動することが出来る。
３）数が多くなればなるほど、身長の近い者が逆順に並んでいても問題にしない。
以上の要因から、ＣＰＵ一個が無情報で正確にソートしなければならないことを前提としたアルゴリズムに時間的に優っているのである。
192:デフォルトの名無しさん
06/06/09 09:57:16
>>191
3)に関しては相手にお前何センチって聞けばいんじゃね
193:デフォルトの名無しさん
06/06/09 11:38:13 BE:108696487-#
>>191
機械がやる場合、たとえば標準偏差を与えて記憶や経験の代わりに予想の根拠とすることは
できるような気がする。
194:デフォルトの名無しさん
06/06/09 11:53:31
n 人で整列するとして、
・頭が n 個あるので log n 時間で整列が可能。
・人間が寝ている場合には、 n 台のロボットを使って log n 時間で整列可能。
ただし、
n が大きくなってくると、入れ替えるために移動させるためにかかる時間の方が
支配的になってくるので、O(n) になる。
195:デフォルトの名無しさん
06/06/09 20:29:46
たとえば、探索の場合には、
線形探索や二分探索という位置決めがデータによらない手法に対して、
データの種類によって次の探索位置を変える内挿探索という手法がある。
196:デフォルトの名無しさん
06/06/09 21:22:52
３次元空間上に２つの直線があって、
もしその２直線が交点を持つなら、
交点を計算するアルゴリズムってどうなりますか？
２次元平面上での交点計算みたいに方程式作ってもうまくいかないんですが・・・
なんかヒントくれるとありがたいです。
197:デフォルトの名無しさん
06/06/09 21:34:09
方程式で解くんじゃないの？
直線A：(x(s), y(s), z(s))
直線B：(x(t), y(t), z(t))
とパラメータ表示して、連立方程式
x(s)=x(t), y(s)=y(t)
から s, t を求める。
ここで解があれば、さらにz座標の式にいれてすべての座標が一致するかどうか確かめる。
198:デフォルトの名無しさん
06/06/09 21:40:16
あ～、なるほど。
先に2次元で解いておいて、3次元にしてもOKか見るわけですね。
なんか頭混乱してて、こんなこともわからなかったです・・・
ありがとうございました。
199:デフォルトの名無しさん
06/06/09 21:52:39
数学板で聞けば一発計算できる公式とか教えてくれそう
200:デフォルトの名無しさん
06/06/09 22:05:54
大学受験の頃は一発で出せる公式も勉強したかもしれんが、もう忘れたな。
201:デフォルトの名無しさん
06/06/09 22:25:30
忘れたなら何度でも導けばいい
202:デフォルトの名無しさん
06/06/10 16:23:04
俺なら
(最大値 - 俺の値)/(最大値 - 最小値)
で数直線上の何%くらいに位置するか検討をつけ、
この場合は身長の分布を思い出して、区間の人数割合を想像してから
自分の属する区間あたりにまず向かう。
適当に整列されて来たら
自分より背の高い奴がすぐ前にいればそいつの前に出る。
203:デフォルトの名無しさん
06/06/12 21:23:27
アルゴリズムの達人が集まってるスレはここですか？
質問なんだけど、BPマッチングっていうアルゴリズムって存在する？検索してもそれらしいのがヒットしないんだが
204:デフォルトの名無しさん
06/06/13 01:30:01
Bipartite Matchingかな
205:デフォルトの名無しさん
06/06/13 15:41:11
DPマッチングの読み間違いとか
206:デフォルトの名無しさん
06/06/13 15:42:01
クイックsortより速いソート挙げて
207:デフォルトの名無しさん
06/06/13 16:07:21
スーパーウルトラデラックスsort
208:デフォルトの名無しさん
06/06/13 16:15:30
基数ソート
209:デフォルトの名無しさん
06/06/13 16:32:32
バケツソート
210:デフォルトの名無しさん
06/06/13 16:33:40
あらかじめソートされたデータだけしか扱わないようにする
211:デフォルトの名無しさん
06/06/13 17:06:19
ソート済みリストをソートしようとしたら
もっとも速く処理が終る(もとと同じリストを吐き出す)ソートは？
212:デフォルトの名無しさん
06/06/13 21:37:45
>>211
挿入ソート、バブルソート
どちらも一回の走査で終了を検出できてO(N)
213:デフォルトの名無しさん
06/06/14 10:40:11
マージソートでは？
214:デフォルトの名無しさん
06/06/15 16:17:06
マージ部分で手を抜くと O(n log n)．
ただ，ちょっと賢くマージをすると O(n) になる．
215:デフォルトの名無しさん
06/06/26 18:41:04
ここで質問してもいいでしょうか？
記号列 S1={aabbbcccceefffggggxxxxyzzzz} S2={xxxyzzzzzzzzqqqqcceeff} みたいなのがあり、
それぞれの記号列の中で一致している長さX(可変、無限に長くしたい)以上の部分列を全て挙げる
この例では、X=5としたら {cceeff} {xxxyzzzz} を挙げる。
これを、できるだけ計算量とメモリを節約してやるアルゴリズムは？
それから、このアルゴリズム（この問題）には名前みたいなのあります？
216:デフォルトの名無しさん
06/06/26 20:12:01
名前があるか知らんが、ちょこっと考えたもの
S1とS2の半直線部分文字列を、マージ後ソートして比較する
メモリは、文字列を記憶するメモリ＋文字数×（sizeof(ポインタ)+記号列を特定するIDなど)
速度は、クイックソートでも使えば速そう
半直線部分文字列のソート後には
abbbcccceefffggggxxxxyzzzz(S1)
...
cceeff(S2)
cceefffggggxxxxyzzzz(S1)
...
xxxyzzzz(S1)
xxxyzzzzzzzzqqqqcceeff(S2)
...
zzzzzzzzqqqqcceeff(S2)
てな感じに並んでるかな、文字列がメモリ中にあればポインタだけソートすればOK。任意の長さの一致が全て判明する。
217:デフォルトの名無しさん
06/06/26 21:27:48
{ceeff}とか{cceef}とか{xxxyz}とかは解の候補にならないの？
218:デフォルトの名無しさん
06/06/26 21:30:05
>>215
S1,S2のSuffix Arrayを生成してからマージするような形で判定していけば良いと思う。
まぁ、ぶっちゃけ>>216のマージとソートの順序が逆になっただけだけど。
219:デフォルトの名無しさん
06/06/26 21:31:11
>>215
Xが何の長さなのかわからんし、何が一致しているのかわからん
総じて何を言いたいのかさっぱりわからん
220:219
06/06/26 21:35:29
すまん、「以上」を読み落としてた
意味はわかったが、アルゴリズムは全然思いつかない
221:デフォルトの名無しさん
06/06/27 12:17:48
マージしてソートってよくわからん。
とりあえずバカ正直な方法は
ａａｂｂｂｃｃｃｃｅｅｆｆｆｇｇｇｇｘｘｘｘｙｚｚｚｚ（s1）
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ （s2_0）
・・・
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ （s2_3）
・・・
ｃｅｅｆｆ ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃ（s2_10）
と、一方の文字列をずらしていって、一致する部分を探すことかな。
初めに文字のパターンを調べて、例えば a, b といった文字は片方にしか含まれないから
そういう位置ではパターン検索を省略できるとかくらいかな。
222:215
06/06/27 15:33:41
すみません >>221 と同じく、>>216の方法 よくわかりませんでした。
221 だと計算量 は |S1|×|S2|×|短い方| ぐらいなると思うんですが、
216 だともっと計算量減るでしょうか
>>217
それも解候補です。
本当は"極大"な解だけにしたいんですが、 今は全部出していいです。
例として aaabbbccc.. なんていうのを出してしまいましたが、
本当はもっとランダムな任意の記号列でやりたいのです。
223:デフォルトの名無しさん
06/06/27 16:01:48
まず、一方の文字列から「辞書」を作る
aabbbcccceefffggggxxxxyzzzz から
a: aabbb, abbbc,
b: bbbcc, bbccc, bcccc
・・・
y: yzzzz
（説明のために5文字だけだけど、当然、最長パターンまで作っても良い）
次に、もう一方の文字列から、一文字読み込んで、
そこから始まる文字列パターンが「辞書」に登録されてるか調べる。
メモリは食いそうだが、総当たりで調べるよりは少なくなる気がする
224:デフォルトの名無しさん
06/06/27 20:09:13
>>222
処理時間の大部分はソートの時間、クイックソートを使うとして
O(N log(N)) Nは|S1|+|S2|
特殊な例外を除いて計算量は減る。
問題は、文字数×8バイト(32bitマシンで)のポインタ領域が必要なこと
225:デフォルトの名無しさん
06/06/28 09:48:42
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
マージしてからソートはよくわからなかったから
ソートしてからマージで書いた．きちんと証明してないから
正当性はよくわからん．
Suffix Array の構成は O(n) でできることが知られていて，
マージの部分も同じ文字列を何度も比較するのをやめれば
O( (n+m)*min(n,m) ) でできる．合計して O( (n+m) * min(n,m) )．
226:デフォルトの名無しさん
06/06/28 09:58:26
>>224
長い文字列の比較はそれ自身コストが高いということを忘れてない？
227:デフォルトの名無しさん
06/06/28 16:44:35
>>226
もしかして最後の文字まで比較してると思ってる？
228:デフォルトの名無しさん
06/07/03 06:56:52
最後まで比較せずに済むという保証はどこにもない。
229:デフォルトの名無しさん
06/07/03 12:45:58
>>216
は、n-gram統計における「長尾・森の方法」だな。
岩波のソフトウェア科学の15巻参照
100万字での任意長重複列挙が1秒(Pen-M 1.5GHz)ってとこ。
ソートは文字列専用のソートを利用(単純なクイックソートをちょいと工夫)
>>224や>>228のいう「特殊な例外」（たとえばS1とS2が等しかったり、S1が
S2を包含する場合)では計算量は他の方法並みに大きくなる。
230:デフォルトの名無しさん
06/07/08 16:49:56
大量のエロ動画をRに焼こうと思うが、Rが最小枚数で済む様に最適化するアルゴリズム（もしくは応用できそうなアルゴリズム）ってある？
231:デフォルトの名無しさん
06/07/08 17:04:06
ビン詰め問題とかいう名前であった気がする。
その手の問題は、最適解を見つけるアルゴリズムは見つかってないか、
アルゴリズムが存在しないことが証明されてる（すべての組み合わせを調べるしかない）
ただし、最適解じゃないけど、そこそこ良い組み合わせを得る方法が研究されてる。
232:デフォルトの名無しさん
06/07/08 17:11:33
Hopfieldニューラルネットワークの最適化問題とか。
233:デフォルトの名無しさん
06/07/10 10:27:22
>>230
使える動画を 6 種類ローテで回して、単なる水着を一つ入れておくってどう？
これで一週間回せると思うけど。
234:デフォルトの名無しさん
06/07/10 14:51:21
ナップサック問題とはどう違うの？
235:デフォルトの名無しさん
06/07/10 15:49:37
いわゆる「ナップサック問題」は、袋の最大値が決まってて荷物の総価値が最大にするように選ぶって問題だよね。
荷物を全部入れる必要はない。
この質問は、荷物の全体が決まってて袋の数を最小にするって問題で、荷物を全部入れる必要がある。
だから問題としては違うんじゃないの。
アルゴリズムの本質的なテクニックは同じなのかも知れないけど。
236:デフォルトの名無しさん
06/07/10 18:44:50
どうせRに保存した動画なんてこの先見やしないので、
1枚用意して、そこに全動画を保存したと思い込めばok
237:デフォルトの名無しさん
06/07/10 21:36:04
どなたか、シェルソートとバブルソートの処理時間に差が出る
ことについて初心者でも分かるように説明させて
くださいませんでしょうか？お願いいたします。
238:デフォルトの名無しさん
06/07/10 22:36:14
適当にかき混ぜながらソートするので，
バブルソートや挿入ソートで遅くなるケースを回避しやすいから．
239:デフォルトの名無しさん
06/07/10 23:47:37
もちろん速くなるケースも回避しやすい．
240:デフォルトの名無しさん
06/07/11 07:53:20
で，結局どれくらいになるかは根性で期待値計算すると O(n^{3/2}) とか見えてくる，
241:デフォルトの名無しさん
06/07/11 07:56:35
よって初心者でも分かるように説明するのは無理．
242:デフォルトの名無しさん
06/07/17 16:04:35
以下のような単語がいくつかあった場合、
その全ての組み合わせのパターンを算出
するアルゴリズムってないですか？
カレー 餃子 牛丼 ラーメン
カレー 牛丼 餃子 ラーメン
牛丼 餃子 ラーメン カレー
・・・
・・・
・・・
243:デフォルトの名無しさん
06/07/17 16:10:44
総当りするしかないだろ。
244:笹井奈琴
06/07/17 16:10:57
>>242
宿題スレの方が
245:デフォルトの名無しさん
06/07/17 16:11:46
std::next_permutation？
246:デフォルトの名無しさん
06/07/17 16:11:57
>>242
ルール説明が雑すぎ
247:デフォルトの名無しさん
06/07/17 16:51:29
>>242
順列の計算習うのって中学だっけ高校だったっけ。
248:デフォルトの名無しさん
06/07/19 19:50:12
様々な大きさの矩形を整列させるアルゴリズムって既に有名な方法があります？
具体的には、横:sx 縦:syの大きさを持つ長方形を、なるべく無駄が出ないように
正方形の中に敷き詰めるような動作です。
//-----------------------------------------------------------------
struct SIZE { int sx; int sy; };
struct POINT { int x; int y; };
const int nBoxCount = 1000;
SIZE box[nBoxCount] = {{10,10}, {7,5}, {3,8}, ...こんな感じで1000個
POINT pos[nBoxCount]; // ←ここに整列後の位置座標を保存する
//-----------------------------------------------------------------
敷き詰め先の正方形のサイズは問いません。
（後でスケールを調整して、0.0～1.0の浮動小数点座標に変換するので）
「なるべく無駄なく」「正方形に」敷き詰める事を重視してます。
とはいえ、整列時に矩形の辺同士を無理にくっつける必要はありません。
上記を満たすようなアルゴリズムが既に存在しているようなら、
そのアルゴリズム名を教えていただけませんか？
（話を単純化させるため、こんな書き方をしましたが、最終的には
3D空間内全ての４頂点ポリゴンを平面投影し、それらを
正方形面＝テクスチャUV空間 に敷き詰める動作をさせたいです）
249:デフォルトの名無しさん
06/07/19 19:52:44
遺伝的アルゴリズムでそんな研究が合ったような気がするなあ……
250:デフォルトの名無しさん
06/07/19 20:08:25
>>248
全部の組み合わせを評価するってのはダメなの？
一つの正方形に1,000個落とすって、枠に対する長方形の大きさが小さすぎて、
現実的に意味なくない？ ランダムに落としても、さほど差がないように思う
けれど。
251:デフォルトの名無しさん
06/07/19 20:18:41
なんか、丸の問題なら見たなー
それは、箱の中に数個の点を置きそれをちょっとづつ大きくしてくのだったかな・・・・？
これでやるときは、ランダムに座標を取って、ちょっとづつサイズを大きくしていき
当たり判定で、やるんだっけか？
まあ、プログラミング習ったばっかで読んだから忘れた
252:デフォルトの名無しさん
06/07/19 20:19:55
と書き終わってみたら、長方形じゃ無理か・・・・・
253:デフォルトの名無しさん
06/07/19 20:36:33
ネスティング(Nesting) アルゴリズムで検索してみ
普通は任意形状の配置だけど
254:デフォルトの名無しさん
06/07/19 20:40:36
>>248じゃないけど。
>>250
> 全部の組み合わせを評価するってのはダメなの？
理論的には出来るけど、何通りになると思う？
1000個の長方形を単純に一列にならべるだけで1000! 通り（大きすぎてよくわからん）
各長方形の縦横の向きまで考えれば、上の組み合わせにさらに2^1000をかけたものになる。
255:248
06/07/19 20:47:59
>>249-254の方々、色々な情報ありがとうございました。
>>253
素晴らしいです！
かなりヒントになりました。
この辺キーワードで検索かけまくって、お勉強いたします。
256:デフォルトの名無しさん
06/07/19 20:54:38
Expose?
257:デフォルトの名無しさん
06/07/20 04:06:59
↓こんな処理を考えています。
// 「 former は latter よりも前にこなければならない」という順序付け
struct ordering { int former, latter; };
// M 個の順序付け orderings に基づいて [0, N) の整数を並べ替えた結果を
// sorted に格納する。
// ただし orderings の全ての要素について former != latter であることが
// 保証されており、矛盾する順序付けも含まれていないとする。
void sort_by_ordering_set( int sorted[] , int N
, struct ordering const orderings[] , int M );
・この処理（問題）に、何か良く知られた名前が付いていればおしえてください。
・N, M に対する複雑度はどれぐらいになるでしょうか？
・お勧めのアルゴリズムがあれば教えてください。
ここ数日、仕事の片手間にいろいろ考えているんですが、
速度を無視した実装すらできていません。
今は make のソースでも見たらいいんだろうか、とか思っています。
258:デフォルトの名無しさん
06/07/20 04:34:04
トポロジカルソートでぐぐれ
259:デフォルトの名無しさん
06/07/20 12:46:21
>速度を無視した実装すらできていません。
Javaでやってみました。
void sortByOrderingSet(int[] sorted, int[][] orderings) {
boolean[] visited = new boolean[sorted.length];
for (int p = 0; p < sorted.length;) {
YET:
for (int i = 0; i < sorted.length; i++) {
if (visited[i]) continue;
for (int j = 0; j < orderings.length; j++)
if (i == orderings[j][1] && !visited[orderings[j][0]])
continue YET;
visited[sorted[p++] = i] = true;
}
}
}
260:デフォルトの名無しさん
06/07/20 13:38:35
>>257
アルゴリズムの話じゃないが "latter" は "later" に直しとかないと
恥かくんじゃないか？
261:デフォルトの名無しさん
06/07/20 13:59:10
半順序関係ってかっこいいよね
262:デフォルトの名無しさん
06/07/20 14:27:04
>>260
former / latter はごくごく一般的な単語
恥かいてるのはあんただよ
263:257
06/07/21 00:46:55
>>258, >>259
ありがとうございます。道が開けました。
264:デフォルトの名無しさん
06/07/30 09:44:29
おまいら、半順序木からデータを探すとき、どのくらいの時間がかかるますか？
0(n)くらい？それともちょっとくらいは速くできる？
265:デフォルトの名無しさん
06/07/31 01:32:32
半順序木だけでやるなら計算量の意味では O(n) が限界。
ランダマイズとかすると減るかもしれんが。
構築段階から手を加えて良いなら、半順序木に要素が追加されるときに
ハッシュか何かにその要素を追加し、以後木に編集がかかったときに
ハッシュと同期する、とかいうのが常套手段。
266:デフォルトの名無しさん
06/08/08 20:46:26
x が与えられたとき，2^(a+1) > x ≧ 2^a となる 2^a を高速に(ループ等を使わ
ず，できればビット演算のみで)求める方法を探しているのですが，そういうア
ルゴリズムご存じの方いらっしゃらないでしょうか？
言語は C です．
267:デフォルトの名無しさん
06/08/08 20:58:58
それは俺も知りたい。
(int)(log(x)/log(2))
じゃマズいよな。
268:デフォルトの名無しさん
06/08/08 21:35:37
最上位ビット以外を0にすれば良いわけだな。
(x & x-1) ^ x
で最下位ビットが取り出せるので、前後でビットを逆に並べ替えれば良いんだが、
思いつかん。
269:デフォルトの名無しさん
06/08/08 22:48:06
>>266
ビット演算スレがあるから覗いてみたら?
270:デフォルトの名無しさん
06/08/08 22:52:02
>>268
ま、どうでもいいけどx&-xのほうがクール
271:デフォルトの名無しさん
06/08/08 22:59:39
>>270 それだと負の数の表現形式が問題になって嫌な予感。
272:デフォルトの名無しさん
06/08/08 23:08:41
>>266
ビット数決めうちなら以下の手がある(CPU依存の命令使うという手もあるが省略)。
x |= x>>1
x |= x>>2
x |= x>>4
x |= x>>8
x |= x>>16
x ^= x>>1
273:デフォルトの名無しさん
06/08/08 23:09:04
>>296
情報有り難うございます．書き込んでみました．
274:デフォルトの名無しさん
06/08/08 23:12:36
>>272
有り難うございます．
定石があるものとばかり思っていたのですが，意外と難しいんですね...
これから解読してみます．
275:272
06/08/08 23:19:30
>>274
実は上のコードはビット演算マニアから言えば定石だったりする。
もし、詳細が知りたければ「ハッカーの楽しみ」という本を読めばいい。
無駄に深い知識を得ることが出来る。
276:デフォルトの名無しさん
06/08/08 23:25:27
>>275
そういえば積ん読してあったなぁ，と思って探してみたら出てきました．
p.51 のやつですね．
理解にかかる時間が節約できそうです．有り難うございました．
277:デフォルトの名無しさん
06/08/09 20:05:19
おまいらマニアつーかヲタクです。
278:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/09 20:51:18
んで、変換対象のデータが複数ある場合はSSE2を使うと。
static const __m128 fp_mask = { 0xFF800000, 0xFF800000, 0xFF800000, 0xFF800000 };
__asm cvtdq2ps xmm0, xmmword ptr [vsrc] ;//32bit整数×4をロードし単精度×４に変換
__asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
__asm cvtps2dq xmm0, xmm0 ;//32bit整数×４に変換
__asm movdqa xmmword ptr [vdest], xmm0 ;//結果をストア
対象データが大量にある場合、まっとうな方法よりこれが一番スループット出るんだよね
ソフトパイプラインでレイテンシ埋めれば完璧。
279:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/09 20:52:44
× __asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
○ __asm andps xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
演算結果から言えば同じなんだけど
280:デフォルトの名無しさん
06/08/10 11:13:28
>>279
素朴な疑問なんだけど、その両者の違いは32ビット単位か64ビット単位かってことだよね。
実際のCPUの動きとしては、何か違うの?
それと、対象データが大量にあるなら>278のfp_maskはxmmレジスタにロードした方がいいのかな?
281:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/10 20:32:47
CPUの実装にもよるんじゃないかな。
たとえばCore 2 Duoの技術情報には、SIMD整数命令とSIMD浮動小数命令を
同じレジスタ上で混ぜて使うとペナルティが生じるという趣旨のことが書かれてる。
見映え的にも型に合ってない命令を無闇に混ぜないほうがいいかな、と。
「movapsとmovapdとmovdqaって何が違うんだ？」と思ってロード帯域計ってみた
ことがあるけど、若干差が生じるんだよな、なぜか。
でもCPUによっては生じないかも知れない。
> fp_maskはxmmレジスタにロードした方がいいのかな?
基本的にはそう。
ロード帯域に余裕がある場合は、レジスタを定数1個のために占有するよりは
処理の並列化のために使った方がいい場合も無くはない。
282:280
06/08/11 01:50:01
>>281
なるほど、解説THX。
283:デフォルトの名無しさん
06/08/13 11:31:18
ある２つの文字列が「どの程度同じか」を見つけるアルゴリズムを教えて下さい。
例えば「aあいうえおbbb」と「ccあいうえおeeee」は『大体同じ』と判断したいのです。
この例の場合「あいうえお」の部分が同じな訳ですが、これが「あ いうえ お」とか
「あいう-えお」でも、「あいうえお」と同じとみなしたいです。
人間が目で見れば、「大体同じ文字列」というのはすぐ分かるのですが、
これをどうやってプログラムで実現すればいいのか・・・
284:デフォルトの名無しさん
06/08/13 11:39:05
LCSとは違うの？
285:デフォルトの名無しさん
06/08/13 12:11:11
>>284
ＬＣＳって何でしょうか・・・？
ググッてもよく分からない・・・
286:デフォルトの名無しさん
06/08/13 12:23:38
Longest Common Subsequence
287:デフォルトの名無しさん
06/08/13 12:43:03
>>286
成る程、深く研究されているんですね・・・
Windows 上で使えるプログラムやライブラリ、
DLL 等があれば教えて下さい。
比較する文字列を 2 つ渡すと、何 % 一致しているかを
返す関数みたいなのがあるといいのですが・・・
288:デフォルトの名無しさん
06/08/13 13:35:09
ライブラリは知らんが、O(nm) の実装なら
URLﾘﾝｸ(en.wikipedia.org)
にある。そんなに複雑ではないので、参考にして書いてみたらどう？
289:デフォルトの名無しさん
06/08/13 16:31:43
Smith-Watermanかな
あとDNA配列の一致を調べるのと似てるからそれ関係を見てみると面白いかも
BLASTとかFASTAとかだっけかな・・・
290:デフォルトの名無しさん
06/08/13 21:37:50
URLﾘﾝｸ(www.topcoder.com)
のアルゴリズム部門に挑戦してみようという人はいないか？
現在、日本は、21位だぞ。
URLﾘﾝｸ(www.topcoder.com)
291:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/13 21:50:09
AGREPはどーよ
URLﾘﾝｸ(www.tgries.de)
292:SOURCE ◆tAo.kQ2STk
06/08/13 23:48:19
>>290-291
英語は苦手だ。
293:デフォルトの名無しさん
06/08/14 00:03:48
インテルで最適化コンテストやってなかったっけ?
#あれだとアルゴリズムレベルでの工夫の余地はないのかな。
294:デフォルトの名無しさん
06/08/14 01:42:06
>>293
でもまあ機械語いじるのもパズル的な部分はあるし面白そう
オレは無理だが
295:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/14 02:00:58
ソースコード読むのに英語か日本語かなんて関係ないだろ
296:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/14 02:01:48
英語のドキュメントが読めないって致命的になるから勉強したほうがいいよ。
297:デフォルトの名無しさん
06/08/14 02:06:51
ﾜﾛpｗｗｗ
298:デフォルトの名無しさん
06/08/14 11:30:45
>296 言語による
299:デフォルトの名無しさん
06/08/14 13:35:15
>>283
URLﾘﾝｸ(hp.vector.co.jp)
は？
経路を記憶するコードを追加すればdiffも簡単にできる。
一致度の%も、定義によって異なってくるが間単に計算できる。
300:デフォルトの名無しさん
06/08/14 14:24:54
>>299
自分でそのコードを書く事は出来そうもないので、>>287 の様な
「比較する文字列を 2 つ渡すと、何 % 一致しているかを返す」
様なツールというか関数を探してます・・・
でもないみたいですね。
301:デフォルトの名無しさん
06/08/14 14:48:05
自分で書けよ……
302:デフォルトの名無しさん
06/08/14 17:48:51
擬似コードが載っているんだから書けるべ。
>299見て書けないならプログラマに向いてないよ。
303:デフォルトの名無しさん
06/08/14 19:27:46
>>300
出鱈目書いてよこすが、こんなもんでいいだろうか？
double cmpstr(char *buf1,char *buf2,int size){
int i,j
j=0;
for (i==0;i>=size-1;i++){
if (buf1[i]==buf2[i]){
j++;
}
}
return j/(size-1);
}
304:デフォルトの名無しさん
06/08/14 19:29:01
あ、最後から2行目
return j/size;
だ。
305:デフォルトの名無しさん
06/08/18 19:20:05
>>300
phpのsimilar_textのソース読んでみてはどうだろう。
O(n^3) くらいだったような気がするが。
306:デフォルトの名無しさん
06/08/21 18:26:00
スローすぎてあくびが出るぜ
307:デフォルトの名無しさん
06/08/21 21:15:47
おまいら自分用のアルゴリズムライブラリとか持ってますか？
308:デフォルトの名無しさん
06/08/22 17:20:55
日本語でおｋ
309:デフォルトの名無しさん
06/08/23 21:44:59
脳内訂正能力の低下が顕著
310:デフォルトの名無しさん
06/08/26 22:50:35
脳内訂正能力を利用した圧縮アルゴリズム
311:デフォルトの名無しさん
06/08/26 23:06:40
昔々、あるところに、おじいさんとおばあんがいました。
おじいさんは山へ芝刈りに、おばあさんは川へ洗濯に行きまた。
おばあさん洗濯をしていると、
大きな桃がどんぶらこっこどんぶらっこと流れてきました。
312:デフォルトの名無しさん
06/08/27 19:34:13
そこで、おばあさんは
「おお、なんと大きな桃じゃ！」
と言い、嬉しそうに丸呑みにしました。
313:デフォルトの名無しさん
06/08/28 00:51:56
>>311
脳内訂正能力を利用した圧縮ですよね？
おばあん ← １文字圧縮
芝刈り ← ”柴刈り”を暗号化
行きまた ← １文字圧縮
おばあさん洗濯 ← １文字圧縮
どんぶらこっこどんぶらっこ ← １文字圧縮
314:デフォルトの名無しさん
06/08/28 21:51:15
暗号化は意図しない動作でした
315:デフォルトの名無しさん
06/08/29 18:42:20
二次元平面において、線分と単純多角形が与えられたとき、
線分が多角形の内部を通るかどうかを判定する簡単な方法があれば教えてください。
幾つか自分でもやってみたのですが、線分が多角形の端点と重なる場合などで
正しい結果が出ませんでした。どなたかお願いします。
316:デフォルトの名無しさん
06/08/29 19:29:07
>>315
「単純多角形」の定義は何？
317:デフォルトの名無しさん
06/08/29 19:43:53
「多角形の端点」もおかしい。
318:デフォルトの名無しさん
06/08/29 19:51:56
「線分が多角形の端点と重なる場合など」（頂点や辺の意味だろうけど）を
内部を通ることにするかしないか自分の定義しだいじゃないのか？
319:デフォルトの名無しさん
06/08/29 21:24:34
グラフの自動レイアウト関係で参考になるアルゴリズムや考え方はありますか？
重力・斥力でやっているけれどいまいち効率の挙動が悪いんで素。
320:315
06/08/29 21:27:34
>>316
単純多角形とは自己交差を持たない穴の開いていない多角形のことです。
このとき、多角形は境界をなす頂点の列を用いて表現できます。
>>317
単純多角形の境界をなす頂点のことを「端点」と表現しました。
>>318
それを曖昧にしないように、「内部」という言葉を使ったのですが、説明不足でした。
境界と共有点を持つケースは、交わらないと判定したいのです。
よろしくお願いします。
321:デフォルトの名無しさん
06/08/29 22:22:40
>>307
10年以上育ててたのが、HDと共に逝った
322:デフォルトの名無しさん
06/08/29 23:12:41
まず >>318 の言うとおり自分でどういう判定をしたいのか定義する
あとはひたすら図を書いて場合分けするしかないよ
323:デフォルトの名無しさん
06/08/29 23:14:29
>>321 悲惨。それも10年以上。当然、こんなときどうするかバックアップなどのアルゴリズムは考えあるんだろうね？
324:デフォルトの名無しさん
06/08/29 23:55:14
>>315
つURLﾘﾝｸ(www.google.co.jp)
325:デフォルトの名無しさん
06/08/30 00:19:19
>>315
0 線分の始点が多角形内部にあるときは交差あり
1 多角形を反時計回りに正規化
2 多角形の全ての頂点を登録(配列1)
3 線分の始終点を頂点として登録(配列2)
4 線分と多角形の交点を(配列1)と(配列2)に新しい頂点として順序良く挿入。
ただし別の頂点と重なるときは登録しない。
5 全ての交点(配列1の点Nと配列2の点Mが同じ座標とする)について、
(配列1)の前後の頂点と合わせた３点N-1,N,N+1、(配列2)の頂点Mに着目して
6 M-1が存在してM→M-1がN-1→N→N+1の左側に出て行く線なら交差あり
7 同様にM→M+1がN-1→N→N+1の左側に出て行く線なら交差あり
N-1→N→N+1は折れ線の場合もあるので注意。外積と内積を組み合わせて判定。
線分と多角形の辺が頂点以外で交差する典型的ケースをあらかじめ判定してもOK
326:デフォルトの名無しさん
06/09/13 01:29:07
aはビットフラグで、メモリ、FDD、HDD、FANなどの故障状態を表しています。
bは条件です。FDDとHDDが両方故障なら2進で11です。
FDDとHDDが両方故障であるのを得るために2進の11がdefineしてあるのは
変更できませんが、FDDとHDDが両方故障であるのを調べるために
if ( a & b == b )
を実行するのには何か無駄がある気がしますが、もっとよい方法はありますか？
327:デフォルトの名無しさん
06/09/13 01:39:38
>>326
if ((a & FDD) && (a & HDD))
328:デフォルトの名無しさん
06/09/13 02:14:27
>>327
bの値もプログラム中で決定するので327のようにソースに直接書けません。
bを使ったプログラムにします。
bの条件を追加してFDDとHDDとUSBの3つとも故障で2進で111とした場合
もっとよい方法があれば教えてください。
329:デフォルトの名無しさん
06/09/13 02:47:44
>>326
「何か無駄がある気がします」なんて言われたら
どんな答えを出してもそういわれそうな気がして答える気にならない。
具体的に何が不満なんだ？
330:デフォルトの名無しさん
06/09/13 04:11:56
データ構造選んだ時点で
どのアルゴリズムが使えて
どのアルゴリズムが使えないかが決まってくるわけで
331:デフォルトの名無しさん
06/09/13 05:04:37
最適になるようにアルゴリズムとデータ構造を選択するのがプログラマの仕事。
ヒント：青い鳥
だな。理想を求めるのはいいけど、いつまでたっても納品できない悪寒。
ヲレライブラリを失わないためのヲレ危機管理アルゴリズムが不十分だったという検証ができたというヲチか。
バックアップぐらい危機管理の基本中の基本だぜ。
プログラマって人生設計も立てられずに人生のアルゴリズムもなくイベントドリブンで生活してそうだな。
332:デフォルトの名無しさん
06/09/13 05:12:48
なかなか厳しいな～
特にイベントドリブンテところが痛いな～
そんなプログラマに救いの手を♪
333:デフォルトの名無しさん
06/09/13 12:56:27
反復部分文字列の検索アルゴリズムを考えてます。
反復部分文字列とは一つの文字列中に複数回出現する文字列のことで
1.同じ反復部分文字列同士は重なりあわない(ABCABCABC => ABCと抽出 ABCABCは抽出しない)
2.反復部分文字列の部分文字列も反復部分文字列だがそれは抽出しない(ABCDEABCF => ABCと抽出 A B C AB BC は抽出しない)
という条件付きで2回以上出現するもので長さn以上の文字列を検索したいのです。
現在ドットマトリックス(str[i]==str[j]の値の行列を作り対角線方向に検索する方法)による検索しか思いつきませんが何か高速なアルゴリズムはありませんでしょうか？
SEQUITURアルゴリズムをいじれば早くなるかと思ったのですが条件を満たす文字列の一部しか見つけられないので悩んでます。
334:デフォルトの名無しさん
06/09/13 13:19:13
2つの任意の整数の組(a,b)が任意の数だけあるとする。
ただしa<bは常に満たされる。
『例えば「(2,4)(2,3)(1,6)(4,8)」の場合、
(2,4)(2,3)(4,8)は(2,3,4,8)という組を作る。』
というアルゴリズムを考えているのですが、いい方法が全く思いつきません。
分かる方、ヒントをください！
335:デフォルトの名無しさん
06/09/13 13:32:15
ハッシュ辞書使って、検索早めるのはどうよ。
gif なんかの LZW エンコードのソースに書かれているよ。
336:333
06/09/13 13:43:52
>>335
なるほど！圧縮でも部分配列の検索を利用しますね。そちら方面で調べてみます。
337:デフォルトの名無しさん
06/09/13 13:45:10
>>334
意味が今ひとつわからん。
かっこの中の数字のペアを数学で言うところの同値関係と考えて
その同値類に分けた集合をつくるってことか？
338:デフォルトの名無しさん
06/09/13 13:52:17
グラフのレイアウトで参考になるアルゴリズムはありませんか？
ノード間に関係を表すエッジが複数あるとしてランダムに表示されたノードを関係あるものを近くに表示させたいと思っています。
バネモデルなどを使った力学的モデルを使った配置の考え方は見つけたのですが、実行してみるとかなり遅くなってしまいます。
別に見つけた商用ライブラリyFilesのサンプルを使ってみるとあっという間に終わり何か別種のアルゴリズムを使っているとしか思えません。
URLﾘﾝｸ(www.yworks.com)
何か考え方のヒントになるようなものでも助かるので何かないでしょうか。
339:デフォルトの名無しさん
06/09/13 23:14:17
>>326
URLﾘﾝｸ(oshiete1.goo.ne.jp)
ふてぇ野郎だ。
340:338
06/09/14 23:56:30
おしえてGoo煮出してみます。
スレ汚しすいませんでした。
341:334
06/09/15 04:22:02
>>337
ちょっと調べたのですが、同値関係？同値類？という状態です。
いま作ろうとしているのはN体問題に衝突･合体を組み合わせるため、
『どの物体が、どの物体へ衝突したか』
を判定するアルゴリズムです。
衝突したことが直接判定できるのは2つまで(物体a,物体b)で、
3つ以上が同時に衝突する場合、衝突に関与した物体はこの(a,b)の組み合わせから
判断しなければなりません。
「(2,4)(2,3)(1,6)(4,8)」の場合、合体して新たな物体を生じるのは
(2,3,4,8)(1,6)であることを見つけ出そうとしています。
なんだか長くなってしまいましたが、少し自分でも考えてみます。
342:デフォルトの名無しさん
06/09/15 07:53:27
>>341
「衝突・合体」 だけだったら Union Find．
分離もしたくなったら，単一要素を分離するだけなら Union Find Split，
接続している要素の切断なら Euler Tour Tree とか Topology Tree とか．
343:デフォルトの名無しさん
06/09/15 20:46:34
>>341
Pythonで作ってみた
（実際の言語固有の便利さを、どこまで使っていいのか良くわからん）
Data = ((2,4), (2,3), (1,6), (4,8))
ResultLists = []
TmpHash = {}
for (X,Y) in Data:
if not (X in TmpHash):
if not (Y in TmpHash): #両方の数字が初めて出てきた場合
TmpHash[X] = [X, Y] #新しくリストを作成
TmpHash[Y] = TmpHash[X] #もう一方の数のハッシュを作成
ResultLists.append(TmpHash[X]) #結果リストに追加
else: #片方の数字(X)のみが初めて出てきた場合
TmpHash[Y].append(X) #既出の数字のハッシュのリストに初めての数字を追加
TmpHash[X] = TmpHash[Y] #初めての数字のハッシュを作成
else:
if not (Y in TmpHash): #片方の数字(Y)のみが初めて出てきた場合（以下同様）
TmpHash[X].append(Y)
TmpHash[Y] = TmpHash[X]
print ResultLists
344:デフォルトの名無しさん
06/09/16 06:12:16
>>343
間違ってる．そのプログラムを
Data = [ (1,2),(2,3), (4,5),(5,6), (3,4) ]
で実行すると
[[1, 2, 3], [4, 5, 6]]
になるが，正しくは
[[1, 2, 3, 4, 5, 6]]
になるべき．
345:デフォルトの名無しさん
06/09/16 07:15:24
Python で作ってみた．Python よく知らんので拙いコードな気がする．
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
346:334・341
06/09/17 05:13:19
ありがとうございます！
アルゴリズムの本を何冊か当たっても出なかった問題が
即座に出てくるなんて、2chの中の人すげー
いまからPython勉強します
347:デフォルトの名無しさん
06/09/17 06:35:03
いまだに>>334の数字にペアがなにを表してるかわからない自分は逝ってよしですか・・・orz
348:デフォルトの名無しさん
06/09/17 06:45:33
>>347
・物体 {1, ..., n} がある．
・物体同士の衝突を検査する関数 check(a,b) がある．
・衝突した物体は粘土のように合体する．
という設定で，
衝突している物体対のリスト [ (a_1,b_1), (a_2,b_2), ... , (a_m,b_m) ] が与えられる．
衝突して合体した結果，どのようになるか調べよ．
という問題．
349:デフォルトの名無しさん
06/09/17 09:56:40
C#でやったらこんなんになった。逝ってくる・・・orz
URLﾘﾝｸ(uploader.erv.jp)
350:デフォルトの名無しさん
06/09/17 10:30:32
複数の物体があるとして関係があるもの(これはユーザーの定義などにより設定される)はある程度近くなり、また物体同士で近すぎるものはある程度の距離を保つようにしたいと思います。
ここで計算して少し動かしてまた計算してとやってたんですが、微分積分などを使って一発でやることって可能ですか？
351:デフォルトの名無しさん
06/09/17 20:09:21
>>346
あたる本がよろしくないんだな．
セジウィック「アルゴリズムC」，CLR 「アルゴリズムイントロダクション」など
まともなアルゴリズムの本なら最小全域木との繋がりでたいてい書いてあるよ．
352:デフォルトの名無しさん
06/09/17 20:24:17
>>350
問題設定がよくわからん．
「物体」とか「関係」とか言わずに，どんな問題を解きたいかを
はっきり述べてくれたほうがよい．
問題だけ見ると >>338 と同じような気がするんだが．
353:デフォルトの名無しさん
06/09/18 13:07:51
>>350
３体問題を解決してフィールズ賞取れよ、って言ってるのかな？
簡単にできる場合と難しい場合があることくらいまでは俺にも分かるが、できない場合があることを証明するのは俺には荷が重いな。
354:デフォルトの名無しさん
06/09/18 13:09:27
>>352 あー同じようなもんです。
>>353 やっぱりそういう話ですよね。
355:デフォルトの名無しさん
06/09/18 14:07:45
B木をファイルとして実装する方法で詳しいサイトないですか
356:デフォルトの名無しさん
06/09/18 17:31:47
>>350
じゃあ 352 と同じ問題だと思って回答するぞ．
力学モデルは十分実用的のはずで，小規模系で遅いとしたら
時間刻みが細かすぎるか，用いてる力学モデルが致命的に悪い．
特に時間刻みは重要で，別にシミュレーションするわけじゃないんだから
かなり大雑把に計算しても大丈夫．数値安定性が保たれる限界くらいの
刻みに選んでも平気．
大規模系で遅いとしたら，アルゴリズムの改良が必要．
たとえば高速多重極展開なんかは有力な解決になりうる．
357:デフォルトの名無しさん
06/09/18 17:33:31
352 は 338 のミス
358:デフォルトの名無しさん
06/09/18 20:11:35
>>356
表示しながら収束状況を見てると、ノードが行ったり来たりしてるのは問題外ですよね・・・
359:デフォルトの名無しさん
06/09/19 11:44:17
>>338
こういうのって初期配置も結構重要だと思うんだけど、その辺意識してるのかな？
360:デフォルトの名無しさん
06/09/19 15:07:25
yEdすげー
361:デフォルトの名無しさん
06/09/19 17:46:49
.kjm;:,ok:k,;uhbvxew6te4z64c
362:デフォルトの名無しさん
06/09/20 00:11:27
>355
363:338
06/09/20 01:17:57
>>359
やってるうちに初期配置がかなり重要なことはわかってきました。
今は初期配置をうまくやるアルゴリズムを一つ思いついたので今度試してみるところです。
ただ、初期配置をうまくやってその後収束させる方向が正しいのか、全く違うやり方があるんじゃないかとヒントを探してるところです。
364:デフォルトの名無しさん
06/09/20 09:06:03
>>363
ノードを同心円状に配置するのはどうだろう。
グラフのあるノードを中心として、距離1のノードは半径1の円周上に等間隔に配置。
距離2のノードは半径2の円周上に…という感じ。
この方法で以前試した時は、そこそこうまくいった覚えがあるが、
グラフがツリーに近い形状だったからかもしれない。
力学モデルを使っていて遅いとのことだけど、
パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
それから移動量を小さくして微調整すると良いと思う。
もう既にやってるかもしれないしけど…
あと、遅くなる原因としてもう一つ。
これは自分がやったミスで、
収束するのが遅い遅いと思っていて、原因を探るために処理ごとの所要時間を取ってみたら、
実はグラフの収束を確認するための描画に時間がかかっていただけという情けないのもあった。
1回動かすたびに毎回描画なんてしてたから当たり前なんだけど。
365:364
06/09/20 09:08:07
> パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
> それから移動量を小さくして微調整すると良いと思う。
力学モデルなら自然とこうなるな…申し訳ない。
366:デフォルトの名無しさん
06/09/20 09:33:39
プロファイルぐらい取ればどこで遅いかぐらいは一目瞭然でしょ。
367:デフォルトの名無しさん
06/09/20 22:29:42
そういう話をしてるんじゃなくてな
368:デフォルトの名無しさん
06/10/30 00:19:45
エレベータで全押しする奴を止めるアルゴリズム作って
369:デフォルトの名無しさん
06/10/30 00:23:34
>>368
ボタンを押したら新しいボタンが表示される、ってシステムならＯＫ
370:デフォルトの名無しさん
06/10/30 14:05:21
同じボタンずっと押したらキャンセルとかつけてほしい
371:デフォルトの名無しさん
06/10/30 14:09:06
ダブクリでキャンセルできるエレベーターとかはあるよ
372:デフォルトの名無しさん
06/10/30 22:16:57
>>368
考え方が間違ってる
全押ししても正常に動作するようにする方法を聞くんだ
373:デフォルトの名無しさん
06/10/30 23:51:04
操作に論理ミスがあっても正常に動作する方法ってどんなんだ
374:デフォルトの名無しさん
06/10/31 00:28:29
エラー出せば？
375:デフォルトの名無しさん
06/10/31 01:51:53
全階ボタン押したらエラーが出るエレベータ
376:デフォルトの名無しさん
06/10/31 11:21:22
例外処理でワイヤー切断
377:デフォルトの名無しさん
06/10/31 13:23:34
エレベーターガールを配置する。
378:デフォルトの名無しさん
06/10/31 13:33:33
エレベーターガールがエレベーターアーント気味なのは仕様です
379:デフォルトの名無しさん
06/10/31 18:03:27
エレベータを止めるのではなく、全押しした奴を止めたいなら、このほかに縄が必要だな。
#define N 適当な数
if (押されたボタンの数>重さセンサが感知した量/60kgf+N)
{
SpeakMessage("ボタンが押されすぎです。一旦消します。");
UnlitAllButtons();
}
//地震とかで全押しする必要がある場合の処理をしていません。
380:デフォルトの名無しさん
06/10/31 20:45:55
全押しされた時点で一番近い階に止まったら
ボタンすべてキャンセルすればいんじゃね？
もし本当に必要ならもう一度押すだろうし。
381:デフォルトの名無しさん
06/11/01 12:27:53
>>380 こういうあほな使用を実システムでも作ってないかと心配になる
382:デフォルトの名無しさん
06/11/01 21:02:26
質問自体がネタなんだからいいじゃん。
そもそも、エレベータに全押し対策機能つけようと思う奴、いるわけないだろ？
(本当につけたら、誤認識の嵐で、相当使いづらいエレベータになるからね。)
あくまで、架空のエレベータの話だ。
383:デフォルトの名無しさん
06/11/02 00:46:53
実際に、ボタン長押しでキャンセルされるエレベーターがあるわけだが。
384:デフォルトの名無しさん
06/11/02 00:57:38
そんな話はしていない。
385:デフォルトの名無しさん
06/11/02 01:16:37
で、381のエレガントな解法は？
386:デフォルトの名無しさん
06/11/02 09:57:51
全ボタンに指紋読み取り機能を実装し、複数人によって全押しされた場合は有効。
一人により全押しされた場合は、全てのボタンをキャンセルし、移動方向直近の階に停止させ
上からタライと小麦粉を落とす。
387:デフォルトの名無しさん
06/11/02 11:24:36
水 → 小麦粉 → タライ
がベスト
# 同一人が違う指で押したらどうする？
388:デフォルトの名無しさん
06/11/02 11:33:34
エレベータに乗るドアに目的階のボタンが無いのはなぜなんだぜ？
389:デフォルトの名無しさん
06/11/02 13:02:30
新しいぜ。 疑問断定形。
390:デフォルトの名無しさん
06/11/02 17:01:50
>>386
親切な人いるじゃん。
ボタンの前に立つと、「何階ですか？」と聞く人。
391:デフォルトの名無しさん
06/11/02 17:10:37
>389
半年(ry
392:デフォルトの名無しさん
06/11/02 17:11:22
エレベーターのお姉ちゃんは毎日タライの餌食
393:デフォルトの名無しさん
06/11/02 18:23:17
URLﾘﾝｸ(www.youtube.com)
394:デフォルトの名無しさん
06/11/05 00:45:48
>>392
押すボタンによって指を使い分ければok
395:デフォルトの名無しさん
06/11/06 09:31:35
普通，手袋してるっしょw
396:デフォルトの名無しさん
06/11/06 13:33:29
階層DFDを使って自分の費用・授業・図書のデータを管理するシステムプログラムを設計せよ
・費用は収入や食費・交通費・生活費等の支出等のデータを扱う
・授業は履修している、もしくは履修済みの授業、一週間の授業表等のデータを扱う
・図書は借りた本等のデータを扱う
ユーザーはこのシステムにIDとパスワードを使ってアクセスし、
データ倉庫user-dataに保存されている自分のデータを参照できるようにせよ。
プログラム設計っつー授業でこんな問題出されたんですが、
URLﾘﾝｸ(members.jcom.home.ne.jp)
階層DFDはこんな感じでいいんですか？
これをデータ辞書を追加したり、構造化英語で書いたり最終的にはJavaで実装できるようにしろとまで言われてます
397:デフォルトの名無しさん
06/11/06 15:09:16
開閉同時押しで目的階をクアドゥルプルクリック→目的階以外キャンセル
398:デフォルトの名無しさん
06/11/07 04:45:31
思ったんだけど、キャンセル機能とかついてると、
逆にいたずらされて降りられなかったり、
変質者とかに悪用されたりとかしない？
399:デフォルトの名無しさん
06/11/07 23:45:09
全部キャンセルされたら最寄り階で開くってことでどうでしょ。
400:デフォルトの名無しさん
06/11/08 09:41:00
かべのなかにいる!
401:デフォルトの名無しさん
06/11/08 15:31:16
ゆかのしたにもいるかも
402:デフォルトの名無しさん
06/11/08 16:11:00
クラーケンが現れた!
403:sage
06/11/08 22:14:54
優先度付き待ち行列をハッシュで効率よく実現する方法を教えてください。
404:デフォルトの名無しさん
06/11/08 22:19:18
優先度付きキューならヒープのほうが適任だと思うけど？
405:sage
06/11/08 22:25:26
＞404
連結リストとヒープは使うなという制約が…
平衡木も考えたんだが効率がいまいち。
406:デフォルトの名無しさん
06/11/08 22:59:06
平衡探索木でよいような？
一番左下へのポインタを持ちまわれば計算量的には同じになるはずだけど。
407:デフォルトの名無しさん
06/11/09 00:04:39
k個のソート済みのリストを入力し、それらを１つのソートされたリストにマージしたい。
単純な方法を用いるとO(kn)かかってしまう（ｎはｋ個のリスト中の要素全ての数）
ヒープを用いて効率よく実行する方法を述べその計算量を示せ。
408:デフォルトの名無しさん
06/11/09 00:11:14
>>407 宿題はお断り。
409:デフォルトの名無しさん
06/11/09 00:23:58
>>407
どのリストの先頭が最も小さいか、を管理するためにヒープを用いる。O(n log k)。
410:デフォルトの名無しさん
06/11/14 21:42:37
A(♂)→B(♀)
B(♀)→C(♂)
C(♂)→D(♀)
D(♀)→C(♂)
C(♂)→B(♀)
A(♂)＝俺
だれかこの問題を解決できる画期的なアルゴリズムを考えてくだちい
ていうかC(♂)氏ね
411:デフォルトの名無しさん
06/11/14 22:12:21
delete A(♂)
412:デフォルトの名無しさん
06/11/14 22:37:26
int main() {
C = A;
return 0;
}
413:デフォルトの名無しさん
06/11/15 17:18:05
>>334
超亀レスだが、ポインタ書き換えによる単一化を使うと効率がいい。
C#っぽい擬似コードで。public省略。Nは物体数。
class Pair { int a; int b; }
class Cell { int n; Cell(int n) { this.n = n; } }
Cell[] MakeUnifiedCells(Pair[] pairs) {
Cell[] cells = new Cell[N]; // 要素はnull初期化
foreach (Pair pair in pairs) {
Cell cellA = cells[pair.a]; Cell cellB = cells[pair.b];
if (cellA == null && cellB == null) {
cells[pair.a] = new Cell(pair.b);
} else if (cellA == null) { // assert(cellB != null)
cellB.n = pair.a;
} else { // assert(cellA != null)
cellA.n = pair.b;
}
}
return ret;
}
int GetEquivalenceClass(int n, Cell[] cells) {
while (cells[n] != null) n = cells[n].n;
return n;
}
まず、MakeUnifiedCells(Pair[] pairs)を使って、Cell[] cellsを用意する。
物体nがどの同値類に属するかは、GetEquivalenceClass(n, cells)で求められる。
414:413
06/11/15 17:18:46
GetEquivalenceClassの最適化版は↓みたいなかんじ。
int GetEquivalenceClass(int n, Cell[] cells) {
if (cells[n] == null) return n;
else if (cells[cells[n].n] == null) return cells[n].n;
else {
int ret = GetEquivalenceClass(cells[n].n, cells);
cells[n].n = ret;
return ret;
}
}