แบบสอบถามสำหรับค่าทศนิยมของอาร์เรย์ย่อยของอาร์เรย์ไบนารีใน C++

คำอธิบายปัญหา − เพื่อแก้ปัญหาแต่ละคำถาม เราจะต้องหาและพิมพ์ตัวเลขทศนิยมที่สร้างโดย subarray โดยเริ่มจาก L ถึง R เช่น subarray[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} มันจะสร้างเลขฐานสอง 0010 ที่มีการแปลงทศนิยมเป็น 2

สำหรับเคียวรี 2 อาร์เรย์ย่อยที่สร้างขึ้นคือ { 1, 1, 0, 0, 1, 0, 1} มันจะสร้างเลขฐานสอง 1100101 ที่มีการแปลงทศนิยมเป็น 101

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาง่ายๆ คือการข้ามผ่านสตริงไบนารีจากดัชนี L ไปยังดัชนี R ค้นหาเลขฐานสองที่เกิดขึ้น จากนั้นแปลงเลขฐานสองที่กำหนดให้มีค่าเท่ากับทศนิยม

โปรแกรมแสดงการดำเนินการตามแนวทางของเรา

ตัวอย่าง

#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

แนวทางอื่น การแก้ปัญหาคือการใช้อาร์เรย์ที่คำนวณล่วงหน้า เราจะสร้างอาร์เรย์ที่คำนวณไว้ล่วงหน้าซึ่งจะเก็บตัวเลขทศนิยมที่สร้างไว้จนถึงค่าดัชนี (ni) และสำหรับการแก้ปัญหา เราจะพบความแตกต่างระหว่างค่าที่ l และ r

ค่า ith ของอาร์เรย์จะพบได้โดยใช้สูตรการแปลงเลขฐานสองถึงทศนิยม นำมาประยุกต์จากด้านขวา เช่น จาก n-1

decimalArray[i] =bin[i]*2^(n-1-i) + bin[i+1]*2^(n-1-i+1) + … บิน[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