알고리즘 - n 의 연속 정수 시퀀스 (C + +)
1420 단어 Algorithm
/*
* n - C++ - by Chimomo
*
* ： n， n 。 ： 15， 1+2+3+4+5=4+5+6=7+8=15， 3 1-5、4-6 7-8。
*
* Answer:
*
* Suppose n = i+(i+1)+...+(j-1)+j,
* then n = (i+j)(j-i+1)/2 = (j*j-i*i+i+j)/2
* => j^2+j+(i-i^2-2n) = 0
* => j = (sqrt(1-4(i-i^2-2n))-1)/2
* => j = (sqrt(4i^2+8n-4i+1)-1)/2.
*
* We know 1 <= i < j <= n/2+1, so for each i in [1,n/2], do this arithmetic to check if there is a integer answer.
*
* Note: ax^2+bx+c=0 ： x = (-b±sqrt(b^2-4ac))/2a。
*/
#include
#include
#include
#include
using namespace std;
int FindConsecutiveSequence(int n) {
int count = 0;
for (int i = 1; i <= n / 2; i++) {
double sqroot = sqrt(4 * i * i + 8 * n - 4 * i + 1);
int floor = sqroot;
if (sqroot == floor) {
cout << i << "-" << (sqroot - 1) / 2 << endl;
count++;
}
}
return count;
}
int main() {
int count = FindConsecutiveSequence(15);
cout << "Totally " << count << " sequences found." << endl;
return 0;
}
// Output:
/*
1-5
4-6
7-8
Totally 3 sequences found.
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
