ASIX-M3-UF2-A3 - Historial de revisió

Jmoreno a 17:12, 22 feb 2024

2024-02-22T17:12:43Z

Jmoreno a 17:04, 22 feb 2024

2024-02-22T17:04:01Z

Jmoreno a 17:03, 22 feb 2024

2024-02-22T17:03:24Z

Jmoreno a 16:54, 25 gen 2024

2024-01-25T16:54:27Z

Jmoreno a 16:15, 25 gen 2024

2024-01-25T16:15:36Z

Rsort: /* Exemple d'ús de recursivitat: sèrie de Fibonacci */

2021-03-06T18:43:41Z

‎Exemple d'ús de recursivitat: sèrie de Fibonacci

Rsort: /* Exemple d'ús de recursivitat: factorials */

2021-03-06T18:38:53Z

‎Exemple d'ús de recursivitat: factorials

Rsort: /* Exemple d'ús de recursivitat: factorials */

2021-03-06T18:38:29Z

‎Exemple d'ús de recursivitat: factorials

Rsort: /* Exemple d'ús de recursivitat: factorials */

2021-03-06T18:37:31Z

‎Exemple d'ús de recursivitat: factorials

Rsort: /* Conceptes de recursivitat */

2021-03-06T18:25:01Z

‎Conceptes de recursivitat

@@ Línia 79: / Línia 79: @@
         es vagi aproximant al cas base '''
         return fibonacci(n - 1) + fibonacci(n - 2)
 </source>

@@ Línia 79: / Línia 79: @@
         es vagi aproximant al cas base '''
         return fibonacci(n - 1) + fibonacci(n - 2)
 </source>

@@ Línia 79: / Línia 79: @@
         es vagi aproximant al cas base '''
         return fibonacci(n - 1) + fibonacci(n - 2)
 </source>

@@ Línia 67: / Línia 67: @@
 fibonacci(1) = 1
 fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
-<!--
 Per tant el podríem codificar així:
 <source lang="python">
@@ Línia 80: / Línia 80: @@
         return fibonacci(n - 1) + fibonacci(n - 2)
 </source>
 Cal anar amb compte amb els programes recursius com el que utilitzem aquí per generar nombres de Fibonacci. Cada invocació del mètode fibonacci que no coincideix amb un dels casos base produeix dues crides recursives més al mètode fibonacci. Per tant, aquest conjunt de crides recursives se surt ràpidament de control. Per calcular el valor 20 de Fibonacci amb aquest programa, es requereixen 21,891 crides al mètode fibonacci; per calcular el valor 30 de Fibonacci es requereixen 2,692,537 crides! A mesura que tractem de calcular valors més grans de Fibonacci, observarem que cada nombre de Fibonacci consecutiu que calculem amb l'aplicació requereix un augment considerable en temps de càlcul i en el nombre de crides al mètode fibonacci.

@@ Línia 67: / Línia 67: @@
 fibonacci(1) = 1
 fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
+<!--
 Per tant el podríem codificar així:
 <source lang="python">
@@ Línia 80: / Línia 80: @@
         return fibonacci(n - 1) + fibonacci(n - 2)
 </source>
 Cal anar amb compte amb els programes recursius com el que utilitzem aquí per generar nombres de Fibonacci. Cada invocació del mètode fibonacci que no coincideix amb un dels casos base produeix dues crides recursives més al mètode fibonacci. Per tant, aquest conjunt de crides recursives se surt ràpidament de control. Per calcular el valor 20 de Fibonacci amb aquest programa, es requereixen 21,891 crides al mètode fibonacci; per calcular el valor 30 de Fibonacci es requereixen 2,692,537 crides! A mesura que tractem de calcular valors més grans de Fibonacci, observarem que cada nombre de Fibonacci consecutiu que calculem amb l'aplicació requereix un augment considerable en temps de càlcul i en el nombre de crides al mètode fibonacci.

@@ Línia 69: / Línia 69: @@
 Per tant el podríem codificar així:
-<source lang="java">
+<source lang="python">
-public int fibonacci(int n) {
+def fibonacci(int n):
-   int resultat;
+    if n <=1:
-    if (n <=1) {
+       # Cas base: Se sap el resultat directament
-     //Cas base: Se sap el resultat directament
+       return n
-     resultat=1;
+    else:
-    } else {
+   ''' Cas recursiu: Per calcular-lo cal invocar el propi metode
-       /*Cas recursiu: Per calcular-lo cal invocar el propi metode
+       El valor del nou parametre d'entrada ha de variar de manera que
-         El valor del nou parametre d'entrada ha de variar de manera que
+       es vagi aproximant al cas base '''
-         es vagi aproximant al cas base */
+        return fibonacci(n - 1) + fibonacci(n - 2)
 </source>
