이 문제에서 정수 N이 주어집니다. 우리의 임무는 시리즈 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8의 N번째 항을 찾는 프로그램을 만드는 것입니다. 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) 의 값을 계산할 수 있습니다. - N을 사용하는 1개.
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