データ構造とアルゴリズム総合

1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ] データ構造とアルゴリズムに関する総合スレ。 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ 486 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:30:03.12 ] よく意味が分からない 487 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:32:58.97 ] xを0x00000000〜0xFFFFFFFFまでのAのリストを作ればいいんじゃね 488 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:43:33.99 ] 具体例で考えればいい A=1のときのxを求める A=2のときのxを求める 489 名前：デフォルトの名無しさん [2012/10/04(木) 21:44:05.80 ] >>486 分かりづらかったかも、すみません。 ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、 ｘの値を求めるには？ ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど） 490 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 21:45:22.64 ] 難しそうなアルゴリズムだ 491 名前：デフォルトの名無しさん [2012/10/04(木) 21:59:08.08 ] 連投すみませんです。自分の説明に絶望した・・。 unsigned int A； unsigned int x； // ？ A = x + reverse_bits(x); if (A == 0x3476edc0) { // この条件を満たすｘを求めるには・・？任意のAについてどうやって計算すればいいか・・・ } // 1101:0010 -> 0100:1011 ビット順序反転する関数 unsigned int reverse_bits(unsigned int v){ 　v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 　v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 　v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 　v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 　v = ( v >> 16 ) | ( v << 16); 　return v; } 492 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:14:13.06 ] >>485 無理だな。 A と X は 2^32 通り、X + Rev(X) も 2^32 通り。 ただし、X + Rev(X) はオーバーフローする分、実際の数は少ない。 よって、任意の A に対して X を求めることは無理。 493 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:15:25.15 ] 訂正。 ○ X + Rev(X) は 2^32 通り以下。 494 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:15:49.33 ] Javaならオーバーフローしない！ 495 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:16:38.89 ] 下位ビットが立ってたら上位ビットも立つ形になるんだし和で非対称になったとしても最下位ビットが 496 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:17:39.08 ] 更に訂正。 ○ X + Rev(X) は 2^31 通り以下。 X + Rev(X) = Rev(X) + Rev(Rev(X)) だから。 497 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:22:18.63 ] >>492 オーバーフロー分は切り捨てて良いのですが・・・無理でしょうか？ A = (unsigned int) ( x + reverse_bits(x) ); １元１次方程式に見えるので解があるような、 いやでも無いような・・・悶々としてます。 498 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:22:59.96 ] A = 0xFFFF FFFF みたいな形が一番、式を満たす X の数多いようだな。 499 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:23:25.14 ] 496の対称性があるから無理じゃね 500 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:24:25.45 ] さっさと487のいうように一覧にして全数字を網羅できるかチェックすれば早いのよ！（それじゃアルゴリズムじゃありませんが＞＜） 501 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:27:35.73 ] >>497 492,496を読んで、それでも一般には無理だと理解できない脳が怖い。 502 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:31:08.08 ] 496の言う対称性が分かればできる数字がほぼ半分しかないってことがわかる 503 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:33:39.78 ] A=X+Rev(X)なら Rev(X)=Yとすると A=Y+Rev(Y)=X+Rev(X)が成り立つ つまり同じ解を出すXが２通りあるってこと 504 名前：デフォルトの名無しさん mailto:sage [2012/10/04(木) 22:38:19.54 ] >>503 うーん　そうですね。 ｘとAが１対多の関係がある時点でダメなのか・・・ 皆さんありがとうです 505 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 00:07:59.21 ] >>503 それは間違い 506 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 00:58:37.93 ] 簡単のため、2ビットの場合で考えてみる。 A = 00のときX = 00 A = 01のとき解なし A = 10のときX = 11 A = 11のときX = 01,10 解があれば解を返し、なければ解なしと出力するアルゴリズムって総当たり探索になるのかな？ それとも代数的に解けるのだろうか？ 507 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:01:28.13 ] オーバーフロー切り捨てを考慮するとなるとかなり複雑になりそう 508 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:08:57.90 ] A=000 X=000 A=001 X=011,110 A=010 X=101 A=011 X= A=100 X=010 A=101 X=001,100 A=110 X=111 A=111 X= 509 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:11:02.77 ] で、これ求めて何に使うわけ？ 510 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:14:16.72 ] 0ビット目だけは下位ビットからの繰り上がりで1に出来ないことから Aの0ビット目をみて 511 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:15:22.75 ] >>509 FFT関係だと思います 512 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:17:16.96 ] >>510 11は解があるよ 513 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:21:21.45 ] A=0000 X=0000 A=0001 X= A=0010 X=1001 A=0011 X= A=0100 X= A=0101 X=0111,1110 A=0110 X=0010,0100 A=0111 X= A=1000 X=1011,1101 A=1001 X=0001,1000 A=1010 X= A=1011 X= A=1100 X=0110 A=1101 X= A=1110 X=1111 A=1111 X=0011,1100,0101,1010 514 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:22:28.99 ] フーリエ変換か 515 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:27:14.69 ] nビット整数だとnが奇数でも偶数でも全ビットが1のものを除けば対称になってる 516 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:28:20.19 ] その対称の端のXはオールビットが0か1 517 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 01:31:36.52 ] >>513 これシンプルな計算で解の有無が判定できるのかね・・・不規則に見えるが 518 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:45:27.52 ] ^ をべき乗の記号として 2^((n+1)/2) 通りチェックする方法なら分かる 519 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:49:10.90 ] A=1111 X=0011,1100,0101,1010,0110,1001,0111,1000,0001,1110,1101,0010,1011,0100,1111,0000 520 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 03:54:10.07 ] >>519 反転じゃなくて逆順だよ？ 521 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:00:24.13 ] 489 デフォルトの名無しさん [] 2012/10/04(木) 21:44:05.80 ID: Be:     >>486     分かりづらかったかも、すみません。     ｘ + ビット反転(ｘ)の結果が0x3476edc0のとき、     ｘの値を求めるには？     ビット反転は 10110010 → 01001101　のような感じの処理（この例は8ビットですけど） 522 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:16:49.17 ] 質問者は反転と逆転の違いが 523 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 04:19:19.69 ] 例出すのも下手 わざとやってるだろ 524 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 12:41:22.64 ] 解いてみた 諸事情により 31 bit まで #module #defcfunc bitreverse int num, int bit, local rev repeat bit rev=(rev<<1)|((num>>cnt)&1) loop return rev #deffunc solve array result, int num, int bit, local result_num, local u_, local l, local m, local n dim result n=1<<((bit+1)/2) m=(1<<bit)-1 repeat n l=cnt u_=(num-l)&(n-1) x=l|bitreverse(u_, bit) if ((x+bitreverse(x, bit))&m)=num { result.result_num=x result_num++ } loop return result_num #global solve result, $ff, 8 repeat stat mes strf("%x", result.cnt) loop 525 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:18:10.35 ] HSP? 526 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:36:02.53 ] アルゴリズム記述用の抽象言語みたいなのってないのかな 527 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:48:32.32 ] 32bit全探索する気か 528 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 15:50:40.72 ] 8bitくらいまで>>513のように羅列していって何らかの傾向や法則性が無いか確かめられたらいいんだけどな 529 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 16:50:50.02 ] しょうがねぇなぁ〜 codepad.org/Kkm8uPyR 530 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 18:11:37.70 ] >>526 片言Algol知らんのか? 531 名前：デフォルトの名無しさん [2012/10/05(金) 20:26:48.63 ] "片言Algol"でググっても何なのか出てこないんですけどー"片言Algol"って何ですかー？ 532 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 20:54:44.01 ] 片言のAlgol 533 名前：デフォルトの名無しさん mailto:sage [2012/10/05(金) 21:15:37.12 ] pidgin ALGOLも知らんとは！(怒 534 名前：デフォルトの名無しさん [2012/10/08(月) 00:42:46.73 ] pidgin ・・・　混成語 他の言語と混ぜて使うってこと？よけい混乱しないか？ 535 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 07:19:41.75 ] >>534 ある言語の、外人 植民地人向けカタコトOKバージョン。 満州国を作ったあたりでpidgin日本語を作ってた。 語尾を「〜アル」で統一とか。 廃れてしまったがモノはちゃんと完成し、教育もされたようだ。 マンガの中国人が「〜アルよ」と言うのはその名残らしい。 536 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 08:39:37.95 ] ゼンジー北京ってまだ生きてんの？ 537 名前：デフォルトの名無しさん mailto:sage [2012/10/08(月) 19:17:57.21 ] codepad.org/dZ6OuG1e ghc f "101010" --2進 fx "12abcd"--16進 虫食い算を解く要領で１桁ずつ特定しています 538 名前：537 mailto:sage [2012/10/09(火) 00:34:47.45 ] codepad.org/ETbL5UUF 32bitでエラーに成るのを修正 A=B+(reverse B) rx B --> A fx A --> B rx "123456" -->"7c609e" fx "7c609e" -->["7a3440","7a2c40","723450","722c50","6a3448","6a2c48","623458","622c58","5a3444 ","5a2c44","523454","522c54","4a344c","4a2c4c","42345c","422c5c","3a3442","3a2c4 2","323452","322c52","2a344a","2a2c4a","22345a","222c5a","1a3446","1a2c46","1234 56","122c56","0a344e","0a2c4e","02345e","022c5e"] 539 名前：デフォルトの名無しさん [2012/10/14(日) 18:17:20.75 ] データ構造とアルゴリズムと設計パターンは、 ソフトウェア開発に必須の技術 540 名前：デフォルトの名無しさん [2012/10/14(日) 19:30:55.13 ] B木のようなプログラム文も、書けるようにならなければなりませんか？ 541 名前：デフォルトの名無しさん mailto:sage [2012/10/14(日) 20:07:16.63 ] プログラム文という言葉は初めて見たかも 542 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 00:01:49.62 ] ヒント翻訳ソフト 543 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 01:18:47.48 ] >>542 翻訳ソフト使うと何が解決するの？ 544 名前：デフォルトの名無しさん mailto:sage [2012/10/15(月) 17:34:20.97 ] というかダイクストラ法とクラスカル法の違いって何？ 両方とも最小スパニング木を求める方法なのにお互い関係ないものなの？ ダイクストラで検索かけようとしても候補にクラスカルって出てこないし 逆もない。 クラスカルはプリムとセットで議論になるケースが多いけど。 誰か教えて。 545 名前：デフォルトの名無しさん mailto:sage [2012/10/18(木) 08:39:59.95 ] 定義が違うし出力も違う。 そして、「同じものを求める二つのアルゴリズムなら関係があるはず」と言うのは思い込み。 546 名前：デフォルトの名無しさん [2012/10/23(火) 21:57:07.56 ] クラスカル、プリム・・・重み付きで、その重みが最小となる全域木を求めるAG ダイクストラ・・・その経路までの最短キョリを求めるAG クラスカルは全てのノードを繋ぐ ダイクストラは最短ノードを選択 547 名前：デフォルトの名無しさん mailto:sage [2012/10/23(火) 22:46:30.76 ] 線形探索も立派なアルゴリズム。 548 名前：デフォルトの名無しさん [2012/10/29(月) 21:42:14.08 ] AGってなんなん？ 549 名前：デフォルトの名無しさん mailto:sage [2012/10/29(月) 21:46:33.53 ] GAなら知ってる 550 名前：デフォルトの名無しさん mailto:sage [2012/10/29(月) 23:57:14.35 ] GKなら乙 551 名前：デフォルトの名無しさん [2012/11/22(木) 18:39:52.58 ] 線分で出来てるポリゴンで、 線分がクロスしているときにも正しい面積を出す方法はありますか？ イメージ的には、魚と魚のシッポがある場合に、魚の面積を得る方法。 552 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 19:37:05.37 ] 単純に2分の1になるんじゃないの？ 553 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 20:07:37.68 ] ポリゴンの共通部分体積を計算しなきゃな。 554 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 21:22:43.29 ] クロスポイントで分割するしかないんじゃないの 555 名前：デフォルトの名無しさん mailto:sage [2012/11/22(木) 23:20:34.69 ] 地震キター 556 名前：551 [2012/11/26(月) 14:06:33.84 ] あらかじめクロスポイントが分かってないとできない、 座標を適当に入れるだけだと魚かシッポか判断できない、 ってことですね？ 557 名前：デフォルトの名無しさん mailto:sage [2012/11/26(月) 14:23:38.70 ] 塗りつぶすんならそれ用のアルゴリズムもあるけどね 558 名前：551 mailto:sage [2012/11/26(月) 14:52:07.91 ] 塗りつぶさずに処理したいです。 559 名前：デフォルトの名無しさん mailto:sage [2012/11/26(月) 21:09:10.39 ] 半直線伸ばして線分と交差する回数の偶奇で判定できるかもしれない 560 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 11:40:37.00 ] 交点の座標を求めるのを厭わないなら、 交点も頂点の一つ（線分2本分なので二つ）に含めてしまえば、 普通に多角形の面積として求められるんじゃない？ 561 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 12:09:09.66 ] 交点がちょうど頂点上だったり、線分が重複していたり、 まあ頑張ってくれ 562 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:04:01.15 ] そこら辺の場合分けは地獄だな。 563 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:15:10.54 ] 面積求めるのにそんな例外事項は考慮する必要ない。 原点と、線分の両端点とで張る三角形の面積を、足したり引いたりするだけでしょ。 頂点どうしや頂点と交点が非常に接近してても問題ないし、 線分の全部や一部が重複してても問題ない。 564 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 15:23:49.89 ] あぁ、すまん、これは「交点が求まったら」という前提な。 交点を求めることそのものは、工夫がいるね。 565 名前：デフォルトの名無しさん mailto:sage [2012/11/27(火) 16:54:57.32 ] 二回ループ 566 名前：デフォルトの名無しさん [2012/12/05(水) 12:33:15.73 ] 今あるn個の数値データの中から例えば１〜８個の数字を選んでｘ〜yの値にある組み合わせを作る というアルゴリズムを考えているのですが、こういうアルゴリズムは何法とかで検索すればいいんでしょうか? 取りあえず総合で聞いてみたのですが、スレ違いなら誘導していただければ幸いです。 567 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 12:33:45.43 ] あう・・・ age失礼しました。 568 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 12:42:43.84 ] combination (あるいは permutation) 569 名前：デフォルトの名無しさん mailto:sage [2012/12/05(水) 13:24:52.20 ] >>568 ありがとうございます。 キーワードで調べてみます。 570 名前：デフォルトの名無しさん [2012/12/21(金) 10:45:15.05 ] ここで質問するべき事かわからないのですが、 適当な板もスレも見つからなかったのでお願いします。 Adobe illustratorでjavascriptを使って文字列の検索置換を行った時に 変更部分を目視で確認したいので置換した文字部分のみ色を変えたいのです。 正規表現を使って文字列置換するのは簡単なんですが、色を変えようとするとうまい方法が思いつきません。 100以上のパターンを検索置換しないといけません。 どんな考え方で作成したら良いのでしょうか？ 571 名前：デフォルトの名無しさん mailto:sage [2012/12/21(金) 10:53:39.57 ] toro.2ch.net/test/read.cgi/tech/1355011916/ 572 名前：デフォルトの名無しさん [2012/12/21(金) 10:59:58.44 ] >>570は誘導されたので移動します。 573 名前：デフォルトの名無しさん [2012/12/21(金) 13:05:37.93 ] 領海 574 名前：デフォルトの名無しさん [2012/12/24(月) 11:36:38.88 ] バカは死ね 575 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:10:58.26 ] ある整数の番号の範囲(例えば100〜999)があります。 要求によって番号を割り当てると、その番号は使用できなくなり 返却された番号はまた使えるようになります。 割り当て、返却を繰り返すと番号が断片化しますが その場合でも安定した速度で未使用番号を検索できるアルゴリズムはないでしょうか? 576 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:15:15.80 ] 未使用番号の連結リスト FATがやってるやつ 577 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:17:11.78 ] 膨大な数になったらどうするんです？ 578 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:40:50.83 ] 膨大さと使えるメモリと許される時間による 579 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:44:32.37 ] メモリやディスクブロックの割り当てに使われているような手法が応用できそう。 エクステントをツリーで管理するとか。 580 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 22:44:41.80 ] 例にしろ、100〜999って言っておいて、後から膨大とか後出しすぎ 581 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 23:15:24.37 ] そこでblock符号ですよ！ 圧縮にも使える便利なデータ構造でもある 582 名前：デフォルトの名無しさん mailto:sage [2012/12/27(木) 23:44:43.26 ] 連続領域が必要ってわけでもなさそうだし、連結リストの何が不満なの？ 583 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 00:07:37.60 ] >>576でFA 584 名前： ◆QZaw55cn4c mailto:sage [2012/12/28(金) 01:09:30.09 ] >>576 FAT は未使用クラスタを連結リストにしていません。未使用マーク(0hとか）にするだけです。 585 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 08:49:08.74 ] 普通にリングバッファでキュー作ればいいだろ 何を難しく考えてるんだ 586 名前：デフォルトの名無しさん mailto:sage [2012/12/28(金) 09:00:25.38 ] >>576 FATって同じところに何度もアクセスしてディスク壊しやすいアルゴリズムだっけ？

---

---

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

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