MCD-MCM

1. Dissenya la funció mcd(a, b) que donats dos enters positius a i b, en calculi el màxim comú divisor. Utilitzarem el mètode d’anar provant si un nombre donat divideix a la vegada a i b. Si ho provem en l’ordre min(a,b), min(a,b)-1, …, 2, 1, el primer que divideixi a a i b, serà el màxim comú divisor.

   Desa la funció al fitxer mcdmcm.py. La funció ha de passar el següent doctest:

   >>> mcd (15,25)
   5
   >>> mcd (36, 90)
   18
   >>> mcd(453, 87)
   3
   >>> mcd(462, 1071)
   21
   

   Nota

   Pots descarregar el fitxer amb tests mcd-1.txt

2. Dissenya la funció mcd_euclides_1(a, b) que donats dos enters positius \(a\) i \(b\), en calculi el màxim comú divisor. Utilitzarem un mètode donat per Euclides que consisteix en aplicar les següents propietats del mcd:

   \[\begin{split}mcd(a,b) = \begin{cases} mcd(a-b, b) & \text{si } b \lt a \\ a & \text{si } b = a \\ mcd(a, b-a) & \text{si } b \gt a \\ \end{cases}\end{split}\]

   Per exemple, \(mcd(10,15) = mcd(10,5) = mcd(5,5) = 5\)

   Desa la funció al fitxer mcdmcm.py. La funció ha de passar el següent doctest:

   >>> mcd_euclides_1 (15,25)
   5
   >>> mcd_euclides_1 (36, 90)
   18
   >>> mcd_euclides_1 (453, 87)
   3
   >>> mcd_euclides_1 (462, 1071)
   21
   

   Nota

   Pots descarregar el fitxer amb tests mcd-2.txt

3. Dissenya la funció mcd_euclides_2(a, b) que donats dos enters positius \(a\) i \(b\), en calculi el màxim comú divisor. Utilitzarem un mètode donat per Euclides l’algorisme d’Euclides que consisteix en aplicar les següents propietats del mcd:

   \[\begin{split}mcd(a,b) = \begin{cases} a & \text{si } b = 0 \\ mcd(b, r) & \text{si } b \gt 0 \text{, essent } r \text{ el residu de la divisió entera d'} a \text{ per } b \\ \end{cases}\end{split}\]

   Per exemple, \(mcd(567,28)=mcd(28,7)=mcd(7,0)=7\)

   Desa la funció al fitxer mcdmcm.py. La funció ha de passar el següent doctest:

   >>> mcd_euclides_2 (15,25)
   5
   >>> mcd_euclides_2 (36, 90)
   18
   >>> mcd_euclides_2 (453, 87)
   3
   >>> mcd_euclides_2 (462, 1071)
   21
   

   Nota

   Pots descarregar el fitxer amb tests mcd-3.txt

4. Dissenya la funció mcm(a, b) que donats dos enters positius, en calculi el mínim comú múltiple. Utilitza la funció de l’apartat 1.

   Desa la funció al fitxer mcdmcm.py. La funció ha de passar el següent doctest:

   >>> mcm (15,25)
   75
   >>> mcm (36, 90)
   180
   >>> mcm (453, 87)
   13137
   >>> mcm (462, 1071)
   23562
   

   Nota

   Pots descarregar el fitxer amb tests mcm.txt

Solució

Disposes d’una solució al fitxer mcdmcm.py.