C++ 시리즈에서 n번째 항을 찾는 프로그램 1 2 2 3 3 3 4

이 문제에서 정수 N이 주어집니다. 작업은 시리즈 1 2 2 3 3 3 4…에서 n번째 항을 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 6

출력

3

설명

n번째 항까지의 급수는 1, 2, 2, 3, 3, 3, ...

솔루션 접근 방식

문제를 해결하는 간단한 방법은 중첩 루프를 사용하는 것입니다. 외부 for 루프는 1에서 n까지입니다. 그리고 내부 루프는 1에서 i까지입니다(외부 루프의 반복자). 내부 루프의 각 반복에 대해 시리즈의 요소 수를 세고 count가 n과 같을 때 i 값을 반환합니다.

문제를 해결하기 위한 보다 효율적인 접근 방식은 패턴 위치를 사용하는 것입니다. 시퀀스의 요소는 시리즈의 위치와 함께 -

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 ² - x => x ² - x - 2n =0

2차 방정식의 해에 대한 공식을 사용하여 방정식을 풉니다.

$$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