{"id":456,"date":"2014-12-30T22:54:16","date_gmt":"2014-12-30T21:54:16","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=456"},"modified":"2015-07-03T11:54:32","modified_gmt":"2015-07-03T09:54:32","slug":"numeri-di-fibonacci","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/numeri-di-fibonacci\/","title":{"rendered":"Numeri di Fibonacci"},"content":{"rendered":"<p>I numeri di Fibonacci prendono il nome da una sfida matematica che Fibonacci lanci\u00f2 a un suo collega.<br \/>\nIl problema tratta la proverbiale velocit\u00e0 con cui i conigli si riproducono:<\/p>\n<ul>\n<li>il 1\u00b0 mese \u00e8 presente una coppia di conigli<\/li>\n<li>una coppia di conigli diventa matura all&#8217;inizio del 2\u00b0 mese di vita<\/li>\n<li>la gestazione dura un mese<\/li>\n<li>ogni parto produce una coppia maschio-femmina di conigli<\/li>\n<li>ogni coppia di conigli sopravvive e si riproduce per sempre&#8230;<\/li>\n<\/ul>\n<p>Calcolare il numero di coppie di conigli dopo 10 mesi.<\/p>\n<h3>Analisi<\/h3>\n<p>Tramite i pulsanti puoi osservare l&#8217;evoluzione della popolazione di conigli fino al sesto mese<\/p>\n<div style=\"padding-left: 30px;\"><img decoding=\"async\" name=\"animazione3\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/fibonacci6.png\"><\/p>\n<p><input type=\"button\" value=\"1\u00b0\" onClick=\"cambia(1)\"> <input type=\"button\" value=\"2\u00b0\" onClick=\"cambia(2)\"> <input type=\"button\" value=\"3\u00b0\" onClick=\"cambia(3)\"> <input type=\"button\" value=\"4\u00b0\" onClick=\"cambia(4)\"> <input type=\"button\" value=\"5\u00b0\" onClick=\"cambia(5)\"> <input type=\"button\" value=\"6\u00b0\" onClick=\"cambia(6)\"><script language=\"JavaScript\">var frame=0;function cambia(f){frame=f;document.animazione3.src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/fibonacci\"+frame+\".png\"}<\/script><\/div>\n<p>Ogni mese sono presenti i conigli gi\u00e0 presenti il mese precedente pi\u00f9 quelli appena nati, che sono in numero uguale ai conigli presenti due mesi prima!<\/p>\n<p>I numeri di Fibonacci sono proprio la successione <strong>1<\/strong>, <strong>1<\/strong>, <strong>2<\/strong>, <strong>3<\/strong>, <strong>5<\/strong>, <strong>8<\/strong>, <strong>13<\/strong>, <strong>21<\/strong>, <strong>34<\/strong>, <strong>55<\/strong>, <strong>89<\/strong>, &#8230; cio\u00e8 il numero di coppie di conigli per ogni mese.<\/p>\n<p>Al decimo mese ci saranno <strong>55<\/strong> coppie di conigli.<\/p>\n<h3>Algoritmo iterativo<\/h3>\n<p>A partire dai valori noti (1, 1) si calcola, mese dopo mese, un nuovo valore finch\u00e9 non si giunge al mese richiesto.<\/p>\n<p>Per calcolare <tt>fibonacci(5)<\/tt> si seguono i passi<\/p>\n<div style=\"padding-left: 30px;\"><tt>fibonacci(1) = 1<br \/>\nfibonacci(2) = 1<br \/>\nfibonacci(3) = fibonacci(2)+fibonacci(1) = 1+1 = 2<br \/>\nfibonacci(4) = fibonacci(3)+fibonacci(2) = 2+1 = 3<br \/>\nfibonacci(5) = fibonacci(4)+fibonacci(3) = 3+2 = 5<\/tt><\/div>\n<pre>Function fibonacci(n: Integer): LongInt;\r\nVar\r\n   i      : Integer;\r\n   a, b, c: LongInt;\r\nBegin\r\n   If(n <= 2) Then\r\n      fibonacci:=1\r\n   Else\r\n      Begin\r\n         a:=1;\r\n         b:=1;\r\n         For i:=3 To n Do\r\n            Begin\r\n               c:=a+b;\r\n               a:=b;\r\n               b:=c;\r\n            End;\r\n         fibonacci:=c;\r\n      End;\r\nEnd;<\/pre>\n<h3>Algoritmo ricorsivo<\/h3>\n<p>La formulazione ricorsiva dei numeri di Fibonacci \u00e8 molto comoda perch\u00e9 sintetica<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><img decoding=\"async\" title=\"WikiImage\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/fibonacci.gif\" alt=\"image\" \/><\/div>\n<p>Per calcolare <tt>fibonacci(5)<\/tt> si seguono i passi<\/p>\n<div style=\"padding-left: 30px;\"><tt>fibonacci(5) = fibonacci(4)+fibonacci(3)<br \/>\n= (fibonacci(3)+fibonacci(2)) + (fibonacci(2)+fibonacci(1))<br \/>\n= ((fibonacci(2)+fibonacci(1)) + 1) + (1+1)<br \/>\n= ((1+1)+1)+(1+1)<br \/>\n= 5<\/tt><\/div>\n<pre class=\"\">Function fibonacci(n: Integer): LongInt;\r\nBegin\r\n   If(n <= 2) Then\r\n      fibonacci:=1\r\n   Else\r\n      fibonacci:=fibonacci(n-1)+fibonacci(n-2);\r\nEnd;<\/pre>\n<h3>Con formula!<\/h3>\n<p>Non \u00e8 necessario alcun algoritmo iterativo o ricorsivo se si utilizza la formula<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-465 size-full\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/fibonacci2.gif\" alt=\"fibonacci2\" width=\"267\" height=\"57\" \/><\/div>\n<p>Il contributo del secondo termine \u00e8 cos\u00ec piccolo che pu\u00f2 essere trascurato. Calcola il primo termine e considera l'intero pi\u00f9 vicino (arrotonda).<\/p>\n<hr\/>\n<p>Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessit\u00e0 in tempo.<\/p>\n<h3 id=\"hn_59ca4f8bbb_1\">Algoritmo ricorsivo<\/h3>\n<div class=\"code\">Il tempo di attesa pu\u00f2 essere considerato proporzionale al numero di chiamate ricorsive<\/div>\n<p style=\"padding-left: 30px;\">T(1) = 1<br \/>\nT(2) = 1<br \/>\nT(3) = 1+T(2)+T(1) = 1+1+1 = 3 &gt;\u00a02<sup>2<\/sup>-1<br \/>\nT(4) = 1+T(3)+T(2) = 1+3+1 = 5 &gt;\u00a02<sup>2<\/sup>-1<br \/>\nT(5) = 1+T(4)+T(3) = 1+5+3 = 9 &gt;\u00a02<sup>3<\/sup>-1<br \/>\nT(6) = 1+T(5)+T(4) = 1+9+5 = 15 &gt;\u00a02<sup>3<\/sup>-1<br \/>\nT(7) = 1+T(6)+T(5) = 1+15+9 = 25 &gt;\u00a02<sup>4<\/sup>-1<br \/>\nT(8) = 1+T(7)+T(6) = 1+25+15 = 41 &gt;\u00a02<sup>4<\/sup>-1<br \/>\n...<br \/>\nT(n) \u2265 2<sup>n\/2<\/sup>-1.<\/p>\n<p>Il tempo di attesa \u00e8 maggiore di un tempo esponenziale, anche se con esponente <tt>n\/2<\/tt> piuttosto che <tt>n<\/tt>, quindi per n <em>molto grande<\/em><\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(n) \u2208\u00a0<strong>O(2<sup>n<\/sup>)<\/strong>.<\/div>\n<p>L'algoritmo ricorsivo per il calcolo dell'n-simo numero di Fibonacci ha complessit\u00e0 <strong>esponenziale<\/strong>!<\/p>\n<h3 id=\"hn_59ca4f8bbb_2\">Algoritmo iterativo<\/h3>\n<p>Si tratta di un algoritmo con un'iterazione semplice, senza chiamate ricorsive, quindi<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(n)=c<sub>1<\/sub>+c<sub>2<\/sub>n<\/div>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(n) \u2208\u00a0<strong>O(n)<\/strong>.<\/div>\n<p>L'algoritmo iterativo per il calcolo dell'n-simo numero di Fibonacci ha complessit\u00e0 <strong>lineare<\/strong>!<\/p>\n<h3>Con formula<\/h3>\n<p>Se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(n)=c<\/div>\n<div class=\"indent\" style=\"padding-left: 30px;\">T(n) \u2208\u00a0<strong>O(1)<\/strong>.<\/div>\n<p class=\"indent\"><em>Se consideriamo che per <strong>n<\/strong> molto grande l'operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente a <strong>n<\/strong> allora si ottiene di nuovo una complessit\u00e0 lineare.<\/em><\/p>\n<h3 class=\"indent\">Conclusioni<\/h3>\n<p class=\"indent\">Dato un certo problema, il calcolo dell'<strong>n<\/strong>-esimo numero di Fibonacci, possiamo individuare diversi algoritmi con complessit\u00e0 diverse.<br \/>\nAl variare di <strong>n<\/strong> utilizzeremo l'algoritmo pi\u00f9 conveniente!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I numeri di Fibonacci prendono il nome da una sfida matematica che Fibonacci lanci\u00f2 a un suo collega. Il problema tratta la proverbiale velocit\u00e0 con cui i conigli si riproducono: il 1\u00b0 mese \u00e8 presente una coppia di conigli una coppia di conigli diventa matura all&#8217;inizio del 2\u00b0 mese di vita la gestazione dura un &#8230; <a title=\"Numeri di Fibonacci\" class=\"read-more\" href=\"https:\/\/www.valcon.it\/pascal\/numeri-di-fibonacci\/\" aria-label=\"Leggi di pi\u00f9 su Numeri di Fibonacci\">Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/456"}],"collection":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/comments?post=456"}],"version-history":[{"count":18,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/456\/revisions"}],"predecessor-version":[{"id":5648,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/456\/revisions\/5648"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/media?parent=456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/categories?post=456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/tags?post=456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}