PHP에서 n의 계승을 구현하는 방법

PHP에서 n의 계승을 구현하는 방법: 1. "functionfact(int $n): int{...}"와 같은 코드를 사용하여 일반 재귀를 통해 구현합니다. 2. 다음과 같은 일반 루프를 사용하여 구현합니다. "while ($num

이 문서의 운영 환경: Windows 10 시스템, PHP 버전 7.2.15, DELL G3 컴퓨터

PHP에서 n의 계승을 구현하는 방법은 무엇입니까?

내가 아는 한 구현은 계승의 방법은 일반적으로 세 가지 유형으로 나눌 수 있는데, 일반적으로 재귀와 반복은 각각 하나의 유형으로 간주되며, 연산 수(특히 곱셈 수를 줄이기 위해 몇 가지 영리한 수학적 방법을 사용하는 큰 범주도 있습니다. 연산)을 통해 계산 효율성을 최적화합니다.

고정밀, 큰 정수의 계승을 고려하려는 경우 PHP 언어의 경우 상황이 더 복잡해집니다. 예를 들어 BCMath 확장에서 제공하는 일부 메서드를 사용할 때 명시적인 숫자 및 문자열 변환 작업이 더 자주 발생합니다. .

이 글은 n만을 정수로 고려할 때 위의 상황을 구현하려고 시도합니다. 각 경우에 사용 가능한 코드 예제가 제공되며, 글 끝에 여러 방법에 대한 포괄적인 비교가 첨부되어 있습니다.

일반 재귀 구현

첫 번째는 일반 재귀 구현입니다. 재귀 사실(n) = n * 사실(n-1)의 일반 공식에 따르면 계승 계산 코드를 작성하는 것은 쉽습니다. 일반적인 재귀적 구현의 장점은 코드가 상대적으로 간결하고, 일반 수식과 동일한 프로세스로 코드를 이해하기 쉽다는 점입니다. 단점은 자신을 자주 호출해야 하기 때문에 많은 수의 push 및 pop 작업이 필요하고 전체적인 계산 효율성이 높지 않다는 것입니다(문서 끝의 표 참조).

function fact(int $n): int
{
    if ($n == 0) {
        return 1;
    }
    return $n * fact($n - 1);
}

일반 루프 구현

일반 루프 구현에는 약간의 "동적 프로그래밍" 성향이 있지만 중간 상태 변수는 덜 자주 사용되고 추가 저장 공간이 필요하지 않기 때문에 일반 동적 프로그래밍 알고리즘보다 간단합니다. 일반적인 재귀 방법은 하향식(n에서 1까지) 계산 프로세스인 반면 일반 루프는 상향식 계산입니다.

그래서 상대적으로 말하면 위의 방법만큼 코드가 직관적이지는 않지만, 푸시 및 팝 프로세스가 덜 빈번하기 때문에 계산 효율이 더 높아질 것입니다(글 끝의 표 참조).

function fact(int $n): int
{
    $result = 1;
    $num = 1;
    while ($num <= $n) {
        $result = $result * $num;
        $num = $num + 1;
    }
    return $result;
}

자체 구현된 큰 정수 계승

PHP의 int 유형의 범위 제한으로 인해 위의 두 가지 방법은 최대 20까지만 계승을 정확하게 계산할 수 있습니다. 20의 팩토리얼만 고려한다면 0~20의 팩토리얼을 미리 계산해서 배열에 저장하고 필요할 때 한 번씩 쿼리하는 조회 테이블 방식을 사용하는 것이 더 빠를 것입니다.

큰 수의 계승에 적응하고 정확한 계산 결과를 얻을 수 있도록 이 문서는 계산 결과의 각 비트를 배열을 사용하여 저장하는 "일반 루프 방법"을 기반으로 개선되었습니다(낮은 것부터 높은 것까지). ), 곱하고 순서대로 전달하여 각 자릿수에 대한 결과를 계산합니다.

이 방법의 장점은 고정밀 대수 계승 상황에 적용할 수 있다는 점은 말할 필요도 없습니다. 단점은 소수 계승의 경우 계산 과정이 복잡하고 느리다는 것입니다.

function fact(int $n): array
{
    $result = [1];
    $num = 1;
    while ($num <= $n) {
        $carry = 0;
        for ($index = 0; $index < count($result); $index++) {
            $tmp = $result[$index] * $num + $carry;
            $result[$index] = $tmp % 10;
            $carry = floor($tmp / 10);
        }
        while ($carry > 0) {
            $result[] = $carry % 10;
            $carry = floor($carry / 10);
        }
        $num = $num + 1;
    }
    return $result;
}

