NCr% p കണക്കുകൂട്ടുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് കഡെൻസ് ഇന്ത്യ കോംലി മീഡിയ ഓല ക്യാബുകൾ സമചതുരം
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം

പ്രശ്നം പ്രസ്താവന

“NCr% p കമ്പ്യൂട്ട് ചെയ്യുക” എന്ന പ്രശ്നം നിങ്ങൾ ബൈനോമിയൽ കോഫിഫിഷ്യന്റ് മൊഡ്യൂളോ പി കണ്ടെത്തേണ്ടതുണ്ടെന്ന് പറയുന്നു. അതിനാൽ നിങ്ങൾ ആദ്യം ദ്വിമാന ഗുണകത്തെക്കുറിച്ച് അറിഞ്ഞിരിക്കണം. മുമ്പത്തെ പോസ്റ്റിൽ‌ ഞങ്ങൾ‌ ഇതിനകം ചർച്ചചെയ്തു. നിങ്ങൾക്ക് അത് പരിശോധിക്കാൻ കഴിയും ഇവിടെ.

ഉദാഹരണം

n = 5, r = 2, p = 6
4

വിശദീകരണം

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
അതിനാൽ, ദ്വിമാന ഗുണകത്തിന്റെ സൂത്രവാക്യം ഉപയോഗിച്ച് ഞങ്ങൾ 5C2 കണക്കാക്കി. തുടർന്ന് മൂല്യത്തെക്കാൾ മൊഡ്യൂളോ എടുത്തു.

NCr% p കണക്കുകൂട്ടുക

സമീപനം

ദ്വിമാന ഗുണകത്തിന്റെ കണക്കുകൂട്ടൽ സംബന്ധിച്ച മുമ്പത്തെ പോസ്റ്റിൽ. ഞങ്ങൾ ചെയ്തത് ആദ്യം എൻ‌സി‌ആർ പരിഹരിക്കാൻ ആവശ്യമായ മൂല്യങ്ങൾ കണക്കുകൂട്ടി. ഞങ്ങൾ ഉപയോഗിച്ചു ഡൈനാമിക് പ്രോഗ്രാമിംഗ് പ്രശ്നം പരിഹരിക്കുന്നതിന്, പക്ഷേ ഞങ്ങൾ nCr ന്റെ മൂല്യം മാത്രമാണ് കണക്കാക്കുന്നത്. ദ്വിപദ കോഫിഫിഷ്യന്റ് മൊഡ്യൂളല്ല ചില സംഖ്യ p. നിഷ്കളങ്കമായ സമീപനം ആദ്യം ബൈനോമിയൽ കോഫിഫിഷ്യന്റ് കണക്കാക്കുകയും പിന്നീട് പി. എന്നാൽ ഈ കണക്കുകൂട്ടലിന് ഒരു പരിധിയുണ്ട്. വലിയ സംഖ്യകൾക്കായി നിങ്ങൾക്ക് ദ്വിമാന ഗുണകങ്ങൾ കണക്കാക്കാൻ കഴിയില്ല, കാരണം അത് ഒരു ഓവർഫ്ലോയ്ക്ക് കാരണമാകും. അതിനാൽ പൂർണ്ണസംഖ്യ ഓവർഫ്ലോയിലേക്ക് പോകാതെ ശരിയായ ഫലം നൽകാൻ കഴിയുന്ന ഒരു മാർഗം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

നമുക്ക് ചെയ്യാൻ കഴിയുന്ന ഒരു കാര്യം, നമ്മുടെ ദ്വിപദ ഗുണകം കണക്കാക്കുമ്പോൾ മോഡുലസ് തുടരുക. അതിനാൽ മുമ്പത്തെ പോസ്റ്റിന്റെ പരിഹാരമായ ഒരേയൊരു മാറ്റം, കണക്കുകൂട്ടലുകളിൽ ഞങ്ങൾ മോഡുലസ് എടുക്കും എന്നതാണ്. അങ്ങനെ ഞങ്ങളുടെ ആവർത്തന സൂത്രവാക്യം അൽപ്പം മാറും, പക്ഷേ സംക്രമണങ്ങൾ അതേപടി തുടരും. നിലവിലെ ദ്വിമാന ഗുണകം മുമ്പുണ്ടായിരുന്ന അതേ സംസ്ഥാനങ്ങളെ ആശ്രയിച്ചിരിക്കുന്നു.

കോഡ്

NCr% p കണക്കുകൂട്ടുന്നതിനുള്ള സി ++ കോഡ്

#include<bits/stdc++.h>
using namespace std;
// this function just makes our pascal triangle
int computeBinomialCoefficientsModuloP(int n, int r, int p)
{
  int C[r+1];
    C[0] = 1;
    for (int i = 0; i <= n; i++)
    {
        // since the recursive formula is dependent on current and previous binomial coefficient on i
        // if we had run a forward loop our algorithm would have not given us a correct result
        for (int j = min(i, r); j >0 ; j--)
        {
            C[j] = (C[j - 1] + C[j])%p; // use recursive formula
        }
    }
    return C[r];
}

int main()
{
    int n,k,p;cin>>n>>k>>p;
    // here n & k do not satisfy the properties of binomial coefficient
    // then we will answer it as 0
    int val = computeBinomialCoefficientsModuloP(n, k, p);
    if(val != 0)
      cout<<val<<endl;
    else
      cout<<0<<endl;
}
5 2 4
2

NCr% p കണക്കുകൂട്ടുന്നതിനുള്ള ജാവ കോഡ്

import java.util.*;
class Main{
  // this function just makes our pascal triangle
  static int computeBinomialCoefficientsModuloP(int n, int r, int p) 
  {
  	int C[] = new int[r+1];
  	C[0] = 1;
    for (int i = 0; i <= n; i++) 
    { 
      // since the recursive formula is dependent on current and previous binomial coefficient on i
      // if we had run a forward loop our algorithm would have not given us a correct result 
      for (int j = Math.min(i, r); j >0 ; j--) 
      {
          C[j] = (C[j - 1] + C[j])%p; // use recursive formula
      }
    } 
    return C[r]; 
  }
  
  public static void main(String[] args)
  {
      Scanner sc = new Scanner(System.in);
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      int p = sc.nextInt();
      int val = computeBinomialCoefficientsModuloP(n, k, p);
      if(val != 0)
        System.out.println(val);    
      else
        System.out.println(0);
   }
}
5 2 4
2

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N * R), ഇവിടെ N, R എന്നിവ ഇൻപുട്ടുകൾ നൽകുന്നു. കാരണം, ഞങ്ങളുടെ ദ്വിമാന ഗുണകം കണക്കാക്കുമ്പോൾ, ഞങ്ങൾക്ക് ഒരു ബാഹ്യ ലൂപ്പും ഒരു ആന്തരിക ലൂപ്പും ഉണ്ടായിരുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

അഥവാ), ഇന്റർമീഡിയറ്റ് മൂല്യങ്ങൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു അറേ ഉണ്ടാക്കിയതിനാൽ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.