C++でのバイナリ配列のサブ配列の10進値のクエリ

問題の説明 −ここで各クエリを解決するには、LからRまでのサブアレイによって作成された10進数、つまりサブアレイ[L...R]を見つけて出力する必要があります。

問題を理解するために例を見てみましょう

入力

bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6

出力

2 101

説明

クエリ1の場合、形成されるサブ配列は{0、0、1、0}です。 10進数の変換が2である2進数0010が作成されます。

クエリ2の場合、形成されるサブ配列は{1、1、0、0、1、0、1}です。 10進数の変換が101である2進数1100101を作成します。

ソリューションアプローチ

簡単な解決策 は、バイナリ文字列をインデックスLからインデックスRにトラバースし、形成された2進数を見つけて、指定された2進数をそれに相当する10進数に変換することです。

私たちのアプローチの実装を示すプログラム

例

#include <iostream>
#include <math.h>
using namespace std;

int CalcDecimalValue(int bin[], int L, int R) {
   int decimal = 0;
   int j = 0;
   for(int i = R; i >= L; i--){
      decimal += bin[i] * pow(2, j);
      j++;
   }
   return decimal;
}

int main() {
   
   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i]   [0], query[i][1])<<"\n";
   }
   return 0;
}

出力

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

別のアプローチ 問題を解決するには、事前に計算された配列を使用します。 （n-i）番目のインデックス値までに作成された10進数を格納する事前計算された配列を作成します。そして、クエリを解くために、lとrの値の違いを見つけます。

配列のi番目の値は、2進数から10進数への変換式を使用して検出されます。右側から、つまりn-1から適用します

decimalArray [i] =bin [i] * 2 ^（n-1-i）+ bin [i + 1] * 2 ^（n-1-i + 1）+…bin [n-1] * 2 ^（ 0）。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];

void createDecimalArray(int bin[], int n){
   memset(decimalArray, 0, n*sizeof(int));
   decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
   for (int i = n - 2; i >= 0; i--)
   decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}

int CalcDecimalValue(int L, int R, int n){
   if (R != n - 1)
   return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
   return decimalArray[L] / (1 << (n - 1 - R));
}

int main(){

   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   createDecimalArray(bin, n);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0],    query[i][1], n)<<"\n";
   }
   return 0;
}

出力

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101