C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で最大nCr値を持つ指定された配列からペアを検索します

コンセプト

n個の正の整数の配列arr[]が与えられた場合、タスクは、arr [i]Carr[j]が最大で可能になるように配列から要素arr[i]とarr[j]を決定することです。複数の有効なペアについては、いずれか1つを印刷してください。

入力 

arr[] = {4, 1, 2}

出力 

4 2
4C1 = 4
4C2 = 4
2C1 = 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;
// Now Function to print the pair that gives maximum nCr
void printMaxValPair1(vector<long long>& v1, int n1){
   sort(v1.begin(), v1.end());
   // This provides the value of N in nCr
   long long N1 = v1[n1 - 1];
   // Case 1 : When N1 is odd
   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;
   }
   // Case 2 : When N1 is even
   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;
   }
}
// Driver code
int main(){
   vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
   int n1 = v1.size();
   printMaxValPair1(v1, n1);
   return 0;
}

出力

6 3

  1. Xとの絶対差がC++で最大値を与えるノードを見つけます

    ツリーがあり、すべてのノードの重みと整数xがあるとします。 | weight [i]--x|となるようなノードiを見つける必要があります。最小です。グラフが以下のようで、x =15 出力は3になります。ノードごとに次のようになります ノード1、| 5 – 15 | =10 ノード2、| 10 – 15 | =5 ノード3、| 11 – 15 | =4 ノード4、| 8 – 15 | =7 ノード5、| 6 – 15 | =9 アイデアは単純です。ツリーでDFSを実行し、ノードの追跡を行います。ノードのxとの重み付き絶対差が最小値を示します 例 #include

  2. Pythonで最大nCr値を持つ指定された配列からペアを検索します

    n個の整数を持つ配列arrがあるとすると、arr [i] Carr [j]ができるだけ大きくなるように、配列からarr[i]とarr[j]を見つける必要があります。ペアが複数ある場合は、いずれか1つを返却してください。 したがって、入力が[4、1、2]のようである場合、出力は4 C1 =4、4C2 =6、2C1 =2として、4 2になります。したがって、（4,2）は必要に応じてペアになります。 これを解決するには、次の手順に従います- リストを並べ替えるv N：=v [n-1] N mod 2が1と同じ場合、 最初：=N / 2（整数除算） 秒：=最初+1 左：=-1、右：=-1