逆算のためのポリシーベースのデータ構造の使用

g ヘッダー ファイルを使用して、C コンパイラでコードをコンパイルします。 g は、C でポリシーベースのデータ構造のコードをコンパイルするための Linux ベースのヘッダー ファイルです。ポリシーベースのデータ構造は、コードの高いパフォーマンスと柔軟性を実現するために使用される構造です。これらのデータ構造は非常に豊富であるため、要素のインデックスの検索、インデックス位置への要素の挿入、インデックス範囲からの要素の削除など、多くの機能に使用できます。

Example

の中国語訳は次のとおりです:

Example

逆カウントの例を見てみましょう -

ツリーを構築するための内部トラバースが 1,2,3,4,5 であるとします。これを逆にトラバースすると、ツリーの形式は 5,4,3 になります。 2 ,1.

次のツリー構造を入力として受け取ります

リーリー

指定された構造ツリーの長さは 4 です。ここで、反転のプロセスを理解するために次の手順を検討します。

ステップ 1 - 要素は index[0] で始まり、5、 で始まり、index[4] までのすべての要素とペアになります。は 1 です。したがって、インデックス 0 と 4 の間の合計数は 4 になります。

リーリー

ステップ 2 - 要素は index[1] から始まり、4、 となり、index[4 ] まで各要素とペアになります。は 1 です。したがって、インデックス 1 から 4 までの合計数は 3 になります。

リーリー

ステップ 3 - 要素は index[2] で始まり、3、 で始まり、index[4] まで各要素とペアになります。それが1です。したがって、インデックス 2 と 4 の間の合計数は 2 になります。

リーリー

ステップ 4 - 要素は index[3]、つまり 2 で始まり、index[4 ]# まで各要素とペアになります。 ##、つまり 1。したがって、インデックス 3 と 4 の間の合計数は 1 になります。 リーリー

このようにして、特定の構築ツリーの反転を書くことができます。したがって、count(4 3 2 1) の反転回数の合計は

10 になります。

この記事では、ポリシーベースのデータ構造を使用して、反転カウントの問題を解決します。

＃＃＃文法＃＃＃

プログラムでは次の構文を使用します -

リーリー

パラメータ

data_type

- ベクトルに使用されるデータ型。

vector_variable_name

-ベクトルに使用する変数名。

リーリー パラメータ

typedef

- これは、C プログラムで使用される予約キーワードです。

int

-挿入された配列項目のデータ型。

null_type

- これはマッピング戦略であり、コレクションとして使用されます。マップする場合、2 番目のパラメータはマップ タイプでなければなりません。

less

- 2 つの関数の比較。 rb_tree_tag

- 挿入と削除に基づく赤黒ツリーのツリー タイプ。

tree_order_statistics_node_update

-これは、ヘッダー ファイル「tree_policy.hpp」に基づいています。これには、ノード バリアントのツリー コンテナーを更新するためのさまざまな操作が含まれています。したがって、サブツリー内のノードを追跡します。

pbds

- ポリシーベースのデータ構造の変数名。

リーリー ＃＃＃アルゴリズム＃＃＃

ヘッダー ファイル

iostream

と

vector を使用してプログラムを開始します。
• 次に、

  g に基づいたヘッダー ファイルのポリシーベース データ構造 (pbds) について説明します。 GNU のポリシーに従って、データ構造に基づいて必要な名前空間を使用します。つまり、「名前空間 __gnu_pbds を使用する」ということです。

  これは、pbds に従ってツリーの形式を初期化します、すなわち
'typedeftree, rb_tree_tag,tree_order_statistics_node_update> pbds;
• これらを使用することで、サブツリー内のノード。

  Double Long データ型 'inversion_Cnt'

  の関数定義を定義しています。これはベクトル整数パラメータを受け取り、配列要素のアドレスを格納します。

• 合計ペアの逆カウントを処理するために、変数「cnt」に「0」を格納します。

• pb

  という名前のオブジェクトは、配列要素の挿入と並べ替えを操作するために、戦略ベースの変数
'pbds'
• に初期化されます。

  変数を初期化した後、for

  ループを使用して配列要素を反復処理します。この配列要素は、次の 2 つのステートメントに従って反転されます。 -

• cnt = i-pb.order_of_key(arr[i]);
-
,
• ,

  ,,,# を計算します。 ＃＃ 待って。 pb.insert(arr[i]); - 事前定義関数 insert() を使用して、配列要素の反転、つまり arr[i] を追加します。

• main 関数を開始し、ベクトル配列入力を宣言します。

次に、変数
• 'count'

  を使用して関数

  'inversion_Cnt'
を呼び出します。

• 最後に、'count' 変数は、配列内の反転の合計数を示します。

• Example の中国語訳は次のとおりです: Example

このプログラムでは、戦略的なデータ構造を使用して数値の逆数を計算します。

#include <iostream>
#include <vector>
// *******g++ header file*********
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
double long inversion_Cnt( vector<int>& arr) {
   double long cnt = 0;
   pbds pb;
   for(int i = 0; i < arr.size(); i++) {
      cnt += i-pb.order_of_key(arr[i]); 
      pb.insert(arr[i]); // add the array element 
   }
   return cnt;
}
int main() {
   vector<int> arr = {5, 4, 3, 2, 1}; // The inversion of following input array is <5,4>, <5,3>, <5,2>, <5,1>, <4,3>, <4,2>, <4,1>, <3,2>, <3,1>, <2,1>
   double long count = inversion_Cnt(arr);
   cout<<"Total number of inversion count using Policy based data structure is : "<<count<<endl;
   return 0;
}

输出

Total number of inversion count using Policy based data structure is : 10

结论

我们通过执行基于反转计数的程序来探索 Linux 头文件 (g++) 的概念。众所周知，C++程序用于操作系统，它有一个跟踪器来记录系统的每一个信息。与此程序相同，我们看到子树如何跟踪其每个节点。

以上が逆算のためのポリシーベースのデータ構造の使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。