資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學Java區間最小公倍數查詢程式
區間查詢是資料庫中常見的當前熱點操作，存在於資料結構中，用於檢索輸出值位於上限和下限之間的所有記錄。此過程使用某些輸入資料，以有效的方式對特定輸入的任何子集進行結構化。 range 函式（表示為 range()）用於在 for 迴圈中迭代一系列值。我們需要在過程開始時將起始值宣告為 0。如果以某種方式錯過了此步驟，則該過程將執行並迭代迴圈直到結束（-1）。
區間是指可以儲存在變數中的最小值和最大值。它們由運算子生成，用於呼叫變數陣列並返回在 x 到 y-1 之間的區間內的輸出列表。
示例
假設我們有一個整數陣列，我們需要以 LCM(a,r) 的形式評估查詢。因此，我們必須以有效的方式評估查詢。
LCM(a,r) 表示陣列中索引 a 和 r 之間存在的最小公倍數。此處，兩個指標都包含在內。
從數學上我們都知道：最小公倍數 = 分子的最小公倍數 / 分母的最大公約數。
因此，使用此邏輯，我們可以遵循下面編寫的區間最小公倍數查詢規則
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 宣告為在特定編碼環境中查詢最小公倍數操作所需的時間，並且需要 O(N) 時間來構建樹以從編寫的程式中獲得輸出。它還指示該過程的空間需求。
區間最小公倍數查詢演算法：
步驟 1 − 開始
步驟 2 − 為兩個數字初始化兩個數字變數。
步驟 3 − 查詢每個數字的儲存值。
步驟 4 − 使用 'max' 函式分離變數。
步驟 5 − 如果 max 可被第一個數字和第二個數字整除。
步驟 6 − 將 max 作為最小公倍數打印出來。
步驟 7 − 否則，如果不可整除，則將其加 1。
步驟 8 − 然後再次轉到步驟五，直到打印出一個數字。
步驟 9 − 重複此過程，直到找到滿足條件的最大值。
步驟 10 − 結束。
區間最小公倍數查詢語法
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]);
}
在此語法中，我們解釋瞭如何在特定編碼環境中進行區間最小公倍數查詢。
使用方法
方法 1 − 使用線段樹的樸素方法。
方法 2 − 以一般方式查詢兩個數的最小公倍數。
使用線段樹的樸素方法
此問題沒有更新操作，但僅使用樸素方法是不正確的。我們需要實現線段樹才能獲得可能的結果。這裡我們將使用一個邏輯：
LCM(a, b) = (a*b) / GCD(a,b)
以下是實現步驟：
為陣列構建線段樹。
遍歷線段樹的特定範圍。
計算該範圍內的最小公倍數。
列印該線段的答案。
示例 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
以一般方式查詢兩個數的最小公倍數
在此程式中，我們有兩個整數 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.
結論
在今天的文章中，我們學習瞭如何使用特定編碼環境編寫程式來找出給定區間最小公倍數查詢的範圍。
167 次瀏覽
