แนวคิด
สมมติ bn เป็นลำดับตัวเลข ที่แสดงด้วยความสัมพันธ์เวียนเกิด (recurrence relation) b₁ = 1 และ bₙ₊₁/bₙ = 2ⁿ ภารกิจคือหาค่า log₂(bₙ) สำหรับ n ที่กำหนด
อินพุต
6
เอาต์พุต
15
คำอธิบาย
log₂(bₙ) = (n * (n - 1)) / 2 = (6*(6-1))/2 = 15
อินพุต
200
เอาต์พุต
19900
วิธีการ
bₙ₊₁/bₙ = 2ⁿ bₙ/bₙ₋₁ = 2ⁿ⁻¹ ... b₂/b₁ = 2¹ คูณทุกสมการ: (bₙ₊₁/bₙ)(bₙ/bₙ₋₁)...(b₂/b₁) = 2ⁿ⁺⁽ⁿ⁻¹⁾⁺...⁺¹ bₙ₊₁/b₁ = 2ⁿ⁽ⁿ⁺¹⁾/₂ เนื่องจาก 1+2+...+n = n(n+1)/2 และ b₁ = 1 bₙ₊₁ = 2ⁿ⁽ⁿ⁺¹⁾/₂ แทน n+1 ด้วย n: bₙ = 2ⁿ⁽ⁿ⁻¹⁾/₂ หา log ทั้งสองข้าง: log₂(bₙ) = n(n-1)/2
ตัวอย่างโค้ด
// C++ program to find nth term of
// a given recurrence relation
#include <bits/stdc++.h>
using namespace std;
// ฟังก์ชันคืนค่าที่ต้องการ
int sum(int n1) {
int ans1 = (n1 * (n1 - 1)) / 2;
return ans1;
}
int main() {
int n = 200;
cout << sum(n);
return 0;
}
ผลลัพธ์
19900
