資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式查詢陣列中給定索引範圍內的最大公約數
在資料結構領域，範圍查詢是一種預處理方法，用於以高效的方式操作某些輸入資料。範圍查詢負責回答任何特定輸入在任何資料集上的查詢。如果我們想從表中複製一些資料列，我們需要為該特定資料集維護一個索引。索引是直接連結或鍵，旨在在資料集中提供高效的搜尋過程。它主要用於加速從丟失的資料來源中檢索資料。
在數學中，**最大公約數**（GCD）是可以同時整除兩個輸入整數的最大整數。這裡，所有數字都必須是非零值。舉個例子
GCD of 70, 80 = 10 (10 is the largest number which divides them with remainder as 0) GCD of 42, 120, 285 = 3 (3 is the largest number which divides them with remainder as 0)
查詢陣列中給定索引範圍內的最大公約數的演算法（詳細）
步驟1 - 開始
步驟2 - 構造arr[0]到arr[n-1]的部分
步驟3 - 繼續等分
步驟4 - 對這兩個部分進行遞迴呼叫
步驟5 - 對於每個部分，僅儲存最大公約數的值將儲存線上段樹中
步驟6 - 構建另一個線段樹，從下到上填充它
步驟7 - 每個節點儲存一定範圍內的GCD的一些資料
步驟8 - 如果節點範圍是startQuery和endQuery，則返回值節點
步驟9 - 否則，如果範圍無效，則將返回null或-1作為輸出
步驟10 - 否則，將GCD函式作為遞迴呼叫返回
步驟11 - 終止
查詢陣列中給定索引範圍內的最大公約數的演算法（簡短）
步驟1 - 假設a和b是兩個非零整數
步驟2 - 令a mod b = R
步驟3 - 如果a=b且b=R
步驟4 - 然後，重複步驟2和步驟3
步驟5 - 過程將一直執行，直到a mod b大於零
步驟6 - GCD = b
步驟7 - 終止
查詢陣列中給定索引範圍內的最大公約數的語法
Begin
if c = 0 OR d = 0, then
return 0
if c = d, then
return b
if c > d, then
return findGCD(c-d, d)
else
return findGCD(c, d-c)
End
在此語法中，我們可以看到可能的邏輯程式碼，如何找到兩個非零數字的最大公約數。該過程的時間複雜度為O(Q*N*log(Ai))，輔助空間評估為O(1)。
遵循的方法：
方法1 - 使用線段樹查詢給定範圍內數字的GCD的程式
使用線段樹查詢給定範圍內數字的GCD的程式
要使用線段樹查詢給定範圍內數字的GCD，我們需要遵循一些不可避免的步驟。
線段樹的構建
輸入陣列的元素是葉子節點。
每個單獨的內部節點表示所有葉子節點的GCD。
陣列表示可以透過線段樹完成。
-2*(i+1)，索引的左元素
-2*(i+2)，索引的右元素
-父節點是floor((i-1)/2)
使用給定陣列構建新的線段樹
從線段arr[0 ... n-1]開始該過程。
將它們分成兩半。
對這兩半都進行相同的呼叫。
儲存GCD的值。
構建給定範圍的GCD
對於每個可能的查詢，移動樹中存在於左側和右側的兩半。
當給定範圍與一半重疊時；返回節點。
當它位於給定範圍之外時，此時返回0。
對於部分重疊，遍歷並根據所遵循的方法獲取返回值。
示例
#include <bits/stdc++.h>
using namespace std;
int* st;
int findGcd(int ss, int se, int qs, int qe, int si) {
if (ss > qe || se < qs)
return 0;
if (qs <= ss && qe >= se)
return st[si];
int mid = ss + (se - ss) / 2;
return __gcd(findGcd(ss, mid, qs, qe, si * 2 + 1),
findGcd(mid + 1, se, qs, qe, si * 2 + 2));
}
int findRangeGcd(int ss, int se, int arr[], int n) {
if (ss < 0 || se > n - 1 || ss > se) {
cout << "Invalid Arguments"
<< "\n";
return -1;
}
return findGcd(0, n - 1, ss, se, 0);
}
int constructST(int arr[], int ss, int se, int si) {
if (ss == se) {
st[si] = arr[ss];
return st[si];
}
int mid = ss + (se - ss) / 2;
st[si]
= __gcd(constructST(arr, ss, mid, si * 2 + 1),
constructST(arr, mid + 1, se, si * 2 + 2));
return st[si];
}
int* constructSegmentTree(int arr[], int n) {
int height = (int)(ceil(log2(n)));
int size = 2 * (int)pow(2, height) - 1;
st = new int[size];
constructST(arr, 0, n - 1, 0);
return st;
}
int main() {
int a[] = { 20, 30, 60, 90, 50 };
int n = sizeof(a) / sizeof(a[0]);
constructSegmentTree(a, n);
int l = 1;
int r = 3;
cout << "GCD of the given range is here. Please collect your data:";
cout << findRangeGcd(l, r, a, n) << "\n";
return 0;
}
輸出
GCD of the given range is here. Please collect your data:30
結論
在本文中，我們使用特定的程式設計環境開發了一些可能的程式碼。透過這些編碼邏輯和提到的演算法，我們學習瞭如何正確地找到陣列中給定索引範圍內的最大公約數。
310 次檢視