@@ Línia 88: / Línia 84: @@
 * Cal evitar els programes recursius a l'estil de Fibonacci, ja que produeixen una “explosió” exponencial de crides a mètodes. A més en aquest cas es pot observar que hi ha càlculs que els fem moltíssims cops.
 [[Imatge:m3uf2_recursivitat_4.png |600px|center| Recursivitat]]

@@ Línia 24: / Línia 24: @@
 El factorial de l'enter numero (on numero >= 0) pot calcular-se de manera iterativa (sense recursivitat), usant una instrucció for de la següent manera:
-<source lang="java">
+<source lang="python">
-int factorial = 1;
+factorial = 1;
-for ( int comptador = numero; comptador >= 1; comptador-- )
+for comptador in range(numero, 1, -1):
-    factorial = comptador;
+    factorial *= comptador
 </source>
 Podem arribar a una declaració recursiva del mètode del factorial, si observem la següent relació:
-n! = n · (n – 1)!
+n! = n * (n – 1)!
 Per exemple, 5! és sens dubte igual a 5 · 4!, com es mostra en les següents equacions:
-! = 5 · 4 · 3 · 2 · 1
+! = 5 * 4 * 3 * 2 * 1
-! = 5 · (4 · 3 · 2 · 1)
+! = 5 * (4 * 3 * 2 * 1)
-! = 5 · (4!)
+! = 5 * (4!)
 Per tant podem resoldre el problema de forma recursiva així:
-<source lang="java">
+<source lang="python">
-public long factorial(int n) {
+def factorial(n):
-   long resultat;
+    if n <=1:
        //Cas base: Se sap el resultat directament
-       resultat=1;
+       return 1
-    } else {
+    else:
        /*Cas recursiu: Per calcular-lo cal invocar el propi metode
-         El valor del nou parametre d'entrada ha de variar de manera que
+         El valor del nou paràmetre d'entrada ha de variar de manera que
          es vagi aproximant al cas base */
-       resultat = n * factorial(n - 1);
+       return n * factorial(n - 1)
 </source>

@@ Línia 15: / Línia 15: @@
 Per comprendre millor el concepte de recursivitat, vegem un exemple que és bastant comú per als usuaris de computadora: la definició recursiva d'un directori en una computadora. En general, una computadora emmagatzema els arxius relacionats en un directori. Aquest directori pot estar buit, pot contenir arxius i/o pot contenir altres directoris (que, en general, es coneixen com a subdirectoris). Al seu torn, cadascun d'aquests directoris pot contenir també arxius i directoris. Si volem llistar cada arxiu en un directori (incloent tots els arxius en els subdirectoris d'aquest directori), necessitem crear un mètode que llegeixi primer els arxius del directori inicial i que després faci cridades recursives per llistar els arxius en cadascun dels subdirectoris d'aquest directori. El cas base ocorre quan s'arriba a un directori que no contingui subdirectoris. En aquest punt, s'han llistat tots els arxius en el directori original i no es necessita més la recursivitat.
-[[Imatge:m3uf2_m3uf2_recursivitat directa-indirecta.png |500px|center| Recursivitat]]
+[[Imatge:m3uf2_m3uf2_recursivitat directa-indirecta.png |600px|center| Recursivitat]]
 == Exemple d'ús de recursivitat: factorials ==