Newsgroup: it.comp.lang.c
Titolo: tema d'esame





Vi propongo un tema d'esame dato al politecnico di 
Torino...


divertitevi! ^__^


 




FONDAMENTI DI INFORMATICA


Corsi di Laurea in Ingegneria Elettronica, Informatica e delle 
Telecomunicazioni




PROVA DI PROGRAMMAZIONE 26 febbraio 1999




 


 


La 
formica di Langton 
è un animaletto cibernetico che vive su 
una superficie piana suddivisa in numerose cellette quadrate, alcune colorate di 
bianco altre di nero, e il cui moto è governato da semplici leggi:




Se si trova su una cella nera, la colora di bianco, ruota di 90° a 
    sinistra e si sposta di un quadratino avanti;


Se si trova su una cella bianca, la colora di nero, ruota di 90° a 
    destra e si sposta di un quadratino avanti.


Il movimento della formica procede fino a quando essa non "esce" 
dallo spazio disponibile.


In un file di testo sono rappresentate le condizioni iniziali. Nella prima 
riga, mediante una coppia di interi, è rappresentata la posizione 
iniziale della formica (<riga> <colonna>) e mediante una lettera 
(N-ord, S-ud, E-st, O-vest) la direzione. Nelle righe successive è 
rappresentata la superficie mediante una matrice di caratteri, in cui è 
stato utilizzato il carattere ‘.’ (punto) per rappresentare le 
cellette nere e il carattere ‘*’ (asterisco) per quelle bianche. Le 
dimensioni della matrice non sono note a priori, ma non superano le 24 righe e 
le 80 colonne. Il file si intende corretto.


Realizzare un programma che, lette dal file le condizioni iniziali, simuli il 
comportamento della formica e visualizzi sul video, ad ogni passo, lo stato 
della superficie, codificando le cellette con gli stessi caratteri utilizzati 
nell’input ad eccezione della celletta in cui si trova la formica, che 
deve essere codificata con il carattere ‘f’ se la formica è 
posizionata su una celletta nera, con il carattere ‘F’ se 
bianca.


È consentito usare le seguenti funzioni non standard del TURBO-C, il 
cui prototipo è in <conio.h>:


clrscr(); 
pulisce lo schermo;


gotoxy(colonna,riga):
 posiziona il cursore alla riga e 
colonna segnata.

Si raccomanda di visualizzare l’intera superficie solo 
all’inizio, aggiornando successivamente il video solo per le posizioni 
modificate. Tra un passo e il successivo il programma deve attendere che venga 
battuto il tasto <ENTER>.


Il programma 
deve tener conto di future modifiche
: in particolare, la 
superficie in cui vive la formica deve poter essere espansa fino ad una matrice 
480 righe X 640 colonne, le cellette devono poter essere rappresentate mediante 
singoli pixel, lo stato di ciascuna celletta, compresa quella in cui è 
posizionata la formica, mediante colori.



 superficie piana suddivisa in numerose cellette quadrate,
La conoscevo, molto interessante. E' praticamente la dimostrazione
matematica del fatto che dal caos possa nascere improvvisamente
l'ordine. Infatti la formica inizialmente percorre una traiettoria
assolutamente caotica ma ad un certo punto, senza alcun preavviso,
comincia a muoversi su una praticamente rettilinea. Ne avevo realizzato
una semplice implementazione diversi anni fa sullo Spectrum, mia antica
passione.
EMG

comincia a muoversi su una praticamente rettilinea.
Coloriamo ogni punto di partenza diversamente a seconda del numero di passi
dopo i quali la traiettoria assunta è una retta: molto probabilmente
otterremo una bella immagine frattale!
--
Francesco Trotta
http://space.tin.it/computer/ftrotta
Elimina "x_" dal mio indirizzo per mandarmi
un messaggio direttamente

semplici leggi:
Ecco cos'era quella macchia sul 5 verticale ! :) 
Eccoti la mia soluzione.
Ovviamente hai precisato che il file di informazioni si ritiene corretto ed io
ho omesso ogni controllo di errore nel mio programma d seguito :
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
static const char * MSG_ENTER = "premere ENTER per continuare ..." ;
typedef  enum  { SINISTRA, DESTRA } verso_rotazione ;
typedef  struct {  unsigned x ;
                   unsigned y ;
                   char direzione ; } formica ;
