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

 
Treure n amb m daus

En aquesta pràctica resoldrem un interessant problema, també amb una funció recursiva. Es tracta de comptar el nombre de formes possibles en què es pot obtenir una puntuació n amb m daus. 

 
Desenvolupament de la pràctica 

Si es juga amb dos daus, sumant les puntuacions obtingudes amb tots dos, tothom pot observar que la puntuació més probable és la puntuació 7.

Un jugador va expressar a Galileo la seva sorpresa quan va observar que al jugar amb tres daus, la suma 10 apareix amb més freqüència que la suma 9. Segons aquest jugador, la suma 9 i la suma 10 tenen els mateixos casos favorables:

suma 9

 126 135 144 225 234 333

suma 10

 136 145 226 235 244 334

Evidentment, el jugador va cometre un error al considerar casos igualment favorables la puntuació 126 i la puntuació 333, ja que la primera pot sortir de 6 formes possibles (126, 162, 216, 261, 612, 621) i la segona només d'una forma possible.

Comptant bé, tenint en compte l'ordre, hi ha 27 casos favorables a la suma 10 i només 25 casos favorables a la suma 9.

Aquest exercici ens dóna la idea de fer un programa amb una funció f(n,m) que calculi el nombre de formes possibles de treure una puntuació n amb m daus, considerant l'ordre.

Per resoldre el problema plantejat, implementarem una funció recursiva f(n,m) que farà tot el càlcul.

Creeu un nou arxiu font C anomenat m4p04.c. i escriviu el següent codi:

//m4p04.c - Treure la puntuació n amb m daus -

#include <stdio.h>

int minim (int , int );
int f(int, int);

int main(){

 

    int n,m;

 

    printf("Introduïu el valor d'n (puntuació)...");
    scanf("%d",&n);

    printf("Introduïu el valor d'm (nombre de daus)...");
    scanf("%d",&m);

    printf("El nombre de formes de treure la puntuació %d amb
             %d daus és %d\n",n,m,f(n,m));

    return 0;
}

 

int f(int n, int m){

    int ct,temp=0;

    if( m<1)return 0;
    if (m == 1) {
       if (n < 1 || n > 6)return 0;
       return 1;
    }
   

    for (ct = 1;ct<= minim(6, n - m + 1);ct++){
        temp = temp + f(n - ct, m - 1);
    }
    return temp;
}

int minim (int a, int b){

    return (a<b)?a:b;
}

Captura de l'execució del programa.

 

 

Explicació del programa

La funció f() considera tres casos:

Si m<1, llavors, retorna 0 ja que no es pot tenir 0 daus. Aquest cas només es pot donar en el cas que deliberadament l'usuari introdueixi una xifra més petita que 1.

Si m=1 és el cas trivial en què se surt de la recursivitat. Amb un dau només es pot treure una puntuació possible una sola vegada.

En el cas que m>1 fa servir que en el primer dau es pot obtenir una puntuació compresa entre 1 i mínim(6 , n-m+1) i, per cadascuna d'aquestes puntuacions possibles es compta el nombre de formes com la resta de daus poden formar la puntuació que resta.

Exemple:

Seguirem el pas al càlcul de f(9,3)

el primer dau pot ser: 1, 2, 3, 4, 5, 6

Si el primer dau és un 1, queda una puntuació 8 per als dos daus restants, és a dir, f(8,2) formes

Si el primer dau és un 2, queda una puntuació 7 per als dos daus restants, és a dir, f(7,2) formes, i així successivament. El nombre total serà:

f(9,3)=f(8,2)+f(7,2)+f(6,2)+f(5,2)+f(4,2)+f(3,2)+f(2,2)

A la seva vegada, per treure un 8 amb dos daus, el primer dau pot ser un 2, un 3 o un 4. La funció considera també que pot començar per 1, però f(7,1)=0.

f(8,2)=f(7,1)+f(6,1)+f(5,1)+f(4,1)=0+1+1+1=3