팩토리얼 (Factorial)

참고

https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9

계승 - 위키백과, 우리 모두의 백과사전

정의

• N! = 1*2*...*N

팩토리얼을 구하는 방법

1) 반복문을 통해 하나하나 곱하는 방법

long result = 1;

if(N <= 1) {
    return 1;
} else {
    for (int i=1; i<=N; i++) {
	    result *= i;
    }
    
    return result;
}

2) 재귀함수를 이용하는 방법

public long factorial(int number) {
    if(number <= 1) {
        return 1;
    } else {
        return factorial(number-1) * number;
    }
}

팩토리얼의 0의 개수?

• 100! 팩토리얼의 경우 인수가 5인 수는 20개 => N/5

• 25, 50, 75, 100은 인수 5가 두개씩 존재한다. (5*5*1, 5*5*2, 5*5*3, 5*5*4) => N/25

• 결국, 5의 제곱수로 N을 나눈 몫을 더해주면 0의 개수를 구할 수 있을 것이다.

조합 0의 개수?

조합을 계산하는 공식

• 지수의 곱셈은 각 지수를 더하여 계산하고, 지수의 나눗셈은 각 지수를 빼면 된다.

• 조합을 계산하는 공식에 의해 아래와 같이 계산하면 될 것이다.

  1. 5!의 2와 5의 개수를 각각 센다.

  2. 3! = (5-2)!의 2와 5의 개수를 가각 센 뒤 뺀다.

  3. 2!의 2와 5의 개수를 각각 센 뒤 뺀다.

  4. 2의 갯수, 5의 갯수 중 적은 수가 0의 개수이다.