Homework (compito per casa) 1

Il gioco Alto/Basso (ricerca binaria)

Vedi anche: DomandeHomework1, SoluzioneHomework1, RisultatiHomework1

---

---

Descrizione

Il gioco che dovete implementare è il gioco "Alto/Basso", in cui chi gioca deve indovinare il numero pensato dall'avversario con il minor numero di tentativi. L'avversario (io) conosce il numero e per ogni tentativo risponde solo alto o basso o indovinato.

Esiste una strategia ottima che permette di indovinare il numero con un massimo di log(N) tentativi (dove N è il numero di possibili valori).

Voi dovete implementare la strategia ottima che consiste in:

• proporre il numero mediano del'intervallo di numeri "possibili"
• usare la risposta (alto/basso) per ridurre l'intervallo opportunamente
• ritentare.

L'intervallo di numeri in cui io sceglierò quello da indovinare va da 0 a 1000 compresi.

Descrizione in pseudocodice

Il vostro programma deve:

1. definire le variabili
2. inizializzare le variabili che rappresentano l'intervallo 0-1000
3. eseguire l'istruzione setvbuf (vedi la nota sotto)
4. ripetere fintanto che l'intervallo di valori "possibili" contiene più di 1 elemento
   1. calcolare il valor medio dell'intervallo
   2. proporre il valore
   3. leggere la risposta
   4. se la risposta è 0
      1. ha indovinato ed esce dal programma
      2. altrimenti se la risposta è ---+1
         1. il numero da indovinare è maggiore e deve aggiornare l'estremo inferiore dell'intervallo con il valore appena proposto più 1
         2. altrimenti (la risposta è -1), il numero da indovinare è minore e deve aggiornare l'estremo superiore dell'intervallo con il valore appena proposto meno 1
5. se si arriva qui vuol dire che l'intervallo contiene ora un solo valore, che va proposto
6. si legge la risposta (che sarà 0)
7. esce

Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!

Input

Il vostro programma riceve in input per ciascun tentativo uno dei tre valori

• ---+1 (ovvero il numero da indovinare è maggiore)
• 0 (ovvero avete indovinato il numero)
• -1 (ovvero il numero da indovinare è minore)

Output

Il vostro programma deve proporre ciascun tentativo come un numero intero seguito da accapo. Questo si ottiene usando l'istruzione

   printf("%d\n",tentativo);

ATTENZIONE

Vi chiedo di inserire nel programma, subito dopo le dichiarazioni delle variabili la istruzione seguente:

   setvbuf(stdout, NULL, _IONBF, 0);

Questa istruzione mi permette di provare il vostro programma automaticamente.

ATTENZIONE Senza di essa il programma funziona correttamante da tastiera ma non funziona quando lo controllo automaticamente (e voi perdete i punti).

Come compilare ed eseguire il programma

• usate un editor per scrivere il testo del programma e salvatelo in formato testo semplice in un file con l'estensione .c (ad esempio di nome indovina.c)
  • NON usate Word, Openoffice, Kword, Abiword che introducono caratteri strani
• compilate (e contemporaneamente linkate) il programma con il comando

gcc -g -o indovina indovina.c

• eseguite il programma scrivendo

./indovina

Esempio di input/output

Se eseguite il programma e pensate il numero 311 l'input e l'output saranno (in rosso l'input battuto da voi per il programma)

./indovina
500
-1
249
---+1
374
-1
311
0

Versione un pelino più difficile

Chi vuole può implementare una versione appena un pelino più difficile che, prima di iniziare i tentativi, legge da input i due numeri interi che indicano il minimo ed il massimo dell'intervallo dei possibili valori da considerare.

• prima il minimo
• poi il massimo

Come consegnare il programma

• Avete tempo fino a Domenica 26 Ottobre alle ore 24.00 (ora sono le 23:13 del 23).
• Consegnate il testo del programma sorgente C da voi scritto. Io lo compilerò e testerò.
• Usate esclusivamente la pagina di consegna. Non verranno accettate spedizioni via email.

-- AndreaSterbini - 10 Oct 2003

• Set ALLOWTOPICCHANGE = DocentiProg1Group