역방향 계산을 위해 정책 기반 데이터 구조 사용

g++ 헤더 파일을 사용하여 C++ 컴파일러에서 코드를 컴파일합니다. g++는 C++의 정책 기반 데이터 구조용 코드를 컴파일하기 위한 Linux 기반 헤더입니다. 정책 기반 데이터 구조는 코드의 고성능과 유연성을 위해 사용되는 구조입니다. 이러한 데이터 구조는 매우 풍부하므로 요소에 대한 인덱스 검색, 인덱스 위치에 요소 삽입, 인덱스 범위에서 요소 제거 등과 같은 많은 기능에 사용할 수 있습니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

역수 계산의 예를 들어보겠습니다 -

트리를 만들기 위한 내부 순회가 1,2,3,4,5라고 가정하고, 이를 역순으로 순회하면 트리의 형태는 5,4,3,2,1이 됩니다.

다음 트리 구조를 입력으로 사용하겠습니다

으아아아

주어진 구조 트리 길이는 4입니다. 이제 반전 과정을 이해하기 위해 다음 단계를 고려해 보겠습니다.

1단계 - 요소는 5, 인 index[0]로 시작하고 1인 index [4]까지 각 요소와 쌍을 이룹니다. 따라서 인덱스 0과 4 사이의 총 개수는 4입니다.

으아아아

2단계 - 요소는 index[1](4, )에서 시작하여 index[4](1)까지 각 요소와 쌍을 이룹니다. 따라서 인덱스 1~4 사이의 총 개수는 3입니다.

으아아아

3단계 - 요소는 3, 인 index[2]로 시작하고 1인 index [4]까지 각 요소와 쌍을 이룹니다. 따라서 인덱스 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 - 매핑 전략이며 컬렉션으로 사용됩니다. 지도를 작성하려면 두 번째 매개변수가 지도 유형이어야 합니다.

less - 두 기능의 비교.

rb_tree_tag - 삽입 및 삭제를 기반으로 하는 레드-블랙 트리의 트리 유형입니다.

tree_order_statistics_node_update − 이는 노드 변형의 트리 컨테이너를 업데이트하기 위한 다양한 작업이 포함된 헤더 파일 'tree_policy.hpp'를 기반으로 합니다. 따라서 우리는 하위 트리의 노드를 추적할 것입니다.

pbds - 정책 기반 데이터 구조의 변수 이름입니다.

으아아아

알고리즘

• 헤더 파일 iostream 및 벡터를 사용하여 프로그램을 시작합니다. 그다음에는 g++ 기반의 헤더 파일 정책 기반 데이터 구조(pbds)에 대해 설명하겠습니다.

• GNU의 정책인 '네임스페이스 __gnu_pbds 사용'에 따라 데이터 구조를 기반으로 필요한 네임스페이스를 사용하겠습니다. pbds에 따라 트리의 형식을 초기화합니다. 즉, 'typedef tree, rb_tree_tag, tree_order_statistics_node_update>이를 사용하여 하위 트리의 노드를 추적합니다.

• 우리는 벡터 정수의 매개변수를 취하고 배열 요소의 주소를 저장하는 double long 데이터 유형 'inversion_Cnt'의 함수 정의를 정의하고 있습니다.

• 전체 쌍의 역수를 처리하기 위해 변수 'cnt'에 '0'을 저장합니다.

• 그런 다음 pb라는 개체는 정책 기반 변수 'pbds'로 초기화되어 배열 요소의 삽입 및 정렬 작업을 수행합니다.

• 변수를 초기화한 후 for 루프를 사용하여 배열 요소를 반복합니다. 이 배열 요소는 다음 두 명령문에 따라 반전됩니다 -

• cnt += i-pb.order_of_key(arr[i]); - ,, , , , 등을 계산하여

• pb.insert(arr[i]); - 사전 정의된 함수 insert()를 사용하여 배열 요소의 반전(예: arr[i])을 추가합니다.

• 메인 함수를 시작하고 벡터 배열 입력을 선언합니다.

• 그런 다음 변수 '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 중국어 웹사이트의 기타 관련 기사를 참조하세요!