ในปัญหานี้ เราได้รับจำนวนเต็ม x และ y สองจำนวน งานของเราคือการสร้างฟังก์ชันที่จะเทียบเท่ากับ pow(x,y) โดยใช้วิธีการวนซ้ำซึ่งจะทำให้งานเสร็จสิ้นในเวลาที่ซับซ้อนเป็น 0(Log y)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
x = 7 , y = 3
ผลลัพธ์
343
ฟังก์ชันวนซ้ำสำหรับ pow(x,y) จะวนซ้ำและอัปเดตผลลัพธ์สำหรับค่าคี่ของ y คูณด้วย x และอัปเดต x เป็น x2 ทุกครั้งที่วนซ้ำ
โปรแกรมแสดงการดำเนินการแก้ไข
ตัวอย่าง
#include <iostream>
using namespace std;
void calcPower(int x, unsigned int y) {
int result = 1;
while (y > 0) {
if (y & 1)
result *= x;
y = y >> 1;
x = x * x;
}
cout<<result;
}
int main() {
int x = 7;
unsigned int y = 3;
cout<<x<<" raised to "<<y<<" is ";
calcPower(x,y);
return 0;
} ผลลัพธ์
raised to 3 is 343
