এই সমস্যায়, আমাদেরকে একটি বাইনারি অ্যারে বিন [] দেওয়া হয়েছে এবং Q প্রশ্নগুলির প্রতিটিতে দুটি মান L এবং R রয়েছে। আমাদের কাজ হল C++ এ একটি বাইনারি অ্যারের সাবয়ারের দশমিক মানের জন্য কোয়েরির সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা শক্তিশালী> .
সমস্যা বর্ণনা − এখানে প্রতিটি প্রশ্নের সমাধান করার জন্য, আমাদের দশমিক সংখ্যাটি খুঁজে বের করতে হবে এবং প্রিন্ট করতে হবে যা 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
অন্য পদ্ধতি প্রি-কম্পিউটেড অ্যারে ব্যবহার করে সমস্যাটি সমাধান করা হয়। আমরা একটি প্রি-কম্পিউটেড অ্যারে তৈরি করব যা (n-i)ম সূচক মান পর্যন্ত তৈরি করা দশমিক সংখ্যা সংরক্ষণ করবে। এবং প্রশ্নগুলি সমাধানের জন্য, আমরা l এবং r-এর মানের মধ্যে পার্থক্য খুঁজে পাব।
বাইনারি থেকে দশমিক রূপান্তর সূত্র ব্যবহার করে অ্যারের ith মান পাওয়া যাবে। এটিকে ডান দিক থেকে প্রয়োগ করা হচ্ছে, অর্থাৎ 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