알고리즘 - n 의 연속 정수 시퀀스 (C + +)

큰 소의 인공지능 튜 토리 얼 을 공유 하 다.제로 베이스!통속 적 이 고 알 기 쉽다!유머당신 도 인공지능 팀 에 합류 하 기 를 바 랍 니 다!클릭 하 세 요http://www.captainbed.net 

/*
 *    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.

*/