1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sezione 3 - più confortevole]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Questo è CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Quindi la prima domanda è stranamente formulata.

5
00:00:12,700 --> 00:00:17,480
GDB permette di "debug", un programma, ma, più in particolare, che cosa ti permette di fare?

6
00:00:17,480 --> 00:00:22,590
Ti risponderò che uno, e io non so cosa stia esattamente previsto,

7
00:00:22,590 --> 00:00:27,910
così Sto indovinando che è qualcosa lungo le linee di esso permette di passo dopo passo

8
00:00:27,910 --> 00:00:31,540
a piedi attraverso il programma, interagire con esso, le variabili del cambiamento, fare tutte queste cose -

9
00:00:31,540 --> 00:00:34,270
sostanzialmente completamente controllare l'esecuzione di un programma

10
00:00:34,270 --> 00:00:38,410
e ispezionare qualsiasi data parte della esecuzione del programma.

11
00:00:38,410 --> 00:00:43,030
Quindi, le caratteristiche consentono di eseguire il debug di cose.

12
00:00:43,030 --> 00:00:44,830
Va bene.

13
00:00:44,830 --> 00:00:50,520
Perché la ricerca binaria richiede che un array da ordinare?

14
00:00:50,520 --> 00:00:53,360
Chi ha voglia di rispondere?

15
00:00:56,120 --> 00:01:00,070
[Studente] Perché non funziona se non è ordinato. Sì >>. [Risate]

16
00:01:00,070 --> 00:01:04,910
Se non è risolto, allora è impossibile dividere a metà

17
00:01:04,910 --> 00:01:07,850
e sapere che tutto a sinistra è meno e tutto a destra

18
00:01:07,850 --> 00:01:10,490
è maggiore del valore centrale.

19
00:01:10,490 --> 00:01:12,790
Quindi ha bisogno di essere ordinati.

20
00:01:12,790 --> 00:01:14,170
Va bene.

21
00:01:14,170 --> 00:01:17,570
Perché è una sorta di bolla in O quadrato n?

22
00:01:17,570 --> 00:01:23,230
Qualcuno vuole prima di dare una molto veloce panoramica di alto livello di che tipo bolla è?

23
00:01:25,950 --> 00:01:33,020
[Studente] Che, fondamentalmente, passare attraverso ogni elemento e di controllare gli elementi primi.

24
00:01:33,020 --> 00:01:37,150
Se sono su dove li scambiare, poi di controllare gli elementi successivi e così via.

25
00:01:37,150 --> 00:01:40,770
Quando si raggiunge la fine, poi si sa che l'elemento più grande è posto alla fine,

26
00:01:40,770 --> 00:01:42,750
in modo da ignorare che uno poi si continua a passare attraverso,

27
00:01:42,750 --> 00:01:48,490
e ogni volta che si controlla un elemento meno fino a quando non si apportano modifiche. Sì >>.

28
00:01:48,490 --> 00:01:58,470
Si chiama bubble sort, perché se si capovolgere la matrice su un lato in modo che sia alto e in basso, verticale,

29
00:01:58,470 --> 00:02:03,100
quindi i valori di grandi dimensioni si depositano sul fondo ed i valori piccola bolla fino alla cima.

30
00:02:03,100 --> 00:02:05,210
È così che ha preso il nome.

31
00:02:05,210 --> 00:02:08,220
E sì, basta andare attraverso.

32
00:02:08,220 --> 00:02:11,190
Continui a passare attraverso la matrice, scambiando il valore maggiore

33
00:02:11,190 --> 00:02:14,040
per ottenere valori più grandi sul fondo.

34
00:02:14,040 --> 00:02:17,500
>> Perché è O di quadrato n?

35
00:02:18,690 --> 00:02:24,620
In primo luogo, nessuno vuole dire perché è O di n al quadrato?

36
00:02:24,620 --> 00:02:28,760
[Studente] Perché per ogni corsa va n volte.

37
00:02:28,760 --> 00:02:32,100
Si può solo essere sicuro che hai preso il più grande elemento fino in fondo,

38
00:02:32,100 --> 00:02:35,230
poi si deve ripetere che a molti elementi. Sì >>.

39
00:02:35,230 --> 00:02:41,800
Quindi, tenere a mente che cosa grande O significa e che cosa significa Omega grandi.

40
00:02:41,800 --> 00:02:50,560
The Big O è come il limite superiore per quanto lento possa effettivamente funzionare.

41
00:02:50,560 --> 00:02:58,990
Così dicendo che è O del quadrato n, non è O di n altrimenti sarebbe in grado di eseguire

42
00:02:58,990 --> 00:03:02,640
in tempo lineare, ma è O di n cubo

43
00:03:02,640 --> 00:03:06,390
perché è delimitata da O di n cubo.

44
00:03:06,390 --> 00:03:12,300
Se è delimitata da O quadrato di n, allora è anche delimitata da n cubo.

45
00:03:12,300 --> 00:03:20,280
Così è n quadrato, e nel caso peggiore assoluta non può fare meglio squared n,

46
00:03:20,280 --> 00:03:22,830
ed è per questo che è O di n quadrato.

47
00:03:22,830 --> 00:03:31,200
Quindi, per vedere la matematica lieve come risulta essere n quadrato,

48
00:03:31,200 --> 00:03:40,530
se abbiamo cinque cose nella nostra lista, la prima volta il numero di operazioni di swap potremmo potenzialmente bisogno di fare

49
00:03:40,530 --> 00:03:47,170
per ottenere questo? Facciamo in realtà solo -

50
00:03:47,170 --> 00:03:52,040
Quanti swap stiamo andando ad avere per fare nella prima prova del Bubble sort attraverso l'array?

51
00:03:52,040 --> 00:03:53,540
[Studente] n - 1. Sì >>.

52
00:03:53,540 --> 00:03:58,340
>> Se ci sono 5 elementi, avremo bisogno di fare n - 1.

53
00:03:58,340 --> 00:04:01,100
Poi, il secondo il numero di swap stiamo andando ad avere per fare?

54
00:04:01,100 --> 00:04:03,440
[Studente] n - 2. Sì >>.

55
00:04:03,440 --> 00:04:11,640
E il terzo sarà n - 3, e poi per comodità scriverò le ultime due

56
00:04:11,640 --> 00:04:15,270
come allora stiamo andando ad avere bisogno di fare 2 swap e 1 di swap.

57
00:04:15,270 --> 00:04:19,899
Credo che l'ultimo può o non può effettivamente bisogno per accadere.

58
00:04:19,899 --> 00:04:22,820
E 'uno swap? Non lo so.

59
00:04:22,820 --> 00:04:26,490
Quindi questi sono gli importi totali delle operazioni di swap o almeno confronti si devono fare.

60
00:04:26,490 --> 00:04:29,910
Anche se non scambiare, hai ancora bisogno di confrontare i valori.

61
00:04:29,910 --> 00:04:33,910
Quindi ci sono n - 1 confronti della prima esecuzione tramite la matrice.

62
00:04:33,910 --> 00:04:42,050
Se riorganizzare queste cose, cerchiamo di fare sei in realtà le cose e quindi le cose stack up bene,

63
00:04:42,050 --> 00:04:44,790
e poi farò 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Quindi, solo riordinando queste somme, vogliamo vedere quanti confronti facciamo

65
00:04:49,910 --> 00:04:52,700
nel intero algoritmo.

66
00:04:52,700 --> 00:04:56,550
Quindi, se portiamo questi ragazzi qui,

67
00:04:56,550 --> 00:05:07,470
allora siamo ancora solo sommando i confronti però ci sono stati molti.

68
00:05:07,470 --> 00:05:13,280
Ma se sommiamo questi e sommiamo questi e sommiamo questi,

69
00:05:13,280 --> 00:05:18,130
è ancora lo stesso problema. Abbiamo appena riassumere quei gruppi particolari.

70
00:05:18,130 --> 00:05:22,400
>> Così ora stiamo sommando le 3 n. Non si tratta solo di 3 n.

71
00:05:22,400 --> 00:05:27,650
E 'sempre sarà n / 2 di n.

72
00:05:27,650 --> 00:05:29,430
Così qui ci capita di avere 6.

73
00:05:29,430 --> 00:05:34,830
Se avessimo 10 cose, allora potremmo fare questo gruppo per 5 diverse coppie di cose

74
00:05:34,830 --> 00:05:37,180
e finire con n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Quindi, si sta andando sempre di ottenere n / 2 n, e quindi questo te lo butto fuori a n quadrato / 2.

76
00:05:45,840 --> 00:05:48,890
E quindi, anche se è il fattore di mezzo, che avviene a venire in

77
00:05:48,890 --> 00:05:54,190
a causa del fatto che ogni iterazione attraverso la matrice confrontiamo 1 meno

78
00:05:54,190 --> 00:05:58,040
è così che si ottiene il più del 2, ma è ancora n quadrato.

79
00:05:58,040 --> 00:06:01,650
Non ci interessa il fattore costante di un mezzo.

80
00:06:01,650 --> 00:06:07,760
Quindi un sacco di grandi cose O come questa si basa su un solo tipo di fare questo tipo di matematica,

81
00:06:07,760 --> 00:06:12,260
facendo le somme aritmetiche e cose serie geometriche,

82
00:06:12,260 --> 00:06:17,750
ma la maggior parte di loro in questo corso sono piuttosto semplici.

83
00:06:17,750 --> 00:06:19,290
Va bene.

84
00:06:19,290 --> 00:06:24,430
Perché è una sorta di inserimento in Omega di n? Che cosa significa omega?

85
00:06:24,430 --> 00:06:27,730
[Due studenti di lingua in una sola volta - incomprensibili] >> Si '.

86
00:06:27,730 --> 00:06:30,630
Omega si può pensare come il limite inferiore.

87
00:06:30,630 --> 00:06:36,550
>> Quindi, non importa quanto sia efficiente il vostro algoritmo di ordinamento per inserimento è,

88
00:06:36,550 --> 00:06:41,810
indipendentemente dalla lista che è passato in, ha sempre confrontare almeno n cose

89
00:06:41,810 --> 00:06:44,620
o deve scorrere le cose n.

90
00:06:44,620 --> 00:06:47,280
Perché è così?

91
00:06:47,280 --> 00:06:51,190
[Studente] Perché se la lista è già ordinato, poi attraverso la prima iterazione

92
00:06:51,190 --> 00:06:54,080
si può solo garantire che il primo elemento è il meno,

93
00:06:54,080 --> 00:06:56,490
e la seconda iterazione si può garantire solo le prime due sono

94
00:06:56,490 --> 00:07:00,010
perché non si sa che il resto della lista è ordinata. Sì >>.

95
00:07:00,010 --> 00:07:08,910
Se si passa in un elenco completamente ordinato, per lo meno si deve andare su tutti gli elementi

96
00:07:08,910 --> 00:07:12,180
per vedere che non ha bisogno di essere spostati.

97
00:07:12,180 --> 00:07:14,720
Quindi, passando sopra l'elenco e dire oh, questo è già ordinato,

98
00:07:14,720 --> 00:07:18,240
è impossibile per voi sapere che è risolto solo dopo aver verificato ogni elemento

99
00:07:18,240 --> 00:07:20,660
per vedere che sono in modo ordinato.

100
00:07:20,660 --> 00:07:25,290
Quindi il limite inferiore per inserzione è Omega di n.

101
00:07:25,290 --> 00:07:28,210
Che cosa è il caso peggiore tempo di esecuzione di merge sort,

102
00:07:28,210 --> 00:07:31,390
peggiore dei casi, essendo O grandi di nuovo?

103
00:07:31,390 --> 00:07:37,660
Così, nel peggiore dei casi, come si merge sort esegue?

104
00:07:42,170 --> 00:07:43,690
[Studente] N log n. Sì >>.

105
00:07:43,690 --> 00:07:49,990
I più veloci algoritmi di ordinamento generale sono n log n. Non si può fare di meglio.

106
00:07:51,930 --> 00:07:55,130
>> Ci sono casi particolari, e se abbiamo tempo di oggi - ma probabilmente won't -

107
00:07:55,130 --> 00:07:59,330
abbiamo potuto vedere quello che fa meglio di n log n.

108
00:07:59,330 --> 00:08:04,050
Ma, nel caso generale, non si può fare meglio di n log n.

109
00:08:04,050 --> 00:08:09,680
E merge sort sembra essere quello che si deve sapere per questo corso che è n log n.

110
00:08:09,680 --> 00:08:13,260
E così saremo effettivamente attuazione di tale oggi.

111
00:08:13,260 --> 00:08:18,070
E, infine, in non più di tre frasi, come funziona sorta lavoro di selezione?

