- 1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ]
- 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉
>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。
前スレ↓
pc8.2ch.net/test/read.cgi/tech/1090227743/
- 702 名前：デフォルトの名無しさん mailto:sage [2008/10/14(火) 19:06:55 ]
- management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？
- 703 名前： mailto:sage [2008/10/15(水) 18:43:09 ]
- >>701
エラーがでます。
>>702
シュンサクとかいうデーターベースで使われてると読んだのです。
- 704 名前：アラフＯＯ.ｏ（笑） [2008/10/15(水) 23:21:58 ]
- >>703
オモローな記事があるぞ。兄弟。
いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
ttp://www.atmarkit.co.jp/fcoding/articles/algorithm/01/algorithm01a.html
- 705 名前：デフォルトの名無しさん mailto:sage [2008/10/16(木) 20:09:11 ]
- >>703
pr.fujitsu.com/jp/news/2006/12/15.html
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。
アルゴリズムじゃなくてシステムじゃないか。
人物から見ても >>701 であってるんだな。
あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。
- 706 名前： mailto:sage [2008/10/17(金) 03:43:42 ]
- >>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。
- 707 名前：デフォルトの名無しさん [2008/10/18(土) 18:41:25 ]
- 範囲のリストに新しい１つの範囲を追加するアルゴリズムをお願いします。
例えば、[1,2][5,7][8,15]という範囲のリストがあります。
上記のリストに[3,5]という範囲を追加すると
[1,2][3,5][5,7][8,15]に。
上記のリストに[1,6]という範囲を追加すると
新しく追加する範囲が常に優先されて、
[1,6][6,7][8,15]に。
上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
[1,2][5,7][8,10][10,13][13,15]。
リストは常にソートされているものとして、各範囲は重なって
はいけません。上記で範囲[Start,End]でEndは含まれません。
範囲のリストに1万件とか２万件を高速に連続追加できれば幸いです。
よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。
- 708 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 18:46:16 ]
- あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。
- 709 名前：デフォルトの名無しさん [2008/10/18(土) 18:53:28 ]
- 多めに確保して置いて、存在するところのビットを立てておけ。
- 710 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:08 ]
- データ構造はリストでお願いします。聞きたいのはアルゴリズムです。
実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定？
んー。
- 711 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:40 ]
- ふと思いついたもの。
範囲を示すインデックスにどの範囲に属するかという情報を持たせる。
上の例で実際にやってみる。
[1,2][5,7][8,15]に[3,5]を追加する。
範囲を示すインデックスがどの範囲に属するかという変数 = ID (0,1,0,0,0,2,2,0,3,3,3,3,3,3,3)
[3,5]を追加。(0,1,0,4,4,2,2,0,3,3,3,3,3,3,3)
[1,6]を追加。(0,4,4,4,4,4,2,0,3,3,3,3,3,3,3)
[10,13]を追加。(0,1,0,0,0,2,2,0,3,3,4,4,4,3,3)
以上。追加は高速だと思う。
範囲のリストへのアクセスはIDからリストを作るので、そこは作る処理の時間だけ遅くなる。
- 712 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:19:05 ]
- そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？
- 713 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:24:57 ]
- あー。すみません。データ構造とアルゴリズムは関係があるので、データ構造はリスト
でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。
- 714 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:39:07 ]
- >>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。
- 715 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:13:16 ]
- 範囲の列を、pより小さい部分とp以上の部分に分ける操作を考えて「値pによる分割」と呼ぶことにする
例えば[1,2][5,7][8,15]を3で分割すると[1,2]と[5,7][8,15]に、
10で分割すると[1,2][5,7][8,10]と[10,15]になる(このように列の分割が範囲そのものの分割を伴うことがある)
範囲の列Sに[start, end]を挿入するには、Sをstartで分割してS1とS2を得、S2をendで分割してS3とS4を得、
S1とS4の間に[start, end]を挟んだものを結果とすればいい
Sをpで分割するには、まずS中の範囲でendがpを越えるもののうち一番左にあるものを探す
そういうものがなければ、SはSと空列に分割される
あれば、それのbeginをpと比較して、それを分割するか全部右側に入れるか決める
多分この手順でいけるけど、これが高速に実行できるようなデータ構造は何があるだろう
2-3 Finger Treesとかならindexとappendとsplitが全部O(log n)だから、O((log n)^2)で挿入できるかな
- 716 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:47:34 ]
- >>702 >>713
データ構造を弄ってよいなら，
できるべき操作をちゃんと指定してほしい．
たとえば
(1) 範囲の追加
(2) 範囲 [x,y] に含まれる全ての範囲を小さい順に出力
(3) 小さいほうから数えて k 番目の範囲の出力
(4) ある点を含む区間の有無の判定
(5) ...
みたいな感じで列挙してください．
あと，>>710 に関して質問なのだけど，
いまある区間が分割された場合（>>707 の [10,13] の例），
オブジェクトとしてはどうなっているの？
(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
(b) [8,10] と [13,15] は同じオブジェクトに対応する
どっち？
- 717 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:22:08 ]
- >>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
unsigned int StartIndex;
unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。
- 718 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:25:14 ]
- >挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？
- 719 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:17:17 ]
- >>713,714
反応してくれてどうもです。
最近はあまりやらないんですけど、前はパズルを解くプログラムを作ったりしていました。
ポイントは簡単な問題を数多くこなす事だと思っています。
すると、どういう処理が効率がいいのか分かってきます。
こういう場合の為におすすめです。あまり無いと思いますが。。。
- 720 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:52:35 ]
- ＞上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
＞[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの？ そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。
- 721 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:59:37 ]
- >>720
想像力不足
- 722 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:38:10 ]
- 俺は動画のフレーム編集を想像しながらスレを見てた
- 723 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:42:24 ]
- だとしたら>>716のa,bはa？
あと>>721はどんなもの想像してたんかな？
- 724 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:05:09 ]
- >>707です。
>>716
>(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
オブジェクトを複製して別物で管理します(範囲以外のプロパティをコピーして)
>できるべき操作をちゃんと指定してほしい．
外部に公開する機能は
・範囲の追加(1個ずつ)
・リストの先頭から末尾への連続アクセス
・リストの全削除
以上です。
>>717
なるほど、上で書いた外部に公開する機能みてもB-Treeでいいのかもしれませんね。
ちょっと実装してみます。
>>715
わ。ありがとうございます。すごいわかりやすいです。
もうちょっと色々もだえてみます。
- 725 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:12:56 ]
- ・リストの先頭から末尾への連続アクセス
だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。
- 726 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 12:23:29 ]
- >720
ttp://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。
- 727 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:08:31 ]
- 8≦Nを満たす正の整数Nを3と5の和の組み合わせで表すにはどうすればいい？
3が何個、5が何個って分かればいいんだけど
あと表せない数はあるんだろうか
最初の5つはこんな感じ
8=5+3
9=3+3+3
10=5+5
11=5+3+3
12=3+3+3+3
13=5+5+3
- 728 名前：デフォルトの名無しさん [2008/10/22(水) 23:37:07 ]
- N = 3m+5nでしょ。 互いに素ならいけるんではなかったか? m,nが整数なら
- 729 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:37:40 ]
- 単に3と5の個数をデータとして持てばいいんじゃないの?
8,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。
- 730 名前：デフォルトの名無しさん [2008/10/22(水) 23:39:21 ]
- ax+by=1を満たす整数x,yが存在する
d.hatena.ne.jp/gould2007/20071009
- 731 名前：デフォルトの名無しさん [2008/10/22(水) 23:41:50 ]
- そしたら連続する3つ作れればそれ以降、全てつくれるってことだな
- 732 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:01:14 ]
- その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました
- 733 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:50:53 ]
- どうもおかしいと思った。
＞最初の5つはこんな感じ
6つあったのねw
- 734 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:09:36 ]
- A Small and Fast IP Forwarding Table Using Hashing.
これ何度みても計算できねぇ助けて
- 735 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:53:54 ]
- 一緒に考えてやるからその論文を見る方法を教えろ
- 736 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 02:07:20 ]
- ttp://cial.csie.ncku.edu.tw/ppt/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.ppt
ttp://cial.csie.ncku.edu.tw/pdf/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.pdf
ぐぐった
合ってるかは知らん
- 737 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 11:10:39 ]
- >>736
それっすそれっす
- 738 名前：しろうと [2008/10/26(日) 16:22:55 ]
- 突然すみません。しろうとです。
バイナリーサーチの計算量はO(log n)ですが、その導き方について。
T(n)=O(1) n<=1
T(n)=T(n/2)+O(1) n>1
以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。
ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1
したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。
また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか？
- 739 名前：デフォルトの名無しさん [2008/10/26(日) 18:18:41 ]
- アルゴリズムをよく考えてみ
k=１のとき、つまり1回分割したときはn/2
k=2のとき、つまり2回分割したときはn/4 = n/2^2
k=3のとき、つまり3回分割したときはn/8 =n/2^3
といって、求めたいのは、つまりnをk回分割したときの計算量だから
k=???のとき、つまりk回分割したときにn/2^k → ???を求める為には
数式頼みはよろしくないよ
- 740 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 18:49:12 ]
- >>738
ひどい導出だ．O(1) の扱いが雑すぎる．
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述．
もし本当に本にこう書いてあるなら捨てたほうがいい．
- 741 名前：くまさん [2008/10/26(日) 18:59:21 ]
- プログラムの初心者です。
アルゴリズムの流れ図について、自然数ｍ、ｎに対して、
ｍのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。
- 742 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 19:37:22 ]
- 流れ図の問題なんだな？そうなんだよな？
ではまず、効率の良いアルゴリズムを言ってくれ。
- 743 名前：くまさん [2008/10/26(日) 22:23:58 ]
- ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。
n＾２＊ｎ＾２＊ｎ＾２
これがヒントだそうです。
どうしたら、よろしいのでしょうか？
お願いします。
- 744 名前：くまさん [2008/10/26(日) 22:44:42 ]
- ｎの４乗はｎの２乗×ｎの２乗です。 ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。
従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。
の2乗
これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。
- 745 名前：デフォルトの名無しさん [2008/10/26(日) 22:45:56 ]
- よくわからんな、何だろ
ビット演算を絡ませたアセンブラ的な問題なのかな？
お前らどうする？これ放置していいん？
- 746 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 22:53:29 ]
- 罠じゃねえの?
説明がデタラメだし。
- 747 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:18:56 ]
- >>744
＞ｎの８乗はｎの２乗×ｎの４乗
ダウト。乗数は足し算です。
n^8
= n^(4+4)
= n^4 * n^4
= (n * n * n * n) * (n * n * n * n)
ね？
＞ｎの６４乗はｎの２乗×ｎの３２乗
同様に、ｎの３２乗×ｎの３２乗がｎの６４乗で
あえて言うなら（ｎの３２乗）の２乗がｎの６４乗
つまり
>>745
問題のヒントが出鱈目だから放置していい。
- 748 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:20:45 ]
- >>736の問題助けてくれｗまじでｗ
- 749 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:27:51 ]
- 要するに>>736を分かりやすく翻訳してくれって言ってる？
サマリー読む限り、別に問題提起ってわけではなさそうだけど……？
- 750 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:35:16 ]
- >>749
4bitの集合を考え、具体例として以下で計算した場合
0000, 1100 0011, 0100, 0110, 0111, 1011, 0001.
1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね？
- 751 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:12:25 ]
- ４ページのExample 1の話？
- 752 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:28:44 ]
- うん
- 753 名前：デフォルトの名無しさん [2008/10/28(火) 20:57:21 ]
- kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7885.txt
上記は疑似コードで書かれていますが、アルゴリズム１もアルゴリズム２も
配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム１の
０２行目では配列をどうやってtempにぶちこめるのでしょうか？ 配列Aが例えば
{2, 6, 3, 7}だとすると、tempには最初に何が入るのですか？再帰なので、
A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり
A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の２が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。
- 754 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 21:06:35 ]
- >>753
リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。
- 755 名前：デフォルトの名無しさん [2008/10/29(水) 00:57:04 ]
- 再帰の仕組みって勉強すればなんとかなるもんじゃないだろ
何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ
>>753
間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない
君の配列の書き方を使って書くと
A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方！
じゃあA[1,3]の最小値って何さ → 同じやり方で済むじゃん
みたいな考え方を適用すべき
- 756 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 01:01:16 ]
- LISP学んだり、フラクタル図形書いてみたり
だまし絵とか見に行くといいんじゃないかな
- 757 名前：755 [2008/10/29(水) 01:09:03 ]
- >>753
おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。
- 758 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:22:29 ]
- n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？
ソートして先頭3つでやるのはなんかもったいない気がして・・・
- 759 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:41:45 ]
- 端から舐めて上位3個を取り出す方法だろうなぁ
- 760 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:47:31 ]
- それだと比較回数3n？
- 761 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:50:26 ]
- ヒープ
- 762 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:53:24 ]
- 20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？
- 763 名前：デフォルトの名無しさん [2008/10/29(水) 15:30:41 ]
- >>757
ありがとうございました。
- 764 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 15:31:13 ]
- nth_element, partial_sort
- 765 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:05:02 ]
- >>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．
実用的にはデータの分布に依存するので，実測しないと何とも．
- 766 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:16:37 ]
- >>765
全体ソートするのとオーダーかわらんじゃん
- 767 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:31:52 ]
- っ「選択アルゴリズム」
- 768 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:33:23 ]
- 選択アルゴリズムはk番目の値しか探せないぞ
- 769 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:38:05 ]
- >>768はまったくプログラミングの才能が無いな。
- 770 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:41:47 ]
- partial_sort使うのがいいんじゃない？
- 771 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:43:47 ]
- >>770
それ、なんのこと言ってるの? C++前提なの?
- 772 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:50:02 ]
- 「部分ソート」と呟いておく。
- 773 名前：デフォルトの名無しさん [2008/10/29(水) 19:03:55 ]
- たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして
93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。
- 774 名前：デフォルトの名無しさん [2008/10/29(水) 19:09:33 ]
- もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。
次のループでそれ以上を選ぶ。
- 775 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 21:53:17 ]
- v[0]が4にならねーよ
わからねー
- 776 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 06:19:01 ]
- >>766
全体ソートは O(n log n) だから log の値が違う
- 777 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 13:30:13 ]
- Nは100～10000程度で、double x[N]; に適当な数が入っているとします。
任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、
あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。
ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、
任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。
（与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ）
このときに上の二分法のようなアルゴリズムはあるでしょうか？
普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。
- 778 名前：デフォルトの名無しさん [2008/10/30(木) 13:54:09 ]
- ないな O(N)で困る例はなんだよ
- 779 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 15:30:46 ]
- >>778
ないこと証明できる？
困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり？
- 780 名前：デフォルトの名無しさん [2008/10/30(木) 15:43:21 ]
- a,bの存在範囲毎に最小点を計算しておけば定数時間
- 781 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 16:07:07 ]
- >>777
i11www.iti.uni-karlsruhe.de/~awolff/pub/dmsw-fpqgc-06.pdf
のイントロに書いてあるけど，
[CY84]: 前処理 O(n^2)，問い合わせ O(log n)
[LC85]: 前処理 O(n^2)，問い合わせ O(log n)
[MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね．
一通り目を通してみたけど，LC85 は特に簡単．双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して，点位置決定問題に帰着するだけ．
- 782 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:50:08 ]
- >>781
あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。
追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか？
- 783 名前：デフォルトの名無しさん [2008/10/30(木) 19:16:37 ]
- そもそも何に必要なんだよ?
- 784 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 19:34:27 ]
- >>782
私の大学からだとCY84以外は契約論文誌なので，Webから取れた．
もし必要ならどっかにアップロードするよ．
Mu03はciteseerからも取れたので，論文名で検索してみると良い．
- 785 名前：デフォルトの名無しさん [2008/10/30(木) 19:47:13 ]
- 前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では?
- 786 名前：デフォルトの名無しさん [2008/10/30(木) 19:50:29 ]
- 最後のやつだとこの辺に関連情報あるぞ
scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr=
- 787 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:04:09 ]
- >>784
Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。
>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。
- 788 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:29:11 ]
- >>785
O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。
なので、クエリ時間を増やしても n^2 より安い手法が存在する。
- 789 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:28:46 ]
- マス目に二種類の記号を置いていった時、
AAA ABA
ABB ABA
AAA AAA
というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？
- 790 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:43:56 ]
- >>789
問題が不明瞭
マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ？
- 791 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:54:59 ]
- 簡単な方法はない。
地道に全回転・反転パターン（8通り）を網羅してチェックする。
プログラムが見通しよくなるように工夫がひつようかも。
- 792 名前：デフォルトの名無しさん [2008/10/31(金) 18:21:54 ]
- 行同値的を出してそれを比較すれば・・・駄目か
- 793 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 18:37:25 ]
- トランザクションメモリの実装
ここでやる夫的に説明してくれよ
- 794 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 19:41:21 ]
- . ' _ 二二 _ .､
／ /´ -‐…‐- .｀＼
/ /´ i !｀ヽﾄ､
. ,ﾍ ,' i ! ! | |i |ﾊ i ヽ ｷﾘｯ
/ ゝ! ﾉ| ! !::__!::ノ ´ ￣ i::.i ｜!
＼ .| .:i i :i i |´ ＼ ／ ｀!､ﾊ:!
｀ヽi 从 i i | ニﾆﾐ .ﾆニ !:::::| ＜トランザクションメモリの実装
. | ＹﾊｉﾊN {r::ﾘ｀ ´{r::ﾘ '::::N ここでやる夫的に説明してくれよ
. | ヽゝ ´´ ｀｀ﾊ!｀
. |∧ Ⅵ! ′ ,':::|
ｊ/∧ _!::｝ 、 ⊂' ..ｲ:::::|
///∧´ ∨ ｀ ,.... ィ´ﾞY:::::|
. /////∧ ヽ {ﾄ､∧ |::::::!
,＜￣￣∧ } ｀ヽ ＞''} {￣｀ヽ
. / ｀ヽ:::::::::Y´ヽ i´｀∨::::∧
/ ∨:::::| .:: ! i .:.: !::::/ i
＿ ＿＿_
,. :'´: :,. -―‐-ミ:ヽ、
／: : : :厶ｨ': ´￣￣ヾ : :＼
/: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼ ＜じゃっておｗｗｗ
ｉ: : :.!: : : ﾚ‐' ｀￣⌒ ⌒" ﾄﾍ:ﾊ!
ﾄ--|: : :.!: : ､| ｰ‐'' ´ ｀'ｰ }: :.ﾄ
ﾐ ﾐ ﾐ : :!: : : :! z=≡ ≡z.{: :.ﾊ ﾐ ﾐ ﾐ
/⌒)⌒)⌒.ﾊ :_Nとつ ＼＼＼ C VVﾘ /⌒)⌒)⌒)
| / / /:弋こ ＼ヽ ＿＿,. } (⌒)/ / / /／
| :::::::::::(⌒) : :}＼ / 1 ／ ゝ :::::::::::/
| ノくf⌒Y ｀ {_ _,ﾉイ| / ） /
ヽ / ヽ ﾍ,､ _｢ |::!:::::} / ／ バ
| | l||l 从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l バ ン
ヽ -一''''''"~~｀`'ー--､/:::::ｲ; -一'''''''ー-､ ン
ヽ ＿＿＿＿(⌒)(⌒)⌒) ):::/} (⌒＿(⌒)⌒)⌒))
- 795 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 21:00:10 ]
- かんなぎは評価されすぎ。
- 796 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 03:17:29 ]
- 無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。
って意味のわかる人教えて下さい。
- 797 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 06:37:03 ]
- 意味が分からんな。
「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。
- 798 名前：796 mailto:sage [2008/11/13(木) 06:40:40 ]
- >>797
無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか？
- 799 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:13:30 ]
- やはり意味不明。
今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。
- 800 名前：796 mailto:sage [2008/11/13(木) 07:25:04 ]
- そうですか。失礼しました。忘れてもらって結構です。
- 801 名前：796 mailto:sage [2008/11/13(木) 07:31:12 ]
- 別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは
例えばどういうときかわかりますか？
- 802 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:42:43 ]
- >>801
G = (V,E) を 3点 a,b,c からなるグラフとし，
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し，
頂点 a から b への最短路を求めようとすると破綻する．
|
 |
