|
| 1 | +\documentclass[11pt,a4]{article} |
| 2 | + |
| 3 | +\usepackage[margin=2cm]{geometry} |
| 4 | + |
| 5 | +\usepackage{amsmath} |
| 6 | +\usepackage{url} |
| 7 | + |
| 8 | +\usepackage[utf8]{inputenc} |
| 9 | + |
| 10 | +% Default fixed font does not support bold face |
| 11 | +\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{10} % for bold |
| 12 | +\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{10} % for normal |
| 13 | + |
| 14 | +% Custom colors |
| 15 | +\usepackage{color} |
| 16 | +\definecolor{deepblue}{rgb}{0,0,0.5} |
| 17 | +\definecolor{deepred}{rgb}{0.6,0,0} |
| 18 | +\definecolor{deepgreen}{rgb}{0,0.5,0} |
| 19 | + |
| 20 | +\usepackage{listings} |
| 21 | + |
| 22 | +% Python style for highlighting |
| 23 | +\newcommand\pythonstyle{\lstset{ |
| 24 | +language=Python, |
| 25 | +basicstyle=\ttm, |
| 26 | +otherkeywords={self}, % Add keywords here |
| 27 | +keywordstyle=\ttb\color{deepblue}, |
| 28 | +emph={MyClass,__init__}, % Custom highlighting |
| 29 | +emphstyle=\ttb\color{deepred}, % Custom highlighting style |
| 30 | +stringstyle=\color{deepgreen}, |
| 31 | +frame=tb, % Any extra options here |
| 32 | +showstringspaces=false % |
| 33 | +}} |
| 34 | + |
| 35 | + |
| 36 | +% Python environment |
| 37 | +\lstnewenvironment{python}[1][] |
| 38 | +{ |
| 39 | +\pythonstyle |
| 40 | +\lstset{#1} |
| 41 | +} |
| 42 | +{} |
| 43 | + |
| 44 | +% Python for external files |
| 45 | +\newcommand\pythonexternal[2][]{{ |
| 46 | +\pythonstyle |
| 47 | +\lstinputlisting[#1]{#2}}} |
| 48 | + |
| 49 | +% Python for inline |
| 50 | +\newcommand\pythoninline[1]{{\pythonstyle\lstinline!#1!}} |
| 51 | + |
| 52 | + |
| 53 | +\usepackage{collectbox} |
| 54 | + |
| 55 | +\newcommand{\mybox}[2]{$\quad$\fbox{ |
| 56 | +\begin{minipage}{#1cm} |
| 57 | +\hfill\vspace{#2cm} |
| 58 | +\end{minipage} |
| 59 | +}} |
| 60 | + |
| 61 | +\usepackage{fancyhdr} |
| 62 | +\pagestyle{fancy} |
| 63 | +\rhead{Programmazione 1 - Esercitazione 2} |
| 64 | + |
| 65 | +\include{book_header} |
| 66 | + |
| 67 | +\begin{document} |
| 68 | +\thispagestyle{empty} |
| 69 | +\hrule |
| 70 | +\begin{center} |
| 71 | + {\Large {\bf Programmazione 1 \hspace{3cm} $\quad \quad$ Soluzioni Esercitazione 2}} |
| 72 | +\end{center} |
| 73 | +\hrule |
| 74 | + |
| 75 | +\section*{} |
| 76 | +Le soluzioni sono anche fornite in un unico script python sul sito: |
| 77 | +\begin{center} |
| 78 | + \url{https://github.com/mathcoding/programming/tree/master/scripts} |
| 79 | +\end{center} |
| 80 | + |
| 81 | +\begin{enumerate} |
| 82 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 83 | +\item Scrivere una procedura che calcoli l'ennesimo numero di Fibonacci usando un {\bf processo iterativo} |
| 84 | +(si veda il {\tt Lab 4} per la definizione di processo iterativo). |
| 85 | +\begin{python} |
| 86 | +def FibRec(n): |
| 87 | + """ Calcolo di Fibonacci con PROCESSO RICORSIVO """ |
| 88 | + if n == 0 or n == 1: |
| 89 | + return n |
| 90 | + return FibRec(n-1) + FibRec(n-2) |
| 91 | + |
| 92 | +def FibIter(n): |
| 93 | + """ Calcolo di Fibonacci con PROCESSO ITERATIVO """ |
| 94 | + def FibI(a, b, counter): |
| 95 | + if counter < 2: |
| 96 | + return a |
| 97 | + return FibI(a+b, a, counter-1) |
| 98 | + |
| 99 | + return FibI(1, 0, n) |
| 100 | +\end{python} |
| 101 | + |
| 102 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 103 | +\item Una funzione $f$ è definita dalla regola seguente: |
| 104 | +\begin{align} |
| 105 | + f(n) = \left\{\begin{array}{ll} n & \mbox{if } n<3 \\ f(n-1)+2\,f(n-2)+3\,f(n-3) & \mbox{if } n \geq 3 \end{array} \right. |
| 106 | +\end{align} |
| 107 | +\begin{enumerate} |
| 108 | +\item Si scriva una procedura che calcoli $f$ usando un {\bf processo ricorsivo}. |
| 109 | +\item Si scriva una procedura che calcoli $f$ usando un {\bf processo iterativo}. |
| 110 | +\end{enumerate} |
| 111 | +\begin{python} |
| 112 | +def FnRec(n): |
| 113 | + """ Calcolo di f(n) = f(n-1)+2*f(n-2)+3*f(n-3), con f(0)=0, f(1)=1, f(2)=2 |
| 114 | + (uso di processo ricorsivo) """ |
| 115 | + if n < 3: |
| 116 | + return n |
| 117 | + return FnRec(n-1) + 2*FnRec(n-2) + 3*FnRec(n-3) |
| 118 | + |
| 119 | +def FnIter(n): |
| 120 | + """ Calcolo di f(n) = f(n-1)+2*f(n-2)+3*f(n-3), con f(0)=0, f(1)=1, f(2)=2 |
| 121 | + (uso di processo iterativo) """ |
| 122 | + def FnI(a, b, c, counter): |
| 123 | + if counter < 3: |
| 124 | + return a |
| 125 | + return FnI(a+2*b+3*c, a, b, counter-1) |
| 126 | + |
| 127 | + return FnI(2, 1, 0, n) |
| 128 | +\end{python} |
| 129 | + |
| 130 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 131 | +\item Si scrive un predicato che ci dica se un dato numero $n$ sia un numero primo. |
| 132 | +Si può usare la definizione che $n$ è un numero primo, se e solo se $n$ è il suo più piccolo divisore maggiore di uno |
| 133 | +(suggerimento: scrivere prima una funzione che trova il più piccolo divisore di $n$). |
| 134 | + |
| 135 | +È possibile scrivere questa procedura in modo tale che l'ordine di crescita per il numero di operazioni richieste sia $\Theta(\sqrt{n})$? |
| 136 | +\begin{python} |
| 137 | +def IsPrime(n): |
| 138 | + """ Predicato che restituisce "True" quando "n" e` un numero primo """ |
| 139 | + def MinorDivisore(a, n): |
| 140 | + if a*a > n: |
| 141 | + return n |
| 142 | + if n % a == 0: |
| 143 | + return a |
| 144 | + return MinorDivisore(a+1, n) |
| 145 | + |
| 146 | + if n == 0: |
| 147 | + return False |
| 148 | + if n == 1: |
| 149 | + return True |
| 150 | + return MinorDivisore(2,n) == n |
| 151 | +\end{python} |
| 152 | + |
| 153 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 154 | +\item La procedura {\tt Sommatoria} vista nel {\tt Lab 7} genera un processo ricorsivo lineare. |
| 155 | +La stessa procedura può essere riscritta in modo tale che il processo generato sia iterativo: |
| 156 | +scrivere la procedura che genera un processo iterativo lineare. |
| 157 | +\begin{python} |
| 158 | +def SommatoriaIter(F, a, Next, b): |
| 159 | + def SommatoriaI(a, b, accumulator): |
| 160 | + if a > b: |
| 161 | + return accumulator |
| 162 | + return SommatoriaI(Next(a), b, accumulator+F(a)) |
| 163 | + |
| 164 | + return SommatoriaI(a, b, 0) |
| 165 | +def IntegraleIter(F, a, b, dx): |
| 166 | + def AddDx(x): |
| 167 | + return x + dx |
| 168 | + return dx*SommatoriaIter(F, a+dx/2, AddDx, b) |
| 169 | +\end{python} |
| 170 | + |
| 171 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 172 | +\item In maniera analoga alla funzione {\tt Sommatoria}, si può definire una funzione {\tt Produttoria} |
| 173 | +che restituisce i valori dei prodotti di una funzione valutata in un insieme di punti definiti da un dato intervallo $[a,b]$: |
| 174 | +$$ |
| 175 | + \prod_{n=a}^b f(n) = f(a)\cdot ... \cdot f(b) |
| 176 | +$$ |
| 177 | +Scrivere tale funzione e mostrare come sia possibile usarla per calcolare $n!$ |
| 178 | +\begin{python} |
| 179 | +def ProduttoriaRec(F, a, Next, b): |
| 180 | + if a > b: |
| 181 | + return 1 |
| 182 | + else: |
| 183 | + return F(a) * ProduttoriaRec(F, Next(a), Next, b) |
| 184 | +print("Es. 2.5 => ProduttoriaRec(1, 5): ", ProduttoriaRec(lambda x: x, 1, Inc, 5)) |
| 185 | +\end{python} |
| 186 | + |
| 187 | +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 188 | +\item Eseguire il grafico sovrapposto delle funzioni seguenti: |
| 189 | +$$R(n)=n, R(n)=10^5\,n, R(n)=n^2, R(n)=\log{n}, R(n)=n\log{n}, R(n)=1.6^n, R(n)=2^n.$$ |
| 190 | +\noindent {\bf ATTENZIONE:} Questa procedura potrebbe non funzionare correttamente all'interno di Spyder. |
| 191 | +Tuttavia uno script python può essere eseguito anche da linea di comando, come visto in laboratorio. |
| 192 | +Per i grafici, si consiglia di vedere pochi grafici alla volta con velocità di crescita simili. |
| 193 | + |
| 194 | +\begin{python} |
| 195 | +from numpy import linspace |
| 196 | +from matplotlib.pyplot import plot, xlabel, ylabel, show, legend, clf |
| 197 | +from math import log |
| 198 | + |
| 199 | +def PlotFunzioni(): |
| 200 | + D = linspace(1, 10, 100) |
| 201 | + clf() |
| 202 | + #plot(D, [x for x in D], label="y=x") |
| 203 | + plot(D, [x*x for x in D], label="y=x^2") |
| 204 | + plot(D, [log(x) for x in D], label="y=log(x)") |
| 205 | + plot(D, [x*log(x) for x in D], label="y=x*log(x)") |
| 206 | + |
| 207 | + #D = linspace(1, 10, 100) |
| 208 | + #plot(D, [1.6**x for x in D], label="y=1.6^x") |
| 209 | + #plot(D, [2**x for x in D], label="y=2^x") |
| 210 | + xlabel("x") |
| 211 | + ylabel("y=f(x)") |
| 212 | + legend(loc="upper left", shadow=True) |
| 213 | + show() |
| 214 | +\end{python} |
| 215 | + |
| 216 | + |
| 217 | +\end{enumerate} |
| 218 | + |
| 219 | +\end{document} |
0 commit comments