istruzioni

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
delfo52
Livello 9
Livello 9
Messaggi: 1379
Iscritto il: mer mag 25, 2005 3:19 pm
Località: bologna

istruzioni

Messaggio da delfo52 » dom gen 15, 2006 12:10 am

ho trascorso le vacanze natalizie in giro per la Campania con una comitiva di amici camperisti.
Il mondo dei camperisti è un mondo che va accettato e non giudicato, ma che può essere fonte di perplessità matematiche: vado a spiegarmi.
La nostra "carovana " era composta da 29 camper, tutti numerati in modo chiaro e ben visibile sia sul parabrezza anteriore che sul retro.
Quando il serpentone dei mezzi si mette in moto per trasferirsi da una località ad un'altra, accade sempre che, per ingorghi, o per errori, o per chissà quale motivo, l'ordine numerico tende a perdersi, per cui, ad un certo punto, magari in autostrada, si rende necessario "riordinare le fila".
Tenete presente che i vari equipaggi sono in contatto radio con i cosiddetti "baracchini" che sono radio (non chiedetemi specifiche tecniche) con cui è possibile parlarsi e darsi indicazioni varie.
Orbene: avendo una serie di camper numerati da 1 a 29, in ordine sparso, per tornare alla serie ordinata, quale tipo di "istruzioni" è opportuno dare ai vari mezzi ?
L'ordine "se il mezzo davanti a te ha un numero superiore al tuo, sorpassalo" porta al risultato richiesto? sempre? è quello con cui si ottiene l'ordinamento corretto nel minor tempo possibile?
sarebbe gradita la simulazione su PC.
P.S.
per farmi perdonare, vi racconto questa; che ho appreso nel corso delle peregrinazioni nella MAPS sorrentina.
In visita ad una distilleria di "limoncello" ho pensato di fare una domanda "intelligente e imbarazzante"chiedendo ragione del boom e della diffusione esponenziale di tale prodotto negli ultimi anni: la disponibilità della materia prima (cioè dei limoni) non è un problema?
Ho imparato che il problema non si pone; se in passato la produzione era molto più limitata, la ragione stava nella produzione "casalinga" consentita dalla possibilità di distillare in casa, ad ogni vendemmia, il vino rimasto dall'anno precedente. se ne otteneva una quantità di alcool molto ridotto con cui si produceva una piccola quantità di infuso di scorza di limone ad uso esclusivamente familiare.
Da quando la distillazione in casa è stata proibita, l'alcool bisogna comprarlo, ma a questo punto, la disponobiltà è pressochè illimitata. Dal momento che la produzione di limoni è più o meno continua nei dodici mesi (salvo oscillazioni nella qualità), da allora è possibile (e facile) produrre quantità esagerate di liquore, e invadere il mercato: il problema non erano i limoni, ma l'alcool !!!!
Enrico

Pasquale
Livello 11
Livello 11
Messaggi: 2333
Iscritto il: mer mag 25, 2005 1:14 am

Messaggio da Pasquale » lun gen 16, 2006 12:54 am

Il caso più sfavorevole è quello del disordine "ordinato" dal 29 all'1.
Spero che non vi venga in mente veramente di riordinare la colonna sull'autostrada, perchè penso che sarebbe una bomba ad orologeria.
Comunque, nel caso specifico, darei disposizione ad ogni camper, in ordine crescente, a partire dal n.1, di sorpassare tutti i camper con numero maggiore, cioè 28; poi toccherebbe al n.2, etc., per un totale di 28 operazioni di ordinamento.
In genere, con questo sistema, per ordinare n elementi sono necessarie n-1 operazioni, per essere sicuri del risultato: secondo il disordine iniziale, è possibile anche che con un numero inferiore di operazioni si raggiunga l'ordine voluto, ma dovendo impostare un programma, è necessario prevedere tutte le n-1 operazioni.
Nel caso della colonna di camper, siccome non credo che il disordine capovolga completamente l'ordine iniziale, non vedo altri sistemi:

avanti il n.1, avverti quando hai finito (ho finito)
avanti il n.2, avverti quando hai finito (ho finito)
avanti il 3, avverti quando hai finito (davanti ho il 2)
allora avanti il 4.......
etc.

Con Decimal Basic:

DIM a(29)
DATA 29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
FOR m=1 TO 29
READ a(m)
NEXT M
FOR p=1 TO 28
FOR m=2 TO 30-p
IF a(m)<a(m-1) THEN swap a(m),a(m-1)
NEXT M
NEXT P
FOR m=1 TO 29
PRINT a(m);
next M
END

