Aprendre a programar 5 - tractament seqüèncial

Una cosa molt important és no ocupar més memòria de la necessària quan programem. Quan volem calcular una cosa sobre una sèrie de dades, no hem de desar-les totes si no és necessari. Això és el tractament seqüencial, anar tractant les dades a mida que entren. Per exemple, suposem que volem calcular el màxim d'una sèrie de números que ens entraran. Una opció seria utilitzar un vector per desar-los allà, i més tard buscar quin és l'element més gran. Però això implicaria desar n elements, i recórrer tots aquests el doble del necessari. En canvi, un tractament seqüencial seria una cosa així:

int maxim;
cin >>maxim;
int n;
while (cin >>n) {
    if (n>maxim) maxim=n;
}
cout <<maxim<<endl;

Només hem necessitat dues variables, una pel màxim provisional, i una altra pel número que llegim en cada moment. Bastant menys que si ho llegíssim prèviament

Un altre exemple. Imaginem que volem un programa que llegeixi una posició n, i una sèrie de números, i digui quin hi ha a la posició n (molt similar al problema P39225). El que podríem fer és:

int main () {
    int n;
    cin >>n;
    int num;
    for (int i=0;i<n;++i) {
        cin >>num;
    }
    cout <<num<<endl;
}

Algú podria pensar "Ei, però no estàs llegint tots els números". Exacte, això és molt important. La gràcia del tractament seqüencial és que, si ja podem saber el resultat amb les dades que tenim, no cal seguir. No cal llegir tots els números que entren, si ja sabem quin està a la posició n. 

Un altre exemple seria el problema P36430. Aquest ens explica que Fermat (el troll matemàtic *) va demostrar que x^n+y^n=z^n no tenia solució natural per n>2 (excepte amb x=y=z=0). No obstant, pel cas 2 hi ha diverses solucions, i el problema ens demana buscar-ne una. 

Concretament ens dóna 4 números, a, b, c i d, i ens demana trobar la solució mínima tal que x estigui entre a i b, i y entre c i d. 

int pot2(int a) {

    return a*a;

}

void fermat(int a, int b, int c, int d) {

    for (int i=a;i<=b;++i) {

        for (int j=c;j<=d;++j) {

            int aux1=pot2(i)+pot2(j);

            int aux2=sqrt(aux1);

            if (aux2*aux2==aux1) {

                cout <<i<<"^2 + "<<j<<"^2 = "<<aux2<<"^2"<<endl;

                return;

            }

        }

    }

    cout <<"Sense solucio!"<<endl;

}

A aquest problema li podríem dir "prova i error". El que fa és anar provant, fins que troba el resultat. En el moment que el troba, fa el return, de manera que no segueix provant

* Fermat és el troll matemàtic per excel·lència. L'Últim Teorema de Fermat no es diu així perquè fos l'últim que va fer, ja que això no se sap. Es diu així perquè va ser l'últim que es va publicar, ja que, de fet, el van publicar amb ell ja mort. Va aparèixer escrit, en el marge d'un llibre seu, juntament amb la frase "He descobert una demostració veritablement meravellosa d'aquesta proposició, però aquest marge és massa estret perquè hi càpiga". Fermat va morir al 1665, i fins al 1995 no es va demostrar que la (fins a aquell moment) Conjectura de Fermat era correcta. 330 anys per demostrar el teorema

Per altra banda, jo no els trobo gaire gràcia a aquests problemes. L'únic que cal tenir en compte és que, si trobes la solució, acabar. De fet, suposo que veient quants enviaments tinc en aquesta llista, es pot notar com d'interessants em semblen

Així que podem passar ràpid al següent article, on parlo d'emmagatzematge massiu de dades