08/09/21 12:35:56
>>479
不明確ですいません･･･orz
1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。
２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。
平面走査型ちょっくらぐぐってきます。
483:デフォルトの名無しさん
08/09/22 00:32:18
>>481
書くべき事がたりませんでした。。。
では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない
というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？
484:デフォルトの名無しさん
08/09/22 02:43:01
DP使うしかないんじゃない？
485:デフォルトの名無しさん
08/09/23 09:49:23
>>480
状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ．
重さが自然数であれば，品数を n，重さの最大値を W としたとき
普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば
O(n^2 W) のアルゴリズムが簡単に作れる．
重さが実数であれば，基本的には枝刈り探索しかないのだから，
上の三つ組みを持って適当に探索する．
本気を出すなら，品数や重さなどによって適切な探索法が変わるけど
そこまでがんばるかい？
486:デフォルトの名無しさん
08/09/23 11:07:05
>>482
もうググって見つけたかもしれないけれど，
1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる：
・y 軸に平行な直線を考える（走査線と呼ぶ）
・走査線を x = -∞ → +∞ に移動させていく．
・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う．
走査線は y 座標でソートされた二分探索木を用いると，
描画判定を行うべき矩形を O(log n + k) 程度で列挙できる．
二分探索木を管理するのが面倒ならリストで持ってもよいが，
これだと列挙に O(n) かかる．
（矩形がそれなりに散らばっていれば，現実的には相当改善する）
こういうのは「線分交差列挙」などで調べると参考になると思う．
ちなみに矩形が動的に増えたり減ったりするような状況設定なら，
空間分割木などの幾何データ構造を使うことになる．
2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題．
もしデータの段階で「連続した線分の集まり」と思ってよいなら，
1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ．
それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない．
たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと，
曲線と矩形の交差を全チェックするしかない．
487:デフォルトの名無しさん
08/09/25 01:27:20
ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、
それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。
488:デフォルトの名無しさん
08/09/25 19:54:18
自動生成って何？
指定したサイズのもの全てとか、小さい順とかで列挙すること？
それとも、条件を満たすもののサンプリング？
489:デフォルトの名無しさん
08/09/25 21:02:22
nの数を与えて、その全パターンを出すアルゴリズムです。
n=7なら、108通り全部とか。
490:デフォルトの名無しさん
08/10/19 01:32:31
あげ
491:デフォルトの名無しさん
09/01/18 20:54:29
age
492:デフォルトの名無しさん
09/01/19 19:28:43
良スレの予感
493:デフォルトの名無しさん
09/01/19 23:10:09
DBMについて興味があり、最近書籍やウェブなどをあたっていました。
B-Treeなどのアルゴリズムについてなんとなく理解したのですが、
それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
C言語で実装されているソースの解説などどこかにあるでしょうか。
もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、
ちょっと敷居が高いです。
494:デフォルトの名無しさん
09/01/20 01:02:00
いきなりF1に乗ろうとする奴っているよね。
495:デフォルトの名無しさん
09/03/03 06:57:31
>>493
>それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
互換性が要らないならバイナリでダンプしてもいいし、サイズを優先してバイナリで
writeしてもいい。互換性を重視するならテキストでwriteするといい。
速度を優先するならseekしたほうがいい。言語によってはシリアライズ機構がある。
よく分かっただろう？
496:デフォルトの名無しさん
09/03/03 08:09:55
>>493
自分で実装したC#のソースなら持ってるけど
497:デフォルトの名無しさん
09/03/04 18:34:35
そのseekってなんのこと？
498:デフォルトの名無しさん
09/03/05 06:32:12
速いライブラリを自分で探せってこった。
499:デフォルトの名無しさん
09/03/20 20:01:14
499
500:デフォルトの名無しさん
09/03/20 20:56:21
500
501:デフォルトの名無しさん
09/03/20 21:16:26
>>493
ISAM
502:デフォルトの名無しさん
09/03/20 23:09:41
URLﾘﾝｸ(page4.auctions.yahoo.co.jp)
503:デフォルトの名無しさん
09/04/01 00:32:52
多角形の頂点の座標が配列で与えられている時に
その図形の重心を求めるアルゴリズムを教えてください。
頂点の数は３以上。
全ての辺について、他の辺と交差することは無い。
一つの角の大きさは0～360度。
504:デフォルトの名無しさん
09/04/01 00:43:45
三角形の場合なら公式かなんかあったんだっけ？重心って。
多角形の場合は、三角形に分割して、
それぞれの重心に対して、面積で重み付けして相加平均かな。
505:デフォルトの名無しさん
09/04/01 00:58:49
504で十分だけど、以下も参考になるかもしれない。
URLﾘﾝｸ(oshiete1.goo.ne.jp)
506:デフォルトの名無しさん
09/04/01 01:09:53
>>504-505
これで先に進めそうです。
ありがとうございました。
507:デフォルトの名無しさん
09/04/08 10:28:33
ははは
508:デフォルトの名無しさん
09/06/21 20:30:51
漏れはアルゴリズム考えてると頭痛がしてくるからブルートフォースでいいやと思ってたけど
百万個を20ステップでバイナリサーチするlog nの威力を前にしてあっさり宗旨替えしたｗ
509:デフォルトの名無しさん
09/06/21 21:06:10
バルバロイもそうやって教化されていくんだな
510:（ナワバリ付き）グループ内問題なら処理を軽くする法
09/06/21 21:48:11
>>468 見てとっさに「過密ストレス指標」と
「指標が高い奴は低い奴に八つ当たりOK」
っていう移動対象絞り込み方が浮かんだ…
特定対象ばかりが連続移動を避けたい時？
実際には、完全独立自由主義でなければ
ご近所さんグループで扱う方がいいかな
グループ内成員どうしが比較的接近してて
他のグループの成員とは離れている場合
「外」への移動を好ませればいいのかな
平面なら上が第一候補、ダメなら右など
優先でダメなら時計回りに選択肢変更
一通り計算後グループ内を一斉移動
明確なグループがなければ初期座標で分類
以降はそれに従う（大きな変動がなければ）
通信などによって掛かる時間が移動させる
対象の個数そのものならこんな感じかな？
均等に散らばってれば走査線が一番？
研究・ライブラリ等充実してるようだし
(「MMORPGのアイテムやPCの移動じゃないんだから…w」
※身内や同画面内の都合なら移動もガマンしてくれる等
511:デフォルトの名無しさん
09/06/22 23:33:24
そうは言うけど、ソートしとかないと駄目じゃん。
ソートのステップ数も入れて考えられた？
512:デフォルトの名無しさん
09/07/27 18:33:04
あげ
513:デフォルトの名無しさん
09/07/27 21:07:38
COSS age。今年は東工大でやってるわけだが、参加してる人はいるかい。
514:デフォルトの名無しさん
09/07/29 07:01:46
素数をぷりぷり生成し続けるアルゴリズムを教えて下さい
515:デフォルトの名無しさん
09/07/29 07:07:20
つ[エラトステネスの篩]
516:デフォルトの名無しさん
09/07/29 07:15:13
2 3 5 7 9 11 13 ..ってプリプリ垂れるんですよ
だとしてもエラトスに帰着されるのですか？
517:デフォルトの名無しさん
09/07/29 09:05:55
>>516
「ぷりぷり生成」の意味が曖昧。
518:デフォルトの名無しさん
09/07/29 09:17:27
URLﾘﾝｸ(www.nicovideo.jp)
519:デフォルトの名無しさん
09/07/29 12:23:11
一般的に次の素数を求める方法、というのは存在しない。
したがって、（最初の2を別として）奇数を順に生成して、それを
ふるいにかけるという方法しかない。
520:デフォルトの名無しさん
09/07/29 12:42:47
>>519
> 一般的に次の素数を求める方法、というのは存在しない。
マジ？詳しく教えて
521:デフォルトの名無しさん
09/07/29 13:25:07
>>517
2 からスタートして永遠に次に大きい素数を吐き出し続ける事とします
522:デフォルトの名無しさん
09/07/29 14:38:46
>>521
メモリは無限にあるとしてよいならば試し割りなり篩なりで十分。
高々有限ならば、不可能。
523:デフォルトの名無しさん
09/07/29 15:18:33
>>522
無理しなくていいよ
たまには素直になろうね
524:デフォルトの名無しさん
09/07/29 16:11:26
なに上のレス？おつむおかしい人？
>>516のように2,3,5,7,9,11,13とぷりぷりたれるだけなら、
a[0]=2,a[1]=3,a[n+1]=a[n]+2で十分だろ
9を素数だと思ってんだしさ
このテの人はどうせめちゃくちゃ大きい素数なんて出力させないんだし、
試し割りでも採用してればいいだろｗ
525:デフォルトの名無しさん
09/07/29 16:19:43
これは酷い
526:デフォルトの名無しさん
09/07/29 16:39:48
馬鹿にしないで下さい＞＜
527:デフォルトの名無しさん
09/07/29 17:28:28
long a[100000],al=0;for(long i=2;i<200;i++)for(long j=0;(j<al && a[j]*a[j]<=i)?i%a[j++]!=0:0==printf("%d : %d\n",al,a[al++]=i););
これで200個ぷりぷりでます
これ以上圧縮してかけなかったｗ
528:デフォルトの名無しさん
09/07/29 18:34:01
ぐぐったもの。動作確認はしていない。
x[1<<15],w=1200,p,r;main(s){for(;++s<w;)for(x[p+=r==1]=r=s;s%--r;);}
529:デフォルトの名無しさん
09/07/29 19:31:03
毎回エラトスするよりも
素数はメモライズしていった方が速いわけですね
でもこのやり方はメモリも無尽蔵に使うということですかね
530:デフォルトの名無しさん
09/07/29 19:59:53
FOR N=1 TO 12251:PRINT PRM(N):NEXT
531:デフォルトの名無しさん
09/07/29 20:46:49
そういえば、一つ前の素数を返すアルゴリズムはみつかってたような気がするな
確かwikiで見たが、思い出せん
532:デフォルトの名無しさん
09/07/29 20:54:28
一つ前の素数じゃなかったし、まだ証明されてなかった(フォーチュン予想)
これとは別に、wikiに解が素数となる式が載ってるね
常人には理解不能だわ
wz + h + j ? q = 0
(gk + 2g + k + 1)(h + j) + h ? z = 0
(16k + 1)3(k + 2)(n + 1)2 + 1 ? f2 = 0
2n + p + q + z ? e = 0
e3(e + 2)(a + 1)2 + 1 ? o2 = 0
(a2 ? 1)y2 + 1 ? x2 = 0
16r2y4(a2 ? 1) + 1 ? u2 = 0
n + l + v ? y = 0
(a2 ? 1)l2 + 1 ? m2 = 0
ai + k + 1 ? l ? i = 0
((a + u2(u2 ? a))2 ? 1)(n + 4dy)2 + 1 ? (x + cu)2 = 0
p + l(a ? n ? 1) + b(2an + 2a ? n2 ? 2n ? 2) ? m = 0
q + y(a ? p ? 1) + s(2ap + 2p ? p2 ? 2p ? 2) ? x = 0
z + pl(a ? p) + t(2ap ? p2 ? 1) ? pm = 0
533:デフォルトの名無しさん
09/07/29 22:48:35
>>532
どこのwikiに載ってたの？
534:デフォルトの名無しさん
09/07/30 07:13:02
Wikipediaをwikiって略すなー、な所だな
535:デフォルトの名無しさん
09/07/30 12:13:47
ところでウィキペディアにフォーチュンの予想はない件
536:デフォルトの名無しさん
09/07/30 12:42:35
フォーチュンってどれくらい偉い人？
声優で喩えて
537:デフォルトの名無しさん
09/07/30 13:38:19
石丸博也くらい
538:デフォルトの名無しさん
09/07/30 15:11:05
そんなに偉い人だったのか 僕もヌンデマス
539:デフォルトの名無しさん
09/07/30 17:33:34
>>535
google books で、ウェルズのプライムナンバーズの訳本が読めるぞ。
該当箇所は、P122だけど、ちょうどそこは読める範囲にある。
興味があればどうぞ。
540:デフォルトの名無しさん
09/07/31 02:19:19
フォーチュンってサモアのデマで有名なマーガレット・ミードの旦那かよ
541:tor.rootkit.de
09/08/17 17:57:46
自動焼人 ★ ＝ 自動保守 ◆KAWORUKOFI ＝ 自動保守#K9K?_D[L
名言集 その１
『アパッチ砲はワシが作った』
URLﾘﾝｸ(jbbs.livedoor.jp)
自分の管理するしたらばで借りた掲示板にて
> 5062 ：自動保守 ◆AOIMAD.NZM [] ：2009/08/16(日) 00:46:29 ID:nQYgq9jg0
> そもそも、アパッチ砲っていうのは、私が指揮官になった時代に私の先輩たちが導入して
> 先輩たちが命名したもの、っていうかまぁ、そういう砲は今まで存在してないから
> 名前つけなくちゃいけないしｗ
>
> ってことで、使っているうちに広まった名前なので、それが正式名称になるんじゃないかと。
>
> URLﾘﾝｸ(www.paradisearmy.com)（俺の先輩が命名）
> URLﾘﾝｸ(www.paradisearmy.com)（俺が命名？）
※注 「アパッチ砲」の正式名称は「Apache Jmeter」で、もちろん自動焼人の先輩が作ったものではありません
----------------------------------------------
この自動焼人 ★メールマガジンの配信停止をご希望される方は
ｽﾚﾘﾝｸ(sec2chd板)
にて自動焼人 ★までご連絡ください
542:デフォルトの名無しさん
09/11/09 05:02:04
平方根を求めるアルゴリズム下さい
小数点演算を使用せず整数のまま演算し、
実数の平方根を超えない最大の整数を返すものとします
543:デフォルトの名無しさん
09/11/09 06:29:51
isqrt.c でググれ
544:デフォルトの名無しさん
09/11/09 08:42:18
つ 「ニュートン法」
545:デフォルトの名無しさん
09/11/09 12:09:28
１から元の値の間で二分法が簡単かな
546:デフォルトの名無しさん
09/11/09 20:55:55
int sqr(int n){int i=0;for(;i*i<=n;i++);return i-1;}
547:デフォルトの名無しさん
09/11/11 09:09:02
f(x)=x^2-n
f'(x)=2x
2a(x-a)+(a^2-n)=0
x=(n+a^2)/2a
>>> def x(n, a):
... b = (n+a*a)/(2.0*a)
... if b - a > -0.000000001 and b - a < 0.000000001:
... print b
... else:
... x(n, b)
...
>>> x(2, 1)
1.41421356237
548:デフォルトの名無しさん
09/11/11 09:43:10
小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
549:デフォルトの名無しさん
09/11/11 10:39:58
>>546 を「答え」とか
550:デフォルトの名無しさん
09/11/11 10:49:46
>>548
2の平方根が1とかって意味あんのか？
551:デフォルトの名無しさん
09/11/12 01:38:30
以下のような多次元項の因数分解を近似的に行うプログラムを書きたいのですが…、
最小自乗などなら解けるかなと思ったのですが…、どなたかご教授願います。
問題：
ΣCkX^k→Σ(AkXk-Bk)^k+e
すべて実数スカラ値。kの範囲は0<k<n。eは誤差値。^kはk乗の意。
左辺が与えられた時に、eを最小にするAnとBnを求める。
552:551
09/11/12 01:58:02
訂正です
ΣCkX^k→Σ(AkXk-Bk)^k+e
ではなくて
Σ(CkX^k)→Π(AkXk-Bk)^k+e
でした
553:デフォルトの名無しさん
09/11/12 12:50:07
Σ(CkX^k)→Π(AkX-Bk)^k+e
でなく？
554:551
09/11/12 13:38:17
Σ(CkX^k)→Π(AkX-Bk)^k+e です
555:デフォルトの名無しさん
09/11/13 10:02:20
>>546
それバグってルし
556:デフォルトの名無しさん
09/11/13 12:28:15
小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
557:デフォルトの名無しさん
09/11/13 12:42:55
>>556
2の平方根が1とかって意味あんのか？
558:デフォルトの名無しさん
09/11/14 23:12:53
>>557
なんで無いと思うんだ？
559:デフォルトの名無しさん
09/11/15 09:52:32
>>558
>>548-550
>>556-557
560:デフォルトの名無しさん
09/11/15 10:20:04
>>557
いや、そういう仕様だし。
これを平方根だというから誤解が生じるんであって、
「(int)floor(sqrt(x)) の値を float 介さず求める関数を作れ」でしょ。
561:デフォルトの名無しさん
09/11/16 23:15:10
単に開平法をさせたいだけじゃないの？
562:デフォルトの名無しさん
09/11/16 23:33:04
いやいや、ちゃんと >>542 読めよ。
「実数の平方根を超えない最大の整数を返すものとします」
563:デフォルトの名無しさん
09/11/17 23:52:09
高速 sqrt 整数 でググったらおもしろいの見つけた
整数なら各ビット毎に収束させる事で必要ビット数の半分のループ（32bitなら16)で解がでるのね
564:デフォルトの名無しさん
09/11/18 02:02:43
>>563
事実上>>545の亜種のような気がするが…
565:デフォルトの名無しさん
09/11/18 12:28:24
亜種と言うかまんま
566:デフォルトの名無しさん
09/11/18 12:43:06
unsigned int isqrt(unsigned int x)
{
unsigned int s, t;
if (x == 0) return 0;
s = 1; t = x;
while (s < t) { s <<= 1; t >>= 1; }
do {
t = s;
s = (x / s + s) >> 1;
} while (s < t);
return t;
}