データ構造におけるベルヌーイ分布
ベルヌーイ分布は、x =0とx=1でラベル付けされた2つの可能な結果を持つ離散分布です。x=1は成功であり、x=0は失敗です。成功は確率pで発生し、失敗は確率qでq =1 –pとして発生します。だから
$$ P \ lgroup x \ rgroup =\ begin {cases} 1-p \:for&x =0 \\ p \:for&x =0 \ end {cases} $$
これは、次のように書くこともできます-
$$ P \ lgroup x \ rgroup =p ^ {n} \ lgroup1-p \ rgroup ^ {1-n} $$
例
#include <iostream> #include <random> using namespace std; int main(){ const int nrolls=10000; default_random_engine generator; bernoulli_distribution distribution(0.7); int count=0; // count number of trues for (int i=0; i<nrolls; ++i) if (distribution(generator)) count++; cout << "bernoulli_distribution (0.7) x 10000:" << endl; cout << "true: " << count << endl; cout << "false: " << nrolls-count << endl; }
出力
bernoulli_distribution (0.7) x 10000: true:7024 false: 2976
-
データ構造の最小スパニングツリー
スパニングツリー は、最小数のエッジで接続されたすべての頂点を持つ無向グラフのサブセットです。 すべての頂点がグラフで接続されている場合、少なくとも1つのスパニングツリーが存在します。グラフには、複数のスパニングツリーが存在する場合があります。 最小スパニングツリー 最小スパニングツリー(MST) は、接続された重み付き無向グラフのエッジのサブセットであり、すべての頂点を可能な限り最小の合計エッジ重みで接続します。 MSTを導出するには、プリムのアルゴリズムまたはクラスカルのアルゴリズムを使用できます。したがって、この章ではプリムのアルゴリズムについて説明します。 すでに説明したように、
-
データ構造における二分木表現
ここでは、コンピュータのメモリでバイナリツリーを表現する方法を説明します。表現するには2つの異なる方法があります。これらは配列とリンクリストを使用しています。 このようなツリーが1つあるとします- 配列表現は、レベル順の方法を使用して要素をスキャンすることにより、ツリーデータを格納します。したがって、ノードをレベルごとに格納します。一部の要素が欠落している場合は、空白のままにします。上記のツリーの表現は以下のようになります- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 5