アルゴリズムオタク

>>938
大きさ16のテーブル

>>938
0000から1111までの数の全部を対象に完全ハッシュ値を求めたいの？

>>938

f(x) = x

>>940
部分集合の場合もありえます。

だったらその部分集合の性質を知ってないと作れないよ

答え知ってると思ってて聞いたけど
オタクとか言うほどレベル高くないんですね

海外じゃ論文とかで有名なネタなのに

へぇ
論文見せて

>>938が勘違いしてるに1カノッサ

ネタ振ったつもりになってるに２ゴールド

で、論文は？

つ www.google.co.jp

アホ？ｗ

「ただいま執筆中です」

結局出せなかったか
ゴミめ

再帰が好きな人います？

好きというより得意

>>953
昔 LISP 触ってたから、今でも好きだよ。

Ｃでも再帰は普通に使うが

loop で考えるよりも再帰の方が考えやすい問題もあるわな

例えばフィボナッチ数を求める関数を作るときなんかそうだね。
先ずシンプルな再帰版を作って、次に結果を保存する版を作りたくなる。
その辺りで、どうせ組み込み型の整数では実現できる数が少ないことに気付いてテーブル作って終了w

n から m まで加算しろ
と, 言われた場合はループも再帰も不可

>>958
フィボナッチって、まずループで作っちゃうけどな。

ループも再帰も、単なる実装の問題だからどうでもいい。

#if 0 // 再帰
int 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

>>960
そもそもフィボナッチを作ろうと思ったことがない。
再帰の例で使われてるのしか見たことない。

>>963
つ 木構造
フィボナッチと置換すれ

O(1) (笑)

STLのpartial_sortの計算時間って、要素数N、ソートする要素数をKとするとNlogKらしいんだけどなんでそうなるの？
http://stdcxx.apache.org/doc/stdlibref/partial-sort.html

std::partial_sortって確か内部的にヒープソートを使ってたはず。

要素数kのheap作成がO(K)で、その後(N-K)要素をpush/popするのに
一回あたりO(logK)というだけ？

最悪の場合な。だから保証されている。
heap木を壊さないために必要。

Wikipediaのselection algorithmsのとこに載ってる、O(N+klogk)の変形quicksortの方が速そうだけど、
わざわざヒープを使ってるのには何か理由があるのかなぁ？
http://en.wikipedia.org/wiki/Selection_algorithm#Optimised_sorting_algorithms

> heap木を壊さないため

どういうこと?

理由はよくわからないが歴史的な経緯により
sort()はクイックソート、stable_sort()にはマージソート、
partial_sortにはヒープソートを使っていると「C++標準ライブラリ」には書いてある。

>>971
ヒープソートについてぐぐってみ。
正確にはO(log2N)必要。O記法によりO(logN)になってるだけ。

調べてみたらpartial_sort()の目的にヒープソートが合っているかららしい。
クイックソートは途中でソート処理を打ち切るのは困難であるが、
ヒープソートは容易であるのでpartial_sort()の用途に合っている。

stable_sortにquickやheapが使えないのはアルゴリズムの性質上そのとおりだと思うけど、安定であることが求められて以内partial_sortにquickが使えないのは納得できないなー。

>>974
資料希望。>>970には真逆のことが書いてあるわけで。

悔しければC++標準化委員会に入れば？

そうする。

まあ無理だと思うけど。

Wikipediaに書いてあるアルゴリズムは、STLのnth_elementとsortを組み合わせれば、自分でコード書かなくても使えることが分かった。
http://wordaligned.org/articles/top-ten-percent

この記事と同じように速度測ってみて、使い分けることにするわ。スレ違いっぽいのでこのへんで。

次スレは？

/* ギャップバッファ
http://haiku.mine.nu/gapbuffer.zip
これの、GapBuffer_GetRealPosition()関数の戻り値が何を意味しているのかわかりません。

age

ギャップバッファー上のバイト位置から、
データとしての先頭からのバイト位置を計算。

return i - (this->end - this->start);
あたりの間違いだろうな。

>>384
すみませんが、よくわかりません。
if(i < this->gap_start)
return i - (this->gap_end - this->gap_start)
else
って事ですか？

初心者スレ行け

ume

da