Enrere Mòdul 4
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació Annex: la depuració

 
La suma dels naturals

En aquesta pràctica farem un programa per calcular la suma dels n  primers nombres de tres formes diferents:

  • Fent explícitament les n-1 sumes.
  • Aplicant la fórmula de la suma dels n primers termes d'una progressió aritmètica.
  • Mitjançant un algoritme recursiu.
 
Desenvolupament de la pràctica

És sabut que la suma dels n primers nombres naturals es pot obtenir mitjançant la fórmula:

 

Per exemple, 1+2+3+4+5+6+7+8+9+10=10·(1+10)/2 = 55

La suma dels n primers nombres naturals també es pot fer mitjançant una funció recursiva, ja que:  Sn = n+Sn-1. El problema de les funcions recursives és que es pot omplir la pila interna i el programa no funcionarà bé per nombres grans. En el programa que es presenta a continuació es calcularà la suma dels n primers nombres enters, essent n un nombre enter entrat pel teclat. Aquesta suma es farà pels dos mètodes abans esmentats i a més per un tercer mètode que es un algorisme iteratiu molt intuïtiu. 

Creeu un nou espai de treball per aquest mòdul amb el nom: m4. Aneu afegint un projecte nou del tipus Win32 Console Application per cada nova pràctica o exercici amb els noms que cada vegada es proposi.

Definiu un projecte nou anomenat m4p01 i afegiu-li un arxiu de font C/C++ anomenat m4p01.cpp. Escriviu el següent codi:

//m4p01.cpp: La suma dels n primers nombres naturals

#include<stdio.h>

 

int suma(int); //prototipus de la funció recursiva suma()

 

void main(){

 

    int n;
    int ct;
    int suma1; // fa el càlcul amb les n-1 sumes
    int suma2; //aplica la fórmula
    int suma3; //fa servir una funció recursiva

 

    printf("comprovació de la fórmula s=n(1+n)/2\n\n");
    printf("introduïu n :");scanf("%d",&n);

 

    suma1=0;

    for(ct=1;ct<=n;ct++) suma1=suma1+ct;

    suma2=n*(1+n)/2;
    suma3=suma(n);
    printf("mètode 1: 1+2+...+n: %d\n",suma1);
    printf("mètode 2: (1+n)*n/2: %d\n",suma2);
    printf("mètode 3: Recursivament : %d\n",suma3);

}

 

 

//definició de la funció recursiva suma()
int suma(int n){

    if (n<2) return n;
    return n+suma(n-1);

}

Explicació del programa

La variable local suma1 emmagatzemarà el valor de la suma dels n nombres de forma explicita mitjançant el següent bucle:

 
suma1=0;

for(ct=1;ct<=n;ct++) suma1=suma1+ct;

És important inicialitzar el valor de la variable suma1 a 0 ja que les variables locals no s'inicien a 0 automàticament.

La variable local suma2 emmagatzemarà el valor de la suma a partir de la fórmula abans esmentada:

 
suma2=n*(1+n)/2

Per últim, la variable suma3 emmagatzemarà el resultat d'aplicar la funció recursiva suma(). Es diu funció recursiva perquè en el cos de la funció hi ha una crida a la pròpia funció.

 

//definició de la funció recursiva suma()
int suma(int n){

    if (n<2) return n;
    return n+suma(n-1);

}

Tota funció recursiva ha de tenir un cas d'escapament, és a dir, un cas en què pugui sortir d'aquest bucle infinit que representa la recursivitat. En aquesta funció, en el cas que n sigui més petit que 2, torna el mateix n i surt del bucle.