資料結構
網路
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+ 次瀏覽
廣告