在C ++中从给定数组中找到最大nCr值的一对

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

概念

对于给定的n个正整数数组arr []，任务是从数组中确定元素arr [i]和arr [j]，以使arr [i] Carr [j]最有可能。对于多于1有效对，请打印其中任何一个。

输入项 

arr[] = {4, 1, 2}

输出结果 

4 24C1 = 44C2 = 42C1 = 4
(4, 2) is the only pairs with maximum nCr.

方法

n C r被视为单调递增函数，即n + 1 C r > n C r。我们可以运用这一事实来接近我们的答案；我们将在所有给定的整数中选择最大值n。这样我们固定了n的值。

现在，我们专注于r。我们知道n C r = n C n-r，这表明nCr将首先达到其最大值，然后减小。

对于n的奇数值，则我们的最大值将出现在n / 2和n / 2 + 1处。

关于n = 11，我们将获得11 C 5和11 C 6的最大值。

对于n的偶数，则我们的最大值将出现在n / 2处。

关于n = 4，我们将获得4 C2时的最大值

示例

// This is C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
//现在可以打印出最大nCr的线对
void printMaxValPair1(vector<long long>& v1, int n1){
   sort(v1.begin(), v1.end());
   //这提供了nCr中的N值
   long long N1 = v1[n1 - 1];
   //情况1：当N1为奇数时
   if (N1 % 2 == 1) {
      long long first_maxima1 = N1 / 2;
      long long second_maxima1 = first_maxima1 + 1;
      long long ans1 = 3e18, ans2 = 3e18;
      long long from_left1 = -1, from_right1 = -1;
      long long from = -1;
      for (long long i = 0; i < n1; ++i) {
         if (v1[i] > first_maxima1) {
            from = i;
            break;
         }
         else {
            long long diff = first_maxima1 - v1[i];
            if (diff < ans1) {
               ans1 = diff;
               from_left1 = v1[i];
            }
         }
      }
      from_right1 = v1[from];
      long long diff1 = first_maxima1 - from_left1;
      long long diff2 = from_right1 - second_maxima1;
      if (diff1 < diff2)
         cout << N1 << " " << from_left1;
      else
         cout << N1 << " " << from_right1;
   }
   //情况2：当N1是偶数时
   else {
      long long maxima = N1 / 2;
      long long ans1 = 3e18;
      long long R = -1;
      for (long long i = 0; i < n1 - 1; ++i) {
         long long diff = abs(v1[i] - maxima);
         if (diff < ans1) {
            ans1 = diff;
            R = v1[i];
         }
      }
      cout << N1 << " " << R;
   }
}
//驱动程式码
int main(){
   vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
   int n1 = v1.size();
   printMaxValPair1(v1, n1);
   return 0;
}

输出结果

6 3

以上是 在C ++中从给定数组中找到最大nCr值的一对 的全部内容， 来源链接： utcz.com/z/321943.html

回到顶部