typedef  struct {  unsigned lim_inf_x ;
                   unsigned lim_inf_y ;
                   unsigned lim_sup_x ;
                   unsigned lim_sup_y ; } lim_matrice ;
void  disegna_punto ( unsigned x, unsigned y, char c, char * * mat )
{
      gotoxy ( x, y ) ;
      mat [ y-1 ] [ x-1 ] = c ;
      putch ( c ) ;
}
void  formica_ruota ( formica * f, verso_rotazione v  )
{
      switch ( f->direzione )
      {
             case 'N' : switch ( v )
                        {
                               case SINISTRA : f->direzione = 'O' ;
                                               f->x -= 1 ;
                                               break ;
                               case DESTRA   : f->direzione = 'E' ;
                                               f->x += 1 ;
                                               break ;
                        }
                        break ;
             case 'S' : switch ( v )
                        {
                               case SINISTRA : f->direzione = 'E' ;
                                               f->x += 1 ;
                                               break ;
                               case DESTRA   : f->direzione = 'O' ;
                                               f->x -= 1 ;
                                               break ;
                        }
                        break ;
             case 'E' : switch ( v )
                        {
                               case SINISTRA : f->direzione = 'N' ;
                                               f->y -= 1 ;
                                               break ;
                               case DESTRA   : f->direzione = 'S' ;
                                               f->y += 1 ;
                                               break ;
                        }
                        break ;
             case 'O' : switch ( v )
                        {
                               case SINISTRA : f->direzione = 'S' ;
                                               f->y += 1 ;
                                               break ;
                               case DESTRA   : f->direzione = 'N' ;
                                               f->y -= 1 ;
                                               break ;
                        }
                        break ;
      }
}
int  formica_nei_limiti ( formica f, lim_matrice lm )
{
     return ( (f.x >= lm.lim_inf_x) && (f.x <= lm.lim_sup_x) &&
              (f.y >= lm.lim_inf_y) && (f.y <= lm.lim_sup_y)  ) ;
}
void  formica_occupa ( formica * f, char * * mat )
{
     switch ( mat [ f->y-1 ] [ f->x-1 ] )
     {
            case '.' : disegna_punto ( f->x, f->y, 'f', mat ) ; break ;
            case '*' : disegna_punto ( f->x, f->y, 'F', mat ) ; break ;
     }
}
void  formica_rilascia ( formica * f, char * * mat )
{
      switch ( mat [ f->y-1 ] [ f->x-1 ] )
      {
             case 'f'   : disegna_punto ( f->x, f->y, '*', mat ) ;
                          formica_ruota ( f, SINISTRA ) ;
                          break ;
             case 'F'   : disegna_punto ( f->x, f->y, '.', mat ) ;
                          formica_ruota ( f, DESTRA ) ;
                          break ;
      }
}
void  disegna_matrice ( char * * mat, size_t max_x, size_t max_y )
{
      unsigned x, y ;
      for ( y = 1 ; y <= max_y ; y++ )
          for  ( x = 1 ; x <= max_x ; x++ )
          {
               gotoxy ( x, y ) ;
               putch ( mat [ y-1 ] [ x-1 ] ) ;
          }
}
void aspetta_enter()
{
     int c ;
     gotoxy(1, 24) ;
     printf(MSG_ENTER);
     while ( ( c = getchar() ) != '\n' ) ;
     gotoxy(1, 24) ; clreol() ;
}
int main( void )
{
    formica      mia_formica ;
    char         riga [81] ;
    char         start_dir ;
    char * *     matrice ;
    lim_matrice  lm ;
    FILE *       text_file ;
    unsigned     start_x ;
    unsigned     start_y;
    unsigned     x_idx ;
    unsigned     y_idx ;
    size_t       dim_y = 0 ;
    size_t       dim_x = 0 ;
    clrscr() ;
    text_file = fopen ( "condiniz.txt", "rt" ) ;
    fscanf ( text_file, " ( %u , %u ) %c ", &start_x,
                                            &start_y,
                                            &start_dir );
    fgets ( riga, 81, text_file ) ;
    dim_x = strlen ( riga ) - 1 ;
    dim_y ++ ;
    while ( fgets ( riga, 81, text_file ) ) dim_y++ ;
    lm.lim_inf_x = 1 ;
    lm.lim_inf_y = 1 ;
    lm.lim_sup_x = dim_x ;
    lm.lim_sup_y = dim_y ;
    matrice = malloc ( dim_y * sizeof ( char * ) ) ;
    for ( y_idx = 0; y_idx < dim_y; y_idx++ )
        matrice[y_idx] = malloc ( dim_x ) ;
    if ( matrice == NULL )
    {
       puts ( "\a*** memoria insufficiente ***" );
       exit ( 1 ) ;
    }
    rewind ( text_file ) ;
    fgets ( riga, 81, text_file ) ;
    for ( y_idx = 0; y_idx < dim_y ; y_idx++ )
    {
         fgets ( riga, 81, text_file ) ;
         for (x_idx = 0 ; x_idx < dim_x ; x_idx++ )
              matrice[ y_idx ][ x_idx ] = riga [ x_idx ] ;
    }
    fclose ( text_file ) ;
    disegna_matrice ( matrice, dim_x, dim_y ) ;
    mia_formica.x = start_x ;
    mia_formica.y = start_y ;
    mia_formica.direzione = start_dir ;
    while ( formica_nei_limiti ( mia_formica, lm ) )
    {
       formica_occupa ( &mia_formica, matrice ) ;
       aspetta_enter() ;
       formica_rilascia ( &mia_formica, matrice ) ;
    }
    for ( y_idx = 0; y_idx < dim_y; y_idx++ )
        free( matrice[y_idx] ) ;
    free ( matrice ) ;
    return 0 ;
}
Ho testato il codice con "condiniz.txt" contenente le seguenti righe :
(15,7) E
..*..***.*.***.**.**
.***.**.**...**.*..*
...**.*..*...**.*..*
...**.*..***.***...*
......**.....**.*..*
**.**.**.*..*..***.*
...**.*..****.....*.
...***..*.***.....*.
*****...*...*..***.*
**....***.***.....*.
E mi sembra che funzioni bene...
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

