หาพจน์ที่ N ของอนุกรม 1, 2, 2, 4, 4, 4, 4, 8... ด้วย C++

ภาพรวมปัญหา

หาพจน์ที่ N ของอนุกรม: 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, ...

รูปแบบ: เลข 2ᵏ ปรากฏ 2ᵏ ครั้ง

ตัวอย่าง

อินพุต

N = 7

เอาต์พุต

4

วิธีแก้ปัญหา

วิธีที่ 1: Simulation - O(N)

นับจำนวนพจน์จนถึง N

วิธีที่ 2: สูตรทางคณิตศาสตร์ - O(1) ⭐

ตำแหน่งสุดท้ายของค่า 2ᵏ คือ 2ᵏ⁺¹ - 1

หา k ที่ทำให้ 2ᵏ - 1 < N ≤ 2ᵏ⁺¹ - 1

k = ⌊log₂(N + 1)⌋

คำตอบ = 2ᵏ

โค้ดตัวอย่าง (สูตร O(1))

#include <iostream>
#include <cmath>
using namespace std;

int calcNthTerm(int N) {
    int k = floor(log2(N + 1));
    return (1 << k);  // 2^k
}

int main() {
    int N = 10;
    cout << N << "th term of the series is " << calcNthTerm(N);
    return 0;
}

เอาต์พุต

10th term of the series is 8

สรุป

ใช้ลอการิทึมฐาน 2 หาเลขชี้กำลัง เร็วที่สุด O(1)