Newsgroup: it.comp.lang.c
Titolo: Problema degli esagoni

Salve a tutti, e' la prima volta che scrivo a una newsgroup e vi ringrazio
anticipatamente per l'aiuto che mi potrete dare per questo problema di
programmazione.(premetto che sono al primo anno del diploma di informatica e
che per ora so programmare modestamente in C).
Il problema in questione e' un quesito fatto al campionato mondiale di
programmazione delle universita' organizzato dall'IBM:
Ho una mappa a caselle esagonali, e ho 10000 caselle costruite cosi', la
prima e' a caso e rappresenta il numero uno, la seconda nella faccia
inferiore della prima rappresenta il numero 2 in senso orario nelle caselle
a fianco al numero 1 si mettono i numeri 3...7, completati i sei esagoni
attorno al numero 1  sotto l'esagono del numero 7 si mette il numero 8 e
sempre in senso orario si mettono gli altri dodici elementi etc. etc. fino
al 10000 elemento. Ora il problema e' presi due numeri a caso calcolare il
percorso minimo di esagoni che li unisce.(se mi potreste consigliare una
strategia vi sarei grato)
                                        Grazie

strategia vi sarei grato)
Non so se sia la strategia migliore, pero' ho pensato di realizzare
cosi' il programma :
Innanzitutto rappresentare la mappa esagonale con un vettore di
posizioni del tipo :
typedef struct { short x, y ; } esagono_t ;
static esagono_t cella[10000] ;
/* le celle vengono numerate, per comodita' a cominciare da 0 anziche'
da 1 */
Le posizioni vengono inizializzate seguendo lo schema a spirale.
Cioe' cella = { {0,0}, {-1,+1}, {-2,0}, {-1,-1}, {0, -1}, ... }
Ovviamente per l'inizializzazione si utilizza un ciclo che agisce
secondo un certo criterio (che credo d'aver trovato).
Date le coordinate di entrambe le celle di partenza, si determina la
cella la cui distanza e' media dall'una e dall'altra cella.
A questo punto si applica lo stesso procedimento in via ricorsiva,
considerando la prima cella e la cella trovata e in seguito la cella
trovata e la seconda cella.
In questo modo, salvando di volta in volta le celle trovate in una
lista, nell'ordine, si ottiene il percorso minimo dalla prima cella
alla seconda.
Non so se la mia spiegazione e' chiara, ma comunque sto realizzando il
programma in C.

 programma in C.
Non avevamo dubbi! ;-)
-- 
 Reply to 
luca....@tiscalinet.it

Non avevamo dubbi! ;-)
;)
/*
 * Soluzione al problema degli esagoni
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 10000
#define SINISTRA_BASSO  0
#define SINISTRA        1
#define SINISTRA_ALTO   2
#define DESTRA_ALTO     3
#define DESTRA          4
#define DESTRA_BASSO    5
typedef struct { short x, y ; } cella_t ;
typedef struct tag_cella {
                            unsigned indice_cella ;
                            struct tag_cella * prossimo ;
                         } * cella_p ;
static const cella_t incremento [6] =
{ {-1, -1}, {-2, 0}, {-1,+1}, {+1,+1}, {+2, 0}, {+1, -1} } ;
/* variabili globali */
static unsigned cont_locale = 0 ;
static unsigned indice = 0 ;
static unsigned direzione = SINISTRA_BASSO ;
static cella_p  testa_percorso = NULL ;
static cella_t cella [MAX] ;
static unsigned livello ( void )
{
   return ( indice / 6 + ( ( indice % 6 ) != 1 ) ) ;
}
static void cambia_direzione ( void )
{
       direzione = ( direzione == DESTRA_BASSO ) ?
                   ( SINISTRA_BASSO ) :
                   ( direzione + 1 ) ;
}
static void calcola_prossimo ( cella_t * c )
{
       if ( cont_locale == livello() )
       {
          cont_locale = 0 ;
          cambia_direzione() ;
          ++indice ;
          calcola_prossimo( c ) ;
       }
       else
       {
          c->x += incremento [ direzione ].x ;
          c->y += incremento [ direzione ].y ;
          ++cont_locale ;
       }
}
static double distanza ( const unsigned indice1,
                         const unsigned indice2 )
{
       return ( sqrt (pow(cella[indice1].x-cella[indice2].x, 2.0) +
                      pow(cella[indice1].y-cella[indice2].y, 2.0)) ) ;
}
static void inizializza_celle ( void )
{
    unsigned i ;
    cella_t C = { 0, 0 } ;
    for ( i = 0 ; i < MAX ; i++ )
    {
        cella[i] = C ;
        calcola_prossimo( &C ) ;
    }
}
static int adiacenti ( const unsigned indice1,
                       const unsigned indice2 )
{
       double ST2 = sqrt( 2.0 ), d = distanza( indice1, indice2 ) ;
       return ( (d <= ST2 ) ||
                ((d == 2.0) &&
                 (cella[indice1].y == cella[indice2].y)) ) ;
}
static unsigned cella_distanza_media ( const unsigned indice1,
                                       const unsigned indice2 )
{
       double d = distanza( indice1, indice2  ) / 2, dm, m = MAX ;
       unsigned i, p ;
       for ( i = 0 ; i < MAX ; i++ )
           if ( ( i != indice1 ) && ( i != indice2 ) )
           {
              dm = ( distanza( indice1, i ) +
                     distanza( i, indice2 ) ) / 2 ;
              if ( dm - d < m )
              {
                 m = dm - d ;
                 p = i ;
              }
           }
       return p ;
}
void inserisci_celle_limite( const unsigned i1, const unsigned i2 )
{
     testa_percorso = malloc ( sizeof *testa_percorso ) ;
     testa_percorso->prossimo = malloc ( sizeof *testa_percorso ) ;
     testa_percorso->prossimo->prossimo = NULL ;
     testa_percorso->indice_cella = i1 ;
     testa_percorso->prossimo->indice_cella = i2 ;
}
void inserisci_cella ( const unsigned i1, const unsigned i )
{
     cella_p cursore = testa_percorso, temp, p ;
     while ( cursore->indice_cella != i1 )
           cursore = cursore->prossimo ;
     p = cursore->prossimo ;
     temp = malloc ( sizeof *temp ) ;
     temp->indice_cella = i ;
     cursore->prossimo = temp ;
     temp->prossimo = p ;
}
static void scrivi_percorso ( void )
{
     cella_p cursore = testa_percorso ;
     while ( cursore->prossimo != NULL )
     {
           printf ( "%d ->", cursore->indice_cella+1 ) ;
           cursore = cursore->prossimo ;
     }
     printf ( "%d\n", cursore->indice_cella+1 ) ;
}
static void segna_percorso( unsigned indice1, unsigned indice2 )
{
       unsigned indice_cella ;
       if (!adiacenti( indice1, indice2 ))
       {
          indice_cella = cella_distanza_media( indice1,
                                               indice2 ) ;
          inserisci_cella ( indice1, indice_cella ) ;
          segna_percorso( indice1, indice_cella ) ;
          segna_percorso( indice_cella, indice2 ) ;
       }
}
int main( void )
{
    unsigned nA, nB ;
    inizializza_celle() ;
    printf( "prima cella : " ) ; scanf ( "%u", &nA ) ;
    printf( "seconda cella : " ) ; scanf ( "%u", &nB ) ;
    inserisci_celle_limite( nA-1, nB-1 ) ;
    segna_percorso ( nA-1, nB-1 ) ;
    puts( "percorso minimo :" ) ;
    scrivi_percorso() ;
    return 0 ;
}