アルゴリズムオタク

アルゴリズムオタク ..

2:デフォルトの名無しさん
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。任意の長さの一致が全て判明する。

次ページ