1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Section 3 - Plus confortable]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Université de Harvard]

3
00:00:05,070 --> 00:00:07,310
>> [C'est CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Donc la première question est étrangement rédigée.

5
00:00:12,700 --> 00:00:17,480
GDB vous permet de "debug" un programme, mais, plus précisément, qu'est-ce qu'il te laisser faire?

6
00:00:17,480 --> 00:00:22,590
Je vais répondre à cette question, et je ne sais pas ce que c'est exactement prévu,

7
00:00:22,590 --> 00:00:27,910
donc je pense que c'est quelque chose le long des lignes de celui-ci vous permet, étape par étape

8
00:00:27,910 --> 00:00:31,540
marcher à travers le programme, d'interagir avec lui, les variables de changement, faire toutes ces choses -

9
00:00:31,540 --> 00:00:34,270
essentiellement complètement contrôler l'exécution d'un programme

10
00:00:34,270 --> 00:00:38,410
et inspecter n'importe quelle partie de l'exécution du programme.

11
00:00:38,410 --> 00:00:43,030
Donc, ces fonctionnalités vous permettent de déboguer les choses.

12
00:00:43,030 --> 00:00:44,830
D'accord.

13
00:00:44,830 --> 00:00:50,520
Pourquoi est-ce binaire de recherche exigent que toute une série de trier?

14
00:00:50,520 --> 00:00:53,360
Qui veut répondre à cela?

15
00:00:56,120 --> 00:01:00,070
[L'élève] Parce que ça ne fonctionne pas si elle n'est pas triée. Ouais >>. [Rires]

16
00:01:00,070 --> 00:01:04,910
Si ce n'est pas triée, alors il est impossible de le couper en deux

17
00:01:04,910 --> 00:01:07,850
et je sais que tout ce qui précède est de moins en tout à droite

18
00:01:07,850 --> 00:01:10,490
est supérieure à la valeur moyenne.

19
00:01:10,490 --> 00:01:12,790
Donc, il doit être triée.

20
00:01:12,790 --> 00:01:14,170
D'accord.

21
00:01:14,170 --> 00:01:17,570
Pourquoi est-tri à bulles en O du carré n?

22
00:01:17,570 --> 00:01:23,230
Quelqu'un veux d'abord donner un très rapide aperçu de haut niveau de ce tri à bulles est?

23
00:01:25,950 --> 00:01:33,020
[L'élève] En gros, vous passez par chaque élément et vous vérifiez les éléments des premières années.

24
00:01:33,020 --> 00:01:37,150
Si ils sont hors de l'endroit où vous les permuter, puis vous vérifiez les éléments à venir et ainsi de suite.

25
00:01:37,150 --> 00:01:40,770
Lorsque vous arrivez à la fin, alors vous savez que le plus grand élément est placé à la fin,

26
00:01:40,770 --> 00:01:42,750
si vous ignorez celui-là alors vous continuez à travers,

27
00:01:42,750 --> 00:01:48,490
et chaque fois que vous devez cocher une case moins élément jusqu'à ce que vous n'apportez aucune modification. Ouais >>.

28
00:01:48,490 --> 00:01:58,470
C'est ce qu'on appelle tri à bulles, parce que si vous retournez le tableau sur le côté de sorte qu'il est de haut en bas, vertical,

29
00:01:58,470 --> 00:02:03,100
puis les grandes valeurs vont tomber au fond et les petites valeurs se propagera jusqu'au sommet.

30
00:02:03,100 --> 00:02:05,210
Voilà comment il a obtenu son nom.

31
00:02:05,210 --> 00:02:08,220
Et oui, vous venez de passer.

32
00:02:08,220 --> 00:02:11,190
Vous continuez à travers le réseau, l'échange de la plus grande valeur

33
00:02:11,190 --> 00:02:14,040
Pour obtenir les valeurs les plus élevées au fond.

34
00:02:14,040 --> 00:02:17,500
>> Pourquoi est-il O du carré n?

35
00:02:18,690 --> 00:02:24,620
Tout d'abord, personne ne veux pas dire pourquoi il est de O n carré?

36
00:02:24,620 --> 00:02:28,760
[L'élève] Parce que pour chaque course il va n fois.

37
00:02:28,760 --> 00:02:32,100
Vous ne pouvez être certain que vous avez pris le plus grand élément tout en bas,

38
00:02:32,100 --> 00:02:35,230
alors vous avez à répéter que, pour que de nombreux éléments. Ouais >>.

39
00:02:35,230 --> 00:02:41,800
Donc, gardez à l'esprit ce grand O signifie et quels moyens Omega grands.

40
00:02:41,800 --> 00:02:50,560
Le grand A, c'est comme la limite supérieure de la lenteur qu'il peut réellement fonctionner.

41
00:02:50,560 --> 00:02:58,990
Donc, en disant que c'est du carré O n, il n'est pas O n ou bien elle serait en mesure d'exécuter

42
00:02:58,990 --> 00:03:02,640
en temps linéaire, mais il est de O n en cubes

43
00:03:02,640 --> 00:03:06,390
parce qu'il est borné par O de n cubes.

44
00:03:06,390 --> 00:03:12,300
Si elle est bornée par O de carré n, alors il est délimitée aussi par n cubes.

45
00:03:12,300 --> 00:03:20,280
Donc, il est n au carré, et dans le pire des cas absolue ne peut pas faire mieux que carré n,

46
00:03:20,280 --> 00:03:22,830
C'est pourquoi il est de O n carré.

47
00:03:22,830 --> 00:03:31,200
Alors pour voir les mathématiques légère à la façon dont il sort pour être n au carré,

48
00:03:31,200 --> 00:03:40,530
si nous avons cinq choses dans notre liste, la première fois le nombre de swaps pourrions-nous éventuellement besoin de faire

49
00:03:40,530 --> 00:03:47,170
afin d'obtenir? Nous allons en fait juste -

50
00:03:47,170 --> 00:03:52,040
Combien de swaps que nous allons avoir à faire dans la première manche du tri à bulles à travers le réseau?

51
00:03:52,040 --> 00:03:53,540
[L'élève] n - 1. Ouais >>.

52
00:03:53,540 --> 00:03:58,340
>> S'il ya 5 éléments, nous allons avoir besoin de faire n - 1.

53
00:03:58,340 --> 00:04:01,100
Puis, le second le nombre de swaps que nous allons avoir à faire?

54
00:04:01,100 --> 00:04:03,440
[L'élève] n - 2. Ouais >>.

55
00:04:03,440 --> 00:04:11,640
Et le troisième va être n - 3, puis pour plus de commodité, je vais écrire les deux derniers

56
00:04:11,640 --> 00:04:15,270
que nous allons avoir besoin de faire 2 swaps et 1 swap.

57
00:04:15,270 --> 00:04:19,899
Je suppose que le dernier peut ou ne peut pas réellement besoin de se produire.

58
00:04:19,899 --> 00:04:22,820
Est-il un échange? Je ne sais pas.

59
00:04:22,820 --> 00:04:26,490
Donc, ce sont les montants totaux des swaps ou tout au moins les comparaisons que vous avez à faire.

60
00:04:26,490 --> 00:04:29,910
Même si vous n'avez pas de swap, vous avez encore besoin de comparer les valeurs.

61
00:04:29,910 --> 00:04:33,910
Il ya donc n - 1 comparaisons dans le premier passage dans le tableau.

62
00:04:33,910 --> 00:04:42,050
Si vous réorganisez ces choses, nous allons réellement faire six choses que tant de choses se comparent très bien,

63
00:04:42,050 --> 00:04:44,790
et puis je vais faire 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Il suffit donc de réorganiser ces sommes, nous voulons voir combien de comparaisons que nous faisons

65
00:04:49,910 --> 00:04:52,700
dans l'algorithme entier.

66
00:04:52,700 --> 00:04:56,550
Donc, si nous apportons ces gars ici-bas,

67
00:04:56,550 --> 00:05:07,470
alors nous n'en sommes qu'au résumé des comparaisons mais il y avait beaucoup.

68
00:05:07,470 --> 00:05:13,280
Mais si l'on cumule ces derniers et nous résumons ci et nous résumons ci,

69
00:05:13,280 --> 00:05:18,130
c'est toujours le même problème. Nous venons de résumer ces groupes particuliers.

70
00:05:18,130 --> 00:05:22,400
>> Alors maintenant, nous sommes sommateur 3 n de. Il ne s'agit pas seulement de 3 n.

71
00:05:22,400 --> 00:05:27,650
Il va toujours être n / 2 n de.

72
00:05:27,650 --> 00:05:29,430
Donc ici nous arrive d'avoir 6.

73
00:05:29,430 --> 00:05:34,830
Si nous avions 10 choses, alors nous pourrions faire ce regroupement pour 5 paires différentes des choses

74
00:05:34,830 --> 00:05:37,180
et finir avec n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Donc, vous allez toujours obtenir n / 2 n, et donc ce que nous allons le noter sur la n au carré / 2.

76
00:05:45,840 --> 00:05:48,890
Ainsi, même si c'est le facteur de la moitié, ce qui arrive d'entrer en

77
00:05:48,890 --> 00:05:54,190
en raison du fait que, grâce à chaque itération sur le tableau 1 on compare moins

78
00:05:54,190 --> 00:05:58,040
c'est comme ça que nous obtenons le plus 2, mais il est toujours n au carré.

79
00:05:58,040 --> 00:06:01,650
Nous ne se soucient pas le facteur constant de la moitié.

80
00:06:01,650 --> 00:06:07,760
Il ya donc beaucoup de choses importantes O comme celui-ci s'appuie sur tout type de faire ce genre de calcul,

81
00:06:07,760 --> 00:06:12,260
faire des sommes arithmétiques et des trucs série géométrique,

82
00:06:12,260 --> 00:06:17,750
mais la plupart d'entre eux dans ce cours sont assez simples.

83
00:06:17,750 --> 00:06:19,290
D'accord.

84
00:06:19,290 --> 00:06:24,430
Pourquoi le tri par insertion en Oméga de n? Qu'est-ce que omega dire?

85
00:06:24,430 --> 00:06:27,730
[Deux élèves qui parlent à la fois - inintelligibles] >> Oui.

86
00:06:27,730 --> 00:06:30,630
Omega vous pouvez penser que la borne inférieure.

87
00:06:30,630 --> 00:06:36,550
>> Donc, peu importe à quel point votre algorithme de tri par insertion est,

88
00:06:36,550 --> 00:06:41,810
quelle que soit la liste qui est transmis, il doit toujours comparer au moins les choses n

89
00:06:41,810 --> 00:06:44,620
ou il doit effectuer une itération sur les choses n.

90
00:06:44,620 --> 00:06:47,280
Pourquoi est-ce?

91
00:06:47,280 --> 00:06:51,190
[L'élève] Parce que si la liste est déjà trié, puis à travers la première itération

92
00:06:51,190 --> 00:06:54,080
vous ne pouvez garantir que l'élément premier est le moins,

93
00:06:54,080 --> 00:06:56,490
et la seconde itération, vous ne pouvez garantir les deux premiers sont

94
00:06:56,490 --> 00:07:00,010
parce que vous ne savez pas ce que le reste de la liste est triée. Ouais >>.

95
00:07:00,010 --> 00:07:08,910
Si vous passez dans une liste triée complètement, à tout le moins, vous devez passer en revue tous les éléments

96
00:07:08,910 --> 00:07:12,180
de voir que rien ne doit être déplacé.

97
00:07:12,180 --> 00:07:14,720
Ainsi, passant au-dessus de la liste et de dire oh, c'est déjà trié,

98
00:07:14,720 --> 00:07:18,240
il est impossible pour vous de savoir qu'il est trié avant d'avoir vérifié chaque élément

99
00:07:18,240 --> 00:07:20,660
de voir qu'ils sont dans l'ordre.

100
00:07:20,660 --> 00:07:25,290
Ainsi, la borne inférieure sur le tri par insertion est Omega de n.

101
00:07:25,290 --> 00:07:28,210
Ce qui est le cas le plus défavorable temps d'exécution du tri par fusion,

102
00:07:28,210 --> 00:07:31,390
pire des cas étant O grands encore?

103
00:07:31,390 --> 00:07:37,660
Donc, dans le pire des cas, comment tri par fusion de fonctionner?

104
00:07:42,170 --> 00:07:43,690
[L'élève] N log n. Ouais >>.

105
00:07:43,690 --> 00:07:49,990
Le plus rapide des algorithmes de tri généraux sont n log n. Vous ne pouvez pas faire mieux.

106
00:07:51,930 --> 00:07:55,130
>> Il ya des cas particuliers, et si nous avons le temps aujourd'hui - mais nous avons probablement ne le ferai pas -

107
00:07:55,130 --> 00:07:59,330
nous avons pu voir celui qui fait mieux que n log n.

108
00:07:59,330 --> 00:08:04,050
Mais dans le cas général, vous ne pouvez pas faire mieux que n log n.

109
00:08:04,050 --> 00:08:09,680
Et le tri par fusion se trouve être celui que vous devez savoir pour ce cours qui est n log n.

110
00:08:09,680 --> 00:08:13,260
Et donc nous allons effectivement être mise en œuvre aujourd'hui.

111
00:08:13,260 --> 00:08:18,070
Et enfin, en moins de trois phrases, comment fonctionne tri par sélection?

112
00:08:18,070 --> 00:08:20,370
Quelqu'un veut-il répondre, et je vais compter vos phrases

113
00:08:20,370 --> 00:08:22,390
parce que si vous allez sur 3 -

114
00:08:25,530 --> 00:08:28,330
Est-ce que quelqu'un se souvient de tri par sélection?

115
00:08:31,280 --> 00:08:37,809
Tri par sélection est généralement assez facile de se rappeler à partir du nom.

116
00:08:37,809 --> 00:08:45,350
Vous venez de parcourir le tableau, trouver tout ce que la plus grande valeur est la plus petite ou -

117
00:08:45,350 --> 00:08:47,290
l'ordre que vous triez po

118
00:08:47,290 --> 00:08:50,750
Donc, disons que nous sommes le tri du plus petit au plus grand.

119
00:08:50,750 --> 00:08:55,250
Vous itérer sur le tableau, à la recherche de tout ce que l'élément minimum est

120
00:08:55,250 --> 00:08:59,750
sélectionnez-le, puis il suffit d'échanger tout ce qui est en premier lieu.

121
00:08:59,750 --> 00:09:04,090
Et puis lors du deuxième passage sur le tableau, recherchez l'élément minimal de nouveau,

122
00:09:04,090 --> 00:09:07,490
sélectionnez-le, puis l'échanger avec ce qui est dans la deuxième position.

123
00:09:07,490 --> 00:09:10,650
Donc, nous sommes juste sélectionner et de choisir les valeurs minimales

124
00:09:10,650 --> 00:09:16,050
et les insérer dans la face de la matrice jusqu'à ce qu'il soit trié.

125
00:09:19,210 --> 00:09:21,560
Questions à ce sujet?

126
00:09:21,560 --> 00:09:25,710
>> Ceux-ci apparaissent inévitablement dans les formulaires que vous devez remplir lorsque vous soumettez le pset.

127
00:09:29,010 --> 00:09:32,360
Ce sont essentiellement les réponses à celles-ci.

128
00:09:32,360 --> 00:09:34,230
Bon, alors maintenant des problèmes de codage.

129
00:09:34,230 --> 00:09:40,140
J'ai déjà envoyé par e-mail - Quelqu'un at-il pas cet e-mail? D'accord.

130
00:09:40,140 --> 00:09:46,630
J'ai déjà envoyé par e-mail l'espace que nous allons utiliser,

131
00:09:46,630 --> 00:09:52,120
et si vous cliquez sur mon nom - je pense que je vais être à la base

132
00:09:52,120 --> 00:09:57,170
en raison de la r arrière - mais si vous cliquez sur mon nom, vous verrez 2 révisions.

133
00:09:57,170 --> 00:10:02,650
Révision 1 va être je l'ai déjà copié et collé le code dans les espaces

134
00:10:02,650 --> 00:10:06,900
pour la chose recherche que vous allez avoir à mettre en œuvre.

135
00:10:06,900 --> 00:10:10,540
Et Révision 2 sera la chose la sorte que nous mettons en œuvre par la suite.

136
00:10:10,540 --> 00:10:15,770
Ainsi, vous pouvez cliquer sur mon Révision 1 et à partir de là.

137
00:10:17,350 --> 00:10:22,060
Et maintenant, nous voulons mettre en œuvre binaire de recherche.

138
00:10:22,060 --> 00:10:26,470
>> Quelqu'un veut-il simplement donner un pseudo-explication de haut niveau

139
00:10:26,470 --> 00:10:31,440
de ce que nous allons avoir à faire de la recherche? Ouais.

140
00:10:31,440 --> 00:10:36,170
[L'élève] Il suffit de prendre le milieu du tableau et de voir si ce que vous cherchez

141
00:10:36,170 --> 00:10:38,650
est inférieure à celle ou plus.

142
00:10:38,650 --> 00:10:41,080
Et si elle est inférieure, vous allez à la moitié de ce fait moins,

143
00:10:41,080 --> 00:10:44,750
et si ce n'est plus, que vous alliez à la moitié, c'est plus et vous répétez jusqu'à ce que vous obtenez juste une chose.

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

145
00:10:46,570 --> 00:10:51,320
Notez que notre tableau numbers est déjà trié,

146
00:10:51,320 --> 00:10:57,190
et si cela signifie que nous pouvons tirer profit de cela et nous avons pu vérifier d'abord,

147
00:10:57,190 --> 00:11:00,390
ok, je suis à la recherche pour le nombre 50.

148
00:11:00,390 --> 00:11:03,720
Donc, je peux aller dans le centre.

149
00:11:03,720 --> 00:11:07,380
Orient est difficile de définir le moment où il s'agit d'un nombre pair de choses,

150
00:11:07,380 --> 00:11:10,820
mais disons simplement que nous serons toujours tronquer au milieu.

151
00:11:10,820 --> 00:11:14,420
Nous avons donc ici 8 choses, de sorte que le milieu serait de 16.

152
00:11:14,420 --> 00:11:17,330
Je suis à la recherche de 50, donc 50 est supérieur à 16.

153
00:11:17,330 --> 00:11:21,310
Alors maintenant, je peux traiter mon gros tableau comme ces éléments.

154
00:11:21,310 --> 00:11:23,450
Je peux jeter tout de 16 cours.

155
00:11:23,450 --> 00:11:27,440
Maintenant, mon tableau est juste ces 4 éléments, et je le répète.

156
00:11:27,440 --> 00:11:31,910
Alors je veux trouver au milieu nouveau, ce qui va être 42.

157
00:11:31,910 --> 00:11:34,730
42 est inférieur à 50, afin que je puisse jeter ces deux éléments.

158
00:11:34,730 --> 00:11:36,890
C'est mon tableau restante.

159
00:11:36,890 --> 00:11:38,430
Je vais trouver le milieu nouveau.

160
00:11:38,430 --> 00:11:42,100
Je suppose que 50 est un mauvais exemple parce que j'étais toujours jeter des choses à gauche,

161
00:11:42,100 --> 00:11:48,280
mais par la même mesure, si je suis à la recherche de quelque chose

162
00:11:48,280 --> 00:11:52,100
et c'est au moins la partie que je suis en train de regarder,

163
00:11:52,100 --> 00:11:55,080
alors je vais jeter tout à droite.

164
00:11:55,080 --> 00:11:58,150
Alors maintenant, nous devons mettre en oeuvre.

165
00:11:58,150 --> 00:12:02,310
Notez que nous avons besoin de passer à la taille.

166
00:12:02,310 --> 00:12:06,730
Nous ne pouvons pas non plus besoin de coder en dur la taille.

167
00:12:06,730 --> 00:12:11,640
Donc, si nous nous débarrassons de ce # define -

168
00:12:19,630 --> 00:12:21,430
D'accord.

169
00:12:21,430 --> 00:12:27,180
Comment puis-je bien comprendre ce que la taille du tableau numbers est actuellement?

170
00:12:27,180 --> 00:12:30,950
>> Combien d'éléments sont dans le tableau numbers?

171
00:12:30,950 --> 00:12:33,630
[Étudiants] Numéros, supports,. Longueur?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Cela n'existe pas en C.

173
00:12:36,600 --> 00:12:38,580
Besoin d'. Longueur.

174
00:12:38,580 --> 00:12:42,010
Les tableaux n'ont pas de propriétés, il n'est donc pas propriété de longueur de tableaux

175
00:12:42,010 --> 00:12:45,650
qui vous donnera juste le temps qu'il se trouve.

176
00:12:48,180 --> 00:12:51,620
[L'élève] Voir la quantité de mémoire dont il dispose et diviser par la quantité - >> Oui.

177
00:12:51,620 --> 00:12:55,810
Alors, comment pouvons-nous voir combien de mémoire il a? >> [L'élève] Sizeof. >> Ouais, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof est l'opérateur qui va retourner la taille de la matrice de nombres.

179
00:13:01,680 --> 00:13:10,060
Et ça va être des nombres entiers mais il ya beaucoup de fois la taille d'un entier

180
00:13:10,060 --> 00:13:14,050
puisque c'est combien de mémoire il s'agit en fait de prendre place.

181
00:13:14,050 --> 00:13:17,630
Donc, si je veux que le nombre de choses dans le tableau,

182
00:13:17,630 --> 00:13:20,560
alors je vais vouloir diviser par la taille d'un entier.

183
00:13:22,820 --> 00:13:26,010
D'accord. Alors qui me permet de passer en taille ici.

184
00:13:26,010 --> 00:13:29,430
Pourquoi ai-je besoin de passer à la taille du tout?

185
00:13:29,430 --> 00:13:38,570
Pourquoi ne puis-je pas simplement faire ici int size = sizeof (botte de foin) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Pourquoi ça ne marche pas?

187
00:13:41,490 --> 00:13:44,470
[L'élève] Ce n'est pas une variable globale.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existe et nous passons en nombre comme botte de foin,

189
00:13:51,540 --> 00:13:54,700
et cela est une sorte de préfiguration de ce qui est à venir. Ouais.

190
00:13:54,700 --> 00:14:00,170
[L'élève] Haystack est juste la référence à lui, donc il serait de retour la taille de cette référence est.

191
00:14:00,170 --> 00:14:02,150
Ouais.

192
00:14:02,150 --> 00:14:09,000
Je doute que dans la conférence que vous avez vu la pile encore vraiment, non?

193
00:14:09,000 --> 00:14:11,270
Nous venons tout juste parlé.

194
00:14:11,270 --> 00:14:16,090
Ainsi, la pile est l'endroit où toutes les variables vont être stockées.

195
00:14:16,090 --> 00:14:19,960
>> Toute mémoire qui est allouée pour les variables locales qui se passe dans la pile,

196
00:14:19,960 --> 00:14:24,790
et chaque fonction obtient son propre espace sur la pile, son cadre propre pile est ce que ça s'appelle.

197
00:14:24,790 --> 00:14:31,590
Alors principale a son stack frame, et à l'intérieur de celui-ci va exister ce tableau numbers,

198
00:14:31,590 --> 00:14:34,270
et il va y avoir de sizeof taille (nombre).

199
00:14:34,270 --> 00:14:38,180
Il va avoir la taille d'un nombre divisé par la taille des éléments,

200
00:14:38,180 --> 00:14:42,010
mais que toutes les vies dans stack frame principale.

201
00:14:42,010 --> 00:14:45,190
Lorsque nous appelons la recherche, la recherche tient son propre cadre de pile,

202
00:14:45,190 --> 00:14:48,840
son propre espace pour stocker toutes ses variables locales.

203
00:14:48,840 --> 00:14:56,420
Mais ces arguments - de sorte botte de foin n'est pas une copie de ce tableau entier.

204
00:14:56,420 --> 00:15:00,990
Nous ne transmettons pas dans le tableau en tant que copie en recherche.

205
00:15:00,990 --> 00:15:04,030
Il passe juste une référence à ce tableau.

206
00:15:04,030 --> 00:15:11,470
Ainsi, la recherche peut accéder à ces numéros par cette référence.

207
00:15:11,470 --> 00:15:17,100
Il est toujours accéder aux choses qui vivent à l'intérieur du cadre de pile principale,

208
00:15:17,100 --> 00:15:22,990
mais au fond, quand on arrive à des pointeurs, qui devrait être bientôt,

209
00:15:22,990 --> 00:15:24,980
c'est ce que les pointeurs sont.

210
00:15:24,980 --> 00:15:29,400
Les pointeurs sont juste des références à des choses, et vous pouvez utiliser des pointeurs pour accéder à des choses

211
00:15:29,400 --> 00:15:32,030
qui sont dans les cadres de pile d'autres choses.

212
00:15:32,030 --> 00:15:37,660
Ainsi, même si le nombre est locale au menu principal, on peut toujours y accéder via ce pointeur.

213
00:15:37,660 --> 00:15:41,770
Mais puisque c'est juste un pointeur et c'est juste une référence,

214
00:15:41,770 --> 00:15:45,040
sizeof (botte de foin) retourne juste la taille de la référence elle-même.

215
00:15:45,040 --> 00:15:47,950
Il ne retourne pas la taille de la chose qu'il pointe vers.

216
00:15:47,950 --> 00:15:51,110
Il ne retourne pas la taille réelle des chiffres.

217
00:15:51,110 --> 00:15:55,660
Et si cela ne va pas travailler comme nous le voulons.

218
00:15:55,660 --> 00:15:57,320
>> Questions à ce sujet?

219
00:15:57,320 --> 00:16:03,250
Pointeurs aura disparu dans beaucoup plus de détails dans le gore dans les semaines à venir.

220
00:16:06,750 --> 00:16:13,740
Et c'est pourquoi beaucoup de choses que vous voyez, des choses ou des choses la plupart des recherches de tri,

221
00:16:13,740 --> 00:16:16,990
ils sont presque tous besoin de prendre la taille réelle de la matrice,

222
00:16:16,990 --> 00:16:20,440
parce que dans C, nous n'avons aucune idée de ce que la taille du tableau est.

223
00:16:20,440 --> 00:16:22,720
Vous devez manuellement passer po

224
00:16:22,720 --> 00:16:27,190
Et vous ne pouvez pas passer manuellement dans le tableau en entier, car vous êtes juste de passage dans la référence

225
00:16:27,190 --> 00:16:30,390
et il ne peut pas obtenir la taille de la référence.

226
00:16:30,390 --> 00:16:32,300
D'accord.

227
00:16:32,300 --> 00:16:38,160
Alors maintenant, nous voulons mettre en œuvre ce qui a été expliqué précédemment.

228
00:16:38,160 --> 00:16:41,530
Vous pouvez travailler sur cela pendant une minute,

229
00:16:41,530 --> 00:16:45,250
et vous n'avez pas à vous soucier de faire tout à la perfection à 100% de travail.

230
00:16:45,250 --> 00:16:51,410
Il suffit d'écrire le pseudo-moitié pour la façon dont vous pensez que cela devrait fonctionner.

231
00:16:52,000 --> 00:16:53,630
D'accord.

232
00:16:53,630 --> 00:16:56,350
Pas besoin d'être complètement fini avec ce moment.

233
00:16:56,350 --> 00:17:02,380
Mais personne ne se sentent à l'aise avec ce qu'ils ont à ce jour,

234
00:17:02,380 --> 00:17:05,599
comme quelque chose que nous pouvons travailler avec ensemble?

235
00:17:05,599 --> 00:17:09,690
Quelqu'un veut-il faire du bénévolat? Ou je vais choisir au hasard.

236
00:17:12,680 --> 00:17:18,599
Il n'a pas besoin d'être juste à côté de toute mesure, mais quelque chose que nous pouvons modifier dans un état opérationnel.

237
00:17:18,599 --> 00:17:20,720
[L'élève] Bien sûr. Ok >>.

238
00:17:20,720 --> 00:17:27,220
Ainsi, vous pouvez enregistrer la révision en cliquant sur la petite icône Enregistrer.

239
00:17:27,220 --> 00:17:29,950
Vous êtes Ramya, non? >> [L'élève] Ouais. >> [Bowden] D'accord.

240
00:17:29,950 --> 00:17:35,140
Alors maintenant, je peux voir votre révision et tout le monde peut tirer jusqu'à la révision.

241
00:17:35,140 --> 00:17:38,600
Et nous avons ici - D'accord.

242
00:17:38,600 --> 00:17:43,160
Donc Ramya allé avec la solution récursive, ce qui est certainement une solution valable.

243
00:17:43,160 --> 00:17:44,970
Il ya deux façons que vous pouvez faire à ce problème.

244
00:17:44,970 --> 00:17:48,060
Vous pouvez soit le faire de manière itérative ou récursive.

245
00:17:48,060 --> 00:17:53,860
La plupart des problèmes que vous rencontrez qui peut être fait de manière récursive peut aussi être fait de manière itérative.

246
00:17:53,860 --> 00:17:58,510
Donc, ici, nous l'avons fait de manière récursive.

247
00:17:58,510 --> 00:18:03,730
>> Quelqu'un veut-il définir ce que signifie faire une fonction récursive?

248
00:18:07,210 --> 00:18:08,920
[L'élève] Lorsque vous avez une fonction appel lui-même

249
00:18:08,920 --> 00:18:13,470
puis s'appeler elle-même jusqu'à ce qu'il ressorte avec une véritable et vrai. Ouais >>.

250
00:18:13,470 --> 00:18:17,680
Une fonction récursive est juste une fonction qui s'appelle elle-même.

251
00:18:17,680 --> 00:18:24,140
Il ya trois grandes choses qui une fonction récursive doit avoir.

252
00:18:24,140 --> 00:18:27,310
Le premier est évidemment, il s'appelle lui-même.

253
00:18:27,310 --> 00:18:29,650
Le second est le cas de base.

254
00:18:29,650 --> 00:18:33,390
Donc, à un certain moment la fonction doit cesser de se nommant,

255
00:18:33,390 --> 00:18:35,610
et c'est ce qui est le cas de base pour.

256
00:18:35,610 --> 00:18:43,860
Donc, ici, nous savons que nous devrions arrêter, nous devrions abandonner dans notre recherche

257
00:18:43,860 --> 00:18:48,150
lorsque le démarrage est égal à la fin - et nous allons passer en revue ce que cela signifie.

258
00:18:48,150 --> 00:18:52,130
Mais finalement, la dernière chose qui est important pour les fonctions récursives:

259
00:18:52,130 --> 00:18:59,250
les fonctions doivent en quelque sorte l'approche du cas de base.

260
00:18:59,250 --> 00:19:04,140
Comme si vous n'êtes pas réellement mettre à jour quoi que ce soit lorsque vous faites le deuxième appel récursif,

261
00:19:04,140 --> 00:19:07,880
si vous êtes littéralement juste d'appeler la fonction à nouveau avec les mêmes arguments

262
00:19:07,880 --> 00:19:10,130
et aucune des variables globales ont changé ou quoi que ce soit,

263
00:19:10,130 --> 00:19:14,430
vous n'atteindrez jamais le scénario de référence, dans ce cas, c'est mauvais.

264
00:19:14,430 --> 00:19:17,950
Ce sera une récursion infinie et un débordement de pile.

265
00:19:17,950 --> 00:19:24,330
Mais ici, nous voyons que la mise à jour se passe, puisque nous mettons à jour start + fin / 2,

266
00:19:24,330 --> 00:19:28,180
nous mettons à jour l'argument final ici, nous mettons à jour l'argument start ici.

267
00:19:28,180 --> 00:19:32,860
Donc, dans tous les appels récursifs nous mettons à jour quelque chose. D'accord.

268
00:19:32,860 --> 00:19:38,110
Voulez-vous nous expliquer votre solution? >> Bien sûr.

269
00:19:38,110 --> 00:19:44,270
J'utilise SearchHelp de sorte que chaque fois que je fais cet appel de fonction

270
00:19:44,270 --> 00:19:47,910
J'ai le début de l'endroit où je suis à la recherche de l'agencement et la fin

271
00:19:47,910 --> 00:19:49,380
d'où je suis à la recherche du tableau.

272
00:19:49,380 --> 00:19:55,330
>> A chaque étape où il est dit que c'est l'élément central, qui est de début + fin / 2,

273
00:19:55,330 --> 00:19:58,850
c'est équivalent à ce que nous recherchons?

274
00:19:58,850 --> 00:20:04,650
Et si c'est le cas, nous l'avons trouvé, et je suppose qui est passé les niveaux de récursivité.

275
00:20:04,650 --> 00:20:12,540
Et si ce n'est pas vrai, alors nous vérifions si cette valeur milieu du tableau est trop grand,

276
00:20:12,540 --> 00:20:19,320
Dans ce cas, nous regardons la moitié gauche du tableau en allant du début à l'indice du milieu.

277
00:20:19,320 --> 00:20:22,710
Et sinon, nous ne la demi final.

278
00:20:22,710 --> 00:20:24,740
[Bowden] D'accord.

279
00:20:24,740 --> 00:20:27,730
Ça a l'air bien.

280
00:20:27,730 --> 00:20:36,640
Ok, donc un couple des choses, et en fait, c'est une chose très haut niveau

281
00:20:36,640 --> 00:20:41,270
que vous n'aurez jamais besoin de savoir pour ce cours, mais il est vrai.

282
00:20:41,270 --> 00:20:46,080
Les fonctions récursives, vous entendez toujours qu'ils sont une mauvaise affaire

283
00:20:46,080 --> 00:20:51,160
parce que si vous vous appeler récursivement trop de fois, vous obtenez un débordement de pile

284
00:20:51,160 --> 00:20:54,990
puisque, comme je l'ai dit précédemment, chaque fonction obtient son cadre propre pile.

285
00:20:54,990 --> 00:20:59,500
Ainsi, chaque appel de la fonction récursive obtient son cadre propre pile.

286
00:20:59,500 --> 00:21:04,140
Donc, si vous faites des appels récursifs 1000, vous obtenez 1.000 images de la pile,

287
00:21:04,140 --> 00:21:08,390
et rapidement vous amener à avoir des frames de pile trop de choses et tout casser.

288
00:21:08,390 --> 00:21:13,480
C'est pour cela que les fonctions récursives sont généralement mauvais.

289
00:21:13,480 --> 00:21:19,370
Mais il est bien un sous-ensemble des fonctions récursives appelé queue-récursives,

290
00:21:19,370 --> 00:21:26,120
et cela arrive à être un exemple de celui où si le compilateur le remarque

291
00:21:26,120 --> 00:21:29,920
et il se doit, je pense - en Clang si vous lui passez le drapeau-O2

292
00:21:29,920 --> 00:21:33,250
puis il s'en apercevra est récursive et rendre les choses bien.

293
00:21:33,250 --> 00:21:40,050
>> Il va réutiliser le même frame de pile maintes et maintes fois pour chaque appel récursif.

294
00:21:40,050 --> 00:21:47,010
Et donc puisque vous utilisez le même frame de pile, vous n'avez pas besoin de s'inquiéter

295
00:21:47,010 --> 00:21:51,690
jamais empiler débordement, et en même temps, comme vous l'avez dit,

296
00:21:51,690 --> 00:21:56,380
où une fois que vous revenez vrai, alors il doit retourner jusqu'à l'ensemble de ces cadres de pile

297
00:21:56,380 --> 00:22:01,740
et le 10e appel à SearchHelp doit retourner à la 9e, doit retourner à la 8e.

298
00:22:01,740 --> 00:22:05,360
Donc, qui n'a pas besoin de se produire lorsque les fonctions sont récursive.

299
00:22:05,360 --> 00:22:13,740
Et si ce qui rend cette queue fonction récursive est remarquerez que, pour tout appel donné à SearchHelp

300
00:22:13,740 --> 00:22:18,470
l'appel récursif qu'il a fait est ce qu'il est de retour.

301
00:22:18,470 --> 00:22:25,290
Ainsi, dans le premier appel à SearchHelp, soit nous retourner immédiatement faux,

302
00:22:25,290 --> 00:22:29,590
immédiatement renvoie true, sinon on fait un appel récursif à SearchHelp

303
00:22:29,590 --> 00:22:33,810
où ce que nous sommes de retour est ce que cet appel est de retour.

304
00:22:33,810 --> 00:22:51,560
Et nous ne pouvions pas le faire si nous avons fait quelque chose comme int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
quelques-unes changement aléatoire.

306
00:22:55,440 --> 00:23:01,470
>> Alors maintenant, cet appel récursif, cette int x = SearchHelp appel récursif,

307
00:23:01,470 --> 00:23:05,740
n'est plus récursive car il a bel et bien de revenir

308
00:23:05,740 --> 00:23:10,400
retour à un cadre de pile précédente de sorte que cet appel à la fonction précédente

309
00:23:10,400 --> 00:23:13,040
peut alors faire quelque chose avec la valeur de retour.

310
00:23:13,040 --> 00:23:22,190
Donc, ce n'est pas récursive terminale, mais ce que nous avions avant est bien récursive. Ouais.

311
00:23:22,190 --> 00:23:27,000
[Étudiants] ne devrait pas le cas la deuxième base être vérifié en premier

312
00:23:27,000 --> 00:23:30,640
parce qu'il pourrait y avoir une situation où lorsque vous lui transmettez l'argument

313
00:23:30,640 --> 00:23:35,770
vous avez commencer à la fin =, mais ils sont la valeur aiguille.

314
00:23:35,770 --> 00:23:47,310
La question a été ne peut pas nous lancer dans le cas où la fin est la valeur aiguille

315
00:23:47,310 --> 00:23:52,000
ou commencer à la fin =, de manière appropriée, commencer à la fin =

316
00:23:52,000 --> 00:23:59,480
et vous n'avez pas fait vérifier cette valeur particulière encore,

317
00:23:59,480 --> 00:24:03,910
puis commencer à la fin + / 2 va juste être la même valeur.

318
00:24:03,910 --> 00:24:07,890
Mais nous avons déjà retourné false et nous n'avons jamais réellement vérifié la valeur.

319
00:24:07,890 --> 00:24:14,240
Donc, à tout le moins, dans le premier appel, si la taille est 0, alors nous voulons retourner faux.

320
00:24:14,240 --> 00:24:17,710
Mais si la taille est 1, puis départ ne va pas jusqu'à la fin de l'égalité,

321
00:24:17,710 --> 00:24:19,820
et nous allons vérifier au moins l'un des éléments.

322
00:24:19,820 --> 00:24:26,750
Mais je pense que vous avez raison dans ce que nous pouvons retrouver dans un cas où commencer fin + / 2,

323
00:24:26,750 --> 00:24:31,190
début finit par être le même que celui de début + fin / 2,

324
00:24:31,190 --> 00:24:35,350
mais nous n'avons jamais réellement vérifié cet élément.

325
00:24:35,350 --> 00:24:44,740
>> Donc, si nous vérifions d'abord est l'élément central de la valeur que nous recherchons,

326
00:24:44,740 --> 00:24:47,110
alors nous pouvons immédiatement retourner vrai.

327
00:24:47,110 --> 00:24:50,740
Sinon, si ils sont égaux, alors il n'y a pas lieu de poursuivre

328
00:24:50,740 --> 00:24:58,440
puisque nous allons juste mettre à jour au cas où nous sommes sur un tableau à un seul élément.

329
00:24:58,440 --> 00:25:01,110
Si ce seul élément n'est pas celle que nous recherchons,

330
00:25:01,110 --> 00:25:03,530
alors tout est faux. Ouais.

331
00:25:03,530 --> 00:25:08,900
[L'élève] Le fait est que puisque la taille est en fait plus grand que le nombre d'éléments dans le tableau,

332
00:25:08,900 --> 00:25:13,070
il ya déjà un décalage - >> Il en sera de taille -

333
00:25:13,070 --> 00:25:19,380
[L'élève] Dis: si le tableau était de taille 0, alors le SearchHelp sera effectivement vérifier botte de foin de 0

334
00:25:19,380 --> 00:25:21,490
au premier appel.

335
00:25:21,490 --> 00:25:25,300
Le tableau a une taille de 0, de sorte que le 0 est - >> Oui.

336
00:25:25,300 --> 00:25:30,750
Il ya une autre chose qui - il pourrait être bon. Réfléchissons.

337
00:25:30,750 --> 00:25:40,120
Donc, si le tableau avait 10 éléments et celui du milieu que nous allons faire est de vérifier l'index 5,

338
00:25:40,120 --> 00:25:45,700
si nous vérifions 5, et disons que la valeur est inférieure.

339
00:25:45,700 --> 00:25:50,720
Nous sommes donc en jetant tout de suite de 5 en avant.

340
00:25:50,720 --> 00:25:54,030
Donc, commencer à la fin + / 2 va être notre nouveau,

341
00:25:54,030 --> 00:25:57,450
alors oui, il va toujours rester au-delà de la fin du tableau.

342
00:25:57,450 --> 00:26:03,570
Si c'est une affaire si elle était pair ou impair, alors nous vérifions, disons, 4,

343
00:26:03,570 --> 00:26:05,770
mais nous sommes toujours jeter -

344
00:26:05,770 --> 00:26:13,500
Alors oui, la fin est toujours va être au-delà de la fin réelle de la matrice.

345
00:26:13,500 --> 00:26:18,350
Ainsi, les éléments que nous nous concentrons sur la fin est toujours va être celle d'après.

346
00:26:18,350 --> 00:26:24,270
Et donc si le démarrage ne jamais finir égales par ailleurs, nous sommes dans un tableau de taille 0.

347
00:26:24,270 --> 00:26:35,600
>> L'autre chose que je pensais, c'est que nous mettons à jour début à la fin start + / 2,

348
00:26:35,600 --> 00:26:44,020
si c'est le cas que je vais avoir des ennuis avec, d'où partent + fin / 2

349
00:26:44,020 --> 00:26:46,820
est l'élément nous vérifions.

350
00:26:46,820 --> 00:26:58,150
Disons que nous avons eu ce tableau de 10 éléments. Peu importe.

351
00:26:58,150 --> 00:27:03,250
Donc, commencer à la fin + / 2 va être quelque chose comme celui-ci,

352
00:27:03,250 --> 00:27:07,060
et si ce n'est pas la valeur, disons que nous voulons mettre à jour.

353
00:27:07,060 --> 00:27:10,060
La valeur est supérieure, si nous voulons regarder cette moitié du tableau.

354
00:27:10,060 --> 00:27:15,910
Alors, comment nous mettons à jour début, nous mettons à jour début à maintenant cet élément.

355
00:27:15,910 --> 00:27:23,790
Mais cela peut encore travailler, ou à tout le moins, vous pouvez le faire début + fin / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[L'élève] Vous n'avez pas besoin d'être commencer à la fin + [inaudible] >> Oui.

357
00:27:27,850 --> 00:27:33,240
Nous avons déjà vérifié cet élément et sais que ce n'est pas celui que nous recherchons.

358
00:27:33,240 --> 00:27:36,800
Donc, nous n'avons pas besoin de mettre à jour début pour être cet élément.

359
00:27:36,800 --> 00:27:39,560
Nous ne pouvons tout simplement l'ignorer et mettre à jour commence à être de cet élément.

360
00:27:39,560 --> 00:27:46,060
Et y at-il jamais un cas, disons que ce sont fin,

361
00:27:46,060 --> 00:27:53,140
oui, alors commencer serait cela, démarrez + fin / 2 ne serait-ce,

362
00:27:53,140 --> 00:28:00,580
commencer à la fin + - Ouais, je pense que ça peut se retrouver dans une récursion infinie.

363
00:28:00,580 --> 00:28:12,690
Disons que c'est juste un tableau de taille 2 ou un tableau de taille 1. Je pense que cela va fonctionner.

364
00:28:12,690 --> 00:28:19,490
Donc, actuellement, c'est que l'élément de départ et de fin est de 1 au-delà.

365
00:28:19,490 --> 00:28:24,110
Ainsi, l'élément que nous allons faire est de vérifier celui-ci,

366
00:28:24,110 --> 00:28:29,400
et puis quand nous mettons à jour début, nous mettons à jour début à 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
qui va nous finir de retour avec départ étant cet élément.

368
00:28:33,160 --> 00:28:36,210
>> Donc, nous vérifions le même élément, encore et encore.

369
00:28:36,210 --> 00:28:43,310
C'est donc le cas où chaque appel récursif doit effectivement mettre à jour quelque chose.

370
00:28:43,310 --> 00:28:48,370
Nous avons donc besoin de faire start + fin / 2 + 1, ou bien il s'agit d'un cas

371
00:28:48,370 --> 00:28:50,710
où nous ne sommes pas réellement la mise à jour de départ.

372
00:28:50,710 --> 00:28:53,820
Tout le monde voit que?

373
00:28:53,820 --> 00:28:56,310
D'accord.

374
00:28:56,310 --> 00:29:03,860
Quelqu'un at-il des questions sur cette solution ou d'autres commentaires?

375
00:29:05,220 --> 00:29:10,280
D'accord. Quelqu'un at-il une solution itérative que nous pouvons tous regarder?

376
00:29:17,400 --> 00:29:20,940
Avons-nous tous le faire de manière récursive?

377
00:29:20,940 --> 00:29:25,950
Ou aussi, je suppose que si vous sienne ouverte, alors vous pourriez avoir annulé le précédent.

378
00:29:25,950 --> 00:29:28,810
Est-ce qu'il enregistre automatiquement? Je ne suis pas positif.

379
00:29:35,090 --> 00:29:39,130
Quelqu'un at-il itérative?

380
00:29:39,130 --> 00:29:42,430
Nous pouvons marcher à travers elle même si elle n'est pas.

381
00:29:46,080 --> 00:29:48,100
L'idée va être la même chose.

382
00:30:00,260 --> 00:30:02,830
Solution itérative.

383
00:30:02,830 --> 00:30:07,140
Nous allons vouloir faire essentiellement la même idée

384
00:30:07,140 --> 00:30:16,530
où nous voulons garder la trace de la nouvelle extrémité de la barrette et le nouveau départ de la matrice

385
00:30:16,530 --> 00:30:18,510
et cela à plusieurs reprises.

386
00:30:18,510 --> 00:30:22,430
Et si ce qu'on garde une trace de que le début et la fin se croisent jamais,

387
00:30:22,430 --> 00:30:29,020
alors nous n'avons pas à le trouver et nous pouvons renvoyer false.

388
00:30:29,020 --> 00:30:37,540
Alors, comment puis-je faire cela? N'importe qui ont des suggestions ou des codes pour me tirer vers le haut?

389
00:30:42,190 --> 00:30:47,450
[L'élève] Faites une boucle while. Ouais >>.

390
00:30:47,450 --> 00:30:49,450
Vous allez avoir à faire une boucle.

391
00:30:49,450 --> 00:30:51,830
>> Avez-vous eu le code que je pouvais tirer vers le haut, ou ce que tu allais à suggérer?

392
00:30:51,830 --> 00:30:56,340
[L'élève] Je pense que oui. Tous droits >>. Cela rend les choses plus faciles. Quel est votre nom?

393
00:30:56,340 --> 00:30:57,890
[L'élève] Lucas.

394
00:31:00,140 --> 00:31:04,190
Révision 1. D'accord.

395
00:31:04,190 --> 00:31:13,200
Low est ce que nous appelons commencer avant.

396
00:31:13,200 --> 00:31:17,080
Up est pas tout à fait ce que nous avons appelé avant la fin.

397
00:31:17,080 --> 00:31:22,750
En fait, la fin est maintenant dans le tableau. C'est un élément que nous devrions prendre en considération.

398
00:31:22,750 --> 00:31:26,890
Si bas, c'est 0, c'est la taille du tableau - 1,

399
00:31:26,890 --> 00:31:34,780
et maintenant nous sommes en boucle, et nous vérifions -

400
00:31:34,780 --> 00:31:37,340
Je suppose que vous pouvez marcher à travers elle.

401
00:31:37,340 --> 00:31:41,420
Quel était votre pensée à travers ce? Nous parcourir votre code.

402
00:31:41,420 --> 00:31:49,940
[L'élève] Bien sûr. Regardez la valeur botte de foin au milieu et le comparer à l'aiguille.

403
00:31:49,940 --> 00:31:58,520
Donc, si elle est supérieure à l'aiguille, alors vous voulez - oh, en fait, ce devrait être à l'envers.

404
00:31:58,520 --> 00:32:05,180
Vous allez avoir à jeter la moitié droite, et alors oui, que devrait être l'inverse.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Donc, cela devrait être moins? Est-ce que vous avez dit? >> [L'élève] Ouais.

406
00:32:08,830 --> 00:32:10,390
[Bowden] D'accord. Moins.

407
00:32:10,390 --> 00:32:15,700
Donc, si ce que nous cherchons est inférieur à ce que nous voulons,

408
00:32:15,700 --> 00:32:19,410
alors oui, nous voulons jeter la moitié gauche,

409
00:32:19,410 --> 00:32:22,210
ce qui signifie que nous mettons à jour tout ce que nous envisageons

410
00:32:22,210 --> 00:32:26,610
en déplaçant bas à droite de la matrice.

411
00:32:26,610 --> 00:32:30,130
Cela semble bon.

412
00:32:30,130 --> 00:32:34,550
Je pense qu'il a le même problème que nous avons dit sur le précédent,

413
00:32:34,550 --> 00:32:49,760
où si faible est 0 et est en hausse de 1, puis bas + haut / 2 va être mis en place pour la même chose.

414
00:32:49,760 --> 00:32:53,860
>> Et même si ce n'est pas le cas, il est encore plus efficace à tout le moins

415
00:32:53,860 --> 00:32:57,630
accepter de perdre l'élément que nous venons d'examiner que nous savons être faux.

416
00:32:57,630 --> 00:33:03,240
Si bas + haut / 2 + 1 - >> [l'élève] Cela devrait être l'inverse.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Ou cela devrait être - 1 et l'autre doit être de + 1.

418
00:33:05,900 --> 00:33:09,580
[L'élève] Et il devrait y avoir un double signe égal. >> [Bowden] Ouais.

419
00:33:09,580 --> 00:33:11,340
[L'élève] Ouais.

420
00:33:14,540 --> 00:33:15,910
D'accord.

421
00:33:15,910 --> 00:33:21,280
Et enfin, maintenant que nous avons ce 1 + - 1 chose,

422
00:33:21,280 --> 00:33:31,520
est-il - il ne serait pas - est-il jamais possible à faible de se retrouver avec une valeur supérieure à neuf?

423
00:33:35,710 --> 00:33:40,320
Je pense que la seule façon qui puisse arriver - Est-il possible? >> [L'élève] Je ne sais pas.

424
00:33:40,320 --> 00:33:45,220
Mais si elle devient tronqué et puis obtient moins que 1, puis - >> Oui.

425
00:33:45,220 --> 00:33:47,480
[L'élève] Il serait peut-être manquant.

426
00:33:49,700 --> 00:33:53,940
Je pense que ça devrait être bon seulement parce que

427
00:33:53,940 --> 00:33:58,800
pour elle de se retrouver plus faible qu'ils doivent être égaux, je pense.

428
00:33:58,800 --> 00:34:03,070
Mais si elles sont égales, alors nous n'aurions pas pu faire la boucle while pour commencer

429
00:34:03,070 --> 00:34:06,670
et nous venons aurait retourné la valeur. Donc, je pense que nous sommes bien maintenant.

430
00:34:06,670 --> 00:34:11,530
Notez que même si ce problème n'est plus récursive,

431
00:34:11,530 --> 00:34:17,400
le même genre d'idées applicables où l'on peut voir comment cela si facilement se prête

432
00:34:17,400 --> 00:34:23,659
à une solution récursive par le fait que nous ne faisons que mettre à jour les indices maintes et maintes fois,

433
00:34:23,659 --> 00:34:29,960
nous faisons le problème plus en plus petits, nous mettons l'accent sur un sous-ensemble du tableau.

434
00:34:29,960 --> 00:34:40,860
[L'élève] Si faible est de 0 et plus est 1, ils seraient tous les deux 0 + 1/2, ce qui irait à 0,

435
00:34:40,860 --> 00:34:44,429
puis on serait + 1, on serait - 1.

436
00:34:47,000 --> 00:34:50,870
[L'élève] Où allons-nous vérifier l'égalité?

437
00:34:50,870 --> 00:34:55,100
Comme si le milieu est en fait l'aiguille?

438
00:34:55,100 --> 00:34:58,590
Nous ne sommes pas en train de faire cela? Oh!

439
00:35:00,610 --> 00:35:02,460
Si C'est -

440
00:35:05,340 --> 00:35:13,740
Oui. Nous ne pouvons pas faire le test ici parce que disons que le milieu en premier -

441
00:35:13,740 --> 00:35:16,430
[L'élève] Il s'agit en fait n'aime pas jeter la borne.

442
00:35:16,430 --> 00:35:20,220
Donc, si vous jetez la limite, il faut d'abord vérifier ou autre.

443
00:35:20,220 --> 00:35:23,350
Ah. Ouais. >> [L'élève] Ouais.

444
00:35:23,350 --> 00:35:29,650
Alors maintenant, nous avons jeté celui que nous avons actuellement regardé,

445
00:35:29,650 --> 00:35:33,260
ce qui signifie que nous avons maintenant besoin d'avoir aussi

446
00:35:33,260 --> 00:35:44,810
if (botte de foin [(bas + haut) / 2] == aiguille), alors on peut retourner la valeur true.

447
00:35:44,810 --> 00:35:52,070
Et si je mets autre ou tout simplement si, il signifie littéralement la même chose

448
00:35:52,070 --> 00:35:57,110
parce que cela aurait renvoyé true.

449
00:35:57,110 --> 00:36:01,450
Donc, je vais mettre d'autre si, mais ce n'est pas grave.

450
00:36:01,450 --> 00:36:10,440
>> Donc, d'autre si cela, sinon cela, et c'est une chose commune que je fais

451
00:36:10,440 --> 00:36:14,340
où même si c'est le cas, où tout est bon ici,

452
00:36:14,340 --> 00:36:22,780
comme faible ne peut jamais être supérieur à toi, c'est pas un raisonnement vaut pour savoir si c'est vrai.

453
00:36:22,780 --> 00:36:28,010
Ainsi, vous pouvez tout aussi bien dire tout bas est inférieur ou égal à

454
00:36:28,010 --> 00:36:30,720
ou alors faible est inférieur à

455
00:36:30,720 --> 00:36:35,300
si elles ne sont jamais égales ou faible qui se passe pour la laisser passer,

456
00:36:35,300 --> 00:36:40,130
alors nous pouvons sortir de cette boucle.

457
00:36:41,410 --> 00:36:44,630
Questions, préoccupations, commentaires?

458
00:36:47,080 --> 00:36:49,270
D'accord. Cela semble bon.

459
00:36:49,270 --> 00:36:52,230
Maintenant, nous voulons faire de tri.

460
00:36:52,230 --> 00:37:04,030
Si nous passons à mon deuxième révision, nous voyons ces mêmes chiffres,

461
00:37:04,030 --> 00:37:07,550
mais maintenant ils ne sont plus dans l'ordre.

462
00:37:07,550 --> 00:37:12,840
Et nous voulons mettre en œuvre trier par n'importe quel algorithme en O de n log n.

463
00:37:12,840 --> 00:37:17,240
Ainsi, l'algorithme pensez-vous que nous devrions mettre en œuvre ici? >> [L'élève] Tri par fusion.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ouais. Le tri par fusion est en O (n log n), et c'est ce que nous allons faire.

465
00:37:23,810 --> 00:37:26,680
Et le problème va être assez similaire,

466
00:37:26,680 --> 00:37:31,920
où il se prête facilement à une solution récursive.

467
00:37:31,920 --> 00:37:35,580
Nous pouvons également venir avec une solution itérative si l'on veut,

468
00:37:35,580 --> 00:37:42,540
mais la récursivité sera plus facile ici et que nous devrions faire la récursivité.

469
00:37:45,120 --> 00:37:49,530
Je suppose que nous allons traverser tri par fusion d'abord,

470
00:37:49,530 --> 00:37:54,280
bien qu'il y ait une belle vidéo sur le tri par fusion déjà. [Rires]

471
00:37:54,280 --> 00:37:59,780
Ainsi, le tri par fusion il ya - je perds tellement de ce document.

472
00:37:59,780 --> 00:38:02,080
Oh, il n'en reste qu'un.

473
00:38:02,080 --> 00:38:03,630
Donc fusionner.

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

475
00:38:26,090 --> 00:38:27,440
D'accord.

476
00:38:29,910 --> 00:38:33,460
Merge prend deux tableaux distincts.

477
00:38:33,460 --> 00:38:36,780
Individuellement ces deux tableaux sont tous deux classés.

478
00:38:36,780 --> 00:38:40,970
Donc ce tableau, 1, 3, 5, triées. Ce tableau, 0, 2, 4, triées.

479
00:38:40,970 --> 00:38:46,710
Maintenant, ce que la fusion devrait faire est de les combiner en un seul module qui est elle-même triée.

480
00:38:46,710 --> 00:38:57,130
Nous voulons donc un tableau de taille 6 qui va avoir ces éléments à l'intérieur de celui-ci

481
00:38:57,130 --> 00:38:59,390
dans l'ordre.

482
00:38:59,390 --> 00:39:03,390
>> Et afin que nous puissions profiter du fait que ces deux tableaux sont triés

483
00:39:03,390 --> 00:39:06,800
pour ce faire dans un temps linéaire,

484
00:39:06,800 --> 00:39:13,510
sens du temps linéaire si ce tableau est de taille x et y c'est la taille,

485
00:39:13,510 --> 00:39:20,970
alors l'algorithme global doit être O (x + y). D'accord.

486
00:39:20,970 --> 00:39:23,150
Alors suggestions.

487
00:39:23,150 --> 00:39:26,030
[L'élève] Pourrions-nous commencer par la gauche?

488
00:39:26,030 --> 00:39:30,150
Alors vous allez mettre le 0 en bas d'abord, puis le 1, puis là, vous êtes à la 2.

489
00:39:30,150 --> 00:39:33,320
Donc, c'est un peu comme vous avez un onglet qui se déplace vers la droite. >> [Bowden] Ouais.

490
00:39:33,320 --> 00:39:41,070
Pour ces deux tableaux si on se concentre sur l'élément le plus à gauche.

491
00:39:41,070 --> 00:39:43,530
Parce que les deux tableaux sont triés, nous savons que ces 2 éléments

492
00:39:43,530 --> 00:39:46,920
sont les éléments les plus petits dans les deux ensemble.

493
00:39:46,920 --> 00:39:53,500
Cela signifie donc que 1 de ces 2 éléments doivent être le plus petit élément dans notre tableau fusionné.

494
00:39:53,500 --> 00:39:58,190
Il se trouve que le plus petit est celui sur la droite cette fois.

495
00:39:58,190 --> 00:40:02,580
Donc, nous prenons 0, l'insérer sur la gauche, parce que 0 est inférieur à 1,

496
00:40:02,580 --> 00:40:08,210
de sorte que 0, l'insérer dans notre première position, puis nous mettons à jour cette

497
00:40:08,210 --> 00:40:12,070
à concentrer maintenant sur le premier élément.

498
00:40:12,070 --> 00:40:14,570
Et maintenant, nous le répétons.

499
00:40:14,570 --> 00:40:20,670
Alors maintenant, nous comparons 2 et 1. 1 est plus petit, donc nous allons insérer 1.

500
00:40:20,670 --> 00:40:25,300
Nous mettons à jour ce pointeur pour pointer vers ce type.

501
00:40:25,300 --> 00:40:33,160
Maintenant, nous le faisons à nouveau, donc 2. Cela mettra à jour, comparez ces 2, 3.

502
00:40:33,160 --> 00:40:37,770
Cette mise à jour, puis 4 et 5.

503
00:40:37,770 --> 00:40:42,110
Donc, c'est la fusion.

504
00:40:42,110 --> 00:40:49,010
>> Il devrait être assez évident qu'il est temps linéaire, puisque nous venons de traverser chaque élément une fois.

505
00:40:49,010 --> 00:40:55,980
Et c'est le plus grand pas à mettre en œuvre le tri par fusion fait cela.

506
00:40:55,980 --> 00:40:59,330
Et ce n'est pas si dur.

507
00:40:59,330 --> 00:41:15,020
Un couple de choses à s'inquiéter pour est, disons nous étions fusion 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Dans ce cas, nous nous retrouvons dans la situation où celui-ci va être plus petit,

509
00:41:30,930 --> 00:41:36,160
puis nous mettons à jour ce pointeur, celui-ci va être plus petit, mettre à jour ce,

510
00:41:36,160 --> 00:41:41,280
celui-ci est plus petit, et maintenant il faut reconnaître

511
00:41:41,280 --> 00:41:44,220
quand vous avez fait fonctionner à partir d'éléments de comparaison.

512
00:41:44,220 --> 00:41:49,400
Comme nous avons déjà utilisé ce tableau entier,

513
00:41:49,400 --> 00:41:55,190
tout dans ce tableau est maintenant venez d'insérer dans ici.

514
00:41:55,190 --> 00:42:02,040
Donc, si jamais nous lancer dans le point où l'un de nos tableaux est déjà complètement fusionné,

515
00:42:02,040 --> 00:42:06,510
alors que nous venons de prendre tous les éléments de l'autre réseau et les insérer dans la fin du tableau.

516
00:42:06,510 --> 00:42:13,630
Afin que nous puissions vous suffit d'insérer 4, 5, 6. D'accord.

517
00:42:13,630 --> 00:42:18,070
C'est une chose à surveiller.

518
00:42:22,080 --> 00:42:26,120
La mise en œuvre qui devrait être l'étape 1.

519
00:42:26,120 --> 00:42:32,600
Fusionner les trier ensuite sur cette base, il est à 2 pas, à 2 pas stupides.

520
00:42:38,800 --> 00:42:42,090
Donnons ce tableau.

521
00:42:57,920 --> 00:43:05,680
Ainsi, le tri par fusion, étape 1 consiste à casser de manière récursive le tableau en deux moitiés.

522
00:43:05,680 --> 00:43:09,350
Donc diviser ce tableau en deux moitiés.

523
00:43:09,350 --> 00:43:22,920
Nous avons maintenant 4, 15, 16, 50 et 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Et maintenant nous le faisons à nouveau et nous avons partagé ces en deux moitiés.

525
00:43:25,800 --> 00:43:27,530
Je vais le faire de ce côté.

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

527
00:43:34,790 --> 00:43:37,440
Nous ferions la même chose ici.

528
00:43:37,440 --> 00:43:40,340
Et maintenant, nous l'avons divisé en deux moitiés à nouveau.

529
00:43:40,340 --> 00:43:51,080
Et nous en avons 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Voilà donc notre scénario de base.

531
00:43:53,170 --> 00:44:00,540
Une fois les tableaux sont de taille 1, puis nous nous arrêtons avec la scission en deux moitiés.

532
00:44:00,540 --> 00:44:03,190
>> Maintenant, que faisons-nous avec ça?

533
00:44:03,190 --> 00:44:15,730
Nous finissons ce sera aussi le décomposer en 8, 23, 42, et 108.

534
00:44:15,730 --> 00:44:24,000
Alors, maintenant que nous sommes à ce point, maintenant la deuxième étape de tri par fusion est tout simplement la fusion de paires sur les listes.

535
00:44:24,000 --> 00:44:27,610
Donc, nous voulons fusionner celles-ci. Il suffit d'appeler fusionner.

536
00:44:27,610 --> 00:44:31,410
Nous savons fusion sera de retour ceux-ci dans l'ordre.

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

538
00:44:33,920 --> 00:44:41,440
Maintenant, nous voulons fusionner ceux-ci, et qui retournera une liste avec ceux de l'ordre de tri,

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

540
00:44:44,160 --> 00:44:57,380
Nous fusionnons ceux - Je ne peux pas écrire - 8, 23 et 42, 108.

541
00:44:57,380 --> 00:45:02,890
Nous avons donc paires fusionnées fois.

542
00:45:02,890 --> 00:45:05,140
Maintenant que nous venons de fusionner à nouveau.

543
00:45:05,140 --> 00:45:10,130
Notez que chacune de ces listes est triée par lui-même,

544
00:45:10,130 --> 00:45:15,220
et alors nous pouvons simplement fusionner ces listes pour obtenir une liste de taille 4 qui est triée

545
00:45:15,220 --> 00:45:19,990
et de fusionner ces deux listes pour obtenir une liste de taille 4 qui est trié.

546
00:45:19,990 --> 00:45:25,710
Et enfin, nous pouvons fusionner ces deux listes de taille 4 pour obtenir une liste de taille 8 qui est trié.

547
00:45:25,710 --> 00:45:34,030
Donc, pour voir que c'est l'ensemble n log n, nous avons déjà vu que la fusion est linéaire,

548
00:45:34,030 --> 00:45:40,390
alors quand nous avons affaire à fusionner ceux-ci, si semblable au coût global de la fusion

549
00:45:40,390 --> 00:45:43,410
pour ces deux listes est à seulement 2 parce que -

550
00:45:43,410 --> 00:45:49,610
Ou bien, c'est O de n, mais n ici est juste ces 2 éléments, il est donc 2.

551
00:45:49,610 --> 00:45:52,850
Et ces 2 sera 2 et ces 2 sera 2 et ces 2 sera 2,

552
00:45:52,850 --> 00:45:58,820
donc sur l'ensemble des fusions que nous devons faire, nous finissons par faire n.

553
00:45:58,820 --> 00:46:03,210
Comme 2 + 2 + 2 + 2 est 8, qui est n,

554
00:46:03,210 --> 00:46:08,060
de sorte que le coût de la fusion dans cette série est n.

555
00:46:08,060 --> 00:46:10,810
Et puis la même chose ici.

556
00:46:10,810 --> 00:46:16,980
Nous allons fusionner ces 2, alors ces 2 et individuellement cette fusion aura quatre opérations,

557
00:46:16,980 --> 00:46:23,610
Cette fusion aura quatre opérations, mais encore une fois, entre tous ceux-ci,

558
00:46:23,610 --> 00:46:29,030
nous finissent par se confondre n choses ensemble, et si cette étape a n.

559
00:46:29,030 --> 00:46:33,670
Ainsi, chaque niveau a n éléments étant fusionnées.

560
00:46:33,670 --> 00:46:36,110
>> Et combien de niveaux sont-ils?

561
00:46:36,110 --> 00:46:40,160
A chaque niveau, notre gamme augmente de taille 2.

562
00:46:40,160 --> 00:46:44,590
Voici nos tableaux sont de taille 1, ici ils sont de taille 2, ici ils sont de taille 4,

563
00:46:44,590 --> 00:46:46,470
et enfin, ils sont de taille 8.

564
00:46:46,470 --> 00:46:56,450
Donc, puisqu'il est doublé, il va y avoir un total de log n de ces niveaux.

565
00:46:56,450 --> 00:47:02,090
Donc, avec log n niveaux, chaque niveau de l'individu en prenant n l'ensemble des opérations,

566
00:47:02,090 --> 00:47:05,720
nous obtenons un algorithme log n n.

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

568
00:47:08,940 --> 00:47:13,320
Les gens ont déjà fait des progrès sur la façon de mettre en œuvre?

569
00:47:13,320 --> 00:47:18,260
Quelqu'un est-il déjà dans un état où je peux tirer vers le haut leur code?

570
00:47:20,320 --> 00:47:22,260
Je peux vous donner une minute.

571
00:47:24,770 --> 00:47:27,470
Celui-ci va être plus long.

572
00:47:27,470 --> 00:47:28,730
Je recommande fortement récurrentes -

573
00:47:28,730 --> 00:47:30,510
Vous n'avez pas à faire la récursivité pour fusion

574
00:47:30,510 --> 00:47:33,750
parce que faire la récursivité pour de fusion, vous allez devoir passer un tas de différentes tailles.

575
00:47:33,750 --> 00:47:37,150
Vous pouvez, mais c'est ennuyeux.

576
00:47:37,150 --> 00:47:43,720
Mais la récursivité pour le tri lui-même est assez facile.

577
00:47:43,720 --> 00:47:49,190
Vous avez juste littéralement appeler un tri sur la moitié gauche, en quelque sorte sur la moitié droite. D'accord.

578
00:47:51,770 --> 00:47:54,860
Quelqu'un at-il quelque chose que je peux tirer vers le haut encore?

579
00:47:54,860 --> 00:47:57,540
Ou bien je vais vous donner une minute.

580
00:47:58,210 --> 00:47:59,900
D'accord.

581
00:47:59,900 --> 00:48:02,970
Quelqu'un at-il quelque chose que nous pouvons travailler avec?

582
00:48:05,450 --> 00:48:09,680
Ou bien nous allons travailler avec cette puis développez partir de là.

583
00:48:09,680 --> 00:48:14,050
>> Quelqu'un at-il plus que ce que je peux tirer vers le haut?

584
00:48:14,050 --> 00:48:17,770
[L'élève] Ouais. Vous pouvez tirer vers le haut le mien. Tous droits >>.

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

586
00:48:22,170 --> 00:48:25,280
[L'élève] Il y avait beaucoup de conditions. >> Oh, mince. Pouvez-vous -

587
00:48:25,280 --> 00:48:28,110
[Étudiants] je dois le sauver. Ouais >>.

588
00:48:32,420 --> 00:48:35,730
Donc, nous avons fait la fusion séparément.

589
00:48:35,730 --> 00:48:38,570
Oh, mais ce n'est pas si mal que ça.

590
00:48:39,790 --> 00:48:41,650
D'accord.

591
00:48:41,650 --> 00:48:47,080
Alors tri est lui-même juste appeler mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Expliquez-nous ce mergeSortHelp fait.

593
00:48:49,530 --> 00:48:55,700
[L'élève] MergeSortHelp assez fait bien les deux étapes principales,

594
00:48:55,700 --> 00:49:01,270
qui consiste à trier chaque moitié de la matrice, puis à fusionner les deux.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Bon, alors donnez-moi une seconde.

596
00:49:10,850 --> 00:49:13,210
Je pense que c'est - >> [l'élève] J'ai besoin de -

597
00:49:17,100 --> 00:49:19,400
Ouais. Il me manque quelque chose.

598
00:49:19,400 --> 00:49:23,100
En fusion, je me rends compte que j'ai besoin de créer un nouveau tableau

599
00:49:23,100 --> 00:49:26,530
parce que je ne pouvais pas le faire à la place. Oui >>. Vous ne pouvez pas. Corrigez.

600
00:49:26,530 --> 00:49:28,170
[L'élève] Donc je crée un nouveau tableau.

601
00:49:28,170 --> 00:49:31,510
J'ai oublié à la fin de fusionner pour re-changer.

602
00:49:31,510 --> 00:49:34,490
D'accord. Nous avons besoin d'un nouveau tableau.

603
00:49:34,490 --> 00:49:41,000
Dans tri par fusion, ce qui est presque toujours le cas.

604
00:49:41,000 --> 00:49:44,340
Une partie du coût d'un meilleur algorithme en temps-sage

605
00:49:44,340 --> 00:49:47,310
est presque toujours besoin d'utiliser la mémoire un peu plus.

606
00:49:47,310 --> 00:49:51,570
Donc, ici, peu importe comment vous faites le tri par fusion,

607
00:49:51,570 --> 00:49:54,780
Vous ne manquerait pas besoin d'utiliser de la mémoire supplémentaire.

608
00:49:54,780 --> 00:49:58,240
Il ou elle a créé un nouveau tableau.

609
00:49:58,240 --> 00:50:03,400
Et puis vous dire à la fin nous avons juste besoin de copier nouveau tableau dans le tableau original.

610
00:50:03,400 --> 00:50:04,830
[L'élève] Je crois, oui.

611
00:50:04,830 --> 00:50:08,210
Je ne sais pas si cela fonctionne en termes de comptage par référence ou autre -

612
00:50:08,210 --> 00:50:11,650
Ouais, ça va marcher. >> [L'élève] D'accord.

613
00:50:20,620 --> 00:50:24,480
Avez-vous essayé d'exécuter ce? >> [L'élève] Non, pas encore. Ok >>.

614
00:50:24,480 --> 00:50:28,880
Essayez de l'exécuter, et puis je vais en parler pendant une seconde.

615
00:50:28,880 --> 00:50:35,200
[L'élève] J'ai besoin d'avoir tous les prototypes de fonctions et tout, hein?

616
00:50:37,640 --> 00:50:40,840
Les prototypes de fonctions. Oh, tu veux dire comme - Oui.

617
00:50:40,840 --> 00:50:43,040
Trier appelle mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Donc, pour que sorte d'appeler mergeSortHelp, mergeSortHelp doivent soit avoir été définie

619
00:50:47,390 --> 00:50:56,370
avant de trier ou nous avons juste besoin du prototype. Il suffit de copier et coller cela.

620
00:50:56,370 --> 00:50:59,490
Et de même, mergeSortHelp appelle fusionner,

621
00:50:59,490 --> 00:51:03,830
mais la fusion n'a pas encore été défini, afin que nous puissions laisser savoir mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
que c'est ce qui va fusionner ressembler, et c'est tout.

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

624
00:51:22,770 --> 00:51:32,660
Nous avons un problème ici, où nous n'avons pas le cas de base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp est récursive, de sorte que toute fonction récursive

626
00:51:38,110 --> 00:51:42,610
va avoir besoin d'une sorte de scénario de base pour savoir quand s'arrêter lui-même récursivement appel.

627
00:51:42,610 --> 00:51:45,590
Quel est notre scénario de base vont être ici? Ouais.

628
00:51:45,590 --> 00:51:49,110
[L'élève] Si la taille est de 1? >> [Bowden] Oui.

629
00:51:49,110 --> 00:51:56,220
Donc, comme nous l'avons vu là, nous nous sommes arrêtés tableaux de fractionnement

630
00:51:56,220 --> 00:52:01,850
une fois arrivés dans des tableaux de taille 1, qui, inévitablement, sont eux-mêmes classés.

631
00:52:01,850 --> 00:52:09,530
Donc, si la taille est égale à 1, nous savons que le tableau est déjà trié,

632
00:52:09,530 --> 00:52:12,970
afin que nous puissions simplement retourner.

633
00:52:12,970 --> 00:52:16,880
>> Notez que c'est vide, donc nous ne retournons pas quelque chose de particulier, nous venons de revenir.

634
00:52:16,880 --> 00:52:19,580
D'accord. Donc, c'est notre scénario de base.

635
00:52:19,580 --> 00:52:27,440
Je suppose que notre scénario de base pourraient également être s'il nous arrive d'être fusionner un tableau de taille 0,

636
00:52:27,440 --> 00:52:30,030
nous voulons probablement s'arrêter à un moment donné,

637
00:52:30,030 --> 00:52:33,610
si nous pouvons simplement dire taille inférieure à 2 ou inférieur ou égal à 1

638
00:52:33,610 --> 00:52:37,150
de telle sorte que cela fonctionne pour n'importe quel ensemble maintenant.

639
00:52:37,150 --> 00:52:38,870
D'accord.

640
00:52:38,870 --> 00:52:42,740
Donc, c'est notre scénario de base.

641
00:52:42,740 --> 00:52:45,950
Maintenant, voulez-vous nous expliquer de fusion?

642
00:52:45,950 --> 00:52:49,140
Qu'est-ce que tous ces arrêts?

643
00:52:49,140 --> 00:52:54,480
Là-haut, nous faisons juste la même idée, le -

644
00:52:56,970 --> 00:53:02,470
[L'élève] J'ai besoin d'être en passant la taille de tous les appels mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
J'ai ajouté la taille comme un primaire supplémentaire et il n'est pas là, comme la taille / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, la taille / 2, taille / 2. >> [Élève] Oui, et aussi dans la fonction ci-dessus ainsi.

647
00:53:16,210 --> 00:53:21,320
[Bowden] ici? >> [L'élève] Juste taille. >> [Bowden] Oh. Taille, la taille? >> [L'élève] Ouais.

648
00:53:21,320 --> 00:53:23,010
[Bowden] D'accord.

649
00:53:23,010 --> 00:53:26,580
Laissez-moi réfléchir une seconde.

650
00:53:26,580 --> 00:53:28,780
Ne nous nous heurtons à un problème?

651
00:53:28,780 --> 00:53:33,690
Nous sommes toujours à traiter la gauche de 0. >> [L'élève] No.

652
00:53:33,690 --> 00:53:36,340
C'est faux aussi. Désolé. Il devrait être mis en marche. Ouais.

653
00:53:36,340 --> 00:53:39,230
[Bowden] D'accord. J'aime mieux cela.

654
00:53:39,230 --> 00:53:43,880
Et à la fin. D'accord.

655
00:53:43,880 --> 00:53:47,200
Alors maintenant, voulez-vous nous expliquer de fusion? >> [L'élève] D'accord.

656
00:53:47,200 --> 00:53:52,150
Je suis juste marcher à travers ce nouveau tableau que j'ai créé.

657
00:53:52,150 --> 00:53:57,420
Sa taille est la taille de la portion de tableau que nous voulons être triés

658
00:53:57,420 --> 00:54:03,460
et essayer de trouver l'élément que je devrais mettre dans l'étape nouvelle matrice.

659
00:54:03,460 --> 00:54:10,140
Donc, pour ce faire, d'abord je vérifie si la moitié gauche du tableau continue d'avoir des éléments, pas plus,

660
00:54:10,140 --> 00:54:14,260
et si elle n'est pas, alors vous allez vers le bas pour que l'état de chose, qui dit simplement

661
00:54:14,260 --> 00:54:20,180
ok, il doit être dans le tableau de droite, et nous allons le mettre dans l'index actuel de newArray.

662
00:54:20,180 --> 00:54:27,620
>> Et puis sinon, je vérifie si le côté droit du tableau est également terminé,

663
00:54:27,620 --> 00:54:30,630
dans ce cas, je viens de mettre dans la gauche.

664
00:54:30,630 --> 00:54:34,180
C'est peut-être pas vraiment nécessaire. Je ne suis pas sûr.

665
00:54:34,180 --> 00:54:40,970
Mais de toute façon, les deux autres chèques qui des deux sont plus petits dans la gauche ou la droite.

666
00:54:40,970 --> 00:54:49,770
Et aussi, dans chaque cas, je suis d'incrémentation selon placeholder je incrémenter.

667
00:54:49,770 --> 00:54:52,040
[Bowden] D'accord.

668
00:54:52,040 --> 00:54:53,840
Ça a l'air bon.

669
00:54:53,840 --> 00:54:58,800
Quelqu'un at-il des commentaires ou des préoccupations ou des questions?

670
00:55:00,660 --> 00:55:07,720
Ainsi, les quatre cas que nous devons mettre les choses en étant juste - ou il ressemble à cinq -

671
00:55:07,720 --> 00:55:13,100
mais nous devons nous demander si le tableau gauche n'a plus de choses que nous devons fusionner,

672
00:55:13,100 --> 00:55:16,390
si le tableau à droite est à court de choses que nous devons fusionner -

673
00:55:16,390 --> 00:55:18,400
Je signale à rien.

674
00:55:18,400 --> 00:55:21,730
Donc, si le tableau de gauche a plus de choses ou le tableau de droite est à court de choses.

675
00:55:21,730 --> 00:55:24,320
Ce sont deux cas.

676
00:55:24,320 --> 00:55:30,920
Nous devons aussi le cas trivial de savoir si la chose gauche est inférieure à la bonne chose.

677
00:55:30,920 --> 00:55:33,910
Ensuite, nous voulons choisir la bonne chose à gauche.

678
00:55:33,910 --> 00:55:37,630
Ce sont les cas.

679
00:55:37,630 --> 00:55:40,990
Donc, ce fut bien, alors c'est tout.

680
00:55:40,990 --> 00:55:46,760
Tableau gauche. Il est 1, 2, 3. D'accord. Alors oui, ce sont les quatre choses que nous pourrions vouloir faire.

681
00:55:50,350 --> 00:55:54,510
Et nous n'irons pas plus une solution itérative.

682
00:55:54,510 --> 00:55:55,980
Je ne recommanderais pas -

683
00:55:55,980 --> 00:56:03,070
Le tri par fusion est un exemple d'une fonction qui est à la fois non récursive,

684
00:56:03,070 --> 00:56:07,040
il n'est pas facile de le faire récursive,

685
00:56:07,040 --> 00:56:13,450
mais aussi ce n'est pas très facile de le faire itératif.

686
00:56:13,450 --> 00:56:16,910
C'est très facile.

687
00:56:16,910 --> 00:56:19,170
Cette mise en œuvre du tri par fusion,

688
00:56:19,170 --> 00:56:22,140
fusionner, peu importe ce que vous faites, vous allez construire de fusion.

689
00:56:22,140 --> 00:56:29,170
>> Ainsi, le tri par fusion construite au-dessus de fusion est récursivement juste ces trois lignes.

690
00:56:29,170 --> 00:56:34,700
Itérative, il est plus ennuyeux et plus difficile à penser.

691
00:56:34,700 --> 00:56:41,860
Mais remarquez que ce n'est pas récursive terminale car mergeSortHelp - quand il appelle lui-même -

692
00:56:41,860 --> 00:56:46,590
il a encore besoin de faire des choses après ce retour de l'appel récursif.

693
00:56:46,590 --> 00:56:50,830
Donc ce frame de pile doit continuer d'exister même après l'appel de cette.

694
00:56:50,830 --> 00:56:54,170
Et puis, quand vous appelez cela, le cadre de pile doit continuer d'exister

695
00:56:54,170 --> 00:56:57,780
parce que même après cet appel, nous avons encore besoin de fusionner.

696
00:56:57,780 --> 00:57:01,920
Et il n'est pas triviale pour faire de cette récursive.

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

698
00:57:08,300 --> 00:57:09,860
Très bien.

699
00:57:09,860 --> 00:57:13,400
Pour en revenir à trier - oh, il ya deux choses que je veux montrer. D'accord.

700
00:57:13,400 --> 00:57:17,840
Pour en revenir à trier, nous allons le faire rapidement.

701
00:57:17,840 --> 00:57:21,030
Ou chercher. Trier? Trier. Ouais.

702
00:57:21,030 --> 00:57:22,730
Pour en revenir aux débuts de la sorte.

703
00:57:22,730 --> 00:57:29,870
Nous voulons créer un algorithme qui trie le tableau en utilisant un algorithme

704
00:57:29,870 --> 00:57:33,660
en O de n.

705
00:57:33,660 --> 00:57:40,860
Alors, comment est-ce possible? Quelqu'un at-il un quelconque -

706
00:57:40,860 --> 00:57:44,300
J'ai fait allusion auparavant à -

707
00:57:44,300 --> 00:57:48,300
Si nous sommes sur le point de s'améliorer à partir de n log n O n,

708
00:57:48,300 --> 00:57:51,450
nous avons amélioré notre algorithme en temps-sage,

709
00:57:51,450 --> 00:57:55,250
ce qui signifie que ce que nous allons avoir besoin de faire pour rattraper ça?

710
00:57:55,250 --> 00:57:59,520
[L'élève] Space. Ouais >>. Nous allons utiliser plus d'espace.

711
00:57:59,520 --> 00:58:04,490
Et même pas un peu plus d'espace, c'est l'espace exponentiellement plus.

712
00:58:04,490 --> 00:58:14,320
Je pense donc que ce type d'algorithme est quelque chose de pseudo, polynôme pseudo -

713
00:58:14,320 --> 00:58:18,980
pseudo - je ne me souviens pas. Pseudo quelque chose.

714
00:58:18,980 --> 00:58:22,210
Mais c'est parce que nous avons besoin d'utiliser autant d'espace

715
00:58:22,210 --> 00:58:28,610
que cela est réalisable, mais pas réaliste.

716
00:58:28,610 --> 00:58:31,220
>> Et comment pouvons-nous y parvenir?

717
00:58:31,220 --> 00:58:36,810
Nous pouvons y parvenir si nous garantir que tel ou tel élément dans le tableau

718
00:58:36,810 --> 00:58:39,600
est inférieur à une certaine taille.

719
00:58:42,070 --> 00:58:44,500
Alors disons simplement que la taille est 200,

720
00:58:44,500 --> 00:58:48,130
n'importe quel élément dans un tableau ci-dessous est la taille 200.

721
00:58:48,130 --> 00:58:51,080
Et c'est effectivement très réaliste.

722
00:58:51,080 --> 00:58:58,660
Vous pouvez très facilement avoir un tableau que vous savez tout ce qu'il

723
00:58:58,660 --> 00:59:00,570
sera inférieur à un certain nombre.

724
00:59:00,570 --> 00:59:07,400
Comme si vous avez un certain vecteur absolument massive ou quelque chose

725
00:59:07,400 --> 00:59:11,810
mais vous savez que tout va être comprise entre 0 et 5,

726
00:59:11,810 --> 00:59:14,790
alors ça va être beaucoup plus rapide de faire cela.

727
00:59:14,790 --> 00:59:17,930
Et la borne sur l'un des éléments est 5,

728
00:59:17,930 --> 00:59:21,980
si cette limite, c'est la quantité de mémoire que vous allez utiliser.

729
00:59:21,980 --> 00:59:26,300
Ainsi, la limite est de 200.

730
00:59:26,300 --> 00:59:32,960
En théorie, il ya toujours un bond depuis un entier ne peut atteindre 4 milliards d'euros,

731
00:59:32,960 --> 00:59:40,600
mais ce n'est pas réaliste car alors nous serions en utilisant l'espace

732
00:59:40,600 --> 00:59:44,400
de l'ordre de 4 milliards d'euros. Donc, c'est irréaliste.

733
00:59:44,400 --> 00:59:47,060
Mais ici, nous allons dire que notre limite est de 200.

734
00:59:47,060 --> 00:59:59,570
L'astuce pour le faire en temps O de n est nous faisons un autre tableau appelé compte de la taille BOUND.

735
00:59:59,570 --> 01:00:10,470
Donc en fait, il s'agit d'un raccourci pour - En fait, je ne sais pas si cela Clang.

736
01:00:11,150 --> 01:00:15,330
Mais dans GCC à tout le moins - je Clang en supposant qu'il fait trop -

737
01:00:15,330 --> 01:00:18,180
ce sera juste initialiser le tableau entier soit 0.

738
01:00:18,180 --> 01:00:25,320
Donc, si je ne veux pas le faire, alors je pourrais le faire séparément for (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Alors maintenant, tout est initialisé à 0.

741
01:00:35,260 --> 01:00:39,570
Je itérer sur mon tableau,

742
01:00:39,570 --> 01:00:51,920
et ce que je fais, c'est que je compte le nombre de chaque - Descendons ici.

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

744
01:00:55,480 --> 01:01:00,010
Qu'est-ce que je compte est le nombre d'occurrences de chacun de ces éléments.

745
01:01:00,010 --> 01:01:03,470
Nous allons effectivement ajouter un couple de plus ici avec quelques répétitions.

746
01:01:03,470 --> 01:01:11,070
Ainsi, la valeur que nous avons ici, la valeur de ce qui se passe à tableau [i].

747
01:01:11,070 --> 01:01:14,850
Donc val pourrait être 4 ou 8 ou autre.

748
01:01:14,850 --> 01:01:18,870
Et maintenant, je compte combien de valeur que j'ai vu,

749
01:01:18,870 --> 01:01:21,230
donc compte [val] + +;

750
01:01:21,230 --> 01:01:29,430
Après cela, les comptages va ressembler à 0001.

751
01:01:29,430 --> 01:01:42,190
Faisons compte [val] - LIÉ + 1.

752
01:01:42,190 --> 01:01:48,230
>> Maintenant, c'est juste pour tenir compte du fait que nous sommes en partant de 0.

753
01:01:48,230 --> 01:01:50,850
Donc, si 200 est va être notre plus grand nombre,

754
01:01:50,850 --> 01:01:54,720
puis de 0 à 200 est de 201 choses.

755
01:01:54,720 --> 01:02:01,540
Donc, compte, ça va ressembler 00001 parce que nous avons un 4.

756
01:02:01,540 --> 01:02:10,210
Ensuite, nous aurons 0001 où nous aurons un 1 dans l'index de comptage 8.

757
01:02:10,210 --> 01:02:14,560
Nous allons avoir un 2 dans l'index 23 de comptage.

758
01:02:14,560 --> 01:02:17,630
Nous aurons un 2 dans l'indice 42e chef d'accusation.

759
01:02:17,630 --> 01:02:21,670
Ainsi, nous pouvons utiliser count.

760
01:02:34,270 --> 01:02:44,920
Donc num_of_item = compte [i].

761
01:02:44,920 --> 01:02:52,540
Et si num_of_item est de 2, cela signifie que nous voulons insérer 2 du nombre i

762
01:02:52,540 --> 01:02:55,290
dans notre tableau trié.

763
01:02:55,290 --> 01:03:02,000
Nous avons donc besoin de garder une trace de combien nous sommes loin dans le tableau.

764
01:03:02,000 --> 01:03:05,470
= Indice So 0.

765
01:03:05,470 --> 01:03:09,910
Array - Je vais l'écrire.

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

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

768
01:03:28,580 --> 01:03:32,490
Est-ce que je veux? Je pense que c'est ce que je veux.

769
01:03:35,100 --> 01:03:38,290
Oui, ça a l'air bon. D'accord.

770
01:03:38,290 --> 01:03:43,050
Donc tout le monde ne comprends quel est le but de mon tableau compte, c'est?

771
01:03:43,050 --> 01:03:48,140
On compte le nombre d'occurrences de chacun de ces nombres.

772
01:03:48,140 --> 01:03:51,780
Ensuite, je suis itération sur ce tableau compte,

773
01:03:51,780 --> 01:03:57,190
et la position i dans le tableau compte

774
01:03:57,190 --> 01:04:01,930
est le nombre de i est qui doit apparaître dans mon tableau trié.

775
01:04:01,930 --> 01:04:06,840
C'est pourquoi comptaient 4 va être 1

776
01:04:06,840 --> 01:04:11,840
et les décomptes de 8 va être de 1, les dénombrements de 23 va être 2.

777
01:04:11,840 --> 01:04:16,900
C'est comme ça que beaucoup d'entre eux que je veux insérer dans mon tableau trié.

778
01:04:16,900 --> 01:04:19,200
Alors je viens de le faire.

779
01:04:19,200 --> 01:04:28,960
Je suis en insérant num_of_item i est dans mon tableau trié.

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

781
01:04:32,460 --> 01:04:43,100
Et de nouveau, c'est le temps linéaire, puisque nous sommes juste itération sur cette fois,

782
01:04:43,100 --> 01:04:47,470
mais c'est aussi linéaire dans ce nombre se trouve être,

783
01:04:47,470 --> 01:04:50,730
et il dépend fortement de ce que votre limite est.

784
01:04:50,730 --> 01:04:53,290
D'un bond de 200, ce n'est pas si mal que ça.

785
01:04:53,290 --> 01:04:58,330
Si votre borne se passe à 10.000, alors c'est un peu moins bien,

786
01:04:58,330 --> 01:05:01,360
mais si votre limite va être de 4 milliards de dollars, c'est complètement irréaliste

787
01:05:01,360 --> 01:05:07,720
et ce tableau va devoir être de taille 4 milliards de dollars, ce qui est irréaliste.

788
01:05:07,720 --> 01:05:10,860
Donc, c'est tout. Des questions?

789
01:05:10,860 --> 01:05:13,270
[Réponse de l'élève inaudible] >> OK.

790
01:05:13,270 --> 01:05:15,710
J'ai réalisé une autre chose quand nous allions passer.

791
01:05:17,980 --> 01:05:23,720
Je pense que le problème était de Lucas et probablement tous un seul que nous avons vu.

792
01:05:23,720 --> 01:05:26,330
J'ai complètement oublié.

793
01:05:26,330 --> 01:05:31,040
La seule chose que je voulais dire, c'est que lorsque vous avez affaire à des choses comme les indices,

794
01:05:31,040 --> 01:05:38,320
vous n'avez jamais vraiment voir quand vous écrivez une boucle for,

795
01:05:38,320 --> 01:05:41,120
mais techniquement, chaque fois que vous faites affaire avec ces indices,

796
01:05:41,120 --> 01:05:45,950
vous devriez quasiment toujours faire face à des entiers non signés.

797
01:05:45,950 --> 01:05:53,850
La raison à cela est lorsque vous faites affaire avec des entiers signés,

798
01:05:53,850 --> 01:05:56,090
donc si vous avez 2 entiers signés et que vous les additionnez

799
01:05:56,090 --> 01:06:00,640
et ils finissent trop grand, alors vous vous retrouvez avec un nombre négatif.

800
01:06:00,640 --> 01:06:03,410
C'est donc ce que débordement d'entier est.

801
01:06:03,410 --> 01:06:10,500
>> Si j'ajoute 2 milliards et 1 milliard, je me retrouve avec solde négatif de 1 milliard de dollars.

802
01:06:10,500 --> 01:06:15,480
Voilà comment travailler sur des ordinateurs entiers.

803
01:06:15,480 --> 01:06:17,510
Donc, le problème avec l'aide -

804
01:06:17,510 --> 01:06:23,500
C'est très bien, sauf si bas arrive à 2 milliards de dollars et se place à 1 milliard,

805
01:06:23,500 --> 01:06:27,120
alors cela va être négatif 1 milliard et puis nous allons diviser ce par 2

806
01:06:27,120 --> 01:06:29,730
et finissent par un solde négatif de 500 millions.

807
01:06:29,730 --> 01:06:33,760
Donc, c'est un problème que si vous arrive d'être à la recherche à travers un réseau

808
01:06:33,760 --> 01:06:38,070
des milliards de choses.

809
01:06:38,070 --> 01:06:44,050
Mais si + bas arrive à débordement, alors c'est un problème.

810
01:06:44,050 --> 01:06:47,750
Dès que nous les rendre non signé, puis 2 milliards de dollars plus 1 milliard 3 milliards.

811
01:06:47,750 --> 01:06:51,960
3 milliards divisé par 2 est de 1,5 milliards d'euros.

812
01:06:51,960 --> 01:06:55,670
Donc, dès qu'ils sont signés, tout est parfait.

813
01:06:55,670 --> 01:06:59,900
Et donc c'est aussi un problème lorsque vous écrivez votre pour les boucles,

814
01:06:59,900 --> 01:07:03,940
et en fait, il n'est probablement automatiquement.

815
01:07:09,130 --> 01:07:12,330
Il fait juste hurler à vous.

816
01:07:12,330 --> 01:07:21,610
Donc, si ce nombre est trop grand pour être juste un entier, mais il pourrait tenir dans un entier non signé,

817
01:07:21,610 --> 01:07:24,970
il crie après vous, c'est pour ça que vous n'avez jamais vraiment courir sur la question.

818
01:07:29,150 --> 01:07:34,820
Vous pouvez voir que l'indice ne va jamais être négatif,

819
01:07:34,820 --> 01:07:39,220
et donc quand vous itérer sur un tableau,

820
01:07:39,220 --> 01:07:43,970
vous pouvez presque toujours dire unsigned int i, mais vous n'avez pas vraiment besoin.

821
01:07:43,970 --> 01:07:47,110
Les choses vont assez bien pour travailler tout aussi bien.

822
01:07:48,740 --> 01:07:50,090
D'accord. [Chuchote] Quelle heure est-il?

823
01:07:50,090 --> 01:07:54,020
La dernière chose que je voulais montrer - et je vais le faire très rapidement.

824
01:07:54,020 --> 01:08:03,190
Vous savez comment nous avons # define afin que nous puissions # define MAX comme 5 ou quelque chose?

825
01:08:03,190 --> 01:08:05,940
Il ne faut pas faire MAX. # Define LIÉ que 200. C'est ce que nous avons fait avant.

826
01:08:05,940 --> 01:08:10,380
Qui définit une constante, qui va tout simplement être copié et collé

827
01:08:10,380 --> 01:08:13,010
partout où nous nous trouvons pour écrire BOUND.

828
01:08:13,010 --> 01:08:18,189
>> Nous pouvons donc faire plus avec # define.

829
01:08:18,189 --> 01:08:21,170
Nous pouvons définir des fonctions #.

830
01:08:21,170 --> 01:08:23,410
Ils ne sont pas vraiment des fonctions, mais nous les appellerons fonctions.

831
01:08:23,410 --> 01:08:36,000
Un exemple serait quelque chose comme MAX (x, y) est défini par (x <y y: x). D'accord.

832
01:08:36,000 --> 01:08:40,660
Donc, vous devriez être habitué à la syntaxe opérateur ternaire,

833
01:08:40,660 --> 01:08:49,029
mais il est inférieur à y x? Retour y, else return x.

834
01:08:49,029 --> 01:08:54,390
Donc vous pouvez voir que vous pouvez faire cette fonction distincte,

835
01:08:54,390 --> 01:09:01,399
et la fonction pourrait être comme bool MAX prend 2 arguments, retourner ce.

836
01:09:01,399 --> 01:09:08,340
C'est l'un des plus communs que je vois fait comme ça. Nous les appelons les macros.

837
01:09:08,340 --> 01:09:11,790
Il s'agit d'une macro.

838
01:09:11,790 --> 01:09:15,859
C'est juste la syntaxe pour cela.

839
01:09:15,859 --> 01:09:18,740
Vous pouvez écrire une macro pour faire ce que vous voulez.

840
01:09:18,740 --> 01:09:22,649
Vous voyez souvent des macros de débogage printfs et d'autres choses.

841
01:09:22,649 --> 01:09:29,410
Ainsi, un type de printf, il ya des constantes spéciales en C comme Souligné Ligne de soulignement,

842
01:09:29,410 --> 01:09:31,710
2 underscores LINE soulignent,

843
01:09:31,710 --> 01:09:37,550
et il ya aussi, je pense que 2 souligne FUNC. C'est peut-être cela. Quelque chose comme ça.

844
01:09:37,550 --> 01:09:40,880
Ces choses seront remplacés par le nom de la fonction

845
01:09:40,880 --> 01:09:42,930
ou le numéro de la ligne que vous êtes sur.

846
01:09:42,930 --> 01:09:48,630
Souvent, vous écrivez printfs débogage qui ici-bas je pourrais alors simplement écrire

847
01:09:48,630 --> 01:09:54,260
DEBUG et il affichera le numéro de la ligne et de la fonction que je me trouve être en

848
01:09:54,260 --> 01:09:57,020
qu'il a rencontré cette déclaration DEBUG.

849
01:09:57,020 --> 01:09:59,550
Et vous pouvez également imprimer d'autres choses.

850
01:09:59,550 --> 01:10:05,990
Donc, une chose que vous devriez regarder dehors pour est, s'il m'arrive de # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
quelque chose comme 2 * 2 * y et x.

852
01:10:11,380 --> 01:10:14,310
Donc, pour une raison quelconque, vous arrive de faire beaucoup de choses.

853
01:10:14,310 --> 01:10:16,650
Donc faire une macro.

854
01:10:16,650 --> 01:10:18,680
Il s'agit en fait rompu.

855
01:10:18,680 --> 01:10:23,050
Je voudrais l'appeler par faire quelque chose comme DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Que faudrait-il de retour?

857
01:10:28,840 --> 01:10:30,580
[L'élève] 12.

858
01:10:30,580 --> 01:10:34,800
Oui, 12 doit être retourné, et 12 est renvoyé.

859
01:10:34,800 --> 01:10:43,350
3 sera remplacé par x, 6 sera remplacé par y, et nous retournons 2 * 6, qui est de 12.

860
01:10:43,350 --> 01:10:47,710
Maintenant, qu'en est-il cela? Que faut-il de retour?

861
01:10:47,710 --> 01:10:50,330
[L'élève] 14. Idéalement >>, 14.

862
01:10:50,330 --> 01:10:55,290
Le problème est que la façon dont hachage définit le travail, n'oubliez pas qu'il s'agit d'une copie littérale et coller

863
01:10:55,290 --> 01:11:00,160
d'à peu près tout, donc ce que cela va être interprété comme

864
01:11:00,160 --> 01:11:11,270
est de 3 moins de 1 + 6, 2 fois 1 plus 6, 2 fois 3.

865
01:11:11,270 --> 01:11:19,780
>> Donc, pour cette raison, vous devrez presque toujours envelopper tout entre parenthèses.

866
01:11:22,180 --> 01:11:25,050
Toute variable vous envelopper presque toujours entre parenthèses.

867
01:11:25,050 --> 01:11:29,570
Il ya des cas où vous n'avez pas à, comme je sais que je n'ai pas besoin de le faire ici

868
01:11:29,570 --> 01:11:32,110
parce que moins est à peu près toujours juste aller au travail,

869
01:11:32,110 --> 01:11:34,330
bien que cela pourrait même ne pas être vrai.

870
01:11:34,330 --> 01:11:41,870
S'il ya quelque chose de ridicule comme DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
alors que va se faire remplacée par 3 est égal à moins de 1 est égal à 2,

872
01:11:49,760 --> 01:11:53,460
et oui, alors ça va faire 3 inférieur à 1, est-ce que 2 égal,

873
01:11:53,460 --> 01:11:55,620
ce qui n'est pas ce que nous voulons.

874
01:11:55,620 --> 01:12:00,730
Ainsi, afin d'éviter tout problème de priorité des opérateurs,

875
01:12:00,730 --> 01:12:02,870
toujours envelopper entre parenthèses.

876
01:12:03,290 --> 01:12:07,700
D'accord. Et c'est tout, 5:30.

877
01:12:08,140 --> 01:12:12,470
Si vous avez des questions sur le jeu de processeurs, laissez-nous savoir.

878
01:12:12,470 --> 01:12:18,010
Il doit être un plaisir, et l'édition pirate est aussi beaucoup plus réaliste

879
01:12:18,010 --> 01:12:22,980
que l'édition pirate de l'an dernier, et nous espérons que beaucoup d'entre vous l'essayer.

880
01:12:22,980 --> 01:12:26,460
L'année dernière a été très accablante.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]