알고리즘 문제를 위한 기초 수학 알고리즘(펙토리얼,최대공약수,최소공배수,소수 찾기)

알고리즘 문제를 풀다보면 펙토리얼, 최대공약수, 최소공배수, 소수 찾기가 등장합니다. 이때 위 수학 알고리즘을 효율적으로 풀 수 있는 알고리즘을 소개해보도록 하겠습니다.

펙토리얼 펙토리얼의 사전적 정의는 1에서 n까지의 모든 자연수의 곱을 말합니다. 예를 들어 3!

(! = 펙토리얼 기호)는 1 * 2 * 3 = 6이라고 할 수 있습니다.

그러면 이 펙토리얼 문제는 어떻게 효율적으로 해결 할 수 있을까요? 바로 재귀함수로 해결하면 됩니다!

예시 코드를 보겠습니다. //펙토리얼 함수 int Fac(int a) { if (a <= 1) return 1; return a * Fac(a - 1); } int main() { cout << Fac(3); } 6 위 코드는 3!

을 구하는 구하는 코드입니다. 펙토리얼 함수코드 부분을 보시면 재귀함수로 작성되어 있는 것을 알 수 있습니다.

위 함수를 한번 해석을 해보자면 a <= 1때까지 계속 a - 1로 재귀로 호출하여 a가 1이 되거나 이하면 1를...

요청 처리 중입니다...

알고리즘 문제를 위한 기초 수학 알고리즘(펙토리얼,최대공약수,최소공배수,소수 찾기)

등록된 다른 글