(se invece di FOR p=1 to 28, usiamo FOR p=1 to x, con x<28, vediamo che l'ordinamento non si completa)

PROBLEMA: ammesso che la velocità di crociera sia di 80 Km orari, che tutti i camper mantengano una distanza di sicurezza di 100m, procedano dal n. 29 al n.1 e che non vi siano altri automezzi in circolazione, quanti chilometri avrà percorso il camper n.29 dall'inizio al termine delle operazioni di riordinamento secondo il criterio di cui sopra?
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Messaggio da ZioGiò » lun gen 16, 2006 9:35 pm

L'ordine "se il mezzo davanti a te ha un numero superiore al tuo, sorpassalo" porta al risultato richiesto?
In effetti l'istruzione "se il mezzo davanti a te (se esiste, cioè se non sto considerando un camper in testa alla carovana) ha un numero superiore al tuo, sorpassalo" sembra essere sufficiente, a patto che, una volta effettuato lo scambio, si controlli ulteriormente il camper che ha effettuato il sorpasso. Il modo migliore per evidenziare questa istruzione è una funzione ricorsiva che fa proprio quanto detto a parole. Ah, è inoltre conveniente partire a controllare dal secondo camper in coda...

tradotto in linguaggio C:

Codice: Seleziona tutto

void ordina(int n){
     //Funzione che scambia due valori tra loro
     void scambia(int p, int n);
     
     //si è raggiunta la fine della carovana e gli elementi sono sicuramente ordinati
     if(n == NUM){
	      return;
     }
     
     //Si è raggiunta la cima della lista e quindi il arr[0] è sicuramente minore di arr[1]
     //Porto avanti il controllo direttamente a arr[2]
     if(n == 0){
         n = 2; 
     }

     //arr[n] è minore di arr[n - 1]
     if(arr[n] < arr[n - 1]){
	     scambia(n, n - 1);
	     ordina(n - 1);
	     return;
     }
     
     //arr[n] è maggiore di arr[n - 1]
     ordina(n+1);
     return;
}
Questa funzione ricorsiva sembra effettuare lo stesso numero di scambi della funzione proposta dal buon Pasquale, in quanto il movimento massimo consentito è di +1 nella carovana. E' probabile però che con una carovana molto lunga la ricorsività permetta di evitare alcuni scambi. Questo risponde alla seconda domanda:
è quello con cui si ottiene l'ordinamento corretto nel minor tempo possibile?
L'ordinamento più efficiente, secondo me, si avrebbe osservando l'intera carovana, prendendo il camper con il numero più basso e spostandolo in cima alla carovana (col teletrasporto? :)) e considerando la nuova carovana senza il primo elemento e ripetendo queste istruzioni fino ad arrivare a considerare l'ultimo camper.

Includo qui sotto il sorgente di un codice C che accetta NUM campers del quale l'utente inserisce il numerino e li ordina con i due metodi proposti, tracciando il numero di passaggi.
Non sono in grado di fare una stima della memoria utilizzata da ordina() e ordinaNon() ma, mi sembra di ricordare, in generale una funzione ricorsiva usa meno memoria di un ciclo for.
La versione eseguibile (su windows) potete trovarla qui:
http://www.lyra.net/camper.exe
ridotta a 7 elementi (altrimenti inserirli tutti è una noia!)
Ah, a causa della compatibilità del compilatore, una volta scaricato l'eseguibile, è necessario lanciarlo dal DOS:
- aprire ms dos
- entrare nella cartella in cui risiede l'eseguibile (ad esempio con l'istruzione "cd cartellaCamper")
- scrivere camper (senza estensione) e premere invio

Se trovate errori/miglioramenti scrivete!!!

Codice: Seleziona tutto

#include <stdio.h>
//numero totale di veicoli
//Devo definirlo in cima altrimenti mi toccherebbe usare le liste dinamiche per gestire l'array di valori
#define NUM 30 

//Utilizzo una variabile globale (è più comodo di un puntatore) anche se meno "elegante"
int arr[NUM]; 
int i, j, numScambi = 0;
//Copia di arr
int arr2[NUM]; 

main(){
       //Prototipi delle funzioni
       //Riempio l'array coi valori "casuali" inseriti dall'utente
       void askValue(); 
       //Visualizza il contenuto dell'array
       void visualizza();
       //controlla che la somma dei valori contenuti nell'array sia la sommatoria per i che va da 1 a NUM di i
       //Questo per evitare che l'utente inserisca come numeri di ordinamento 1 3 4.
       int controllaValori(); 
       //ordina l'array (funzione ricorsiva)
       void ordina(int n);
       //ordina l'array (non ricorsiva)
       void ordinaNon();

       askValue();
       //Memorizzo una copia dei valori inseriti 
       for(i = 0; i < NUM; i++){
             arr2[i] = arr[i];
       }
       //Visualizza la carovana "disordinata"
       printf("\nI numeri dei camper inseriti sono:\n");
       visualizza(); 
       if(controllaValori() == 0){
            //PARTE CHE UTILIZZA LA FUNZIONE RICORSIVA
            //Inizio a controllare i dati dal secondo elemento della lista
            ordina(1); 
            printf("----------\nI numeri dei camper in fila sono:\n");
            //visualizza (se il programma funziona) la carovana ordinata
            visualizza(); 
            printf("\nNumero scambi effettuati: %d\n----------\n", numScambi);
            
            //PARTE CHE UTILIZZA LA FUNZIONE NON RICORSIVA
            //Riprendo l'array inserito
            for(i = 0; i < NUM; i++){
                  arr[i] = arr2[i];
            }
            numScambi = 0;
            ordinaNon();
            printf("I numeri dei camper in fila sono:\n");
            visualizza();
            printf("\nNumero scambi effettuati: %d\n", numScambi);
       } else {
             printf("I valori inseriti non sono validi per questo tipo di problema");
       }
}

