알고리즘 학습 17 --- n 의 단계 곱 하기 0 의 개 수 를 계산 합 니 다.

1000 단어 알고리즘
제목: 정수 n 을 정 하면 n 의 곱 하기 n!끝 에 0 이 몇 개 있 을까요?n = 10, n! =362800,n!끝 에 0 이 두 개 있어 요.
n 의 단 계 를 직접 계산 해서 판단 하면 시간 이 걸 릴 뿐만 아니 라 넘 치 는 경우 도 있다.
일단 N! =K * 10 ^ M 및 K 는 10 으로 나 눌 수 없습니다. 그러면 N 을 알 수 있 습 니 다!끝 에 M 개 0 이 있어 요.다시 생각해 봐. N!질 인수 분해 진행, N! =(2 ^ X) * (3 ^ Y) * (5 ^ Z).X > Z 가 보이 지 않 습 니 다. 2 로 나 눌 수 있 는 숫자 가 5 로 나 눌 수 있 는 숫자 보다 많 기 때문에 M = Z 를 얻 을 수 있 습 니 다.
그래서 알고리즘 은 계산 1 - n 의 인수 분해 중 5 의 개수 로 바 뀌 었 다
알고리즘 위조 코드 는 다음 과 같다.
int Factorialn(int num)


for i <- 1 to num
     j=i
     while(j%5 == 0)
          ++count

          j /= 5;

return count;

C + + 구현
int Factorialn(int num)
{
    int j = 0, count = 0;
    //for i <- 1 to num
    for(int i = 1; i <= num; ++i)
    {
        //j=i
        j=i;
        //while(j%5 == 0)
        while(j%5 == 0)
        {
            //++count
            ++count;

            //num/=5
            j /= 5;
        }
    }

    return count;
}

좋은 웹페이지 즐겨찾기