otterremo una bella immagine frattale!
Molto probabilmente no ;)
Le immagini frattali nascono sul piano complesso e sono ben altra cosa ;)


Le immagini frattali nascono sul piano complesso e sono ben altra cosa ;)
Non ho una esperienza molto approfondita in materia, ma ci provo ugualmente
(non me ne vogliano Mandelbrot, Julia e Lorentz).
L'unico problema su cui però non avevo posto sufficiente attenzione è la non
ricorsività della trasformazione. Potresti però modificare il problema in
modo che la formichina si comporti alla stessa maniera, utilizzando però una
trasformazione ricorsiva. Il problema non sarebbe però più lo stesso :-)
Ogni volta che mi trovo su un piano e fisso le coordinate di un punto, che
sia il punto di partenza dalla formichina o che sia un'altra qualsiasi
coppia di numeri, le due coordinate posso vederle come i coefficienti di
parte reale e complessa di un numero complesso.
Forse sto dicendo tante cavolate o forse no: sarebbero da provare. Se poi mi
dici che sei un matematico che si occupa da anni dell'argomento... :-)
Scherzi a parte, mi sono permesso, sono indecentemente OT, ma prometto di
non farlo più.


parte reale e complessa di un numero complesso.
Il problema di fondo e' la cosiddetta densita' del piano su cui la formica si
muove.
Il comportamento della formica di Langton e' interessante proprio perche' si
muove su una specie di scacchiera (La cui densita' di punti e' pertanto finita).
Anche estendendo la scacchiera all'infinito non si raggiungerebbe lo scopo.
Perche' si estenderebbe il numero di punti, ma non la loro densita'.
La figura che puo' nascere puo' avere un bel disegno, ma possiede, comunque, un
livello di dettaglio finito, dato che la formica si muove su uno spazio
limitato.
Le immagini frattali, invece, nascono da operazioni tra punti del piano
complesso.
Cio' che rende un'immagine "frattale" e' la caratteristica di dettaglio
infinito.
Questo significa che si puo' considerare una porzione sempre piu' piccola della
figura, la quale avra' un livello di dettaglio pari alla figura originale.
E questo all'infinito.
Spesso, poi, (vedi l'insieme di Mandelbrot), le figure posseggono la
caratteristica della "Self Similarity", cioe' un dettaglio che riproduce
l'intera figura e che puo' avere, a sua volta, una caratteristica del genere...
L'esempio tipico e' quello di un albero, in cui la stessa caratteristica di
ramificazione puo' essere vista come una generazione frattale...
Il DNA della pianta, essendo limitato nella sua capacita' di memorizzazione,
probabilmente conserva informazioni tali, da suscitare una generazione ricorsiva
dei rami o delle foglie.
Ma, adesso, siamo veramente OT ! dal C alla botanica !!! :)


 otterremo una bella immagine frattale!