void askValue(){
     printf("Numero di veicoli: %d\n", NUM);
     for(i = 0; i < NUM; i++){
           printf("- Inserisci il numero del camper di posto %d: ", i+1);
           scanf("%d", &arr[i]);
     }
}

void ordinaNon(){
     void scambia(int p, int n);
     for(i = 0; i < NUM - 1; i++){
           for(j = 1; j < NUM - i; j++){
                if(arr[j] < arr[j-1])
                    scambia(j, j - 1);
           }
     }
}

int controllaValori(){
     int somma = 0, verifica = 0, max = 0;
     for(i = 0; i < NUM; i++){
           somma = somma + arr[i];
           verifica = verifica + i + 1;
     }
     
     //trovo il massimo
     for(i = 0; i < NUM; i++){
           if(arr[i]> max)
                max = arr[i];
     }
     
     if(verifica == somma && max == NUM)
          return(0);
     return(1);
}

void visualizza(){
     for(i = 0; i < NUM; i++){
           //Controllo se aggiungere il - finale o no
           if(i != NUM-1)
                printf("%d - ", arr[i]);
           else
               printf("%d\n", arr[i]);
     }
}

void ordina(int n){
     //Funzione che scambia due valori tra loro
     void scambia(int p, int n);
     
     //si è raggiunta la fine della carovana e gli elementi sono sicuramente ordinati
     if(n == NUM){
	      return;
     }
     
     //Si è raggiunta la cima della lista e quindi il arr[0] è sicuramente minore di arr[1]
     //Porto avanti il controllo direttamente a arr[2]
     if(n == 0){
         n = 2; 
     }
     
     //Caso in cui i numeri arr[n] e arr[n-1] sono esattamente successivi (con arr[n] > arr[n-1])
     //Sposto i controlli al numero seguente
     /*if(arr[n] == arr[n-1] + 1){ 
         ordina(n+1);
         return;
     }*/

     //arr[n] è minore di arr[n - 1]
     if(arr[n] < arr[n - 1]){
	     scambia(n, n - 1);
	     ordina(n - 1);
	     return;
     }
     
     //arr[n] è maggiore di arr[n - 1]
     ordina(n+1);
     return;
}

void scambia(int a, int b){
     //Per visualizzare i passaggi intermedi decommentare le seguenti due linee
     //printf("Passaggio intermedio: \n");
     //visualizza();
     int tmp;
     tmp = arr[a];
     arr[a] = arr[b];
     arr[b] = tmp;
     numScambi++;
     return;
}
Saluti
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

delfo52
Livello 9
Livello 9
Messaggi: 1379
Iscritto il: mer mag 25, 2005 3:19 pm
Località: bologna

Messaggio da delfo52 » lun gen 16, 2006 10:16 pm

grazie per i contributi, di cui farò certamente uso nei prossimi viaggi (non è vero, ma lo dico per titillare il vostro ego).
In realtà il vero, grosso problema, si verifica quando qualche mezzo non è più "a vista" rispetto agli altri. In questa situazione, si può avere l'impressione di essere "davanti a tutti", e magari non è vero; lo stesso per la coda...
Che fare per accertare le cose?
La proposta che faccio è praticabile su strade o autostrade dotate di regolare segnaletica chilometrica. Chi crede di essere in testa al gruppo, anzi "in fuga", cioè non a contatto visivo con chi lo segue, dichiara alla radio , in diretta, a quale Km della strada sta transitando: se qualcuno risulta più avanti di lui, si ripete la procedura. Lo stesso per la coda degli automezzi.
Avete proposte migliorative?
Enrico

Pasquale
Livello 11
Livello 11
Messaggi: 2333
Iscritto il: mer mag 25, 2005 1:14 am

Messaggio da Pasquale » gio gen 19, 2006 3:04 am

Una soluzione è quella di darsi appuntamento ogni x chilometri, ad esempio alla tale area di servizio, in modo da potersi riposare, rifocillare, controllare, aspettare i ritardatari, prendere nuovi accordi, etc. : è chiaro che tutti devono conoscere l'itinerario, o deve eserci qualcuno che lo spiega.
La carovana può essere suddivisa in sottocarovane che attuano la stessa strategia e tutta la carovana si ritrova in un punto più lontano, se non alla destinazione finale (dipende dai chilometri che bisogna percorrere).
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi