Harvard CS50: Compiti della settimana 3 (lezioni 7 e 8), parte 2

Lezioni sui fondamenti di programmazione di Harvard CS50 Materiali aggiuntivi: notazione asintotica, algoritmi di ordinamento e ricerca Compiti della settimana 3, parte 1. Ordinamento e ricerca.

Il gioco inizia!

È ora di giocare! La maggior parte delle persone ha familiarità con il gioco puzzle "Tag". Per formalizzarlo, “Tag” è un campo bidimensionale 4x4, in questo campo non ci sono 16, ma 15 quadrati, cioè uno slot rimane vuoto. Ciascuno dei quadrati è numerato e può muoversi orizzontalmente o verticalmente all'interno del campo (se, ovviamente, c'è spazio per muoversi). L'obiettivo è posizionare i numeri in ordine, da 1 a 15 da sinistra a destra dall'alto verso il basso. Quindi lo spazio vuoto sarà nell'angolo in basso a destra. Il movimento di qualsiasi tessera (o più) è un “passo” in questo spazio di gioco. La combinazione mostrata nell'immagine sopra è già impilata, ma nota che nello spazio vuoto possono essere inserite 12 o 15 tessere. Le regole stabiliscono che una tessera non può essere spostata diagonalmente o rimossa dal tabellone di gioco. In realtà ci sono molte configurazioni per iniziare il gioco (puoi contare esattamente quante), ma per semplicità, disponiamo le tessere in ordine dalla più grande alla più piccola e lasciamo uno spazio vuoto nell'angolo in basso a destra del tabellone . L'unica cosa è scambiare 1 e 2 in modo che il puzzle sia risolvibile. Ora vai alla directory ~/ del tuo workbench , quindi /pset3/fifteen e apri quindici.c . Contiene il codice per il motore di gioco. Il compito è aggiungere codice al gioco. Ma prima compiliamo il nostro "motore" (probabilmente sai già come farlo). Nonostante il gioco non sia finito, puoi avviare l'applicazione. Sarà più comodo eseguirlo in una finestra di terminale più grande del solito, che può essere aperta facendo clic sul segno più verde (+) accanto a una delle schede del codice e selezionando Nuovo terminale . Oppure puoi aprire la finestra del terminale a schermo intero facendo clic sull'icona Ingrandisci nell'angolo in alto a destra della console. Vedi che alcune cose funzionano in qualche modo. Ma in realtà la maggior parte del gioco non è stata ancora scritta. Ed ecco, preparati, la tua uscita!

Studio

Studia il codice e i commenti di quindici.c e poi rispondi alle domande seguenti:

1. A parte una tavola 4x4, quali dimensioni di campo consente il nostro motore?
2. Quale struttura dati è il campo di gioco?
3. Quale funzione viene chiamata per salutare il giocatore all'inizio del gioco?
4. Quali funzionalità devi implementare?
5. Nota: se vuoi che il controllo automatico ti dica se hai risposto correttamente alle domande, accanto al file quindici.c, trova il file quindici.txt e scrivi le risposte a queste domande al suo interno.

Implementazione

