Termenii șirului dintr-un interval

Explicarea metodei de rezolvare

Formula termenului general

Șirul este definit prin recurență, dar din recurență se obține o formulă directă. Fiecare termen este suma dintre termenul precedent și dublul poziției lui, deci termenul de pe poziția n este:

fₙ = f₀ + 2·1 + 2·2 + … + 2·n = 1 + 2·(1 + 2 + … + n) = 1 + 2 · n(n+1)/2 = n² + n + 1.

Formula se verifică pe termenii dați în enunț:

Formula este esențială pentru eficiență: ea permite calcularea oricărui termen dintr-o singură operație, fără parcurgerea termenilor dinaintea lui.

Determinarea pozițiilor

Șirul este strict crescător, fiindcă fₙ − fₙ₋₁ = 2n > 0 pentru n ≥ 1. Rezultă că termenii din intervalul [x, y] ocupă poziții consecutive în șir. Este de ajuns să fie determinate poziția primului și poziția ultimului dintre ei.

Poziția unui termen v se obține din ecuația n² + n + 1 = v, adică n² + n − (v − 1) = 0, a cărei soluție pozitivă este n = (−1 + √(4v − 3)) / 2. Valoarea se calculează cu funcția sqrt, apoi se corectează prin cel mult o deplasare cu o poziție în sus sau în jos, pentru ca eventuala eroare de rotunjire a calculului în virgulă mobilă să nu ducă la un rezultat greșit.

Se determină astfel:

• ix, cea mai mică poziție pentru care termenul este mai mare sau egal cu x;
• iy, cea mai mare poziție pentru care termenul este mai mic sau egal cu y.

Scrierea în ordine inversă

Enunțul cere termenii în ordine inversă a apariției lor în șir, adică în ordine descrescătoare. Termenii nu se memorează: pozițiile se parcurg de la iy până la ix, în ordine descrescătoare, iar la fiecare pas se calculează direct termenul n² + n + 1 și se scrie în fișier.

Programul

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

/* Termenul de pe pozitia i: f(i) = i*i + i + 1. */
long long f(long long i) {
    return i * i + i + 1;
}

/* Cea mai mica pozitie i pentru care f(i) >= v. */
long long primaPozitie(long long v) {
    long long i = (long long)((sqrt(4.0 * v - 3.0) - 1) / 2);
    if (i < 0)
        i = 0;
    while (f(i) < v)
        i++;
    while (i > 0 && f(i - 1) >= v)
        i--;
    return i;
}

/* Cea mai mare pozitie i pentru care f(i) <= v. */
long long ultimaPozitie(long long v) {
    long long i = (long long)((sqrt(4.0 * v - 3.0) - 1) / 2);
    if (i < 0)
        i = 0;
    while (f(i) > v)
        i--;
    while (f(i + 1) <= v)
        i++;
    return i;
}

int main() {
    long long x, y;
    cin >> x >> y;

    ofstream g("titu2022.out");

    long long ix = primaPozitie(x);
    long long iy = ultimaPozitie(y);

    for (long long i = iy; i >= ix; i--)
        g << f(i) << " ";

    g.close();

    return 0;
}