用于范围 LCM 查询的 Java 程序

javaobject oriented programmingprogramming更新于 2024/3/28 0:44:17

范围查询是数据结构中常见的数据库当前兴趣操作,用于恢复输出值位于上边界和下边界之间的所有记录。此过程使用一些输入数据,以在特定输入的任何子集上以有效的方式构造它们。范围函数(表示为 range())用于对一系列进行 for 循环迭代。我们需要在过程开始时将起始值声明为 0。如果我们以某种方式错过了这一步,该过程将运行并迭代循环直到结束 (-1)。

范围是可以存储在变量中的最小值和最大值。它们由运算符生成,用于调用变量数组并返回 x 到 y-1 范围内的输出列表。

示例

假设我们有一个整数数组集,我们需要以 LCM(a,r) 的形式评估查询。因此,我们必须以有效的方式评估查询。

LCM(a,r) 表示索引 a 和 r 之间数组的最小公倍数。这里两个表示都包含在内。

从数学上讲,我们都知道;L.C.M. = 分子的 L.C.M/分母的 H.C.F。

因此,通过使用这种逻辑,我们可以遵循下面写的规则来排列 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

public class roudtp {
   static final int MAX = 1000;
   static int tree[] = new int[4 * MAX];
   static int arr[] = new int[MAX];
   static int gcd(int a, int b) {
      if (a == 0) {
         return b;
      }
      return gcd(b % a, a);
   }
   static int lcm(int a, int b) {
      return a * b / gcd(a, b);
   }
   static void build(int node, int start, int end) {
      if (start == end) {
         tree[node] = arr[start];
         return;
      }
      int mid = (start + end) / 2;
      build(2 * node, start, mid);
      build(2 * node + 1, mid + 1, end);
      int left_lcm = tree[2 * node];
      int right_lcm = tree[2 * node + 1];
      tree[node] = lcm(left_lcm, right_lcm);
   }
   static int query(int node, int start, int end, int l,int r){
      if (end < l || start > r) {
         return 1;
      }
      if (l <= start && r >= end) {
         return tree[node];
      }
      int mid = (start + end) / 2;
      int left_lcm = query(2 * node, start, mid, l, r);
      int right_lcm
      = query(2 * node + 1, mid + 1, end, l, r);
      return lcm(left_lcm, right_lcm);
   }
   public static void main(String[] args) {
      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] = 16;
      arr[9] = 1;
      arr[10] = 44;
      build(1, 0, 10);
      System.out.println(query(1, 0, 10, 7, 5));
      System.out.println(query(1, 0, 10, 16, 10));
      System.out.println(query(1, 0, 10, 44, 10));
   }
}

输出

1
1
1

以一般方式查找 2 的最小公倍数

在此程序中,我们有两个整数 n1 和 n2。这两个数字中较大的一个存储在 max 中。

示例 2

public class Main {
   public static void main(String[] args) {
      int n1 = 7, n2 = 16, lcm;
      lcm = (n1 > n2) ? n1 : n2;
      // Always true as a function
      while(true) {
         if( lcm % n1 == 0 && lcm % n2 == 0 ) {
            System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
            break;
         }
         ++lcm;
      }
   }
}

输出

The LCM of 7 and 16 is 112.

结论

在今天的这篇文章中,我们学习了如何使用特定的编码环境编写程序来找出给定的 LCM 查询的范围。


相关文章


有用资源