資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++區間最小公倍數查詢程式
範圍查詢是資料庫中常見的當前熱點操作，存在於資料結構中，用於恢復所有輸出值位於上限和下限之間的記錄。此過程使用一些輸入資料，以高效的方式對特定輸入的任何子集進行結構化。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; C++ Program for range LCM queries 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 − 如果最大值可以被第一個數字和第二個數字整除。
步驟 6 − 列印最大值作為最小公倍數。
步驟 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
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int tree[4 * MAX];
int arr[MAX];
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int lcm(int a, int b) { return a * b / gcd(a, b); }
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);
// build the parent
int left_lcm = tree[2 * node];
int right_lcm = tree[2 * node + 1];
tree[node] = lcm(left_lcm, right_lcm);
}
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);
}
int main() {
arr[0] = 16;
arr[1] = 7;
arr[2] = 10;
arr[3] = 22;
arr[4] = 1;
arr[5] = 97;
arr[6] = 11;
arr[7] = 31;
arr[8] = 24;
arr[9] = 15;
arr[10] = 44;
build(16, 0, 10);
cout << query(16, 0, 10, 22, 15) << endl;
cout << query(22, 0, 16, 15, 10) << endl;
cout << query(1, 0, 10, 0, 10) << endl;
return 0;
}
輸出
1 1 0
以一般方式查詢兩個數的最小公倍數
在此程式中，我們有兩個整數 n1 和 n2。這兩個數字的最大值儲存在 max 中。
示例 2
#include <iostream>
using namespace std;
int main() {
int n1, n2, max;
cout << "Enter two numbers to find LCM: ";
cin >> n1 >> n2;
max = (n1 > n2) ? n1 : n2;
do {
if (max % n1 == 0 && max % n2 == 0) {
cout << "LCM = " << max;
break;
}
else
++max;
} while (true);
return 0;
}
輸出
Enter two numbers to find LCM:0
結論
在今天的這篇文章中，我們學習瞭如何使用特定的編碼環境編寫程式來找出給定區間最小公倍數查詢的範圍。
瀏覽量 159