BCMath 확장 방법

BCMath는 문자열로 표현되는 숫자(크기 및 정밀도와 상관없이)의 수치 계산을 처리하는 PHP용 수학적 확장입니다. C 언어로 구현한 확장이므로 위의 자체 구현보다 계산 속도가 더 빠릅니다.

추천 학습: "PHP Video Tutorial"

노트북에서 2000의 팩토리얼도 계산합니다. 자체 구현에는 평균 0.5~0.6초가 걸리며, BCMath를 사용하면 0.18~0.19초가 걸립니다. 이 방법의 가장 큰 단점은 해당 확장을 설치해야 한다는 점이며, 이는 비코드 수준 변경이므로 환경 관리 업그레이드가 불편한 애플리케이션의 경우 실용성이 의심됩니다.

function fact(int $n): string
{
    $result = '1';
    $num = '1';
    while ($num <= $n) {
        $result = bcmul($result, $num);
        $num = bcadd($num, &#39;1&#39;);
    }
    return $result;
}

최적화 알고리즘

이 글의 시작 부분에서 언급했듯이 최적화 알고리즘은 빠른 계승을 달성하기 위해 연산 수(특히 곱셈 연산 수)를 최대한 줄이려고 합니다. 작은 정수 계승의 경우 가장 빠른 알고리즘은 시간 복잡도가 O(1)인 테이블 조회 방법이어야 하므로 이 섹션에서는 주로 큰 정수의 정확한 계승을 논의하고 테스트합니다.

현재 n! = C(n, n/2) * (n/2) * (n/2)을 통해 계승 최적화가 더 일반적이라는 것을 알 수 있습니다. 공식 하이라이트는 주로 C(n, n/2)의 최적화입니다. 큰 정수의 경우 C(n, n/2)를 구현하는 PHP 언어의 효율성이 높지 않고, 코드 가독성이 상대적으로 좋지 않다는 점(숫자와 문자열의 명시적 변환이 빈번함)을 고려하여 이 기사에서는 다음을 사용합니다. 또 다른 더 영리한 방법입니다.

곱셈의 계산 속도는 일반적으로 덧셈과 뺄셈의 계산 속도보다 느립니다. 곱셈 연산 횟수를 줄이면 전체 계산 속도가 향상될 수 있습니다. 수학적 귀납법을 통해 n의 계승에 대해 (n/2)^2보다 작은 1, 1+3, 1+3+5... 값을 연속적으로 찾은 다음 곱할 수 있음을 알 수 있습니다. 목표값을 얻기 위해 순서대로 진행합니다.

이 알고리즘의 장점은 계산 속도가 빠르다는 것이지만, 구현 과정이 직관적이지 않고 이해하기 어렵다는 단점이 있습니다. 테스트 후, 다음 코드는 2000~0.11초의 계승 평균 시간을 계산하는데, 이는 일반 루프 방법 시간의 약 절반입니다.

이 최적화 방법 외에도 1...n의 숫자가 2로 나누어지는지 반복적으로 확인하고, 2x로 나누어지는 횟수를 기록하고, 요약하려고 하는 등 다른 유사한 아이디어도 보았습니다. 일반적인 홀수 공식을 곱하고 마지막으로 2^x를 곱하여 결과를 얻습니다.

function fact(int $n): string
{
    $middleSquare = pow(floor($n / 2), 2);
    $result = $n & 1 == 1 ? 2 * $middleSquare * $n : 2 * $middleSquare;
    $result = (string)$result;
    for ($num = 1; $num < $n - 2; $num = $num + 2) {
        $middleSquare = $middleSquare - $num;
        $result = bcmul($result, (string)$middleSquare);
    }
    return $result;
}

综合对比

本文中提到的方法是按照由劣到优的顺序，因此，下列表格中每一行中提到优劣势，主要是和其上一两种方法对比。

表格中「测试耗时」一列的测试环境为个人笔记本，硬件配置为 Dell/i5-8250U/16GB RAM/256GB SSD Disk，软件配置为 Win 10/PHP 7.2.15。

总结

虽然本文将实现方法分为三大类，但其实也可以分为循环和递归两大类，在这两类中分别使用相应的算法优化计算效率。But，总体而言，循环的效率要优于递归。

讲道理，本文中使用的优化算法并不是最优解，只是用 PHP 相对好实现，代码易读性也比较高。有兴趣的读者可以谷歌了解更多的骚操作。

위 내용은 PHP에서 n의 계승을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!