在C ++中查找给定单调序列中的元素位置

  • Z时代
  • 2024-01-10
  • 分类：综合

概念

对于给定的整数l和单调递增序列-

f(m)= am + bm [log2(m)] + cm ^ 3其中（a = 1，2，3，…），（b = 1，2，3，…），（c = 0，1， 2，3，…）请记住，此处[log2(m)]表示，将对数取为2，然后将值四舍五入。因此，

如果m = 1，则值为0。

如果m = 2-3，则值为1。

如果m = 4-7，则值为2。

如果m = 8-15，则值为3。

我们的任务是确定值m，使f(m)= l，如果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;
//显示函数以给定a的值返回f(m)的值
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;
      //现在，如果c为0，则m的值可以约为10 ^ 15。
      //现在，如果c1！= 0，则m ^ 3值必须为10 ^ 18-
      //因此m的最大值可以是10 ^ 6。
      if (c1 == 0) {
         end1 = LARGE_N;
      }
      long long ans1 = 0;
      //现在，为了进行有效的搜索，请执行二进制搜索。
      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;
}
//驱动程式码
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

以上是 在C ++中查找给定单调序列中的元素位置 的全部内容， 来源链接： utcz.com/z/338253.html

回到顶部