数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
