이항 확장 계열을 인쇄하는 프로그램을 작성하세요.

이항 전개는 (a+b)^n 형식의 표현식을 전개하는 데 사용되는 수학 공식입니다. 여기서 n은 양의 정수이고 a와 b는 실수 또는 복소수일 수 있습니다. 전개는 전개의 각 항의 계수를 제공합니다.

이항 전개는 다음과 같이 표현할 수 있습니다.

$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+... + ^nC_ra ^{n-r}b^r+...+ ^nC_na^0b^n}$$

여기서 $mathrm{^nC_r}$는

에 의해 주어진 이항 계수입니다.

$mathrm{^nC_r=frac{n!}{r!times(n−r)!}}$, 여기서 n! n의 계승을 나타냅니다

전개는 위 공식을 사용하여 모든 이항항을 계산하고 이를 전개 방정식에 대입하는 데 사용할 수 있습니다.

문제 설명

세 개의 정수 a, b, n이 주어졌습니다. (a+b)^n의 이항 전개 항을 구합니다.

예제 1

들어가세요 -

으아아아

출력 -

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

이항 전개(1+2)^3은 다음과 같습니다

$mathrm{(1+2)^3 = C(3,0)a^3b^0 + C(3,1)a^2b^1 + C(3,2)a^1b^2 + C( 3,3)a^0b^3}$

= 1*1*1 + 3*1*2 + 3*1*4 + 1*1*8

따라서 [1, 6, 12, 8]은 이항 전개의 항입니다.

예시 2

들어가세요 -

으아아아

출력 -

으아아아

방법 1: 재귀 이항 확장

이항 확장 공식을 사용하세요.

$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+... + ^nC_ra ^{n-r}b^r+...+ ^nC_na^0b^n}$$

이항계수를 재귀적으로 계산하여 각 항의 값을 구할 수 있습니다.

의사코드

으아아아

예: C++ 구현

아래 프로그램에서 binomialCoeff() 함수는 r번째 이항 계수의 값을 재귀적으로 계산하는 반면, binomialTerms() 함수는 전개에서 이항 항의 값을 계산합니다.

으아아아

출력

으아아아

시간 복잡도 - O(2^n), 여기서 binomialTerms()의 재귀 트리와 2^n 노드로 인해 binomialCoeff() 함수의 시간 복잡도는 중첩 루프로 인해 O(2^n)입니다. binomialCoeff()를 n+1번 호출하면 함수의 복잡도는 O(n^2)입니다. 따라서 전체 복잡도는 O(2^n)입니다.

공간 복잡도 - 재귀 호출 스택으로 인해 공간 복잡도는 O(n)입니다.

방법 2: 반복 이항 확장

이항 확장 공식을 사용하세요.

$$mathrm{(a+b)^n= ^nC_0a^nb^0+ ^nC_1a^{n-1}b^1 + ^nCa^{n-2}b^2+... + ^nC_ra ^{n-r}b^r+...+ ^nC_na^0b^n}$$

반복과 나눗셈을 결합하여 이 확장의 각 항의 값을 찾을 수 있습니다.

첫 번째 함수는 이항 계수를 계산하고 두 번째 함수는 a와 b의 거듭제곱을 곱하여 원하는 이항 항을 얻는 2개의 함수를 만듭니다.

의사코드

으아아아

예: C++ 구현

아래 프로그램에서 binomialCoeff() 함수는 r번째 이항 계수를 계산하는 반면, binomialTerms() 함수는 a, b 및 n이 주어진 이항 전개의 모든 항을 계산합니다.

으아아아

출력

으아아아

Time Complexity - O(n^2) 여기서 binomialCoeff() 함수의 시간 복잡도는 O(r)입니다. 여기서 r은 r과 n-r의 더 작은 수이고 binomialTerms() 함수는 중첩 루프로 인해 호출됩니다. binomialCoeff() n +1번이면 복잡도는 O(n^2)입니다. 따라서 전체 복잡도는 O(n^2)입니다.

Space Complexity - 벡터가 이항 항을 저장하므로 O(n)입니다.

결론

요약하자면, 이항 확장의 이항 항을 찾으려면 위에서 언급한 두 가지 방법 중 하나를 사용할 수 있습니다. 시간 복잡도 범위는 O(2^n)에서 O(n^2)이며, 여기서 반복 방법이 더 좋습니다. 재귀적 방법보다 더 최적화되었습니다.

위 내용은 이항 확장 계열을 인쇄하는 프로그램을 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!