＜集大成＞アルゴリズム大辞典

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 152 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:23:32 ] もともと>>139のような比較自体に意味がないし、 (x and (not (x asr 31))) が格別優れているわけでもなかろが、 >>150 ええと、>>147はまったく意味の無い記述とされてるし、 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、 ようするにalgorithmなり記述を評価する能力無し、という告白でよろしいか? 153 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:30:27 ] まあ、少なくとも x := x and (not (x asr 31) ) は、アルゴリズムじゃなくて「技」だしなあ。 154 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:38:39 ] x := x and (not (x asr　sizeof(x) ) 155 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:48:12 ] という事で、C言語なら3項演算子を使え。　バカなコンパイラならインラインでCMOVを使えと 156 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:50:29 ] ABS　マクロなんかは、論理演算に変換されるね 覚えてないけど、符号拡張＋XORだったかな？ 157 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:41:28 ] >>152 ＞ 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、 さすがに、そんなコンパイラは使いもんにならないと思う。 31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する となると、マジヤバイ。 >>154 えーと、１年生ですか？w 158 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:54:11 ] >>157 >31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する !!!? バカ、マジヤバス。低脳乙www 終了。 159 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:54:21 ] x := x and (not (x asr BitSizeOf(x) ) 160 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:55:31 ] x := x and (not (x asr log2(INT_MAX) ) 161 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:56:51 ] x := x and (not (x asr ∞ ) ) 162 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 19:14:01 ] x =( abs(x) + x ) /2 163 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 23:28:42 ] >>158 えーと、幼稚園ですか？w 164 名前：デフォルトの名無しさん mailto:sage [2005/10/29(土) 00:12:48 ] >>157,163 おまえがなwww 165 名前：デフォルトの名無しさん [2005/11/03(木) 23:15:11 ] ( ´∇｀)y-~~~ へぇ 166 名前：デフォルトの名無しさん [2005/11/08(火) 00:13:18 ] B-Treeを自分で書いて理解したいのですが、難しくてよくわからん。 アホ向けに解説してあるサイトか書籍ないでしょうか。 167 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 00:33:13 ] >>166 ttp://unit.aist.go.jp/itri/knoppix/ 168 名前：デフォルトの名無しさん [2005/11/08(火) 01:55:08 ] >>167 クノッピでBtreeが理解できるの? 169 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 05:05:57 ] >>164あたりまで ともかくそんな高度な話題を論じれる貴方達を尊敬する。 俺にはついていけないよ。 170 名前：デフォルトの名無しさん mailto:sage [2005/11/09(水) 00:00:21 ] >>166 読み辛いのなら、デバッガを使って変数の値を追っていくといい 171 名前：デフォルトの名無しさん [2005/11/10(木) 01:14:30 ] すいません、「Universal hashing」について教えてくだせぇ。 lecture-wiki.ecc.u-tokyo.ac.jp/index.php?uonoue%2FJSR%2F11 このページにもその部分だけ書かれてなくて困ってます。 「平方採中法」とは違うものなんでしょうか？ 172 名前：171 [2005/11/10(木) 04:11:50 ] 自己解決しました 173 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 19:12:43 ] 平衡木のAVL木において，バランスが崩れた場合に，単一回転と二重回転 によってバランスを保つことを勉強しました． 単一回転と二重回転の選択の判断ってどうしてるんですか? 174 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 20:25:30 ] >>173 その勉強した内容は、隅から隅まで読んでみたのかな？ たとえば次のページみたいに、普通は書いてあるよ。 ttp://lecture.ecc.u-tokyo.ac.jp/~yamaguch/pub/cp2-8/what-is-search-avl.html 175 名前：& ◆i.twkzJbf. mailto:sage [2005/11/13(日) 21:41:13 ] >>174 大変，ありがとうございます! 図書館にあるアルゴリズムの本をあさり，「こういうパターン の時は単一回転」という図は掲載されていたのですが，明確に 文章で書かかれているものが，無かったんです． 上記のURL には明確に文章で記載されていたので，理解できました． ありがとうございました． 176 名前：デフォルトの名無しさん mailto:sage [2006/02/05(日) 09:40:09 ] 2 177 名前：デフォルトの名無しさん [2006/02/05(日) 09:41:09 ] 今春、情報処理試験受けてきます 178 名前：デフォルトの名無しさん mailto:sage [2006/02/15(水) 22:05:35 ] 誰かイージスシステムのアルゴリズムうｐしてよ。 できればCASL2形式のソースコードで頼む。 179 名前：デフォルトの名無しさん mailto:sage [2006/03/06(月) 23:50:20 ] GDIのArcToってどういうアルゴリズムで実装されているかご存知の方いませんか？ また、ArcToを実装する場合、Google等でそのアルゴリズムの名前を検索するとヒット するようなメジャーなアルゴリズムってあるのでしょうか？ 今、DirectXを使用してVRAMに直接弧を描画する関数を作っています。 楕円描画のアルゴリズムを使用して、弧を描く関数自体はできたのですが、問題点として、 �@　条件分岐が多くスパゲッチーなコードになる �A　○○のアルゴリズム、とかの名前で、世間一般に知られているかが分からず、 　　　スパゲッチーなコードでも、その内容を見た人が調べて把握できるかが不安。 今後の保守性に不安があるので、弧の描画に用いられている一般的な アルゴリズムがあるなら、そちらに揃えたいです。 ないなら、多少速度を犠牲にしてもGDIのArcToを使ってしまおうかと悩みちゅうです。 180 名前：デフォルトの名無しさん mailto:sage [2006/03/08(水) 11:31:54 ] DDA を使ってるなら、Bresenham　アルゴリズム とでも書いておけば判るだろう 181 名前：デフォルトの名無しさん [2006/04/05(水) 02:28:16 ] ヒープを使えば最小値（もしくは最大値）を迅速に取り出すことができます。 しかし、ある条件を満たしている間は最小値を、 そうでない場合は最大値を取り出すとなると、効率のいい方法が思いつきません。 線形探索で最大値を探し出すことになってしまいます。 （ソースコードは以下のURL） ttp://anotherred.hp.infoseek.co.jp/cgi-bin/src/up1346.txt なにかいい方法は無いものなのでしょうか。 182 名前：デフォルトの名無しさん [2006/04/05(水) 02:32:24 ] (181の続き） 某ソフトのある部分と流れがそっくりですが・・・ そっくりそのままコピペしたわけではないので、 そこらへんは目をつぶっていただけるとありがたいです。 183 名前：デフォルトの名無しさん mailto:sage [2006/04/05(水) 05:54:32 ] >>181 ようするに、最大値と最小値の両方を高速に取り出せるデータ構造か。 両方 O(1) で出来るものはしらんが、両方 O(log n) でできるものならB木の類。 184 名前：デフォルトの名無しさん mailto:sage [2006/04/05(水) 12:56:41 ] あとは、データを最初にソートしておくか。 185 名前：デフォルトの名無しさん [2006/04/05(水) 13:19:15 ] >>183 木構造ですか・・・ たしか、木構造を使用したデーターベース関連のソースがあるので、 速度のことさえ気にしなければいけそうですね。 ちょっとベンチマークを取ってることにします。 わざわざ答えてくださりありがとうございました。 >184 二分ソートを使うとなると、かえって遅くなりそう・・・ 適切な位置を探すのにO(log n) データの移動に最悪でO(n) 平均はいくらぐらいか知らないけど。 186 名前：デフォルトの名無しさん [2006/04/23(日) 23:18:33 ] 質問です。 0<= x < N までの値を巡回する式を作りたいのです。 用途としては、選択肢を指すカーソルが一番下まで行った時、さらに下ボタンを押すと一番上を指すように。 一番上まで行った時にさらに上ボタンを押すと、一番下を指すように。 という使い方です。 x = (x + N) % N; でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。 Nが2の乗数なら、マスクをとるという方法も思いつくのですが…。 何か定型的な方法はありますでしょうか？ x = ((x % N) + N) % N; でもとりあえず良いのですが、かなり冗長に見えます。 187 名前：デフォルトの名無しさん mailto:sage [2006/04/23(日) 23:39:39 ] >>186 > でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。 つか、xが-N未満になりうる時点でバグってると思うが？ 0<= x < N なんでしょ？ 188 名前：デフォルトの名無しさん mailto:sage [2006/04/23(日) 23:51:29 ] もう面倒だから素直に分岐つかえば x % n + (x < 0 ? n : 0) 189 名前：デフォルトの名無しさん [2006/04/24(月) 00:08:33 ] >>187 説明が下手ですいません。 xになにかしらの数が代入され、それをうまく 0<=x<N に丸め込みたいのです。 int hoge(int x) { while(x < 0) x += N; x %= N; return x; } とお考えください。 >>188 その式だと、ちょっとやりたいこととは違うようです。 whileやifを使わずに綺麗にやる式があれば…と思っているのですが 190 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 00:46:26 ] >>188 それ負のとき0が5になる 191 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 00:50:35 ] 188のもあってるが、 ＞x = ((x % N) + N) % N; のほうが分岐無いだけ速くねーか 192 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 06:33:35 ] xは負数としてもそんな極端な負数にはならないんでしょ？ NM=INT_MAX/N; として x = (x + NM) % N; でいいんじゃないの？ 193 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 16:25:32 ] いまいちやりたいことがわからんが、 UIなら計算量をケチる必要性はないので多少冗長でもかまわないのでは。 xの初期値として x = (x + N) % N; が計算できて、xは以降、0<=y<N、という値が足されたり引かれたりするだけという状況を仮定すると、 (>>186だとそういう状況ですよね。xに乗除算は入ってこない) x-yを行うときはx<yならばNを足してからyを引くでいいんでないかい。 除算よりも比較の方が圧倒的に速いから。 194 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 16:36:30 ] いや、それなら基本的に　 xが-N未満になど、普通はなりようがないのだ。 x <-Nになる事はないのだから 用途的には x = (x + N) % N; で何の問題もない。 過剰仕様といえよう。 もし、xがEPROMとかに保存されてる間にゴミと化しても変な事にならないようにという事なら x を　符号無数とすればいい 195 名前：デフォルトの名無しさん mailto:sage [2006/04/25(火) 00:18:10 ] 360度 0〜4095の値をとる円の時に、この問題に悩むな。 -500000とか入れられたときに、0〜4095に直すとどうなるか。みたいな。 DWORDにする手もあるんだが、Javaだと符号intしかないからなぁ・・ 196 名前：デフォルトの名無しさん mailto:sage [2006/04/25(火) 06:36:53 ] 0〜4095なら　4095とのand でいいんだから、悩まないぞ 197 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 22:52:10 ] テキストの類似度を判定するアルゴリズムって、なんかいいのないかな。 leveshteinとかsimilar_textだと、"abcdefgh"と"hgfedcba"の類似性を かなり低く見積もってくれたりするんだけど、人間の直感にマッチするような アルゴリズムってないもんですかね。 198 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 10:17:58 ] 人の直感がそれぞれだからねぇ 199 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 16:01:49 ] >>197 俺の直感だと、その2つは似てない 200 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 21:35:30 ] Oliver [1993] とか。 similar_text ttp://jp2.php.net/manual/ja/function.similar-text.php 201 名前：デフォルトの名無しさん mailto:sage [2006/05/23(火) 17:06:12 ] SoundEx　とかはどうなの？ 202 名前：デフォルトの名無しさん [2006/05/30(火) 16:49:01 ] 複数の候補からランダムに選択させたいんですが、 そこに重み付けを導入する場合って、どんなアルゴリズムがあります? 203 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 07:54:15 ] 誰か解答を求む！ C で文字列を比較するのは (*(int *)s1) == (*(int *)s2) これのほうが早い？ 204 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 07:57:42 ] >>203 ここで聞く前に試したほうが早いし確実だと思うのは気のせいでしょうか 205 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 09:25:22 ] 速いっつーか，間違ってねえか？ 206 名前：203 mailto:sage [2006/06/08(木) 09:29:08 ] すいません、ミスです 207 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 10:42:46 ] 切れ目探しで鬱になったけど早い事は早かった 間違ってるの？ 208 名前：207 mailto:sage [2006/06/08(木) 10:47:38 ] ミスｗ 209 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 13:58:46 ] なるほど、疾いよ、strcmpの1/10になれる これどのCPUでもいけるの？ 210 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 15:47:53 ] まだ続けるのか？ 211 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 15:26:03 ] 奥村先生は放送大学に出演している。 212 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 15:47:54 ] >>211 ナイス情報サンクス｡ LATEXとＪＡＶＡかー｡ アルゴリズムキボンヌだなぁ｡ 213 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 16:02:00 ] >>212 「JAVAによるアルゴリズム事典」はpLaTeXで書いたとちゃっかり宣伝していた。 214 名前：デフォルトの名無しさん mailto:sage [2006/06/25(日) 00:14:43 ] B+-treeに関して説明してあるお薦めサイトか、 理解しやすいオープンソースプログラムってあります？ 215 名前：デフォルトの名無しさん mailto:sage [2006/07/06(木) 08:08:55 ] B木までは説明してるサイトでもB+やB*は名前がでてくるかどうかって感じだな 216 名前：デフォルトの名無しさん mailto:sage [2006/07/06(木) 15:40:55 ] 奥村先生はJAVAが出て来たとき世界は統一されたと思ったらしい。 217 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 13:40:04 ] さすが学者先生だな。 何かで世界統一されることなんてないよ。 218 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 17:01:29 ] >>216 ソースは？ 解釈が間違っている可能性がある。 219 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 20:40:34 ] >>218 放送大学で言っていた。 220 名前：デフォルトの名無しさん [2006/08/12(土) 09:04:26 ] 遺伝的アルゴリズムは？ 221 名前：デフォルトの名無しさん mailto:sage [2006/09/02(土) 16:52:02 ] 　　 （　・∀・）　　　|　|　ｶﾞｯ 　　と　　　　）　 　 |　| 　　　 Ｙ　/ノ　　　 人 　　　　 /　）　 　 < 　>__Λ∩ 　　 ＿/し'　／／. Ｖ｀Д´）/ 　　（＿フ彡　　　　　 　　/ 222 名前：デフォルトの名無しさん mailto:sage [2006/09/14(木) 01:08:00 ] GA ってこと? 223 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 22:57:32 ] 格子点を、原点からの距離が小さい順に数え上げていくアルゴリズムをしりませんか？ 簡単の為、問題を２次元にします。 この時、 (0,0) (1,0) (0,1) (1,1) (2,0) (2,1) (1,2) (2,2) ・・・・・・・ という配列を得たいのです。 思いついた単純な方法は、 for(i =1; i < N ; i++) for(j = 1 ; j < N; j++){ d = i**2 + j**2 arry.push([i,j],d) } sort arry by d aryy.each { a printt a } という方法ですが、あまりスマートとはいえないし、 同じ距離d (= 1)をもつ点(1,0),(0,1)がこの順で並ぶとは限らないという欠点があります。 （同じ距離を持つ(x,y)なら　x>=yというを満足する点からで並んで欲しい) 224 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:03:57 ] >>223 「安定なソート」でぐぐれ。若しくはC++のstd:stable_:sortで関数オブジェクトに x>=yという条件を含めれば簡単。 225 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:04:27 ] ×std:stable_:sort ○std::stable_sort 226 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:33:51 ] おもしろいな 群論とか使えばいけそうだが。。。 俺の知識では無理ｗ 227 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:42:44 ] #include <iostream> #include <vector> #include <algorithm> #include <utility> struct MyComp { bool operator()(const std::pair<double, double>& p1, const std::pair<double, double>& p2) { double d1 = p1.first * p1.first + p1.second * p1.second; double d2 = p2.first * p2.first + p2.second * p2.second; if (d1 < d2) return true; else if (d1 > d2) return false; else { // d1 == d2 if (p1.first < p1.second && p2.first > p2.second) return false; else return true; } } }; struct MyOut { void operator()(const std::pair<double, double>& p) { std::cout << '(' << p.first << ',' << p.second << ')' << std::endl; } }; 228 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:43:16 ] int main() { double a[][2] = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {1, 2}, {2, 2}}; std::vector<std::pair<double, double> > dp; for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) dp.push_back(std::make_pair(a[i][0], a[i][1])); std::sort(dp.begin(), dp.end(), MyComp()); std::for_each(dp.begin(), dp.end(), MyOut()); } (1, 0), (0,5, 0) なんてペアがある場合は考慮してない。 229 名前：デフォルトの名無しさん mailto:sage [2006/09/18(月) 00:43:40 ] ヴォースゲー！ 230 名前：デフォルトの名無しさん [2006/09/20(水) 15:41:34 ] 複数の矩形が存在するときに、それぞれの重複を求めるアルゴリズムを考えています。 最終的には、与えられた領域を重複の無い横に細長い形の矩形で表現したいと思っているのですが、 これを表現するための良いアルゴリズムはあるでしょうか？ 231 名前：デフォルトの名無しさん mailto:sage [2006/09/20(水) 22:14:34 ] >>230 スキャンラインコンバージョン？ 232 名前：デフォルトの名無しさん mailto:sage [2006/09/20(水) 23:44:29 ] >>230 おれは力技でやった 233 名前：デフォルトの名無しさん [2006/09/24(日) 15:55:30 ] This is a pen! 234 名前：デフォルトの名無しさん mailto:sage [2006/09/24(日) 17:39:47 ] >>230 平面走査で解ける．計算量は O( n log n + k )， ただし n は矩形の数，k は分割線の個数． 簡単のため，どの矩形の上下の y 座標にも，同じものはないとする． アルゴリズムを述べた後にこの制限は外す． 1. すべての矩形の上側の辺と下側の辺を，    y 座標の昇順に並べられたキュー Q に突っ込む． 2. while Q が空でない: 3.   e = Q.pop() 4.   if e が下辺         then T に対応する矩形を挿入         else T から対応する矩形を削除 5.   T に入っている矩形で，e と交わるものを切断する． ここで T は平面走査構造．x でソートされた平衡二分探索木を用いると 4 が O(log n) で行える．5 は e の左側の点で二分探索し，交わる領域を 線型に探すと O(log n + k') で行える．ただし k' は e と交わる矩形の数． 同じ y 座標を許す場合は，一括に処理できる辺を蓄えておいて， 一度しか切断しないようにすれば対応できる． 235 名前：デフォルトの名無しさん [2006/09/30(土) 15:33:44 ] 斜め楕円の描画 void DrawEllipse(HDC hdc, double dFx1, double dFy1, double dFx2, double dFy2, double dLen ) { double a,b,c,d,A,B,C,L,M,x; int sx,sy;a = dFx1; c = dFx2;L = dLen; A = L*L-(a-c)*(a-c); BOOL bFlg = TRUE; for(int y=0; y<300; y++){ b = y-dFy1;d = y-dFy2; M = L*L-a*a-b*b-c*c-d*d; B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c); C = (a*a+b*b)*(c*c+d*d)-M*M/4; if(B*B-4*A*C>0){ x = (-B+sqrt(B*B-4*A*C))/(2*A); if( bFlg ){ bFlg = FALSE; sx = x;sy = y; MoveToEx(hdc,x,y,NULL); } LineTo(hdc,x,y); } } 236 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 15:34:17 ] 続き for(int y=300; y>0; y--){ b = y-dFy1;d = y-dFy2; M = L*L-a*a-b*b-c*c-d*d; B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c); C = (a*a+b*b)*(c*c+d*d)-M*M/4; if(B*B-4*A*C>0){ x = (-B-sqrt(B*B-4*A*C))/(2*A); LineTo(hdc,x,y); } } if( !bFlg ){ LineTo(hdc,sx,sy); } } あげちまたスマソ 237 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 15:35:42 ] 標準に存在しないからって力技で自作したんだがどうだろう ベジエ勉強したほうが良いのかな 238 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 19:41:45 ] せめて入力変数の意味くらい書いてくれ 239 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:01:13 ] >>237 ベジエ曲線で完全な楕円は表現できない 近似はできるけどな 240 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:20:49 ] >>238 HDCはおいておいて、残りの5つは 焦点の座標（２つ）と長径 >>239 実用に耐えるなら近似で良いんだけどね 241 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:59:26 ] 用途にもよるが、俺ならサンプル点の密度が極端に偏るアルゴリズムは使わないな。 242 名前：デフォルトの名無しさん [2006/10/22(日) 19:47:46 ] 最大遅れ最小スケジューリング (minimization of the maximum lateness) ってあるけど、 この最大遅れの「最大」ってなんなの? 遅れの合計を最大化したものを最小化? 意味がわからん。 エロい人教えて 243 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 19:51:50 ] 最大の遅れを最小にする．たとえば ・最初の仕事で30分遅れてあとの仕事はジャスト．（最大遅れ30分） ・全部10分づつ遅れる．（最大遅れ10分） の二つだったら，後者のほうが良いとするスケジューリング． 244 名前：242 mailto:sage [2006/10/22(日) 19:55:00 ] >>243 なるほど!トンクス 245 名前：デフォルトの名無しさん [2006/10/31(火) 16:55:59 ] $a=array('red','blue','yellow','green'); $b=array('white','blue','yellow','green'); $c=array('green','red','yellow','cian','black'); $a,$b,$cのどれにも存在する要素の'yellow','green'を取得するソースをPHPで。 246 名前：デフォルトの名無しさん [2006/11/02(木) 01:42:06 ] PHPで何？ 247 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 11:51:23 ] >>245 array_uintersect 248 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 19:21:30 ] 二つのソート済みの配列が与えられていて（合計の要素数はN） N個の要素からメディアンを計算量O(LogN)で求めるアルゴリズムを教えてください。 ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf www.cse.ust.hk/faculty/scheng/comp271h/assign/hw2_sol.pdf 検索して出てきたこの二つのPDFにある擬似コードをCで実装してみたんですけど 何度かテストしたらどちらも時々スタックオーバーフローが発生してしまいました。 （正しい結果を返すときもありました） 二つの配列の長さが同じ場合にしか使えないコードでもいいのでお願いします。 249 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 20:57:41 ] >>248 2つのソート済み配列をA,Bとする。 Aの中央値とBの中央値を比較する。 Aの方が大きいとすると、Aの小さいほうの集合とBの大きいほうの集合を残す。 以下これを反復する。1回の反復は配列の要素を指定して比較するだけだから定数オーダー。 反復ごとに要素数が半分になるから反復回数はlog N回 250 名前：248 mailto:sage [2006/11/03(金) 03:05:44 ] >>249 ありがとうございます。こんな感じになりました。 int median_search(const int *A,const int *B, int n){ 　　int m; 　　if(n==1) 　　　　return A[0]>B[0]?A[0]:B[0]; 　　m = n>>1; 　　if(A[m]>B[m]) 　　　　return median_search(A,B+m,m); 　　return median_search(A+m,B,m); } nは配列AとBの長さです。 ソート済みの配列AとBをマージした長さ2nの配列をCとするとこの関数はC[n]を返します。 A[0]>B[0]?A[0]:B[0];の部分を、A[1]<B[1]?A[1]:B[1];にすればC[n+1]を返します。 251 名前：248 mailto:sage [2006/11/03(金) 03:14:48 ] 連続投稿すみません・・。 >>250は配列の長さnが２のべき乗の場合しか使えないようですね・・。 もうちょっと考えてみます・・。 252 名前：デフォルトの名無しさん [2006/11/04(土) 02:07:10 ] バルブソート の検索結果 約 98,900 件中 1 - 10 件目 (0.75 秒)

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef