Prima di affrontare i problemi, guarda le lezioni 7-8 , leggi e approfondisci i “ Materiali aggiuntivi della terza settimana ”. Sono dedicati agli algoritmi di ricerca (lineari e binari), all'ordinamento (ce ne sono molti!), nonché al lavoro di un debugger (la capacità di lavorare con un debugger per eseguire il debug dei programmi è un'abilità estremamente importante!). Se tutto è andato come dovrebbe con le lezioni frontali e la teoria, potrai facilmente rispondere alle domande del test:
Perché la ricerca binaria richiede un array ordinato?
Perché si stima che il bubble sort sia O(n2)?
Perché la stima dell'ordinamento per inserzione è Ω(n)?
Come funziona l'ordinamento della selezione? Descrivi in tre frasi (o meno).
Qual è il limite superiore (caso peggiore) per quanto tempo può essere eseguito l'ordinamento di unione?
Il debugger GDB ti consente di eseguire il debug di un programma. E se formuli in modo più specifico, cosa ti permette esattamente di fare?
Obiettivi
Impara a lavorare con progetti che contengono più file
Impara a leggere il codice sorgente di qualcun altro
Comprendere vari algoritmi e funzioni ricorsive
La maggior parte di questi obiettivi sono praticamente impossibili da valutare formalmente. Pertanto, dal punto di vista della verifica formale dei problemi, c'è poco che ti sembrerà difficile. Ti ricordiamo però: puoi imparare a programmare solo attraverso la pratica costante! Pertanto, ti invitiamo non solo a risolvere i compiti, ma anche a dedicare ulteriore tempo e impegno e ad implementare tutti gli algoritmi discussi questa settimana. Inoltrare!
Inizio
Ricorda che per i problemi pratici delle settimane uno e due, hai scritto programmi da zero e creato le tue directory pset1 e pset2 utilizzando il comando mkdir . Per il compito pratico della terza settimana, devi scaricare la distribuzione (o "distro" come la chiamiamo noi) che abbiamo scritto e aggiungervi le tue righe di codice. Innanzitutto, leggi il nostro codice e prova a capirlo. L'abilità più importante questa settimana è imparare a leggere il codice degli altri. Quindi, accedi a cs50.io ed esegui il comando update50 in una finestra di terminale per assicurarti che la versione dell'area di lavoro sia aggiornata. Se hai chiuso accidentalmente la finestra del terminale e non riesci a trovarla, vai al menu Visualizza e assicurati che l'opzione Console sia selezionata (selezionala se non lo è). Fare clic su (+), all'interno del cerchio verde sulla cornice della finestra del terminale, selezionare Nuovo terminale . Successivamente, esegui il comando cd ~/workspace e assicurati di essere all'interno della directory dello spazio di lavoro (questa è la tua directory). Successivamente, esegui il comando: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip per scaricare l'archivio ZIP del libro dei problemi nel tuo spazio di lavoro (wget è il comando di download di Linux). Se è tutto ok, vedrai nella riga la seguente frase: 'pset3.zip' saved Assicurati di aver scaricato veramente pset3.zip eseguendo il comando: ls e poi corri unzip pset3.zip a decomprimere il file. Se esegui nuovamente il comando ls , vedrai anche la directory pset3 . Vai ad esso eseguendo il comando cd pset3 e poi richiedi di visualizzare nuovamente il contenuto della directory: ls vedrai che ci sono due sottodirectory in questa directory: fifteen find Già intrigante!
Ricerca
Immergiamoci ora in una di queste sottodirectory. Per fare ciò, eseguiremo il comando: cd ~/workspace/pset3/find Se visualizzi il contenuto di questa cartella sullo schermo (probabilmente ricordi già come farlo), ecco cosa dovresti vedere: helpers.c helpers.h Makefile find.c generate.c Wow, ci sono molti file. Ma non preoccuparti, ci occuperemo di loro adesso. Il file generate.c contiene il codice per un programma che utilizza un "generatore di numeri pseudo-casuali" (generato dalla funzione drand48 ) per generare un gran numero di numeri casuali (in realtà pseudo-casuali, i computer non sono in grado di gestire la pura casualità!) , e posizionali uno alla volta nella riga. Compila il programma: make generate Ora eseguilo eseguendo il comando: ./generate Il programma ti darà il seguente messaggio: Usage: generate n [s] Ciò significa che il programma prevede uno o due argomenti della riga di comando. Usando il primo, n, è obbligatorio; questo numero indica quanti numeri pseudocasuali si desidera creare. Il parametro s è facoltativo, come indicato dalle parentesi quadre. Il numero s può essere chiamato "seme" per il generatore di numeri pseudocasuali. Con "seme" intendiamo i dati di input per il generatore di numeri pseudocasuali che influenzano il suo output. Ad esempio, se stai usando drand48, prima chiamando srand48 (un'altra funzione il cui scopo è "seminare" drand48) con un argomento, diciamo, 1, e quindi chiamando drand48 tre volte, drand48 potrebbe restituire 2728, poi 29785, quindi 54710. Se invece del precedente, usando drand48, chiami prima srand48 con un argomento, diciamo, 2, e poi usi drand48 di nuovo tre volte, drand48 potrebbe restituisci 59797, poi 10425, poi 37569. Ma se rivedi drand48 chiamando di nuovo srand48 con un argomento pari a 1, il risultato delle tre chiamate successive a drand48 otterrai di nuovo 2728, poi 29785, poi 54710! Vedi, tutto accade per una ragione. Esegui nuovamente il programma, questa volta, diciamo n=10, come mostrato di seguito; vedrai un elenco di 10 numeri pseudo-casuali. ./generate 10 Eseguiamo il programma una terza volta con lo stesso valore di n; dovresti vedere un altro elenco di 10 numeri. Ora prova a eseguire il programma con due parametri. Prendiamo s=0 come mostrato di seguito. ./generate 10 0 Ora esegui di nuovo lo stesso comando: ./generate 10 0 non puoi nemmeno discutere: hai visto di nuovo la stessa sequenza "casuale" di dieci cifre. Questo è ciò che accade se non si modificano i semi del generatore di numeri pseudocasuali. Ora diamo un'occhiata al programma generate.c stesso(ricordi come?). I commenti all'inizio di questo file spiegano le funzionalità generali del programma. Ma sembra che ci siamo dimenticati di commentare il codice stesso. Leggi attentamente il codice e leggilo finché non capisci il significato di ogni riga. Quindi commenta questo codice per noi, sostituendo ogni TODO con una frase che descrive lo scopo o la funzionalità della riga o delle righe di codice corrispondenti. (nota: unsigned int è un int “unsigned”, ovvero non può essere negativo). Per ottenere maggiori informazioni su rand o srand, esegui: man drand48 oppure man srand48 Dopo aver commentato quanto più possibile in generate.c, ricompila il programma per assicurarti di non aver rotto nulla: make generate Se generate non viene più compilato, correggi ciò che hai rotto: )! Come promemoria, il comando make automatizza la compilazione del codice, quindi non è necessario eseguire il comando clang inserendo manualmente una serie di opzioni. Ma in realtà, make semplifica semplicemente il nostro input, ma in realtà dietro di esso si nasconde lo stesso clangore con i parametri di cui abbiamo bisogno. Tuttavia, man mano che i tuoi programmi diventano più grandi, make non riesce più a capire dal contesto come compilare il codice. In questo caso dovrai indicare a make come compilare i programmi, soprattutto se implicano l'utilizzo di file sorgente diversi (come .c). Per risolvere questo problema utilizzeremo i file di configurazione (Makefile) che dicono a make esattamente cosa fare. Come faceva il comando make a sapere come dovremmo compilare generate? Infatti il team ha utilizzato un file di configurazione che avevamo già scritto. Questo file si chiama Makefile e si trova nella stessa directory di generate.c . Makefile è un elenco di regole che specificano come creare il file generato da generate.c. Nel file troverete, in particolare, le righe relative: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c La prima riga indica make che dovrà essere creato un "target" chiamato generate richiamando il comando dalla seconda riga. Inoltre, la prima riga dice a make che generate dipende da generate.c, il che significa che make ricostruirà generate solo nelle esecuzioni successive se quel file è stato modificato. Non è un brutto trucco per risparmiare tempo, vero? In effetti, esegui nuovamente il comando seguente se non hai modificato generate.c . make generate Verrai informato che generate è già stato aggiornato alla versione corrente. Nota : il rientro all'inizio della seconda riga non è una sequenza di spazi, ma piuttosto un carattere di tabulazione. Sfortunatamente, make richiede che i comandi siano preceduti da tabulazioni, quindi fai attenzione a non trasformarli in spazi o incorrerai in strani errori! Il flag -Werror indica il comando clangtratta gli avvertimenti (cattivi) come errori (anche peggiori), quindi sarai costretto (in modo positivo ed educativo!) a correggerli. Ora diamo un'occhiata al file find.c. Tieni presente che questo programma prevede un argomento della riga di comando: "igloo", che deve essere trovato in un "pagliaio" di valori. Successivamente, rivedi il codice e compila il programma eseguendo il comando seguente. make find make sostanzialmente ci ha dato quanto segue: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm fai attenzione! Hai appena compilato un'applicazione composta da uno, ma due file: helpers.c e find.c . Come ha fatto a saperlo? Per capirlo, apri di nuovo il Makefile per vedere cosa sta realmente succedendo lì. Le righe interessate sono riportate di seguito. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Ciò che intendiamo per dipendenza (dopo i due punti) è che qualsiasi modifica a find.c , helpers.c o helpers.h forzerà make a ricostruire find la prossima volta che verrà chiamato per tali scopi. Ora esegui questo programma facendo, ad esempio, quanto segue: ./find 13 Dopodiché, ti verrà chiesto di fornire un certo stack (cioè numeri interi) e dargli da mangiare una cannuccia alla volta. Quando ti stanchi di digitare numeri, premi la combinazione di tasti Ctrl-D . Questa combinazione invierà al programma un carattere di fine file (EOF). Il simbolo forzerà la funzione GetInt della libreria CS50 a restituire la costante INT_MAX e questa, a sua volta, in find.c forzerà find a smettere di digitare "stack". Il programma ora cercherà l'ago nel pagliaio che hai fornito e alla fine ti dirà se è stato trovato. In breve, il programma cerca un valore in un array. Almeno dovrebbe, ma il problema è che non troverà ancora nulla! Ma qui vieni in soccorso! Parleremo dell'importanza del tuo ruolo un po' più tardi. In effetti, il processo di fornitura di un pagliaio può essere automatizzato, almeno "unendo" l'output di generate in find come input. Ad esempio, il comando seguente passa 1000 numeri pseudocasuali da trovare, che quindi cerca tra questi valori 42. ./generate 1000 | ./find 42 Tieni presente che quando generate passa i dati grezzi da trovare, non vedrai il numero generato, ma vedrai find in esecuzione . In alternativa, puoi "reindirizzare" l'output di generate in un file con un comando come questo: ./generate 1000 > numbers.txt Il contenuto di questo file può essere reindirizzato all'input di find con il comando: ./find 42 < numbers.txt Diamo un'altra occhiata al codice nel Makefile e notiamo il riga seguente: all: find generate Ciò significa che puoi build generare e trovare eseguendo il seguente comando: make all Inoltre, il comando sotto questa riga è equivalente al comando sopra di essa, poiché make crea la prima voce nel Makefile per impostazione predefinita. make Se solo potessi ridurre tutte queste attività pratiche a un solo comando! Ma ahimè! Infine, presta attenzione a queste ultime righe nel Makefile: clean: rm -f *.o a.out core find generate Questa voce permette di rimuovere tutti i file che finiscono in .o o che si chiamano core (lo spiegheremo tra poco!), e anche di eseguire semplicemente la ricerca o la generazione di programmi eseguendo la riga: Se vuoi make clean sperimentare , allora c'è qualcosa a cui prestare attenzione: non aggiungere, ad esempio, *.c all'ultima riga del Makefile! (perché?) Tutte le righe che iniziano con il segno # sono solo commenti.
Compito 1: ricerca
È tempo di qualcosa di interessante! Tieni presente che find.c chiama search , una funzione dichiarata in helpers.h . Sfortunatamente, ci siamo dimenticati di implementare completamente questa funzione in helpers.c ! (Va notato che potremmo mettere il contenuto di helpers.h e helpers.c in un unico find.c . Ma a volte è meglio separare i programmi in più file. Soprattutto se alcune funzioni, o meglio funzioni di utilità, possono essere utili per altri programmi. Come ad esempio le funzioni della libreria CS50. Dai un'occhiata a helpers.c e vedrai che la ricerca restituisce sempre false, indipendentemente dal fatto che il valore fornito sia espresso in valori. Riscrivi la ricerca in modo che utilizzi la ricerca lineare, restituendo true , se il valore è in valori e false se il valore non è in valori. Abbi cura di restituire immediatamente false se n non è positivo. Quando sei pronto per verificare la validità, prova a chiamare il seguente comando: Poiché uno dei numeri ./generate 1000 50 | ./find 127 stampati con generate quando 50 è stato seminato è 127, il tuo codice dovrebbe trovare l'ago! Al contrario, prova questo comando: ./generate 1000 50 | ./find 128 Poiché 128 non è tra l'insieme di numeri generati da generate quando 50 è stato seminato, il tuo codice non deve trovare l'"ago" . Esegui altri test eseguendo generate con alcuni seed, analizzando l'output e cercando l'ago che dovrebbe essere nel pagliaio. Nota che main in find.c è scritto in modo tale che find restituisce 0 se viene trovato l'"ago", altrimenti restituisce 1. Puoi controllare il cosiddetto "codice di output" che main restituisce quando eseguito dopo aver eseguito qualche altro comandi echo $? . Ad esempio, se l'implementazione della ricerca è corretta, se esegui ./generate 1000 50 | ./find 127 echo $? vedrai 0, mentre 127 è tra i 1000 numeri restituiti da generate con un seme di 50, quindi la ricerca che hai scritto dovrebbe restituire true. In questo caso main (scritto da noi) dovrebbe restituire 0 (cioè exit). Se fornisci il seguente input ./generate 1000 50 | ./find 128 echo $? , vedrai 1 perché 128 non è tra i 1000 numeri restituiti da generate con un seed di 50. In questo caso, search (scritto da te) restituirà false e main (scritto da noi ) restituirà 1 (e quindi finirà il lavoro). Capisci la logica? Quando tutto è pronto per essere controllato utilizzando check50, esegui il seguente comando: check50 2015.fall.pset3.find helpers.c A proposito, non dovresti abituarti a testare il tuo codice usando check50 prima di testarlo tu stesso. Dopotutto, check50 non esiste realmente, quindi eseguire il codice con i propri campioni di input, confrontando l'output effettivo con l'output previsto, è la migliore abitudine che puoi prendere a questo punto. È vero, non diventarne dipendente! Se sei interessato a giocare con l'implementazione di find degli assistenti CS50, esegui questo comando: ~cs50/pset3/find
Ordinamento
La ricerca lineare non è qualcosa di veramente impressionante, ma dalle prime lezioni (e nella settima abbiamo ripetuto di nuovo questo trucco!) ti ricordi che puoi trovare un ago in un pagliaio molto più velocemente. Ma prima dobbiamo sistemare il nostro pagliaio. Tieni presente che find.c chiama sort , una funzione dichiarata in helpers.h . Sfortunatamente, ci siamo “dimenticati” di implementare completamente questa funzionalità in helpers.c ! Esamina helpers.c e vedrai che sort ritorna immediatamente, anche se la funzione principale di find gli passa effettivamente l'array effettivo. Ora ricorda la sintassi della dichiarazione dell'array. Non solo specifichi il tipo di elemento di questo array, ma ne specifichi anche la dimensione tra parentesi quadre. Questo è ciò che facciamo per il pagliaio in find.c : int haystack [MAX]; ma quando attraversi un array, ne specifichi solo il nome. E lo facciamo esattamente allo stesso modo quando esaminiamo il pagliaio per eseguire l'ordinamento in find.c : sort (haystack, size); (Indovina perché passiamo la dimensione di quell'array separatamente?) Quando dichiariamo una funzione che accetta un array unidimensionale come argomento, non è necessario specificare la dimensione dell'array. Allo stesso modo, non l'abbiamo fatto quando abbiamo dichiarato sort in helpers.h (e helpers.c): void sort (int values [] int n); implementa sort in modo che la funzione ordini effettivamente l'array di numeri da piccolo a grande. È necessario che il tempo di esecuzione sia pari a O(n 2 ), dove n è la dimensione dell'array. Probabilmente vorrai implementare l'ordinamento a bolle, l'ordinamento per selezione o l'ordinamento per inserimento, come abbiamo appreso nella terza settimana. Tuttavia, è importante notare: non esiste un modo "corretto" per implementare questi algoritmi. Esiste un numero enorme di varianti. In effetti, puoi sempre migliorarli se lo ritieni opportuno, purché la tua implementazione converga a O(n2 ) . Tuttavia, lascia la sperimentazione al corpo della funzione e, per semplificare il test, non modificare la nostra dichiarazione di ordinamento. Dovrebbe assomigliare a questo: void sort (int values [] int n); Poiché la funzione restituisce un valore void, non dovrebbe restituire un array ordinato. Invece, deve ordinare "distruttivamente" l'effettivo array che sta "attraversando", spostando i suoi elementi. Nella quarta settimana discuteremo del fatto che gli array vengono passati per riferimento anziché per valore. Cioè, sort non riceverà copie dell'array, ma l'array originale stesso. Anche se non puoi modificare la nostra dichiarazione di ordinamento, puoi sempre definire la tua funzione in helpers.c, che può quindi essere chiamata da sort. Decidi tu stesso il modo migliore per testare l'implementazione dell'ordinamento. Non dimenticare che printf e GDB ti aiuteranno! E non dimenticare che puoi creare più e più volte la stessa sequenza di numeri pseudo-casuali specificando esplicitamente i valori seed per generate.
Ricerca binaria, suggerimenti
La prima cosa che devi capire sulla funzione find è che abbiamo già scritto il codice (distribuzione). Stiamo semplicemente colmando alcune lacune nel codice esistente. Il programma find.c richiede l'immissione di numeri (ovvero, per riempire una "pila"), quindi cerca un "ago" al suo interno su richiesta dell'utente, utilizzando le funzioni di ordinamento e ricerca definite in helpers.c . Quindi, find è già scritto, dobbiamo scrivere helpers . Quindi ecco cosa dobbiamo fare:
Implementare la ricerca. Questa funzione dovrebbe restituire true se il valore viene trovato nello stack e false se non è presente.
Implementa sort, una funzione che ordina un array di valori.
Inizialmente, la ricerca è stata implementata come lineare. Ma puoi fare di meglio. L'algoritmo di ricerca lineare viene eseguito in tempo O(n) . Il tuo compito è scrivere un algoritmo di ricerca binaria. Il suo tempo di esecuzione è O(log n) . Tuttavia, il suo problema è che necessita di dati ordinati come input, altrimenti non funzionerà. Ricordi l'esempio del libro strappato e probabilmente sai perché è così. Se hai eseguito una ricerca binaria tra gli elementi e non ne sono rimasti più (cioè semplicemente non c'è alcun "ago" in questa "pila"), è necessario che la funzione restituisca false. La ricerca binaria può essere implementata in modo iterativo o ricorsivo (David Malan ha parlato di ricorsione nell'ottava lezione).
Successivamente, esegui il comando 
GO TO FULL VERSION