대용량의 조합

Question

파스칼의 삼각형의 100 번째 행에있는 특정 항목이 3으로 나눌 수 있는지 계산하려고합니다. nCr 인 nCr을 사용하여 계산합니다. 여기서 n은 100이고 r은 다른 것입니다 100 번째 행의 항목. 나는 조합을

public static double Combination(int n, int m, double comb) 
    { 
     for (int r = -1; ++r < m;) 
      comb = comb * (n - r)/(r + 1); 
     return comb; 
    } 

를 계산하기 위해 아래의 코드를 사용하고 그러나 그러한 100C16 같은 값에 대해 나는 그것을 진수 전자를 포함한 많은 수를 얻고있다. 인터넷에서 검색 한 결과 실제로 3이 나눌 수없는 12 개의 숫자가 있다는 것을 알았지 만 내 프로그램은 100 번째 행에서 3으로 나눌 수없는 63 개의 숫자를 제공합니다. 어떤 것이 있는지 말해 줄 수는 있습니까? 잘못하고있다.

Answer 1

"nCr"은 n-choose-r의 줄임말이거나 N에서 r을 선택한다고 가정합니다.

nCr이 3으로 나눌 수 있는지 확인하려면 결과를 계산할 필요가 없습니다. 3로 나눌 수 있는지 알아야합니다. 몇 번이나 n 횟수를 확인해야합니다. 3으로 나눌 수 있으며, 몇 번 r! 3로 나눌 수 있고 몇 번이나 (n-r)! 입니다.

정말 간단합니다 - 1! 3, 2로 나눌 수 없다! 그렇지 않아, 3! 한 번 나눌 수있다. 4! 5! 한 번 나눌 수도 있습니다. 6! 두 번 나눌 수 있으며 7도 마찬가지입니다! 및 8! 9! 4 배로 나눌 수 있습니다. 모든 단계를 n까지 진행하십시오 (또는 점진적으로 계산하지 않고 수식을 작성하십시오. 그다지 어렵지는 않습니다). 그리고 확인하십시오.

해설 - 히브리어로 "몇 번이나 n!이 3으로 나눌 수 있습니까?"라는 수학 연구가 적절한 영어 표현 방법이 아닐 수도 있습니다. "n!은 3m 번 나누어 쓸 수 있습니다."라는 말은 n!=3^m*k을 의미하며, 여기서 k는 3으로 나눌 수 없습니다.

편집 : 예. 10c4가 3으로 나눌 수 있는지 봅시다.

몇번이나 k라는 작은 테이블을 만들어 보겠습니다. 3로 나누어 (하세요 divisiblity 열을 계산할 때 K 열이 단지 데모, 당신은 실제로 필요하지 않습니다) :

k  k!  Divisibility 
    1  1  0 
    2  2  0 
    3  6  1 
    4  24  1 
    5  120  1 
    6  720  2 
    7 5040  2 
    8 40320  2 
    9 362880  4 
10 3628800  4 

10C4 10입니다!/(6! * 4!).

10! 4 배로 나눌 수 있습니다 (의미는 10! = 3^4 * 3로 나눌 수없는 것), 6! 2 배 할부입니다 4! 1 회 분배 가능

그래서 10! (6! * 4!)는 3으로 나눌 수 있습니다. 사실 3 * 70입니다.

Answer 2

우선 두 배를 사용하고 있는데, 좋은 생각이라고 생각하지 않습니다. 부동 소수점 숫자는 잠시 후에 오류를 발생시킵니다. 숫자가 거대한 하나는 다음과 같은 방법을 사용할 수 있다는 것을 성장하지 않을 경우

:이 경우

public static long nCr (int m, int n) { 
    long tmp = 1; 
    int j = 2; 
    int k = m-n; 
    for(int i = m; i > k; i--) { 
     tmp *= i; 
     while(j <= n && tmp%j == 0) { 
      tmp /= j++; 
     } 
    } 
    while(j <= n) { 
     tmp /= j++; 
    } 
    return tmp; 
} 

을하지만이 여전히 충분하지 않습니다. 이 경우 하나 devision과 곱셈을 인터리브 할 필요가 없습니다 당신은이 BigInteger 하나 그것을 주장 할 수 System.Numerics

public static BigInteger nCr (int m, int n) { 
     BigInteger tmp = 1; 
     int j = 2; 
     int k = m-n; 
     for(int i = m; i > k; i--) { 
      tmp *= i; 
      while(j <= n && tmp%j == 0) { 
       tmp /= j++; 
      } 
     } 
     while(j <= n) { 
      tmp /= j++; 
     } 
     return tmp; 
    } 

에 BigInteger 구조체를 사용할 수 있습니다. 다만, BigInteger가 꽤 큰 경우, 데이터의 조작에는 (바이트 수의 배열로서 표현되기 (위해) 때문에) 시간이 걸립니다. 그것을 작게 유지하면 오랜 계산 시간을 피할 수 있습니다.