HomeWork1 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Homework (compito per casa) 1 
---++ Il gioco Alto/Basso (ricerca binaria)

Vedi anche: DomandeHomework1, SoluzioneHomework1, RisultatiHomework1
----
%TOC%
----

---+++ 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
   1 inizializzare le variabili che rappresentano l'intervallo 0-1000
   1 eseguire l'istruzione *setvbuf* (vedi la nota [[#ATTENZIONE][sotto]])
   1 ripetere fintanto che l'intervallo di valori "possibili" contiene più di 1 elemento
      1 calcolare il valor medio dell'intervallo
      1 proporre il valore
      1 leggere la risposta
      1 se la risposta è 0
         1 ha indovinato ed esce dal programma
         1 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
            1 altrimenti (la risposta è -1), il numero da indovinare è *minore* e deve aggiornare l'estremo superiore dell'intervallo con il valore appena proposto meno 1
   1 se si arriva qui vuol dire che l'intervallo contiene ora un solo valore, che va proposto
   1 %RED%si legge la risposta (che sarà 0)%FINE%
   1 esce

__%RED%Attenzione%FINE%__ 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
<pre style='background:lightgrey'>
   printf("%d\n",tentativo);
</pre>

---++++ ATTENZIONE
Vi chiedo di inserire nel programma, *subito dopo le dichiarazioni delle variabili* la istruzione seguente:
<pre style='background:lightgrey'>
   setvbuf(stdout, NULL, _IONBF, 0);
</pre>
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
<pre style='background:lightgrey'>
gcc -g -o indovina indovina.c
</pre>
   * eseguite il programma scrivendo
<pre style='background:lightgrey'>
./indovina
</pre>

---+++ 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)
<pre style='background:lightgrey'>
%RED%./indovina%FINE%
500
%RED%-1%FINE%
249
%RED%---+1%FINE%
374
%RED%-1%FINE%
311
%RED%0%FINE%
</pre>

---+++ 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 *%RED%Domenica 26 Ottobre alle ore 24.00%FINE%* (ora sono le *%SERVERTIME{"$hou:$min del $day"}%*).
   * Consegnate *il testo del programma sorgente C* da voi scritto. Io lo compilerò e testerò.
   * Usate *esclusivamente* la <a href="/~andrea/consegna.html">pagina di consegna</a>. Non verranno accettate spedizioni via email.

-- Users.AndreaSterbini - 10 Oct 2003

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group