ในปัญหานี้เราได้รับจำนวนเต็ม N หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาเทอม N ของชุดที่ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8…
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 7
ผลลัพธ์
4
แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาคือการใช้ลูปเพื่อค้นหาคำศัพท์ที่ตำแหน่งที่ n ข้อกำหนดจะได้รับการอัปเดตโดยเพิ่มเป็นสองเท่าหลังจากการทำซ้ำแต่ละครั้ง และเพิ่มลงในตัวนับระยะ
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int calcNthTerm(int N) {
int termCounter = 0, termValue = 1;
while (termCounter < N) {
termCounter += k;
termValue *= 2;
}
return termValue / 2;
}
int main() {
int N = 10;
cout<<N<<"th term of the series is "<<calcNthTerm(N);
return 0;
} ผลลัพธ์
10th term of the series is 8
แนวทางที่มีประสิทธิภาพ
วิธีที่มีประสิทธิภาพในการแก้ปัญหาคือการหาคำศัพท์ทั่วไปของชุดข้อมูล
Here, are terms and their last index, 1 -> last index = 1. 2 -> last index = 3. 4 -> last index = 7. 8 -> last index = 15. . . T(N) -> last index = 2*(T(N)) - 1 Also, T(N) is always of a power of 2, i.e. T(N) = 2m 2m lies in the series till the index 2m+1-1.
ในการหาคำศัพท์นั้น เราสามารถคำนวณหาค่าของ 2 (m) - 1 ใช้ N.
ทำให้ 2
m
- 1
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา 2m - 1 < N
So, m < log2(N + 1)
ตัวอย่าง
#include <iostream>
#include <math.h>
using namespace std;
int calcNthTerm(int N) {
return ( pow(2, (floor)(log(N + 1) / log(2)) ) ) ;
}
int main() {
int N = 10;
cout<<N<<"th term of the series is "<<calcNthTerm(N);
return 0;
} ผลลัพธ์
10th term of the series is 8
