資料結構
網路
關係資料庫管理系統 (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 次瀏覽