Bene, iniziamo a implementare il gioco. Ricorda, ci stiamo muovendo a piccoli passi, non provare a fare tutto in una volta. Implementiamo invece le funzionalità una alla volta e assicuriamoci che funzionino prima di procedere. In particolare, suggeriamo di implementare le funzioni di gioco nel seguente ordine: init (inizializzazione), draw (disegno), move (fare un passo), won (vincere). Le decisioni di progettazione (ad esempio quanto spazio inserire tra le nostre tessere numeriche) sono tue. Il campo di gioco dovrebbe assomigliare a questo: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Ancora una volta, tieni presente che nella posizione di partenza, 1 e 2 si trovano in ordine inverso (questo vale per il classico campo 4x4 se il numero di tessere è dispari). Se il numero di tessere è pari e il campo è 3x3, non è necessario scambiare le due tessere “più basse”. 8 7 6 5 4 3 2 1 _ Per testare la tua implementazione dei “Tag”, devi provare a riprodurli (non dimenticare, puoi uscire dal programma prima del suo naturale completamento premendo la combinazione di tasti crtl+c). Assicurati che il programma funzioni se vengono inseriti numeri errati. E ricorda che proprio come hai automatizzato l'input in find, puoi automatizzare la "procedura dettagliata" del gioco. Infatti nella cartella ~cs50/pset3 sono presenti i file 3x3.txt e 4x4.txt , che contengono tutte le sequenze di passaggi per vincere sui campi 3x3 e 4x4. Per testare il programma, ad esempio, utilizzando il primo dei file, esegui il comando seguente: ./fifteen 3 < ~cs50/pset3/3x3.txt Imposta l'argomento che ti serve per velocizzare l'animazione. E in generale, se vuoi, puoi sempre cambiare gioco. Per divertirsi con le "sequenze di escape ANSI" compreso il colore. Dai un'occhiata alla nostra implementazione di clear e controlla http://isthe.com/chongo/tech/comp/ansi_escapes.html per imparare nuovi trucchi. Se lo desideri, scrivi le tue funzioni o modifica i prototipi delle funzioni che abbiamo scritto. L'unica limitazione è che non cambi la logica della funzione principale, altrimenti non potremo applicarle alcuni test automatici per confermare che il tuo programma funzioni correttamente. In particolare, main deve restituire 0 se e solo se l'utente ha risolto il puzzle. I valori diversi da zero devono essere restituiti per tutte le opzioni di errore. Se si verificano errori, scriveteci. Bene, se vuoi giocare con l'implementazione dell'applicazione preparata dagli assistenti CS50, esegui il seguente comando: ~cs50/pset3/fifteen Se sei interessato a vedere un'implementazione più interessante, con la risoluzione automatica dei puzzle, dai un'occhiata alla versione "Hacker" del programma: ~cs50/hacker3/fifteen Invece di inserire un numero nella finestra di gioco, digita la parola DIO. Fantastico, non è vero? Se vuoi verificare ufficialmente la correttezza del tuo programma con check50, tieni presente che check50 presuppone che lo spazio vuoto del campo di gioco sia riempito con 0; se hai scelto un valore diverso, sostituiscilo con zero per una corretta verifica. Inoltre, check50 presuppone che tu stia indicizzando i campi della scheda nell'ordine [riga] [colonna], non scheda [colonna] [riga]. check50 2015.fall.pset3.fifteen fifteen.c

Scopri di più sull'implementazione delle funzioni di gioco di Quindici

• init (inizializzazione)
• disegno
• muoversi (fare un passo)
• vinto (vincere)

dentro

In questa funzione introduciamo il campo di gioco. Per fare ciò, utilizziamo un array bidimensionale di numeri interi. La dimensione dell'array è MAX x MAX, dove MAX è una costante che indica il numero massimo di riquadri che possono essere inseriti in una riga o colonna di un campo. Pertanto, dobbiamo definire la variabile int board[MAX][MAX] Tuttavia, ricordiamo che la dimensione del campo di gioco è determinata dall'utente. Pertanto, dobbiamo definire una variabile che indichi la dimensione della scheda che l'utente deve inserire. Questo è int d . dove d è la dimensione della scheda, d <= MAX. Tuttavia, in C non è possibile modificare la dimensione di un array, quindi è necessario accontentarsi della dimensione massima. In init devi inserire i valori sulla lavagna. Leggi di più sugli array bidimensionali se non hai ancora lavorato con loro. In breve, hanno due indici, il primo indica il numero di riga, il secondo il numero di colonna. Per il nostro problema, iniziamo con il numero massimo e finiamo nel caso d = 3 (“Otto”) con uno e un angolo vuoto. Se abbiamo ancora "Tag", scambiamo 1 e 2. Cosa fare con lo spazio vuoto? Il nostro array è composto da numeri interi, quindi il vuoto deve essere riempito con qualche numero intero. Pertanto, è necessario scegliere un numero intero per inizializzare la tessera vuota (o, nel caso di un gioco fisico, l'assenza di una tessera). I loop possono essere utilizzati per inizializzare il tabellone di gioco e riempirlo con un set iniziale di tessere. Esaminiamo gli indici i e j, dove board[i][j] è una tessera che si trova nella riga numero i e nella colonna numero j. Riempiamo il tabellone in ordine decrescente. Se il numero di tessere (senza quelle vuote) è dispari, scambia 1 e 2.

disegno