112
00:08:18,070 --> 00:08:20,370
Qualcuno vuole rispondere, e io conto le frasi

113
00:08:20,370 --> 00:08:22,390
perché se si va oltre 3 -

114
00:08:25,530 --> 00:08:28,330
Qualcuno ricorda per selezione?

115
00:08:31,280 --> 00:08:37,809
Sorta di selezione di solito è abbastanza facile da ricordare solo dal nome.

116
00:08:37,809 --> 00:08:45,350
Basta scorrere l'array, trovare qualunque sia il valore più grande è o più piccolo -

117
00:08:45,350 --> 00:08:47,290
qualunque ordine si sta ordinamento trovi

118
00:08:47,290 --> 00:08:50,750
Quindi diciamo che stiamo ordinamento dal più piccolo al più grande.

119
00:08:50,750 --> 00:08:55,250
È scorrere l'array, alla ricerca di tutto ciò che è l'elemento minimo,

120
00:08:55,250 --> 00:08:59,750
selezionarlo, e poi semplicemente scambiare tutto ciò che è in primo luogo.

121
00:08:59,750 --> 00:09:04,090
E poi al secondo passaggio la matrice, cercare l'elemento minimo di nuovo,

122
00:09:04,090 --> 00:09:07,490
selezionarlo, e poi scambiarlo con ciò che è in seconda posizione.

123
00:09:07,490 --> 00:09:10,650
Quindi, ci sono solo la raccolta e scegliendo i valori minimi

124
00:09:10,650 --> 00:09:16,050
e inserendoli nella prima parte dell'array finché non viene risolto.

125
00:09:19,210 --> 00:09:21,560
Domande su questo?

126
00:09:21,560 --> 00:09:25,710
>> Questi inevitabilmente appaiono nelle forme che devono compilare quando si elaborano il pset.

127
00:09:29,010 --> 00:09:32,360
Queste sono fondamentalmente le risposte a quelli.

128
00:09:32,360 --> 00:09:34,230
Bene, ora i problemi di codifica.

129
00:09:34,230 --> 00:09:40,140
Ho già inviato tramite e-mail - Non avere nessuno che la posta elettronica? Va bene.

130
00:09:40,140 --> 00:09:46,630
Ho già inviato tramite e-mail lo spazio che abbiamo intenzione di utilizzare,

131
00:09:46,630 --> 00:09:52,120
e se si fa clic sul mio nome - quindi penso che ho intenzione di essere in fondo

132
00:09:52,120 --> 00:09:57,170
a causa della r indietro - ma se cliccate sul mio nome vedrai 2 revisioni.

133
00:09:57,170 --> 00:10:02,650
Revisione 1 sta per essere ho già copiato e incollato il codice in spazi

134
00:10:02,650 --> 00:10:06,900
ricerca per la cosa si sta andando ad avere per implementare.

135
00:10:06,900 --> 00:10:10,540
E Revisione 2 sarà la cosa tipo che implementiamo dopo.

136
00:10:10,540 --> 00:10:15,770
Quindi, è possibile fare clic sul mio Revisione 1 e lavorare da lì.

137
00:10:17,350 --> 00:10:22,060
E ora vogliamo implementare la ricerca binaria.

138
00:10:22,060 --> 00:10:26,470
>> Qualcuno ha voglia di fare solo un pseudocodice di alto livello spiegazione

139
00:10:26,470 --> 00:10:31,440
di quello che stiamo andando ad avere a che fare per la ricerca? Gia '.

140
00:10:31,440 --> 00:10:36,170
[Studente] Devi solo prendere il centro della matrice e vedere se quello che stai cercando

141
00:10:36,170 --> 00:10:38,650
sia inferiore o superiore a quella.

142
00:10:38,650 --> 00:10:41,080
E se è meno, si va alla metà che è meno,

143
00:10:41,080 --> 00:10:44,750
e se è di più, si va a metà che è più e che si ripete fino a che non solo ottenere una cosa.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Si '.

145
00:10:46,570 --> 00:10:51,320
Si noti che la nostra matrice di numeri è già ordinato,

146
00:10:51,320 --> 00:10:57,190
e in modo che significa che siamo in grado di approfittare di questo e abbiamo potuto verificare prima,

147
00:10:57,190 --> 00:11:00,390
ok, sto cercando il numero 50.

148
00:11:00,390 --> 00:11:03,720
Così posso andare al centro.

149
00:11:03,720 --> 00:11:07,380
Oriente è difficile da definire quando si tratta di un numero pari di cose,

150
00:11:07,380 --> 00:11:10,820
ma diciamo solo che saremo sempre troncare al centro.

151
00:11:10,820 --> 00:11:14,420
Quindi qui abbiamo 8 cose, in modo che il centro sarebbe 16.

152
00:11:14,420 --> 00:11:17,330
Sto cercando per il 50, quindi 50 è maggiore di 16.

153
00:11:17,330 --> 00:11:21,310
Così ora posso trattare praticamente la mia matrice come questi elementi.

154
00:11:21,310 --> 00:11:23,450
Posso buttare via tutto, a partire dal 16 oltre.

155
00:11:23,450 --> 00:11:27,440
Ora il mio array è solo questi 4 elementi, e lo ripeto.

156
00:11:27,440 --> 00:11:31,910
Allora io voglio trovare il mezzo nuovo, che sta per essere 42.

157
00:11:31,910 --> 00:11:34,730
42 è inferiore a 50, in modo da poter buttare via questi due elementi.

158
00:11:34,730 --> 00:11:36,890
Questa è la mia matrice rimanente.

159
00:11:36,890 --> 00:11:38,430
Vado a trovare il mezzo nuovo.

160
00:11:38,430 --> 00:11:42,100
Credo che 50 era un cattivo esempio perché ero sempre buttare via le cose a sinistra,

161
00:11:42,100 --> 00:11:48,280
ma per la stessa misura, se sto cercando qualcosa

162
00:11:48,280 --> 00:11:52,100
ed è meno l'elemento Attualmente sto guardando,

163
00:11:52,100 --> 00:11:55,080
allora ho intenzione di buttare via tutto a destra.

164
00:11:55,080 --> 00:11:58,150
Così ora abbiamo bisogno di attuare tale.

165
00:11:58,150 --> 00:12:02,310
Si noti che abbiamo bisogno di passare di dimensione.

166
00:12:02,310 --> 00:12:06,730
Si può anche non essere necessario a livello di codice dimensioni.

167
00:12:06,730 --> 00:12:11,640
Quindi, se ci liberiamo di quel # define -

168
00:12:19,630 --> 00:12:21,430
Va bene.

169
00:12:21,430 --> 00:12:27,180
Come posso ben capire che la dimensione della matrice di numeri è attualmente?

170
00:12:27,180 --> 00:12:30,950
>> Quanti elementi sono nella matrice numeri?

171
00:12:30,950 --> 00:12:33,630
[Studenti] Numeri, staffe,. Lunghezza?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Che non esiste in C.

173
00:12:36,600 --> 00:12:38,580
Bisogno. Lunghezza.

174
00:12:38,580 --> 00:12:42,010
Gli array non hanno proprietà, quindi non c'è alcuna proprietà lunghezza di array

175
00:12:42,010 --> 00:12:45,650
che sarà solo darvi tutto il tempo capita di essere.

176
00:12:48,180 --> 00:12:51,620
[Studente] Cfr. la quantità di memoria che ha e dividere per quanto - >> Si '.

177
00:12:51,620 --> 00:12:55,810
Quindi, come possiamo vedere quanta memoria ha? >> [Studente] sizeof. >> Si ', sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof è l'operatore che sta per restituire la dimensione della matrice numeri.

179
00:13:01,680 --> 00:13:10,060
E che sta per essere numeri interi ma ci sono molte volte più grande di un numero intero

180
00:13:10,060 --> 00:13:14,050
dato che è la quantità di memoria che in realtà è occupare.

181
00:13:14,050 --> 00:13:17,630
Quindi, se voglio il numero di cose nella matrice,

182
00:13:17,630 --> 00:13:20,560
allora ho intenzione di voler dividere per le dimensioni di un intero.

183
00:13:22,820 --> 00:13:26,010
Va bene. In modo che mi permette di passare in formato qui.

184
00:13:26,010 --> 00:13:29,430
Perché ho bisogno di passare in dimensioni a tutti?

185
00:13:29,430 --> 00:13:38,570
Perché non posso semplicemente fare qui int size = sizeof (pagliaio) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Perché questo non funziona?

187
00:13:41,490 --> 00:13:44,470
[Studente] Non è una variabile globale.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack esiste e stiamo passando a numeri come pagliaio,

189
00:13:51,540 --> 00:13:54,700
e questo è una sorta di prefigurazione di quello che verrà. Gia '.

190
00:13:54,700 --> 00:14:00,170
[Studente] Haystack è solo il riferimento ad esso, in modo che sarebbe tornato quanto grande che sia di riferimento.

191
00:14:00,170 --> 00:14:02,150
Gia '.

192
00:14:02,150 --> 00:14:09,000
Dubito in conferenza aver visto la pila ancora veramente, giusto?

193
00:14:09,000 --> 00:14:11,270
Abbiamo appena parlato.

194
00:14:11,270 --> 00:14:16,090
Quindi lo stack è dove tutte le variabili stanno per essere memorizzati.

195
00:14:16,090 --> 00:14:19,960
>> Ogni memoria è allocata per le variabili locali sta nello stack,

196
00:14:19,960 --> 00:14:24,790
e ogni funzione prende il suo spazio nello stack, il suo stack frame è ciò che si chiama.

197
00:14:24,790 --> 00:14:31,590
Così ha il suo principale stack frame, e all'interno di esso sta per esistere questa matrice di numeri,

198
00:14:31,590 --> 00:14:34,270
e sta andando ad essere di dimensione sizeof (numeri).

199
00:14:34,270 --> 00:14:38,180
E 'intenzione di avere dimensioni di numeri divisi da dimensione degli elementi,

200
00:14:38,180 --> 00:14:42,010
ma che tutte le vite all'interno dello stack frame principale.

201
00:14:42,010 --> 00:14:45,190
Quando chiamiamo ricerca, la ricerca prende il telaio proprio stack,

202
00:14:45,190 --> 00:14:48,840
proprio spazio per archiviare tutte le sue variabili locali.

203
00:14:48,840 --> 00:14:56,420
Ma questi argomenti - in modo da pagliaio non è una copia di questo intero array.

204
00:14:56,420 --> 00:15:00,990
Non passare l'intero array come una copia in ricerca.

205
00:15:00,990 --> 00:15:04,030
Passa solo un riferimento a tale matrice.

206
00:15:04,030 --> 00:15:11,470
Così ricerca può accedere a questi numeri attraverso questo riferimento.

207
00:15:11,470 --> 00:15:17,100
E 'ancora l'accesso alle cose che vivono dentro di stack frame principale,

208
00:15:17,100 --> 00:15:22,990
ma in fondo, quando si arriva a puntatori, che dovrebbe essere presto,

209
00:15:22,990 --> 00:15:24,980
questo è ciò che i puntatori sono.

210
00:15:24,980 --> 00:15:29,400
I puntatori sono solo riferimenti a cose, ed è possibile utilizzare i puntatori per accedere a cose

211
00:15:29,400 --> 00:15:32,030
che sono in stack frame altre cose ».

212
00:15:32,030 --> 00:15:37,660
Così, anche se i numeri è locale principale, possiamo ancora accedere attraverso questo puntatore.

213
00:15:37,660 --> 00:15:41,770
Ma dal momento che è solo un puntatore ed è solo un punto di riferimento,

214
00:15:41,770 --> 00:15:45,040
sizeof (pagliaio) restituisce solo la dimensione del riferimento stesso.

215
00:15:45,040 --> 00:15:47,950
Non restituire la dimensione della cosa sta indicando.

216
00:15:47,950 --> 00:15:51,110
Essa non restituisce la dimensione effettiva dei numeri.

217
00:15:51,110 --> 00:15:55,660
E quindi questo non è andare a lavorare come vogliamo che.

218
00:15:55,660 --> 00:15:57,320
>> Domande su questo?

219
00:15:57,320 --> 00:16:03,250
Puntatori sarà andato in in dettaglio molto più cruento nelle settimane a venire.

220
00:16:06,750 --> 00:16:13,740
Ed è per questo che un sacco di cose che si vedono, la maggior parte delle cose di ricerca o cose di ordinamento,

221
00:16:13,740 --> 00:16:16,990
sono quasi tutti bisogno di andare a prendere la dimensione effettiva della matrice,

222
00:16:16,990 --> 00:16:20,440
perché in C, non abbiamo idea di quale sia la dimensione della matrice è.

223
00:16:20,440 --> 00:16:22,720
È necessario passare manualmente trovi

224
00:16:22,720 --> 00:16:27,190
E non si può passare manualmente l'intero array perché sei solo di passaggio nel riferimento

225
00:16:27,190 --> 00:16:30,390
e non può ottenere la dimensione di riferimento.

226
00:16:30,390 --> 00:16:32,300
Va bene.

227
00:16:32,300 --> 00:16:38,160
Quindi ora vogliamo attuare ciò che è stato spiegato in precedenza.

228
00:16:38,160 --> 00:16:41,530
È possibile lavorare su di esso per un minuto,

229
00:16:41,530 --> 00:16:45,250
e non dovete preoccuparvi di ottenere tutto perfettamente funzionante al 100%.

230
00:16:45,250 --> 00:16:51,410
Basta scrivere il pseudocodice metà per come si pensa che dovrebbe funzionare.

231
00:16:52,000 --> 00:16:53,630
Va bene.

232
00:16:53,630 --> 00:16:56,350
Non c'è bisogno di essere completamente fatto con questo ancora.

233
00:16:56,350 --> 00:17:02,380
Ma qualcuno sentirsi a proprio agio con quello che hanno fino ad ora,

234
00:17:02,380 --> 00:17:05,599
come qualcosa che possiamo lavorare con insieme?

235
00:17:05,599 --> 00:17:09,690
Qualcuno vuole fare volontariato? Oppure scegliere in modo casuale.

236
00:17:12,680 --> 00:17:18,599
Non deve essere proprio di ogni misura, ma qualcosa che si può modificare in uno stato di lavoro.

237
00:17:18,599 --> 00:17:20,720
[Studente] Certo. Va bene >>.

238
00:17:20,720 --> 00:17:27,220
Così si può salvare la revisione facendo clic sulla piccola icona Salva.

239
00:17:27,220 --> 00:17:29,950
Hai Ramya, giusto? >> [Studente] Si '. >> [Bowden] Ok.

240
00:17:29,950 --> 00:17:35,140
Così ora posso visualizzare la revisione e tutti possono tirare su la revisione.

241
00:17:35,140 --> 00:17:38,600
E qui abbiamo - Va bene.

242
00:17:38,600 --> 00:17:43,160
Così Ramya andato con la soluzione ricorsiva, che è sicuramente una valida soluzione.

243
00:17:43,160 --> 00:17:44,970
Ci sono due modi per fare questo problema.

244
00:17:44,970 --> 00:17:48,060
È possibile fare in modo ricorsivo o iterativo.

245
00:17:48,060 --> 00:17:53,860
La maggior parte dei problemi che si verificano che può essere fatto in modo ricorsivo può essere fatto anche iterativamente.

246
00:17:53,860 --> 00:17:58,510
Quindi qui abbiamo fatto in modo ricorsivo.

247
00:17:58,510 --> 00:18:03,730
>> Qualcuno vuole definire che cosa significa fare una funzione ricorsiva?

248
00:18:07,210 --> 00:18:08,920
[Studente] Quando si dispone di una funzione di chiamare se stesso

249
00:18:08,920 --> 00:18:13,470
e poi si chiama fino a quando non esce con vero e vero. Sì >>.

250
00:18:13,470 --> 00:18:17,680
Una funzione ricorsiva è solo una funzione che si chiama.

251
00:18:17,680 --> 00:18:24,140
Ci sono tre grandi cose che una funzione ricorsiva deve avere.

252
00:18:24,140 --> 00:18:27,310
Il primo è, ovviamente, che si chiama.

253
00:18:27,310 --> 00:18:29,650
Il secondo è il caso base.

254
00:18:29,650 --> 00:18:33,390
Quindi, ad un certo punto la funzione deve smettere di chiamare se stesso,

255
00:18:33,390 --> 00:18:35,610
ed è quello che il caso base è per.

256
00:18:35,610 --> 00:18:43,860
Ecco allora sappiamo che dovremmo smettere, dovremmo rinunciare nella nostra ricerca

257
00:18:43,860 --> 00:18:48,150
quando inizio è uguale a fine - e andremo su ciò che significa.

258
00:18:48,150 --> 00:18:52,130
Ma alla fine, l'ultima cosa che è importante per le funzioni ricorsive:

259
00:18:52,130 --> 00:18:59,250
le funzioni deve in qualche modo avvicinarsi al caso base.

260
00:18:59,250 --> 00:19:04,140
Come se non si è in realtà l'aggiornamento nulla quando si effettua la seconda chiamata ricorsiva,

261
00:19:04,140 --> 00:19:07,880
se si sta letteralmente chiamando la funzione di nuovo con gli stessi argomenti

262
00:19:07,880 --> 00:19:10,130
e non le variabili globali sono cambiati o altro,

263
00:19:10,130 --> 00:19:14,430
che non potrà mai raggiungere il caso base, in questo caso non va bene.

264
00:19:14,430 --> 00:19:17,950
Sarà una ricorsione infinita e un overflow dello stack.

265
00:19:17,950 --> 00:19:24,330
Ma qui vediamo che l'aggiornamento è in corso in quanto stiamo aggiornando start + end / 2,

266
00:19:24,330 --> 00:19:28,180
stiamo aggiornando l'argomento fin qui, stiamo aggiornando l'argomento start qui.

267
00:19:28,180 --> 00:19:32,860
Così in tutte le chiamate ricorsive stiamo aggiornando qualcosa. Va bene.

268
00:19:32,860 --> 00:19:38,110
Vuoi camminare noi tramite la tua soluzione? Certo >>.

269
00:19:38,110 --> 00:19:44,270
Sto utilizzando SearchHelp in modo che ogni volta che faccio questa chiamata di funzione

270
00:19:44,270 --> 00:19:47,910
Ho l'inizio di dove sto cercando nella matrice e la fine

271
00:19:47,910 --> 00:19:49,380
di dove sto cercando la matrice.

272
00:19:49,380 --> 00:19:55,330
>> Ad ogni passo dove sta dicendo che è l'elemento centrale, che è inizio + fine / 2,

273
00:19:55,330 --> 00:19:58,850
che è uguale a quello che stiamo cercando?

274
00:19:58,850 --> 00:20:04,650
E se lo è, allora lo abbiamo trovato, e credo che viene superato i livelli di ricorsione.

275
00:20:04,650 --> 00:20:12,540
E se questo non è vero, allora verificare se tale valore medio della matrice è troppo grande,

276
00:20:12,540 --> 00:20:19,320
nel qual caso guardiamo la metà sinistra della matrice andando dall'inizio all'indice medio.

277
00:20:19,320 --> 00:20:22,710
E altrimenti facciamo la metà fine.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Ok.

279
00:20:24,740 --> 00:20:27,730
Ottima idea.

280
00:20:27,730 --> 00:20:36,640
Ok, quindi un paio di cose, e in realtà, questa è una cosa di altissimo livello

281
00:20:36,640 --> 00:20:41,270
che non avrai mai bisogno di sapere per questo corso, ma è vero.

282
00:20:41,270 --> 00:20:46,080
Funzioni ricorsive, è sempre sentito che sono un cattivo affare

283
00:20:46,080 --> 00:20:51,160
perché se in modo ricorsivo chiamarti troppe volte, si ottiene un overflow dello stack

284
00:20:51,160 --> 00:20:54,990
dal momento che, come ho detto prima, ogni funzione prende il telaio proprio stack.

285
00:20:54,990 --> 00:20:59,500
Così ogni chiamata della funzione ricorsiva prende il telaio proprio stack.

286
00:20:59,500 --> 00:21:04,140
Quindi, se si fanno 1.000 chiamate ricorsive, si ottiene 1.000 stack frame,

287
00:21:04,140 --> 00:21:08,390
e rapidamente vi porterà ad avere stack frame troppe cose e solo rompere.

288
00:21:08,390 --> 00:21:13,480
Allora è per questo che le funzioni ricorsive sono generalmente male.

289
00:21:13,480 --> 00:21:19,370
Ma vi è un sottoinsieme piacevole di funzioni ricorsive chiamato coda funzioni ricorsive,

290
00:21:19,370 --> 00:21:26,120
e questo sembra essere un esempio di quella in cui il compilatore se ne accorge

291
00:21:26,120 --> 00:21:29,920
e dovrebbe, credo - in Clang se gli viene passato il flag-O2

292
00:21:29,920 --> 00:21:33,250
poi si noterà questo è tail ricorsiva e fare le cose bene.

293
00:21:33,250 --> 00:21:40,050
>> Si riutilizzare lo stesso telaio dello stack più e più volte per ogni chiamata ricorsiva.

294
00:21:40,050 --> 00:21:47,010
E così dal momento che si sta utilizzando lo stesso telaio dello stack, non è necessario preoccuparsi di

295
00:21:47,010 --> 00:21:51,690
impilare mai traboccante, e al tempo stesso, come hai detto prima,

296
00:21:51,690 --> 00:21:56,380
dove una volta si torna vero, allora deve restituire il backup di tutti questi stack frame

297
00:21:56,380 --> 00:22:01,740
e la chiamata 10 al SearchHelp deve tornare al 9, è tenuto a restituire al 8.

298
00:22:01,740 --> 00:22:05,360
In modo che non ha bisogno di accadere quando le funzioni sono coda ricorsiva.

299
00:22:05,360 --> 00:22:13,740
E così ciò che rende questa coda funzione ricorsiva è notare che per ogni invito a searchHelp

300
00:22:13,740 --> 00:22:18,470
la chiamata ricorsiva che si sta facendo è quello che sta tornando.

301
00:22:18,470 --> 00:22:25,290
Così nella prima chiamata a SearchHelp, si sia immediatamente restituire false,

302
00:22:25,290 --> 00:22:29,590
immediatamente restituire true, oppure effettuare una chiamata ricorsiva a SearchHelp

303
00:22:29,590 --> 00:22:33,810
dove quello che stiamo tornando è ciò che la chiamata sta tornando.

304
00:22:33,810 --> 00:22:51,560
E non abbiamo potuto fare questo se abbiamo fatto qualcosa di simile int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
solo un po 'di cambiamento casuale.

306
00:22:55,440 --> 00:23:01,470
>> Così ora questa chiamata ricorsiva, questo int x = chiamata SearchHelp ricorsiva,

307
00:23:01,470 --> 00:23:05,740
non è più la coda ricorsiva, perché in realtà ha bisogno di tornare

308
00:23:05,740 --> 00:23:10,400
di nuovo ad un stack frame precedente in modo che la chiamata precedente alla funzione

309
00:23:10,400 --> 00:23:13,040
È quindi possibile fare qualcosa con il valore di ritorno.

310
00:23:13,040 --> 00:23:22,190
Quindi questo non è tail ricorsiva, ma quello che avevamo prima è ben coda ricorsiva. Gia '.

311
00:23:22,190 --> 00:23:27,000
[Studente] non dovrebbe seconda base caso essere controllato per primo

312
00:23:27,000 --> 00:23:30,640
perché ci potrebbe essere una situazione in cui quando si passa l'argomento

313
00:23:30,640 --> 00:23:35,770
aver inizio = fine, ma sono il valore ago.

314
00:23:35,770 --> 00:23:47,310
La questione è stata non possiamo correre nel caso in cui il valore finale è dell'ago

315
00:23:47,310 --> 00:23:52,000
o avviare = fine, opportunamente, inizio fine =

316
00:23:52,000 --> 00:23:59,480
e non si è effettivamente verificato che il valore particolare ancora,

317
00:23:59,480 --> 00:24:03,910
quindi avviare + finale / 2 è solo andare a essere lo stesso valore.

318
00:24:03,910 --> 00:24:07,890
Ma abbiamo già restituito false e non abbiamo mai effettivamente controllato il valore.

319
00:24:07,890 --> 00:24:14,240
Così per lo meno, in prima convocazione, se la dimensione è 0, allora vogliamo restituire false.

320
00:24:14,240 --> 00:24:17,710
Ma se la dimensione è 1, allora inizio non sta per finire pari,

321
00:24:17,710 --> 00:24:19,820
e noi provvederemo a verificare almeno l'unico elemento.

322
00:24:19,820 --> 00:24:26,750
Ma credo che tu abbia ragione nel senso che possiamo finire in un caso in cui inizio + fine / 2,

323
00:24:26,750 --> 00:24:31,190
start finisce per essere la stessa di inizio + fine / 2,

324
00:24:31,190 --> 00:24:35,350
ma in realtà non abbiamo mai verificato tale elemento.

325
00:24:35,350 --> 00:24:44,740
>> Quindi, se per prima cosa controllare è l'elemento centrale il valore che stiamo cercando,

326
00:24:44,740 --> 00:24:47,110
allora possiamo immediatamente restituire true.

327
00:24:47,110 --> 00:24:50,740
Altrimenti se sono uguali, allora non c'è ragione di continuare

328
00:24:50,740 --> 00:24:58,440
dal momento che stiamo solo andando a l'aggiornamento a un caso in cui siamo su un singolo elemento di un array.

329
00:24:58,440 --> 00:25:01,110
Se questo elemento non è quello che stiamo cercando,

330
00:25:01,110 --> 00:25:03,530
allora tutto è sbagliato. Gia '.

331
00:25:03,530 --> 00:25:08,900
[Studente] Il fatto è che, poiché la dimensione è in realtà maggiore del numero di elementi nella matrice,

332
00:25:08,900 --> 00:25:13,070
c'è già un offset - >> Così sarà formato -

333
00:25:13,070 --> 00:25:19,380
[Studente] Dire se la matrice era di dimensioni 0, il SearchHelp effettivamente verificare pagliaio di 0

334
00:25:19,380 --> 00:25:21,490
in prima convocazione.

335
00:25:21,490 --> 00:25:25,300
La matrice ha dimensione 0, in modo che il 0 è - >> Si '.

336
00:25:25,300 --> 00:25:30,750
C'è un'altra cosa che - che potrebbe essere buono. Pensiamo.

337
00:25:30,750 --> 00:25:40,120
Quindi, se l'array ha 10 elementi e quella centrale che andremo a controllare è indice 5,

338
00:25:40,120 --> 00:25:45,700
quindi stiamo controllando 5, e diciamo che il valore è inferiore.

339
00:25:45,700 --> 00:25:50,720
Quindi stiamo buttando via tutto da 5 in poi.

340
00:25:50,720 --> 00:25:54,030
Così inizia + finale / 2 sarà la nostra fine nuovo,

341
00:25:54,030 --> 00:25:57,450
Quindi sì, è sempre intenzione di rimanere oltre la fine della matrice.

342
00:25:57,450 --> 00:26:03,570
Se si tratta di un caso se era pari o dispari, allora dovremmo controllare, per esempio, 4,

343
00:26:03,570 --> 00:26:05,770
ma stiamo ancora buttando via -

344
00:26:05,770 --> 00:26:13,500
Quindi sì, la fine sta andando sempre di essere al di là della fine effettiva della matrice.

345
00:26:13,500 --> 00:26:18,350
Quindi gli elementi che si stanno concentrando su, fine sta andando sempre essere quello dopo.

346
00:26:18,350 --> 00:26:24,270
E così se all'inizio fa mai fine uguali, siamo in un array di dimensione 0.

347
00:26:24,270 --> 00:26:35,600
>> L'altra cosa che ho pensato è che stiamo aggiornando start per avviare da fine + / 2,

348
00:26:35,600 --> 00:26:44,020
quindi questo è il caso che io sto avendo problemi con, dove partono + finale / 2

349
00:26:44,020 --> 00:26:46,820
è l'elemento che stiamo controllando.

350
00:26:46,820 --> 00:26:58,150
Diciamo che abbiamo avuto questo 10-elemento di matrice. Qualunque cosa.

351
00:26:58,150 --> 00:27:03,250
Così inizia + finale / 2 sta per essere qualcosa come questo,

352
00:27:03,250 --> 00:27:07,060
e se questo non è il valore, diciamo che vogliamo aggiornare.

353
00:27:07,060 --> 00:27:10,060
Il valore è maggiore, quindi vogliamo guardare a questa metà della matrice.

354
00:27:10,060 --> 00:27:15,910
Così come stiamo aggiornando inizio, stiamo aggiornando inizio ad essere ora questo elemento.

355
00:27:15,910 --> 00:27:23,790
Ma questo può ancora funzionare, o per lo meno, si può fare di inizio + fine / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Studente] Non è necessario iniziare da fine + [incomprensibile] >> Si '.

357
00:27:27,850 --> 00:27:33,240
Abbiamo già verificato questo elemento e so che non è quello che stiamo cercando.

358
00:27:33,240 --> 00:27:36,800
Quindi non c'è bisogno di aggiornare dall'inizio per essere questo elemento.

359
00:27:36,800 --> 00:27:39,560
Possiamo basta saltare e aggiornare iniziano ad essere questo elemento.

360
00:27:39,560 --> 00:27:46,060
E c'è sempre un caso, diciamo, che questo fosse fine,

361
00:27:46,060 --> 00:27:53,140
così poi iniziare è questo, start + finale / 2 sarebbe questo,

362
00:27:53,140 --> 00:28:00,580
inizio fine + - Si ', penso che possa finire in una ricorsione infinita.

363
00:28:00,580 --> 00:28:12,690
Diciamo che è solo un array di dimensione 2 o un array di dimensione 1. Penso che questo possa funzionare.

364
00:28:12,690 --> 00:28:19,490
Quindi al momento, è l'elemento di inizio e fine è 1 di là di esso.

365
00:28:19,490 --> 00:28:24,110
Quindi, l'elemento che stiamo andando a controllare è questo,

366
00:28:24,110 --> 00:28:29,400
e poi quando si aggiorna inizio, stiamo aggiornando dall'inizio per essere 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
che sta per finire ci riporta con partenza essendo questo elemento.

368
00:28:33,160 --> 00:28:36,210
>> Quindi stiamo controllando lo stesso elemento più e più volte.

369
00:28:36,210 --> 00:28:43,310
Quindi questo è il caso in cui ogni chiamata ricorsiva deve essere effettivamente aggiornare qualcosa.

370
00:28:43,310 --> 00:28:48,370
Quindi abbiamo bisogno di fare start + end / 2 + 1, oppure c'è un caso

371
00:28:48,370 --> 00:28:50,710
dove non è in realtà l'aggiornamento iniziale.

372
00:28:50,710 --> 00:28:53,820
Ognuno vede che?

373
00:28:53,820 --> 00:28:56,310
Va bene.

374
00:28:56,310 --> 00:29:03,860
Qualcuno ha domande su questa soluzione o commenti più?

375
00:29:05,220 --> 00:29:10,280
Va bene. Qualcuno ha una soluzione iterativa che tutti noi possiamo guardare?

376
00:29:17,400 --> 00:29:20,940
Abbiamo tutti lo fanno in modo ricorsivo?

377
00:29:20,940 --> 00:29:25,950
O anche Credo che se lei ha aperto, allora si potrebbe avere sovrascritto a quello precedente.

378
00:29:25,950 --> 00:29:28,810
Ha salva automaticamente? Io non sono positive.

379
00:29:35,090 --> 00:29:39,130
Qualcuno ha iterativo?

380
00:29:39,130 --> 00:29:42,430
Siamo in grado di camminare attraverso di essa, se non insieme.

381
00:29:46,080 --> 00:29:48,100
L'idea sarà lo stesso.

382
00:30:00,260 --> 00:30:02,830
Iterativo soluzione.

383
00:30:02,830 --> 00:30:07,140
Stiamo andando a voler fare sostanzialmente la stessa idea

384
00:30:07,140 --> 00:30:16,530
dove vogliamo tenere traccia della nuova fine della matrice e il nuovo inizio della matrice

385
00:30:16,530 --> 00:30:18,510
e farlo più e più volte.

386
00:30:18,510 --> 00:30:22,430
E se quello che stiamo tenendo traccia di come l'inizio e la fine sempre si intersecano,

387
00:30:22,430 --> 00:30:29,020
allora non lo abbiamo trovato e siamo in grado di restituire false.

388
00:30:29,020 --> 00:30:37,540
Allora, come faccio a farlo? Qualcuno ha suggerimenti o codice per me per tirare su?

389
00:30:42,190 --> 00:30:47,450
[Studente] fare un ciclo while. Sì >>.

390
00:30:47,450 --> 00:30:49,450
Stai andando a voler fare un ciclo.

391
00:30:49,450 --> 00:30:51,830
>> Lo si dispone di codice potrei tirare su, o quello che volevi suggerire?

392
00:30:51,830 --> 00:30:56,340
[Studente] Penso di sì. Va bene >>. Questo rende le cose più facili. Qual era il suo nome?

393
00:30:56,340 --> 00:30:57,890
[Studente] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisione 1. Va bene.

395
00:31:04,190 --> 00:31:13,200
Basso è quello che abbiamo chiamato prima di iniziare.

396
00:31:13,200 --> 00:31:17,080
Up non è proprio quello che abbiamo chiamato prima della fine.

397
00:31:17,080 --> 00:31:22,750
In realtà, alla fine è ora all'interno della matrice. E 'un elemento che dovrebbe prendere in considerazione.

398
00:31:22,750 --> 00:31:26,890
Così basso è 0, è la dimensione della matrice - 1,

399
00:31:26,890 --> 00:31:34,780
e ora stiamo looping, e stiamo verificando -

400
00:31:34,780 --> 00:31:37,340
Credo che si può raggiungere a piedi attraverso di essa.

401
00:31:37,340 --> 00:31:41,420
Qual è stato il vostro pensiero attraverso questo? Cammina con noi attraverso il vostro codice.

402
00:31:41,420 --> 00:31:49,940
[Studente] Certo. Guarda il valore pagliaio in mezzo e confrontarlo con l'ago.

403
00:31:49,940 --> 00:31:58,520
Quindi, se è più grande del tuo ago, poi si vuole - oh, in realtà, che dovrebbe essere al contrario.

404
00:31:58,520 --> 00:32:05,180
Stai andando a voler buttare via la metà destra, e quindi si, che dovrebbe essere la strada.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Quindi questo dovrebbe essere meno? È che quello che hai detto? >> [Studente] Si '.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Ok. Di meno.

407
00:32:10,390 --> 00:32:15,700
Quindi, se ciò che stiamo guardando è più piccolo di quello che vogliamo,

408
00:32:15,700 --> 00:32:19,410
allora sì, si vuole buttare via la metà sinistra,

409
00:32:19,410 --> 00:32:22,210
il che significa che stiamo aggiornando tutto quello che stiamo considerando

410
00:32:22,210 --> 00:32:26,610
spostando basso a destra della matrice.

411
00:32:26,610 --> 00:32:30,130
Questo sembra buono.

412
00:32:30,130 --> 00:32:34,550
Io penso che abbia lo stesso problema che abbiamo detto su quello precedente,

413
00:32:34,550 --> 00:32:49,760
dove se bassa è 0 ed è alto 1, quindi a basso + up / 2 sta per impostare fino a essere la stessa cosa di nuovo.

414
00:32:49,760 --> 00:32:53,860
>> E anche se non è questo il caso, è ancora più efficiente per lo meno

415
00:32:53,860 --> 00:32:57,630
sbarazzarvi l'elemento che abbiamo appena visto che sappiamo essere sbagliato.

416
00:32:57,630 --> 00:33:03,240
Così basso + alto / 2 + 1 - >> [studente] Questo dovrebbe essere il contrario.

417
00:33:03,240 --> 00:33:05,900
[Bowden] O questo dovrebbe essere - uno e l'altro deve essere + 1.

418
00:33:05,900 --> 00:33:09,580
[Studente] E ci dovrebbe essere un doppio segno di uguale. >> [Bowden] Si '.

419
00:33:09,580 --> 00:33:11,340
[Studente] Si '.

420
00:33:14,540 --> 00:33:15,910
Va bene.

421
00:33:15,910 --> 00:33:21,280
E, infine, ora che abbiamo questo + 1 - 1 cosa,

422
00:33:21,280 --> 00:33:31,520
è - non può essere - è mai possibile che da basso a finire con un valore maggiore di up?

423
00:33:35,710 --> 00:33:40,320
Penso che l'unico modo che può accadere - E 'possibile? >> [Studente] Non lo so.

424
00:33:40,320 --> 00:33:45,220
Ma se si tronca e poi si fa meno che 1 e poi - >> Si '.

425
00:33:45,220 --> 00:33:47,480
[Studente] Sarebbe forse avere incasinato.

426
00:33:49,700 --> 00:33:53,940
Penso che dovrebbe essere buona solo perché

427
00:33:53,940 --> 00:33:58,800
per farlo finire inferiore avrebbero dovuto essere uguali, credo.

428
00:33:58,800 --> 00:34:03,070
Ma se sono uguali, allora non avrebbe fatto il ciclo while per cominciare

429
00:34:03,070 --> 00:34:06,670
e abbiamo appena avrebbe restituito il valore. Quindi penso che siamo a posto ora.

430
00:34:06,670 --> 00:34:11,530
Si noti che anche se questo problema non è più ricorsiva,

431
00:34:11,530 --> 00:34:17,400
lo stesso tipo di idee si applicano dove possiamo vedere come questo così facilmente si presta

432
00:34:17,400 --> 00:34:23,659
ad una soluzione ricorsiva dal fatto che stiamo solo aggiornando gli indici più e più volte,

433
00:34:23,659 --> 00:34:29,960
stiamo rendendo il problema più piccolo, ci stiamo concentrando su un sottoinsieme della matrice.

434
00:34:29,960 --> 00:34:40,860
[Studente] Se basso è 0 e fino a 1, che sarebbero entrambi 0 + 1/2, che sarebbe andato a 0,

435
00:34:40,860 --> 00:34:44,429
e poi uno sarebbe + 1, uno sarebbe - 1.

436
00:34:47,000 --> 00:34:50,870
[Studente] Dove stiamo verificando l'uguaglianza?

437
00:34:50,870 --> 00:34:55,100
Come se quello centrale è in realtà l'ago?

438
00:34:55,100 --> 00:34:58,590
Non stiamo facendo attualmente che? Oh!

439
00:35:00,610 --> 00:35:02,460
Se E'-

440
00:35:05,340 --> 00:35:13,740
Sì. Non possiamo fare la prova qui, perché diciamo la prima metà -

441
00:35:13,740 --> 00:35:16,430
[Studente] In realtà è come non buttare via il limite.

442
00:35:16,430 --> 00:35:20,220
Quindi, se buttare via il limite, è necessario verificare in primo luogo o qualsiasi altra cosa.

443
00:35:20,220 --> 00:35:23,350
Ah. Gia '. >> [Studente] Si '.

444
00:35:23,350 --> 00:35:29,650
Così ora abbiamo buttato via quella che abbiamo attualmente esaminato,

445
00:35:29,650 --> 00:35:33,260
il che significa che ora abbiamo bisogno di avere anche

446
00:35:33,260 --> 00:35:44,810
if (pagliaio [(basso + alto) / 2] == ago), allora possiamo restituire true.

447
00:35:44,810 --> 00:35:52,070
E se ho messo altro o solo se, letteralmente significa la stessa cosa

448
00:35:52,070 --> 00:35:57,110
perché questo avrebbe restituito true.

449
00:35:57,110 --> 00:36:01,450
Così mi metterò altro se, ma non importa.

450
00:36:01,450 --> 00:36:10,440
>> Quindi, se questo altro, altrimenti questo, e questa è una cosa comune che faccio

451
00:36:10,440 --> 00:36:14,340
dove anche se è il caso in cui tutto è buono qui,

452
00:36:14,340 --> 00:36:22,780
come il basso non può mai essere superiore in su, non è un ragionamento un valore di circa se questo è vero.

453
00:36:22,780 --> 00:36:28,010
Così si può anche dire che, mentre bassa è inferiore o uguale a

454
00:36:28,010 --> 00:36:30,720
o mentre bassa è inferiore

455
00:36:30,720 --> 00:36:35,300
quindi se sono mai uguali o bassa succede a passare in su,

456
00:36:35,300 --> 00:36:40,130
allora possiamo uscire da questo ciclo.

457
00:36:41,410 --> 00:36:44,630
Domande, dubbi, commenti?

458
00:36:47,080 --> 00:36:49,270
Va bene. Questo sembra buono.

459
00:36:49,270 --> 00:36:52,230
Ora vogliamo fare di ordinamento.

460
00:36:52,230 --> 00:37:04,030
Se andiamo alla mia seconda revisione, vediamo questi stessi numeri,

461
00:37:04,030 --> 00:37:07,550
ma ora non sono più in modo ordinato.

462
00:37:07,550 --> 00:37:12,840
E vogliamo implementare l'ordinamento utilizzando qualsiasi algoritmo in O di n log n.

463
00:37:12,840 --> 00:37:17,240
Quindi l'algoritmo pensi che dovrebbe attuare qui? >> [Studente] merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Si '. Merge sort è O (n log n), ed è quello che stiamo per fare.

465
00:37:23,810 --> 00:37:26,680
E il problema sta per essere abbastanza simili,

466
00:37:26,680 --> 00:37:31,920
dove si presta facilmente ad una soluzione ricorsiva.

467
00:37:31,920 --> 00:37:35,580
Possiamo anche trovare una soluzione iterativa, se vogliamo,

468
00:37:35,580 --> 00:37:42,540
ricorsione, ma sarà più facile qui e dobbiamo fare la ricorsione.

469
00:37:45,120 --> 00:37:49,530
Credo che ci guiderà attraverso merge sort in primo luogo,

470
00:37:49,530 --> 00:37:54,280
anche se vi è un video lovely di merge sort già. [Risate]

471
00:37:54,280 --> 00:37:59,780
Quindi merge sort ci sono - sto sprecando così tanto di questo lavoro.

472
00:37:59,780 --> 00:38:02,080
Oh, c'è solo una sinistra.

473
00:38:02,080 --> 00:38:03,630
Così si fondono.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Va bene.

476
00:38:29,910 --> 00:38:33,460
Merge prende due array separati.

477
00:38:33,460 --> 00:38:36,780
Individualmente i due array sono entrambi ordinati.

478
00:38:36,780 --> 00:38:40,970
Quindi questo array, 1, 3, 5, ordinato. Questo array, 0, 2, 4, ordinato.

479
00:38:40,970 --> 00:38:46,710
Ora che cosa unione dovrebbe fare è combinare in un singolo array che è esso stesso ordinati.

480
00:38:46,710 --> 00:38:57,130
Quindi vogliamo un array di dimensione 6 che sta per avere questi elementi all'interno di esso

481
00:38:57,130 --> 00:38:59,390
in modo ordinato.

482
00:38:59,390 --> 00:39:03,390
>> E così siamo in grado di approfittare del fatto che questi due array sono ordinati

483
00:39:03,390 --> 00:39:06,800
per fare questo in tempo lineare,

484
00:39:06,800 --> 00:39:13,510
significato tempo lineare se questo array è x dimensioni e questo è y dimensioni,

485
00:39:13,510 --> 00:39:20,970
allora l'algoritmo totale dovrebbe essere O (x + y). Va bene.

486
00:39:20,970 --> 00:39:23,150
Così suggerimenti.

487
00:39:23,150 --> 00:39:26,030
[Studente] Si potrebbe ricominciare da sinistra?

488
00:39:26,030 --> 00:39:30,150
Quindi metto giù lo 0 e poi il 1 e poi qui siete al 2.

489
00:39:30,150 --> 00:39:33,320
Quindi è un po 'come si dispone di una scheda che si muove verso destra. >> [Bowden] Si '.

490
00:39:33,320 --> 00:39:41,070
Per entrambi questi array, se solo concentrarsi sull'elemento più a sinistra.

491
00:39:41,070 --> 00:39:43,530
Dato che entrambi gli array sono ordinati, si sa che questi 2 elementi

492
00:39:43,530 --> 00:39:46,920
sono i più piccoli elementi o matrice.

493
00:39:46,920 --> 00:39:53,500
In modo che significa che 1 di questi 2 elementi deve essere il più piccolo elemento nel nostro array fuso.

494
00:39:53,500 --> 00:39:58,190
Si dà il caso che il più piccolo è quello sulla destra questa volta.

495
00:39:58,190 --> 00:40:02,580
Quindi prendiamo 0, inserirla sulla sinistra perché 0 è minore di 1,

496
00:40:02,580 --> 00:40:08,210
in modo da prendere 0, inserirlo nella nostra prima posizione, e poi aggiornare questa

497
00:40:08,210 --> 00:40:12,070
a concentrarsi ora sul primo elemento.

498
00:40:12,070 --> 00:40:14,570
E ora ripetiamo.

499
00:40:14,570 --> 00:40:20,670
Così ora mettiamo a confronto 2 e 1. 1 è più piccolo, quindi dovremo inserire 1.

500
00:40:20,670 --> 00:40:25,300
Aggiorniamo questo puntatore per puntare a questo ragazzo.

501
00:40:25,300 --> 00:40:33,160
Ora lo facciamo di nuovo, in modo 2. Questo aggiornerà, confrontare questi 2, 3.

502
00:40:33,160 --> 00:40:37,770
Questo aggiornamento, poi 4 e 5.

503
00:40:37,770 --> 00:40:42,110
Così che è unione.

504
00:40:42,110 --> 00:40:49,010
>> Dovrebbe essere abbastanza evidente che si tratta di tempo lineare dato che basta andare su ogni elemento di una volta.

505
00:40:49,010 --> 00:40:55,980
E questo è il più grande passo per l'attuazione merge sort sta facendo questo.

506
00:40:55,980 --> 00:40:59,330
E non è così difficile.

507
00:40:59,330 --> 00:41:15,020
Un paio di cose di cui preoccuparsi è diciamo eravamo fusione 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
In questo caso si finisce nello scenario in cui questo sta andando essere più piccoli,

509
00:41:30,930 --> 00:41:36,160
allora aggiorniamo questo puntatore, questo sta andando essere più piccole, aggiornare questo,

510
00:41:36,160 --> 00:41:41,280
questo è più piccolo, e ora si deve riconoscere

511
00:41:41,280 --> 00:41:44,220
quando hai effettivamente eseguito su elementi da confrontare con.

512
00:41:44,220 --> 00:41:49,400
Dal momento che abbiamo già utilizzato questo array,

513
00:41:49,400 --> 00:41:55,190
tutto in questo array è ora appena inserito in questa sede.

514
00:41:55,190 --> 00:42:02,040
Quindi, se mai eseguito nel punto in cui uno dei nostri array è completamente fusa già,

515
00:42:02,040 --> 00:42:06,510
poi basta prendere tutti gli elementi della matrice altro e inserirle nella fine della matrice.

516
00:42:06,510 --> 00:42:13,630
Quindi possiamo solo inserire 4, 5, 6. Va bene.

517
00:42:13,630 --> 00:42:18,070
Questa è una cosa a cui prestare attenzione.

518
00:42:22,080 --> 00:42:26,120
Attuazione che dovrebbe essere il punto 1.

519
00:42:26,120 --> 00:42:32,600
Merge sort poi in base a questo, è a 2 passi, 2 passi stupidi.

520
00:42:38,800 --> 00:42:42,090
Diciamo solo dare questo array.

521
00:42:57,920 --> 00:43:05,680
Così merge sort, punto 1 è quello di rompere ricorsivamente l'array in due metà.

522
00:43:05,680 --> 00:43:09,350
Quindi dividere questo array in due metà.

523
00:43:09,350 --> 00:43:22,920
Ora abbiamo 4, 15, 16, 50 e 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
E ora lo facciamo di nuovo e abbiamo diviso questi a metà.

525
00:43:25,800 --> 00:43:27,530
Ho appena faro 'da questa parte.

526
00:43:27,530 --> 00:43:34,790
Quindi 4, 15 e 16, 50.

527
00:43:34,790 --> 00:43:37,440
Vorremmo fare la stessa cosa qui.

528
00:43:37,440 --> 00:43:40,340
E ora ci si divise in due parti di nuovo.

529
00:43:40,340 --> 00:43:51,080
E abbiamo 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Quindi, questo è il nostro caso base.

531
00:43:53,170 --> 00:44:00,540
Una volta che le matrici sono di dimensione 1, quindi ci fermiamo con la scissione in due parti.

532
00:44:00,540 --> 00:44:03,190
>> Ora che cosa facciamo con questo?

533
00:44:03,190 --> 00:44:15,730
Finiamo questo inoltre si suddividono in 8, 23, 42, e 108.

534
00:44:15,730 --> 00:44:24,000
Quindi, ora che siamo a questo punto, ora passo due di merge sort è solo la fusione coppie alle liste.

535
00:44:24,000 --> 00:44:27,610
Quindi vogliamo unire questi. Ci basta chiamare unione.

536
00:44:27,610 --> 00:44:31,410
Sappiamo unione torneremo questi in modo ordinato.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Ora vogliamo unire questi, e che restituirà una lista con quelli in modo ordinato,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Siamo quelli che si fondono - Non riesco a scrivere - 8, 23 e 42, 108.

541
00:44:57,380 --> 00:45:02,890
Così abbiamo coppie unite una volta.

542
00:45:02,890 --> 00:45:05,140
Ora dobbiamo solo unire di nuovo.

543
00:45:05,140 --> 00:45:10,130
Si noti che ciascuna di queste liste è ordinato in sé,

544
00:45:10,130 --> 00:45:15,220
e poi si può solo unire queste liste per ottenere un elenco di dimensioni 4 che è ordinato

545
00:45:15,220 --> 00:45:19,990
e unione di queste due liste per ottenere un elenco di dimensioni 4 che è ordinato.

546
00:45:19,990 --> 00:45:25,710
E, infine, siamo in grado di unire i due elenchi di dimensione 4 per ottenere una lista di dimensione 8 che è ordinato.

547
00:45:25,710 --> 00:45:34,030
Quindi, per vedere che questo è nel complesso n log n, abbiamo già visto che la fusione è lineare,

548
00:45:34,030 --> 00:45:40,390
così quando abbiamo a che fare con la fusione questi, così come il costo complessivo della fusione

549
00:45:40,390 --> 00:45:43,410
per queste due liste è solo 2 perché -

550
00:45:43,410 --> 00:45:49,610
O beh, e 'O di n, ma n qui è solo questi 2 elementi, in modo che sia 2.

551
00:45:49,610 --> 00:45:52,850
E questi 2 sarà 2 e questi 2 sarà 2 e questi 2 sarà 2,

552
00:45:52,850 --> 00:45:58,820
così su tutte le fusioni che dobbiamo fare, si finisce per fare n.

553
00:45:58,820 --> 00:46:03,210
Come 2 + 2 + 2 + 2 è 8, che è n,

554
00:46:03,210 --> 00:46:08,060
quindi il costo della fusione in questa serie è n.

555
00:46:08,060 --> 00:46:10,810
E poi la stessa cosa qui.

556
00:46:10,810 --> 00:46:16,980
Ci unire questi 2, quindi questi 2, e individualmente questa unione avrà quattro operazioni,

557
00:46:16,980 --> 00:46:23,610
questa unione avrà quattro operazioni, ma ancora una volta, tra tutti questi,

558
00:46:23,610 --> 00:46:29,030
si finisce per unire n cose totali, e così questa operazione richiederà n.

559
00:46:29,030 --> 00:46:33,670
E così ogni livello ha n elementi alla fusione.

560
00:46:33,670 --> 00:46:36,110
>> E quanti livelli ci sono?

561
00:46:36,110 --> 00:46:40,160
Ad ogni livello, la serie cresce taglia 2.

562
00:46:40,160 --> 00:46:44,590
Ecco le nostre matrici sono di dimensione 1, qui sono di dimensione 2, qui sono di dimensione 4,

563
00:46:44,590 --> 00:46:46,470
e, infine, sono di dimensione 8.

564
00:46:46,470 --> 00:46:56,450
Quindi, dal momento che è il raddoppio, ci saranno un totale di n log di questi livelli.

565
00:46:56,450 --> 00:47:02,090
Quindi, con log n livelli, ogni singolo livello di assunzione n operazioni totali,

566
00:47:02,090 --> 00:47:05,720
otteniamo un log n n algoritmo.

567
00:47:05,720 --> 00:47:07,790
Domande?

568
00:47:08,940 --> 00:47:13,320
Sono persone già compiuto progressi sulle modalità di attuazione del presente?

569
00:47:13,320 --> 00:47:18,260
C'è qualcuno che è già in uno stato in cui posso solo tirare su il loro codice?

570
00:47:20,320 --> 00:47:22,260
Posso dare un minuto.

571
00:47:24,770 --> 00:47:27,470
Questo sta andando essere più lungo.

572
00:47:27,470 --> 00:47:28,730
Consiglio vivamente recidiva -

573
00:47:28,730 --> 00:47:30,510
Non è necessario fare la ricorsione per unione

574
00:47:30,510 --> 00:47:33,750
perché per fare la ricorsione per unione, si sta andando ad avere per passare un po 'di diverse dimensioni.

575
00:47:33,750 --> 00:47:37,150
È possibile, ma è fastidioso.

576
00:47:37,150 --> 00:47:43,720
Ma ricorsione per l'ordinamento in sé è abbastanza facile.

577
00:47:43,720 --> 00:47:49,190
Basta chiamare letteralmente ordinamento metà sinistra, sorta a metà destra. Va bene.

578
00:47:51,770 --> 00:47:54,860
Qualcuno ha qualcosa che posso tirare ancora registrato?

579
00:47:54,860 --> 00:47:57,540
Oppure darò un minuto.

580
00:47:58,210 --> 00:47:59,900
Va bene.

581
00:47:59,900 --> 00:48:02,970
Qualcuno ha qualcosa che possiamo lavorare?

582
00:48:05,450 --> 00:48:09,680
Oppure dobbiamo solo lavorare con questo e quindi espandere da lì.

583
00:48:09,680 --> 00:48:14,050
>> Qualcuno ha più di questo che posso tirare su?

584
00:48:14,050 --> 00:48:17,770
[Studente] Si '. Si può tirare la mia. Va bene >>.

585
00:48:17,770 --> 00:48:19,730
Sì!

586
00:48:22,170 --> 00:48:25,280
[Studente] Ci sono stati un sacco di condizioni. >> Oh, cavolo. Can you -

587
00:48:25,280 --> 00:48:28,110
[Studente] devo salvarlo. Sì >>.

588
00:48:32,420 --> 00:48:35,730
Così abbiamo fatto fare l'unione separatamente.

589
00:48:35,730 --> 00:48:38,570
Oh, ma non è così male.

590
00:48:39,790 --> 00:48:41,650
Va bene.

591
00:48:41,650 --> 00:48:47,080
Così sorta in sé è semplicemente chiamando mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Spiegaci cosa mergeSortHelp fa.

593
00:48:49,530 --> 00:48:55,700
[Studente] MergeSortHelp praticamente fa molto le due fasi principali,

594
00:48:55,700 --> 00:49:01,270
che è di ordinare ogni metà della matrice e poi unire entrambi.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, allora dammi un secondo.

596
00:49:10,850 --> 00:49:13,210
Penso che questo - >> [studente] Ho bisogno di -

597
00:49:17,100 --> 00:49:19,400
Gia '. Mi manca qualcosa.

598
00:49:19,400 --> 00:49:23,100
In unione, mi rendo conto che ho bisogno di creare un nuovo array

599
00:49:23,100 --> 00:49:26,530
perché non potrei farlo al suo posto. Sì >>. Non è possibile. Correggi.

600
00:49:26,530 --> 00:49:28,170
[Studente] Così ho creato un nuovo array.

601
00:49:28,170 --> 00:49:31,510
Ho dimenticato alla fine di unione per ri-cambiare.

602
00:49:31,510 --> 00:49:34,490
Va bene. Abbiamo bisogno di un nuovo array.

603
00:49:34,490 --> 00:49:41,000
In merge sort, questo è quasi sempre vero.

604
00:49:41,000 --> 00:49:44,340
Parte del costo di un algoritmo migliore tempo-saggio

605
00:49:44,340 --> 00:49:47,310
è quasi sempre la necessità di utilizzare la memoria un po 'di più.

606
00:49:47,310 --> 00:49:51,570
Quindi, ecco, non importa come si fa merge sort,

607
00:49:51,570 --> 00:49:54,780
si sarebbe inevitabilmente necessario utilizzare un po 'di memoria aggiuntiva.

608
00:49:54,780 --> 00:49:58,240
Lui o lei ha creato un nuovo array.

609
00:49:58,240 --> 00:50:03,400
E poi dire alla fine abbiamo solo bisogno di copiare nuova matrice nella matrice originale.

610
00:50:03,400 --> 00:50:04,830
[Studente] Penso di sì, sì.

611
00:50:04,830 --> 00:50:08,210
Non so se funziona, in termini di conteggio di riferimento o qualsiasi altra cosa -

612
00:50:08,210 --> 00:50:11,650
Sì, funzionerà. >> [Studente] Ok.

613
00:50:20,620 --> 00:50:24,480
Hai provato l'esecuzione di questo? >> [Studente] No, non ancora. Va bene >>.

614
00:50:24,480 --> 00:50:28,880
Provare a eseguire, e poi ne parlerò per un secondo.

615
00:50:28,880 --> 00:50:35,200
[Studente] Ho bisogno di avere tutti i prototipi di funzione e tutto il resto, pero ', vero?

616
00:50:37,640 --> 00:50:40,840
I prototipi di funzione. Oh, vuoi dire come - Sì.

617
00:50:40,840 --> 00:50:43,040
Ordina chiama mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Quindi, al fine di ordinamento chiamare mergeSortHelp, mergeSortHelp deve essere stata definita

619
00:50:47,390 --> 00:50:56,370
prima di ordinare o ci serve solo il prototipo. Basta copiare e incollare questo.

620
00:50:56,370 --> 00:50:59,490
E allo stesso modo, mergeSortHelp chiama unione,

621
00:50:59,490 --> 00:51:03,830
ma unione non è stata ancora definita, in modo che possiamo lasciare che mergeSortHelp sapere

622
00:51:03,830 --> 00:51:08,700
che questo è ciò che si fondono è andare a guardare come, e questo è tutto.

623
00:51:09,950 --> 00:51:15,730
Così mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Abbiamo un problema qui dove non abbiamo alcun caso base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp è ricorsiva, in modo che qualsiasi funzione ricorsiva

626
00:51:38,110 --> 00:51:42,610
avrà bisogno di un qualche tipo di scenario di base per sapere quando smettere di chiamare sé stesso ricorsivamente.

627
00:51:42,610 --> 00:51:45,590
Qual è il nostro scenario di base sarà qui? Gia '.

628
00:51:45,590 --> 00:51:49,110
[Studente] Se la dimensione è di 1? >> [Bowden] Sì.

629
00:51:49,110 --> 00:51:56,220
Così come abbiamo visto proprio lì, ci siamo fermati array scissione

630
00:51:56,220 --> 00:52:01,850
una volta arrivati ​​in un array di dimensione 1, che inevitabilmente sono a loro volta ordinati.

631
00:52:01,850 --> 00:52:09,530
Quindi, se la dimensione è uguale a 1, sappiamo che l'array è già ordinato,

632
00:52:09,530 --> 00:52:12,970
in modo che possiamo semplicemente restituire.

633
00:52:12,970 --> 00:52:16,880
>> Si noti che è vuoto, in modo da non restituiscono niente di particolare, abbiamo appena ritorno.

634
00:52:16,880 --> 00:52:19,580
Va bene. Ecco, questo è il nostro caso base.

635
00:52:19,580 --> 00:52:27,440
Credo che il nostro scenario di base potrebbe essere anche se ci capita di essere la fusione un array di dimensione 0,

636
00:52:27,440 --> 00:52:30,030
probabilmente vuole fermare a un certo punto,

637
00:52:30,030 --> 00:52:33,610
quindi possiamo dire dimensione inferiore a 2 o inferiore o uguale a 1

638
00:52:33,610 --> 00:52:37,150
in modo che questo funziona per qualsiasi matrice ora.

639
00:52:37,150 --> 00:52:38,870
Va bene.

640
00:52:38,870 --> 00:52:42,740
Ecco, questo è il nostro caso base.

641
00:52:42,740 --> 00:52:45,950
Ora vuoi camminare noi attraverso unione?

642
00:52:45,950 --> 00:52:49,140
Che cosa significano tutti questi casi?

643
00:52:49,140 --> 00:52:54,480
Quassù, stiamo solo facendo la stessa idea, la -

644
00:52:56,970 --> 00:53:02,470
[Studente] Ho bisogno di essere di passaggio dimensioni, con tutte le chiamate mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Ho aggiunto dimensioni come primario aggiuntivo e non è lì, come dimensioni / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, taglia / 2, superficie / 2. >> [Studente] Sì, e anche nella funzione di cui sopra pure.

647
00:53:16,210 --> 00:53:21,320
[Bowden] qui? >> [Studente] Proprio dimensioni. >> [Bowden] Oh. Taglia, taglia? >> [Studente] Si '.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Ok.

649
00:53:23,010 --> 00:53:26,580
Fammi pensare per un secondo.

650
00:53:26,580 --> 00:53:28,780
Non ci si imbatte in un problema?

651
00:53:28,780 --> 00:53:33,690
Siamo sempre trattare il sinistro come 0. >> [Studente] No.

652
00:53:33,690 --> 00:53:36,340
Questo è sbagliato troppo. Scusi. Dovrebbe essere inizio. Gia '.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Ok. Mi piace che meglio.

654
00:53:39,230 --> 00:53:43,880
E fine. Va bene.

655
00:53:43,880 --> 00:53:47,200
Quindi ora vuoi camminare noi attraverso unione? >> [Studente] Ok.

