โปรแกรมหากำลังของจำนวนเชิงซ้อนใน O(log n) ใน C++

กำหนดจำนวนเชิงซ้อนในรูปของ x+yi และจำนวนเต็ม n งานคือการคำนวณและพิมพ์ค่าของจำนวนเชิงซ้อนถ้าเรายกกำลังจำนวนเชิงซ้อนด้วย n

จำนวนเชิงซ้อนคืออะไร

จำนวนเชิงซ้อนคือจำนวนที่สามารถเขียนได้ในรูปของ a + bi โดยที่ a และ b เป็นจำนวนจริง และ i คือคำตอบของสมการหรือเราสามารถบอกได้ว่าจำนวนจินตภาพ พูดง่ายๆ ก็คือ จำนวนเชิงซ้อนคือผลรวมของจำนวนจริงกับจำนวนจินตภาพ

การเพิ่มกำลังของจำนวนเชิงซ้อน

ในการยกกำลังของจำนวนเชิงซ้อนเราใช้สูตรด้านล่าง −

(a+bi) (c+di)=( ac−bd )+(ad+bc )ฉัน

เหมือนเรามีจำนวนเชิงซ้อน

2+3i และเพิ่มพลังขึ้น 5 เราจะได้ –

(2+3 i) ⁵ =(2+3 ผม)(2+3i)(2+3 ผม)(2+3 ผม)(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 )