資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中查詢單調序列中的元素位置
概念
對於給定的整數l和一個單調遞增序列：
f(m) = am + bm [log₂(m)] + cm³ 其中 (a = 1, 2, 3, …), (b = 1, 2, 3, …), (c = 0, 1, 2, 3, …) 注意，[log₂(m)] 表示取以2為底的對數並向下取整。因此，
如果 m = 1，則值為 0。
如果 m = 2-3，則值為 1。
如果 m = 4-7，則值為 2。
如果 m = 8-15，則值為 3。
我們的任務是確定使得 f(m) = l 的值 m，如果 l 不屬於該序列，則我們必須列印 0。
需要注意的是，這些值可以用64位表示，三個整數 a、b 和 c 不超過 100。
輸入
a = 2, b = 1, c = 1, l = 12168587437017
輸出
23001 f(23001) = 12168587437017
輸入
a = 7, b = 3, c = 0, l = 119753085330
輸出
1234567890
方法
**使用樸素方法** - 對於給定的 a、b、c 值，找到每個 m 值的 f(m) 值並進行比較。
**使用高效方法** - 實現二分查詢，選擇 m = (min + max) / 2，其中 min 和 max 分別表示 m 的最小值和最大值，然後：
- 如果 f(m) < l，則遞增 m。
- 如果 f(m) > l，則遞減 m。
- 如果 f(m) = l，則 m 即為所需答案。
- 現在重複上述步驟，直到找到所需的值或該值在序列中不存在。
示例
// C++ implementation of the approach
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;
// Shows function to return the value of f(m) for given values of a,
b, c, m
long long func(long long a1, long long b1, long long c1, long long
m){
long long res1 = a1 * m;
long long logVlaue1 = floor(log2(m));
res1 += b1 * m * logVlaue1;
res1 += c1 * (m * m * m);
return res1;
}
long long getPositionInSeries1(long long a1, long long b1,
long long c1, long long l){
long long start1 = 1, end1 = SMALL_N;
// Now if c is 0, then value of m can be in order of 10^15.
// Now if c1!=0, then m^3 value has to be in order of 10^18
// so maximum value of m can be 10^6.
if (c1 == 0) {
end1 = LARGE_N;
}
long long ans1 = 0;
// Now for efficient searching, implement binary search.
while (start1 <= end1) {
long long mid1 = (start1 + end1) / 2;
long long val1 = func(a1, b1, c1, mid1);
if (val1 == l) {
ans1 = mid1;
break;
}
else if (val1 > l) {
end1 = mid1 - 1;
}
else {
start1 = mid1 + 1;
}
}
return ans1;
}
// Driver code
int main(){
long long a1 = 2, b1 = 1, c1 = 1;
long long l = 12168587437017;
cout << getPositionInSeries1(a1, b1, c1, l)<<endl;
long long a2 = 7, b2 = 3, c2 = 0;
long long l1 = 119753085330;
cout << getPositionInSeries1(a2, b2, c2, l1)<<endl;
long long a3 = 6, b3 = 2, c3 = 1;
long long l2 = 11975309533;
cout << getPositionInSeries1(a3, b3, c3, l2)<<endl;
return 0;
}輸出
23001 1234567890 0
更新於：2020年7月24日
200 次瀏覽
廣告