資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究範圍查詢以查詢具有最大數字和的元素
簡介
在本教程中，我們討論了在 C++ 中進行範圍查詢以查詢具有最大數字和的元素的問題。為了解決這個問題，需要一個元素陣列和一些查詢。查詢表示陣列的索引，並使用這些查詢查詢具有最大數字和的陣列元素。最大數字和是兩個數字（個位和十位數字的加法）或一位數字的最高和。例如：12，其和為 3（1 + 2）。在本教程中，透過使用查詢找到具有最大數字和的數字。
為了實現這種方法，我們使用兩種方法
樸素方法
構建線段樹
演示 1
a[] = {1, 44, 16, 11, 18}
Query = [1, 4]
輸出
The maximum digit sum element is 18
解釋
在上面的示例中，使用查詢的子陣列為 {44, 16, 11, 18}。輸入陣列的起始索引為 0。為了找到最大數字和的元素，以以下方式新增兩位數字
44 = 4+4 = 8
16 = 1+6 = 7
11 = 1+1 = 2
18 = 1+8 = 9
最大和為 9，並且具有最大數字和的元素為 18。
演示 2
a[] = {12, 44, 55, 45, 63}
Query = [2, 4]
輸出
The maximum digit sum element is 55
解釋
在上面的示例中，使用查詢 [2, 4] 的子陣列為 {55, 45, 63}。為了找到最大數字和的元素，像這樣找到每個元素的和
55 = 5+5 = 10
45 = 4+5 = 9
63 = 6+3 = 9
最大和為 10，並且具有此最大和的元素為 55。
C++ 庫函式
語法
size(): 它是 C++ 標準庫的內建函式。它返回輸入字串的長度。
string_name.size();
pow(): 它在 <cmath> 標頭檔案中定義。它接受兩個引數，並返回第一個引數的第二個引數次冪。
pow(a, b);
vector: 它是一個動態陣列，在 C++ 的 vector 標頭檔案中定義。可以輕鬆地插入和刪除其元素。
vector<data_type> vector_name;
ceil(): 它在 <cmath> 標頭檔案中定義。它接受一個引數，並返回引數的最近大於或等於的值。
ceil(n);
sizeof(): 它在 C++ 標準庫中定義。它在編譯時計算變數、常量和資料型別的 size。
sizeof(variable);
演算法 1
初始化一個元素陣列 a[]。
定義查詢以查詢元素的索引。
使用 for 迴圈遍歷查詢中定義的陣列索引。
透過將數字加在一起計算每個元素的和。
列印具有最大數字和的數字。
示例 1
我們使用簡單的方法實現任務。在這種方法中，我們使用 for 迴圈遍歷陣列，查詢中定義了起始和結束範圍。計算元素的和，並列印具有最大數字和的元素。
#include <iostream>
using namespace std;
// Function for calculating the digit sum
int digitSum(int no){
int result = 0;
while (no > 0){
result += no % 10;
no /= 10;
}
return result;
}
// Function for finding the maximum sum digit number
int maximumDigitSum(int a[], int s, int i, int j){
int maxs = -1, maxn = -1;
for (int x = i; x <= j; x++){
int result = digitSum(a[x]);
if (result > maxs){
maxs = result;
maxn = a[x];
}
else if (result == maxs && a[x] > maxn){
maxn = a[x];
}
}
return maxn;
}
// code controller
int main(){
// Input array
int a[] = { 11, 14, 34, 51, 32 };
int s = sizeof(a) / sizeof(a[0]);
int i = 1, j = 4;
cout << "The maximum digit sum number is : "<<maximumDigitSum(a, s, i, j) << endl;
return 0;
}
輸出
The maximum digit sum number is : 34
演算法 2
初始化一個元素陣列。
指定查詢範圍。
構建一個線段樹，其中每個節點表示一個元素陣列。
線段樹的構建首先將其分成兩半，每個節點表示兩個值。
將值插入左孩子和右孩子。
線段樹中的每個節點都有兩個值：數字和 maxDigitSum。
使用查詢中定義的範圍，透過遍歷線段樹來查詢最大數字和。
列印結果。
示例 2
在這裡，我們透過構建線段樹在 C++ 中實現該問題。構建線段樹並使用查詢查詢最大數字和。遞迴呼叫使用者定義的函式 maximumDigitSum 來迭代線段樹並計算輸出。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Function to calculate the digit sum of a number
int digitSumNumber(int no){
int result = 0;
while (no > 0){
result += no % 10;
no /= 10;
}
return result;
}
// Function to build the segment tree
void buildSegmentTree(vector<int>& segtree, const vector<int>& a, int l, int h, int p){
if (l == h){
segtree[p] = a[l];
return;
}
int m = (l + h) / 2;
buildSegmentTree(segtree, a, l, m, 2 * p + 1);
buildSegmentTree(segtree, a, m + 1, h, 2 * p + 2);
segtree[p] = max(segtree[2 * p + 1], segtree[2 * p + 2]);
}
// Function to query the segment tree for maximum digit sum in a given range
int querySegTree(vector<int>& segtree, int i, int j, int l, int h, int p){
if (i <= l && j >= h)
return segtree[p];
if (i > h || j < l)
return 0;
int m = (l + h) / 2;
return max(querySegTree(segtree, i, j, l, m, 2 * p + 1),
querySegTree(segtree, i, j, m + 1, h, 2 * p + 2));
}
// Function to initialize the segment tree
int maxDigitSum(const vector<int>& a, int s, int i, int j){
int segTreeHeight = ceil(log2(s));
int segTreeSize = 2 * pow(2, segTreeHeight) - 1;
vector<int> segtree(segTreeSize);
buildSegmentTree(segtree, a, 0, s - 1, 0);
return querySegTree(segtree, i, j, 0, s - 1, 0);
}
int main(){
vector<int> a = {12, 13, 45, 17, 10, 23};
int s = a.size();
int i = 1, j = 4;
int number = maxDigitSum(a, s, i, j);
cout << "Maximum digit sum in the range [" << i << ", " << j << "]: " << number << endl;
return 0;
}
輸出
Maximum digit sum in the range [1, 4]: 45
結論
我們已經完成了本教程關於在查詢範圍內查詢數字最大和的學習。我們使用了兩種方法來解決本教程的任務：樸素方法和線段樹。用一些示例演示了問題陳述，以便理解其目的。在 C++ 實現過程中，我們初始化一個數組並定義查詢範圍以查詢最大數字和的數字。
214 次瀏覽