Questa funzione dovrebbe stampare lo stato corrente del campo di gioco. Ricorda che possiamo avere valori con una o due cifre, quindi per una bella formattazione dopo i numeri 1-9 la funzione dovrebbe stampare uno spazio ( #s ). Questo può essere fatto utilizzando il segnaposto %2d . printf (“%2d”, board[i][j]); Inoltre, non dimenticare la cella vuota. Seleziona il carattere che lo rappresenterà (nel nostro esempio si tratta di un carattere di sottolineatura). La funzione di disegno dovrebbe disegnare questo personaggio non appena raggiungi una cella vuota. Quindi il nostro ciclo sarebbe qualcosa del genere: for каждой строки for каждого element строки print meaning и пробел print новую строку Ricorda che l'ordine in cui la funzione draw disegna le tessere sullo schermo dovrebbe riflettere l'ordine in cui si trovano nell'array definito nella funzione init .

mossa

Dopo aver inizializzato il campo di gioco e tracciato le posizioni iniziali delle tessere, è necessario consentire all'utente di modificare la posizione delle tessere, ovvero di effettuare movimenti. Quindi in Fifteen.c il programma prende l'output dell'utente, costruisce il tabellone di gioco e poi chiama la funzione di spostamento e le dice quale tessera vuole spostare. Fai attenzione: stai applicando la funzione specificamente al numero sulla tessera e non alla sua posizione sul tabellone (nell'array). Quindi è necessario trovare la posizione effettiva della tessera. Inoltre, dovresti consentire all'utente di spostare il riquadro solo quando possibile. Nell'immagine sopra possiamo spostare solo le tessere numero 2, 5 e 8. Come determinarlo? Dal valore di una tessera vuota. Quindi la funzione di spostamento funziona in questo modo:

• Accetta il numero della tessera che l'utente desidera spostare
• Cerca la posizione nell'array (sul campo di gioco) di questa tessera
• Ricorda la posizione di una tessera vuota
• Se una tessera vuota è adiacente a quella che l'utente desidera spostare, vengono scambiate nell'array.

vinto

Questa funzione controlla se il gioco è terminato dopo ogni passaggio dell'utente. Restituisce vero se le tessere sono nell'ordine corretto (inclusa la posizione della tessera vuota nell'angolo in basso a destra). In questo caso è possibile terminare il programma. Se le tessere sono ancora sparse, la funzione restituisce false e passa le redini alla funzione sposta . Come organizzare un sopralluogo? Come nel caso dell'inizializzazione e del disegno della scheda, vengono utilizzati due cicli for nidificati. Ad esempio, è possibile impostare una condizione secondo cui ogni numero successivo nell'array deve essere maggiore del precedente. Nota quale valore è scritto nella tessera vuota. O in un altro modo: usa un contatore per assicurarti che tutte le tessere siano a posto, se riesci a gestirlo e scrivi la formula per ottenerlo. Ti auguriamo buona fortuna per i tuoi esperimenti!

Come convalidare il tuo codice e ottenere voti

Attenzione! Se per te è importante verificare solo la correttezza delle attività, utilizza cs50check. Se vuoi ottenere i voti sulla piattaforma edx, segui la procedura descritta di seguito. Tieni presente che questa procedura utilizza lo stesso cs50check per controllare le attività. L'unica differenza è che ricorda i risultati e calcola il punteggio complessivo.

1. Accedi all'IDE CS50
2. Vicino all'angolo in alto a sinistra dell'IDE CS50 , dove si trova il browser dei file (non nella finestra del terminale), fare clic con il pulsante destro del mouse sulla directory pset3 e fare clic su Download . Dovresti vedere che il browser ha scaricato l' archivio pset3.tar.gz .
3. In una finestra o scheda separata, accedi a CS50 Submit
4. Fare clic sull'icona Invia nell'angolo in alto a sinistra dello schermo
5. Nell'elenco delle cartelle a sinistra, fare clic sulla directory Problem Set 3 , quindi fare clic sul pulsante Carica nuovo invio. E 'sulla destra.
6. Nella schermata che appare, clicca sul pulsante Aggiungi file .... Si aprirà una finestra per selezionare i file dal tuo computer.
7. Passare alla cartella in cui è stato salvato pset3.tar.gz. Molto probabilmente si trova nella cartella Download o ovunque il browser inserisca i file per impostazione predefinita. Quando trovi pset3.tar.gz , fai clic una volta su di esso per selezionarlo, quindi fai clic su Apri .
8. Fai clic su Avvia caricamento . I tuoi file verranno caricati sui server CS50 .
9. Nella schermata che appare, dovresti vedere la finestra Nessun file selezionato . Se sposti il ​​cursore del mouse verso sinistra, vedrai un elenco di file scaricati. Per confermare, fare clic su ciascuno di essi. Se non sei sicuro di qualcosa, puoi ricaricare i file ripetendo gli stessi passaggi. Puoi farlo quante volte vuoi fino alla fine del 2016.