656
00:53:47,200 --> 00:53:52,150
Sto solo a piedi attraverso questa nuova matrice che ho creato.

657
00:53:52,150 --> 00:53:57,420
La sua dimensione è la dimensione della porzione di matrice che vogliamo essere ordinati

658
00:53:57,420 --> 00:54:03,460
e cercando di trovare l'elemento che dovrei mettere nel passaggio nuovo array.

659
00:54:03,460 --> 00:54:10,140
Quindi, per fare questo, in primo luogo sto controllando se la metà sinistra della matrice continua ad avere elementi più,

660
00:54:10,140 --> 00:54:14,260
e se non lo fa, allora si scende a condizione che gli altri, che dice basta

661
00:54:14,260 --> 00:54:20,180
va bene, deve essere nel campo di destra, e metteremo che nell'indice corrente di newArray.

662
00:54:20,180 --> 00:54:27,620
>> E poi altrimenti, sto controllando se il lato destro della matrice è terminata,

663
00:54:27,620 --> 00:54:30,630
nel qual caso ho appena messo nella sinistra.

664
00:54:30,630 --> 00:54:34,180
Questo non potrebbe in realtà essere necessario. Non ne sono sicuro.

665
00:54:34,180 --> 00:54:40,970
Ma in ogni caso, gli altri due verifica quale delle due sono più piccoli in sinistra o destra.

666
00:54:40,970 --> 00:54:49,770
E anche in ogni caso, sto incrementando qualsiasi segnaposto che incrementare.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Ok.

668
00:54:52,040 --> 00:54:53,840
Questo sembra buono.

669
00:54:53,840 --> 00:54:58,800
Qualcuno ha commenti o dubbi o domande?

670
00:55:00,660 --> 00:55:07,720
Così i quattro casi che dobbiamo portare le cose in solo di essere - o sembra che cinque -

671
00:55:07,720 --> 00:55:13,100
ma dobbiamo considerare se la matrice di sinistra è a corto di cose che dobbiamo unire,

672
00:55:13,100 --> 00:55:16,390
se il campo di destra è a corto di cose che dobbiamo unire -

673
00:55:16,390 --> 00:55:18,400
Io sto puntando a nulla.

674
00:55:18,400 --> 00:55:21,730
Quindi, se la matrice di sinistra è a corto di cose o di campo di destra è a corto di cose.

675
00:55:21,730 --> 00:55:24,320
Questi sono due casi.

676
00:55:24,320 --> 00:55:30,920
Abbiamo anche bisogno il caso banale di se la cosa a sinistra è minore la cosa giusta.

677
00:55:30,920 --> 00:55:33,910
Poi vogliamo scegliere la cosa di sinistra.

678
00:55:33,910 --> 00:55:37,630
Questi sono i casi.

679
00:55:37,630 --> 00:55:40,990
Quindi questo era giusto, in modo che è così.

680
00:55:40,990 --> 00:55:46,760
Matrice sinistra. È 1, 2, 3. Va bene. Quindi sì, queste sono le quattro cose che potremmo voler fare.

681
00:55:50,350 --> 00:55:54,510
E non andrà oltre una soluzione iterativa.

682
00:55:54,510 --> 00:55:55,980
Non lo consiglio -

683
00:55:55,980 --> 00:56:03,070
Merge sort è un esempio di una funzione che è sia non tail ricorsiva,

684
00:56:03,070 --> 00:56:07,040
non è facile fare la coda ricorsiva,

685
00:56:07,040 --> 00:56:13,450
ma non è molto facile da fare è iterativo.

686
00:56:13,450 --> 00:56:16,910
Questo è molto facile.

687
00:56:16,910 --> 00:56:19,170
Questa implementazione di merge sort,

688
00:56:19,170 --> 00:56:22,140
unire, non importa quello che fai, che stai andando a costruire unione.

689
00:56:22,140 --> 00:56:29,170
>> Così merge sort costruito sulla cima di unione è ricorsivamente solo queste tre righe.

690
00:56:29,170 --> 00:56:34,700
Iterativo, è più fastidioso e più difficile da pensare.

691
00:56:34,700 --> 00:56:41,860
Ma si noti che non è la coda ricorsiva dal mergeSortHelp - quando si chiama -

692
00:56:41,860 --> 00:56:46,590
ha ancora bisogno di fare le cose dopo questo ritorno della chiamata ricorsiva.

693
00:56:46,590 --> 00:56:50,830
Quindi questo stack frame deve continuare ad esistere anche dopo la chiamata a questo.

694
00:56:50,830 --> 00:56:54,170
E poi quando si chiama questo, lo stack frame deve continuare ad esistere

695
00:56:54,170 --> 00:56:57,780
perché anche dopo la chiamata, abbiamo ancora bisogno di unire.

696
00:56:57,780 --> 00:57:01,920
Ed è banale per rendere questa coda ricorsiva.

697
00:57:04,070 --> 00:57:06,270
Domande?

698
00:57:08,300 --> 00:57:09,860
Bene.

699
00:57:09,860 --> 00:57:13,400
Quindi, tornando a ordinare - oh, ci sono due cose che voglio mostrare. Va bene.

700
00:57:13,400 --> 00:57:17,840
Tornando al tipo, faremo in fretta.

701
00:57:17,840 --> 00:57:21,030
Oppure cerca. In ordine? Ordina. Gia '.

702
00:57:21,030 --> 00:57:22,730
Tornando agli inizi del genere.

703
00:57:22,730 --> 00:57:29,870
Vogliamo creare un algoritmo che ordina l'array usando un algoritmo

704
00:57:29,870 --> 00:57:33,660
in O di n.

705
00:57:33,660 --> 00:57:40,860
Così come è possibile? Qualcuno ha qualche tipo di -

706
00:57:40,860 --> 00:57:44,300
Ho accennato prima al -

707
00:57:44,300 --> 00:57:48,300
Se stiamo per migliorare, passando da n log n a O di n,

708
00:57:48,300 --> 00:57:51,450
abbiamo migliorato il nostro algoritmo di time-saggio,

709
00:57:51,450 --> 00:57:55,250
il che significa che ciò che abbiamo intenzione di bisogno di fare per compensare questo?

710
00:57:55,250 --> 00:57:59,520
[Studente] Spazio. Sì >>. Abbiamo intenzione di utilizzare più spazio.

711
00:57:59,520 --> 00:58:04,490
E non anche solo più spazio, è lo spazio esponenzialmente più.

712
00:58:04,490 --> 00:58:14,320
Quindi penso che questo tipo di algoritmo è qualcosa di pseudo, polinomio pseudo -

713
00:58:14,320 --> 00:58:18,980
pseudo - non ricordo. Pseudo qualcosa.

714
00:58:18,980 --> 00:58:22,210
Ma è perché abbiamo bisogno di usare tanto spazio

715
00:58:22,210 --> 00:58:28,610
che questo è possibile, ma non è realistico.

716
00:58:28,610 --> 00:58:31,220
>> E come si fa a raggiungere questo obiettivo?

717
00:58:31,220 --> 00:58:36,810
Siamo in grado di farlo, nel caso vi possiamo garantire che un particolare elemento della matrice

718
00:58:36,810 --> 00:58:39,600
è al di sotto di una certa dimensione.

719
00:58:42,070 --> 00:58:44,500
Quindi, diciamo solo che la dimensione è di 200,

720
00:58:44,500 --> 00:58:48,130
qualsiasi elemento di un array è inferiore a grandezza 200.

721
00:58:48,130 --> 00:58:51,080
E questo è in realtà molto realistico.

722
00:58:51,080 --> 00:58:58,660
Si può facilmente avere una matrice che tu sai tutto in esso

723
00:58:58,660 --> 00:59:00,570
sarà inferiore a un certo numero.

724
00:59:00,570 --> 00:59:07,400
Come se avete qualche vettore assolutamente enormi o qualcosa del genere

725
00:59:07,400 --> 00:59:11,810
ma tu sai tutto quello che sta per essere tra 0 e 5,

726
00:59:11,810 --> 00:59:14,790
allora sarà significativamente più veloce per fare questo.

727
00:59:14,790 --> 00:59:17,930
E il limite su qualsiasi degli elementi è 5,

728
00:59:17,930 --> 00:59:21,980
così questo limite, che è la quantità di memoria che si vuole utilizzare.

729
00:59:21,980 --> 00:59:26,300
Quindi, il limite è 200.

730
00:59:26,300 --> 00:59:32,960
In teoria c'è sempre un limite dal momento che un numero intero può essere fino a 4 miliardi di euro,

731
00:59:32,960 --> 00:59:40,600
ma questo è realistica in quanto si verrebbe così ad utilizzare lo spazio

732
00:59:40,600 --> 00:59:44,400
dell'ordine di 4 miliardi. Ecco, questo è irrealistico.

733
00:59:44,400 --> 00:59:47,060
Ma qui diremo la nostra associazione è di 200.

734
00:59:47,060 --> 00:59:59,570
Il trucco per farlo in O di n è che facciamo un altro array chiamato conta di dimensioni BOUND.

735
00:59:59,570 --> 01:00:10,470
Quindi, in realtà, questa è una scorciatoia per - Io in realtà non so se Clang fa questo.

736
01:00:11,150 --> 01:00:15,330
Ma nel GCC almeno - Sto Clang ammesso che fa anche -

737
01:00:15,330 --> 01:00:18,180
questo sarà solo inizializzare l'intero array di essere 0s.

