アルゴリズムオタク
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん
2006/03/07(火) 23:06:03エレベーターを待っているときは、動きを制御するアルゴリズムを考えたり
既存のサブルーチンのアルゴリズムを考えたり、ゲームをやってても敵の
動きのアルゴリズムを考え、ストーリーなどは全く頭に入らない
愛読書は「アルゴリズムとデータ構造?」
言語なんて関係ない!アルゴリズムが好き!
0002デフォルトの名無しさん
2006/03/07(火) 23:25:310003デフォルトの名無しさん
2006/03/08(水) 00:12:31ttp://sidhes.hp.infoseek.co.jp/alg3.htm
0004デフォルトの名無しさん
2006/03/08(水) 00:18:320005デフォルトの名無しさん
2006/03/08(水) 00:21:060006デフォルトの名無しさん
2006/03/08(水) 00:36:20x = x ^ y;
y = x ^ y;
x = x ^ y;
これで x と y の値がいれかわるのだ!すごい
0007デフォルトの名無しさん
2006/03/08(水) 00:39:53http://www.dd.iij4u.or.jp/~okuyamak/Information/xor_fixed_swapping.html
0008デフォルトの名無しさん
2006/03/08(水) 00:48:55これが真に役立つ場面ってなかなかないんだよねぇ。
俺がいままでやった中ではフィボナッチ数列を求めるプログラムぐらい。
もっともそのまんまの形じゃなくて
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;
}
0009デフォルトの名無しさん
2006/03/08(水) 01:04:17インパクにぶちこまれ首振ってました。俺も掴まされてガセネタ食らい無様に
醜態さらしました。懲罰動議出されたときは一瞬引いたけど、兄貴の「いやなら
辞めていいんだぜ!」の一言で覚悟決め、生まれて初めて謝りました。そ
の後、幹事長・党首も晒しあげられてビンビンの冷や汗、思いっきり謝り派手に脳無し
タケベの顔に飛ばしました。スッゲー男らしく気持ちよかったです。また行くとき
カキコして下さい!帰ってからNHKのニュース見て、また感じまくってます!
0010デフォルトの名無しさん
2006/03/08(水) 02:01:06似たようなのでユークリッドの互除方が好き
0011デフォルトの名無しさん
2006/03/08(水) 02:56:080012デフォルトの名無しさん
2006/03/08(水) 05:46:38解説してるどっかの大学のオンライン講義資料知りませんか。
0013デフォルトの名無しさん
2006/03/10(金) 15:24:31とっておきのを思い付きました。
「検便アルゴリズム」です。
みんなで熱く語り合いませんか。
0014デフォルトの名無しさん
2006/03/10(金) 15:27:53最初に粗くshell sortしておくと速くならんかな。
細かい部分はinsertion sortして。
0015デフォルトの名無しさん
2006/03/10(金) 15:39:10marge sort使えって
0016デフォルトの名無しさん
2006/03/10(金) 15:39:46mergeだって
0017デフォルトの名無しさん
2006/03/10(金) 17:42:45略してアル中
0018デフォルトの名無しさん
2006/03/10(金) 17:45:53おまい、それを言いたいためだけにこのスレたてたんか?!
0019デフォルトの名無しさん
2006/03/10(金) 18:00:17おまいから、語ってみろよ
それはそうと、自己組織化のアルゴリズム教えてくれ
0020デフォルトの名無しさん
2006/03/10(金) 18:10:41ただこれだけだ。
0021デフォルトの名無しさん
2006/03/10(金) 18:35:33もうちょっと機能や用途を的確に表す分かり
やすいダイレクトなネーミングしろよ。
>見つけたデータを配列の先頭に移す。
自己組織化という名前とどう関係あるのかさっぱり分からない。
一度ヒットした検索の結果を頭に持ってくるようなことは
ちょっと気が利いたやつなら普通にやるが、そういう用途
なのか?
0022デフォルトの名無しさん
2006/03/10(金) 20:16:420023デフォルトの名無しさん
2006/03/10(金) 20:27:13猿ゴリズム = アルゴリズムと呼ぶには、あまりにも稚拙。
0024デフォルトの名無しさん
2006/03/10(金) 21:09:590025デフォルトの名無しさん
2006/03/10(金) 21:13:12再実装はさけられないしな。
0026デフォルトの名無しさん
2006/03/10(金) 21:16:59重要なのは楽しいかどうか
どうせ最終的にやることは変わらんしな
0027デフォルトの名無しさん
2006/03/10(金) 21:19:59どっちかというと、アルゴリズミストという感じがするな。
>>26
調べる訓練を十分積んでないと、再発明の方が心理的に楽なんだよな。
しかしそれまでに研究されたアルゴリズム上の穴や欠点が反映されない罠。
0028デフォルトの名無しさん
2006/03/10(金) 21:22:25「先進国アルゴリズム協会」(通称:SAK)は北半球の国々による
アルゴリズムの研究を目的とした公的機関である。
世界から優秀なSEやプログラマが集められており、年に数回の学会を催している。
最近有名なのは、画像ファイルからそれがエロ画像であるかを判定するアルゴリズムである。
これにより、エロ画像掲示板等向けの巡回ソフトを開発する際に、
余計なネタ画像を避けてエロ画像のみを収集することができ、日米を中心としたIT先進国も注目している。
0029デフォルトの名無しさん
2006/03/10(金) 22:06:49不当な文化の押し付けであるとして、アジアを中心とした人権団体から非難が出ている。
これに対しSAK側は沈黙を決め込み、半ば強引な進め方が行われており、
人権団体では、日米主体のエロ文化が蔓延するのではないかと懸念している。
0030デフォルトの名無しさん
2006/03/10(金) 23:03:140031デフォルトの名無しさん
2006/03/10(金) 23:18:540032デフォルトの名無しさん
2006/03/10(金) 23:23:11赤ん坊の写真まで除去されてしまう
0033デフォルトの名無しさん
2006/03/10(金) 23:57:410034デフォルトの名無しさん
2006/03/11(土) 00:00:160035デフォルトの名無しさん
2006/03/11(土) 02:30:37あるコントロールを作ってこれは角ならその方面のサイズを
辺ならその辺を基準にした高さを
右クリックなら回転を
マウス操作で行おうとしてるんですが
マウス座標はXYなので回転後の伸縮幅の計算でわけがわからなくなってしまった
三角関数が入り組んでる状態で頭がいたいので
どっかにサンプルころがってないですかね?
あるいはスマートに共通の関数とかで処理する方法があれば教えてください
0036デフォルトの名無しさん
2006/03/11(土) 02:37:32おまいの日本語がわかりにくい
回転移動の1次変換
ttp://www.geisya.or.jp/~mwm48961/kou2/linear_image3.html
0037デフォルトの名無しさん
2006/03/11(土) 02:40:370038デフォルトの名無しさん
2006/03/11(土) 03:01:51回転はできてます
例えば45度左にすでに傾いていた場合、上辺をドラッグして左右辺の長さを変えるわけです
マウスの位置に上辺が来ないといけないわけですが
マウスのY座標から左上と右上の角の座標が知りたいわけです
これは単純にサイズ変更だけじゃなくて移動もしないといけません
この時に回転軸も重心を取ってるのでずれてきます
上辺がマウスに重なるように下辺は固定したまま上辺だけを移動したいのです
0039デフォルトの名無しさん
2006/03/11(土) 03:21:33ぜんぶ自前で線描画した図形にしたらどーかね
0040デフォルトの名無しさん
2006/03/11(土) 03:54:06なにをゆっているのですか?
0041デフォルトの名無しさん
2006/03/11(土) 04:00:350042デフォルトの名無しさん
2006/03/11(土) 05:39:15リストから重複要素を取り除いたリストを得るアルゴリズムをお願いします。
高速なのをお願いします。
0043デフォルトの名無しさん
2006/03/11(土) 05:52:19じゃあもう少し要点をまとめるので答えてね
ある角度αで回転した四角形があります
左上角を(x,y)とします
上辺の中心を(x',y')とします
この中心をドラッグし移動するとマウスと上辺は交差する位置を維持します
下辺2点は固定です
この時いまマウスがいる座標を(x'',y'')とします
この座標と交差する上辺の左角の座標を求める計算式を提示してください
0044デフォルトの名無しさん
2006/03/11(土) 09:14:31>ある角度αで回転した四角形があります
どこを中心にどう回転したのか書いてないしな。
曖昧な情報を出してくる辺りネタとしか思えない。
もう帰っていいよ。
0045デフォルトの名無しさん
2006/03/11(土) 10:08:56ほんとに聞きたいなら、その部分コード書いて、判らない所をコメントにして聞いてくれよ。
>>42 リストって言ってるのはホントのリストだな Delphi/BuilderのTListじゃないね?
ただ、どういうリストなのか構造が判るようなコードで書いてくれよ。
じゃないと単なるリストならアルゴリズムもクソもリストを全部辿るしか方法ないじゃない
>>43 判りにくい。コードで書いて
0046デフォルトの名無しさん
2006/03/11(土) 10:54:14僕の考えた低速そうなアルゴリズムはこうです。
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);
0047デフォルトの名無しさん
2006/03/11(土) 11:31:540048デフォルトの名無しさん
2006/03/11(土) 12:20:29顔で判断するのか?
0049デフォルトの名無しさん
2006/03/11(土) 13:04:15Google イメージ検索
0050デフォルトの名無しさん
2006/03/11(土) 16:33:09重心って書いてるじゃんw
ばーか
0051デフォルトの名無しさん
2006/03/11(土) 16:34:56コードで書いたらもうほとんど答えでバグ広いだけじゃんw
ばかじゃねーの
0052デフォルトの名無しさん
2006/03/11(土) 16:42:16function (mouse, leftup, rightup, leftbottom, rightbottom, kakudo){
// mousex mouse.y が (leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するように
// leftup rightupを修正
// ↓
???????????
// ↑
return points
}
はいコードどうぞw
0053デフォルトの名無しさん
2006/03/11(土) 17:07:04ならそれで質問者は解決するわけで、みんなハッピーだ
>>52
つまり、(leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するのは、何?
0054デフォルトの名無しさん
2006/03/11(土) 17:09:350055デフォルトの名無しさん
2006/03/11(土) 17:11:500056デフォルトの名無しさん
2006/03/11(土) 17:13:090057デフォルトの名無しさん
2006/03/11(土) 17:17:420058デフォルトの名無しさん
2006/03/11(土) 17:18:13引き数の型が書かれていない
mouse, leftup, rightup, leftbottom, rightbottom, はpoints として kakudoは何?
それから leftbottom, rightbottom, kakudoはこの関数の動作に関係しないなら引き数にする必要はない
関係するならその説明をしないと意味がないだろう
0059デフォルトの名無しさん
2006/03/11(土) 17:19:33あのさ、この板でこの手の回答の半分はオレなの。
オレが答えなきゃ、回答率は半分になるよ。
0060デフォルトの名無しさん
2006/03/11(土) 17:22:31points は変化後のすべての座標の省略
形なんか好きにしろw
角度計算する際の常識的な形ってやつがあるだろ
使うか使わないかもわからないのかお前は?w
0061デフォルトの名無しさん
2006/03/11(土) 17:26:16オレはこの手の処理をするときは角度じゃなくて sin/cos成分を引き数で渡す。 これはオレの常識
つまり、これは関数というより手続きなんだね? それを表現してくれないといけない。
それで、入力としては mouse, leftup, rightup, leftbottom, rightbottom, kakudo
出力は何?
想像としては、
leftup, rightup, leftbottom, rightbottom の相対関係を固定して kakudoで回転させたいように思うが mouseはどういう拘束条件?
0062デフォルトの名無しさん
2006/03/11(土) 17:30:20角度reftupは90度rightupは90度を固定された
leftupとrightupを入れ替えて
返す
kakudoha現在の座標がその角度で回転されたものだって意味じゃぼけ
0063デフォルトの名無しさん
2006/03/11(土) 17:38:29判った事は
mouse, leftup, rightup, leftbottom, rightbottom が点座標
kakudo が 現在の座標の回転角 ここまでは判った
現在の座標の回転角とは何?
90度というの何と何の角度?
もしかして長方形? 長方形なら2点だけでいいよね?
0064デフォルトの名無しさん
2006/03/11(土) 17:41:03引数の数がその後の計算に影響するとは思えないんだが
自閉症なみのこだわりですねw
0065デフォルトの名無しさん
2006/03/11(土) 17:45:47じゃ、ムダな、2点を削除して
(POINT mouse, POINT p1 , POINT p2 , double kakudo) にしよう
左上p1と右下p2の kakudo で回転された 長方形があるとする。
このmouse上の点が上辺になるように 移動変換したい というのが疑問かい?
0066デフォルトの名無しさん
2006/03/11(土) 17:59:36W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
点 mouse にWが一致するように center を平行移動して返す関数を作れ。
でいいの?水平移動優先? 垂直移動優先?それとも最短移動距離優先?
0067デフォルトの名無しさん
2006/03/11(土) 17:59:560068デフォルトの名無しさん
2006/03/11(土) 18:03:51> この座標と交差する上辺の左角の座標を求める計算式を提示してください
これを翻訳すると
このmouse座標上に上左点が来るように center を設定せよ
これでいいんじゃないの?
0069デフォルトの名無しさん
2006/03/11(土) 18:05:03は違う気がする
0070デフォルトの名無しさん
2006/03/11(土) 18:08:51アーぜんぜん違うw
回転してない長方形があって上をひっぱると上に伸びるだけね
下は固定
これはその長方形を回転させた状態のときに同じく上にひっぱるわけ
0071デフォルトの名無しさん
2006/03/11(土) 18:13:57W
┌┐
││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))
という答えだったけど、これは問題が違うわけね。
ちょっとまってね
0072デフォルトの名無しさん
2006/03/11(土) 18:22:21┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
mouseを重心の位置が原点になるように回転移動逆変換する
rmouse=mouse.ROTATE(-kakudo).MOVE(-center)
問題:
rmouseのy座標の位置が上辺と一致し、下辺座標が変化しないように centerとHを変更せよ
って、事で、もう答え書く必要はないでしょ
007372
2006/03/11(土) 18:56:01自分を祝福したいよ。
0074デフォルトの名無しさん
2006/03/11(土) 20:56:07その説明だけじゃたりんがね
回転演算を3回しないといけない
書いててもスマートじゃないからなんかいい方法ないものかと聞いてみただけ
007572
2006/03/11(土) 21:17:43どっちかいうと問題が秘密で問題に到達するまでのゲームだったね。 けっこう面白かった。
問題が判らないから表現方法を模索した結果、こうなっただけで
実際のデータとしては四角形に固執せずに、任意多角形の問題として
マウスで図形を動かす=マウスの動きに対して何を拘束して何を追従させるかという
問題と捕らえて、一般的に解かせる方がいいよ。
図形を動かす方時のコストなんてしれてるから、多少リッチにCPUコストをかけさせてもいい
で、ここには単なる長方形ではなくて、この長方形にビットマップのようなものを貼り付けるんだろ?
だったら、そっちのコストがずっと大きいから
0076デフォルトの名無しさん
2006/03/12(日) 00:30:36与えられた情報を湾曲させ、猥褻な情報に変換するアルゴリズム。
文字列の変換に関するエロゴリズムが多く考え出されているが、
画像や音声に関してのエロゴリズム考案にもSAKは力を入れている。
文字列変換の例:
愛されて10万戸→愛されて汁マンコ
私の父はSEです→私の乳はSEです
0077デフォルトの名無しさん
2006/03/12(日) 00:39:420078デフォルトの名無しさん
2006/03/12(日) 01:11:41「アルゴリズムオタク」というスレにふさわしい回答ではないな。
どんなささいなコストも、なんらかのアルゴリズムで回避できるならしなきゃ。
0079デフォルトの名無しさん
2006/03/12(日) 05:37:04>愛されて10万戸→愛されて汁マンコ
>私の父はSEです→私の乳はSEです
ただ下品なだけじゃん。
お前ごときがエロゴリズムを語るのは10年早いわ!
童貞からやり直せ!
0080デフォルトの名無しさん
2006/03/12(日) 08:06:180081デフォルトの名無しさん
2006/03/12(日) 14:39:12>「アルゴリズムオタク」というスレにふさわしい回答ではないな。
質問も回答もスレ違いだろ阿呆。
008246
2006/03/13(月) 11:38:460083デフォルトの名無しさん
2006/03/13(月) 11:48:15みんなの知らない言語みたいだから、説明を入れてみたらどう?
0084デフォルトの名無しさん
2006/03/13(月) 18:16:41はリストで、例えば
[1,2,3,4,5,6,7]とすると、
要素head=1
リストbody=[2,3,4,5,6,7]
を意味します。
nilは空リストです。
0085デフォルトの名無しさん
2006/03/13(月) 18:19:54正しくは(h::rest)でした。
0086デフォルトの名無しさん
2006/03/13(月) 18:54:13結局、ソートされたデータなわけ? ソートされてるなら先頭から順に見るだけでいいし
そうでないなら、ソートしつつ削除するような方法になると思うよ
0087デフォルトの名無しさん
2006/03/14(火) 00:25:100088デフォルトの名無しさん
2006/03/14(火) 03:57:45リストの順序を保ちたい場合は考慮されてますか?
0089デフォルトの名無しさん
2006/03/14(火) 06:47:21そもそも リスト構造のままソートするのは効率が悪いから
リストとは別にポインタ配列としてソートする事になるだろうね
0090デフォルトの名無しさん
2006/03/14(火) 07:52:01実装の話ではなくアルゴリズムの話の筈ですが…
0091・∀・)っ-●○◎- ◆Pu/ODYSSEY
2006/03/14(火) 17:38:49比較するときに同一の場合は除去すればいいだけだからソートの延長で考えればいい。
0092デフォルトの名無しさん
2006/03/14(火) 18:41:51配列とポインタの練習としてスタックとキューを実装しる、みたいな問題が出て
再配置がマンドクサーだった俺は循環キューに思いいたったわけだが、
それが俺の始めての「車輪の再発明」だった。
懐かしい。
0093デフォルトの名無しさん
2006/03/14(火) 19:23:49http://human5.2ch.net/test/read.cgi/ms/1141694640/
8 名前:可愛い奥様[] 投稿日:2006/03/07(火) 11:05:23 ID:8dtluKkp
夫の歯ブラシで洗面所の排水溝掃除。
洗面所をビショビショに汚した罰だ。
20 名前:可愛い奥様[age] 投稿日:2006/03/08(水) 00:40:17 ID:pRrk6A21
前に頭きた時あって
1度だけ歯ブラシで肛門カキカキしちゃった
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
家族で密かにはぶっている。
男性は肉体が汚く、精神が美しい傾向がある。(気に入らない相手に肉体的攻撃を加える⇒精神的攻撃も加える男は猛者)
女は肉体が美しく、精神が汚い傾向がある。(気に入らない相手に精神的攻撃を加える⇒肉体的攻撃も加える女は猛者)
女は隠れて悪事をする。気に入らない女子を便所でボコったり、便器舐めさせたり、男の友人を使ってレイプ、仲間外れにしたり。陰口、嫉妬。
女は対人関係において、この汚い性格を隠そうとするため、外面が非常によくなる。(猫かぶり)
男性諸君は外面に騙されないように気を付けて下さい。
0094デフォルトの名無しさん
2006/03/14(火) 20:22:380095デフォルトの名無しさん
2006/03/14(火) 22:50:490096デフォルトの名無しさん
2006/03/17(金) 13:45:22考えられる限り高速な方法で。
普通になら作れます><
0097デフォルトの名無しさん
2006/03/17(金) 16:40:31>>89
ソートしてあればO(n)で重複を取り除けるし、
配列にリンクポインタへのポインタ相当のものを格納すればリストそのものの順序を変える必要はないし
配列ならデータの種類によっては(フラッシュソートなど)O(n)で出来るソートアルゴリズムが存在する
0098http://www.vector.co.jp/soft/win95/util/se072729.html
2006/03/18(土) 19:14:07もしくは64bitにネイティブ対応したテキスト置換ソフトありますか?
0099デフォルトの名無しさん
2006/04/07(金) 08:22:290100デフォルトの名無しさん
2006/04/07(金) 21:47:380101デフォルトの名無しさん
2006/04/09(日) 23:06:57簡単だ
0102デフォルトの名無しさん
2006/04/10(月) 00:21:52うpして
0103デフォルトの名無しさん
2006/04/10(月) 02:04:26for(;;)MessageBox("荒らしだーーーーーーー!!!!");
}
0104デフォルトの名無しさん
2006/04/10(月) 12:18:520105デフォルトの名無しさん
2006/04/12(水) 10:18:39puts("これ荒らし?[y/n]");
if(getchar() == 'y') for(;;) puts("荒らしだーーーーーーー!!!!");
0106デフォルトの名無しさん
2006/04/12(水) 22:22:58そこに出てくるハノイの塔の再帰的処理が理解できない。
どこを繰り返し処理してるの?
パターンがある事に気付けないんだけど。
ちなみに階乗のアルゴリズムが再帰的だとは理解できます。
5!=5*4!
4!=4*3!
3!=3*2!
2!=2*1!
1!=1*0!
0!=1
0107デフォルトの名無しさん
2006/04/12(水) 22:24:34すなわち3本の柱が左からA, B, Cとあって、
n枚の円盤を柱xから柱yへ柱zを利用して移す手順
をC言語で書いてある。
#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;
}
0108デフォルトの名無しさん
2006/04/12(水) 22:33:071回目は、必ずAとCの間でやり取りをする。
2回目は、必ずAとBの間でやり取りをする。
3回目は、必ずBとCの間でやり取りをする。
で、また1回目に戻る。
でも、例えば1回目はAとCでやり取りすることは分かっても
どっちからどっちへ円盤を移すかはどうしてアルゴリズムから分かるの?
人間は「"小さい円盤"の方から"大きい円盤"の方へ」って
目で見て判断できるけど、コンピュータはできないのに。
0109デフォルトの名無しさん
2006/04/12(水) 22:35:40ディスク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辺りのときの振る舞いを自分で追ってみればよく判ると思う。
0110デフォルトの名無しさん
2006/04/13(木) 02:18:16|54321
|
|
↓(n=4を解く)
|5
|
|4321
↓
|
|5
|4321
↓(n=4を解く)
|
|54321
|
・n=4を解くには(以下略)
...
・n=1を解くには
0111デフォルトの名無しさん
2006/04/14(金) 22:08:53アルゴリズムを考えるアルゴリズムがわかってないはずだから無理だとおもいまーす。
荒らすのはそのアルゴリズムかどうかもわからないんだっけ、
わかってるんだっけ?
0112デフォルトの名無しさん
2006/04/14(金) 22:12:210113デフォルトの名無しさん
2006/04/15(土) 01:08:54アルゴリズムマニアの日記
http://d.hatena.ne.jp/higotakayuki/
0114デフォルトの名無しさん
2006/04/16(日) 13:12:260115デフォルトの名無しさん
2006/04/16(日) 13:58:150116デフォルトの名無しさん
2006/04/18(火) 12:44:20n本のマッチがあって、一回に1〜3本取れる。
自分は先手で、最後の一本をとったら勝ちになる。
必勝のアルゴリズムを教えてください。
0117デフォルトの名無しさん
2006/04/18(火) 12:55:410118デフォルトの名無しさん
2006/04/18(火) 12:57:030119デフォルトの名無しさん
2006/04/18(火) 13:21:41( ・д・)……
0120デフォルトの名無しさん
2006/04/18(火) 13:41:09残り7で相手が3取って終了。
0121デフォルトの名無しさん
2006/04/18(火) 13:46:240122デフォルトの名無しさん
2006/04/18(火) 14:57:39最後の一本は-10点とかだったらどうだろう?
0123デフォルトの名無しさん
2006/04/18(火) 18:33:39その場合は最後の一本を取ったら負けというルールとほぼ等しいので、
4の倍数+1になるようにすればいい。
0124デフォルトの名無しさん
2006/04/18(火) 18:42:44たとえば、1000の棒を取る時にはどうよ?
相手がずっと3取ってたら負けね?
0125デフォルトの名無しさん
2006/04/18(火) 19:04:42勝ちパターン考えるのはメンドクセ
0126デフォルトの名無しさん
2006/04/18(火) 19:24:24最後の一本をとったら負けというのなら簡単なんだけど。
0128デフォルトの名無しさん
2006/04/18(火) 20:37:04もう少し頑張ってみます。
フローも書かないと・・・orz
0129デフォルトの名無しさん
2006/04/18(火) 21:01:010130デフォルトの名無しさん
2006/04/19(水) 10:52:29なるんだけど、自分が21を取る為にそれより前のターンで本数調整
したら勝てなくなるから、結局最初の本数で決まりそう。
0131デフォルトの名無しさん
2006/04/24(月) 01:25:04── = ニ /=、。。。。。。。。。。。。。。。。r=、ヽ
─ =ニ三 (◎ ヽ-─────(◎ )
=@ノ◎、 |\ \ / / | /◎、
(_,rへ `ソ /> ◎) (◎く| レ' ,rへ )
─ = ニ \◎'/ / \ ヽ、◎/
ノ / \ ヽ
─ =ニ三 ( ◎( ) ◎)
─ = ー、_ら ⊂、_,r´
このマシンがどうして前に進むのか教えてください。
普通だったら両方から押し合いへし合いして動かない気がするのです。
0132デフォルトの名無しさん
2006/04/24(月) 07:23:340133デフォルトの名無しさん
2006/04/24(月) 08:43:58http://maps.google.com/maps?t=k&om=1&ll=37.401094,-116.868725&spn=0.006162,0.009291
0134デフォルトの名無しさん
2006/04/24(月) 17:55:54ベームベーム?
0135デフォルトの名無しさん
2006/04/25(火) 11:18:110136デフォルトの名無しさん
2006/04/26(水) 15:15:15リストソートはスキップリストで決まりかな。
0137デフォルトの名無しさん
2006/04/29(土) 20:11:490138デフォルトの名無しさん
2006/04/29(土) 20:13:310139デフォルトの名無しさん
2006/04/29(土) 20:20:02たとえば実装が仕様にあってるかどうかテストできるとか。
あとアルゴリズムのデータベースつくってその言語で検索とかできないかなーと。
0140デフォルトの名無しさん
2006/04/29(土) 23:52:59それによって話は全然変わってくるんだが.
0141デフォルトの名無しさん
2006/04/30(日) 08:04:28まあ完璧なテストは無理だけどある程度のテストはできそう。
0142デフォルトの名無しさん
2006/04/30(日) 08:08:46ユニットテストのすごいバージョンってことでいいの?
0143デフォルトの名無しさん
2006/04/30(日) 08:20:09まあ、確かにユニットテストのすごいバージョンです。
0144デフォルトの名無しさん
2006/04/30(日) 09:08:16アルゴリズムが同一とは限らないわけで・・・
入出力を検証しても必ずしも実装が正しいかどうかは分からないよね。
例えば安定クイックソートの実装のつもりでテストをして、
実際に実装されているのはバブルソートだったとしても出力だけでは分からないはず。
0145デフォルトの名無しさん
2006/04/30(日) 15:27:28複雑度のテストとして、要素数の規模を変えて数回テストし、
実行時間の変化を見てくれるとか、うーん、むずかしいかな。
0146137
2006/05/01(月) 20:03:42入出力の仕様の定義だけ行う言語を作るのも意味はあるかと。
そのあとどんな実装を行うかはまた別の問題ということで。
0147デフォルトの名無しさん
2006/05/01(月) 20:10:430148デフォルトの名無しさん
NGNG仕様を後付けしすぎ。
0149デフォルトの名無しさん
2006/05/01(月) 20:46:10O(n log n) のソートと O(n^2) のソートは
質的に全然違うものなので、それを記述できない言語は
アルゴリズムを記述するには不適当。
0150137
2006/05/01(月) 21:09:12よく考えてみたらアルゴリズムを記述する言語というのが間違いでした。
私がほしかったのは問題を記述する言語とでもいいましょうか。
アルゴリズムが満たさなければいけない条件を定義したかったのです。
0151デフォルトの名無しさん
2006/05/01(月) 21:14:22わかってねえなあ。
「O(n log n) である」 ことを 「満たさなければいけない条件」 として
書けないと、全然意味が無いんだって。
「O(n log n) でないと破綻する入力」 みたいなのを自動生成
できりゃいいけどさ、そんなのは不可能だ。
0152137
2006/05/01(月) 21:26:01は最適解がわかってますが、最適解がわかってない問題もたくさんある
わけですし、それほど重要とは思っていません。
0153デフォルトの名無しさん
2006/05/01(月) 21:28:18研究用途ならそういう結論になるかもしれないな。
だが計算量を記述できなければ実用の道をほとんど閉ざすことになる。
0154137
2006/05/01(月) 21:38:14どれくらい頑張れるかは不明な場合が多いのです。
私は仕様を書いたら即動くものができるというようなことは考えていません。
実装する際に何らかの役に立てばいいと思っています。
0155デフォルトの名無しさん
2006/05/01(月) 21:48:480156デフォルトの名無しさん
2006/05/01(月) 22:00:19世の中にはスピードが問題になることも多々あるわけだが。
理論上は可能、ただし、処理に10億年掛かります、とかね。
そもそも仕様が適当すぎ。荒らしに来たとしか思えない。
0157デフォルトの名無しさん
2006/05/01(月) 22:02:12このスレ(の住人)に何を求めてるの?
0158137
2006/05/01(月) 22:14:20原理的にPASCALでかけないものなんて無いでしょう。
もうちょっと楽にならないかなという程度のことです。
>>156
スピードを仕様に盛り込んだとしても達成できなければ意味が無いのです。
たとえばソートをO(logn)でやれといっても無理な話です。
結局できることといったら存在する実装から一番いいものを選ぶだけなんです。
>>157
まあ、一緒になって考えていただければ。
0159デフォルトの名無しさん
2006/05/01(月) 22:38:10このひとが全然アルゴリズムを理解していないことが分かる。
0160137
2006/05/01(月) 22:45:07解くべき問題を記述したいのです。
ソートには色々な計算量のソートがありますが、目的はどのソートも同じです。
その同じな部分を扱いたいのです。
0161デフォルトの名無しさん
2006/05/01(月) 22:56:440162デフォルトの名無しさん
2006/05/01(月) 23:02:520163デフォルトの名無しさん
2006/05/02(火) 00:12:14>まあ、一緒になって考えていただければ。
情報を小出しにし、わけの分からない仕様を提示し、アルゴリズムの話ですらないのに
その上、出て来た意見を片っ端から否定しといて「一緒になって」も無いだろ
0164137
2006/05/02(火) 00:16:19リップサービスと言う言葉の意味を考えてみたらどうだ?
0165デフォルトの名無しさん
2006/05/02(火) 00:16:350166デフォルトの名無しさん
2006/05/02(火) 00:32:180+0=0
0+1=1
1+0=1
1+1=0
だけであらゆるプログラムを作れるんだろうな。
0167デフォルトの名無しさん
2006/05/02(火) 02:33:34http://pc2.2ch.net/test/read.cgi/tech/1013507313/l50
こういうスレが欲しかったんだろ? さあ逝ってきな
0168デフォルトの名無しさん
2006/05/05(金) 13:02:09対応する十進数(例えば[4バイトBCD] × [10のN乗|Nは1バイト符合付き整数])
に変換するのはどうしたらいいかな。
当然、与えられた浮動小数の符合付き整数部のMSBは1に、
結果のBCDの最上位ニブルは0以外に正規化(?)されているものとする。
8ビットマイコンのアセンブラ想定でよろしく。
0169デフォルトの名無しさん
2006/05/05(金) 13:18:25どっちかいうと実装テクニックじゃない
0170デフォルトの名無しさん
2006/05/05(金) 14:53:07アルゴリズムとそうでないものの違いは「俺様が関心があるかどうか」
の違いではないでしょうw
0171デフォルトの名無しさん
2006/05/05(金) 14:55:270172デフォルトの名無しさん
2006/05/05(金) 14:56:09a*2^N = a*b*10^M とやって正規化するくらいだね
0173デフォルトの名無しさん
2006/05/07(日) 18:59:040174デフォルトの名無しさん
2006/05/07(日) 22:05:07希に「そこを自分で考えるのが楽しいんだろ」ていう部分を
メーリングリストや掲示板で「どうやったらいいんでしょうか?」とかって
訊いてくるヤツのことがサッパリ理解できない。
0175デフォルトの名無しさん
2006/05/08(月) 01:00:24そこを自分で考えるのが楽しいんだろ?
0176デフォルトの名無しさん
2006/05/08(月) 15:13:52そういうレスを返すヤツのことがサッパリ理解できない。
0178デフォルトの名無しさん
2006/05/11(木) 18:47:21なかなかいい構造が思いつかない。
0180デフォルトの名無しさん
2006/05/12(金) 12:43:470181デフォルトの名無しさん
2006/05/12(金) 19:21:090182デフォルトの名無しさん
2006/05/25(木) 12:15:420183デフォルトの名無しさん
2006/06/08(木) 07:52:46はい背の順に整列!
って時さ、
全員がクイックソート理解してたと仮定して、その通りに整列してもらうより
普通に整列させた方が速そうじゃない?
モデル化すると、要素全てが各々同時並列的に他の任意の要素の値を知れる場合
そして要素が同時並列的に移動できる場合
0184デフォルトの名無しさん
2006/06/08(木) 08:47:32大雑把にソートした列に、後はデータ自身が自分の入るべき場所を見つけて両側のデータに対して
スペースを作るように要求する感じかね。
オブジェクト指向のいいテストケースになりそうだが。
0185デフォルトの名無しさん
2006/06/08(木) 15:51:28脳はだいたい基数ソートみたいなことをしているんだってさ
0186デフォルトの名無しさん
NGNG周りのオブジェクト全部をみて整列する人はまずいない。
だいたい自分がどのくらいの序列になるか予想して、整列の初期には近くにいる数人の
オブジェクトのうち同じくらいの序列になる物同士で小グループを形成し、グループ内での
序列を決定した後に他の小グループと合体、境界付近を調整する。
小グループ同士が合体したあとにオブジェクトが余っている場合も、自分の序列がどれくらい
かを予想してそこに近い部分集合の中から自分の序列を決定する。
つーわけで、段階的にマージソートと挿入ソートを同時多発的にやっているような気がする。
0187デフォルトの名無しさん
2006/06/08(木) 18:33:14>同じくらいの序列になる物同士で小グループを形成し
これがマージソートと根本的に違うところ.
簡単のため小グループとして「背の低いグループと背の高いグループ」
を取って,それぞれで再帰的に計算してやることにする.
マージソートだと,それぞれをソートした結果をマージするときに
前半のトップと後半のトップを比較して云々とやらないといけなくて,
マージの部分の計算量が O(n) になり,合計として O(n log n) になる.
しかし,「普通に整列」の場合は前半のほうが後半よりも小さいと
わかっているので単純にくっつければよく,マージの部分の計算量が O(1) ですむ.
その結果,合計として O(n) でソートできるようになる.
0188187
2006/06/08(木) 18:37:48自分の経験から小さい人は前,大きい人は後ろに行って,そこでソート
をやってるもんだと思いこんでいた.
その逆の近くに居る人たちから結合することを考えていたのか.申し訳ない.
#多分それでも「合体」の部分で適当にオラクルが利いて O(n) になるとは思うが
0189デフォルトの名無しさん
2006/06/08(木) 21:38:20最初の移動は粒度の荒いバケツでバケツソートってことになる。
バケツ内での並び替えはどうやってるんかな。
100人の場合と1000人の場合で実験してみないとなんともいえないが・・・
0190デフォルトの名無しさん
2006/06/09(金) 00:23:260191デフォルトの名無しさん
2006/06/09(金) 07:50:531)全生徒はそれぞれ「自分及び他人が(同年代の中で)どの程度の背の高さか」を感覚的に知っている。恐らくはクラスの背の順等の経験から。10%程度の粒度で。
2)全生徒はそれぞれ個別に(=同時に)自分が特定の他者より高いか低いかを判断してそれらしい位置に移動することが出来る。
3)数が多くなればなるほど、身長の近い者が逆順に並んでいても問題にしない。
以上の要因から、CPU一個が無情報で正確にソートしなければならないことを前提としたアルゴリズムに時間的に優っているのである。
0192デフォルトの名無しさん
2006/06/09(金) 09:57:163)に関しては相手にお前何センチって聞けばいんじゃね
0193デフォルトの名無しさん
NGNG機械がやる場合、たとえば標準偏差を与えて記憶や経験の代わりに予想の根拠とすることは
できるような気がする。
0194デフォルトの名無しさん
2006/06/09(金) 11:53:31・頭が n 個あるので log n 時間で整列が可能。
・人間が寝ている場合には、 n 台のロボットを使って log n 時間で整列可能。
ただし、
n が大きくなってくると、入れ替えるために移動させるためにかかる時間の方が
支配的になってくるので、O(n) になる。
0195デフォルトの名無しさん
2006/06/09(金) 20:29:46線形探索や二分探索という位置決めがデータによらない手法に対して、
データの種類によって次の探索位置を変える内挿探索という手法がある。
0196デフォルトの名無しさん
2006/06/09(金) 21:22:52もしその2直線が交点を持つなら、
交点を計算するアルゴリズムってどうなりますか?
2次元平面上での交点計算みたいに方程式作ってもうまくいかないんですが・・・
なんかヒントくれるとありがたいです。
0197デフォルトの名無しさん
2006/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座標の式にいれてすべての座標が一致するかどうか確かめる。
0198デフォルトの名無しさん
2006/06/09(金) 21:40:16先に2次元で解いておいて、3次元にしてもOKか見るわけですね。
なんか頭混乱してて、こんなこともわからなかったです・・・
ありがとうございました。
0199デフォルトの名無しさん
2006/06/09(金) 21:52:390200デフォルトの名無しさん
2006/06/09(金) 22:05:540201デフォルトの名無しさん
2006/06/09(金) 22:25:300202デフォルトの名無しさん
2006/06/10(土) 16:23:04(最大値 - 俺の値)/(最大値 - 最小値)
で数直線上の何%くらいに位置するか検討をつけ、
この場合は身長の分布を思い出して、区間の人数割合を想像してから
自分の属する区間あたりにまず向かう。
適当に整列されて来たら
自分より背の高い奴がすぐ前にいればそいつの前に出る。
0203デフォルトの名無しさん
2006/06/12(月) 21:23:27質問なんだけど、BPマッチングっていうアルゴリズムって存在する?検索してもそれらしいのがヒットしないんだが
0204デフォルトの名無しさん
2006/06/13(火) 01:30:010205デフォルトの名無しさん
2006/06/13(火) 15:41:110206デフォルトの名無しさん
2006/06/13(火) 15:42:010207デフォルトの名無しさん
2006/06/13(火) 16:07:210208デフォルトの名無しさん
2006/06/13(火) 16:15:300209デフォルトの名無しさん
2006/06/13(火) 16:32:320210デフォルトの名無しさん
2006/06/13(火) 16:33:400211デフォルトの名無しさん
2006/06/13(火) 17:06:19もっとも速く処理が終る(もとと同じリストを吐き出す)ソートは?
0212デフォルトの名無しさん
2006/06/13(火) 21:37:45挿入ソート、バブルソート
どちらも一回の走査で終了を検出できてO(N)
0213デフォルトの名無しさん
2006/06/14(水) 10:40:110214デフォルトの名無しさん
2006/06/15(木) 16:17:06ただ,ちょっと賢くマージをすると O(n) になる.
0215デフォルトの名無しさん
2006/06/26(月) 18:41:04ここで質問してもいいでしょうか?
記号列 S1={aabbbcccceefffggggxxxxyzzzz} S2={xxxyzzzzzzzzqqqqcceeff} みたいなのがあり、
それぞれの記号列の中で一致している長さX(可変、無限に長くしたい)以上の部分列を全て挙げる
この例では、X=5としたら {cceeff} {xxxyzzzz} を挙げる。
これを、できるだけ計算量とメモリを節約してやるアルゴリズムは?
それから、このアルゴリズム(この問題)には名前みたいなのあります?
0216デフォルトの名無しさん
2006/06/26(月) 20:12:01S1とS2の半直線部分文字列を、マージ後ソートして比較する
メモリは、文字列を記憶するメモリ+文字数×(sizeof(ポインタ)+記号列を特定するIDなど)
速度は、クイックソートでも使えば速そう
半直線部分文字列のソート後には
abbbcccceefffggggxxxxyzzzz(S1)
...
cceeff(S2)
cceefffggggxxxxyzzzz(S1)
...
xxxyzzzz(S1)
xxxyzzzzzzzzqqqqcceeff(S2)
...
zzzzzzzzqqqqcceeff(S2)
てな感じに並んでるかな、文字列がメモリ中にあればポインタだけソートすればOK。任意の長さの一致が全て判明する。
0217デフォルトの名無しさん
2006/06/26(月) 21:27:480218デフォルトの名無しさん
2006/06/26(月) 21:30:05S1,S2のSuffix Arrayを生成してからマージするような形で判定していけば良いと思う。
まぁ、ぶっちゃけ>>216のマージとソートの順序が逆になっただけだけど。
0219デフォルトの名無しさん
2006/06/26(月) 21:31:11Xが何の長さなのかわからんし、何が一致しているのかわからん
総じて何を言いたいのかさっぱりわからん
0220219
2006/06/26(月) 21:35:29意味はわかったが、アルゴリズムは全然思いつかない
0221デフォルトの名無しさん
2006/06/27(火) 12:17:48とりあえずバカ正直な方法は
aabbbcccceefffggggxxxxyzzzz(s1)
xxxyzzzzzzzzqqqqcceeff (s2_0)
・・・
xxxyzzzzzzzzqqqqcceeff (s2_3)
・・・
ceeff xxxyzzzzzzzzqqqqc(s2_10)
と、一方の文字列をずらしていって、一致する部分を探すことかな。
初めに文字のパターンを調べて、例えば a, b といった文字は片方にしか含まれないから
そういう位置ではパターン検索を省略できるとかくらいかな。
0222215
2006/06/27(火) 15:33:41221 だと計算量 は |S1|×|S2|×|短い方| ぐらいなると思うんですが、
216 だともっと計算量減るでしょうか
>>217
それも解候補です。
本当は"極大"な解だけにしたいんですが、 今は全部出していいです。
例として aaabbbccc.. なんていうのを出してしまいましたが、
本当はもっとランダムな任意の記号列でやりたいのです。
0223デフォルトの名無しさん
2006/06/27(火) 16:01:48aabbbcccceefffggggxxxxyzzzz から
a: aabbb, abbbc,
b: bbbcc, bbccc, bcccc
・・・
y: yzzzz
(説明のために5文字だけだけど、当然、最長パターンまで作っても良い)
次に、もう一方の文字列から、一文字読み込んで、
そこから始まる文字列パターンが「辞書」に登録されてるか調べる。
メモリは食いそうだが、総当たりで調べるよりは少なくなる気がする
0224デフォルトの名無しさん
2006/06/27(火) 20:09:13処理時間の大部分はソートの時間、クイックソートを使うとして
O(N log(N)) Nは|S1|+|S2|
特殊な例外を除いて計算量は減る。
問題は、文字数×8バイト(32bitマシンで)のポインタ領域が必要なこと
0225デフォルトの名無しさん
2006/06/28(水) 09:48:42マージしてからソートはよくわからなかったから
ソートしてからマージで書いた.きちんと証明してないから
正当性はよくわからん.
Suffix Array の構成は O(n) でできることが知られていて,
マージの部分も同じ文字列を何度も比較するのをやめれば
O( (n+m)*min(n,m) ) でできる.合計して O( (n+m) * min(n,m) ).
0226デフォルトの名無しさん
2006/06/28(水) 09:58:26長い文字列の比較はそれ自身コストが高いということを忘れてない?
0227デフォルトの名無しさん
2006/06/28(水) 16:44:35もしかして最後の文字まで比較してると思ってる?
0228デフォルトの名無しさん
2006/07/03(月) 06:56:520229デフォルトの名無しさん
2006/07/03(月) 12:45:58は、n-gram統計における「長尾・森の方法」だな。
岩波のソフトウェア科学の15巻参照
100万字での任意長重複列挙が1秒(Pen-M 1.5GHz)ってとこ。
ソートは文字列専用のソートを利用(単純なクイックソートをちょいと工夫)
>>224や>>228のいう「特殊な例外」(たとえばS1とS2が等しかったり、S1が
S2を包含する場合)では計算量は他の方法並みに大きくなる。
0230デフォルトの名無しさん
2006/07/08(土) 16:49:560231デフォルトの名無しさん
2006/07/08(土) 17:04:06その手の問題は、最適解を見つけるアルゴリズムは見つかってないか、
アルゴリズムが存在しないことが証明されてる(すべての組み合わせを調べるしかない)
ただし、最適解じゃないけど、そこそこ良い組み合わせを得る方法が研究されてる。
0232デフォルトの名無しさん
2006/07/08(土) 17:11:330233デフォルトの名無しさん
2006/07/10(月) 10:27:22使える動画を 6 種類ローテで回して、単なる水着を一つ入れておくってどう?
これで一週間回せると思うけど。
0234デフォルトの名無しさん
2006/07/10(月) 14:51:210235デフォルトの名無しさん
2006/07/10(月) 15:49:37荷物を全部入れる必要はない。
この質問は、荷物の全体が決まってて袋の数を最小にするって問題で、荷物を全部入れる必要がある。
だから問題としては違うんじゃないの。
アルゴリズムの本質的なテクニックは同じなのかも知れないけど。
0236デフォルトの名無しさん
2006/07/10(月) 18:44:501枚用意して、そこに全動画を保存したと思い込めばok
0237デフォルトの名無しさん
2006/07/10(月) 21:36:04ことについて初心者でも分かるように説明させて
くださいませんでしょうか?お願いいたします。
0238デフォルトの名無しさん
2006/07/10(月) 22:36:14バブルソートや挿入ソートで遅くなるケースを回避しやすいから.
0239デフォルトの名無しさん
2006/07/10(月) 23:47:370240デフォルトの名無しさん
2006/07/11(火) 07:53:200241デフォルトの名無しさん
2006/07/11(火) 07:56:350242デフォルトの名無しさん
2006/07/17(月) 16:04:35その全ての組み合わせのパターンを算出
するアルゴリズムってないですか?
カレー 餃子 牛丼 ラーメン
カレー 牛丼 餃子 ラーメン
牛丼 餃子 ラーメン カレー
・・・
・・・
・・・
0243デフォルトの名無しさん
2006/07/17(月) 16:10:440245デフォルトの名無しさん
2006/07/17(月) 16:11:460246デフォルトの名無しさん
2006/07/17(月) 16:11:57ルール説明が雑すぎ
0247デフォルトの名無しさん
2006/07/17(月) 16:51:29順列の計算習うのって中学だっけ高校だったっけ。
0248デフォルトの名無しさん
2006/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空間内全ての4頂点ポリゴンを平面投影し、それらを
正方形面=テクスチャUV空間 に敷き詰める動作をさせたいです)
0249デフォルトの名無しさん
2006/07/19(水) 19:52:440250デフォルトの名無しさん
2006/07/19(水) 20:08:25全部の組み合わせを評価するってのはダメなの?
一つの正方形に1,000個落とすって、枠に対する長方形の大きさが小さすぎて、
現実的に意味なくない? ランダムに落としても、さほど差がないように思う
けれど。
0251デフォルトの名無しさん
2006/07/19(水) 20:18:41それは、箱の中に数個の点を置きそれをちょっとづつ大きくしてくのだったかな・・・・?
これでやるときは、ランダムに座標を取って、ちょっとづつサイズを大きくしていき
当たり判定で、やるんだっけか?
まあ、プログラミング習ったばっかで読んだから忘れた
0252デフォルトの名無しさん
2006/07/19(水) 20:19:550253デフォルトの名無しさん
2006/07/19(水) 20:36:33普通は任意形状の配置だけど
0254デフォルトの名無しさん
2006/07/19(水) 20:40:36>>250
> 全部の組み合わせを評価するってのはダメなの?
理論的には出来るけど、何通りになると思う?
1000個の長方形を単純に一列にならべるだけで1000! 通り(大きすぎてよくわからん)
各長方形の縦横の向きまで考えれば、上の組み合わせにさらに2^1000をかけたものになる。
0255248
2006/07/19(水) 20:47:59>>253
素晴らしいです!
かなりヒントになりました。
この辺キーワードで検索かけまくって、お勉強いたします。
0256デフォルトの名無しさん
2006/07/19(水) 20:54:380257デフォルトの名無しさん
2006/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 のソースでも見たらいいんだろうか、とか思っています。
0258デフォルトの名無しさん
2006/07/20(木) 04:34:040259デフォルトの名無しさん
2006/07/20(木) 12:46:21Javaでやってみました。
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;
}
}
}
0260デフォルトの名無しさん
2006/07/20(木) 13:38:35アルゴリズムの話じゃないが "latter" は "later" に直しとかないと
恥かくんじゃないか?
0261デフォルトの名無しさん
2006/07/20(木) 13:59:100262デフォルトの名無しさん
2006/07/20(木) 14:27:04former / latter はごくごく一般的な単語
恥かいてるのはあんただよ
0264デフォルトの名無しさん
2006/07/30(日) 09:44:290(n)くらい?それともちょっとくらいは速くできる?
0265デフォルトの名無しさん
2006/07/31(月) 01:32:32ランダマイズとかすると減るかもしれんが。
構築段階から手を加えて良いなら、半順序木に要素が追加されるときに
ハッシュか何かにその要素を追加し、以後木に編集がかかったときに
ハッシュと同期する、とかいうのが常套手段。
0266デフォルトの名無しさん
2006/08/08(火) 20:46:26ず,できればビット演算のみで)求める方法を探しているのですが,そういうア
ルゴリズムご存じの方いらっしゃらないでしょうか?
言語は C です.
0267デフォルトの名無しさん
2006/08/08(火) 20:58:58(int)(log(x)/log(2))
じゃマズいよな。
0268デフォルトの名無しさん
2006/08/08(火) 21:35:37(x & x-1) ^ x
で最下位ビットが取り出せるので、前後でビットを逆に並べ替えれば良いんだが、
思いつかん。
0269デフォルトの名無しさん
2006/08/08(火) 22:48:06ビット演算スレがあるから覗いてみたら?
0270デフォルトの名無しさん
2006/08/08(火) 22:52:02ま、どうでもいいけどx&-xのほうがクール
0271デフォルトの名無しさん
2006/08/08(火) 22:59:390272デフォルトの名無しさん
2006/08/08(火) 23:08:41ビット数決めうちなら以下の手がある(CPU依存の命令使うという手もあるが省略)。
x |= x>>1
x |= x>>2
x |= x>>4
x |= x>>8
x |= x>>16
x ^= x>>1
0273デフォルトの名無しさん
2006/08/08(火) 23:09:04情報有り難うございます.書き込んでみました.
0274デフォルトの名無しさん
2006/08/08(火) 23:12:36有り難うございます.
定石があるものとばかり思っていたのですが,意外と難しいんですね...
これから解読してみます.
0275272
2006/08/08(火) 23:19:30実は上のコードはビット演算マニアから言えば定石だったりする。
もし、詳細が知りたければ「ハッカーの楽しみ」という本を読めばいい。
無駄に深い知識を得ることが出来る。
0276デフォルトの名無しさん
2006/08/08(火) 23:25:27そういえば積ん読してあったなぁ,と思って探してみたら出てきました.
p.51 のやつですね.
理解にかかる時間が節約できそうです.有り難うございました.
0277デフォルトの名無しさん
2006/08/09(水) 20:05:190278・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/09(水) 20:51:18static const __m128 fp_mask = { 0xFF800000, 0xFF800000, 0xFF800000, 0xFF800000 };
__asm cvtdq2ps xmm0, xmmword ptr [vsrc] ;//32bit整数×4をロードし単精度×4に変換
__asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
__asm cvtps2dq xmm0, xmm0 ;//32bit整数×4に変換
__asm movdqa xmmword ptr [vdest], xmm0 ;//結果をストア
対象データが大量にある場合、まっとうな方法よりこれが一番スループット出るんだよね
ソフトパイプラインでレイテンシ埋めれば完璧。
0279・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/09(水) 20:52:44○ __asm andps xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
演算結果から言えば同じなんだけど
0280デフォルトの名無しさん
2006/08/10(木) 11:13:28素朴な疑問なんだけど、その両者の違いは32ビット単位か64ビット単位かってことだよね。
実際のCPUの動きとしては、何か違うの?
それと、対象データが大量にあるなら>278のfp_maskはxmmレジスタにロードした方がいいのかな?
0281・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/10(木) 20:32:47たとえばCore 2 Duoの技術情報には、SIMD整数命令とSIMD浮動小数命令を
同じレジスタ上で混ぜて使うとペナルティが生じるという趣旨のことが書かれてる。
見映え的にも型に合ってない命令を無闇に混ぜないほうがいいかな、と。
「movapsとmovapdとmovdqaって何が違うんだ?」と思ってロード帯域計ってみた
ことがあるけど、若干差が生じるんだよな、なぜか。
でもCPUによっては生じないかも知れない。
> fp_maskはxmmレジスタにロードした方がいいのかな?
基本的にはそう。
ロード帯域に余裕がある場合は、レジスタを定数1個のために占有するよりは
処理の並列化のために使った方がいい場合も無くはない。
0283デフォルトの名無しさん
2006/08/13(日) 11:31:18例えば「aあいうえおbbb」と「ccあいうえおeeee」は『大体同じ』と判断したいのです。
この例の場合「あいうえお」の部分が同じな訳ですが、これが「あ いうえ お」とか
「あいう-えお」でも、「あいうえお」と同じとみなしたいです。
人間が目で見れば、「大体同じ文字列」というのはすぐ分かるのですが、
これをどうやってプログラムで実現すればいいのか・・・
0284デフォルトの名無しさん
2006/08/13(日) 11:39:050285デフォルトの名無しさん
2006/08/13(日) 12:11:11LCSって何でしょうか・・・?
ググッてもよく分からない・・・
0286デフォルトの名無しさん
2006/08/13(日) 12:23:380287デフォルトの名無しさん
2006/08/13(日) 12:43:03成る程、深く研究されているんですね・・・
Windows 上で使えるプログラムやライブラリ、
DLL 等があれば教えて下さい。
比較する文字列を 2 つ渡すと、何 % 一致しているかを
返す関数みたいなのがあるといいのですが・・・
0288デフォルトの名無しさん
2006/08/13(日) 13:35:09http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
にある。そんなに複雑ではないので、参考にして書いてみたらどう?
0289デフォルトの名無しさん
2006/08/13(日) 16:31:43あとDNA配列の一致を調べるのと似てるからそれ関係を見てみると面白いかも
BLASTとかFASTAとかだっけかな・・・
0290デフォルトの名無しさん
2006/08/13(日) 21:37:50のアルゴリズム部門に挑戦してみようという人はいないか?
現在、日本は、21位だぞ。
ttp://www.topcoder.com/stat?c=country_avg_rating
0291・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/13(日) 21:50:09http://www.tgries.de/agrep/
0293デフォルトの名無しさん
2006/08/14(月) 00:03:48#あれだとアルゴリズムレベルでの工夫の余地はないのかな。
0294デフォルトの名無しさん
2006/08/14(月) 01:42:06でもまあ機械語いじるのもパズル的な部分はあるし面白そう
オレは無理だが
0295・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/14(月) 02:00:580296・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/08/14(月) 02:01:480297デフォルトの名無しさん
2006/08/14(月) 02:06:510298デフォルトの名無しさん
2006/08/14(月) 11:30:450299デフォルトの名無しさん
2006/08/14(月) 13:35:15http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
は?
経路を記憶するコードを追加すればdiffも簡単にできる。
一致度の%も、定義によって異なってくるが間単に計算できる。
0300デフォルトの名無しさん
2006/08/14(月) 14:24:54自分でそのコードを書く事は出来そうもないので、>>287 の様な
「比較する文字列を 2 つ渡すと、何 % 一致しているかを返す」
様なツールというか関数を探してます・・・
でもないみたいですね。
0301デフォルトの名無しさん
2006/08/14(月) 14:48:050302デフォルトの名無しさん
2006/08/14(月) 17:48:51>299見て書けないならプログラマに向いてないよ。
0303デフォルトの名無しさん
2006/08/14(月) 19:27:46出鱈目書いてよこすが、こんなもんでいいだろうか?
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);
}
0304デフォルトの名無しさん
2006/08/14(月) 19:29:01return j/size;
だ。
0305デフォルトの名無しさん
2006/08/18(金) 19:20:05phpのsimilar_textのソース読んでみてはどうだろう。
O(n^3) くらいだったような気がするが。
0306デフォルトの名無しさん
2006/08/21(月) 18:26:000307デフォルトの名無しさん
2006/08/21(月) 21:15:470308デフォルトの名無しさん
2006/08/22(火) 17:20:550309デフォルトの名無しさん
2006/08/23(水) 21:44:590310デフォルトの名無しさん
2006/08/26(土) 22:50:350311デフォルトの名無しさん
2006/08/26(土) 23:06:40おじいさんは山へ芝刈りに、おばあさんは川へ洗濯に行きまた。
おばあさん洗濯をしていると、
大きな桃がどんぶらこっこどんぶらっこと流れてきました。
0312デフォルトの名無しさん
2006/08/27(日) 19:34:13「おお、なんと大きな桃じゃ!」
と言い、嬉しそうに丸呑みにしました。
0313デフォルトの名無しさん
2006/08/28(月) 00:51:56脳内訂正能力を利用した圧縮ですよね?
おばあん ← 1文字圧縮
芝刈り ← ”柴刈り”を暗号化
行きまた ← 1文字圧縮
おばあさん洗濯 ← 1文字圧縮
どんぶらこっこどんぶらっこ ← 1文字圧縮
0314デフォルトの名無しさん
2006/08/28(月) 21:51:150315デフォルトの名無しさん
2006/08/29(火) 18:42:20線分が多角形の内部を通るかどうかを判定する簡単な方法があれば教えてください。
幾つか自分でもやってみたのですが、線分が多角形の端点と重なる場合などで
正しい結果が出ませんでした。どなたかお願いします。
0316デフォルトの名無しさん
2006/08/29(火) 19:29:07「単純多角形」の定義は何?
0317デフォルトの名無しさん
2006/08/29(火) 19:43:530318デフォルトの名無しさん
2006/08/29(火) 19:51:56内部を通ることにするかしないか自分の定義しだいじゃないのか?
0319デフォルトの名無しさん
2006/08/29(火) 21:24:34重力・斥力でやっているけれどいまいち効率の挙動が悪いんで素。
0320315
2006/08/29(火) 21:27:34単純多角形とは自己交差を持たない穴の開いていない多角形のことです。
このとき、多角形は境界をなす頂点の列を用いて表現できます。
>>317
単純多角形の境界をなす頂点のことを「端点」と表現しました。
>>318
それを曖昧にしないように、「内部」という言葉を使ったのですが、説明不足でした。
境界と共有点を持つケースは、交わらないと判定したいのです。
よろしくお願いします。
0321デフォルトの名無しさん
2006/08/29(火) 22:22:4010年以上育ててたのが、HDと共に逝った
0322デフォルトの名無しさん
2006/08/29(火) 23:12:41あとはひたすら図を書いて場合分けするしかないよ
0323デフォルトの名無しさん
2006/08/29(火) 23:14:290324デフォルトの名無しさん
2006/08/29(火) 23:55:14つhttp://www.google.co.jp/search?q=%E5%A4%9A%E8%A7%92%E5%BD%A2+%E5%86%85%E5%A4%96%E5%88%A4%E5%AE%9A
0325デフォルトの名無しさん
2006/08/30(水) 00:19:190 線分の始点が多角形内部にあるときは交差あり
1 多角形を反時計回りに正規化
2 多角形の全ての頂点を登録(配列1)
3 線分の始終点を頂点として登録(配列2)
4 線分と多角形の交点を(配列1)と(配列2)に新しい頂点として順序良く挿入。
ただし別の頂点と重なるときは登録しない。
5 全ての交点(配列1の点Nと配列2の点Mが同じ座標とする)について、
(配列1)の前後の頂点と合わせた3点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
0326デフォルトの名無しさん
2006/09/13(水) 01:29:07bは条件です。FDDとHDDが両方故障なら2進で11です。
FDDとHDDが両方故障であるのを得るために2進の11がdefineしてあるのは
変更できませんが、FDDとHDDが両方故障であるのを調べるために
if ( a & b == b )
を実行するのには何か無駄がある気がしますが、もっとよい方法はありますか?
0327デフォルトの名無しさん
2006/09/13(水) 01:39:38if ((a & FDD) && (a & HDD))
0328デフォルトの名無しさん
2006/09/13(水) 02:14:27bの値もプログラム中で決定するので327のようにソースに直接書けません。
bを使ったプログラムにします。
bの条件を追加してFDDとHDDとUSBの3つとも故障で2進で111とした場合
もっとよい方法があれば教えてください。
0329デフォルトの名無しさん
2006/09/13(水) 02:47:44「何か無駄がある気がします」なんて言われたら
どんな答えを出してもそういわれそうな気がして答える気にならない。
具体的に何が不満なんだ?
0330デフォルトの名無しさん
2006/09/13(水) 04:11:56どのアルゴリズムが使えて
どのアルゴリズムが使えないかが決まってくるわけで
0331デフォルトの名無しさん
2006/09/13(水) 05:04:37ヒント:青い鳥
だな。理想を求めるのはいいけど、いつまでたっても納品できない悪寒。
ヲレライブラリを失わないためのヲレ危機管理アルゴリズムが不十分だったという検証ができたというヲチか。
バックアップぐらい危機管理の基本中の基本だぜ。
プログラマって人生設計も立てられずに人生のアルゴリズムもなくイベントドリブンで生活してそうだな。
0332デフォルトの名無しさん
2006/09/13(水) 05:12:48特にイベントドリブンテところが痛いな〜
そんなプログラマに救いの手を♪
0333デフォルトの名無しさん
2006/09/13(水) 12:56:27反復部分文字列とは一つの文字列中に複数回出現する文字列のことで
1.同じ反復部分文字列同士は重なりあわない(ABCABCABC => ABCと抽出 ABCABCは抽出しない)
2.反復部分文字列の部分文字列も反復部分文字列だがそれは抽出しない(ABCDEABCF => ABCと抽出 A B C AB BC は抽出しない)
という条件付きで2回以上出現するもので長さn以上の文字列を検索したいのです。
現在ドットマトリックス(str[i]==str[j]の値の行列を作り対角線方向に検索する方法)による検索しか思いつきませんが何か高速なアルゴリズムはありませんでしょうか?
SEQUITURアルゴリズムをいじれば早くなるかと思ったのですが条件を満たす文字列の一部しか見つけられないので悩んでます。
0334デフォルトの名無しさん
2006/09/13(水) 13:19:13ただしa<bは常に満たされる。
『例えば「(2,4)(2,3)(1,6)(4,8)」の場合、
(2,4)(2,3)(4,8)は(2,3,4,8)という組を作る。』
というアルゴリズムを考えているのですが、いい方法が全く思いつきません。
分かる方、ヒントをください!
0335デフォルトの名無しさん
2006/09/13(水) 13:32:15gif なんかの LZW エンコードのソースに書かれているよ。
0336333
2006/09/13(水) 13:43:52なるほど!圧縮でも部分配列の検索を利用しますね。そちら方面で調べてみます。
0337デフォルトの名無しさん
2006/09/13(水) 13:45:10意味が今ひとつわからん。
かっこの中の数字のペアを数学で言うところの同値関係と考えて
その同値類に分けた集合をつくるってことか?
0338デフォルトの名無しさん
2006/09/13(水) 13:52:17ノード間に関係を表すエッジが複数あるとしてランダムに表示されたノードを関係あるものを近くに表示させたいと思っています。
バネモデルなどを使った力学的モデルを使った配置の考え方は見つけたのですが、実行してみるとかなり遅くなってしまいます。
別に見つけた商用ライブラリyFilesのサンプルを使ってみるとあっという間に終わり何か別種のアルゴリズムを使っているとしか思えません。
ttp://www.yworks.com/en/products_yed_about.htm
何か考え方のヒントになるようなものでも助かるので何かないでしょうか。
0339デフォルトの名無しさん
2006/09/13(水) 23:14:17ttp://oshiete1.goo.ne.jp/kotaeru.php3?q=2402835
ふてぇ野郎だ。
0340338
2006/09/14(木) 23:56:30スレ汚しすいませんでした。
0341334
2006/09/15(金) 04:22:02ちょっと調べたのですが、同値関係?同値類?という状態です。
いま作ろうとしているのはN体問題に衝突・合体を組み合わせるため、
『どの物体が、どの物体へ衝突したか』
を判定するアルゴリズムです。
衝突したことが直接判定できるのは2つまで(物体a,物体b)で、
3つ以上が同時に衝突する場合、衝突に関与した物体はこの(a,b)の組み合わせから
判断しなければなりません。
「(2,4)(2,3)(1,6)(4,8)」の場合、合体して新たな物体を生じるのは
(2,3,4,8)(1,6)であることを見つけ出そうとしています。
なんだか長くなってしまいましたが、少し自分でも考えてみます。
0342デフォルトの名無しさん
2006/09/15(金) 07:53:27「衝突・合体」 だけだったら Union Find.
分離もしたくなったら,単一要素を分離するだけなら Union Find Split,
接続している要素の切断なら Euler Tour Tree とか Topology Tree とか.
0343デフォルトの名無しさん
2006/09/15(金) 20:46:34Pythonで作ってみた
(実際の言語固有の便利さを、どこまで使っていいのか良くわからん)
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
0344デフォルトの名無しさん
2006/09/16(土) 06:12:16間違ってる.そのプログラムを
Data = [ (1,2),(2,3), (4,5),(5,6), (3,4) ]
で実行すると
[[1, 2, 3], [4, 5, 6]]
になるが,正しくは
[[1, 2, 3, 4, 5, 6]]
になるべき.
0345デフォルトの名無しさん
2006/09/16(土) 07:15:24http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/2668.txt
0346334・341
2006/09/17(日) 05:13:19アルゴリズムの本を何冊か当たっても出なかった問題が
即座に出てくるなんて、2chの中の人すげー
いまからPython勉強します
0347デフォルトの名無しさん
2006/09/17(日) 06:35:030348デフォルトの名無しさん
2006/09/17(日) 06:45:33・物体 {1, ..., n} がある.
・物体同士の衝突を検査する関数 check(a,b) がある.
・衝突した物体は粘土のように合体する.
という設定で,
衝突している物体対のリスト [ (a_1,b_1), (a_2,b_2), ... , (a_m,b_m) ] が与えられる.
衝突して合体した結果,どのようになるか調べよ.
という問題.
0349デフォルトの名無しさん
2006/09/17(日) 09:56:40http://uploader.erv.jp/src/erv_jp0518.txt
0350デフォルトの名無しさん
2006/09/17(日) 10:30:32ここで計算して少し動かしてまた計算してとやってたんですが、微分積分などを使って一発でやることって可能ですか?
0351デフォルトの名無しさん
2006/09/17(日) 20:09:21あたる本がよろしくないんだな.
セジウィック「アルゴリズムC」,CLR 「アルゴリズムイントロダクション」など
まともなアルゴリズムの本なら最小全域木との繋がりでたいてい書いてあるよ.
0352デフォルトの名無しさん
2006/09/17(日) 20:24:17問題設定がよくわからん.
「物体」とか「関係」とか言わずに,どんな問題を解きたいかを
はっきり述べてくれたほうがよい.
問題だけ見ると >>338 と同じような気がするんだが.
0353デフォルトの名無しさん
2006/09/18(月) 13:07:513体問題を解決してフィールズ賞取れよ、って言ってるのかな?
簡単にできる場合と難しい場合があることくらいまでは俺にも分かるが、できない場合があることを証明するのは俺には荷が重いな。
0354デフォルトの名無しさん
2006/09/18(月) 13:09:27>>353 やっぱりそういう話ですよね。
0355デフォルトの名無しさん
2006/09/18(月) 14:07:450356デフォルトの名無しさん
2006/09/18(月) 17:31:47じゃあ 352 と同じ問題だと思って回答するぞ.
力学モデルは十分実用的のはずで,小規模系で遅いとしたら
時間刻みが細かすぎるか,用いてる力学モデルが致命的に悪い.
特に時間刻みは重要で,別にシミュレーションするわけじゃないんだから
かなり大雑把に計算しても大丈夫.数値安定性が保たれる限界くらいの
刻みに選んでも平気.
大規模系で遅いとしたら,アルゴリズムの改良が必要.
たとえば高速多重極展開なんかは有力な解決になりうる.
0357デフォルトの名無しさん
2006/09/18(月) 17:33:310358デフォルトの名無しさん
2006/09/18(月) 20:11:35表示しながら収束状況を見てると、ノードが行ったり来たりしてるのは問題外ですよね・・・
0359デフォルトの名無しさん
2006/09/19(火) 11:44:17こういうのって初期配置も結構重要だと思うんだけど、その辺意識してるのかな?
0360デフォルトの名無しさん
2006/09/19(火) 15:07:250361デフォルトの名無しさん
2006/09/19(火) 17:46:490362デフォルトの名無しさん
2006/09/20(水) 00:11:270363338
2006/09/20(水) 01:17:57やってるうちに初期配置がかなり重要なことはわかってきました。
今は初期配置をうまくやるアルゴリズムを一つ思いついたので今度試してみるところです。
ただ、初期配置をうまくやってその後収束させる方向が正しいのか、全く違うやり方があるんじゃないかとヒントを探してるところです。
0364デフォルトの名無しさん
2006/09/20(水) 09:06:03ノードを同心円状に配置するのはどうだろう。
グラフのあるノードを中心として、距離1のノードは半径1の円周上に等間隔に配置。
距離2のノードは半径2の円周上に…という感じ。
この方法で以前試した時は、そこそこうまくいった覚えがあるが、
グラフがツリーに近い形状だったからかもしれない。
力学モデルを使っていて遅いとのことだけど、
パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
それから移動量を小さくして微調整すると良いと思う。
もう既にやってるかもしれないしけど…
あと、遅くなる原因としてもう一つ。
これは自分がやったミスで、
収束するのが遅い遅いと思っていて、原因を探るために処理ごとの所要時間を取ってみたら、
実はグラフの収束を確認するための描画に時間がかかっていただけという情けないのもあった。
1回動かすたびに毎回描画なんてしてたから当たり前なんだけど。
0365364
2006/09/20(水) 09:08:07> それから移動量を小さくして微調整すると良いと思う。
力学モデルなら自然とこうなるな…申し訳ない。
0366デフォルトの名無しさん
2006/09/20(水) 09:33:390367デフォルトの名無しさん
2006/09/20(水) 22:29:420368デフォルトの名無しさん
2006/10/30(月) 00:19:450369デフォルトの名無しさん
2006/10/30(月) 00:23:34ボタンを押したら新しいボタンが表示される、ってシステムならOK
0370デフォルトの名無しさん
2006/10/30(月) 14:05:210371デフォルトの名無しさん
2006/10/30(月) 14:09:060372デフォルトの名無しさん
2006/10/30(月) 22:16:57考え方が間違ってる
全押ししても正常に動作するようにする方法を聞くんだ
0373デフォルトの名無しさん
2006/10/30(月) 23:51:040374デフォルトの名無しさん
2006/10/31(火) 00:28:290375デフォルトの名無しさん
2006/10/31(火) 01:51:530376デフォルトの名無しさん
2006/10/31(火) 11:21:220377デフォルトの名無しさん
2006/10/31(火) 13:23:340378デフォルトの名無しさん
2006/10/31(火) 13:33:330379デフォルトの名無しさん
2006/10/31(火) 18:03:27#define N 適当な数
if (押されたボタンの数>重さセンサが感知した量/60kgf+N)
{
SpeakMessage("ボタンが押されすぎです。一旦消します。");
UnlitAllButtons();
}
//地震とかで全押しする必要がある場合の処理をしていません。
0380デフォルトの名無しさん
2006/10/31(火) 20:45:55ボタンすべてキャンセルすればいんじゃね?
もし本当に必要ならもう一度押すだろうし。
0381デフォルトの名無しさん
2006/11/01(水) 12:27:530382デフォルトの名無しさん
2006/11/01(水) 21:02:26そもそも、エレベータに全押し対策機能つけようと思う奴、いるわけないだろ?
(本当につけたら、誤認識の嵐で、相当使いづらいエレベータになるからね。)
あくまで、架空のエレベータの話だ。
0383デフォルトの名無しさん
2006/11/02(木) 00:46:530384デフォルトの名無しさん
2006/11/02(木) 00:57:380385デフォルトの名無しさん
2006/11/02(木) 01:16:370386デフォルトの名無しさん
2006/11/02(木) 09:57:51一人により全押しされた場合は、全てのボタンをキャンセルし、移動方向直近の階に停止させ
上からタライと小麦粉を落とす。
0387デフォルトの名無しさん
2006/11/02(木) 11:24:36がベスト
# 同一人が違う指で押したらどうする?
0388デフォルトの名無しさん
2006/11/02(木) 11:33:340389デフォルトの名無しさん
2006/11/02(木) 13:02:300390デフォルトの名無しさん
2006/11/02(木) 17:01:50親切な人いるじゃん。
ボタンの前に立つと、「何階ですか?」と聞く人。
0391デフォルトの名無しさん
2006/11/02(木) 17:10:37半年(ry
0392デフォルトの名無しさん
2006/11/02(木) 17:11:220393デフォルトの名無しさん
2006/11/02(木) 18:23:170394デフォルトの名無しさん
2006/11/05(日) 00:45:48押すボタンによって指を使い分ければok
0395デフォルトの名無しさん
2006/11/06(月) 09:31:350396デフォルトの名無しさん
2006/11/06(月) 13:33:29・費用は収入や食費・交通費・生活費等の支出等のデータを扱う
・授業は履修している、もしくは履修済みの授業、一週間の授業表等のデータを扱う
・図書は借りた本等のデータを扱う
ユーザーはこのシステムにIDとパスワードを使ってアクセスし、
データ倉庫user-dataに保存されている自分のデータを参照できるようにせよ。
プログラム設計っつー授業でこんな問題出されたんですが、
http://members.jcom.home.ne.jp/pokemon_glider/program.jpg
階層DFDはこんな感じでいいんですか?
これをデータ辞書を追加したり、構造化英語で書いたり最終的にはJavaで実装できるようにしろとまで言われてます
0397デフォルトの名無しさん
2006/11/06(月) 15:09:160398デフォルトの名無しさん
2006/11/07(火) 04:45:31逆にいたずらされて降りられなかったり、
変質者とかに悪用されたりとかしない?
0399デフォルトの名無しさん
2006/11/07(火) 23:45:090400デフォルトの名無しさん
2006/11/08(水) 09:41:000401デフォルトの名無しさん
2006/11/08(水) 15:31:160402デフォルトの名無しさん
2006/11/08(水) 16:11:000403sage
2006/11/08(水) 22:14:540404デフォルトの名無しさん
2006/11/08(水) 22:19:180405sage
2006/11/08(水) 22:25:26連結リストとヒープは使うなという制約が…
平衡木も考えたんだが効率がいまいち。
0406デフォルトの名無しさん
2006/11/08(水) 22:59:06一番左下へのポインタを持ちまわれば計算量的には同じになるはずだけど。
0407デフォルトの名無しさん
2006/11/09(木) 00:04:39単純な方法を用いるとO(kn)かかってしまう(nはk個のリスト中の要素全ての数)
ヒープを用いて効率よく実行する方法を述べその計算量を示せ。
0408デフォルトの名無しさん
2006/11/09(木) 00:11:140409デフォルトの名無しさん
2006/11/09(木) 00:23:58どのリストの先頭が最も小さいか、を管理するためにヒープを用いる。O(n log k)。
0410デフォルトの名無しさん
2006/11/14(火) 21:42:37B(♀)→C(♂)
C(♂)→D(♀)
D(♀)→C(♂)
C(♂)→B(♀)
A(♂)=俺
だれかこの問題を解決できる画期的なアルゴリズムを考えてくだちい
ていうかC(♂)氏ね
0411デフォルトの名無しさん
2006/11/14(火) 22:12:210412デフォルトの名無しさん
2006/11/14(火) 22:37:26C = A;
return 0;
}
0413デフォルトの名無しさん
2006/11/15(水) 17:18:05超亀レスだが、ポインタ書き換えによる単一化を使うと効率がいい。
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)で求められる。
0414413
2006/11/15(水) 17:18:46int 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;
}
}
0415413
2006/11/15(水) 17:27:55int GetRoot(int n, Cell[] cells) {
while (cells[n] != null) n = cells[n].n;
return 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)
cells[GetRoot(cellB.n, cells)] = new Cell(pair.a);
} else { // assert(cellA != null)
cells[GetRoot(cellA.n, cells)] = new Cell(pair.b);
}
}
return cells;
}
に修正。
0416デフォルトの名無しさん
2006/11/29(水) 16:34:59選択肢 ア: 節点nを通る初期節点からゴールまでのコスト
イ: 1つ前の節点からゴールまでの実際のコスト
ウ: 隣の節点からゴールまでの予測(推定)コスト
エ: 初期節点からゴールまでの最適経路
オ: ゴールまでの実際のコスト
カ: 節点nからゴールまでの実際のコスト
キ: 初期節点から節点nまでのコスト
ク: 節点nからゴールまでの予測(推定)コスト
ケ: 初期節点からゴールまでの予測(推定)コスト
コ: 節点nからゴールまでの最適経路
どうぞ
0417デフォルトの名無しさん
2006/11/29(水) 21:45:41最良優先探索のアルゴリズムでは優先度つきキューを,
Aアルゴリズムではヒューリスティックを知識として用いる.
特に,Aアルゴリズムで用いる知識のうち,
すべての節点においてA子がB子よりも小さいか等しいとき,
A子の年齢が求まる保証がある.
宿題は自分でやろうね
0418デフォルトの名無しさん
2006/12/01(金) 16:19:48シリーズ物とか、制服物とか、素人物とか女優名とか。
ファイル名をn-gramに分解して、グループに対応するパラメータを学習させたベイジアンフィルタに
通すってのが、今のところ考え付いた解だけど、
大量の文字列を適当に分類する、分類軸の多様性は、学習させたパラメータで吸収みたい
なのは、みんな考えてそうな気がする。
0419デフォルトの名無しさん
2006/12/01(金) 16:47:060420デフォルトの名無しさん
2006/12/01(金) 22:11:19でも実用化されていないから
お前がんばれ。ていうか頼む
0421デフォルトの名無しさん
2006/12/01(金) 22:25:30どのようなアルゴリズムを使用するのか見当も付きません。
処理したい内容は
多角形 or 多角形
多角形 and 多角形
多角形 xor 多角形
などを繰り返し、最終的に矩形の配列(win32ならGetRegionData)を取得したいです。
アルゴリズム名とか、ここに同じようなコードがあるよとか、この本を見れなどなど
教えてください。
0422デフォルトの名無しさん
2006/12/02(土) 00:09:33書きたいのですが、コレと言う手法が思い浮かびません。
なにかヒントをいただけないでしょうか?
よろしくお願いします。
0423デフォルトの名無しさん
2006/12/02(土) 00:13:37構造体が並んでる感じでIDを探すというならバイナリサーチ。
特に何もないならシーケンシャルサーチ。
0424デフォルトの名無しさん
2006/12/02(土) 00:25:42一般にはいろんな手法があると思う(ベイジアンもそう)。
だけど、問題領域を限定するといろいろ分かることはあって、
エロ動画のファイル名に限定するとよりよい方法が見つかるかもしれない。
面白い研究テーマだと思います。
0425デフォルトの名無しさん
2006/12/02(土) 00:29:24様々な差分ファイルが世の中には存在するからな。
それこそ特許取れる研究をしないと。
0426デフォルトの名無しさん
2006/12/02(土) 01:51:30え?二次だったの?
0427デフォルトの名無しさん
2006/12/02(土) 09:23:380428デフォルトの名無しさん
2006/12/02(土) 12:04:27不可逆圧縮の場合、圧縮レベルが違うと画像そのものの同一性も失われるわけだが。
0429デフォルトの名無しさん
2006/12/02(土) 12:09:49全く別物の画像を比較するんじゃないんだから。
0430デフォルトの名無しさん
2006/12/02(土) 13:44:24近さの度合いを測る方法はいくらでもある。
0431デフォルトの名無しさん
2006/12/02(土) 14:50:12コンピュータグラフィックス 理論と実践
James D. Foley他
19章7節を見れ
0432デフォルトの名無しさん
2006/12/02(土) 19:37:27Cのアルゴリズム本を見たが、ソートしか載ってないクズ本だった。orz
0433デフォルトの名無しさん
2006/12/02(土) 20:53:150434・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/12/02(土) 21:14:36ここ最近の本ってさAho-Corasickアルゴリズムとか実用的なの載ってなくね?
アカデミック関連の糞高い本ならたまに載ってるのもあるんだけど、まず
有限オートマトンだの写像だの語彙が理解できないと話にならない。
0435デフォルトの名無しさん
2006/12/02(土) 21:19:43Aho-Corasick は若干アドバンスドなアルゴリズムだろう。
定本とされるアルゴリズムイントロダクションにも、アルゴリズムCにも無い。
まあ文字列系のアルゴリズムの本なら大体載ってるとは思うが。
0436デフォルトの名無しさん
2006/12/02(土) 21:47:480437デフォルトの名無しさん
2006/12/02(土) 22:05:520438・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/12/02(土) 22:10:16「Ahoは日本では馬鹿という意味だそうですが私はそれほど馬鹿ではありません」
0439デフォルトの名無しさん
2006/12/02(土) 22:59:520440デフォルトの名無しさん
2006/12/03(日) 00:31:55ギャグのつもりなのかムッとしていったのか微妙だなw
0441デフォルトの名無しさん
2006/12/03(日) 06:47:16あまり頭が良いようには思えない。
0442デフォルトの名無しさん
2006/12/03(日) 07:08:26お前が言うなよw
0443421
2006/12/03(日) 14:21:08ありがとう。
初のCG系アルゴだから右も左もわからなかったよ。ほんとサンクス。
0444・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/12/03(日) 15:01:360445デフォルトの名無しさん
2006/12/03(日) 15:02:420446デフォルトの名無しさん
2006/12/03(日) 15:36:160447デフォルトの名無しさん
2006/12/03(日) 16:03:350448・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/12/03(日) 16:12:510449デフォルトの名無しさん
2006/12/03(日) 16:15:500450デフォルトの名無しさん
2006/12/03(日) 16:18:330451デフォルトの名無しさん
2006/12/03(日) 16:28:330452デフォルトの名無しさん
2006/12/03(日) 16:30:260453デフォルトの名無しさん
2006/12/03(日) 16:33:230454デフォルトの名無しさん
2006/12/03(日) 16:34:570455デフォルトの名無しさん
2006/12/03(日) 16:35:420456デフォルトの名無しさん
2006/12/03(日) 16:38:270457デフォルトの名無しさん
2006/12/03(日) 16:42:200458デフォルトの名無しさん
2006/12/03(日) 16:43:400459・∀・)っ-○◎●新世紀ダンゴリオン ◆DanGorION6
2006/12/03(日) 16:56:19宿屋で眠れなかったんです。
0460デフォルトの名無しさん
2006/12/03(日) 17:41:250461デフォルトの名無しさん
2006/12/05(火) 23:17:58GAの考え方で交叉を行う為の選択を行う場合
一般的には一度使った要素は排除して考えるべきですか?
2個を使って1個ができるわけだから元の要素が足りなくなりますよね?
一度使った要素も再利用してよろしいのでしょうか?
0462デフォルトの名無しさん
2006/12/05(火) 23:21:050463デフォルトの名無しさん
2006/12/05(火) 23:34:11まさかこんなに早くレスをいただけるとは思っていませんでした。
GAの本はもっていないのでちょっとわからないです。
ネットで調べても曖昧な答えしか見つけられずに(説明上では無記述でもプログラム上では選んだ要素を2度選ばないようにしていたり)。
なので質問させていただきました。
すみません。
0464デフォルトの名無しさん
2006/12/05(火) 23:49:47ルーレット式やランキング式は淘汰に使われるのであって交叉に使われるんじゃないんですね。
お恥ずかしいです。
交叉に使われるのはその中から本当にランダムで選んだ要素同士でよいのですかね。
図書館にでも行って勉強してきます。
0465デフォルトの名無しさん
2006/12/05(火) 23:55:54個性、つまり要素の並び方の組み替えこそがGAのキモ
極端な例だけど、ABCとabcを交叉してAaAができたとして
それのどこに両親の「個性」が残ってる?
ぶっちゃけランダム生成と大差ないよ
0466デフォルトの名無しさん
2006/12/05(火) 23:56:37正:交叉のキモ
0467デフォルトの名無しさん
2006/12/06(水) 00:17:07わざわざ説明ありがとうございます。
自分はまず親自信の選択の仕方に疑問を持ったもので。
交叉の内容は初期収束を抑える為に8割〜9割を二点交叉、1〜2割程度を一様交叉に
しようと思っております。この辺りはやりながら詳しく検討してみますが。
やはり現時点じゃ資料もないので詳しくはわからないのですが
最低限同じ要素同士が親になることと、1度組み合わせた要素との交叉を避ければいいの
じゃないかと考えておりまして。
最初の質問の内容としては要素数20の配列から2個を選んで親にする。
その場合親は次に利用されないで配列の要素数は18個になる…と繰り返すのですか?という内容です。
この場合は10回やったら選ぶ親が居なくなると思ったので…。
エリート選択をするという意味ではありません。
0468デフォルトの名無しさん
2006/12/06(水) 08:58:40とりあえず動くものを作って実験データ取って検証してみればいいじゃん。
0469デフォルトの名無しさん
2006/12/06(水) 12:47:48自然界では普通の兄弟もいれば異母兄弟も異父兄弟もいるよね。
有性生殖と単性生殖(クローン)の両方を行う奴もいるし。
0470461
2006/12/07(木) 08:13:17実際にやってみることは大切ですね。
ありがとうございます。
>>469
兄弟などを考えたら親が同じ可能は0じゃないですもんね。
同じ親でも子が全く同じになる可能性は遺伝子長にもよりますが余り多くはないですよね。
昨日借りてきたジョンホランドの訳書なんですが軽く読み流しただけでは無能は自分には理解できない様な内容でした。
と言うか自分が考えていた以上と言うか。
スレ違いになりますが今日伊庭さんの遺伝的アルゴリズムの基礎?って本を借りるつもりですが
他に初心者でも分かりやすいお勧めの書籍有りましたら教えていただければ幸いでございます。
色々有り難う御座いました。
0471デフォルトの名無しさん
2007/02/09(金) 17:59:10http://oshiete1.goo.ne.jp/qa2722011.html で話題になっているアルゴリズムの由来はご存知ない?
このアルゴリズム、フラグ用の配列を初期化しないで使う、アイディアものだと思うのですが。
#いっそ、「森田のよく利用する賢いアルゴリズム」って名前で公表しろよと思ったのは内緒。
0472デフォルトの名無しさん
2007/02/09(金) 18:16:44数年前に友人と酒飲んで話した時のあやふやな記憶
CPUだかメモリだかの量子っぽい回路ので似たような処理の話を聞いた
ような気がする
0473デフォルトの名無しさん
2007/02/10(土) 02:08:18なんかには、常識的に使われているテクニック。他のところでも
しばしば見ることのある技法だと思う。
やっているのことは、配列 a の内容のうち重複しないものを
配列 b につめなおす次のプログラムをメモ化しただけなので
初期化がいらないのは当たり前。
m = 0;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) /* find a[i] from b[0..m] ? */
if (a[i] == b[j]) break;
if (j == m) { /* not found */
b[m++] = a[i];
}
#この技法は未初期化が残る C のような言語に特有のものなので、
#「アルゴリズム」というほど一般的でないと思う。
0474デフォルトの名無しさん
2007/02/10(土) 05:20:56このアルゴリズムはデータ数<データの変域が前提になってるね。
フラグの初期化の処理をフラグの正しさの確認の処理に置き換えてるから。
0475虚構世界内存在 ◆vWilh8Qklc
2007/02/26(月) 23:43:49より多くの人びとはオタクという概念について混乱している。
それは、特定の種類の虚構作品の選好と総体的外見との間に因果的関係を見て取ったこと、ならびに感覚を即座に絶対化したことから始まった。
そろそろオタク概念の整備をしよう。
http://www.google.co.jp/search?hl=ja&q=%22%E3%82%AA%E3%82%BF%E3%82%AF%E6%A6%82%E5%BF%B5%E3%81%AE%E6%95%B4%E5%82%99%22&lr=lang_ja
したがって、「オタクは気持ち悪い」というのはトートロジーである(そもそも、気持ち悪い者にオタクという固有名を付けたのであるから)。
あとは、「気持ち悪い」という感覚や感情を即座に正当化することが問題か。
http://www.google.co.jp/search?hl=ja&q=%22%E8%B6%85%E8%B6%8A%E8%AB%96%EF%BC%880%E2%86%921%EF%BC%89%22&lr=lang_ja
一般人とは……(虚構世界内存在による使用法)
http://www.google.co.jp/search?hl=ja&q=%E4%B8%80%E8%88%AC%E4%BA%BA+site%3Apub.ne.jp%2F&lr=lang_ja
0476デフォルトの名無しさん
2007/03/04(日) 22:38:001円〜999円のお買い物をするときに
はらう硬貨の枚数とお釣りの硬貨の枚数の和が最小になる払いかたで
払う金額と持っている硬貨枚数がいかなるときでも対応できるアルゴリズムがわかりません
1000円札は1枚は持っています
硬貨は1.5.10.50.100.500です。お札は1000のみです
0477デフォルトの名無しさん
2007/03/04(日) 22:41:130478デフォルトの名無しさん
2007/03/04(日) 23:43:080479デフォルトの名無しさん
2007/03/05(月) 01:06:42簡単じゃないか。
払う硬貨の枚数は常に0が最小なのだから、釣りとして受け取る硬貨の枚数を最小にする呪文を唱えればいい。
「釣りはいらねぇよ、とっときな」
0480デフォルトの名無しさん
2007/03/05(月) 02:30:540481デフォルトの名無しさん
2007/03/05(月) 23:13:340482デフォルトの名無しさん
2007/03/05(月) 23:34:44もっと究めてニューラルネットワークでも組めば別だろうが。
0483デフォルトの名無しさん
2007/03/09(金) 23:48:50500 100 50 10 10 1 1 1 1 払うと 釣りなし。動いたお金は9枚。
500 100 50 10 10 5 払うと 釣り 1。動いたお金は7枚
500 100 100 払うと 釣り 10 10 5 1。動いたお金は7枚。
うーん
0484京大生www ◆HEfxsk5e3k
2007/03/10(土) 00:18:41面白い、おれさまが考えよう
んん・・・・・・・難しい・・・・・・
0485デフォルトの名無しさん
2007/03/10(土) 01:09:480486デフォルトの名無しさん
2007/03/10(土) 01:15:300487デフォルトの名無しさん
2007/03/10(土) 01:17:33硬貨枚数とあるから、6枚だと思う。
0488京大生www ◆HEfxsk5e3k
2007/03/10(土) 01:36:59その過程で有効なアルゴリズムを考え付くこともある。
というわけでやってみようかな
ところで1000円札は硬貨ではないけど
999円の時は1000円札だして1円お釣りが最速だから1枚っていう風に考えていいのか?
0489デフォルトの名無しさん
2007/03/10(土) 01:38:220490デフォルトの名無しさん
2007/03/10(土) 02:04:301=1
2=1+1
3=1+1+1=5-1-1
4=5-1
5=5
6=5+1
7=5+1+1
8=10-1-1
9=10-1
(1) 与えられた支払額の上の位から順に機械的に上の置き換えを行なう。
(2) +-で打ち消すもの同士を消す。3のときだけ2とおりあるのでより打ち消せる方を選ぶ。
(3) +の方で払うと-の方のお釣りが帰ってくる。
674=(500+100)+(50+10+10)+(5-1)=(500+100+50+10+10+5)-(1) 動いたお金は7枚
348=(100+100+100)+(50-10)+(10-1-1)=(100+100+100+50)-(1+1) 動いたお金は6枚
999=(1000-100)+(100-10)+(10-1)=(1000)-(1) 動いたお金は2枚
0491デフォルトの名無しさん
2007/03/10(土) 02:13:080492デフォルトの名無しさん
2007/03/10(土) 03:12:36797=1000+5+1+1-100-100-10 7枚
0493デフォルトの名無しさん
2007/03/10(土) 05:35:070494デフォルトの名無しさん
2007/03/10(土) 07:47:260495デフォルトの名無しさん
2007/03/10(土) 12:03:45後はいかに無駄な探索を省くか(枝刈り)を考えた方が簡単でしかも速く、正確に動く。
0496デフォルトの名無しさん
2007/03/10(土) 12:53:21ちなみにいつもは手持ちの硬貨を減らしつつ、例外的に100円玉をもっとも増やす
アルゴリズムを使っています。
0497デフォルトの名無しさん
2007/03/10(土) 15:19:130498476
2007/03/10(土) 17:45:38Rを使ってプログラムを作りました。
時間かかりすぎる・・・orz
0499デフォルトの名無しさん
2007/03/10(土) 17:54:290500476
2007/03/10(土) 18:46:570501デフォルトの名無しさん
2007/03/10(土) 19:11:48所持硬貨枚数のwhile文に対して
外側に所持硬貨枚数を計算させる部分をもってきていました。
それにしても時間がかかる… 誰か修正してくれ…orz
0502デフォルトの名無しさん
2007/03/10(土) 23:45:431円玉が-4〜4枚
5円玉が-1〜1枚
10円玉が-4〜4枚
50円玉が-1〜1枚
100円玉が-4〜4枚
500円玉が0〜1枚
1000円札が0〜1枚
と考えてよさそうだ
0503デフォルトの名無しさん
2007/03/11(日) 10:44:00何か不満でも?w
0504デフォルトの名無しさん
2007/03/11(日) 12:08:33昔Gooゲームかなんかでこれと同じルールのゲームがあったんだけど(たしか名前はブロキシー)
時間制限がなかったから手動で配置を入力して探索させてみたけど
なんの工夫もしなかったから全然良い点の手みつけられなかった
そのうえGooのやつはランダム要素を持ったブロックが一個だけあって、
それは最後まで残すようにするしかなかった。
0505デフォルトの名無しさん
2007/03/11(日) 15:16:09枚数の和のリストを出力してみた。
(例: 1円は1枚, 2円は2枚, 3円は3枚, 4円は2枚 ... 999円は2枚)
誰か検算してくれ。
1232123321234323443234543455434554345432344323432123432344323454345543456545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
3454345543456545665456765676545665456543455434543234543455434565456654566545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876788767887678765677656765456765677656787678876788767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
345434554345654566545676567654566545654345543454323454345543456545665456654565434554345432344323432
0506デフォルトの名無しさん
2007/03/11(日) 15:39:42(1円1枚, 5円2枚, 10円2枚, 50円2枚, 100円2枚, 500円2枚)
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654576545876567654576545654346543454323654346543476545765457654565434654345432354323432
0507デフォルトの名無しさん
2007/03/11(日) 15:46:050508デフォルトの名無しさん
2007/03/11(日) 16:44:47出力結果が正しそうだったら、ね・・・
0509デフォルトの名無しさん
2007/03/11(日) 17:11:32硬貨を何枚持っているかは不明なんじゃないの?
0510デフォルトの名無しさん
2007/03/11(日) 17:57:22もちろんそうだろ?
「任意の枚数指定ができるプログラムを作れ」ってのが本来の課題。
0511デフォルトの名無しさん
2007/03/11(日) 18:01:02総当たり、たぶん同じ
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
0512デフォルトの名無しさん
2007/03/11(日) 18:50:13ソースうp
0513デフォルトの名無しさん
2007/03/12(月) 16:09:470514デフォルトの名無しさん
2007/03/12(月) 17:45:22なあ、その条件で10円を1枚にしてやってみてくれないか
0515デフォルトの名無しさん
2007/03/13(火) 00:16:42これでいいか?(1円1枚, 5円2枚, 10円1枚, 50円2枚, 100円2枚, 500円2枚)
1432124321254323654347654565434654345432354323432125432354323654347654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545876568765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
476545765458765698767A987898767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654587656876567654576545654346543454323654346543476545765457654565434654345432354323432
0516515
2007/03/13(火) 00:18:200517デフォルトの名無しさん
2007/03/20(火) 23:49:460518デフォルトの名無しさん
2007/03/29(木) 23:52:40最後の問題がどうしても解けないお(;^ω^)
当方文系出身のせいでちんぷんかんぷんなんだお・・・
心優しい方手伝ってはくれないだろうか?お願いしまつ・・・
ageて申し訳ない。次からはsageて行くので・・
0519デフォルトの名無しさん
2007/03/29(木) 23:55:39とりあえず問題を見せてもらおうか。
0520デフォルトの名無しさん
2007/03/29(木) 23:59:32問題;複数の生の整数を入力し、その中の最大値と最小値、平均値を求める
処理の流れ図を作成せよ。なお、入力の終了は-1を入力した場合とし、
データは必ず1件以上入力されるものとする。
多分かなり初歩的なアルゴリズムかと思われるのですが自分にとっては
難しいです・・何せアルゴリズムの本当の初歩しか本で勉強していない
身ですのでorz
お願いしまつ(;´д`)
0521無知な新社会人
2007/03/30(金) 00:00:260522デフォルトの名無しさん
2007/03/30(金) 00:15:48アルゴリズムと言うにもおこがましい。人間がそれを為すようにすればよいだけだ。
ついでに言えば、流れ図なんぞを書かせるような会社には似合いの人材というわけだな。
0523無知な新社会人
2007/03/30(金) 00:20:14手厳しいお返事ありがとうございます。
ですが・・・本当にどういう風に書けばいいのか理解できないのでここの
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに
(´・ω・`)
0524デフォルトの名無しさん
2007/03/30(金) 00:21:59悪いことは言わん、他所の業界へ行け。
罵るつもりはないが、このままじゃお前とお前に関わる者が不幸になる。
・・・と、思ったが、普通の初心者ってこんなんだっけ?
もう20年以上もプログラミングやってるし、初心者の感覚がさっぱりわからん。
0525無知な新社会人
2007/03/30(金) 00:27:53この業界には文系ながらも興味がある上、勉強していてもとても楽しいので
実際仕事に携わってみてから貴方の意見を参考にさせていただきたいです。
ですが、玄人から見たら多分自分みたいな雑魚が入っても迷惑なだけという
意見は理解できます・・・そうならないように努力します。
初心者の私からみたら・・・正直こんなアルゴリズムとも呼べない問題でも
どういう風に図を組み立てればいいかわからないですorz
0526デフォルトの名無しさん
2007/03/30(金) 00:32:39時代遅れだと思うしうちの会社でも使わないんで。
力になれなくてすまんね。
0527デフォルトの名無しさん
2007/03/30(金) 00:34:43>勉強していてもとても楽しいので
この業界ではこれが一番大切な才能だ。それを持っているならどうにかなる。
とりあえず一度に解決しようとするな。一度問題を噛み砕け。
たとえば、まず最大値だけを求めることを考えろ。それでもイメージが沸かなければ
さらに噛み砕いて二つの値が与えられた時にその内の大きなほうの値を求めることを考えろ。
0529デフォルトの名無しさん
2007/03/30(金) 01:34:20流れ図云々より、プログラム書くこと覚えたほうが手っ取り早
0530デフォルトの名無しさん
2007/03/30(金) 13:36:51数字の入力
|
正の数か? ->-1以外の負の数:怒る
|
-1なら入力した個数がいくつかチェック ->0個:コラッ!
正の数ならリストに数値を追加
</繰り返し>
|
-1で個数が0以上の時計算に入る
|
ごにょごにょ
|
出力
0531デフォルトの名無しさん
2007/03/30(金) 14:28:38() //端子
{} //繰り返し開始記号
[]数字の入力 //処理
<>数値チェック //分岐
<-1
[]怒る
()終了
<>数値チェック
==-1
[]ループ脱出
[]リストに数値を追加
{}
<>入力個数チェック
==0
[]怒る
()終了
[]最大値、最小値、平均値の算出
()終了
処でこの問題、求めた値を出力しないでいいんだろうか。
0532無知な新社会人
2007/03/30(金) 14:53:45そんな所よりも肝心要の
「入力処理部分(キーボード割り込みから、整数のparsingぐらいまで)」
をメインにお願いします。
自力でガンガッテるんですが、全然かけません・・・OTL
0533デフォルトの名無しさん
2007/03/30(金) 15:32:39ちょっと待て。あんたの言う要の部分は普通はOS側にライブラリ経由で処理してもらうところだ。
#パースはライブラリだけど。
一体全体、どんな環境の何をやろうとしているんだ?
0534無知な新社会人
2007/03/30(金) 15:56:28もし書きにくいようでしたら、
PC/AT互換機という事でいいでつ。
# OS が絡むと面倒なので、"OS は無し" という事で・・・(;^ω^)
私としては、それなりに流れ図が書けていて、
入社後に教育担当の方から怒られなければ
それでいいでつ(;´д`)
0535デフォルトの名無しさん
2007/03/30(金) 16:02:44環境が指定されてなければ、このあたりは
環境に用意されているものとしていいはずだ。
パースはともかく割り込みのあたりなんて
アルゴリズムの範疇ではない。
0536デフォルトの名無しさん
2007/03/30(金) 16:19:06>OSなしでIO処理しろって、どんな課題だよ。
多分、入社後の研修では H8 とか PIC とか使わされる事に
なりそうなんですが・・・
また、この宿題については、研修担当の方からは
「(所詮、流れ図だから)君の得意な環境を想定して書けばよい」
と言われました。
助けてください゚+.゚(´っω・。`)゚+.゚
0537デフォルトの名無しさん
2007/03/30(金) 16:21:46情報が少なすぎてなんとも言えないけど、
ろくに会話もできないぼんくらをプログラマとして雇うような糞会社が要求する流れ図なんて、
>531のレベルで書けてりゃ充分だろ。
0538無知な新社会人
2007/03/30(金) 16:25:18手厳しいお返事ありがとうございます。
ですが・・・本当にどういう風に書けばいいのか理解できないのでここの
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに
(´・ω・`)
0539デフォルトの名無しさん
2007/03/30(金) 16:50:01>531に後は最大値なんかのロジックを追加するだけだろ。
0541デフォルトの名無しさん
2007/03/30(金) 17:54:25もう、わからないことや出来ないことは素直に「出来ませんでした」でいいんじゃね?
会社側も、「2chとかで調べて何となく作ってみました」よりも「わかりません。教えて下さい」って
社員の方が扱いやすいだろう。
0542デフォルトの名無しさん
2007/03/30(金) 17:58:49>手厳しいも何も、>531は理解できてないのか?
正直難しいです。(ρ_;)・・・・
どうしてこれでよいのか、全然分かりません。
まずは早速教えていただいたとおりに、
一度問題を噛み砕いてみます。
例えば、キー押下によって割り込みピンが
アサートされた時の処理って何行目になるんですか?
0543デフォルトの名無しさん
2007/03/30(金) 18:08:44流れ図ってそんな事まで書くか?
>例えば、キー押下によって割り込みピンがアサートされた時の処理
この意味わかって言ってんの?
0544デフォルトの名無しさん
2007/03/30(金) 18:38:21まったく常識が無いやつだと思われても仕方が無い。
0545デフォルトの名無しさん
2007/03/30(金) 20:42:510546無知な新社会人
2007/03/30(金) 21:24:49どっからといわれましても・・・
多分、私の対象とする課題のスコープと
回答して下さっている方が(勝手に)思い描いている
課題のスコープの差異を指摘なさっているのだと考えますが、
なぜか不思議な事に私の提示する要件の内容に耳を傾けることなく、
ただただ「俺が正しいんだ」
「お前は常識がない・流れ図を理解していない」
と言われ、責め続けられるのみで一向に話が進展しないので、
こちらから具体例を出したまでなのですが。(´・ω・`)
それとももしかして、実際の業務はそのように顧客に接するのが
「正しい SE のありかた」だ、と身をもって
教えてくださっているのでしょうか?
もっといろいろ勉強しなくてはいけない事があるんですね・・・
ありがとうございます。
0547デフォルトの名無しさん
2007/03/30(金) 21:44:21マウスで手書き入力しようが、携帯電話からメールしようが、シリアル伝送で来ようが、
VT端末から来ようが、トグルスイッチでDMAしようが、パンチカード読み取り機から
来ようが、念派で書き換えようが、些末なこと。
そんなことはアルゴリズムを実装・適用する連中が考えればよいわけで、
アルゴリズムというのは、数値はどこからか入力されている、と抽象化した
レイヤーにあるわけ。
0548デフォルトの名無しさん
2007/03/30(金) 21:52:00>>532 は天然ぽくって面白かったけど、
>>546 は天然ぽさが足りなくて全然面白くない。
0549デフォルトの名無しさん
2007/03/30(金) 21:59:01仮に出題意図が低レベルのロジックだったとしよう。
それは普通はアルゴリズムとは呼ばないので、このスレで
質問したことが間違い。
もし割り込みとかそのあたりもアルゴリズムだと思ってるなら
計算機科学に関する常識が足りないので、ちゃんと勉強して
おいたほうがよいと思うよ。
0550デフォルトの名無しさん
2007/03/30(金) 22:29:41「割り込みピンがアサートされた」のような事まで流れ図に書くようにとは
あの問題が書かれてないから皆に通じなかったのも無理はないよ。
せめてアセンブラレベルかプログラミング言語レベルかくらいは言えばよかったね。
0551無知な新社会人
2007/03/30(金) 22:43:23>仮に出題意図が低レベルのロジックだったとしよう。
>それは普通はアルゴリズムとは呼ばないので
>もし割り込みとかそのあたりもアルゴリズムだと思ってるなら
>計算機科学に関する常識が足りないので、ちゃんと勉強して
>おいたほうがよいと思うよ。
「アルゴリズム」という言葉についての
非常にラディカルな定義、誠に有難うございます m(_ _)m
(Dekker 先生とかが聞いたら、さぞお喜びになるでしょう)。
「計算機科学」についても今後しっかり勉強していくつもりです。
0552デフォルトの名無しさん
2007/03/30(金) 22:47:370553無知な新社会人
2007/03/31(土) 00:06:16>>552さんの仰るとおり質問を最初にさせて頂いたのは528の私です。
>>532以降は偽者の私ですが、きっと彼も私と似た境遇で必死なんだと
思われますので、住人の方々も手厚く見守ってあげてください。
>>530-531さん、亀レスですが、本当にありがとうございます。自力でやった
のと比較してかなり違っていたので、大変参考になります。ご親切に図まで
書いていただき、感謝感謝です(*´д`)
このスレも今後時たま覗くと思いますが、これからはまた名無しに戻ります。
いつか自分もちゃんとしたレスができる日を願って・・・
0554デフォルトの名無しさん
2007/03/31(土) 00:45:22「非建設的」をインスタンス化した様な奴だなお前。
0555デフォルトの名無しさん
2007/03/31(土) 01:11:56>PC/AT互換機という事でいいでつ。
腹立つわぁ
0556デフォルトの名無しさん
2007/03/31(土) 14:24:41キモイ顔文字使うヤツは、首釣って死ねよ
0557デフォルトの名無しさん
2007/04/02(月) 11:15:500558デフォルトの名無しさん
2007/04/02(月) 21:58:080559デフォルトの名無しさん
2007/04/04(水) 21:03:050560デフォルトの名無しさん
2007/04/05(木) 17:21:210561デフォルトの名無しさん
2007/04/07(土) 21:56:200562デフォルトの名無しさん
2007/04/24(火) 04:41:24カレンダー生成のアルゴリスムで定番なの無い?
0563デフォルトの名無しさん
2007/04/24(火) 11:21:030564デフォルトの名無しさん
2007/04/24(火) 16:31:480565デフォルトの名無しさん
2007/04/24(火) 17:38:08あとはうるう年のルールを考えて増減するだけでいいんじゃないか?
0566デフォルトの名無しさん
2007/04/24(火) 18:00:120567デフォルトの名無しさん
2007/04/24(火) 18:23:27#include <stdio.h>
int month_table[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int is_leap_year( int y )
{
return ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0);
}
int days_of_month( int y, int m ) /* m:1〜12 */
{
if( (1 <= m) && (m <= 12) ) {
int d = month_table[m-1];
if( (m == 2) && is_leap_year( y ) ) ++d;
return d;
}
return 0; /* error */
}
int day_of_week( int y, int m, int d )
{
if( m < 3 ) {
--y; m += 12;
}
return (y + y/4 - y/100 + y/400 + (26*m+16)/10 + d) % 7;
}
0568デフォルトの名無しさん
2007/04/24(火) 18:25:05{
int d = days_of_month( y, m ), w = day_of_week( y, m, 1 );
int n, dow;
printf( "Calendar %04d/%02d\n", y, m );
printf( "Sun Mon Tue Wed Thr Fri Sat\n" );
printf( "---------------------------\n" );
for( dow = 0; dow < w; ++dow ) printf( " " );
for( dow = w, n = 1; n <= d; ++n ) {
printf( " %02d ", n );
if( ++dow >= 7 ) {
dow = 0;
printf( "\n" );
}
}
printf("\n\n");
}
int main( void )
{
int m;
for( m = 1; m <= 12; ++m ) print_calendar( 2007, m );
return 0;
}
いじょ。
0569デフォルトの名無しさん
2007/04/24(火) 18:57:460570デフォルトの名無しさん
2007/04/24(火) 18:59:23それはもう既に、>566が予防線を張ってしまった。
0571デフォルトの名無しさん
2007/04/25(水) 22:08:37これじゃないのか
0572デフォルトの名無しさん
2007/05/02(水) 13:21:23ってNP問題だっけ?
いまHDDの整理してて出来るだけDVDの空き領域が小さくなるファイルの組み合わせを考えてるんだけど
0573デフォルトの名無しさん
2007/05/02(水) 13:30:410574デフォルトの名無しさん
2007/05/02(水) 13:35:13http://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C
0575デフォルトの名無しさん
2007/05/02(水) 13:39:060576デフォルトの名無しさん
2007/05/02(水) 14:25:00>>574リンク先の pi=ci が成り立つ場合だな。
0577デフォルトの名無しさん
2007/05/03(木) 17:25:540578デフォルトの名無しさん
2007/05/03(木) 17:27:48アルゴリズム
0579デフォルトの名無しさん
2007/05/04(金) 01:20:53CPUキャッシュのミスヒットのように、想定外の動作でむちゃくちゃ効率悪くなったりしない?
0580デフォルトの名無しさん
2007/05/04(金) 08:59:19このようなソートされた配列がある。
データが変わる位置(上の配列なら0,2,6)を
逐次検索より速く見つけ出すアルゴリズムを考案せよ。
自分で二分検索法を改良した方法でやったら却って遅くなりますたorz
0581デフォルトの名無しさん
2007/05/04(金) 09:15:420582デフォルトの名無しさん
2007/05/04(金) 15:34:03一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。
複雑なアルゴリズムはデータ量に対する計算量を少なくはできるが、
その1ステップ毎に必要な計算量はたいてい増えちゃうから、
データ量が少ない場合はかえって遅くなる。
0583デフォルトの名無しさん
2007/05/04(金) 21:48:46>一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。
その程度のサイズのデータ量じゃないんだろ
0584デフォルトの名無しさん
2007/05/04(金) 23:55:25もっとサンプリングを細かくした方が効率良くなると思う。
まあデータの偏り具合にもよるが。
0585デフォルトの名無しさん
2007/05/04(金) 23:58:24お前、二分検索法をちゃんと理解できてるか?
0586デフォルトの名無しさん
2007/05/05(土) 00:19:510587デフォルトの名無しさん
2007/05/05(土) 08:06:532分探索はデータが変わる位置の数はO(N)に比例して,
探索そのものの時間はO(log N)なのでO(N log N)
∴ 逐次探索の方が高速
......と自分の中では直観に反した結論が出てしまった。
自分でもなんとなーく間違ってる気がするので、
だれか偉い人教えて!
0588デフォルトの名無しさん
2007/05/05(土) 10:34:18A2B4C4 と記憶しておけばいい。
0589デフォルトの名無しさん
2007/05/05(土) 11:27:310590デフォルトの名無しさん
2007/05/05(土) 16:01:21ふたつ間違ってる。
>データが変わる位置の数が O(N) に比例する
これは問題設定によるので、そうとはいえない。普通は変わる
位置の個数を M として、M に依存した計算量で評価すべき。
>探索そのものの時間はO(log N)なのでO(N log N)
これは実装に依存する。過去の探索の結果を忘れて探索を
繰り返すとそうなるが、過去の情報を保持するように実装すれば
探索木の頂点数が O(N) なので、最悪でもO(N) にできる。
0591デフォルトの名無しさん
2007/05/07(月) 08:44:04会話のアルゴリズムぅ?
0592デフォルトの名無しさん
2007/05/12(土) 20:09:19現実問題としてはデータ依存としか言えないね
扱う対象がどれくらいの大きさで、何種類の文字が何回くらい切り替わるのか、
これによって実装は変わる
飛び石のようにn文字ずつ進んでいくか
半分に区切っていくか
オーダをとると後者のほうが計算量は小さくなるけど、一般には前者が速いと思う
0593デフォルトの名無しさん
2007/05/25(金) 15:29:37ttp://homepage3.nifty.com/DO/direct_linear_sa.htm
にいくつか紹介されてますが、ソート関係の話は1年違うと速度が大分違うと
聞いたので
0594デフォルトの名無しさん
2007/05/26(土) 08:08:02実用上では、MSufSort か libsufsort が最速っぽい。
suffix array はだいぶ煮詰まってるので、
新奇なものが出ない限り、上記2つを追っていれば十分だとおもふ
0595デフォルトの名無しさん
2007/05/29(火) 18:07:29おお、どもどもです
0596デフォルトの名無しさん
2007/06/06(水) 23:23:39数独のプログラムを作っているのですが、インターフェースが出来て、
ランダムで適当な数字を残してやってみても、あまり面白い問題が出来ません。
数独で人間が仮置きとかせずに解けるような問題を自動生成するアルゴリズムって、
どんなのが考えられるでしょう?
0597デフォルトの名無しさん
2007/06/06(水) 23:29:19その方法だと解が2通り以上出る可能性もあるな
0598デフォルトの名無しさん
2007/06/07(木) 00:01:57そのノウハウで飯が食える人がいるから、そう簡単には教えてくれる人はいないんでない?
ヒント:プログラムで解いてみて、問題ないならOK
0599デフォルトの名無しさん
2007/06/07(木) 00:17:14>あまり面白い問題が出来ません。
なにがどうだったら面白い問題とみなせるんだ?
そこを考えれば自ずとわかるような気がするけど。
0600デフォルトの名無しさん
2007/06/07(木) 06:54:520601デフォルトの名無しさん
2007/06/07(木) 09:43:45巧い作者の問題だと、解いててセンスが感じられて楽しい。
0602デフォルトの名無しさん
2007/06/07(木) 10:40:170603デフォルトの名無しさん
2007/06/07(木) 11:11:54【解答】パズルのプログラミング【作成】
http://hobby9.2ch.net/test/read.cgi/puzzle/1092459010/
0604デフォルトの名無しさん
2007/06/07(木) 12:53:57またずいぶんマイナーなスレを…
0605デフォルトの名無しさん
2007/06/07(木) 16:35:120606デフォルトの名無しさん
2007/06/24(日) 18:56:38コンピュータによるゲームでは、IBMのディープブルーがチェスの世界チャンピオンを破って話題になりまし
たが、コンピュータが人間に勝てないゲームのうち残っている囲碁に関して、新しいアルゴリズムが開発
され、10年以内にはプロ棋士を破ることが実現される可能性があるそうです。
ハンガリー人の研究者が、モンテカルロ法を拡張したUCT(日本語では「ツリー構造に適用された上位信頼限界」
というそうですが…)というアルゴリズムを開発し、その効果を高めるために様々な追加研究を行っているそうです。
このアルゴリズムの特徴は、単純にパターンを網羅して、無作為に抽出・評価するモンテカルロ法から発展して、
様々な評価指数を用い有望な選択肢を抽出し評価を行うようです。例えれば、統計的手法から学習的手法に
進化したもののようです。
コンピュータが誕生してから、時間が経ちますが、一歩ずつでありながらも、確実に人間の思考と互角に機能できる
ように、いろいろな人が研究を続けて進化していることを実感します。そして、そのような実験の結果が、部分的でも
家庭用ゲームやラーニングソフトウェア等にも吸収され、コンピュータの活用がさらに進化すればよいなと思います。
http://blogs.itmedia.co.jp/tsuruta/2007/06/post_6850.html?ref=rssall
0607デフォルトの名無しさん
2007/06/30(土) 23:09:520608デフォルトの名無しさん
2007/07/03(火) 21:48:250609デフォルトの名無しさん
2007/07/03(火) 22:42:221話 俺のアルゴリズムは正しいのだ!
2話 貴様らのアルゴリズムに正義はあるのか!正義はあるのかと聞いている!
3話 アルゴリズムを教えてくれ!ナタク!
最終話 だから女は甘い
0610デフォルトの名無しさん
2007/07/10(火) 16:43:27たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
2桁目を決めよう
↓
答えは10かな?21*10=210で521より小さい
↓
じゃ20かな?21*20=420<521
↓
じゃ30かな?21*30=630>521(もし90でも超えなければ二桁目は9にする)
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は1桁目・・・
こんなのを考えたのですが、もっと良い方法はないですか?
0611デフォルトの名無しさん
2007/07/10(火) 17:03:240612デフォルトの名無しさん
2007/07/10(火) 22:23:400613デフォルトの名無しさん
2007/08/04(土) 11:39:42n=3、 k=4 (A,B,C,D) とするとき、各箱にボールを入れるパターンを考える。
この場合、組合せの総数は 20 となるが、左右対称となるパターン( A=D、B=C ) を
除く条件もある場合、全パターンは以下のような 10 パターンになる。
n、k が任意の値であるとき、同様に全パターンを生成するアルゴリズムはどのようになるか?
A B C D
○○○ | | |
○○ | ○ .| |
○○ | . | ○ |
○○ | . | | ○
○ | ○○ .| |
○ | ○ .| ○ |
○ | ○ .| | ○
○ | .| ○○ |
| ○○○ | |
| ○○ | ○ |
0614デフォルトの名無しさん
2007/08/04(土) 11:42:57等価であるとみなすことができるものとする。
0615デフォルトの名無しさん
2007/08/04(土) 11:45:10(1)
A B C D
○○○ | | |
(2)
A B C D
| .| | ○○○
0616デフォルトの名無しさん
2007/08/04(土) 12:08:28A > D または (A = D かつ B > C) を
満たすもののみ出力すればいいよ
0617デフォルトの名無しさん
2007/08/04(土) 12:17:18確かに、まず「箱毎のボール数」を全列挙するアルゴリズムが出発点ですね。
・・・しかし、nとkが任意の際のうまいアルゴリズムが思い浮かばない・・・
0618デフォルトの名無しさん
2007/08/04(土) 12:26:300, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 0, 3
0, 0, 1, 0
0, 0, 1, 1
0, 0, 1, 2
0, 0, 1, 3
...
3, 3, 3, 3
時計的な "n+1進数"が k桁の繰り上がりパターンを生成、
k個の数の和が n であるパターンを全列挙する・・・
0619デフォルトの名無しさん
2007/08/04(土) 12:37:59n個のボールに、どの箱に入れるかを決めるようにしたら。
パターン重複を避けるには、n個のボールに順序性をもたせる。
例えばボールno.2はno.1の左側に置いてはいけないようにする。
0620デフォルトの名無しさん
2007/08/04(土) 12:41:250621デフォルトの名無しさん
2007/08/04(土) 12:43:54n個の○とk-1個の | を一列に並べろ
ってことでいいんじゃないのか?
配列を逆にして同じものはあとで省くということで。
0622デフォルトの名無しさん
2007/08/04(土) 12:49:06再帰が使えるなら簡単で、
「n 個の箱に k 個のボールを入れる全パターンは
先頭の箱に i 個入れて残りの箱に k-i 個入れる
パターンを全部かき集めてきたもの」
でいい。
対称性は後で除いて十分 (計算量は O( nCk ) なので変わらない)
>>618
その計算量は O( n^k ) なので、
パターン総数 O( nCk ) に対して漸近的に悪い。
0623デフォルトの名無しさん
2007/08/04(土) 13:02:13A,A,A
A,A,B
A,A,C
A,A,D
A,B,A ← 降順が含まれるのでなので無視
A,B,B
A,B,C
A,B,D
A,C,A ← 降順が含まれるのでなので無視
A,C,B ← 降順が含まれるのでなので無視
A,C,C
A,C,D
A,D,A ← 降順が含まれるのでなので無視
A,D,B ← 降順が含まれるのでなので無視
A,D,C ← 降順が含まれるのでなので無視
A,D,D
:
:
D,D,D ← 降順が含まれるのでなので無視
A,B,C,Dをそれぞれ0,1,2,3に置き換えると「n桁のk進数」となる。
0624デフォルトの名無しさん
2007/08/04(土) 13:02:540625デフォルトの名無しさん
2007/08/04(土) 13:10:04そうかK-1回のループと変数2個配列2個くらいでいいのか。頭いいな
左右から交互に左>=右になるよう|を置いていけば
一発で重複パターンなしに生成できそうだ
0626613
2007/08/04(土) 13:17:07パターン生成内容としてはそういうことかな。
>>625の実装イメージがまだ理解できず・・・
n個のボール、k個の箱の左右対称分を除いたパターン数は組合せの式で
(n+2)! / ( (k-1)! * (n-k+3)! ) でいいのだろうか。
n=3, k=4 だと 5! / ( 3! * 2! ) = (1*2*3*4*5) / ( (1*2*3) / (1*2) ) = 120/12 = 10
最初に10通りと分かって、そこから 0〜9 番目のうち x 番目のパターンはコレ、とやるには
やはり結果を配列に入れてことになるのかな。
0627デフォルトの名無しさん
2007/08/04(土) 13:30:04箱の数: K
箱内のボール数: NumBall[ K - 1 ]
パターン数: NumPattern= getNumPattern( N, K )
パターン番号: x ( 0 ≦ x <NumPattern)
x を指定したとき、対応する NumBall[ 0 ] ... NumBall[ K - 1 ] を求めよ
0628デフォルトの名無しさん
2007/08/04(土) 13:35:400629デフォルトの名無しさん
2007/08/04(土) 13:38:55アルゴリズム分かったけど携帯じゃ打ち込めないorz
0630デフォルトの名無しさん
2007/08/04(土) 15:04:59> (n+2)! / ( (k-1)! * (n-k+3)! ) でいいのだろうか。
違うな。
Excel だと COMBIN(n+k-1, k-1)
0631デフォルトの名無しさん
2007/08/04(土) 15:19:30これで全パターンを格納する配列を確保できる
0632デフォルトの名無しさん
2007/08/04(土) 15:37:020633デフォルトの名無しさん
2007/08/04(土) 20:13:25#define K (4)
struct stPattern
{
int NummBall[ K ];
int nDec;
int nDecRev;
};
int ipow(int nValue, int nPower)
{
int nRet = nValue;
int i;
for (i = 2; i <= nPower; i++)
{
nRet *= nValue;
}
return nRet;
}
0634デフォルトの名無しさん
2007/08/04(土) 20:15:04{
int i, p;
p = 1;
for (i = 1; i <= r; ++i) {
p *= (n - i + 1);
p /= i;
}
return p;
}
0635613
2007/08/04(土) 20:21:12http://tool-ya.ddo.jp/webfs/~enigma/hoge.zip
DL/解凍パス
NumBallPattern
0636613
2007/08/04(土) 20:23:271 : 2 1 0 0
2 : 1 2 0 0
3 : 0 3 0 0
4 : 2 0 1 0
5 : 1 1 1 0
6 : 0 2 1 0
7 : 1 0 2 0
8 : 2 0 0 1
9 : 1 1 0 1
N=3、K=4 の実行結果
0637デフォルトの名無しさん
2007/08/04(土) 22:25:00よくわからん上に、n = 6, k = 12 でさえ相当の時間がかかる。
ダサいというか、ひどい。
0638629
2007/08/04(土) 22:47:53#include <stdio.h>
void dispList(int *box) {
int i,e;
for(i=0;box[i]>=0;i++)/**/;e=i-1;
for(i=0;i<=(e-1)/2;i++){
if(box[i]<box[e-i]) return;
if(box[i]>box[e-i]) break;
}
for(i=0;i<=e;i++) printf("%d ",box[i]);
puts("");
}
void genLists(int *box,int n,int k) {
int i;
if(k==1) {
box[0]=n;
dispList(box);
}else{
for(i=n;i>=0;--i) {
box[k-1]=i;
genLists(box,n-i,k-1);
}
};
}
int main() {
int n=3,k=4,*box;
box=(int*)malloc(sizeof(int)*(k+1));
box[k]=-1;
genLists(box,n,k);
system("PAUSE");
return 0;
}
0639デフォルトの名無しさん
2007/08/04(土) 22:57:47http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/4817.c
0640613
2007/08/04(土) 23:04:13実際はVC++でcpp、includeはコピペ忘れ。
書いていなかったけど、Kは6、Kは16くらいまでの上限を想定している。
>>638
スマートで速い。これの方がずっと良いね。
0643デフォルトの名無しさん
2007/08/04(土) 23:13:340644638
2007/08/04(土) 23:26:42うわ、びっくりしたw。オレんと違ってデータ残してるのね…
>>642
ゴメン。627のことはすっかり忘れてた。 639さんの使ってけれ
0645639
2007/08/04(土) 23:31:05613 が残していたのでそれにあわせたのです
0646613
2007/08/04(土) 23:37:19パターンが網羅できていれば、順番は特に問いません。
>>638のソースをベースに、>>639のデータ記録を盛り込もうと試行中・・・
0647613
2007/08/05(日) 00:33:49問題を単純化しようとして敢えて”ボール”と”箱”にしたけれど、本当はバス線の分岐パターンを網羅したいという問題。
バス線につながるノード数と分岐数を決めたとき、全体としてありえる接続パターンを無駄なく網羅したかった。
だから左右対称のパターンは要らないとかの付加条件も発生。
仮にノード数を 8、分岐数を 3 にするとき、バス両端の 2ノード、"分岐"を必ず発生するための 3ノードは固定条件で、
残り 3 ノードをどの各分岐点にいくつ接続するパターンはいくつで、具体的にどうか?という問題になる。
分岐数が変わっても問題を定義できるよう、バス両端のバスを (ノード数 - 2 + 1) 個に分割して考える。この例だと
N03 .N04 .N05 .N06 .N07 N08
.│ .│ │ .│ │ .│
N01─B01┴B02┴B03┴B04┴B05┴B06┴B07─N02
とB01〜B07の7本。分岐数を 3 にするということは、B02〜B06 のうち 3本の長さをゼロにする処理になる。
長さゼロにすべき3本の組合せパターンを網羅し、そこからランダムに一つ選んで、残りの長さゼロではないバス線と
分岐線による別の処理を・・・というところに行き着ける土台ができますた。
この例のパターンを示すソース
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/4819.c
0648613
2007/08/05(日) 00:36:13残り 3 ノードをどの各分岐点に接続するパターンはいくつで、具体的にどうか?という問題になる。
0649デフォルトの名無しさん
2007/08/05(日) 00:36:31くそ天皇 くそ天皇 くそ天皇 くそ天皇
いい加減死ねっつってんだろ屑ニートくそ天皇が
相変わらず病的な粘着っぷりだな屑ニートくそ天皇が
毎日毎日毎日粘着出来て良いでちゅねくそ天皇
くそ天皇さっさと死にやがれゴミが
東京に在住している精神病珍米糞ニートくそ天皇君の末路
さっさと精神病院逝くか首吊って逝くか選べや糞天皇が
早く死ねよ糞ニート天皇が
粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が
早く死ねっつってんだろ屑ニートくそ天皇が
お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや
とっと死に晒せや糞ニート天皇が
0650613
2007/08/05(日) 00:36:540651デフォルトの名無しさん
2007/08/05(日) 00:37:03くそ天皇 くそ天皇 くそ天皇 くそ天皇
いい加減死ねっつってんだろ屑ニートくそ天皇が
相変わらず病的な粘着っぷりだな屑ニートくそ天皇が
毎日毎日毎日粘着出来て良いでちゅねくそ天皇
くそ天皇さっさと死にやがれゴミが
東京に在住している精神病珍米糞ニートくそ天皇君の末路
さっさと精神病院逝くか首吊って逝くか選べや糞天皇が
早く死ねよ糞ニート天皇が
粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が
早く死ねっつってんだろ屑ニートくそ天皇が
お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや
とっと死に晒せや糞ニート天皇が
0652デフォルトの名無しさん
2007/08/05(日) 01:03:57敵を騙すにはまず味方から・・・って俺らを騙したのか!!!!?
0653デフォルトの名無しさん
2007/08/05(日) 01:15:33俺は最初から >>647 の書き方をされたら、
読む気が起きなかったと思う。
0654デフォルトの名無しさん
2007/08/05(日) 13:11:45ttp://www.1101.com/morikawa/index_AI.html
0655デフォルトの名無しさん
2007/08/15(水) 23:43:02に記述されている、
図4の(a)から(b)の結果はどのようなアルゴリズムになりますか?
0656デフォルトの名無しさん
2007/08/15(水) 23:55:570657デフォルトの名無しさん
2007/08/16(木) 00:11:570658デフォルトの名無しさん
2007/08/16(木) 00:31:27過程を知りたいわけです。
0659デフォルトの名無しさん
2007/08/26(日) 06:26:050660デフォルトの名無しさん
2007/08/26(日) 15:40:510661デフォルトの名無しさん
2007/10/10(水) 21:54:170662シロートです
2007/10/12(金) 09:00:55アルゴリズムについて質問があります。質問はどこでしたらいいのか
分からなかったのでこちらに書かせていただきます。スレ違いかもしれませんが
お願いします。もしアルゴリズムの質問板があるならそちらも教えていただけるとありがたいです。
C++言語を使っています。質問です。
4種類の連続した数値のデータがあります。4種類の測定時間や時間間隔は一緒です。
その4種類をひとまとまりとします。そのまとまりがいくつかあります。
それぞれのまとまりから一部分だけを取り出します。その一部分のデータの特徴を
どんどんと集めていき4種類のデータの特性を求めたいです。その方法がわかりません。
すいません。ホントシロートです。質問の意味がわからないかもしれません。
でも本当に困ってます。ヒントだけでもいいのでお願いします。
プログラムが違うのかもしれませんが、
「似たようなデータをどんどん記憶していくことによりそのデータ達の
特性を求める」ということかなと自分では考えたのですがその方法も分かりません。
方法を知っているとかこんなコマンドがあるなど本当に何でもいいのでよろしくお願いします。
4種類のデータはヘリコプタの制御に使う、スロットル、エルロン、エレベータ、ラダーです。
特性はホバリングをしている時の4種類のデータ入力の特徴を見つけたいです。
よろしくお願いします。
0663デフォルトの名無しさん
2007/10/12(金) 09:39:360664デフォルトの名無しさん
2007/10/12(金) 10:55:47取り敢えず、「ヘリコプタ」「ホバリング」「制御」で検索して、見つかったサイトを全部読んできてくれ。
0665デフォルトの名無しさん
2007/10/12(金) 20:23:570666デフォルトの名無しさん
2007/10/12(金) 22:38:27アルゴリズムとロジックの違いはなんですか?
新人研修で先輩に質問したら、ググレカスのひとことで片づけられましたが
いまだに謎が解けません。
よろしくです。
0667exc
2007/10/12(金) 23:09:07アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか?
0668exc
2007/10/12(金) 23:11:34>>662
アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか?
0669exc
2007/10/12(金) 23:16:02アルゴリズムよりもロジックの方が大きな概念なんじゃないでしょうか。
アルゴリズムならロジック的である。
ロジック的だからといってアルゴリズムとは限らない。
0670デフォルトの名無しさん
2007/10/13(土) 17:20:04アルゴリズム:代数的な要素をもった解析可能な処理手順。
または特定の言語に寄らない処理手順の記述
ロジック :コーデイングよりの処理手順
0671デフォルトの名無しさん
2007/10/13(土) 21:38:36公理と推論規則で構成するのがロジック
0672デフォルトの名無しさん
2007/10/15(月) 13:27:45そんな本は捨てたほうがいいな
0673デフォルトの名無しさん
2007/10/15(月) 19:39:190674デフォルトの名無しさん
2007/10/15(月) 20:17:170675デフォルトの名無しさん
2007/10/15(月) 21:16:410676デフォルトの名無しさん
2007/10/16(火) 00:50:130677デフォルトの名無しさん
2007/10/16(火) 00:57:060678デフォルトの名無しさん
2007/10/16(火) 16:09:430679デフォルトの名無しさん
2007/10/16(火) 19:12:340680デフォルトの名無しさん
2007/10/16(火) 21:57:350682デフォルトの名無しさん
2007/10/18(木) 00:07:020683デフォルトの名無しさん
2007/10/18(木) 10:41:28ロジック = 実装されている処理方法
でないの…何か違うな…
0684デフォルトの名無しさん
2007/10/18(木) 11:46:10そんな明確な定義が周知されてない言葉なんか場に応じて使い方が異なるに決まってんだろ
0685デフォルトの名無しさん
2007/10/18(木) 13:19:38アルゴリズム(理論)はロジック(論理)で実装される。
0686デフォルトの名無しさん
2007/10/18(木) 13:21:370687デフォルトの名無しさん
2007/10/21(日) 16:55:37AVL木の方が性能が良いんですがなんか間違ってますか?
赤黒木の方が使えるとか聞くんですけど。
0688デフォルトの名無しさん
2007/10/21(日) 20:03:120689デフォルトの名無しさん
2007/11/01(木) 21:16:270690デフォルトの名無しさん
2007/11/30(金) 21:00:49バグがあるかもしれないし、処理範囲を限定して実装されるかもしれない。
0691デフォルトの名無しさん
2007/12/31(月) 15:10:26アルゴリズムの性能評価って何してるんだ
意味わかんね
分かる人いたら教えてクダーサイ
0692デフォルトの名無しさん
2008/01/03(木) 01:41:010693デフォルトの名無しさん
2008/01/03(木) 19:49:07ということで、性能とは何か ということが焦点になると思う
アルゴリズムの性能 というのは何を意味するのか
ブラックボックス的な評価で言うなら
・機能を満たすこと
・メモリ使用量
・速度
この3つの観点に絞られるような気がする
0694デフォルトの名無しさん
2008/01/04(金) 16:21:28C言語の学習とあわせて学習してます。
search algorithmについて質問です。
10冊ほどパラパラと実際にalgorithmのテキストを見て吟味しましたが、
どの本もツリー・スタックといったありきたりのデータ構造を前提として
そこからいかに高速に少ないメモリ使用量で検索するかという話になっていました。
私は、データ構造をいかに工夫するかという方向でも考察したいのですが、
手がかりになるテキストはありますでしょうか???
また、前提となる知識にどういったものがありますか??
数学については大学教養レベルまではかろうじてある程度です。
computer scienceについてはド素人です。
たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、
データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
有益な検索システムが出来そうな気がします。
「そういうことは普通やらない」or「そういうことは既に考え尽くされている」のだとしても、
そういうことを自分でしっかり考えてみたいんです。
よろしくお願いします。
0695デフォルトの名無しさん
2008/01/04(金) 22:47:10具体例を挙げれないので申し訳ないが、
論文を探してみるのも良いかと思うよ。
0696デフォルトの名無しさん
2008/01/05(土) 00:40:45いっていたんですが何でアルゴリズムに寿命があるんでしょうか?
アルゴリズムってプログラムだから寿命もくそも無いと思うんですが
頭悪い僕に簡単に教えてくれないでしょうか?お願いします。
0697デフォルトの名無しさん
2008/01/05(土) 00:51:040698デフォルトの名無しさん
2008/01/05(土) 01:00:13よく考え付くよって思うよ。
0699デフォルトの名無しさん
2008/01/05(土) 01:05:37> たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、
漢字変換アプリで1回変換したのは候補の最初に移動するって
のはあるけど、使用頻度の低い奴をスワップアウトするとかは
どうすんやろ、逆に教えて。
> データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
> 有益な検索システムが出来そうな気がします。
これはどう役に立つの?
0700デフォルトの名無しさん
2008/01/05(土) 01:27:48データ構造で最近面白いと思ったのは succinct structure だな。
興味があったら調べてみて。
0701694
2008/01/05(土) 03:43:59論文というとACMとか情報処理学会とか入ったほうがいいですかね。
オススメの論文誌ありますか。
ipsjは一度入ってたんですけどね、学生会員だから安いと思って。
>>699
前半は初学者なので分かりません。
後半はサーチをする順序の問題です。
優先度をエントリごとに与えることで優先度の高いものから順にサーチすることにより高速にデータが見つかる可能性が高まります。
優先度自体は人間的主観に基づいてつけるものなのでアルゴリズムの問題ではないですが、
それをどう動的に付け替えるかといったことはアルゴリズムをどう適用するかという問題だし、実践上役に立つと思います。
距離を定義することで、エントリ間の類似度が定義されますと、似たものどうしをまず一通り探すという深さ優先的なサーチをするのか
とりあえずいろんな種類のものをひととおりサーチするという幅優先的なサーチにするのかといった選択も可能になります。
すると、状況に応じて適したサーチメソッドの選択ができるようになります。
ツリーとかスタックといった定型的なデータ構造に限らないより一般的なデータ構造において、どうサーチをするのかということを
考える際に有益だと考えました。
もちろん以上は素人考えなので間違いも含まれると思います。
忌憚ないご意見ください。
>>700
succinct data structureというのはチラッと見た覚えがあります。
是非調べてみます。ありがとうございます。
0702デフォルトの名無しさん
2008/01/05(土) 05:17:27検索対象に対して優先度を計算し直した時点で
すでにデータをナめてることになるんだけど・・・
だからあり得ない []
距離じゃなくてシグネチャとかハッシュ値の一致するものの
中から探すってのならあるけど。
こっちなら検索対象との距離じゃなくてただの絶対的に計算できる
値だから
0703デフォルトの名無しさん
2008/01/05(土) 07:52:46大学によって違うのかな?
0704694
2008/01/05(土) 16:26:31> 検索対象に対して優先度を計算し直した時点で
> すでにデータをナめてることになるんだけど・・・
ド素人の意見なので、通じないかもしれませんが、
私の考えとしては、検索のたびに優先度を計算しなおすのではなくて、
前もって優先度を指定してデータを格納しておき、そして毎回の検索に役立てるというやり方がいいかな
と考えました。
>距離じゃなくてシグネチャとかハッシュ値の一致するものの中から探す
なるほど、前もってデータを分類しておき、検索速度を上げるんですね。
私の興味があるのは、テキストデータのような容易には一律な分類が出来ないもの
(あるいは一律に分類してしまうと強い作為性が生じてしまい実用に耐えないもの)です。
そういった場合に、距離を定めるといいのではと思いました。
>>703
大学生のときにはipsj入っていたという意味で、今は卒業しています。
卒業生として図書館利用することもできますが遠隔地なので手間です。
0705694
2008/01/05(土) 16:30:57距離を定めるといい、と書きましたがこれは一例で、
そういった言わば「変な」「特殊な」数学を駆使した技術でこれまでにないことが出来たら
面白いと思っています。
私は学究的に変で特殊なことだけをやりたいのではなく、一つの選択肢として出来れば面白いと考えている程度です。
もちろん、スタンダードな理論も学習するつもりですが。
0706デフォルトの名無しさん
2008/01/05(土) 16:47:14めんどくさがらずに沢山の論文を読むことだね。
0707694
2008/01/05(土) 18:48:59ありがとうございます。ACM, ipsjに入ることにしました。
論文といった大それた話とは別に、データ構造の側の工夫というのが行われてはいないんでしょうか。
例えば、RDBでデータの格納のしかたを工夫することで検索コストとスピードを上げるだとか、
Googleなどで使われているようなテキスト検索技術だとか。
アルゴリズムとは違う話なのかもしれませんが、そういうのにも興味があって、アルゴリズムではそういうことは扱わないのかな
と思いました。
0708デフォルトの名無しさん
2008/01/05(土) 19:05:230709デフォルトの名無しさん
2008/01/05(土) 22:03:42namazとかか
0710デフォルトの名無しさん
2008/01/08(火) 04:29:030711泉 こなた
2008/01/08(火) 07:46:510712デフォルトの名無しさん
2008/01/08(火) 12:14:13他にも。
・安定性(データによって所用時間が大きく変動しない)
例:クイックソートでは、ソート済みのデータソートには時間がかかる
・確実性
例:漸近法では解が発散することがある。
0713694
2008/01/09(水) 04:14:30既存のデータ構造以上のものを作る、が希望要件ではなくて、
今年中をめどに、アルゴリズムに関する学習を徹底してやる、というのが希望するところです。
来年からは違ったプロジェクトが発動するので、それのための準備期間です。
だから、学究的な立場でデータ構造を研究して成果をあげたいのではないです。
そうではなくて、ド素人からプロの知識レベルくらいになりたいということです。
そのためにリサーチをかけて、本を10冊ばかりざっと読みましたが、どうも求めているような
高い水準で特殊な実用にも耐えるタイプの本がすくないということです。
一番面白かったのは『情報の構造』という本でした。
これは他の本と違って、ユニークなデータ構造をからめたアルゴリズムの記述が多々ありました。
そこで、こういったタイプの本が他にもないか、と探していたのです。
0714デフォルトの名無しさん
2008/01/09(水) 04:47:14実用的なものほどそういう傾向が強い。
ユニークなものは大抵アカデミックに留まるもんだ。
>ド素人からプロの知識レベルくらいになりたい
焦らない方が…
0715デフォルトの名無しさん
2008/01/09(水) 05:09:060716デフォルトの名無しさん
2008/01/09(水) 05:24:12無理に変わったものに手をだそうとするのは時間の無駄。
0717694
2008/01/09(水) 11:24:08一年猶予期間があります。それまでにプロフェッショナルになることは不可能な話では
ないでしょうか。いきなりプロになろうとしているのではありません。
昨日も100ページほど本をじっくり読み進めました。
ゆっくり確実にコツコツとやろうとしていますので、どうかその意図をご理解くださると嬉しいです。
>>715
よく見かけるアルゴリズムが低水準だという意味ではないので、誤解のある書き方をしてしまいました。
申し訳ありません。
私が言いたかったのは、私の想定する特殊な用途のためには、ハイパフォーマンスを発揮できないのではないか、
ということです。
たとえば、ネットワークルーティングアルゴリズムを実装するのにはどんなデータ構造が適しているでしょうか。
グラフ構造というちょっと手強いデータ構造を必要とするかもしれません。
つまり、どんな状況でどんなデータ構造が必要とされてくるか分からない状況で、
stack, treeといった初歩的なdata structureだけしか知らずに太刀打ちしようとするのは無謀だと考えたのです。
プロフェッショナルなスキルを身につける上では、当然グラフ構造、ひいてはグラフに関する
数学理論も理解したいものですよね。
私が言う特殊な状況での高水準というのはそういうことです。
まだどんな仕事がくるか分からないので、そういう万全な勉強をしたいのですよ。
>>716
はい、変わったものを要求しているわけではないことは上の記述でご理解いただけたのではないかと
思います。
逆にお聞きしますが、スタンダードなデータ構造でいかにプロフェッショナルな仕事をするかという方向性でも
今後一年勉強する予定なのですが、その場合私が見かける書籍での学習では不十分な気がしてなりません。
何かアドバイスください。
0718694
2008/01/09(水) 11:26:34× 不可能な話ではないでしょうか。
○ 不可能な話ではないのではないでしょうか。
0719デフォルトの名無しさん
2008/01/09(水) 13:03:380720694
2008/01/09(水) 15:09:17そうします。助言ありがとうございます。
0721デフォルトの名無しさん
2008/01/09(水) 21:02:210722デフォルトの名無しさん
2008/01/10(木) 00:24:45アルゴリズムの問題を下に示します。
今、n個の数字を大きい順に並び替える事を考える。
ただし、同じ数字がある場合、これらは等価と見て並び替えなければならない。
つまり3つの0を考えた時、これらを
0a, 0b, 0cと見て、
これをソートした場合、毎回同じ並びになってはいけないものとする。
このようなソートアルゴリズムを考えよ。
良い方法はありませんかね。
0723デフォルトの名無しさん
2008/01/10(木) 00:41:14宿題か?スレ違いだぞ。
通し番号つけてその番号でソートしろ。
毎回同じ並びになってはいけないって毎回同じデータが来るのか?
だったらn通りの組み合わせを全て出現させる方法を調べろ。
その方法で同値部分の通し番号をつけ直せ。
0724デフォルトの名無しさん
2008/01/10(木) 02:11:09あるよー
stable_sort
0725デフォルトの名無しさん
2008/01/10(木) 09:09:12>724
>724
0726デフォルトの名無しさん
2008/01/11(金) 00:58:04permutation
0727デフォルトの名無しさん
2008/01/11(金) 09:03:18ソート時の大小比較の判定を,2つのoperandの値が等しい時は乱数で決定するようにすればどう?
0728デフォルトの名無しさん
2008/01/11(金) 10:38:120729デフォルトの名無しさん
2008/01/11(金) 11:54:450730デフォルトの名無しさん
2008/01/11(金) 15:19:490731デフォルトの名無しさん
2008/01/11(金) 20:06:22というのが問題の意図なんだから、毎回同じ並びだとおかしい。
0732デフォルトの名無しさん
2008/01/11(金) 20:24:220733デフォルトの名無しさん
2008/01/11(金) 20:43:140734デフォルトの名無しさん
2008/01/11(金) 21:19:13random_shuffle() -> sort()
0735デフォルトの名無しさん
2008/01/11(金) 21:49:320736デフォルトの名無しさん
2008/01/11(金) 23:45:150737デフォルトの名無しさん
2008/01/12(土) 00:03:31シャッフルの計算量ってO(n)だから
十分効率的だよね。俺的にはそれでFAです。
0738デフォルトの名無しさん
2008/01/12(土) 00:07:580739デフォルトの名無しさん
2008/01/12(土) 00:29:37が「毎回必ず違う並びにならなければならない」なのか「必ず毎回同じになるようではならない」なのか
0740デフォルトの名無しさん
2008/01/12(土) 04:45:48まあボゴソートでいいんじゃない? 実装簡単だし。テストが大変かもだけど。
0741デフォルトの名無しさん
2008/01/12(土) 09:27:53調べたらプチわろたw なんという天に任せる手法www
投げやりすぎw
0742デフォルトの名無しさん
2008/01/12(土) 09:45:58前者の方が早い?
0743デフォルトの名無しさん
2008/01/12(土) 09:48:06論理が破綻しているんですか?
~(毎回同じ並びになる)
って事だから、同じやつが連続で出てもいいが、無限回やって
毎回同じ並びになるのはやめいって事だよ。
あったまわる・・
>>741
これはソートというのか・・・
カード投げて拾うとか・・・
0744デフォルトの名無しさん
2008/01/12(土) 09:56:54前者はソート法を選べるから例えばクイックソートを使えばO(n logn)になる。
従って、追加するデータがランダムならば前者がいい。
しかし、例えばカードゲームの持ち札のように常に部分がソートされている必要がある場合は
後者の方がいいとも言える。
0745デフォルトの名無しさん
2008/01/12(土) 09:57:33http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88
0746デフォルトの名無しさん
2008/01/12(土) 10:16:17例えばこんなのが並んでいるだけでもいいんだけど。
ttp://ja.wikipedia.org/wiki/%E7%94%BB%E5%83%8F:Bubble_sort_animation.gif
0747デフォルトの名無しさん
2008/01/12(土) 10:38:410748デフォルトの名無しさん
2008/01/12(土) 10:41:53doubt
b-tree
0749デフォルトの名無しさん
2008/01/12(土) 11:07:560750デフォルトの名無しさん
2008/01/12(土) 11:23:26もしかして "stable sort でなければ何でもいい"って, 話なのではあるまいか?
0751デフォルトの名無しさん
2008/01/12(土) 17:02:26俺はあのソートの背景にある理論を知って涙を流した。
笑い涙だが。
0752デフォルトの名無しさん
2008/01/12(土) 17:41:370753デフォルトの名無しさん
2008/01/12(土) 20:25:010754デフォルトの名無しさん
2008/01/12(土) 20:45:290755デフォルトの名無しさん
2008/01/12(土) 20:45:530756デフォルトの名無しさん
2008/01/13(日) 21:35:51うん
0757デフォルトの名無しさん
2008/01/13(日) 21:36:51教えてください
0758デフォルトの名無しさん
2008/01/13(日) 21:50:12rand() % 6;
よりも
rand() / (RAND_MAX + 1.0) * 6;
の方がいいんですか?
なぜですか?
0759デフォルトの名無しさん
2008/01/13(日) 21:59:480760デフォルトの名無しさん
2008/01/13(日) 22:03:34俺は前者の方が読みやすくて良いと思うけど、
後者の方にもメリットはある。
rand関数の実装方法は処理系依存で内部がどうなってるかわからない。
ただ、完全な乱数をコンピュータで手軽に作りだすことは出来ないから、
当然何らかの疑似乱数関数になっている。
その疑似乱数はあくまでも疑似で、実装によっては
もしかしたら一番下のビットが必ず0になるようなアホな設計かも知れない。
そんな場合、rand()%6 だと0 2 4しか取り出せなくなってしまう。
そういう場合、乱数の範囲から特定する方法(後者の方法)ならば
まず間違いなく0〜5の値を出力することが保証される。
多分こういうことだと思う。何か他にもあればだれかプリーズ
0761デフォルトの名無しさん
2008/01/14(月) 04:49:510762デフォルトの名無しさん
2008/01/14(月) 09:17:280〜5なら問題ないが
int x = rand() % 10000;
とかした場合、明らかな偏りが発生してしまう。
0763デフォルトの名無しさん
2008/01/14(月) 09:42:36これも偏りが発生すると思うんだが。
0-32767 -> 0-5
という変換なんだから。
擬似乱数スレに回避する方法があったぞ。
0764デフォルトの名無しさん
2008/01/14(月) 10:14:430765デフォルトの名無しさん
2008/01/14(月) 13:19:16実際は、2^ビット幅/6 と掛け算して、上位ワードを採用するんだけどね
0766デフォルトの名無しさん
2008/01/14(月) 13:44:140767デフォルトの名無しさん
2008/01/14(月) 14:23:17多分勘違いをしていると思うが、% 10000 で [0 .. 9999] にするとき、RAND_MAX が 32767 なら、
[0 .. 2767] が4通りになり、 [2768 .. 9999] が3通りになる。
>762 は、この4通りの部分がゼロ方向に集まることを指しているのだと思う。
[0 .. RAND_MAX] を [0 .. 9999] に線形に写像すれば、4通りの部分が全範囲にわたって均等に分布するようになる。
それでも4通りの部分をなくそうと思ったら、擬似乱数スレにあるように、RAND_MAX - (RAND_MAX % 10000) 以上を棄却するとよい。すると、どちらの方法でも均等になる(元の乱数が均等なら)。
0768デフォルトの名無しさん
2008/01/14(月) 15:50:12(int)(rand() / (1.0 + RAND_MAX) * N)
rand() は理想的な乱数生成器だとして、N = RAND_MAX - 1 ならば、
0になる確率が2/RAND_MAX、それ以外は1/RAND_MAXになるよね。
線形な写像でも誤差のせいで均等にならない場合もあると。
>>763 が言ってるのはこのことではないような気もするが
0769デフォルトの名無しさん
2008/01/14(月) 16:52:22みんな標準で入ってる乱数は線形合同法だよ。
0770デフォルトの名無しさん
2008/01/14(月) 16:53:120771デフォルトの名無しさん
2008/01/14(月) 17:16:02一体いつの時代の話ですかwwwwwwwwwww
0772デフォルトの名無しさん
2008/01/14(月) 18:34:49二分木で逆ポーランドに変換してからやる方法をさっき知って感動した
0773デフォルトの名無しさん
2008/01/14(月) 21:12:50ポーランド記法が既に逆ナンであって
逆ポーランドって言ってしまうと
元に戻ってないか?ってことなんだ
0774デフォルトの名無しさん
2008/01/15(火) 05:47:15そういう意味だったのか。
でもなんか中途半端というか偏りを散らした(写像変換した)だけで
本質的な解決策じゃないように感じる。
それに、整数 -> 整数 の変換に実数キャストが挟まるのが凄く無駄に思える。
実数の実装も考慮してないし。
棄却するパターンの方が数学的に美しい。と思う。
0775デフォルトの名無しさん
2008/01/15(火) 07:19:20大抵の実装は線形合同法。線形合同法の乱数は、そもそも特性が悪い。
そして下位ビット程特性が悪いんだ。
だから、余りを使って下位を採用すると隔たりが普通より大きくなるんだよ。
0〜5の乱数が欲しいなら余りじゃなくて上位を採用しなければいけない。
というのと
rand() % 6; は割り算が必要だけど
rand() / (RAND_MAX + 1.0) * 6;
は (RAND_MAX +1)は通常は2のべき乗だから、掛け算+シフトで計算出来るから
大抵のCPUで後者が高速という
2つの理由がある。
0776デフォルトの名無しさん
2008/01/15(火) 07:31:370777デフォルトの名無しさん
2008/01/15(火) 07:37:03それはgccのRAND_MAXがint型の最大値に近いから、じゃない?
0778デフォルトの名無しさん
2008/01/15(火) 07:53:45イメージとしては
(long)rand() * ( 1L<<32L )/6L )>>32L;
アセンブラコードだと EDXに2^32/6を入れて
MUL EDX
MOV EAX,EDX
0779デフォルトの名無しさん
2008/01/15(火) 08:14:15あー
ゲームとかではあるかもしれないけど、アルゴリズムスレの扱う範疇からは外れてるね
移植性が無さ過ぎる
0780デフォルトの名無しさん
2008/01/15(火) 08:31:310781デフォルトの名無しさん
2008/01/15(火) 08:32:090782デフォルトの名無しさん
2008/01/15(火) 12:09:53「偏る」を「へだたる」って読んでる?
0783デフォルトの名無しさん
2008/01/15(火) 14:09:240784デフォルトの名無しさん
2008/01/15(火) 14:19:39>実数の実装も考慮してないし。
え? intへのキャストを外すだけだろ。
rand() / (RAND_MAX + 1.0) は区間[0,1)
(rand() / (double)(RAND_MAX) なら区間[0,1])
の実数の乱数だからな。
>>768 のひどい誤差は整数変換のせいなので
むしろ実数の方が均一でより理想的なんだが。
0785デフォルトの名無しさん
2008/01/15(火) 18:40:21なにが高速だって?
0786デフォルトの名無しさん
2008/02/06(水) 02:28:50最も値の近い要素の組A[k],B[l]を求める良い方法はないですか?
0787デフォルトの名無しさん
2008/02/06(水) 02:42:39Bの各要素にB由来という印とインデックスを付加
二つを合わせて配列CとしてCをソート
Cを先頭から走査して隣り合う要素の由来が違うもので差が最小のところを探す
ってのは?
まぁ合わせないでAB別々にソートしてもできるけど
0788786
2008/02/06(水) 03:04:22AB別々にソートしてからマージの要領で
比較していけばいいんですね。
ありがとうございました。
0789デフォルトの名無しさん
2008/02/06(水) 10:55:18Ο記法とか計算時間の算出部などの計算式の意味がさっぱりわかりません。
Ο(n log n)とか意味がわかりません・・・
文系で最後に数学に触れたのは高2だったので、とっくに忘れているし元々数学は得意ではありません。
自分もそのうち効率は悪くても自分なりのソートアルゴリズムを考えてみたいと思っているのですが、
何から勉強をはじめたらいいでしょうか?
0790デフォルトの名無しさん
2008/02/06(水) 11:34:34さすがに、log の意味から書いてあるのは少ないと思うが、
それくらいは高校の教科書読んで勉強してこいよ。
0791デフォルトの名無しさん
2008/02/06(水) 12:22:49nは要素数でO(n log n)はnが増減した時の計算量の増減。
O(n^2)ならnが倍になると計算量が4倍になるってだけ。(3倍なら9倍)
計算量はあくまで計算量なんでアルゴリズムによって単位量あたりの
計算の複雑さは違うからね。
nlognなやつでもクイックソートとヒープソートは速度が大分違う。
メモリの局所性の問題とかもあったりする。
余計なお世話だと思うがソートは優秀なものが出尽くしてしまっているから
今更考え出すより既存のものを学んだ方が良いよ。
0792デフォルトの名無しさん
2008/02/07(木) 01:10:13今日はQTクラスタリングというのを知ったので
このスレにメモっておく。
0793デフォルトの名無しさん
2008/02/07(木) 20:12:150794デフォルトの名無しさん
2008/02/07(木) 23:13:29マージャンプログラム作ってて発見したよ。
0795デフォルトの名無しさん
2008/02/07(木) 23:21:37いろいろ間違ってるよね。O は計算量とは無関係な概念でしょ。
0796デフォルトの名無しさん
2008/02/07(木) 23:59:090797デフォルトの名無しさん
2008/02/08(金) 00:06:36任意の n ≧ N に対して f(n) ≦ C g(n) が成立することをいう
が、オーダ記法の定義でしょ。
計算量をオーダ記法で表現することは多いけど、別に関係はないよね。
オーダ記法で計算量を表さない分野だってあるよ。
0798デフォルトの名無しさん
2008/02/08(金) 00:16:49ほー勉強になるが全く意味がわからんわw
アルゴリズムって難しいね
0799デフォルトの名無しさん
2008/02/08(金) 04:02:58だから密接な関係があると言うのが普通
概念として独立させることができるとしても
0800デフォルトの名無しさん
2008/02/08(金) 07:55:37> オーダ記法は計算量の理論の研究の中から生まれたもの
このことのソースは?
私の認識では、そんなことは年代的に絶対に有り得ない。
計算量の理論は通常はコルモゴロフの1950年か
チューリングの1936年をスタートだと考えるはず。
一方、オーダ記法自体はバッハマンの1894年が初出で、
広く使われるようになったのはランダウの1909年くらいから。
オーダ記法のほうが古い歴史を持っていると思うのだけれど。
0801デフォルトの名無しさん
2008/02/08(金) 08:08:46>チューリングの1936年をスタートだと考えるはず。
ダウト
0802デフォルトの名無しさん
2008/02/08(金) 08:18:450803799
2008/02/08(金) 18:11:400804デフォルトの名無しさん
2008/02/08(金) 18:18:290805デフォルトの名無しさん
2008/02/08(金) 18:44:38まあ大目に見てやれ。
その前は脳内ソースだったんだから。
0806デフォルトの名無しさん
2008/02/09(土) 20:21:35http://d.hatena.ne.jp/ytakamiya/20080125
0807デフォルトの名無しさん
2008/02/10(日) 16:00:22っつーか10年くらい前に
技術評論者のSoftwareDesign(いまもあるのか?)が記事で
CQ出版のInterfaceが既に過去に取り扱ってた画像を
そっくりそのまま盗用してしまってお詫びしていた
0808デフォルトの名無しさん
2008/02/10(日) 20:46:420809デフォルトの名無しさん
2008/02/14(木) 07:09:16なぜ前からじゃないんでしょうか
0810デフォルトの名無しさん
2008/02/14(木) 07:45:21文字列系アルゴリズムでは prefix より suffix のほうが有用だ
(と思われている)から。
0811デフォルトの名無しさん
2008/02/14(木) 13:06:560812デフォルトの名無しさん
2008/02/14(木) 21:33:07prefix tree, prefix list などがあるよ。
0813デフォルトの名無しさん
2008/02/18(月) 21:23:04自分のレベルが低いため、難しくて実装することができません。
やり方を暗記してしまえば問題ないのですが、
暗記に頼るのではなく、考えてちゃんと実装できるようにしたほうがいいでしょうか?
それとも暗記しとけばいいでしょうか?
0814デフォルトの名無しさん
2008/02/18(月) 21:31:540815デフォルトの名無しさん
2008/02/18(月) 22:45:51同じアルゴリズムを毎回毎回実装するなんて愚かしい。そういうものはライブラリとして持っておくべき。
ということで、実装方法を暗記しても意味がない。
結局、何かやりたいことを実現する=アルゴリズムを考えて実装する、になるし何もかも既存のアルゴリズムが
流用できる、なんてなるわけないから自分で考える必要はでてくる。
その練習として、有名どころのアルゴリズムを自分で実装してみて他の実装と比べてみるというのはいいことだと思う。
0816デフォルトの名無しさん
2008/02/18(月) 23:44:27実装できないと言うよりも
適切なアルゴリズムが分かってないんじゃないのかな。
あるいは、目的がぼんやりしているとか。
まぁいずれにしても、アルゴリズムは暗記でいい派だね。
さらには、辞書とか検索で調べられる程度の情報だけでいい。
0817デフォルトの名無しさん
2008/02/19(火) 00:38:360818デフォルトの名無しさん
2008/02/19(火) 02:25:49質問が二つ。
(1) 「自分のレベルが低い」というのは、プログラム能力が低いのか、
それともアルゴリズムを実装に起こす能力が低いのかどっち?
前者なら慣れればなんとかなる。後者ならそもそもアルゴリズムを
十分に理解できていない可能性が高い。
(2) あなたの立場と考えてるアルゴリズムは何?
極端なケースでは、研究者が自分の専門分野のアルゴリズムを
暗記しているようでは全然ダメ。
0819デフォルトの名無しさん
2008/02/19(火) 03:36:37どういう動作するのか、どうプログラムしていいのかとか分からないって状態なんじゃね?
とても概念がわかってるとは言えないと思うけど。
0820813
2008/02/19(火) 20:53:16>>819さんの指摘していただいてるような感じです。
ただ、どういう動作をするのかは理解しているつもりなんですが、
書き起こせないってことはやはり概念を理解していないんですかね・・・
>>818
1の質問についてですが、両方ですかねぇ・・・
プログラムでどういう風に書けばいいかわからないみたいな感じです。
特にループ部分などが・・・ループのネストなんてやったことなくて・・・
2についてですが、
立場はただの趣味でやっているみたいなもんですかね。
将来的にプログラマを目指したいとは思っています。
アルゴリズムは探索やソートなどの基本的なものです。
基本的にソートや探索などの関数は、プログラム側で用意されていますし、
>>815さんの仰るとおり外部ライブラリとしてもっておけばいいのですが、
一応理解したうえで使うべきものなのかなぁと思って質問しました。
0821デフォルトの名無しさん
2008/02/19(火) 21:02:26自分で手を動かさない香具師は向いてない
0822デフォルトの名無しさん
2008/02/19(火) 21:42:40とりあえず何でも良いから山ほどプログラム書くところからだね.
0824デフォルトの名無しさん
2008/02/21(木) 00:09:25とはいっても、どうせ同じようなのを他の人が見つけてるだろうけど…
数学的に厳密な書き方を知らないので雰囲気で書くけど、
m個の離散値を取る(たとえば整数1〜mまで、など)集合に属する値のソートの場合、
O(n×m)でソートが出来る。
例えば0〜127の整数10000個を降順ソートするプログラムはこちら
int array[10000] = {};
for(int i = 0; i < 10000; i++) { array[i] = rand() % 128; }
// データ構造を配列から2次元マップに変更
bool map[10000][128] = {}; // 全部false
for(int i = 0; i < 10000; i++) {
for(int j = 0; j < array[i]; j++) { map[i][j] = true; }
}
// ソート
bool result[10000][128] = {}; // 全部false
for(int i = 0; i < 128; i++) {
int count = 0;
for(int j = 0; j < 10000; j++) { if(map[j][i]) result[count++][i] = true; }
}
// 結果を配列に変換
for(int i = 0; i < 10000; i++) {
for(int j = 127; j >= 0; j--) { if(result[i][j]) { array[i] = j; break; } }
}
コンパイル試してませんが…
0825デフォルトの名無しさん
2008/02/21(木) 00:34:34書いたやつは救いようが無いビンソートにしか見えない
0826デフォルトの名無しさん
2008/02/21(木) 00:37:020827デフォルトの名無しさん
2008/02/21(木) 01:02:25何このゴミ
0828デフォルトの名無しさん
2008/02/21(木) 01:48:20同じ事オモタ
0829デフォルトの名無しさん
2008/02/21(木) 07:31:170830デフォルトの名無しさん
2008/02/21(木) 10:21:120831デフォルトの名無しさん
2008/02/21(木) 11:57:59この実装だと時間・空間計算量O(nm)だけど、
mを定数だと考えると、条件付きO(n)ソートになるな。
最も実用上どうかと思うけど、発想は面白そうだな。可視的にやればうけそう
0832824
2008/02/21(木) 16:03:55想像以上に叩かれてションボリ。スレ汚しすまんでした
0833デフォルトの名無しさん
2008/02/21(木) 17:53:300834デフォルトの名無しさん
2008/02/21(木) 18:04:54ビンソートと同列だから目新しさは全くないけど、
ドットを左に寄せていくとソートいう発想はなかなかいいな。
ttp://void-main.org/test/824.html
0835デフォルトの名無しさん
2008/02/21(木) 19:04:42int[] array = new int[10000], count = new int[128]; // 全部ゼロ
for (int i = 0; i < 10000; i++)
array[i] = (int)(Math.random() * 128);
for (int i = 0; i < 10000; i++)
count[array[i]]++;
for (int p = 0, i = 0; i < 128; i++)
for (int j = 0; j < count[i]; i++, p++)
array[p] = i;
0836デフォルトの名無しさん
2008/02/21(木) 19:11:45それは普通のバケットソート
0837デフォルトの名無しさん
2008/02/21(木) 23:45:180838デフォルトの名無しさん
2008/02/22(金) 05:21:040839デフォルトの名無しさん
2008/02/22(金) 11:58:34子曰、學而不思則罔。思而不學則殆。
0840デフォルトの名無しさん
2008/02/22(金) 12:55:53バカだから文脈読めないけど、難しい言葉使って少しでもかしこく見せたいってかw
0841デフォルトの名無しさん
2008/02/22(金) 13:04:580842デフォルトの名無しさん
2008/02/22(金) 17:01:400843デフォルトの名無しさん
2008/02/22(金) 17:02:23> 自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛い
いや、それはいいんじゃね?
0844デフォルトの名無しさん
2008/02/22(金) 17:04:06こういうのを「ゆとり」と言うんだろう
0845デフォルトの名無しさん
2008/02/22(金) 17:04:540846デフォルトの名無しさん
2008/02/22(金) 17:28:580847デフォルトの名無しさん
2008/02/22(金) 18:28:52個々の優劣が明らかに出来る集団で
各順位の分布を初期からほぼ一定にする様なアルゴリズムってかDNA組合せ無いっすか?
自然淘汰してる様で実は歴史は繰り返すみたいなの
松竹梅な比率
1:3:4 第1世代
↓
1:3:4 第N世代
0848デフォルトの名無しさん
2008/02/22(金) 20:19:200849847
2008/02/22(金) 21:54:22例えば各個体に付松なら6回、竹2回、梅1回の試行して次世代も同個体数
確立以上に存在するABO式血液型OO型のナゾを逆方向から見た考察です。
0850デフォルト名無しさん
2008/02/22(金) 23:47:580851デフォルトの名無しさん
2008/02/23(土) 10:12:50step1 『アルゴリズムオタク』スレで質問する
step2 答えを待つ
0852デフォルトの名無しさん
2008/02/23(土) 10:40:16質問1 括弧がないけど 5 + (6/3) でいいのかな?
質問2 何を1ステップに数えるの?メモリへのロードとかは?
0853デフォルトの名無しさん
2008/02/23(土) 11:02:580854デフォルトの名無しさん
2008/02/23(土) 11:23:090855デフォルトの名無しさん
2008/02/23(土) 11:29:57a+(b/3) を a,b入力値で 四則演算で求めろとか?
加算+シフト演算で出すのは2ステップじゃ無理っぽいな
0856デフォルトの名無しさん
2008/02/24(日) 11:39:06激しくカメレスで恐縮だが、あのソートアルゴリズムは
量子コンピュータ向きなのではないだろうか。えっ、違う?
0857デフォルトの名無しさん
2008/02/24(日) 11:59:520858デフォルト名無しさん
2008/02/25(月) 21:03:57教科書で問題として実際に出ているんです・・・・。
おれの頭じゃ無理で・・・
0859デフォルトの名無しさん
2008/02/25(月) 21:21:59>>852 >>855
質問しといてレスをスルーすんな
0860デフォルトの名無しさん
2008/02/26(火) 11:02:000861デフォルトの名無しさん
2008/02/26(火) 19:57:29定番の方法ってあるんですかね。
ぐぐっても参考になりそうなのが見つからなかった。
自分で適当に書いてみたが
数値がでかすぎるとオーバーフローしてソート順が狂う。
0862デフォルトの名無しさん
2008/02/26(火) 20:59:19そうじゃないなら多倍長浮動小数点を自前で作るしかないね
0863デフォルトの名無しさん
2008/02/26(火) 21:07:31用途がファイル名のソートなので
少数とかは考慮しないで大丈夫です。
0864デフォルトの名無しさん
2008/02/27(水) 16:39:07何度やってもバブルソートがヒープソートの半分くらいの時間でソートしてしまいます。
1〜100000のランダム数列に対して、
heap: 167.83 sec
bubb: 83.2852 sec
という感じです。ヒープソートの実装がまずいのでしょうか?
実装はwikipediaからパクりました。
0865デフォルトの名無しさん
2008/02/27(水) 16:43:210866デフォルトの名無しさん
2008/02/27(水) 16:48:060867デフォルトの名無しさん
2008/02/27(水) 16:50:16int a[size] = {1,2,3,4,5,...};と配列を宣言して、
mysort_bubble(a,size);
mysort_heap(a,size);
というように呼び出します。
void mysort_bubble(int* a, int SIZE)
{
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
}
void mysort_heap(int* a, int size)
{
int max = size;
while (max > 0) {
make_heap(a, max, 0);
swap(a[0], a[max-1]);
max--;
}
return;
}
0868デフォルトの名無しさん
2008/02/27(水) 16:51:15void make_heap(int* a, int size, int idx)
{
int j = idx * 2 + 1;
int k = idx * 2 + 2;
if (j > size-1) {
return;
}
if (j == size-1) {
if (a[j] > a[idx]) {
swap(a[j], a[idx]);
}
return;
}
make_heap(a, size, j);
make_heap(a, size, k);
int l;
if (a[j] > a[k]) {
l = j;
}
else {
l = k;
}
if (a[idx] < a[l]) {
swap(a[idx], a[l]);
make_heap(a, size, l);
}
return;
}
0869866
2008/02/27(水) 17:03:03#include<vector>
#include<time.h>
using namespace std;
#define size 3000000+1
#define rnd(n) ((rand()&255)<<(8*n))
bool comp(const unsigned int &a, const unsigned int &b){return a < b;}
main(){
cout<<size-1<<" 個の配列のソート\n\n";
vector<unsigned int> x(size);
for(int i=0;i<size;i++)x[i]=rnd(0)+rnd(1)+rnd(2)+rnd(3);
int cl=clock();
sort(x.begin(),x.end(),comp);
cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";
cout<<"x[0]="<<x[0];
cout<<"\nx["<<size-1<<"]="<<x[size-1];
}
0870デフォルトの名無しさん
2008/02/27(水) 17:13:34-cout<<(cl+0.0)/1000<<"sec\n";
+cout<<(cl+0.0)/CLOCKS_PER_SEC<<"sec\n";
ですよね?
(自分の環境では、CLOCKS_PER_SECは1000000でした)。
たしかに、速いですね。
0871866
2008/02/27(水) 17:14:22鈍すぎ
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
bool comp(const unsigned int &a, const unsigned int &b){return a < b;}
void mysort_bubble(int* a, int SIZE){
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {swap(a[j], a[j+1]);}}}}
main(){
int SIZE=30000+1;
cout<<SIZE<<" 個の配列のソート\n\n";
int *a=new int [SIZE]; vector<int> x(SIZE);
for(int i=0;i<SIZE;i++)a[i]=x[i]=rand();
int cl=clock(); sort(x.begin(),x.end(),comp); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"x[0]="<<x[0];cout<<"\nx["<<SIZE-1<<"]="<<x[SIZE-1]<<"\n\n";
cl=clock(); mysort_bubble(a,SIZE); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"a[0]="<<a[0];cout<<"\na["<<SIZE-1<<"]="<<a[SIZE-1]<<endl;
}
0872デフォルトの名無しさん
2008/02/27(水) 17:23:20ちゃんと見ていないけど、
mysort_heap, make_heap のところで 1 ベースの配列用と
0 ベースの配列用のコードが混じってるからおかしくなっているんじゃない?
0873デフォルトの名無しさん
2008/02/27(水) 18:22:27自己レス。
右寄せってunko1024とunko256ってのがあったら
数字の部分の文字列を抜き出して
256
1024
という風に右寄せしてさらに比較って感じなのかな。
0874デフォルトの名無しさん
2008/02/27(水) 18:23:41...256
1024
0875デフォルトの名無しさん
2008/02/27(水) 19:52:46ja.wikipedia 見た.なんだこのクソ実装.
きちんと解析する気も起きんが,このヒープソートは
どれだけよく見積もっても O(n^2) はかかってる,
具体的には make_heap 1 回が,最後の再帰を止めても
O(n) かかり,これを sort_heap で n 回繰り返すので,
最後の再帰が一回も実行されないとして O(n^2).
0876デフォルトの名無しさん
2008/02/27(水) 20:18:050877デフォルトの名無しさん
2008/03/19(水) 02:28:32いまさらソートなんてそうとう早くない(ry
0878デフォルトの名無しさん
2008/03/19(水) 04:48:20ソートと同じでこれまた定番な話題に文字列検索がありますが、
文字列中で、複数の単語の中から最初に現れるものを検索
する場合はどうするのが良いでしょうか?
例
検索対象の文字列 abcdefg
単語 ac bc bd bcd
この場合だと検索結果は bc bcd の2つになる。
0879デフォルトの名無しさん
2008/03/19(水) 05:14:010880デフォルトの名無しさん
2008/03/19(水) 05:22:02ここまで糞なヒープソートも珍しいw
全く理解してないくせによくwikipedia書けるな…
>>864
http://www.sci.csuhayward.edu/~billard/cs3240/node33.html
0881デフォルトの名無しさん
2008/03/19(水) 07:07:18「最初に現れるものを検索」ってのが理解できない
文字列 abcdefg で単語 bc, de だったら bc だけになるの?
なんにせよ Aho-Corasick の変形でいけそうだけど
0882デフォルトの名無しさん
2008/03/19(水) 07:09:57ac|bc|bd|bcdを正規表現で検索
0883デフォルトの名無しさん
2008/03/19(水) 07:14:43一桁目の、ビットORをとって、対象文字とANDを取り一致すれば調べていけば
0884デフォルトの名無しさん
2008/03/19(水) 08:19:570885デフォルトの名無しさん
2008/03/19(水) 08:50:110886デフォルトの名無しさん
2008/03/19(水) 08:53:39これかな
0887デフォルトの名無しさん
2008/04/08(火) 21:40:54かなりちんぷんかんぷんです
何故5→Aになるのかも意味が分かりません
アルファベットだったら代入するのは何でもいいんでしょうか?
それとも決まってますか?
後アルゴリズムの効率のいい勉強の仕方も教えてくださいm_ _m
0888デフォルトの名無しさん
2008/04/08(火) 21:46:17俺にはお前の質問がちんぷんかんぷんだ
0889デフォルトの名無しさん
2008/04/08(火) 21:48:34こんなこと言うやつは勉強しても身に付かず、結局
「効率のいいアルゴリズム教えてください」
って言うだけになるんだろうな。
0890デフォルトの名無しさん
2008/04/08(火) 21:49:09まず国語の勉強。
0891デフォルトの名無しさん
2008/04/08(火) 21:56:05文章が変なのはリアル厨房なので大目に見てくださいm(_ _)m
はじめはアルゴリズムの何を勉強したらいいんでしょうか?
0892デフォルトの名無しさん
2008/04/08(火) 22:03:040893デフォルトの名無しさん
2008/04/08(火) 22:16:48コミュニケーションに不自由しない程度の日本語力と
高校程度の数学の能力を身に着けることが先決.
たとえば、
自然数に対して定義された関数 T(n) に関する漸化式
T(n) = 2 T([n/2]) + c n, T(1) = c' を考える(c, c' は定数、[ ] は切り上げ).
この漸化式の解 T(n) が次の性質を持つことを証明せよ:
「ある自然数 N と実数 C が存在して任意の n ≧ N に対して T(n) ≦ C n log n」
と言われて自力で証明できないようでは、アルゴリズム論を勉強しても
結局何も身につかない。
0894デフォルトの名無しさん
2008/04/08(火) 22:55:18本を買え。推薦図書スレで推されている本格的なのを。
0895デフォルトの名無しさん
2008/04/08(火) 23:22:08ああ、まったく意味が分からん。
0896デフォルトの名無しさん
2008/04/09(水) 02:18:30通信授業でアルゴリズムを勉強していますがかなりチンプンカンプンな状態です。
Aに5を代入するにはA=5と記述すると習いましたが理解できていません。代入するとはどういう意味なのでしょうか?
またA以外のアルファベットにも5を代入できるのでしょうか?それとも代入可能なアルファベットはAだけなのでしょうか?
あと効率のいい勉強法をお知りでしたらそちらについてもアドバイスお願いいたします。m_ _m
0897デフォルトの名無しさん
2008/04/09(水) 03:14:11代入ってのは変数に値を入れるという意味。
変数ってのは何らかの値を入れるための箱だと思っておけばいい。
そしてここではAってのが箱の名前で、5ってのが箱に入れる値。
ある種のプログラミング言語においてA=5という表現は、
Aという箱に5という値を入れる操作をコンピュータに行わせるという意味であって、
数学における同様の表現とは全く別の意味。
あと箱にAと名付ける事は代入ではないし、箱の名前はAじゃなくてもいい。
0898デフォルトの名無しさん
2008/04/09(水) 05:37:03普通の(手続き型の)プログラム言語を一つ触ってみるといいんじゃないかな.
Java とか Ruby とか何でもいいから.
そうするとだいぶイメージがわくし,今後のためになるはずよ.
0899デフォルトの名無しさん
2008/04/09(水) 08:04:052chで通信授業するのはやめとけ。
0900デフォルトの名無しさん
2008/04/09(水) 12:11:160901デフォルトの名無しさん
2008/04/09(水) 14:01:06どんなことでも、勉強する時は、同じ分野の本を三冊以上読むんだ。
分からないことをスルーしながら、とにかく沢山読む。
すると、何が分からないのかが分かり、何を調べればよいのかがわかるようになるから、それまでに読んだ本から適切な部分を読んで調べることができるようになる。
とにかく沢山読め。
0902デフォルトの名無しさん
2008/04/09(水) 21:54:330903デフォルトの名無しさん
2008/04/09(水) 22:42:350904デフォルトの名無しさん
2008/04/09(水) 23:08:16今のオタクは・・・
0905デフォルトの名無しさん
2008/04/10(木) 03:30:22オタクは自分で調べるが、他人に教えることは不得手。と思う。
0906デフォルトの名無しさん
2008/04/10(木) 07:08:41オタクってのは自己満足のオナニスト。
知識の切り売りをしているような軽薄な連中とは違うのだよ。
0907デフォルトの名無しさん
2008/04/12(土) 12:20:22まさかエレベータに乗ってるとき隣の奴がアルゴリズム考えてるとは思わないわ
きもいから死んでくれ
0908デフォルトの名無しさん
2008/04/12(土) 14:55:180909デフォルトの名無しさん
2008/04/13(日) 02:44:50お前の方がキモイから
0910デフォルトの名無しさん
2008/05/06(火) 07:36:00信号で歩道用と車道用の切り替わりタイミングとかずっと考えてたけどな
そんで周囲からいつもボーっとしてるって言われてた
ココ居るやつらってみんなそんな感じじゃねーの?
0911デフォルトの名無しさん
2008/05/06(火) 08:23:00あー、なんか判るわ。
私もエレベータの操作パネル見ながら点字を自力解釈したりしてたしね。
0912デフォルトの名無しさん
2008/05/06(火) 08:32:230913デフォルトの名無しさん
2008/05/06(火) 09:40:46俺は、そういうのはプログラミングを始めてからだな。
ただ、ボーっとしてると言われたっていうのはよくわかるw
まさか小学生の子供がそんなこと考えてるとか大人は思いもしないんだよな。
0914デフォルトの名無しさん
2008/05/06(火) 18:46:02ローマ字を習う前だったけど
50音表と睨めっこして
子音+母音のパターンは見つけた
(母音や子音なんて言葉は知らなかったけど)
その時はボーッとしてるなんて言われてたけど
今は研究職やってます。脳味噌の構造はそのまま
0915デフォルトの名無しさん
2008/05/15(木) 04:11:56ボーッとしているように見えるほど没頭するのは。
0916デフォルトの名無しさん
2008/05/26(月) 23:16:421.ランダムなプログラムをいくつか生成する。
2.データをプログラムに通す。
3.出力結果を評価する。
満足のいく速度でデータがソートされれば、終了する。
ダメなプログラムに対しては悪い評価を与える。あるいは破棄する。
それなりに有望なプログラムについては、良い評価を与える。
4.現在存在するプログラムをもとに、少し違ったプログラムを生み出す。
5.2へ
これってボゴソートとは違うよね?
時間計算量はどのくらいになるんだろ?
実際、わりと優秀なプログラムが生き残ったっていう話を聞いたけど。
0917デフォルトの名無しさん
2008/05/27(火) 00:53:030918デフォルトの名無しさん
2008/05/27(火) 01:23:50たぶん、本当にそのとおりに実行したら、
現実的な時間ではソートプログラムは作れないと思う。
0919デフォルトの名無しさん
2008/05/27(火) 02:31:24ソートのアルゴリズムではなくて、個数が20個とかに限定されているときに
最小回数の比較でソートするには何番目と何番目をどの順番で
比較して交換いけばいいか?っていう問題だったと思う。
具体的な実装は>>917。
0920デフォルトの名無しさん
2008/05/27(火) 11:41:32http://namidame.2ch.net/test/read.cgi/news/1211740649/l50
0921デフォルトの名無しさん
2008/06/12(木) 22:56:250922デフォルトの名無しさん
2008/06/14(土) 11:55:28あるよ
0923デフォルトの名無しさん
2008/06/15(日) 10:51:100924デフォルトの名無しさん
2008/06/15(日) 22:49:450925デフォルトの名無しさん
2008/06/16(月) 07:44:210926デフォルトの名無しさん
2008/06/16(月) 13:37:390927デフォルトの名無しさん
2008/06/16(月) 14:20:280928デフォルトの名無しさん
2008/06/16(月) 20:45:580929デフォルトの名無しさん
2008/06/16(月) 21:06:020930デフォルトの名無しさん
2008/06/16(月) 22:41:460931デフォルトの名無しさん
2008/06/16(月) 23:51:53はよだせコラ
0932デフォルトの名無しさん
2008/06/18(水) 22:11:510933デフォルトの名無しさん
2008/06/18(水) 23:09:330934デフォルトの名無しさん
2008/06/19(木) 15:07:200935デフォルトの名無しさん
2008/06/19(木) 15:11:030936デフォルトの名無しさん
2008/06/19(木) 20:52:13もちろん、教えてなどやらんがなw
0937デフォルトの名無しさん
2008/06/19(木) 20:53:460938デフォルトの名無しさん
2008/06/23(月) 01:03:020000から1111の完全ハッシュ求める式
教えてください
0939デフォルトの名無しさん
2008/06/23(月) 01:08:29大きさ16のテーブル
0940デフォルトの名無しさん
2008/06/23(月) 01:33:560000から1111までの数の全部を対象に完全ハッシュ値を求めたいの?
0941デフォルトの名無しさん
2008/06/23(月) 01:38:48f(x) = x
0942デフォルトの名無しさん
2008/06/24(火) 00:08:53部分集合の場合もありえます。
0943デフォルトの名無しさん
2008/06/24(火) 00:14:270944デフォルトの名無しさん
2008/06/24(火) 00:25:31オタクとか言うほどレベル高くないんですね
海外じゃ論文とかで有名なネタなのに
0945デフォルトの名無しさん
2008/06/24(火) 00:52:37論文見せて
0946デフォルトの名無しさん
2008/06/25(水) 12:28:420947デフォルトの名無しさん
2008/06/25(水) 23:18:180948デフォルトの名無しさん
2008/06/26(木) 01:02:590949デフォルトの名無しさん
2008/06/26(木) 08:48:350950デフォルトの名無しさん
2008/06/26(木) 08:51:500951デフォルトの名無しさん
2008/06/26(木) 09:00:410952デフォルトの名無しさん
2008/07/01(火) 21:31:45ゴミめ
0953デフォルトの名無しさん
2008/08/03(日) 09:51:460954デフォルトの名無しさん
2008/08/03(日) 13:19:420955デフォルトの名無しさん
2008/08/03(日) 16:39:00昔 LISP 触ってたから、今でも好きだよ。
0956デフォルトの名無しさん
2008/08/03(日) 21:23:510957デフォルトの名無しさん
2008/08/04(月) 08:13:090958デフォルトの名無しさん
2008/08/04(月) 08:20:33先ずシンプルな再帰版を作って、次に結果を保存する版を作りたくなる。
その辺りで、どうせ組み込み型の整数では実現できる数が少ないことに気付いてテーブル作って終了w
0959デフォルトの名無しさん
2008/08/04(月) 08:36:48と, 言われた場合はループも再帰も不可
0960デフォルトの名無しさん
2008/08/04(月) 08:59:07フィボナッチって、まずループで作っちゃうけどな。
0961デフォルトの名無しさん
2008/08/04(月) 09:11:160962デフォルトの名無しさん
2008/08/04(月) 09:22:54int addFromNtoM(int n, int m)
{
if (n < m) return addFromNtoM(n + 1, m) + n;
return m;
}
#elif 0 // 末尾再帰
int addFromNtoM(int n, int m, int s = 0)
{
if (n < m) return addFromNtoM(n + 1, m, s + n);
return s + m;
}
#elif 0 // ループ
int addFromNtoM(int n, int m)
{
int s = m;
for (; n < m; ++n) s += n;
return s;
}
#else // 要はこれになるからループも再帰も不可と言いたいのかな?
int addFromNtoM(int n, int m)
{
return (m + n) * (m - n + 1) / 2;
}
#endif
0963デフォルトの名無しさん
2008/08/04(月) 20:02:57そもそもフィボナッチを作ろうと思ったことがない。
再帰の例で使われてるのしか見たことない。
0964デフォルトの名無しさん
2008/08/04(月) 23:23:48つ 木構造
フィボナッチと置換すれ
0965デフォルトの名無しさん
2008/08/18(月) 00:54:150966デフォルトの名無しさん
2008/08/18(月) 01:27:24http://stdcxx.apache.org/doc/stdlibref/partial-sort.html
0967デフォルトの名無しさん
2008/08/18(月) 01:37:510968デフォルトの名無しさん
2008/08/18(月) 01:40:14一回あたりO(logK)というだけ?
0969デフォルトの名無しさん
2008/08/18(月) 01:43:49heap木を壊さないために必要。
0970デフォルトの名無しさん
2008/08/18(月) 01:44:00わざわざヒープを使ってるのには何か理由があるのかなぁ?
http://en.wikipedia.org/wiki/Selection_algorithm#Optimised_sorting_algorithms
0971デフォルトの名無しさん
2008/08/18(月) 01:46:18どういうこと?
0972デフォルトの名無しさん
2008/08/18(月) 01:47:38sort()はクイックソート、stable_sort()にはマージソート、
partial_sortにはヒープソートを使っていると「C++標準ライブラリ」には書いてある。
0973デフォルトの名無しさん
2008/08/18(月) 01:48:27ヒープソートについてぐぐってみ。
正確にはO(log2N)必要。O記法によりO(logN)になってるだけ。
0974デフォルトの名無しさん
2008/08/18(月) 01:51:38クイックソートは途中でソート処理を打ち切るのは困難であるが、
ヒープソートは容易であるのでpartial_sort()の用途に合っている。
0975デフォルトの名無しさん
2008/08/18(月) 01:53:030976デフォルトの名無しさん
2008/08/18(月) 01:55:11資料希望。>>970には真逆のことが書いてあるわけで。
0977デフォルトの名無しさん
2008/08/18(月) 01:59:420978デフォルトの名無しさん
2008/08/18(月) 02:03:470979デフォルトの名無しさん
2008/08/18(月) 02:05:080980デフォルトの名無しさん
2008/08/18(月) 02:14:42http://wordaligned.org/articles/top-ten-percent
この記事と同じように速度測ってみて、使い分けることにするわ。スレ違いっぽいのでこのへんで。
0981デフォルトの名無しさん
2008/08/20(水) 03:25:020982デフォルトの名無しさん
2008/08/20(水) 09:59:55http://haiku.mine.nu/gapbuffer.zip
これの、GapBuffer_GetRealPosition()関数の戻り値が何を意味しているのかわかりません。
0983デフォルトの名無しさん
2008/08/20(水) 11:01:120984デフォルトの名無しさん
2008/08/20(水) 11:47:53データとしての先頭からのバイト位置を計算。
return i - (this->end - this->start);
あたりの間違いだろうな。
0985デフォルトの名無しさん
2008/08/20(水) 22:42:01すみませんが、よくわかりません。
if(i < this->gap_start)
return i - (this->gap_end - this->gap_start)
else
って事ですか?
0986デフォルトの名無しさん
2008/08/20(水) 22:51:020987デフォルトの名無しさん
2008/08/21(木) 17:13:180988デフォルトの名無しさん
2008/08/22(金) 00:06:39レス数が950を超えています。1000を超えると書き込みができなくなります。