数据结构
网络
关系数据库管理系统(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 次浏览
