資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律C++ 中二進位制陣列子陣列十進位制值的查詢
在這個問題中，我們給定一個二進位制陣列 bin[] 和 Q 個查詢，每個查詢包含兩個值 L 和 R。我們的任務是**建立一個程式，用 C++ 解決二進位制陣列子陣列的十進位制值查詢**。
**問題描述** - 在這裡，為了解決每個查詢，我們將不得不找到並列印由從 L 到 R 開始的子陣列建立的十進位制數，即子陣列[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 處的值之間的差值。
陣列的第 i 個值將使用二進位制到十進位制轉換公式找到。從右邊應用它，即從 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
更新於: 2020-09-09
79 次瀏覽
廣告