이항 전개는 (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+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]은 이항 전개의 항입니다.
들어가세요 -
으아아아출력 -
으아아아이항 확장 공식을 사용하세요.
$$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}$$
이항계수를 재귀적으로 계산하여 각 항의 값을 구할 수 있습니다.
아래 프로그램에서 binomialCoeff() 함수는 r번째 이항 계수의 값을 재귀적으로 계산하는 반면, binomialTerms() 함수는 전개에서 이항 항의 값을 계산합니다.
으아아아시간 복잡도 - O(2^n), 여기서 binomialTerms()의 재귀 트리와 2^n 노드로 인해 binomialCoeff() 함수의 시간 복잡도는 중첩 루프로 인해 O(2^n)입니다. binomialCoeff()를 n+1번 호출하면 함수의 복잡도는 O(n^2)입니다. 따라서 전체 복잡도는 O(2^n)입니다.
공간 복잡도 - 재귀 호출 스택으로 인해 공간 복잡도는 O(n)입니다.
이항 확장 공식을 사용하세요.
$$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개의 함수를 만듭니다.
아래 프로그램에서 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
