Home Introduzione News Lezioni e laboratorio Programma Esame Esoneri Materiale Progetti studenti Forum studenti Link Home docente

 

Algoritmo A4

Gioco "alto-basso"

(convenzioni di scrittura)

1. Input(max)
2. tentativi = 0
3. primo = 1
4. ultimo = M
5. primo è <= ultimo ?
   5.1 Se sì:
      5.1.1 media = (primo + ultimo) / 2
      5.1.2 Output(media)
      5.1.3 tentativi = tentativi + 1
      5.1.4 Input(risposta) // 'a'=alto, 'b'=basso, 'u'=ok
      5.1.5 risposta è = 'u' ?
         5.1.5.1 Se sì:
            5.1.5.1.1 Output(tentativi)
            5.1.5.1.2 Stop
         5.1.5.2 Se no:
            5.1.5.2.1 risposta è = 'a' ?
               5.1.5.2.1.1 Se sì:
                  5.1.5.2.1.1.1 ultimo = media - 1
                  5.1.5.2.1.1.2 vai al passo 5
               5.1.5.2.1.2 Se no: // allora risposta è = 'b'
                  5.1.5.2.1.2.1 primo = media + 1
                  5.1.5.2.1.2.2 vai al passo 5
   5.2 Se no:
      5.2.1 Output("errore!!")
      5.2.2 Stop

Commenti

Il gioco consiste nel tentativo, da parte dell'algoritmo, di indovinare un numero segreto pensato da un avversario. Il numero, da 1 a un certo valore scelto dall'avversario all'inizio del gioco, e memorizzato nella variabile max, viene individuato attraverso una serie di tentativi dell'algoritmo, che propone delle soluzioni e riceve dall'avversario, per ciascuna soluzione proposta, un risposta fra tre possibili: alto (il numero proposto è troppo alto), basso (troppo basso), uguale (indovinato).

La ricerca del valore da indovinare viene eseguita con l'algoritmo della ricerca binaria o dicotomica.

L'algoritmo impiega al più |log2max| + 1 tentativi per individuare il valore pensato. Ad esempio, se il max viene fissato a 1000000, l'algoritmo impiegherà al più 20 tentativi.

Questa è la bacheca di Informatica Grafica, corso di laurea specialistica in Ing. Edile-architettura
by FdA
ultima modifica: 02/02/2005 11.30