ຄຳ ນວນ nCr% p


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Accenture Cadence ອິນເດຍ ສື່ມວນຊົນ Komli Ola Cabs Square
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ Compute nCr% p” ລະບຸວ່າທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາໂມເລກຸນ modulo p. ດັ່ງນັ້ນທ່ານຕ້ອງຮູ້ກ່ຽວກັບຕົວຄູນ binomial. ພວກເຮົາໄດ້ປຶກສາຫາລືກັນແລ້ວໃນບົດຂຽນກ່ອນ ໜ້າ ນີ້. ທ່ານສາມາດກວດເບິ່ງວ່າ ທີ່ນີ້.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ

nCr = 5C2 = 10
nCr% p = 10% 6 = 4
ດັ່ງນັ້ນ, ພວກເຮົາໄດ້ຄິດໄລ່ 5C2 ໂດຍໃຊ້ສູດຂອງຕົວຄູນ binomial. ຫຼັງຈາກນັ້ນ, ໄດ້ເອົາຮູບແບບມູນຄ່າຫຼາຍກວ່າ.

ຄຳ ນວນ nCr% p

ວິທີການ

ໃນບົດຂຽນທີ່ຜ່ານມາກ່ຽວກັບການຄິດໄລ່ຂອງຕົວຄູນ binomial. ສິ່ງທີ່ພວກເຮົາໄດ້ເຮັດກ່ອນອື່ນ ໝົດ ແມ່ນຄິດໄລ່ບັນດາຄຸນຄ່າທີ່ ຈຳ ເປັນໃນການແກ້ໄຂ. ພວກເຮົາໄດ້ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ເພື່ອແກ້ໄຂບັນຫາແຕ່ຫຼັງຈາກນັ້ນພວກເຮົາໄດ້ຄິດໄລ່ມູນຄ່າຂອງ nCr ເທົ່ານັ້ນ. ບໍ່ແມ່ນໂມເລກຸນຕົວກາງບາງຕົວເລກ p. ວິທີການທີ່ໂງ່ຈ້າຈະເປັນການຄິດໄລ່ຕົວຄູນ binomial ແລະຫຼັງຈາກນັ້ນເອົາໂມດູນ p. ແຕ່ມັນມີຂໍ້ ຈຳ ກັດໃນການຄິດໄລ່ນີ້. ທ່ານບໍ່ສາມາດຄິດໄລ່ຕົວຄູນ Binomial ສຳ ລັບ ຈຳ ນວນຫຼວງຫຼາຍເນື່ອງຈາກວ່າມັນຈະສົ່ງຜົນໃຫ້ມີການໄຫຼວຽນເກີນໄປ. ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາວິທີທີ່ສາມາດສ້າງຜົນໄດ້ຮັບທີ່ຖືກຕ້ອງໂດຍບໍ່ຕ້ອງເຂົ້າໄປໃນ ຈຳ ນວນເຕັມເກີນ.

ສິ່ງ ໜຶ່ງ ທີ່ພວກເຮົາສາມາດເຮັດໄດ້ຄືການສືບຕໍ່ ນຳ ໃຊ້ແບບໂມເລກຸນໃນຂະນະທີ່ການຄິດໄລ່ຕົວຄູນ binomial ຂອງພວກເຮົາ. ດັ່ງນັ້ນຮູບແບບການປ່ຽນແປງພຽງແຕ່ແມ່ນການແກ້ໄຂຂອງການໂພດກ່ອນແມ່ນພວກເຮົາຈະເອົາແບບແຜນໃນລະຫວ່າງການ ຄຳ ນວນ. ດັ່ງນັ້ນສູດສູດປະຕິບັດການຂອງພວກເຮົາຈະປ່ຽນແປງເລັກນ້ອຍ, ແຕ່ວ່າການຫັນປ່ຽນຕ່າງໆຍັງຄົງຄືເກົ່າ. ແລະຕົວຄູນ binomial ໃນປະຈຸບັນແມ່ນຂື້ນກັບລັດດຽວກັນກັບທີ່ເຄີຍມີມາກ່ອນ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອ ຄຳ ນວນ 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

ລະຫັດ Java ເພື່ອ ຄຳ ນວນ 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 ແມ່ນວັດສະດຸປ້ອນໃຫ້. ນີ້ແມ່ນຍ້ອນວ່າໃນເວລາທີ່ພວກເຮົາ ກຳ ລັງຄິດໄລ່ຕົວຄູນ Binomial ຂອງພວກເຮົາ, ພວກເຮົາມີວົງນອກແລະວົງ ໜຶ່ງ ໃນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (R), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ຈັດໂຕະເພື່ອເກັບຄ່າຄ່າລະດັບປານກາງ, ແລະດັ່ງນັ້ນຄວາມສັບສົນໃນອະວະກາດຈຶ່ງເປັນເສັ້ນ.