Quadrato creativo

Dato n, numero intero positivo, il suo quadrato é uguale alla somma dei primi n numeri dispari.

Usare questa curiosa proprietà per calcolare il quadrato dei primi dieci interi positivi.

In pratica dobbiamo sommare i primi n elementi della progressione aritmetica di ragione 2 con primo termine 1.
Qualcosa come 1 + 3 + 5 + 7 + 9 + ....

Questa l'implementazione che mi é venuta naturale:

    for (int i = 1; i < 11; ++i) {
        int sum = 1;
        for (int j = 1; j < i; ++j) {
            sum += (j*2)+1;
        }

        cout << sum << ' ';
    }
    cout << endl;

L'idea é che il ciclo for esterno reinizializza la sommatoria a 1, il primo elemento della successione, e poi aggiunge gli elementi successivi che possono essere calcolati in funzione dell'indice j in modo immediato. Il primo elemento, 3, é infatti pensabile come 2 + 1, il secondo 2*2 + 1, il terzo 3*2 + 1, eccetera.

Ma, a pensarci un attimo, l'uso del doppio loop for é ridondante. Dopotutto per calcolare il risultato per n basta appoggiarsi a quello per n-1.

Il che porta a questa implementazione:

    vector<int> results;

    results.push_back(1);
    for (int i = 1; i < 10; ++i) {
        results.push_back(results[i-1] + (i*2)+1);
    }

    vector<int>::const_iterator it = results.begin();
    while(it != results.end())
        cout << *it++ << ' ';
    cout << endl;

Il primo elemento é uno, lo mettiamo nel vettore dei risultati. Gli altri li calcoliamo aggiungendo al precedente elemento il successivo numero dispari.

A pensarci meglio, però, nel caso generale l'uso di vector non é che sia una idea geniale. Nel caso corrente non ci sono problemi, dato che sappiamo il nostro vector non cresce più di tanto, ma se pensiamo ad un caso in cui si vogliano trovare i quadrati per centinaia, migliaia o anche più interi conviene usare deque.

Ecco qui la mia implementazione in questo caso:

    deque<int> d;

    d.push_back(1);
    for (int i = 1; i < 10; ++i) {
        d.push_back(d.back() + (i*2)+1);
    }

    deque<int>::const_iterator it = d.begin();
    while(it != d.end())
        cout << *it++ << ' ';
    cout << endl;