Tags:
create new tag
view all tags

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! frown

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 22:40 del 02).
  • 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

Edit | Attach | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r4 - 2003-10-15 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback