C++에서 이진 리프팅을 사용하여 N 숫자의 접두사 합계에서 X보다 크거나 같은 첫 번째 요소를 찾습니다.

이 문제에서는 N개의 숫자와 정수 값 x로 구성된 배열 arr[]을 얻습니다. 우리의 임무는 X보다 크거나 같은 N 숫자의 접두어 합에서 첫 번째 요소 를 찾기 위해 이진 부스팅을 사용하는 프로그램을 만드는 것입니다.

접두사 sum 数组元素的强>은 각 요소가 해당 인덱스까지 초기 배열의 모든 요소의 합계인 배열입니다.

예제 - array[] = {5, 2, 9, 4, 1}

prefixSumArray[] = {5, 7, 16, 20, 21}

이 문제를 이해하기 위해 예를 들어 보겠습니다.

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

Solution

여기에서는 Binary Boost 개념을 사용하여 문제를 해결하겠습니다. 이진 승격은 주어진 숫자의 값을 0에서 N까지 2의 거듭제곱(비트 뒤집기에 의해 수행됨)으로 증가시킵니다.

"P" 인덱스의 초기 값을 찾는 부스트 이진 트리와 유사한 개념을 고려해 보겠습니다. 이는 비트를 뒤집어 값이 X보다 크지 않도록 함으로써 증가됩니다. 이제 이 위치 "P"에서의 양력을 고려해 보겠습니다.

이를 위해 숫자의 비트를 뒤집기 시작합니다. 예를 들어 i번째 비트를 뒤집어도 합이 X보다 크지 않습니다. 이제 'P' 값에 따라 두 가지 경우가 있습니다.

대상 위치는 'position + 2^i'과 'position + 2^(i+1)' 사이에 있습니다. 여기서 i-th 부스팅하면 값이 증가합니다. 또는 대상 위치는 "position + 2^i" 사이입니다. 이를 사용하여 우리 솔루션 프로그램

#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}
int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"The index of first elements of the array greater than the given number is ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

이 어떻게 작동하는지 설명하기 위해 인덱스 위치

를 고려합니다. 출력

The index of first elements of the array greater than the given number is 3

위 내용은 C++에서 이진 리프팅을 사용하여 N 숫자의 접두사 합계에서 X보다 크거나 같은 첫 번째 요소를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!