数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中O(log n)时间复杂度的复数幂运算程序
给定一个形如x+yi的复数和一个整数n；任务是计算并打印如果我们将复数的n次幂。
什么是复数？
复数是可以写成a + bi形式的数，其中a和b是实数，i是方程的解，或者我们可以说是一个虚数。所以，简单地说，我们可以说复数是实数和虚数的组合。
复数的幂运算
为了计算复数的幂，我们使用下面的公式：
(a+bi) (c+di)=( ac−bd )+(ad+bc )i
例如，我们有一个复数
2+3i，将其5次幂，我们将得到：
(2+3 i)5=(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)时间内解决这个问题。为此，我们可以：
- 首先以数组的形式输入。
- 在Power函数中计算x^n
- 检查n是否为1，如果是，则返回x
- 递归调用power函数，传入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 )
更新于：2019年12月23日
1K+ 次浏览
广告