ในปัญหานี้ เราได้รับจำนวนเต็ม N ภารกิจคือการหาเทอมที่ n ในอนุกรม 1 2 2 3 3 3 4….
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 6
ผลลัพธ์
3
คำอธิบาย
อนุกรมที่ไม่เกินเทอมที่ n คือ 1, 2, 2, 3, 3, 3, ...
แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาคือการใช้การวนซ้ำซ้อน วงนอกสำหรับลูปคือตั้งแต่ 1 ถึง n และวงในคือตั้งแต่ 1 ถึง i (ตัววนซ้ำของวงนอก) สำหรับการวนซ้ำแต่ละครั้งในวงใน ให้นับจำนวนขององค์ประกอบของชุดข้อมูลและคืนค่าของ i เมื่อการนับเท่ากับ n
วิธีที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหาคือการใช้ตำแหน่งรูปแบบ องค์ประกอบของซีเควนซ์มีตำแหน่งอยู่ในอนุกรมคือ −
Element 1: position 1 Element 2: position 2, 3 Element 3: position 4, 5, 6 Element 4: position 7, 8, 9, 10
สำหรับค่าเหล่านี้ เราสามารถสร้างชุดข้อมูลโดยใช้ตำแหน่งสุดท้ายขององค์ประกอบในชุดข้อมูลคือ
1, 3, 6, 10, 15, 21, 28, ….
x ปรากฏในระยะ 1 + 2 + 3 + … + (x-2) + (x-1)...
ซึ่งสามารถสรุปได้เป็น n =x*(x-1)/2
2n =x 2 - x => x 2 - x - 2n =0
แก้สมการโดยใช้สูตรหาคำตอบของสมการกำลังสอง
$$x=1/2*(1+\sqrt{1+8*n)}$$
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
int x = (((1) + (double)sqrt(1 + (8 * n))) / 2);
return x;
}
int main(){
int n = 12;
cout<<"The series is 1, 2, 2, 3, 3, 3, 4, 4, ...\n";
cout<<n<<"th term of the series is "<<findNthTerm(n);
return 0;
} ผลลัพธ์
The series is 1, 2, 2, 3, 3, 3, 4, 4, ... 12th term of the series is 5
