資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Java程式：查詢陣列中給定索引範圍內的最大公約數(GCD)
在資料結構領域，範圍查詢是一種預處理方法，可以有效地對某些輸入資料進行操作。範圍查詢負責回答對任何資料子集上的特定輸入的任何查詢。如果我們想從表中複製一些資料列，我們需要為該特定資料集維護一個索引。索引是一個直接連結或鍵，旨在提供對資料集的高效搜尋過程。它主要用於加快從丟失的資料來源中檢索資料。
在數學中，最大公約數（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)。
方法
方法 - 使用線段樹查詢給定範圍內數字的GCD的程式
使用線段樹查詢給定範圍內數字的GCD的程式
為了使用線段樹查詢給定範圍內數字的GCD，我們需要遵循一些不可避免的步驟。
線段樹的構造
輸入陣列的元素是葉節點。
每個內部節點代表所有葉節點的GCD。
可以使用線段樹進行陣列表示。
-2*(i+1)，索引的左元素
-2*(i+2)，索引的右元素
-父節點是floor((i-1)/2)
使用給定陣列構造新的線段樹
從段arr[0 . . . n-1]開始。
將它們分成兩半。
對這兩半都進行相同的呼叫。
儲存GCD的值。
構造給定範圍的GCD
對於每個可能的查詢，移動樹的左右兩半。
當給定範圍與一半重疊時；它返回節點。
當它位於給定範圍之外時，此時返回0。
對於部分重疊，根據所遵循的方法遍歷並獲取返回。
示例
import java.io.*;
public class tutorialspointGCD{
private static int[] segTree;
public static int[] buildSegmentTree(int[] arr){
int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
int size = 2*(int)Math.pow(2, height)-1;
segTree = new int[size];
SegementTree(arr, 0, arr.length-1, 0);
return segTree;
}
public static int SegementTree(int[] arr, int startNode,int endNode, int si){
if (startNode==endNode) {
segTree[si] = arr[startNode];
return segTree[si];
}
int mid = startNode+(endNode-startNode)/2;
segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
SegementTree(arr, mid+1, endNode, si*2+2));
return segTree[si];
}
private static int gcd(int a, int b){
if (a < b){
int temp = b;
b = a;
a = temp;
}
if (b==0)
return a;
return gcd(b,a%b);
}
public static int findRangeGcd(int startNode, int endNode, int[] arr){
int n = arr.length;
if (startNode<0 || endNode > n-1 || startNode>endNode)
throw new IllegalArgumentException("Invalid arguments");
return findGcd(0, n-1, startNode, endNode, 0);
}
public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si){
if (startNode>endQuery || endNode < startQuery)
return 0;
if (startQuery<=startNode && endQuery>=endNode)
return segTree[si];
int mid = startNode+(endNode-startNode)/2;
return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
}
public static void main(String[] args)throws IOException{
int[] a = {10, 5, 18, 9, 24};
buildSegmentTree(a);
int l = 0, r = 1;
System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
l = 2;
r = 4;
System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
l = 0;
r = 3;
System.out.println("Greatest Common Divisor is here s . Please collect the data: "+findRangeGcd(l, r, a));
}
}
輸出
Greatest Common Divisor is here. Please collect the data: 5 Greatest Common Divisor is here. Please collect the data: 3 Greatest Common Divisor is here s . Please collect the data: 1
結論
在今天的文章中，我們使用特定的程式設計環境開發了一些可能的程式碼。透過這些編碼的邏輯和提到的演算法，我們學習瞭如何正確地找到陣列中給定索引範圍內的最大公約數。
201 次瀏覽
