Ultimo aggiornamento: 2023-03-18
(Crediti: prof. Violetta Lonati, Università di Milano)
libpsgraph.cQuesto esercizio fa uso della libreria libpsgraph che consente di produrre dei semplici grafici in PostScript. Per usare la libreria si può procedere come segue:
creare una directory (si può usare la directory corrente);
salvare in essa i file libpsgraph.c e libpsgraph.h;
scrivere la propria applicazione (che nel nostro caso è il file koch.c), che include all’inizio la direttiva
#include "libpsgraph.h"compilare il programma con il comando
gcc -std=c90 -Wall -Wpedantic libpsgraph.c koch.c -lm -o koch(attenzione alla necessità di linkare la libreria matematica usando il flag -lm; su Code::Blocks non dovrebbe essere necessario fare nulla di particolare, dato che la libreria matematica dovrebbe essere linkata di default).
La libreria permette di disegnare usando le funzioni della “turtle graphics”; il disegno prodotto viene salvato in formato PostScript su un file, il cui nome va specificato prima di iniziare a disegnare. Il file essere visualizzato con un apposito programma; se non ne avete uno già installato, si può caricare il file su questa pagina Web.
La libreria va usata in questo modo:
per prima cosa, si invoca la funzione start(nomefile) passando come parametro il nome del file in cui si vuole che il grafico venga salvato, ad esempio start("prova.ps");
a questo punto è possibile disegnare usando le funzioni seguenti, che accettano un parametro di tipo double:
draw(x): disegna un segmento lungo \(x\) millimetri;
move(x): si sposta (senza disegnare) di un segmento lungo \(x\) millimetri;
turn(x): ruota di \(x\) gradi in senso orario;
setcolor(r, g, b): imposta il colore a \((r, g, b)\), dove i parametri possono assumere valori in \([0, 1]\)
alla fine, occorre invocare la funzione end().
All’inizio, la “tartaruga” è orientata verso destra in orizzontale; quindi, se la prima istruzione è draw(10) ci si trova con un segmento orizzontale di lunghezza 10 orientato da sinistra verso destra.
Ad esempio, il programma seguente disegna un quadrato:
#include "libpsgraph.h"
int main( void )
{
start("square.ps");
draw(100); turn(90);
draw(100); turn(90);
draw(100); turn(90);
draw(100);
end();
return 0;
}Realizzare una funzione che, data una lunghezza in millimetri \(x\) e un intero \(n \geq 0\) produce la curva di Koch di ordine \(n\) e di “lunghezza” \(x\); per “lunghezza” qui si intende la lunghezza della sola base.
La curva di Koch prende il nome dal matematico svedese Niels Fabian Helge von Koch, che l’ha studiata per primo, ed è definita come segue:
se \(n = 0\), la curva è un segmento di lunghezza \(x\);
se \(n > 0\), la curva è ottenuta concatenando quattro curve di Koch di ordine \(n-1\) e lunghezza \(x/3\) ciascuna, disposte come mostrato in Figura 1.
Le curve di Koch di ordine \(n=0, \ldots, 4\) sono mostrate in Figura 1. Si può notare come la curva di ordine \(n=4\) sia composta da quattro curve di ordine \(n=3\) e lunghezza \(x/3\) orientate allo stesso modo dei quattro segmenti del caso \(n=1\).
Realizzare ora una funzione che, data una lunghezza in millimetri \(x\) e un intero \(n \geq 0\), produce il fiocco di neve di Koch di ordine \(n\): esso si ottiene da un triangolo equilatero i cui lati siano costituiti da tre curve di Koch di ordine \(n\) e lunghezza \(x\) (Figura 2).
Da quanti segmenti è composta la curva di Koch di ordine \(n\)? (per \(n=0\) c’è un solo segmento, per \(n=1\) ce ne sono quattro).
Sia \(K(n)\) il numero complessivo di invocazioni della funzione koch() necessarie per disegnare la curva di Koch di ordine \(n\). Quindi si ha \(K(0)=1\), dato che la funzione viene invocata una sola volta quando \(n=0\); \(K(1)=5\) dato che la funzione viene invocata una volta con \(n=1\) e quattro volte con \(n=0\); e così via. Scrivere una espressione chiusa (cioè non ricorsiva) per \(K(n)\) (Suggerimento: si può partire da una espressione ricorsiva ed espandere i primi termini per individuare l’espressione chiusa).
Dati \(x\) e \(n\), qual è la lunghezza complessiva della curva disegnata dalla chiamate koch(x, n)? Per “lunghezza complessiva” si intende la somma delle lunghezze di tutti i segmenti che la compongono.