C++의 O(log n) 복소수의 거듭제곱 프로그램

<시간/>

x+yi 형식의 복소수와 정수 n이 주어집니다. 작업은 복소수에 n을 제곱하면 복소수의 값을 계산하고 인쇄하는 것입니다.

복소수란 무엇입니까?

복소수는 + bi의 형태로 쓸 수 있는 숫자입니다. 여기서 및 b는 실수이고 i는 방정식의 해이거나 허수라고 할 수 있습니다. 따라서 복소수는 실수와 허수의 조합이라고 간단히 말할 수 있습니다.

복소수의 거듭제곱

복소수의 거듭제곱을 높이려면 아래 공식을 사용합니다 -

(a+bi) (c+di)=( ac−bd )+(ad+bc )i

복소수가 있는 것처럼

2+3i 및 5만큼 전력을 올리면 우리는 -

를 얻습니다.

(2+3 i)⁵ =(2+3 i)(2+3i)(2+3 i)(2+3 i)(2+3i)

위의 공식을 사용하여 답을 얻을 수 있습니다 -

예시

Input: x[0] = 10, x[1] = 11 /*Where x[0] is the first real number and 11 is the
second real number*/
n = 4
Output: -47959 + i(9240)
Input: x[0] = 2, x[1] =3
n = 5
Output: 122 + i(597)

위의 문제를 해결하기 위해 사용하는 접근 방식 -

따라서 반복적인 방법을 사용하면 문제를 쉽게 풀 수 있지만 복잡도는 O(n)이 되지만 O(log n) 시간에 문제를 해결해야 합니다. 이를 위해 우리는 -

먼저 배열 형식으로 입력을 받습니다.
기능 전원 x^n
- n이 1인지 확인한 다음 x를 반환합니다.
- 재귀적으로 power pass x 및 n/2를 호출하고 그 결과를 변수 sq에 저장합니다.
- n을 2로 나누면 나머지가 0인지 확인합니다. 그렇다면 cmul(sq, sq)
- n을 2로 나누면 나머지가 0이 되지 않는지 확인합니다. 그렇다면 cmul(x, cmul(sq, sq))에서 얻은 결과를 반환합니다.
함수 cmul().
- x1 =a+bi 및 x2 =x+di이면 x1 * x2 =(a*c–b*d)+(b*c+d*a)i인지 확인합니다.
얻은 결과를 반환하고 인쇄하십시오.

알고리즘

Start
Step 1-> declare function to calculate the product of two complex numbers
   long long* complex(long long* part1, long long* part2)
   Declare long long* ans = new long long[2]
   Set ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1])
   Se ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1]
   return ans
Step 2-> declare function to return the complex number raised to the power n
   long long* power(long long* x, long long n)
   Declare long long* temp = new long long[2]
   IF n = 0
      Set temp[0] = 0
      Set temp[1] = 0
      return temp
   End
   IF n = 1
      return x
   End
   Declare long long* part = power(x, n / 2)
   IF n % 2 = 0
      return complex(part, part)
   End
   return complex(x, complex(part, part))
Step 3 -> In main()
   Declare int n
   Declare and set long long* x = new long long[2]
   Set x[0] = 10
   Set x[1] = -11
   Set n = 4
   Call long long* a = power(x, n)
Stop

예시

#include <bits/stdc++.h>
using namespace std;
//calculate product of two complex numbers
long long* complex(long long* part1, long long* part2) {
   long long* ans = new long long[2];
   ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]);
   ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1];
   return ans;
}
// Function to return the complex number raised to the power n
long long* power(long long* x, long long n) {
   long long* temp = new long long[2];
   if (n == 0) {
      temp[0] = 0;
      temp[1] = 0;
      return temp;
   }
   if (n == 1)
      return x;
      long long* part = power(x, n / 2);
      if (n % 2 == 0)
         return complex(part, part);
         return complex(x, complex(part, part));
}
int main() {
   int n;
   long long* x = new long long[2];
   x[0] = 10;
   x[1] = -11;
   n = 4;
   long long* a = power(x, n);
   cout << a[0] << " + i ( " << a[1] << " )" << endl;
   return 0;
}

출력

power of complex number in O(Log n) : -47959 + i ( 9240 )