数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python 3 范围LCM查询程序
范围查询是数据库中常见的当前热点操作，存在于数据结构中，用于恢复所有输出值位于上限和下限之间的记录。此过程使用一些输入数据，以高效的方式将它们组织到特定输入的任何子集上。范围函数，表示为 range()，用于在 for 循环中迭代一系列值。我们需要在过程开始时将起始值声明为 0。如果以某种方式错过了此步骤，则过程将运行并迭代循环直到结束 (-1)。
范围是可以在变量中存储的最小值和最大值。它们由运算符生成，并用于调用变量的数组。它们返回在 x 到 y-1 之间的范围内的输出列表。
示例
假设我们有一组整数数组，我们需要以 LCM(a,r) 的形式评估查询。因此，我们必须以高效的方式评估查询。
LCM(a,r) 表示数组中索引 a 和 r 之间存在的最小公倍数。此处，两个指标都包含在内。
从数学上我们都知道；最小公倍数 = 分子最小公倍数 / 分母最大公约数。
因此，使用此逻辑，我们可以遵循下面编写的范围 LCM 查询规则
LCM(a, r) = LCM(arr[a], arr[a+1] , ......... ,arr[r-1], arr[r])
应用此逻辑
输入 –
arr[0] = 5; arr[1] = 7; arr[2] = 5; arr[3] = 2; arr[4] = 10; arr[5] = 12; arr[6] = 11; arr[7] = 17; arr[8] = 14; arr[9] = 1; arr[10] = 44; build(1, 0, 10); cout << query(1, 0, 10, 2, 5) << endl; cout << query(1, 0, 10, 5, 10) << endl; cout << query(1, 0, 10, 0, 10) << endl;
输出 –
60 15708 78540
此特定过程的时间复杂度表示为 O(Log N * Log n)。其中 N 是数组中存在的元素总数。我们需要将 Log n 声明为特定编码环境中 LCM 操作的时间需求查找器，并且需要 O(N) 时间来构建树以从编写的程序中获得输出。它还指示该过程的空间需求。
范围 LCM 查询算法
步骤 1 − 开始
步骤 2 − 为两个数字初始化两个数字变量。
步骤 3 − 查找每个数字的存储值。
步骤 4 − 使用 'max' 函数分离变量。
步骤 5 − 如果最大值可被第一个数字和第二个数字整除。
步骤 6 − 打印最大值作为 LCM。
步骤 7 − 否则，如果不可整除，则将其加 1。
步骤 8 − 然后再次执行步骤五，直到打印出一个数字。
步骤 9 − 重复此过程，直到找到满足条件的最大值。
步骤 10 − 结束。
范围 LCM 查询语法
int find_therangelcm(int a, int tl, int ts, int r) {
if (r > t[a])
return -1;
if (tl == ts)
return tl;
int tm = (tl + ts) / 2;
if (t[a*2] >= r)
return find_therangelcm(a*2, tl, tm, r);
else
return find_therangelcm(a*2+1, tm+1, ts, r - t[a*2]);
}
在此语法中，我们解释了如何在特定编码环境中进行范围 LCM 查询。
遵循的方法
方法 1 − 使用线段树的朴素方法。
方法 2 − 以常规方式查找两个数的 LCM。
使用线段树的朴素方法
此问题没有更新操作，但仅使用朴素方法是不正确的。我们需要实现一个线段树才能获得可能的结果。在这里，我们将使用一个逻辑 -
LCM(a, b) = (a*b) / GCD(a,b)
以下是实现步骤 −
为数组构建线段树。
遍历线段树的特定范围。
计算该范围内的 LCM。
打印该线段的答案。
示例 1
MAX = 1000 tree = [0] * (4 * MAX) arr = [0] * MAX def gcd(a: int, b: int): if a == 0: return b return gcd(b % a, a) def lcm(a: int, b: int): return (a * b) // gcd(a, b) def build(node: int, start: int, end: int): if start == end: tree[node] = arr[start] return mid = (start + end) // 2 build(2 * node, start, mid) build(2 * node + 1, mid + 1, end) left_lcm = tree[2 * node] right_lcm = tree[2 * node + 1] tree[node] = lcm(left_lcm, right_lcm) def query(node: int, start: int, end: int, l: int, r: int): if end < l or start > r: return 1 if l <= start and r >= end: return tree[node] mid = (start + end) // 2 left_lcm = query(2 * node, start, mid, l, r) right_lcm = query(2 * node + 1, mid + 1, end, l, r) return lcm(left_lcm, right_lcm) if __name__ == "__main__": # initialize the array arr[0] = 16 arr[1] = 7 arr[2] = 10 arr[3] = 2 arr[4] = 22 arr[5] = 31 arr[6] = 11 arr[7] = 17 arr[8] = 14 arr[9] = 1 arr[10] = 44 build(1, 0, 10) print(query(1, 0, 10, 7, 5)) print(query(1, 0, 10, 5, 10)) print(query(1, 0, 10, 0, 10))
输出
1 162316 3246320
以常规方式查找两个数的 LCM
在此程序中，我们有两个整数 n1 和 n2。这两个数中较大的数存储在 max 中。
示例 2
def compute_lcm(x, y):
if x > y:
greater = x
else:
greater = y
while(True):
if((greater % x == 0) and (greater % y == 0)):
lcm = greater
break
greater += 1
return lcm
num1 = 16
num2 = 7
print("The L.C.M. is of the given number", compute_lcm(num1, num2))
输出
The L.C.M. is of the given number 112
结论
在今天的文章中，我们学习了如何使用特定的编码环境编写程序来找出给定 LCM 查询的范围。
226 次浏览