738
01:00:18,180 --> 01:00:25,320
Quindi, se io non voglio farlo, quindi ho potuto fare a parte for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND, i + +) e conta [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Così ora tutto è inizializzato a 0.

741
01:00:35,260 --> 01:00:39,570
Ho iterazioni su mia matrice,

742
01:00:39,570 --> 01:00:51,920
e quello che sto facendo è che sto contando il numero di ciascun - Andiamo qui.

743
01:00:51,920 --> 01:00:55,480
Abbiamo 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Quello che sto contando il numero di occorrenze di ciascuna di tali elementi.

745
01:01:00,010 --> 01:01:03,470
Facciamo in realtà aggiungere un paio più in là con alcune ripetizioni.

746
01:01:03,470 --> 01:01:11,070
Quindi il valore che abbiamo qui, il valore di tale sarà array [i].

747
01:01:11,070 --> 01:01:14,850
Quindi val potrebbero essere 4 o 8 o qualsiasi altra cosa.

748
01:01:14,850 --> 01:01:18,870
E ora sto contando quanti di quel valore che ho visto,

749
01:01:18,870 --> 01:01:21,230
quindi conta [val] + +;

750
01:01:21,230 --> 01:01:29,430
Dopo aver fatto questo, conta è andare a guardare qualcosa come 0001.

751
01:01:29,430 --> 01:01:42,190
Facciamo conta [val] - VINCOLATO + 1.

752
01:01:42,190 --> 01:01:48,230
>> Ora che è solo per tenere conto del fatto che stiamo a partire da 0.

753
01:01:48,230 --> 01:01:50,850
Quindi, se 200 è sarà il nostro più grande numero,

754
01:01:50,850 --> 01:01:54,720
quindi 0 per 200 è 201 cose.

755
01:01:54,720 --> 01:02:01,540
Quindi conta, sarà simile a 00.001, dato che disponiamo 4.

756
01:02:01,540 --> 01:02:10,210
Poi avremo 0001 dove avremo un 1 nell'indice 8 conteggio.

757
01:02:10,210 --> 01:02:14,560
Avremo un 2 nell'indice 23 count.

758
01:02:14,560 --> 01:02:17,630
Avremo un 2 nell'indice 42 ° numero.

759
01:02:17,630 --> 01:02:21,670
Così possiamo usare count.

760
01:02:34,270 --> 01:02:44,920
Così num_of_item = conta [i].

761
01:02:44,920 --> 01:02:52,540
E quindi se num_of_item è 2, che significa che vogliamo inserire i 2 del numero

762
01:02:52,540 --> 01:02:55,290
nel nostro array ordinato.

763
01:02:55,290 --> 01:03:02,000
Quindi abbiamo bisogno di tenere traccia di quanto siamo lontani nella matrice.

764
01:03:02,000 --> 01:03:05,470
Così index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - mi limiterò a scrivere.

766
01:03:16,660 --> 01:03:18,020
Conti -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
E 'questo quello che voglio? Penso che sia quello che voglio.

769
01:03:35,100 --> 01:03:38,290
Sì, questo sembra buono. Va bene.

770
01:03:38,290 --> 01:03:43,050
Così fa capire a tutti quale sia lo scopo della mia matrice conta è?

771
01:03:43,050 --> 01:03:48,140
Si conta il numero di occorrenze di ciascuno di questi numeri.

772
01:03:48,140 --> 01:03:51,780
Poi io sono l'iterazione di tale matrice conta,

773
01:03:51,780 --> 01:03:57,190
e la posizione esima dell'array conta

774
01:03:57,190 --> 01:04:01,930
è il numero di i è che dovrebbe apparire nel mio array ordinato.

775
01:04:01,930 --> 01:04:06,840
È per questo che conta di 4 sta per essere 1

776
01:04:06,840 --> 01:04:11,840
e conta di 8 sta per essere 1, conta di 23 sta per essere 2.

777
01:04:11,840 --> 01:04:16,900
È così che molti di loro voglio inserire nel mio array ordinato.

778
01:04:16,900 --> 01:04:19,200
Poi ho solo farlo.

779
01:04:19,200 --> 01:04:28,960
Sto inserendo num_of_item mi e 'nel mio array ordinato.

780
01:04:28,960 --> 01:04:31,670
>> Domande?

781
01:04:32,460 --> 01:04:43,100
E così ancora una volta, questo è il tempo lineare, dal momento che sono solo l'iterazione di una volta,

782
01:04:43,100 --> 01:04:47,470
ma è anche lineare in quanto questo numero sembra essere,

783
01:04:47,470 --> 01:04:50,730
e quindi dipende in larga misura ciò che la vostra associazione è.

784
01:04:50,730 --> 01:04:53,290
Con un balzo di 200, che non è poi così male.

785
01:04:53,290 --> 01:04:58,330
Se la vostra associazione sta per essere 10.000, allora questo è un po 'peggio,

786
01:04:58,330 --> 01:05:01,360
ma se la vostra associazione sta per essere 4 miliardi di euro, che è completamente irrealistico

787
01:05:01,360 --> 01:05:07,720
e questo array sta andando ad avere per essere di dimensione 4 miliardi di euro, che non è realistico.

788
01:05:07,720 --> 01:05:10,860
Quindi, questo è tutto. Domande?

789
01:05:10,860 --> 01:05:13,270
[Risposta degli studenti incomprensibile] >> Ok.

790
01:05:13,270 --> 01:05:15,710
Ho capito un'altra cosa, quando stavamo attraversando.

791
01:05:17,980 --> 01:05:23,720
Penso che il problema era in Lucas e probabilmente ognuno che abbiamo visto.

792
01:05:23,720 --> 01:05:26,330
Ho completamente dimenticato.

793
01:05:26,330 --> 01:05:31,040
L'unica cosa che volevo commentare è che quando hai a che fare con cose come gli indici,

794
01:05:31,040 --> 01:05:38,320
non si è mai davvero vedere questo quando si scrive un ciclo for,

795
01:05:38,320 --> 01:05:41,120
ma tecnicamente, ogni volta che hai a che fare con questi indici,

796
01:05:41,120 --> 01:05:45,950
si dovrebbe quasi sempre a che fare con i numeri interi senza segno.

797
01:05:45,950 --> 01:05:53,850
La ragione di questo è quando hai a che fare con i numeri interi con segno,

798
01:05:53,850 --> 01:05:56,090
quindi se si dispone di 2 interi con segno e li sommano

799
01:05:56,090 --> 01:06:00,640
e finiscono troppo grande, allora si finisce con un numero negativo.

800
01:06:00,640 --> 01:06:03,410
Ecco, questo è quello che è integer overflow.

801
01:06:03,410 --> 01:06:10,500
>> Se posso aggiungere 2 miliardi e 1 miliardo, io alla fine con negativo 1 miliardo.

802
01:06:10,500 --> 01:06:15,480
Ecco come numeri interi funziona su computer.

803
01:06:15,480 --> 01:06:17,510
Quindi il problema con l'utilizzo -

804
01:06:17,510 --> 01:06:23,500
Questo è bene, tranne se basso sembra essere 2 miliardi e capita fino a 1 miliardo,

805
01:06:23,500 --> 01:06:27,120
allora questo sarà negativo 1 miliardo e poi andremo a dividere che per 2

806
01:06:27,120 --> 01:06:29,730
e finire con negativo 500 milioni.

807
01:06:29,730 --> 01:06:33,760
Quindi, questo è solo un problema se vi capita di essere alla ricerca attraverso un array

808
01:06:33,760 --> 01:06:38,070
di miliardi di cose.

809
01:06:38,070 --> 01:06:44,050
Ma se succede + basso fino a traboccare, allora questo è un problema.

810
01:06:44,050 --> 01:06:47,750
Non appena li facciamo senza segno, quindi 2 miliardi di dollari più 1 miliardo 3 miliardi.

811
01:06:47,750 --> 01:06:51,960
3000000000 diviso 2 è di 1,5 miliardi di euro.

812
01:06:51,960 --> 01:06:55,670
Così, non appena sono unsigned, tutto è perfetto.

813
01:06:55,670 --> 01:06:59,900
E così che è anche un problema quando si scrive un ciclo FOR,

814
01:06:59,900 --> 01:07:03,940
e in realtà, probabilmente lo fa automaticamente.

815
01:07:09,130 --> 01:07:12,330
Essa in realtà solo urlare contro di voi.

816
01:07:12,330 --> 01:07:21,610
Quindi, se questo numero è troppo grande per essere solo in un numero intero, ma si adatterebbe in un intero senza segno,

817
01:07:21,610 --> 01:07:24,970
sarà urlare contro di voi, è per questo che non hai mai veramente incontrato il problema.

818
01:07:29,150 --> 01:07:34,820
Si può vedere che un indice non sta per essere negativo,

819
01:07:34,820 --> 01:07:39,220
e così quando si è l'iterazione di un array,

820
01:07:39,220 --> 01:07:43,970
si può quasi sempre dire unsigned int i, ma non si ha realmente bisogno.

821
01:07:43,970 --> 01:07:47,110
Le cose stanno andando a lavorare più o meno altrettanto bene.

822
01:07:48,740 --> 01:07:50,090
Va bene. [Sussurra] Che ora è?

823
01:07:50,090 --> 01:07:54,020
L'ultima cosa che volevo mostrare - e mi limiterò a farlo davvero veloce.

824
01:07:54,020 --> 01:08:03,190
Tu sai come abbiamo # define in modo che possiamo # define MAX come 5 o qualcosa del genere?

825
01:08:03,190 --> 01:08:05,940
Cerchiamo di non fare MAX. # Define BOUND come 200. Questo è quello che abbiamo fatto prima.

826
01:08:05,940 --> 01:08:10,380
Questo definisce una costante, che è solo andare a essere copiato e incollato

827
01:08:10,380 --> 01:08:13,010
ovunque ci capita di scrivere BOUND.

828
01:08:13,010 --> 01:08:18,189
>> Così possiamo davvero fare di più con # define.

829
01:08:18,189 --> 01:08:21,170
Siamo in grado di definire le funzioni #.

830
01:08:21,170 --> 01:08:23,410
Non sono in realtà funzioni, ma che chiameremo funzioni.

831
01:08:23,410 --> 01:08:36,000
Un esempio potrebbe essere qualcosa di simile a MAX (x, y) è definito come (x <y y: x). Va bene.

832
01:08:36,000 --> 01:08:40,660
Così si dovrebbe abituarsi alla sintassi operatore ternario,

833
01:08:40,660 --> 01:08:49,029
ma è inferiore a x y? Ritorno y, else return x.

834
01:08:49,029 --> 01:08:54,390
Così si può vedere è possibile rendere questo una funzione separata,

835
01:08:54,390 --> 01:09:01,399
e la funzione potrebbe essere come bool MAX prende 2 argomenti, restituire questo.

836
01:09:01,399 --> 01:09:08,340
Questo è uno di quelli più comuni che vedo fatto così. Noi li chiamiamo macro.

837
01:09:08,340 --> 01:09:11,790
Si tratta di una macro.

838
01:09:11,790 --> 01:09:15,859
Questo è solo la sintassi per questo.

839
01:09:15,859 --> 01:09:18,740
È possibile scrivere una macro per fare quello che vuoi.

840
01:09:18,740 --> 01:09:22,649
È frequente vedere Macro per il debug printfs e roba del genere.

841
01:09:22,649 --> 01:09:29,410
Quindi un tipo di printf, ci sono costanti speciali in C, come sottolineano LINE sottolineatura,

842
01:09:29,410 --> 01:09:31,710
2 sottolinea LINE sottolineatura,

843
01:09:31,710 --> 01:09:37,550
e c'è anche penso due sottolineatura FUNC. Questo potrebbe essere. Qualcosa del genere.

844
01:09:37,550 --> 01:09:40,880
Quelle cose verrà sostituito con il nome della funzione

845
01:09:40,880 --> 01:09:42,930
o il numero della riga che si è in.

846
01:09:42,930 --> 01:09:48,630
Spesso si scrive printfs debug che qui avrei potuto poi basta scrivere

847
01:09:48,630 --> 01:09:54,260
DEBUG e sarà il numero della linea e la funzione che mi capita di essere in

848
01:09:54,260 --> 01:09:57,020
che ha rilevato che la dichiarazione DEBUG.

849
01:09:57,020 --> 01:09:59,550
E si può anche stampare altre cose.

850
01:09:59,550 --> 01:10:05,990
Quindi, una cosa che si dovrebbe guardare fuori per è che se mi capita di definire # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
come qualcosa come 2 * y e 2 * x.

852
01:10:11,380 --> 01:10:14,310
Quindi, per qualsiasi motivo, vi capita di fare un sacco.

853
01:10:14,310 --> 01:10:16,650
Così ne fanno un macro.

854
01:10:16,650 --> 01:10:18,680
Questo è effettivamente rotto.

855
01:10:18,680 --> 01:10:23,050
Io lo definirei facendo qualcosa di simile DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Che cosa si deve essere restituito?

857
01:10:28,840 --> 01:10:30,580
[Studente] 12.

858
01:10:30,580 --> 01:10:34,800
Sì, 12 deve essere restituito, e 12 viene restituito.

859
01:10:34,800 --> 01:10:43,350
3 viene sostituito per x, 6 viene sostituito per y, e ci restituisce 2 * 6, che è 12.

860
01:10:43,350 --> 01:10:47,710
Ora, che dire di questo? Quali devono essere restituite?

861
01:10:47,710 --> 01:10:50,330
[Studente] 14. >> Idealmente, 14.

862
01:10:50,330 --> 01:10:55,290
Il problema è che come hash definisce il lavoro, ricordatevi che è una copia letterale e incolla

863
01:10:55,290 --> 01:11:00,160
di praticamente tutto, quindi ciò che questo sta per essere interpretato nel senso che

864
01:11:00,160 --> 01:11:11,270
è 3 meno di 1 + 6, 2 volte 1 più 6, 2 volte 3.

865
01:11:11,270 --> 01:11:19,780
>> Quindi, per questo motivo è quasi sempre avvolgere tutto tra parentesi.

866
01:11:22,180 --> 01:11:25,050
Ogni variabile è quasi sempre avvolgere tra parentesi.

867
01:11:25,050 --> 01:11:29,570
Ci sono casi in cui non si devono, come so che non ho bisogno di farlo qui

868
01:11:29,570 --> 01:11:32,110
perché meno è praticamente sempre e solo andare a lavorare,

869
01:11:32,110 --> 01:11:34,330
anche se questo potrebbe anche non essere vero.

870
01:11:34,330 --> 01:11:41,870
Se c'è qualcosa di ridicolo come DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
allora che si fara 'sostituito con 3 è uguale a meno di 1 è uguale a 2,

872
01:11:49,760 --> 01:11:53,460
e così poi è andare a fare 3 minore di 1, vuol uguale a 2,

873
01:11:53,460 --> 01:11:55,620
che non è quello che vogliamo.

874
01:11:55,620 --> 01:12:00,730
Quindi, al fine di prevenire eventuali problemi di precedenza degli operatori,

875
01:12:00,730 --> 01:12:02,870
avvolgere sempre tra parentesi.

876
01:12:03,290 --> 01:12:07,700
Va bene. E questo è tutto, 5:30.

877
01:12:08,140 --> 01:12:12,470
Se avete domande sul pset, fatecelo sapere.

878
01:12:12,470 --> 01:12:18,010
Dovrebbe essere divertente, e l'edizione hacker è anche molto più realistico

879
01:12:18,010 --> 01:12:22,980
rispetto all'edizione hacker lo scorso anno, quindi speriamo che molti di voi provare.

880
01:12:22,980 --> 01:12:26,460
L'anno scorso è stato molto travolgente.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]