Può essere. Comunque bisogna precisare che la retta non è in realtà
'retta' ma è una traiettoria a zig-zag che in media sembra una retta ed
è comunque visibilmente più regolare di quella caotica iniziale.
EMG

 Le immagini frattali nascono sul piano complesso e sono ben altra cosa ;)
A me sembra che possano nascere in qualunque piano cartesiano quando la
dipendenza tra le due variabili sia di tipo 'caotico' e che generalmente
č molto facile che le frontiere dei due insiemi in cui il comportamento
č caotico e non sia una 'curva' frattale.
EMG

Ma, adesso, siamo veramente OT ! dal C alla botanica !!! :)
Non so poi quanto siamo OT. Sono problemi strettamente correlati
all'utilizzo del computer, che, anzi, senza quest'ultimo, sarebbero rimaste
ad uno stato embrionale (si pensi a fare manualmente la stessa
trasformazione ricorsiva alla base del frattale di Mandelbrot z(n+1) =
z(n)^2 + z(0)!). Dato che molti in questa lista amano definire il C "_IL_
linguaggio di programmazione", quale newsgroup sarebbe più adatto?
A questo proposito, ho visto che qualcuno ha già realizzato qualcosa, ma non
utilizzando la modalità grafica. Sbaglio?
Saluti


h caotico e non sia una 'curva' frattale.
Se intendi per piano cartesiano un prodotto cartesiano del tipo RxR (con R
insieme dei numeri reali) allora siamo d'accordo.
Ma nel caso dell'esempio della formica, essa si muove su un piano che e'
prodotto cartesiano di due insiemi numerabili.
L'immagine che produce con il suo percorso puo' avere un aspetto caotico ma non
di certo frattale.
La caratteristica di un'immagine frattale e', per l'appunto, quella di essere
infinitamente dettagliata.
In parole povere, non trovo punti coperti dalla formica, se considero un intorno
(contenuto in RxR) di ogni sua posizione.


linguaggio di programmazione", quale newsgroup sarebbe piy adatto?
Forse uno che tratti di grafica e/o algoritmi ? ;)


 (contenuto in RxR) di ogni sua posizione.
Si, questo è giusto. Però mi sembra che si parlasse non della eventuale
frattalità della traiettoria della formica bensì dell'insieme ottenibile
facendo partire la formica con valori diversi (non ricordo ora
esattamente i termini della questione). E se questi valori iniziali sono
reali ecco che ricadiamo nel piano RxR, giusto?
EMG

 Certo, su questo siamo assolutamente d'accordo.
In realtà mi pare di ricordare che i matematici più addentro
dell'argomento conoscessero già le proprietà dei frattali e ne
immaginassero anche la bellezza estetica prima che il computer ne
permettesse l'apprezzamento anche ai profani.
EMG

permettesse l'apprezzamento anche ai profani.
Non credo, il termine "frattale" stesso nasce con Benoit Mandelbrot, ovvero
nasce su un computer.


reali ecco che ricadiamo nel piano RxR, giusto?
Il problema e' che non so quanto sia compatibile il movimento della formica di
Langton con un piano reale.
La particolarita' del movimento della formica e' causato dal fatto di muoversi
su una specie di scacchiera, come ho gia' detto, in cui i punti investiti sono
equidistanti sia in verticale che in orizzontale.
Difatti, nel piano reale, come si fa a stabilire quale sia il punto (x-a, y)
rispetto a (x, y) ?
Bisognerebbe stabilire un'unita' di misura, ma stabilendo un'unita' di misura si
perde il legame con la natura frattale dell'immagine generata, in quanto
verrebbero saltate tutte le posizioni distanti dal punto in cui la formica si
trova di una distanza sottomultipla di "a" unita' di misura.
Piu' che altro, se e' vero che la formica, da un certo punto in poi, comincia a
muoversi in modo pressoche' rettilineo, si puo' ipotizzare che la sua traettoria
sia una specie di attrattore che costringe la formica a restare sempre in un
determinato spazio.
Anche se, per esempio, nell'attrattore di Lorenz lo spazio e' limitato.


 nasce su un computer.
Boh. Eppure sono quasi sicuro di aver letto una cosa del genere parecchi
anni fa...
EMG
PS. Come mai nei tuoi messaggi di risposta non vedo piů le mie
accentate?