1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [セクション3  - より快適]

2
00:00:02,570 --> 00:00:05,070
[ロブボーデン - ハーバード大学]

3
00:00:05,070 --> 00:00:07,310
>> [これはCS50です。 -  CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> だから最初の質問は、6888184されています。

5
00:00:12,700 --> 00:00:17,480
GDBは、より具体的には、プログラムを "デバッグ"することができますが、、何それはあなたが何ができるのですか？

6
00:00:17,480 --> 00:00:22,590
私はそのいずれかをお答えしましょう​​、私は、まさに予想のか分からない

7
00:00:22,590 --> 00:00:27,910
ので、私はそれの線に沿って何かがあなたがステップバイステップでできますそれを推測している

8
00:00:27,910 --> 00:00:31,540
それと対話すると、プログラムの中を歩く、変数の変更は、これらすべてのことを行う - 

9
00:00:31,540 --> 00:00:34,270
基本的には完全にプログラムの実行を制御

10
00:00:34,270 --> 00:00:38,410
プログラムの実行の任意の部分を点検してください。

11
00:00:38,410 --> 00:00:43,030
ので、これらの機能を使用すると、物事をデバッグできます。

12
00:00:43,030 --> 00:00:44,830
オーケー。

13
00:00:44,830 --> 00:00:50,520
なぜ二分探索は、配列がソートされている必要がありますか？

14
00:00:50,520 --> 00:00:53,360
誰がそんなことに答えることを望んでいる？

15
00:00:56,120 --> 00:01:00,070
[学生]配列がソートされていないなら、それは動作しませんので。 >>うん。 [笑い]

16
00:01:00,070 --> 00:01:04,910
配列がソートされていないなら、それはそれを半分に分割することは不可能だ

17
00:01:04,910 --> 00:01:07,850
その左に、すべてが小さく、右側にあるものをすべて知っている

18
00:01:07,850 --> 00:01:10,490
中間値よりも大きくなっています。

19
00:01:10,490 --> 00:01:12,790
だからそれは、ソートする必要があります。

20
00:01:12,790 --> 00:01:14,170
オーケー。

21
00:01:14,170 --> 00:01:17,570
なぜ乗nのOでバブルソートは何ですか？

22
00:01:17,570 --> 00:01:23,230
誰でも、最初のバブルソートとは何かの非常に迅速な高レベルの概要を提供したいのですか？

23
00:01:25,950 --> 00:01:33,020
[学生]あなたは基本的に各要素を通過して、最初のいくつかの要素を確認してください。

24
00:01:33,020 --> 00:01:37,150
彼らはあなたがそれらを交換するところから出ている場合は、次のいくつかの要素などを確認してください。

25
00:01:37,150 --> 00:01:40,770
あなたが最後に到達したとき、あなたは、最大の要素を末尾に配置されていることを知っている

26
00:01:40,770 --> 00:01:42,750
ので、あなたは、1つが次にあなたが通過し続けることを無視する

27
00:01:42,750 --> 00:01:48,490
そのたびにあなたは何も変更しなくなるまで、1小さい要素をチェックする必要があります。 >>うん。

28
00:01:48,490 --> 00:01:58,470
あなたはその側に配列を反転した場合ので、上下だと、ため、これは、バブルソートと呼ばれる垂直

29
00:01:58,470 --> 00:02:03,100
次に大きな値は底に沈んでしまうと小さな値topへバブルアップします。

30
00:02:03,100 --> 00:02:05,210
それは、その名前を得た方法です。

31
00:02:05,210 --> 00:02:08,220
そして、ええ、あなただけを通過します。

32
00:02:08,220 --> 00:02:11,190
あなたは、大きい方の値を交換し、アレイを介し続ける

33
00:02:11,190 --> 00:02:14,040
底に最大値を取得します。

34
00:02:14,040 --> 00:02:17,500
>> なぜそれがnのOの二乗ですか？

35
00:02:18,690 --> 00:02:24,620
まず、誰もがそれがnのO乗だからこそ言いたいのですか？

36
00:02:24,620 --> 00:02:28,760
[学生]を実行するたびにそれがn倍になったので。

37
00:02:28,760 --> 00:02:32,100
あなただけがすべての方法ダウン最大の要素を撮影したことを確認することができ、

38
00:02:32,100 --> 00:02:35,230
その後、多くの要素として処理することを繰り返す必要があります。 >>うん。

39
00:02:35,230 --> 00:02:41,800
だからビッグOは、どのような意味ビッグオメガ手段何を念頭に置いてください。

40
00:02:41,800 --> 00:02:50,560
ビッグOは、それが実際に実行することができますどの程度遅いの上限のようなものです。

41
00:02:50,560 --> 00:02:58,990
だから乗nのそれはOを言うことによって、それはnのOではないか、そうでなければ、実行することができるだろう

42
00:02:58,990 --> 00:03:02,640
線形時間で、それはn乗のOです

43
00:03:02,640 --> 00:03:06,390
それは、n乗のOに囲まれているからです。

44
00:03:06,390 --> 00:03:12,300
それは乗n個のOで囲まれている場合、それをn乗しても囲まれている。

45
00:03:12,300 --> 00:03:20,280
だからそれは、n乗であり、絶対的な最悪の場合はNの2乗よりも良い行うことはできません、

46
00:03:20,280 --> 00:03:22,830
それはそれは乗n個のOである理由です。

47
00:03:22,830 --> 00:03:31,200
だから、それはNの2乗であることが出てくる方法で若干の数学を見て

48
00:03:31,200 --> 00:03:40,530
私たちは私たちのリストに5つのものを持っている場合、我々は潜在的に行う必要がある可能性がどのように多くのスワップ初めて

49
00:03:40,530 --> 00:03:47,170
これを取得するためには？ただ、実際にしてみましょう - 

50
00:03:47,170 --> 00:03:52,040
どのように多くのスワップ我々は、配列をバブルソートの最初の実行時に行う必要がありますするつもりですか？

51
00:03:52,040 --> 00:03:53,540
【学生】n  -  1。 >>うん。

52
00:03:53,540 --> 00:03:58,340
>> 1から5の要素がある場合は、nを作るために必要になるだろう。

53
00:03:58,340 --> 00:04:01,100
それから二つ目にどのように多くのスワップ我々は行う必要がありますするつもりですか？

54
00:04:01,100 --> 00:04:03,440
【学生】n  -  2。 >>うん。

55
00:04:03,440 --> 00:04:11,640
そして第三は、nであることを行っている -  3、その後の便宜のために、私は最後の二つを書きます

56
00:04:11,640 --> 00:04:15,270
その後、我々は2スワップ、1スワップを作るために必要になるだろう。

57
00:04:15,270 --> 00:04:19,899
私は最後の1、または実際に起こる必要があるかもしれませんと思います。

58
00:04:19,899 --> 00:04:22,820
それはスワップのですか？知りません。

59
00:04:22,820 --> 00:04:26,490
したがって、これらはスワップまたはあなたが作らなければ少なくとも比較の合計金額です。

60
00:04:26,490 --> 00:04:29,910
あなたは交換しない場合でも、値を比較する必要があります。

61
00:04:29,910 --> 00:04:33,910
配列を使用して、最初の実行で1比較 - だから、nが存在する。

62
00:04:33,910 --> 00:04:42,050
あなたがこれらの事を再配置した場合、実際に6物事作るので物事がうまく積み重ねていきましょう、

63
00:04:42,050 --> 00:04:44,790
そして私は、2、1〜3をやる。

64
00:04:44,790 --> 00:04:49,910
だから、これらの金額を整理すると、私たちが作るどのように多くの比較が見たい

65
00:04:49,910 --> 00:04:52,700
アルゴリズム全体インチ

66
00:04:52,700 --> 00:04:56,550
だから我々はここで、これらの人をダウンさせた場合、

67
00:04:56,550 --> 00:05:07,470
その後、我々はまだそこにあったが、多くの比較をサミングしている。

68
00:05:07,470 --> 00:05:13,280
しかし、我々はこれらを合計し、我々はこれらを合計し、我々はこれらを合計した場合、

69
00:05:13,280 --> 00:05:18,130
それはまだ同じ問題です。私達はちょうどそれらの特定のグループを合計します。

70
00:05:18,130 --> 00:05:22,400
>> だから今我々は3 nのを合計している。それはちょうどn個の3ではありません。

71
00:05:22,400 --> 00:05:27,650
それは常にn / 2 nのものになるだろう。

72
00:05:27,650 --> 00:05:29,430
そこでここでは、6を持って起こる。

73
00:05:29,430 --> 00:05:34,830
我々は10の事柄を持っていたなら、私たちは物事の5つの異なるペアは、このグループ化を行うことができます

74
00:05:34,830 --> 00:05:37,180
とN + N + N + N + Nで終わる。

75
00:05:37,180 --> 00:05:45,840
それで、あなたは常にn / 2 nのを取得するつもりだので、この私たちはnの二乗/ 2にそれを書き留めます。

76
00:05:45,840 --> 00:05:48,890
そしてそれが入ってくるように起こるの半分の要因、言っても

77
00:05:48,890 --> 00:05:54,190
アレイ上の各反復を通じて、私たちが1未満と比較しているという事実のために

78
00:05:54,190 --> 00:05:58,040
その結果、我々は2の上を取得する方法ですが、それはまだNの2乗です。

79
00:05:58,040 --> 00:06:01,650
我々は半分の一定の係数を気にしないでください。

80
00:06:01,650 --> 00:06:07,760
このようなビッグOのものの多くは、数学のこのソートを行うだけの種類に依存しているので、

81
00:06:07,760 --> 00:06:12,260
算術和と幾何学的なシリーズものをやって、

82
00:06:12,260 --> 00:06:17,750
しかし、この過程で、それらのほとんどは非常に簡単です。

83
00:06:17,750 --> 00:06:19,290
オーケー。

84
00:06:19,290 --> 00:06:24,430
なぜnのオメガで挿入ソートは何ですか？オメガは何を意味するのか？

85
00:06:24,430 --> 00:06:27,730
[一度に話す二人の学生 - 不明朗] >>うん。

86
00:06:27,730 --> 00:06:30,630
オメガは、下限として考えることができます。

87
00:06:30,630 --> 00:06:36,550
>> だからあなたの挿入ソートのアルゴリズムがどのように効率的に関係なく、

88
00:06:36,550 --> 00:06:41,810
かかわらずに渡されたリストの、それは常に、少なくともn物事を比較する必要がある

89
00:06:41,810 --> 00:06:44,620
またはそれはnの事を反復するために持っています。

90
00:06:44,620 --> 00:06:47,280
これはなぜですか？

91
00:06:47,280 --> 00:06:51,190
[学生]ため、リストが既にソートされていれば、最初の反復を通じ

92
00:06:51,190 --> 00:06:54,080
あなただけの、非常に最初の要素が最小であることを保証することができます

93
00:06:54,080 --> 00:06:56,490
そして2回目の反復では、あなたは、最初の2つがあることを保証できます

94
00:06:56,490 --> 00:07:00,010
あなたは、リストの残りの部分がソートされていることを知らないので。 >>うん。

95
00:07:00,010 --> 00:07:08,910
あなたが完全にソートされたリストを渡した場合、非常に少なくとも、あなたは、すべての要素の上に行かなければならない

96
00:07:08,910 --> 00:07:12,180
何も周りに移動する必要がないことを確認します。

97
00:07:12,180 --> 00:07:14,720
だからリスト上を通過すると、ああ、これはすでに、ソートされていると言って

98
00:07:14,720 --> 00:07:18,240
あなたは、各要素を確認するまで、あなたがそれをソートの知っていることは不可能だ

99
00:07:18,240 --> 00:07:20,660
彼らはソート順になっていることを確認します。

100
00:07:20,660 --> 00:07:25,290
だから、挿入ソートの下界はnのオメガです。

101
00:07:25,290 --> 00:07:28,210
マージソートの実行時間は最悪のケースは、何ですか

102
00:07:28,210 --> 00:07:31,390
最悪の場合、再び大きなOであること？

103
00:07:31,390 --> 00:07:37,660
だから、最悪のシナリオでは、マージソートはどのように動作しますか？

104
00:07:42,170 --> 00:07:43,690
[学生] Nログn。 >>うん。

105
00:07:43,690 --> 00:07:49,990
最速の一般的なソートアルゴリズムは、nログnです。あなたがうまくやることはできません。

106
00:07:51,930 --> 00:07:55,130
>> そこに特殊なケースがあり、我々は今日、時間があれば - しかし、我々はおそらくwon't  - 

107
00:07:55,130 --> 00:07:59,330
我々は、nログnよりも優れていますかを見ることができました。

108
00:07:59,330 --> 00:08:04,050
しかし、一般的なケースでは、nログnよりも良い行うことはできません。

109
00:08:04,050 --> 00:08:09,680
とマージソートではnログnですこのコースのために知っておくべき一つであることを起こる。

110
00:08:09,680 --> 00:08:13,260
そして私たちは、実際には、今日実装されます。

111
00:08:13,260 --> 00:08:18,070
そして最後に、3つ以下の文章では、どのように選択ソートの動作しますか？

112
00:08:18,070 --> 00:08:20,370
誰かが答えたくない、と私はあなたの文章を数えます

113
00:08:20,370 --> 00:08:22,390
なぜならあなたは3を超えた場合 - 

114
00:08:25,530 --> 00:08:28,330
誰もが選択ソートを覚えていますか？

115
00:08:31,280 --> 00:08:37,809
選択ソートは、名前だけで覚えていることは通常は非常に簡単です。

116
00:08:37,809 --> 00:08:45,350
あなただけの配列を繰り返し処理し、最大値であるか、最小のものは何でも見つける - 

117
00:08:45,350 --> 00:08:47,290
あなたはインチ選別している任意の順序

118
00:08:47,290 --> 00:08:50,750
それでは、私たちは最小から最大に選別しているとしましょう​​。

119
00:08:50,750 --> 00:08:55,250
あなたは、最小の要素が何であっても探して、配列を反復

120
00:08:55,250 --> 00:08:59,750
それを選択してから、ちょうど最初の場所にあるもの、それを交換します。

121
00:08:59,750 --> 00:09:04,090
そして、配列の上2番目のパスに、再び最小の要素を探します

122
00:09:04,090 --> 00:09:07,490
それを選択し、次に2番目の位置にあるものでそれを交換します。

123
00:09:07,490 --> 00:09:10,650
だから我々はちょうどピッキングと最小値を選択している

124
00:09:10,650 --> 00:09:16,050
それがソートされるまで、アレイの前面に挿入する。

125
00:09:19,210 --> 00:09:21,560
その上で質問がありますか？

126
00:09:21,560 --> 00:09:25,710
>> これらは、必然的にあなたがpsetを提出している際に記入して、フォームに表示されます。

127
00:09:29,010 --> 00:09:32,360
それらは基本的にはそれらへの回答です。

128
00:09:32,360 --> 00:09:34,230
わかりましたので、今の問題をコーディング。

129
00:09:34,230 --> 00:09:40,140
私はすでに、電子メールを介して送信される - 誰もがその電子メールを取得できませんでしたか？オーケー。

130
00:09:40,140 --> 00:09:46,630
私はすでに、我々が使ってしようとしている電子メールを介して空間を送出

131
00:09:46,630 --> 00:09:52,120
あなたが私の名前をクリックした場合と - ので、私は一番下になるつもりだと思う

132
00:09:52,120 --> 00:09:57,170
後方rのために - しかし、あなたは私の名前をクリックした場合、2つのリビジョンが表示されます。

133
00:09:57,170 --> 00:10:02,650
リビジョン1は、私はすでにスペースにコードをコピー＆ペーストしようとしている

134
00:10:02,650 --> 00:10:06,900
検索の事のためには、実装する必要があるとしている。

135
00:10:06,900 --> 00:10:10,540
とリビジョン2は、我々はその後実装ソートものになるでしょう。

136
00:10:10,540 --> 00:10:15,770
だからあなたは私のリビジョン1をクリックして、そこから作業することができます。

137
00:10:17,350 --> 00:10:22,060
そして今、我々は二分探索を実装したい。

138
00:10:22,060 --> 00:10:26,470
>> 誰もがちょうど擬似コードハイレベルな説明を与えたくない

139
00:10:26,470 --> 00:10:31,440
我々は、検索のために行う必要があるとしている何の？うん。

140
00:10:31,440 --> 00:10:36,170
[学生]あなただけの配列の中間を取ると、あなたが探しているものかどうかを確認

141
00:10:36,170 --> 00:10:38,650
それよりも小さいか、それ以上です。

142
00:10:38,650 --> 00:10:41,080
そして、それはより少ないなら、あなたは、より少ないです前半に移動

143
00:10:41,080 --> 00:10:44,750
それはより多くのだなら、あなたはさらに半分に行くと、あなたは一つのことだけを取得するまで繰り返すこと。

144
00:10:44,750 --> 00:10:46,570
[ボーデン]うん。

145
00:10:46,570 --> 00:10:51,320
当社の数字の配列が既にソートされていることに注意してください、

146
00:10:51,320 --> 00:10:57,190
そして私たちはそれを活用することができ、我々が最初にチェックすることができたことを意味し、

147
00:10:57,190 --> 00:11:00,390
さて、私は50番を探しています。

148
00:11:00,390 --> 00:11:03,720
だから私は、真ん中に入ることができます。

149
00:11:03,720 --> 00:11:07,380
真ん中のは、それが物事の数が偶数のときに定義するのは難しいです

150
00:11:07,380 --> 00:11:10,820
しかしレッツはちょうど私達が常に真ん中に切り捨てるつもりだという。

151
00:11:10,820 --> 00:11:14,420
そこでここでは、8のものを持っているので、真ん中は16となります。

152
00:11:14,420 --> 00:11:17,330
私は50を探していますので、50は16より大きい。

153
00:11:17,330 --> 00:11:21,310
だから今、私は基本的に、これらの要素のように私の配列を扱うことができます。

154
00:11:21,310 --> 00:11:23,450
私は上の16からすべてのものを捨てる​​ことができます。

155
00:11:23,450 --> 00:11:27,440
今私の配列はちょうどこれらの4つの要素である、と私は繰り返す。

156
00:11:27,440 --> 00:11:31,910
それでは私は42になるだろうされ、再び真ん中を見つけたい。

157
00:11:31,910 --> 00:11:34,730
42は、50歳未満であるので、私はこれらの2つの要素を捨てることができます。

158
00:11:34,730 --> 00:11:36,890
これは私の残りの配列です。

159
00:11:36,890 --> 00:11:38,430
私は再び真ん中を見つけるつもりです。

160
00:11:38,430 --> 00:11:42,100
私はいつも左に物事を捨てていたので、私は、50が悪い例だったことを推測

161
00:11:42,100 --> 00:11:48,280
しかし同じメジャーで、私が何かを探していた場合

162
00:11:48,280 --> 00:11:52,100
そしてそれは、私が現在見ている要素より小さいです

163
00:11:52,100 --> 00:11:55,080
その後、私は右にすべてを捨てるつもりです。

164
00:11:55,080 --> 00:11:58,150
だから今我々はそれを実装する必要があります。

165
00:11:58,150 --> 00:12:02,310
私達はサイズを渡す必要があることに注意してください。

166
00:12:02,310 --> 00:12:06,730
我々はまた、ハードコードのサイズに必要することはできません。

167
00:12:06,730 --> 00:12:11,640
我々は取り払うのであれば＃defineを - 

168
00:12:19,630 --> 00:12:21,430
オーケー。

169
00:12:21,430 --> 00:12:27,180
どうすればきれいに数字の配列のサイズは現在あるものを見つけ出すことができますか？

170
00:12:27,180 --> 00:12:30,950
>> numbers配列内の要素数ですか？

171
00:12:30,950 --> 00:12:33,630
[学生]数字、括弧、。長さは？

172
00:12:33,630 --> 00:12:36,600
[ボーデンは] Cに存在していないこと

173
00:12:36,600 --> 00:12:38,580
必要があります長さ。

174
00:12:38,580 --> 00:12:42,010
配列はプロパティを持っていないので、配列のないlengthプロパティはありません

175
00:12:42,010 --> 00:12:45,650
それはちょうどそれがであることを起こるあなたがしかし、長い与える。

176
00:12:48,180 --> 00:12:51,620
[学生]それが持っているどのくらいのメモリを参照し、どのくらいで割る -  >>うん。

177
00:12:51,620 --> 00:12:55,810
だから、どのように我々はそれが持っているどのくらいのメモリを参照してくださいすることができますか？ >> [学生]はsizeof。 >>うん、sizeof演算。

178
00:12:55,810 --> 00:13:01,680
sizeofが数値配列のサイズを返すために起こっている子です。

179
00:13:01,680 --> 00:13:10,060
としかし多くの整数になるだろう、ということがよく整数のサイズがあります

180
00:13:10,060 --> 00:13:14,050
それはそれが実際に取っているどのくらいのメモリだから。

181
00:13:14,050 --> 00:13:17,630
だから私は、配列内の多くのことをしたい場合は、

182
00:13:17,630 --> 00:13:20,560
それから私は、整数の大きさによって分割したいつもりです。

183
00:13:22,820 --> 00:13:26,010
オーケー。だから私はここにサイズを渡すことができます。

184
00:13:26,010 --> 00:13:29,430
なぜ私はすべてでサイズを渡す必要がありますか？

185
00:13:29,430 --> 00:13:38,570
なぜ私はここまでできないintサイズ=はsizeof（干し草の山）/ sizeof（int）を？

186
00:13:38,570 --> 00:13:41,490
なぜこれが動作しませんか？

187
00:13:41,490 --> 00:13:44,470
[学生]それはグローバル変数ではありません。

188
00:13:44,470 --> 00:13:51,540
[ボーデン] Haystackが存在し、我々は干し草の山のように数字で渡している

189
00:13:51,540 --> 00:13:54,700
これが来て何の伏線のようなものです。うん。

190
00:13:54,700 --> 00:14:00,170
[学生] Haystackはちょうどそれへの参照であるので、その参照がどのように大きな返します。

191
00:14:00,170 --> 00:14:02,150
うん。

192
00:14:02,150 --> 00:14:09,000
私はあなたが本当に、まだ右のスタックを見てきた講演の中で疑う？

193
00:14:09,000 --> 00:14:11,270
我々はそれについて話をした。

194
00:14:11,270 --> 00:14:16,090
だからスタックは、あなたのすべての変数が格納しようとしているところです。

195
00:14:16,090 --> 00:14:19,960
>> ローカル変数に割り当てられている任意のメモリがスタックに起こっている、

196
00:14:19,960 --> 00:14:24,790
各関数は、スタック上に独自の空間を取得し、独自のスタックフレームは、それはと呼ばれるものです。

197
00:14:24,790 --> 00:14:31,590
だから主は、そのスタックフレームを持っており、内部のそれのは、この数字の配列が存在するために起こっている

198
00:14:31,590 --> 00:14:34,270
そしてそれは、サイズはsizeof（数字）のことになるだろう。

199
00:14:34,270 --> 00:14:38,180
それは、要素のサイズで割った数字の大きさを持っているために起こっている

200
00:14:38,180 --> 00:14:42,010
しかしメインのスタック·フレーム内のすべての住んでいるところだ。

201
00:14:42,010 --> 00:14:45,190
我々は検索を呼び出すと、検索は、独自のスタックフレームを取得

202
00:14:45,190 --> 00:14:48,840
そのすべてのローカル変数を格納するために、独自のスペース。

203
00:14:48,840 --> 00:14:56,420
しかし、これらの引数は - ので干し草の山は、この配列全体のコピーではありません。

204
00:14:56,420 --> 00:15:00,990
我々は、検索にコピーとして、配列全体を渡しません。

205
00:15:00,990 --> 00:15:04,030
それはちょうど、その配列への参照を渡します。

206
00:15:04,030 --> 00:15:11,470
だから検索は、この参照を介してこれらの番号にアクセスすることができます。

207
00:15:11,470 --> 00:15:17,100
それはまだ、主のスタック·フレームの中に住んで物事へのアクセスだ

208
00:15:17,100 --> 00:15:22,990
しかし、基本的に、我々はすぐにあるべきポインタ、、に到達したとき

209
00:15:22,990 --> 00:15:24,980
これは、ポインタが何であるかです。

210
00:15:24,980 --> 00:15:29,400
ポインタは、物事への参照であり、あなたは物事をアクセスするためにポインタを使用することができます

211
00:15:29,400 --> 00:15:32,030
他のものの 'スタックフレームでということです。

212
00:15:32,030 --> 00:15:37,660
数字は主にローカルであるにもかかわらずだから、私たちはまだ、このポインタを介してアクセスすることができます。

213
00:15:37,660 --> 00:15:41,770
しかし、それは単なるポインタだし、それはあくまでも参考ですので、

214
00:15:41,770 --> 00:15:45,040
はsizeof（干し草の山）はあくまでも参考自体のサイズを返します。

215
00:15:45,040 --> 00:15:47,950
それは、それが指しているもののサイズを返しません。

216
00:15:47,950 --> 00:15:51,110
それは数字の実際のサイズを返しません。

217
00:15:51,110 --> 00:15:55,660
我々はそれがしたいようなので、これが仕事に行くのではない。

218
00:15:55,660 --> 00:15:57,320
>> その上で質問がありますか？

219
00:15:57,320 --> 00:16:03,250
ポインタが来て数週間でかなり多くの血みどろの詳細にに消えてしまいます。

220
00:16:06,750 --> 00:16:13,740
そして、これは、なぜあなたが見ているものが多く、ほとんどの検索物事または後回しです

221
00:16:13,740 --> 00:16:16,990
彼らはほとんどすべて、配列の実際のサイズを取ることが必要になるだろう

222
00:16:16,990 --> 00:16:20,440
C言語であるため、我々は、配列のサイズが何であるか見当がつかない。

223
00:16:20,440 --> 00:16:22,720
手動でそれをインチ渡す必要があります

224
00:16:22,720 --> 00:16:27,190
あなただけの参照を渡しているので、手動で配列全体を渡すことができません

225
00:16:27,190 --> 00:16:30,390
そして、それは基準からサイズを取得することはできません。

226
00:16:30,390 --> 00:16:32,300
オーケー。

227
00:16:32,300 --> 00:16:38,160
だから今我々は前に説明したものを実装したいと思います。

228
00:16:38,160 --> 00:16:41,530
あなたは、分のためにそれに取り組むことができ

229
00:16:41,530 --> 00:16:45,250
そしてあなたはすべて完璧に100％の作業を得ることを心配する必要はありません。

230
00:16:45,250 --> 00:16:51,410
ちょうどあなたはそれが動作するはずですどのよ​​うに考えるかの半分の疑似コードを記述します。

231
00:16:52,000 --> 00:16:53,630
オーケー。

232
00:16:53,630 --> 00:16:56,350
まだ完全にこれを実行する必要はありません。

233
00:16:56,350 --> 00:17:02,380
しかし、誰もが、彼らがこれまで何をして、快適に感じない

234
00:17:02,380 --> 00:17:05,599
何かのように私たちは一緒に働くことができますか？

235
00:17:05,599 --> 00:17:09,690
誰もがボランティアをしたいのですか？または私はランダムに選択されます。

236
00:17:12,680 --> 00:17:18,599
それは右のいずれかの措置が、我々は作業状態に変更することができるものである必要はありません。

237
00:17:18,599 --> 00:17:20,720
[学生]確かに。オーケー。>>

238
00:17:20,720 --> 00:17:27,220
だからあなたは少し保存]アイコンをクリックして、リビジョンを保存することができます。

239
00:17:27,220 --> 00:17:29,950
あなたは正しい、Ramyaね？ >> [生徒]うん。 >> [ボーデン]オーケー。

240
00:17:29,950 --> 00:17:35,140
だから今私はあなたのリビジョンを表示することができ、誰もがリビジョンをプルアップすることができます。

241
00:17:35,140 --> 00:17:38,600
そしてここで我々は持っている - オーケー。

242
00:17:38,600 --> 00:17:43,160
だからRamyaは間違いなく有効なソリューションである再帰的なソリューション、一緒に行きました。

243
00:17:43,160 --> 00:17:44,970
あなたはこの問題を行うことができる2つの方法があります。

244
00:17:44,970 --> 00:17:48,060
あなたはどちらか、または反復して再帰的にそれを行うことができます。

245
00:17:48,060 --> 00:17:53,860
あなたは再帰的に行われることに遭遇するほとんどの問題も反復して行うことができます。

246
00:17:53,860 --> 00:17:58,510
そこでここでは、再帰的にそれをやった。

247
00:17:58,510 --> 00:18:03,730
>> 誰かがそれは、関数が再帰的に何を意味するかを定義したいのですか？

248
00:18:07,210 --> 00:18:08,920
[学生]は、機能を持っているときに自分自身を呼び出す

249
00:18:08,920 --> 00:18:13,470
それが真実であり、真実で出てくるまで、その後自分自身を呼び出す。 >>うん。

250
00:18:13,470 --> 00:18:17,680
再帰関数は、単に自分自身を呼び出す関数です。

251
00:18:17,680 --> 00:18:24,140
再帰関数が持っていなければならない3大きいものがあります。

252
00:18:24,140 --> 00:18:27,310
第一は明らかですが、それは自分自身を呼び出します。

253
00:18:27,310 --> 00:18:29,650
第二は、基本ケースである。

254
00:18:29,650 --> 00:18:33,390
だから、どこかの時点で関数は、自分自身の呼び出しを停止する必要があり、

255
00:18:33,390 --> 00:18:35,610
それは、ベースケースが何のためにあるのかだ。

256
00:18:35,610 --> 00:18:43,860
だからここに私たちは止めるべきであることを知っている、我々は我々の検索であきらめなければならない

257
00:18:43,860 --> 00:18:48,150
startがendと等しいときに - 私たちはそれが何を意味するのかをみることにします。

258
00:18:48,150 --> 00:18:52,130
しかし、最後に、再帰関数のための重要な最後の一つです：

259
00:18:52,130 --> 00:18:59,250
機能は何とかベースケースに近づく必要があります。

260
00:18:59,250 --> 00:19:04,140
2番目の再帰呼び出しを行ったとき、あなたが実際に何かを更新していない場合と同様に、

261
00:19:04,140 --> 00:19:07,880
あなたは文字通り、同じ引数を持つ関数を再度呼び出している場合、

262
00:19:07,880 --> 00:19:10,130
ず、グローバル変数は、変更されていませんか何かしている

263
00:19:10,130 --> 00:19:14,430
あなたは、ベースケースに到達することはありません、その場合は残念だインチ

264
00:19:14,430 --> 00:19:17,950
それは、無限再帰とスタックオーバーフローになります。

265
00:19:17,950 --> 00:19:24,330
しかし、ここで我々は、我々が開始+終了/ 2を更新しているので、UPDATEが行われていることを参照してください

266
00:19:24,330 --> 00:19:28,180
我々はここでstart引数を更新している、ここにend引数を更新しています。

267
00:19:28,180 --> 00:19:32,860
だから、すべての再帰呼び出しで我々は何かを更新しています。オーケー。

268
00:19:32,860 --> 00:19:38,110
あなたのソリューションを介して私たちを歩いてみませんか？ >>確かに。

269
00:19:38,110 --> 00:19:44,270
私はすべての時間が私は、この関数の呼び出しを行うようにSearchHelpを使用しています

270
00:19:44,270 --> 00:19:47,910
私は、配列内の探している場所の開始と終了を持っている

271
00:19:47,910 --> 00:19:49,380
どこで、私は配列を探しています。

272
00:19:49,380 --> 00:19:55,330
>> それがスタートです中央の要素、+エンド/ 2だと言っているのすべての段階で、

273
00:19:55,330 --> 00:19:58,850
それは我々が探しているものと同じですか？

274
00:19:58,850 --> 00:20:04,650
それがあるならば、我々はそれを発見した、と私は再帰のレベルを上に渡されると推測します。

275
00:20:04,650 --> 00:20:12,540
それは本当ではないならば、我々は、配列のその中間の値が大きすぎるかどうかをチェック

276
00:20:12,540 --> 00:20:19,320
その場合、我々は最初から真ん中のインデックスに行くことによって、配列の左半分を見てみましょう。

277
00:20:19,320 --> 00:20:22,710
そうでなければ、我々は終わりの半分を行う。

278
00:20:22,710 --> 00:20:24,740
[ボーデン]オーケー。

279
00:20:24,740 --> 00:20:27,730
それは良さそうです。

280
00:20:27,730 --> 00:20:36,640
わかりましたので、カップルの事、実際には、これは非常にハイレベルなものです

281
00:20:36,640 --> 00:20:41,270
あなたはこのコースのために知っておく必要は決してありませんが、それは真実であること。

282
00:20:41,270 --> 00:20:46,080
再帰関数は、常に彼らはひどい仕打ちだと聞いて

283
00:20:46,080 --> 00:20:51,160
あなたは再帰的に自分自身が何回も呼び出す場合は、スタックオーバーフローを得るため

284
00:20:51,160 --> 00:20:54,990
以来、私は前にも言ったように、すべての関数は独自のスタックフレームを取得します。

285
00:20:54,990 --> 00:20:59,500
だから、再帰関数の各呼び出しでは、独自のスタックフレームを取得します。

286
00:20:59,500 --> 00:21:04,140
あなたは千再帰呼び出しを行うのであれば、あなたは、千のスタックフレームを取得

287
00:21:04,140 --> 00:21:08,390
かつ迅速にあなたはあまりにも多くのスタックフレームと物事が壊れることは持って​​いることにつながる。

288
00:21:08,390 --> 00:21:13,480
再帰関数は、一般的に悪い理由だからです。

289
00:21:13,480 --> 00:21:19,370
しかし、再帰関数の素敵なサブセットは、末尾再帰関数が呼び出された

290
00:21:19,370 --> 00:21:26,120
これは、コンパイラがこれを気がつけば一つの例であることを起こる

291
00:21:26,120 --> 00:21:29,920
あなたはそれを-O2フラグを渡した場合はClangの中に - そしてそれは、私が考えなければならない

292
00:21:29,920 --> 00:21:33,250
それは、これは末尾再帰であることに気づくと物事が良いでしょう。

293
00:21:33,250 --> 00:21:40,050
>> それは、各再帰呼び出しのために何度も何度も同じスタック·フレームを再利用します。

294
00:21:40,050 --> 00:21:47,010
あなたが同じスタックフレームを使用しているので、それで、あなたは心配する必要はありません

295
00:21:47,010 --> 00:21:51,690
今までにあふれ、同時に、あなたが前に言ったように積み重ね、

296
00:21:51,690 --> 00:21:56,380
一度あなたがtrueを返す場合に、それはこれらのスタックフレームのすべてを返す必要があります

297
00:21:56,380 --> 00:22:01,740
とSearchHelpへ第十コールは第九に戻す必要があり、第八に返す必要があります。

298
00:22:01,740 --> 00:22:05,360
だから関数は末尾再帰しているときに発生する必要はありません。

299
00:22:05,360 --> 00:22:13,740
そしてそう何、この関数の尾を再帰的に繰り返すことsearchHelpに任意のコールのためにあることに気づくさ

300
00:22:13,740 --> 00:22:18,470
それは作っていることを再帰呼び出しでは、戻されるものです。

301
00:22:18,470 --> 00:22:25,290
だからSearchHelpへの最初の呼び出しでは、我々は、すぐに、falseを返す

302
00:22:25,290 --> 00:22:29,590
すぐにtrueを返すか、我々はSearchHelpに再帰呼び出しを行う

303
00:22:29,590 --> 00:22:33,810
私たちが返していると、その呼び出しが返されているものです。

304
00:22:33,810 --> 00:22:51,560
我々はint X = SearchHelp、リターン×* 2のような何かをしなかった場合、我々は、これを行うことができませんでした

305
00:22:51,560 --> 00:22:55,440
ちょうどいくつかのランダムな変化。

306
00:22:55,440 --> 00:23:01,470
>> だから今、このような再帰呼び出し、このint X = SearchHelp再帰呼び出し、

307
00:23:01,470 --> 00:23:05,740
それが実際に返す必要がないため、もはや末尾再帰ではない

308
00:23:05,740 --> 00:23:10,400
バック関数への前の呼び出しているので、以前のスタック·フレームへ

309
00:23:10,400 --> 00:23:13,040
その後、戻り値を使って何かを行うことができます。

310
00:23:13,040 --> 00:23:22,190
だから、これは末尾再帰ではありませんが、きれいに末尾再帰になる前に、我々は持っていたもの。うん。

311
00:23:22,190 --> 00:23:27,000
[学生]は二塁のケースは最初にチェックすべきではありません

312
00:23:27,000 --> 00:23:30,640
あなたはそれを引数を渡すような状況があるかもしれないので、

313
00:23:30,640 --> 00:23:35,770
あなたは=エンドを起動しましたが、彼らは針値です。

314
00:23:35,770 --> 00:23:47,310
端が針値です質問は、我々はその事件を実行することはできませんされました

315
00:23:47,310 --> 00:23:52,000
または=エンドを起動して、適切に、=エンドを起動

316
00:23:52,000 --> 00:23:59,480
そして実際に、まだその特定の値をチェックしていない

317
00:23:59,480 --> 00:24:03,910
その後スタート+エンド/ 2がちょうど同じ値になるだろう。

318
00:24:03,910 --> 00:24:07,890
しかし、我々はすでにfalseが返されてきたと我々は、実際に値をチェックすることはありません。

319
00:24:07,890 --> 00:24:14,240
サイズが0の場合はだからせめて、最初の呼び出しで、その場合は偽を返すようにしたい。

320
00:24:14,240 --> 00:24:17,710
大きさが1である場合しかし、その後スタートは、等しい終わりに行くされていません

321
00:24:17,710 --> 00:24:19,820
そして我々は、少なくとも1つの要素をチェックします。

322
00:24:19,820 --> 00:24:26,750
しかし、私はどこでスタート+エンド/ 2、私たちはケースに行きつくことができる点で、あなたは正しいと思う

323
00:24:26,750 --> 00:24:31,190
開始はスタート+エンド/ 2、と同じされて終わる

324
00:24:31,190 --> 00:24:35,350
しかし、我々は実際にその要素をチェックすることはありません。

325
00:24:35,350 --> 00:24:44,740
>> だから、我々が最初にチェックした場合と、中央の要素は、私たちが探している値であり、

326
00:24:44,740 --> 00:24:47,110
その後、我々はすぐにtrueを返すことができます。

327
00:24:47,110 --> 00:24:50,740
それらが等しいなら、他の場合には、継続しても意味がありません

328
00:24:50,740 --> 00:24:58,440
以来、私達はちょうど私達が単一要素の配列である場合に更新するつもりです。

329
00:24:58,440 --> 00:25:01,110
で、単一の要素は、私たちが探しているものではない場合は、

330
00:25:01,110 --> 00:25:03,530
その後、すべてが間違っている。うん。

331
00:25:03,530 --> 00:25:08,900
[学生]のものは、大きさが配列内の要素数より​​も実際に大きいことです

332
00:25:08,900 --> 00:25:13,070
既にオフセットがある -  >>だから意志サイズ - 

333
00:25:13,070 --> 00:25:19,380
[学生]配列のサイズが0だった場合、その後SearchHelpが実際に0の干し草の山を確認すると言う

334
00:25:19,380 --> 00:25:21,490
最初の呼び出しで。

335
00:25:21,490 --> 00:25:25,300
うん>>  - 配列のサイズが0であり、0になるように。

336
00:25:25,300 --> 00:25:30,750
その別のものがあります - それは良いかもしれません。のは、考えてみましょう。

337
00:25:30,750 --> 00:25:40,120
配列は10個の要素を持っていたし、我々はチェックするつもり真ん中はインデックス5であり、そうであれば

338
00:25:40,120 --> 00:25:45,700
ので、我々は5をチェックしているし、その値が小さいことを言うてみましょう。

339
00:25:45,700 --> 00:25:50,720
だから我々は5以降からすべてのものを投げている。

340
00:25:50,720 --> 00:25:54,030
だから、スタート+エンド/ 2私たちの新たなエンドになるだろう、

341
00:25:54,030 --> 00:25:57,450
そう、ええ、それは常に配列の終わりを越えて滞在する予定だ。

342
00:25:57,450 --> 00:26:03,570
それが偶数か奇数であった場合、それはそうだとするなら、私たちは、、と言う、4をチェックすることになります

343
00:26:03,570 --> 00:26:05,770
しかし我々はまだ捨てています - 

344
00:26:05,770 --> 00:26:13,500
そうそう、最後には、必ず実際の配列の末尾を超えてになるだろう。

345
00:26:13,500 --> 00:26:18,350
我々が焦点を当てているので、要素は、最後には、必ずその後一つになるだろう。

346
00:26:18,350 --> 00:26:24,270
スタートは今までに等しい終わりますかそうだとすれば、我々は、サイズが0の配列である。

347
00:26:24,270 --> 00:26:35,600
>> 私が考えていた他の事は我々が開始する開始を更新しています+エンド/ 2であり、

348
00:26:35,600 --> 00:26:44,020
どこスタート+エンド/ 2ので、これは、私がトラブルを抱えているのは、事実です

349
00:26:44,020 --> 00:26:46,820
我々がチェックしている要素です。

350
00:26:46,820 --> 00:26:58,150
Let 'sは、我々はこの10要素の配列を持っていたと言う。ものは何でも。

351
00:26:58,150 --> 00:27:03,250
だから、スタート+エンド/ 2この1のようなものになるだろう、

352
00:27:03,250 --> 00:27:07,060
そしてそれが価値ではない場合、我々は更新したいと言う。

353
00:27:07,060 --> 00:27:10,060
値が大きいので、我々は、配列のこの半分で見てみたい。

354
00:27:10,060 --> 00:27:15,910
だから我々はスタートを更新しているどのように、我々は現在、この要素になるようにスタートを更新しています。

355
00:27:15,910 --> 00:27:23,790
しかし、これはまだ動作する可能性があります、または非常に少なくとも、あなたはスタート+エンド/ 2 + 1を行うことができます。

356
00:27:23,790 --> 00:27:27,850
[学生]は、+エンドを起動する必要はありません[聞こえない] >>うん。

357
00:27:27,850 --> 00:27:33,240
我々はすでに、この要素をチェックし、それは我々が探しているものではないと知っている。

358
00:27:33,240 --> 00:27:36,800
だから我々は、この要素になるようにスタートを更新する必要はありません。

359
00:27:36,800 --> 00:27:39,560
私達はちょうどそれをスキップして、この要素になるように開始更新することができます。

360
00:27:39,560 --> 00:27:46,060
とケースはこれまで存在し、これが最後であったこと、としましょう​​、

361
00:27:46,060 --> 00:27:53,140
このなるので、次に起動すると、+エンドを起動/ 2はこれであろう、

362
00:27:53,140 --> 00:28:00,580
+エンドを起動 - ええ、私はそれが無限再帰で終わることができると思います。

363
00:28:00,580 --> 00:28:12,690
レッツは、それだけでサイズ2かサイズ1の配列の配列だと言う。私は、これがうまくいくと思う。

364
00:28:12,690 --> 00:28:19,490
だから現在、startは要素と終了がそれを超えて1であるということです。

365
00:28:19,490 --> 00:28:24,110
だから我々はチェックしようとしている要素は、この一つであり、

366
00:28:24,110 --> 00:28:29,400
その後、我々はスタートを更新するとき、我々は、0 +1 / 2であるとスタートを更新している

367
00:28:29,400 --> 00:28:33,160
これは、スタートがこの要素であるとの私達に戻って終わろうとしている。

368
00:28:33,160 --> 00:28:36,210
>> だから我々は何度も同じ要素をチェックしています。

369
00:28:36,210 --> 00:28:43,310
だから、これは、すべての再帰呼び出しは実際に何かを更新する必要がありそうです。

370
00:28:43,310 --> 00:28:48,370
だから我々は、大文字と小文字があるスタート+エンド/ + 1、あるいは2を実行する必要があります

371
00:28:48,370 --> 00:28:50,710
ここで我々は、実際にスタートを更新していない。

372
00:28:50,710 --> 00:28:53,820
誰もがそれを参照してください？

373
00:28:53,820 --> 00:28:56,310
オーケー。

374
00:28:56,310 --> 00:29:03,860
誰もがこの溶液またはそれ以上のコメントについての質問を持っていますか？

375
00:29:05,220 --> 00:29:10,280
オーケー。誰もが、我々はすべてを見ることができることを反復解法を持っていますか？

376
00:29:17,400 --> 00:29:20,940
我々はすべて再帰的にそれをしましたか？

377
00:29:20,940 --> 00:29:25,950
あるいはまた、私はあなたが彼女を開いた場合、その後、あなたの前のものをオーバーライドしているかもしれないと思います。

378
00:29:25,950 --> 00:29:28,810
それは自動的に保存しますか？私は肯定的ではない。

379
00:29:35,090 --> 00:29:39,130
誰もが反復していますか？

380
00:29:39,130 --> 00:29:42,430
私たちは一緒にそれを歩く場合はできません。

381
00:29:46,080 --> 00:29:48,100
考え方は同じであることを行っている。

382
00:30:00,260 --> 00:30:02,830
反復解法。

383
00:30:02,830 --> 00:30:07,140
私たちは基本的に同じ考え方をしたいとしている

384
00:30:07,140 --> 00:30:16,530
我々は、新しい配列の末尾のトラックと配列の新たなスタートをどこに置くか

385
00:30:16,530 --> 00:30:18,510
それは何度も何度もやる。

386
00:30:18,510 --> 00:30:22,430
そして、我々は開始と終了が今までのように交差を追跡しているものであれば、

387
00:30:22,430 --> 00:30:29,020
その後、我々はそれを見つけられなかったこと、そして私たちは、falseを返すことができます。

388
00:30:29,020 --> 00:30:37,540
だから私はそれをどのように行うのですか？誰も私をプルアップするための提案やコードをお持ちですか？

389
00:30:42,190 --> 00:30:47,450
[学生]は、whileループを行います。 >>うん。

390
00:30:47,450 --> 00:30:49,450
あなたは、ループを行いたいとしている。

391
00:30:49,450 --> 00:30:51,830
>> あなたは、私がプルアップ可能性のあるコードを持っているか、またはあなたは何を示唆しようとしていた？

392
00:30:51,830 --> 00:30:56,340
[学生]私はそう思います。 >>すべての権利。これは、物事が容易になります。あなたの名前は何でしたか？

393
00:30:56,340 --> 00:30:57,890
[学生]ルーカス。

394
00:31:00,140 --> 00:31:04,190
改訂1。オーケー。

395
00:31:04,190 --> 00:31:13,200
ローは、我々は前に開始すると呼ばれるものです。

396
00:31:13,200 --> 00:31:17,080
ここまでは前に、エンドと呼ばれるものとは限らないからです。

397
00:31:17,080 --> 00:31:22,750
実は、年末には、配列内になりました。それは、我々が考慮すべき要素です。

398
00:31:22,750 --> 00:31:26,890
非常に低いが0で、最大配列のサイズです -  1、

399
00:31:26,890 --> 00:31:34,780
そして今我々はループしている、と我々はチェックしている - 

400
00:31:34,780 --> 00:31:37,340
私はあなたがそれを通って歩くことができると思います。

401
00:31:37,340 --> 00:31:41,420
これを通じて、あなたの思考は何でしたか？あなたのコードを介して私たちを歩く。

402
00:31:41,420 --> 00:31:49,940
[学生]確かに。真ん中に干し草の山の値を見て、針と比較します。

403
00:31:49,940 --> 00:31:58,520
ああ、実際に、それは後方にする必要があります - それはあなたの針よりも大きいですので、もし、あなたがしたい。

404
00:31:58,520 --> 00:32:05,180
あなたは、右半分を捨てるするつもりだ、とそう、ええ、それは方法でなければなりません。

405
00:32:05,180 --> 00:32:08,830
[ボーデンは]だから、これは小さくなければなりません？あなたはそれを言っているのでしょうか？ >> [生徒]うん。

406
00:32:08,830 --> 00:32:10,390
[ボーデン]オーケー。もっと少なく。

407
00:32:10,390 --> 00:32:15,700
ですから、私たちが見ていることは我々が望むものよりも小さい場合、

408
00:32:15,700 --> 00:32:19,410
それから、ええ、私たちは、左半分を捨てたい

409
00:32:19,410 --> 00:32:22,210
これは、我々が検討しているすべてのものを更新していることを意味

410
00:32:22,210 --> 00:32:26,610
配列の右側に移動させることにより、低。

411
00:32:26,610 --> 00:32:30,130
これはよさそうだ。

412
00:32:30,130 --> 00:32:34,550
私は、それは我々が以前のものによると、同じ問題を持っていると思う

413
00:32:34,550 --> 00:32:49,760
低いが0で、最大1であれば、低+ / 2まで、再び同じことになるように設定するにはどこに向かっている。

414
00:32:49,760 --> 00:32:53,860
>> そして、それがそうではない場合であっても、それはまだ非常に少なくとも、より効率的です

415
00:32:53,860 --> 00:32:57,630
単に要素を捨てること私達はちょうど私達が間違っていることは知っているを見た。

416
00:32:57,630 --> 00:33:03,240
/ 2までの非常に低い+ 1  -  >> [学生]は、他の方法でなければなりません。

417
00:33:03,240 --> 00:33:05,900
[ボーデン]またはこれがなければなりません -  1、もう一つは+ 1である必要があります。

418
00:33:05,900 --> 00:33:09,580
[学生]と二重があるはず等号。 >> [ボーデン]うん。

419
00:33:09,580 --> 00:33:11,340
[学生]うん。

420
00:33:14,540 --> 00:33:15,910
オーケー。

421
00:33:15,910 --> 00:33:21,280
そして最後に、今、私たちはこの+1を持っていること -  1の事を、

422
00:33:21,280 --> 00:33:31,520
それは - それはないかもしれません - それは低いため、最大よりも大きい値になってしまうことがこれまで可能ですか？

423
00:33:35,710 --> 00:33:40,320
私は起こることができる唯一の​​方法だと思います - それは可能ですか？ >> [学生]私は知らない。

424
00:33:40,320 --> 00:33:45,220
しかし、それは切り捨て取得し、取得した場合、そのマイナスその後1  -  >>うん。

425
00:33:45,220 --> 00:33:47,480
[学生]それは多分めちゃくちゃになるだろう。

426
00:33:49,700 --> 00:33:53,940
私はそれだけのために良いはずだと思う

427
00:33:53,940 --> 00:33:58,800
それが低終わることのために、それらが等しくなければならないであろう、と思う。

428
00:33:58,800 --> 00:34:03,070
それらが等しい場合でも、我々は、で始まるにwhileループを行わなかったであろう

429
00:34:03,070 --> 00:34:06,670
そして我々は単に値を返したでしょう。だから私たちは今は良いだと思います。

430
00:34:06,670 --> 00:34:11,530
この問題は再帰なくなったにもかかわらず、ことに注意してください、

431
00:34:11,530 --> 00:34:17,400
私たちは、これがそう簡単に自分自身を貸すかを見ることができますどこにアイデアの同じ種類が適用されます。

432
00:34:17,400 --> 00:34:23,659
我々だけで、何度も繰り返しインデックスを更新しているという事実によって再帰的なソリューションへ

433
00:34:23,659 --> 00:34:29,960
我々は問題が小さく作っている、我々は、配列のサブセットに焦点を合わせている。

434
00:34:29,960 --> 00:34:40,860
[学生]低が0で、最大1である場合、それらは両方とも、0 + 1/2、0になるだろう

435
00:34:40,860 --> 00:34:44,429
その後1 + 1となる、1は次のようになります -  1。

436
00:34:47,000 --> 00:34:50,870
[学生]僕らはどこ平等をチェックしている？

437
00:34:50,870 --> 00:34:55,100
真ん中の1が実際に針の場合は好きですか？

438
00:34:55,100 --> 00:34:58,590
我々は現在、ことをやっていないのか？ああ！

439
00:35:00,610 --> 00:35:02,460
it's場合 - 

440
00:35:05,340 --> 00:35:13,740
はい。レッツは、最初の中間と言うので、私たちはここでダウンテストを行うだけではできません - 

441
00:35:13,740 --> 00:35:16,430
[学生]それは実際にバインドを捨てないようなものだ。

442
00:35:16,430 --> 00:35:20,220
あなたがバウンドを捨てる場合そこで、まず最初にまたは何でもそれをチェックする必要があります。

443
00:35:20,220 --> 00:35:23,350
ああ。うん。 >> [生徒]うん。

444
00:35:23,350 --> 00:35:29,650
だから今我々は、我々が現在見て1を捨てて、

445
00:35:29,650 --> 00:35:33,260
これは、我々は今も持っている必要があることを意味し

446
00:35:33,260 --> 00:35:44,810
（干し草の山[（低+上）/ 2] ==針）するなら、私たちは、trueを返すことができます。

447
00:35:44,810 --> 00:35:52,070
そして、私は誰置くかどうかだけなら、それは文字通り同じことを意味

448
00:35:52,070 --> 00:35:57,110
これは真実では戻ってきてしまうからです。

449
00:35:57,110 --> 00:36:01,450
もしそうなら私は他に置くことにしましょう​​が、それは問題ではありません。

450
00:36:01,450 --> 00:36:10,440
>> ので、他の、これは、この他に、これは私が行う一般的なものである場合

451
00:36:10,440 --> 00:36:14,340
どこでそれがすべてがここに良い場合であっても、

452
00:36:14,340 --> 00:36:22,780
ローのようにより大きくなることはありません、それはそれが本当だかどうかについての価値推論ではありません。

453
00:36:22,780 --> 00:36:28,010
ローがより小さいか等しい間、そうあなたにも言うかもしれません

454
00:36:28,010 --> 00:36:30,720
または低未満である間

455
00:36:30,720 --> 00:36:35,300
そう、彼らはこれまでと同等または低い場合を渡すことを起こる、

456
00:36:35,300 --> 00:36:40,130
その後、我々はこのループから抜け出すことができます。

457
00:36:41,410 --> 00:36:44,630
質問、懸念、コメント？

458
00:36:47,080 --> 00:36:49,270
オーケー。これはよさそうだ。

459
00:36:49,270 --> 00:36:52,230
今、私たちは、ソートをやってみたい。

460
00:36:52,230 --> 00:37:04,030
私たちは私の第二の改正に行けば、私たちは、これらの同じ番号を参照してください

461
00:37:04,030 --> 00:37:07,550
しかし、今、彼らは、ソートされた順番になりません。

462
00:37:07,550 --> 00:37:12,840
そして、我々は、nログnのOの任意のアルゴリズムを使用してソートを実装したいと思います。

463
00:37:12,840 --> 00:37:17,240
ですから、我々がここで実装する必要があり、どのアルゴリズムだと思いますか？ >> [生徒]マージソート。

464
00:37:17,240 --> 00:37:23,810
[ボーデン]うん。マージソートをするように、我々がやろうとしているのはO（n log n）である。

465
00:37:23,810 --> 00:37:26,680
そして問題は、かなり似ているために起こっている

466
00:37:26,680 --> 00:37:31,920
どこでそれが簡単に再帰的なソリューションに適しています。

467
00:37:31,920 --> 00:37:35,580
我々がしたい場合、我々はまた、反復解法思い付く

468
00:37:35,580 --> 00:37:42,540
しかし、再帰はここではより簡単になり、私たちは、再帰を行う必要があります。

469
00:37:45,120 --> 00:37:49,530
私は、我々が最初にマージソート順を追って説明します推測

470
00:37:49,530 --> 00:37:54,280
マージソートの美しい映像はすでにありますが。 [笑い]

471
00:37:54,280 --> 00:37:59,780
だからあるマージソート - 私はこの論文のあまりを無駄にしています。

472
00:37:59,780 --> 00:38:02,080
ああ、唯一の1左はそこだ。

473
00:38:02,080 --> 00:38:03,630
だからマージ。

474
00:38:08,190 --> 00:38:12,470
ああ、1、3、5。

475
00:38:26,090 --> 00:38:27,440
オーケー。

476
00:38:29,910 --> 00:38:33,460
マージ結合は、2つの別々の配列を取ります。

477
00:38:33,460 --> 00:38:36,780
個別にそれらの二つの配列がソートされます両方。

478
00:38:36,780 --> 00:38:40,970
したがって、この配列は、1、3、5は、ソートされています。この配列には、0、2、4、ソートされています。

479
00:38:40,970 --> 00:38:46,710
今何マージが行うべきこと自体がソートされている単一の配列にそれらを組み合わせることである。

480
00:38:46,710 --> 00:38:57,130
だから我々はその中に、これらの要素を持っているとしている大きさ6の配列をしたい

481
00:38:57,130 --> 00:38:59,390
ソートされた順序インチ

482
00:38:59,390 --> 00:39:03,390
>> それで我々はこれら2つの配列がソートされているという事実を活用することができます

483
00:39:03,390 --> 00:39:06,800
線形時間でこれを行うには、

484
00:39:06,800 --> 00:39:13,510
、この配列はサイズxであり、これはサイズyであれば線形時間の意味

485
00:39:13,510 --> 00:39:20,970
その後合計アルゴリズムはO（x + y）がなければなりません。オーケー。

486
00:39:20,970 --> 00:39:23,150
だから提案。

487
00:39:23,150 --> 00:39:26,030
[学生]は、我々は左から開始してもらえますか？

488
00:39:26,030 --> 00:39:30,150
だから、あなたがダウンして最初にして1 0を置くことにしましょう​​し、ここであなたは2にいる。

489
00:39:30,150 --> 00:39:33,320
だから、あなたが右に動いているタブを持っているようなものだ。 >> [ボーデン]うん。

490
00:39:33,320 --> 00:39:41,070
私達はちょうど一番左の要素に注目すると、これらの配列の両方のために。

491
00:39:41,070 --> 00:39:43,530
両方の配列がソートされているので、我々は知っているこれらの2つの要素

492
00:39:43,530 --> 00:39:46,920
どちらアレイ内の最小要素である。

493
00:39:46,920 --> 00:39:53,500
だから、それらの2つの要素の1が私たちのマージした配列内の最小の要素でなければならないことを意味します。

494
00:39:53,500 --> 00:39:58,190
それはちょうどので、最小、右今回で一つであることを起こる。

495
00:39:58,190 --> 00:40:02,580
0が1未満であるので、だから我々は、0を取る左に挿入し

496
00:40:02,580 --> 00:40:08,210
ので、0を取る我々の最初の位置にそれを挿入した後、これを更新する

497
00:40:08,210 --> 00:40:12,070
現在、最初の要素に焦点を当てる。

498
00:40:12,070 --> 00:40:14,570
そして今、我々は繰り返す。

499
00:40:14,570 --> 00:40:20,670
だから今我々は2と1を比較します。 1が小さくなるので、我々は1を挿入します。

500
00:40:20,670 --> 00:40:25,300
我々はこの男を指すように、このポインタを更新する。

501
00:40:25,300 --> 00:40:33,160
今、我々は再びそれを行う、2そう。これは、これらの2、3と比較し、更新されます。

502
00:40:33,160 --> 00:40:37,770
その後、このアップデート、4と5。

503
00:40:37,770 --> 00:40:42,110
だからそれはマージされています。

504
00:40:42,110 --> 00:40:49,010
>> それは、我々は一度だけ各要素を渡って行くので、それは線形時間であることがかなり明白になります。

505
00:40:49,010 --> 00:40:55,980
そして、それはマージソートを実装するための最大のステップは、これをやっているされています。

506
00:40:55,980 --> 00:40:59,330
そして、それはそんなに難しいことではありません。

507
00:40:59,330 --> 00:41:15,020
心配するカップルの事はしてみましょう私たちは1、2、3、4、5、6をマージしたと言う。

508
00:41:15,020 --> 00:41:30,930
この場合、我々はこの1つは小さくなるだろうされているシナリオでは、結局、

509
00:41:30,930 --> 00:41:36,160
それから私達はこのポインタを更新し、この1つは、これを更新して、小さいことになるだろう

510
00:41:36,160 --> 00:41:41,280
この1つは小さいです、そして今、あなたは認識しなければならない

511
00:41:41,280 --> 00:41:44,220
あなたが実際と比較するための要素が不足してきたとき。

512
00:41:44,220 --> 00:41:49,400
我々はすでに、この全体の配列を使っているので、

513
00:41:49,400 --> 00:41:55,190
この配列内のすべてのものが今まさにここに挿入されます。

514
00:41:55,190 --> 00:42:02,040
我々はこれまで我々の配列のいずれかが完全に既にマージされたポイントに遭遇しそうだとすれば、

515
00:42:02,040 --> 00:42:06,510
私たちはただ、他の配列のすべての要素を取得し、配列の末尾に挿入します。

516
00:42:06,510 --> 00:42:13,630
だから我々はわずか6、4、5を挿入することができます。オーケー。

517
00:42:13,630 --> 00:42:18,070
それは気をつけて一つのことです。

518
00:42:22,080 --> 00:42:26,120
それは、ステップ1である必要があります実装。

519
00:42:26,120 --> 00:42:32,600
それに基づいて、次にソートマージは、2つのステップ、2ステップ愚かだ。

520
00:42:38,800 --> 00:42:42,090
ちょうどこの配列を与えてみましょう。

521
00:42:57,920 --> 00:43:05,680
だから、マージソート、ステップ1は再帰的に半分に配列を分割することです。

522
00:43:05,680 --> 00:43:09,350
だから半分に、この配列を分割します。

523
00:43:09,350 --> 00:43:22,920
我々は今、4、15、16、50、8、23、42、108を持っています。

524
00:43:22,920 --> 00:43:25,800
そして今、我々は再びそれを行うと、我々は半分にこれらを分割します。

525
00:43:25,800 --> 00:43:27,530
私はこの辺でそれを行うだけでしょう。

526
00:43:27,530 --> 00:43:34,790
50、4、15と16だから。

527
00:43:34,790 --> 00:43:37,440
我々はここを介して同じことをするだろう。

528
00:43:37,440 --> 00:43:40,340
そして今、我々は再び半分に分割します。

529
00:43:40,340 --> 00:43:51,080
そして、我々は4、15、16、50を持っています。

530
00:43:51,080 --> 00:43:53,170
だからそれは私たちのベースケースです。

531
00:43:53,170 --> 00:44:00,540
配列のサイズは1であると、次に我々は、半分に分割すると停止します。

532
00:44:00,540 --> 00:44:03,190
>> 今、私たちは、これで何をすればいいですか？

533
00:44:03,190 --> 00:44:15,730
我々は、これはまた、8、23、42、および108に打破するに終わる。

534
00:44:15,730 --> 00:44:24,000
だから今我々はこの点にいることを、今ではマージソートのステップ2は、単にリストにペアをマージすることです。

535
00:44:24,000 --> 00:44:27,610
だから我々は、これらをマージしたい。私達はちょうどマージと呼びます。

536
00:44:27,610 --> 00:44:31,410
私たちは、マージソートされた順序でこれらを戻すことがわかっている。

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

538
00:44:33,920 --> 00:44:41,440
今、私たちは、これらをマージしたい、そしてそれは、ソートされた順序でそれらを使用してリストを返します。

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

540
00:44:44,160 --> 00:44:57,380
我々は、それらをマージする - 私は書くことができません -  8、23、42、108。

541
00:44:57,380 --> 00:45:02,890
だから我々は一度ペアをマージした。

542
00:45:02,890 --> 00:45:05,140
今、私たちはもう一度マージ。

543
00:45:05,140 --> 00:45:10,130
それ自体はそれぞれのこれらのリストがソートされていることに注意してください、

544
00:45:10,130 --> 00:45:15,220
それから私達はちょうどソートされている大きさ4のリストを取得するには、これらのリストをマージすることができます

545
00:45:15,220 --> 00:45:19,990
とソートされているサイズ4のリストを取得するためにこれらの2つのリストをマージします。

546
00:45:19,990 --> 00:45:25,710
そして最後に、我々はソートされているサイズ8のいずれかのリストを取得するにはサイズ4のものと二つのリストをマージすることができます。

547
00:45:25,710 --> 00:45:34,030
だから、これは全体的なnログnであることを確認するために、我々はすでにマージが線形であることを見て、

548
00:45:34,030 --> 00:45:40,390
ので、我々はそうマージの全体的なコストのように、これらをマージを扱っているときに

549
00:45:40,390 --> 00:45:43,410
これらの2つのリストのためだけに2があるためです - 

550
00:45:43,410 --> 00:45:49,610
またはよく、それはnのOですが、ここでnは、ちょうどこれらの2つの要素であるので、2です。

551
00:45:49,610 --> 00:45:52,850
そして、これら2つの値は2になりますと、これらの2つの値は2になりますと、これらの2つの値は2になります

552
00:45:52,850 --> 00:45:58,820
ので、私たちが行う必要があることをマージのすべてにわたって、私たちはnをやってしまう。

553
00:45:58,820 --> 00:46:03,210
2のように+ 2 + 2 + 2 nである8、、です

554
00:46:03,210 --> 00:46:08,060
ので、このセットにマージのコストはnです。

555
00:46:08,060 --> 00:46:10,810
そして、ここにも同じこと。

556
00:46:10,810 --> 00:46:16,980
そして、私たちは、これら2、これらの2つをマージします、個別にこのマージは、4つの操作がかかります

557
00:46:16,980 --> 00:46:23,610
このマージは、これらのすべての間、再び4つの操作を取るしますが、

558
00:46:23,610 --> 00:46:29,030
私たちは、マージN合計物事に終わるので、このステップは、nを取ります。

559
00:46:29,030 --> 00:46:33,670
ので、各レベルがマージされて、n個の要素を取ります。

560
00:46:33,670 --> 00:46:36,110
>> そして、どのように多くのレベルがありますか？

561
00:46:36,110 --> 00:46:40,160
各レベルでは、我々の配列のサイズが2増加します。

562
00:46:40,160 --> 00:46:44,590
ここに我々の配列はサイズ1のものであり、ここで、彼らはサイズ2のであれば、ここに彼らは、サイズ4のだ

563
00:46:44,590 --> 00:46:46,470
そして最後に、彼らはサイズ8のだ。

564
00:46:46,470 --> 00:46:56,450
それが倍増していますのでので、ログのnこれらのレベルの合計があるように起こっています。

565
00:46:56,450 --> 00:47:02,090
だからログnレベル、個々のレベル取るn個の合計の操作と、

566
00:47:02,090 --> 00:47:05,720
私たちは、常にn log nのアルゴリズムを取得します。

567
00:47:05,720 --> 00:47:07,790
質問はありますか？

568
00:47:08,940 --> 00:47:13,320
人々は、すでにこれを実装する方法についての進歩を遂げている？

569
00:47:13,320 --> 00:47:18,260
誰もがすでに私はちょうど彼らのコードを引っ張ることができる状態になっていますか。

570
00:47:20,320 --> 00:47:22,260
私は分を与えることができます。

571
00:47:24,770 --> 00:47:27,470
この1つは長くなるだろう。

572
00:47:27,470 --> 00:47:28,730
私は非常に再発をお勧めします - 

573
00:47:28,730 --> 00:47:30,510
マージ時に再帰を行う必要はありません

574
00:47:30,510 --> 00:47:33,750
マージのために再帰を行うためには、異なるサイズの束を渡す必要があるとしている。

575
00:47:33,750 --> 00:47:37,150
あなたはできますが、それは迷惑なんだ。

576
00:47:37,150 --> 00:47:43,720
しかし、ソート自体の再帰はとても簡単です。

577
00:47:43,720 --> 00:47:49,190
あなただけの文字通り右半分で並べ替え、左半分にソートを呼び出します。オーケー。

578
00:47:51,770 --> 00:47:54,860
誰も私がまだプルアップすることができます何かを持っている？

579
00:47:54,860 --> 00:47:57,540
さもないと私は分を差し上げます。

580
00:47:58,210 --> 00:47:59,900
オーケー。

581
00:47:59,900 --> 00:48:02,970
誰もが我々が働くことができる何かを持っている？

582
00:48:05,450 --> 00:48:09,680
さもなければ私達はちょうどこのと連携し、そこから拡大していく。

583
00:48:09,680 --> 00:48:14,050
>> 誰も私がプルアップすることができ、この以上のものを持っている？

584
00:48:14,050 --> 00:48:17,770
[学生]うん。あなたは私をプルアップすることができます。 >>すべての権利。

585
00:48:17,770 --> 00:48:19,730
うん！

586
00:48:22,170 --> 00:48:25,280
[学生]の条件がたくさんあり​​ました。 >>ああ、撃つ。次のことができます - 

587
00:48:25,280 --> 00:48:28,110
[学生]私はそれを保存する必要があります。 >>うん。

588
00:48:32,420 --> 00:48:35,730
だから我々は別々にマージんでした。

589
00:48:35,730 --> 00:48:38,570
ああ、それはそれほど悪くはありません。

590
00:48:39,790 --> 00:48:41,650
オーケー。

591
00:48:41,650 --> 00:48:47,080
だからソートはちょうどmergeSortHelpを呼び出しそのものです。

592
00:48:47,080 --> 00:48:49,530
mergeSortHelpが何を私達に説明してください。

593
00:48:49,530 --> 00:48:55,700
[学生] MergeSortHelpはかなり多く、主に2つの手順を行い、

594
00:48:55,700 --> 00:49:01,270
これは、配列の各半分をソートするために、次に、それらの両方をマージすることです。

595
00:49:04,960 --> 00:49:08,050
[ボーデン]わかりましたので、ちょっと待ってて。

596
00:49:10,850 --> 00:49:13,210
私はこれを考える -  >> [学生]私がする必要がある - 

597
00:49:17,100 --> 00:49:19,400
うん。私は何かが欠けている。

598
00:49:19,400 --> 00:49:23,100
マージでは、私は新しい配列を作成するために必要なことがわかります

599
00:49:23,100 --> 00:49:26,530
私はその場所でそれを行うことができなかったからだ。 >>はい。それはできません。訂正してください。

600
00:49:26,530 --> 00:49:28,170
[学生]だから私は、新しい配列を作成します。

601
00:49:28,170 --> 00:49:31,510
私は再変更するマージの終了時に忘れていました。

602
00:49:31,510 --> 00:49:34,490
オーケー。私たちは、新しい配列が必要です。

603
00:49:34,490 --> 00:49:41,000
マージソートでは、これはほとんど常にtrueです。

604
00:49:41,000 --> 00:49:44,340
良いアルゴリズム時間的コストの一部

605
00:49:44,340 --> 00:49:47,310
ほとんど常に少しより多くのメモリを使用する必要があるされています。

606
00:49:47,310 --> 00:49:51,570
だからここでは、あなたがマージソートを行う方法に関係なく、

607
00:49:51,570 --> 00:49:54,780
あなたは必然的にいくつかの余分なメモリを使用する必要があります。

608
00:49:54,780 --> 00:49:58,240
彼または彼女は、新しい配列を作成しました。

609
00:49:58,240 --> 00:50:03,400
そしてあなたは終わりに我々だけで、元の配列に新しい配列をコピーする必要があると言う。

610
00:50:03,400 --> 00:50:04,830
[学生]私はそう思う、うん。

611
00:50:04,830 --> 00:50:08,210
それは、参照または何でカウントの面で動作するかどうか私は知らない - 

612
00:50:08,210 --> 00:50:11,650
うん、それは動作します。 >> [生徒]オーケー。

613
00:50:20,620 --> 00:50:24,480
あなたはこれを実行してみましたか？ >> [生徒]いいえ、まだありません。オーケー。>>

614
00:50:24,480 --> 00:50:28,880
それを実行してみて、その後私は2番目のためにそれについて話します。

615
00:50:28,880 --> 00:50:35,200
[学生]私は右、しかし、すべての関数プロトタイプとすべてを持っている必要がありますか？

616
00:50:37,640 --> 00:50:40,840
関数プロトタイプ。 [はい]  - ああ、あなたはのような意味。

617
00:50:40,840 --> 00:50:43,040
ソートはmergeSortHelpを呼んでいる。

618
00:50:43,040 --> 00:50:47,390
>> mergeSortHelpを呼び出すための並べ替えのためのために、だから、mergeSortHelpが定義されている必要があり

619
00:50:47,390 --> 00:50:56,370
ソート前または私達はちょうどプロトタイプが必要です。ちょうどそれをコピーして貼り付ける。

620
00:50:56,370 --> 00:50:59,490
と同様に、mergeSortHelpは、マージを呼んでいる

621
00:50:59,490 --> 00:51:03,830
しかし、マージはまだ定義されていないので、我々はちょうどmergeSortHelpに知らせることができます

622
00:51:03,830 --> 00:51:08,700
それがマージのように見えるように何が起こっているかだし、それはそれだ。

623
00:51:09,950 --> 00:51:15,730
mergeSortHelpだから。

624
00:51:22,770 --> 00:51:32,660
我々はベースケースを持っていないところで私たちは、ここに問題があります。

625
00:51:32,660 --> 00:51:38,110
MergeSortHelpが再帰的であるので、任意の再帰関数

626
00:51:38,110 --> 00:51:42,610
それ自体を再帰的に呼び出しを停止するタイミングを知るために、ベースケースのいくつかの並べ替えが必要になるだろう。

627
00:51:42,610 --> 00:51:45,590
私たちのベースケースはここで何をするつもりですか？うん。

628
00:51:45,590 --> 00:51:49,110
[学生]大きさが1である場合？ >> [ボーデン]はい。

629
00:51:49,110 --> 00:51:56,220
だから我々はすぐそこに見たように、我々は分裂アレイを停止

630
00:51:56,220 --> 00:52:01,850
かつて我々は、必然的に自分自身をソートされているサイズ1の配列に入った。

631
00:52:01,850 --> 00:52:09,530
サイズが1に等しいのであれば、我々は、配列が既にソートされて知っている

632
00:52:09,530 --> 00:52:12,970
ので、単に返すことができます。

633
00:52:12,970 --> 00:52:16,880
>> ボイドの通知は、私たちは特定の何かを返さない、私達はちょうど返す。

634
00:52:16,880 --> 00:52:19,580
オーケー。だからそれは私たちのベースケースです。

635
00:52:19,580 --> 00:52:27,440
私たちは、サイズが0の配列をマージすることが起こる場合、私たちの基本ケースにもなることができると思います

636
00:52:27,440 --> 00:52:30,030
我々は、おそらく、どこかの時点で停止したい

637
00:52:30,030 --> 00:52:33,610
ので、単に大きさが2未満または未満または1に等しいと言うことができます

638
00:52:33,610 --> 00:52:37,150
ので、これは今どのような配列のために働くこと。

639
00:52:37,150 --> 00:52:38,870
オーケー。

640
00:52:38,870 --> 00:52:42,740
だからそれは私たちのベースケースです。

641
00:52:42,740 --> 00:52:45,950
今、あなたは、マージを通して私たちを歩きたいのですか？

642
00:52:45,950 --> 00:52:49,140
これらのすべての場合は何を意味するのでしょうか？

643
00:52:49,140 --> 00:52:54,480
ここまで、私たちは、同じ考え方をしている - 

644
00:52:56,970 --> 00:53:02,470
[学生]私はすべてmergeSortHelp呼び出しでサイズを渡すことが必要である。

645
00:53:02,470 --> 00:53:10,080
私は追加のプライマリとしてサイズを追加し、それは大きさ/ 2のような、そこにはありません。

646
00:53:10,080 --> 00:53:16,210
[ボーデン]ああ、サイズ/ 2サイズ/ 2。 >> [生徒]うん、また同様に上記の関数インチ

647
00:53:16,210 --> 00:53:21,320
[ボーデン]ここですか？ >> [生徒]ジャストサイズ。 >> [ボーデン]ああ。サイズ、サイズは？ >> [生徒]うん。

648
00:53:21,320 --> 00:53:23,010
[ボーデン]オーケー。

649
00:53:23,010 --> 00:53:26,580
私は一瞬考えてみましょう。

650
00:53:26,580 --> 00:53:28,780
我々はこの問題に遭遇していますか？

651
00:53:28,780 --> 00:53:33,690
我々は常に0として左を扱っている。 >> [生徒]いいえ

652
00:53:33,690 --> 00:53:36,340
それはあまりにも間違っている。申し訳ございませんでした。それがスタートです。うん。

653
00:53:36,340 --> 00:53:39,230
[ボーデン]オーケー。私はその方が好き。

654
00:53:39,230 --> 00:53:43,880
と終了。オーケー。

655
00:53:43,880 --> 00:53:47,200
だから今は、マージを通して私たちを歩きたいのですか？ >> [生徒]オーケー。

656
00:53:47,200 --> 00:53:52,150
私はちょうど私が作成したので、この新しい配列を介して歩いている。

657
00:53:52,150 --> 00:53:57,420
その大きさは、我々がソートさせたい配列の部分の大きさです

658
00:53:57,420 --> 00:54:03,460
と私は、新しい配列のステップに置くべきだと要素を見つけようとする。

659
00:54:03,460 --> 00:54:10,140
だから配列の左半分には、任意の複数の要素を持ち続けている場合は、最初の私がチェックしている、そんなことをして、

660
00:54:10,140 --> 00:54:14,260
そうでない場合と、あなただけの言うことelse条件に下がる

661
00:54:14,260 --> 00:54:20,180
大丈夫、それは右の配列でなければなりません、そして我々はnewArrayの現在のインデックスでそれを置くことにしましょう​​。

662
00:54:20,180 --> 00:54:27,620
>> アレイの右側も終了されていて、その後、それ以外の場合は私がチェックしている、

663
00:54:27,620 --> 00:54:30,630
その場合、私はちょうど左に置く。

664
00:54:30,630 --> 00:54:34,180
それは実際には必要でないかもしれません。私はよく分からない。

665
00:54:34,180 --> 00:54:40,970
しかし、いずれにせよ、2のどれが他の二つのチェックは、左または右に小さくなっている。

666
00:54:40,970 --> 00:54:49,770
また、それぞれの場合において、私はインクリメント方プレースインクリメントしている。

667
00:54:49,770 --> 00:54:52,040
[ボーデン]オーケー。

668
00:54:52,040 --> 00:54:53,840
それはよさそうだ。

669
00:54:53,840 --> 00:54:58,800
誰でもコメントや懸念や疑問を持っていますか？

670
00:55:00,660 --> 00:55:07,720
またはそれは5のように見える - 私たちだけであることに何かをもたらすことを持っていることを4つのケースがそう - 

671
00:55:07,720 --> 00:55:13,100
しかし、我々は左の配列は、我々はマージする必要があるものがなくなっているかどうかを考慮する必要があります

672
00:55:13,100 --> 00:55:16,390
右の配列は、我々はマージする必要があるものが不足しているかどうか - 

673
00:55:16,390 --> 00:55:18,400
私は何を指しています。

674
00:55:18,400 --> 00:55:21,730
だから左配列はものがなくなっているか、または右の配列はものがなくなったかどうか。

675
00:55:21,730 --> 00:55:24,320
それらは2つのケースがあります。

676
00:55:24,320 --> 00:55:30,920
また、左のものが右のものよりも小さいかどうかの些細なケースを必要としています。

677
00:55:30,920 --> 00:55:33,910
その後、我々は左のものを選びたい。

678
00:55:33,910 --> 00:55:37,630
これらは例です。

679
00:55:37,630 --> 00:55:40,990
だから、これは正しかった、ということになるよう。

680
00:55:40,990 --> 00:55:46,760
配列が残っています。それは、1、2、3です。オーケー。そんなわけで、それらは我々がしたいと思うかもしれません4ものです。

681
00:55:50,350 --> 00:55:54,510
そして、我々は反復解法上に行くことはありません。

682
00:55:54,510 --> 00:55:55,980
私はお勧めしません - 

683
00:55:55,980 --> 00:56:03,070
マージソートは、再帰的な両方のテールではない関数の例です。

684
00:56:03,070 --> 00:56:07,040
それは、それは末尾再帰にするのは簡単ではありません

685
00:56:07,040 --> 00:56:13,450
だけでなく、それが反復するのは非常に簡単ではありません。

686
00:56:13,450 --> 00:56:16,910
これは非常に簡単です。

687
00:56:16,910 --> 00:56:19,170
マージソートの実装には、

688
00:56:19,170 --> 00:56:22,140
マージ、あなたが何をするかに関係なく、あなたはマージを構築しようとしている。

689
00:56:22,140 --> 00:56:29,170
>> だからマージの上に構築されたソートは再帰的にちょうどこれらの3行ですマージ。

690
00:56:29,170 --> 00:56:34,700
反復的に、それはより多くの迷惑と考えるのがより困難である。

691
00:56:34,700 --> 00:56:41,860
しかし、それはmergeSortHelp以来、末尾再帰ではないことに気づく - それはそれ自身を呼び出したときに - 

692
00:56:41,860 --> 00:56:46,590
それはまだこのような再帰呼び出しが戻った後のことを行う必要があります。

693
00:56:46,590 --> 00:56:50,830
したがって、このスタックフレームはこのメソッドを呼び出した後であっても存在し続けなければなりません。

694
00:56:50,830 --> 00:56:54,170
そして、あなたがこれを呼び出すと、スタックフレームが存在し続けなければなりません

695
00:56:54,170 --> 00:56:57,780
でも、そのコールの後、我々はまだマージする必要があるためです。

696
00:56:57,780 --> 00:57:01,920
そしてそれはこのテールと、再帰的に自明である。

697
00:57:04,070 --> 00:57:06,270
質問はありますか？

698
00:57:08,300 --> 00:57:09,860
かしこまりました。

699
00:57:09,860 --> 00:57:13,400
だからソートするために戻って - ああ、私が見せたいものがふたつあります。オーケー。

700
00:57:13,400 --> 00:57:17,840
ソートに戻って、我々はすぐにこの作業を行います。

701
00:57:17,840 --> 00:57:21,030
または検索。並べ替え？並べ替え。うん。

702
00:57:21,030 --> 00:57:22,730
ソートの始まりに戻って行く。

703
00:57:22,730 --> 00:57:29,870
我々は、任意のアルゴリズムを使用して、その配列をソートするアルゴリズムを作成したい

704
00:57:29,870 --> 00:57:33,660
n個のOインチ

705
00:57:33,660 --> 00:57:40,860
それでは、どのようにこれは可能ですか？誰もが任意の並べ替えを持っていますか - 

706
00:57:40,860 --> 00:57:44,300
私は時前にほのめかし - 

707
00:57:44,300 --> 00:57:48,300
我々はnログnからnのOに向上させるために約ているのであれば、

708
00:57:48,300 --> 00:57:51,450
我々は、我々のアルゴリズムの時間的に改善している

709
00:57:51,450 --> 00:57:55,250
これは、我々はそのために補うために行う必要があるために何を行っているかを意味します

710
00:57:55,250 --> 00:57:59,520
[学生]スペース。 >>うん。我々は、より多くのスペースを使用してすることになるだろう。

711
00:57:59,520 --> 00:58:04,490
としないだけでも、より多くのスペース、それが指数関数的に多くのスペースです。

712
00:58:04,490 --> 00:58:14,320
だから私はこのタイプのアルゴリズムは擬似何か、擬似多項式だと思う - 

713
00:58:14,320 --> 00:58:18,980
擬似 - 私は思い出すことができません。何か擬似。

714
00:58:18,980 --> 00:58:22,210
しかし、我々はこれだけの容量を使用する必要があるので、それはだ

715
00:58:22,210 --> 00:58:28,610
これは達成が、現実的ではないこと。

716
00:58:28,610 --> 00:58:31,220
>> そして、どのように我々はこれを達成するの​​ですか？

717
00:58:31,220 --> 00:58:36,810
我々が保証した場合我々は、これを達成することができ、そのアレイ内の特定の要素

718
00:58:36,810 --> 00:58:39,600
一定以下の大きさです。

719
00:58:42,070 --> 00:58:44,500
だから、ちょうどサイズが200であると言うてみましょう

720
00:58:44,500 --> 00:58:48,130
配列内の任意の要素には、以下のサイズ200です。

721
00:58:48,130 --> 00:58:51,080
そして、これは実際には非常に現実的である。

722
00:58:51,080 --> 00:58:58,660
あなたは非常に簡単にあなたはそれのすべてを知っている配列を持つことができ

723
00:58:58,660 --> 00:59:00,570
いくつかの数よりも少なくなるだろう。

724
00:59:00,570 --> 00:59:07,400
あなたには、いくつかの絶対に大規模なベクトルか何かを持っている場合など

725
00:59:07,400 --> 00:59:11,810
しかし、あなたは、すべてが0と5の間になるだろう知っている

726
00:59:11,810 --> 00:59:14,790
それがこれを行うことが大幅に速くなるだろう。

727
00:59:14,790 --> 00:59:17,930
とのいずれかの要素にバインドされ、5です

728
00:59:17,930 --> 00:59:21,980
このバウンドので、それはあなたが使用しようとしているどのくらいのメモリである。

729
00:59:21,980 --> 00:59:26,300
だからバインドは200です。

730
00:59:26,300 --> 00:59:32,960
整数のみを最大4億円となりましたことができるので、理論的にはバウンドが常にあるので、

731
00:59:32,960 --> 00:59:40,600
我々はスペースを使用しているはずだそれ以来、それは非現実的だ

732
00:59:40,600 --> 00:59:44,400
40億のオーダーである。だからそれは非現実的である。

733
00:59:44,400 --> 00:59:47,060
しかし、ここで我々はバウンドに言うよは200です。

734
00:59:47,060 --> 00:59:59,570
n個のOでそれをやってのトリックは、我々は大きさのカウントはBOUNDと呼ばれる別の配列を作ることです。

735
00:59:59,570 --> 01:00:10,470
だから、実際、これは次の内容のショートカットです -  Clangのがこれを行う場合、私は実際にはわからない。

736
01:00:11,150 --> 01:00:15,330
しかし、非常に少なくともGCCで -  Clangの仮定 - 私は、あまりにもそれをしない - 

737
01:00:15,330 --> 01:00:18,180
これは単に0であることが、配列全体を初期化します。

738
01:00:18,180 --> 01:00:25,320
私はそれを行うにはしたくないので、もし次に私が別個に行うことができます（int型私= 0;

739
01:00:25,320 --> 01:00:31,500
I <BOUNDは、i + +）とカウント[I] = 0;

740
01:00:31,500 --> 01:00:35,260
だから今はすべてが0に初期化されます。

741
01:00:35,260 --> 01:00:39,570
私は、私の配列を反復

742
01:00:39,570 --> 01:00:51,920
と私がやっていることは、私はそれぞれの数を数えている - ここに降りて行きましょう。

743
01:00:51,920 --> 01:00:55,480
我々は4、15、16、50、8、23、42、108を持っています。

744
01:00:55,480 --> 01:01:00,010
私は何を数えていると、それらの各要素の出現回数である。

745
01:01:00,010 --> 01:01:03,470
実際にいくつか繰り返すと一緒にここにカップルより多く追加してみましょう。

746
01:01:03,470 --> 01:01:11,070
我々がここにあるように、値の値は[i]の配列になるだろう。

747
01:01:11,070 --> 01:01:14,850
だから、valは4または8または何でも可能性があります。

748
01:01:14,850 --> 01:01:18,870
そして今、私は、私が見てきたどのように多く、その値の数えている

749
01:01:18,870 --> 01:01:21,230
カウントしますので、[ヴァル] + +;

750
01:01:21,230 --> 01:01:29,430
これが完了すると、カウントが0001のような何かを見に行くされています。

751
01:01:29,430 --> 01:01:42,190
カウントを行いましょう[ヴァル]  -  + 1 BOUND。

752
01:01:42,190 --> 01:01:48,230
>> 今では我々は0から開始しているという事実を考慮してばかりだ。

753
01:01:48,230 --> 01:01:50,850
だから200が私たちの最大の数であることを行っている場合、

754
01:01:50,850 --> 01:01:54,720
その後、0から200は201の事です。

755
01:01:54,720 --> 01:02:01,540
我々は1つの4を持っているので、カウントだから、それは00001のように見えます。

756
01:02:01,540 --> 01:02:10,210
その後、我々は、我々は数の第八インデックスに1を持っています0001があるでしょう。

757
01:02:10,210 --> 01:02:14,560
我々は、カウント23日インデックスに2があるでしょう。

758
01:02:14,560 --> 01:02:17,630
我々は、カウントの42インデックスに2があるでしょう。

759
01:02:17,630 --> 01:02:21,670
だから我々は、カウントを使用することができます。

760
01:02:34,270 --> 01:02:44,920
だからnum_of_item =カウント[I]。

761
01:02:44,920 --> 01:02:52,540
とnum_of_itemが2であるので、もし、我々は番号iの2を挿入することを意味します

762
01:02:52,540 --> 01:02:55,290
私たちのソートされた配列に変換します。

763
01:02:55,290 --> 01:03:02,000
だから我々は、我々は配列にどのくらいずれているかを追跡する必要があります。

764
01:03:02,000 --> 01:03:05,470
だからインデックス= 0。

765
01:03:05,470 --> 01:03:09,910
アレイ - 私はちょうどそれを書こうと思います。

766
01:03:16,660 --> 01:03:18,020
カウント - 

767
01:03:19,990 --> 01:03:28,580
配列[インデックス+ +] = I;

768
01:03:28,580 --> 01:03:32,490
それは私が何をしたいですか？私はそれは私が欲しいものだと思います。

769
01:03:35,100 --> 01:03:38,290
はい、これはよさそうだ。オーケー。

770
01:03:38,290 --> 01:03:43,050
だから誰もが私のカウントアレイの目的が何であるかを理解するのでしょうか？

771
01:03:43,050 --> 01:03:48,140
それは、これらの数値のそれぞれの出現回数をカウントしています。

772
01:03:48,140 --> 01:03:51,780
それから私はその件数配列を反復処理しています、

773
01:03:51,780 --> 01:03:57,190
とカウント配列内の​​i番目の位置

774
01:03:57,190 --> 01:04:01,930
私のソートされた配列に表示されるはずだ、私は数です。

775
01:04:01,930 --> 01:04:06,840
4の数が1であることを行っている理由です

776
01:04:06,840 --> 01:04:11,840
8のカウントが1であることを行っている、23のカウントが2になるだろう。

777
01:04:11,840 --> 01:04:16,900
だから私はソートされた配列に挿入したいどのようにそれらの多くのです。

778
01:04:16,900 --> 01:04:19,200
その後、私はちょうどそれを行う。

779
01:04:19,200 --> 01:04:28,960
私は私が私のソートされた配列に代入num_of_itemを挿入しています。

780
01:04:28,960 --> 01:04:31,670
>> 質問はありますか？

781
01:04:32,460 --> 01:04:43,100
我々は一度だけこれを反復処理しているのでので、再び、これは、線形時間である

782
01:04:43,100 --> 01:04:47,470
それは、この数があると何が起こるかでも直線だ

783
01:04:47,470 --> 01:04:50,730
ので、それは大いにあなたのバウンドが何であるかに依存します。

784
01:04:50,730 --> 01:04:53,290
200のバウンドと、それはそれほど悪くはありません。

785
01:04:53,290 --> 01:04:58,330
あなたのバウンドが10,000であることを行っている場合、そのことは、少し悪いです

786
01:04:58,330 --> 01:05:01,360
あなたのバウンドが、4億ドルになるとしている場合、それは完全に非現実的だ

787
01:05:01,360 --> 01:05:07,720
この配列は、現実的ではありませんサイズは4億円であることがあることを行っています。

788
01:05:07,720 --> 01:05:10,860
だからそれはそれだ。質問はありますか？

789
01:05:10,860 --> 01:05:13,270
[聞き取れない生徒の応答] >>オーケー。

790
01:05:13,270 --> 01:05:15,710
我々が通過したとき、私はもうひとつを実現しました。

791
01:05:17,980 --> 01:05:23,720
私はこの問題は、ルーカスさんと、おそらく我々が見てきたすべての単一の1であったと思います。

792
01:05:23,720 --> 01:05:26,330
私は完全に忘れていました。

793
01:05:26,330 --> 01:05:31,040
私がコメントしたかった唯一のものは、あなたがインデックスのようなものを扱っているということです

794
01:05:31,040 --> 01:05:38,320
あなたは、forループを書くときにあなたは本当に、これを見ることはありません

795
01:05:38,320 --> 01:05:41,120
しかし技術的には、いつでもあなたは、これらの指標を扱っている

796
01:05:41,120 --> 01:05:45,950
あなたはかなり常に符号なし整数に対処しなければならない。

797
01:05:45,950 --> 01:05:53,850
あなたは、符号付き整数を扱っているときに、この理由は、

798
01:05:53,850 --> 01:05:56,090
そのため、2つの符号付き整数を持っていて、それらを一緒に追加した場合

799
01:05:56,090 --> 01:06:00,640
そして、彼らが大きすぎる結局、その後は負の数になってしまう。

800
01:06:00,640 --> 01:06:03,410
だから整数オーバーフローが何であるかです。

801
01:06:03,410 --> 01:06:10,500
>> 私は2億円、10億ドルを追加した場合、私はマイナス1億ドルとなってしまう。

802
01:06:10,500 --> 01:06:15,480
つまり、整数はコンピュータ上でどのように機能するかだ。

803
01:06:15,480 --> 01:06:17,510
使用する場合の問題は、だから - 

804
01:06:17,510 --> 01:06:23,500
ローは20億であることを起こる、最大1億円が発生するかどうかは除いていいのよ

805
01:06:23,500 --> 01:06:27,120
これは10億負になるだろうし、我々は2であることを分割するつもりだ

806
01:06:27,120 --> 01:06:29,730
と負5億で終わる。

807
01:06:29,730 --> 01:06:33,760
ですから、これは配列を検索することが起こる場合にのみ問題となります

808
01:06:33,760 --> 01:06:38,070
物事の数十億の。

809
01:06:38,070 --> 01:06:44,050
しかし、低+がアップするオーバーフローに起これば、そのことが問題だ。

810
01:06:44,050 --> 01:06:47,750
とすぐに我々は彼らがunsigned作るとして、その後20億プラス10億は3億円です。

811
01:06:47,750 --> 01:06:51,960
2で割った30億は1.5億ドルである。

812
01:06:51,960 --> 01:06:55,670
だから、すぐに彼らは符号なしだとして、すべてが完璧です。

813
01:06:55,670 --> 01:06:59,900
そしてそうそれはあなたがあなたのためにループを書くときにも問題だが、

814
01:06:59,900 --> 01:07:03,940
そして実際に、それはおそらく、それを自動的に行います。

815
01:07:09,130 --> 01:07:12,330
それは実際にちょうどあなたで叫ぶでしょう。

816
01:07:12,330 --> 01:07:21,610
この数字は単なる整数であるには余りにも大きいですが、それは、符号なし整数に収まるであろうのであれば

817
01:07:21,610 --> 01:07:24,970
それはあなたで叫ぶでしょう、あなたが本当に問題に遭遇したことがない理由だそう。

818
01:07:29,150 --> 01:07:34,820
あなたは、インデックスが負になるだろうことはありませんされていることがわかります

819
01:07:34,820 --> 01:07:39,220
ので、あなたは、配列を反復処理しているとき

820
01:07:39,220 --> 01:07:43,970
あなたはほぼ常にunsigned int iを言うことができますが、あなたは本当に必要はありません。

821
01:07:43,970 --> 01:07:47,110
物事も同様にかなり仕事に行くされています。

822
01:07:48,740 --> 01:07:50,090
オーケー。 [ささやき]それが何時ですか？

823
01:07:50,090 --> 01:07:54,020
私が見せたかったの最後のもの - と私はちょうどそれが本当に速いやる。

824
01:07:54,020 --> 01:08:03,190
あなたは、私たちは第5か何かのようにMAXを定義することができるように、我々は＃defineしている方法を知っている？

825
01:08:03,190 --> 01:08:05,940
MAXを行うことのないようにしましょう​​。 ＃200としてバインドを定義します。それは私たちが前にやったことだ。

826
01:08:05,940 --> 01:08:10,380
ただコピーして貼り付けしようとしている定数を定義し、その

827
01:08:10,380 --> 01:08:13,010
どこに私たちはBOUND書き込むために起こる。

828
01:08:13,010 --> 01:08:18,189
>> だから我々は実際に＃定義でより多くのことを行うことができます。

829
01:08:18,189 --> 01:08:21,170
我々は＃関数を定義できます。

830
01:08:21,170 --> 01:08:23,410
彼らは本当に機能はないが、我々はそれらの関数と呼ぶことにします。

831
01:08:23,410 --> 01:08:36,000
例がMAX（x、y）のようなものになるでしょうが（？：X X <Y Y）として定義されています。オーケー。

832
01:08:36,000 --> 01:08:40,660
だからあなたは、三項演算子の構文に慣れる必要があります

833
01:08:40,660 --> 01:08:49,029
しかし、xがyより小さいのですか？ yを返し、そうでなければxを返します。

834
01:08:49,029 --> 01:08:54,390
それで、あなたは、あなたがこの別の関数を作ることができる見ることができる

835
01:08:54,390 --> 01:09:01,399
これを返すブール値MAXは、2つの引数をもつように、関数がある可能性があります。

836
01:09:01,399 --> 01:09:08,340
これは、私がこのように実行を参照してください最も一般的なものの一つです。我々はそれらのマクロを呼び出す。

837
01:09:08,340 --> 01:09:11,790
これはマクロです。

838
01:09:11,790 --> 01:09:15,859
これはちょうどそれのための構文です。

839
01:09:15,859 --> 01:09:18,740
あなたがやりたいためにマクロを書くことができます。

840
01:09:18,740 --> 01:09:22,649
あなたが頻繁にprintfが、ものをデバッグするためのマクロを参照してください。

841
01:09:22,649 --> 01:09:29,410
printfのように、型、LINEは下線下線のようにC言語での特殊な定数がありますが、

842
01:09:29,410 --> 01:09:31,710
2、LINEは下線下線

843
01:09:31,710 --> 01:09:37,550
ともあり、私は2にFUNCアンダースコアだと思います。それはそれであるかもしれません。まあそんなところです。

844
01:09:37,550 --> 01:09:40,880
それらのものは、関数の名前に置き換えられます

845
01:09:40,880 --> 01:09:42,930
またはあなたがいることを行の番号。

846
01:09:42,930 --> 01:09:48,630
頻繁に、あなたがダウンして、ここで私は、ちょうど書けデバッグprintfを書く

847
01:09:48,630 --> 01:09:54,260
DEBUGとそれは私がにたまたまいる行番号と関数を出力します

848
01:09:54,260 --> 01:09:57,020
それはそのデバッグステートメントが発生したこと。

849
01:09:57,020 --> 01:09:59,550
そして、あなたはまた、他のものを印刷することができます。

850
01:09:59,550 --> 01:10:05,990
だからあなたを警戒しなければならない一つのことは、私は＃DOUBLE_MAXを定義するために起こる場合です

851
01:10:05,990 --> 01:10:11,380
2のようなものとして* yと2 * xになります。

852
01:10:11,380 --> 01:10:14,310
何らかの理由でだから、あなたは多くのことをそんなことが起こる。

853
01:10:14,310 --> 01:10:16,650
だからマクロ作る。

854
01:10:16,650 --> 01:10:18,680
これは実際に壊れています。

855
01:10:18,680 --> 01:10:23,050
私はDOUBLE_MAX（3,6）のような何かをすることによってそれを呼ぶだろう。

856
01:10:23,050 --> 01:10:27,530
だから何を返すべき？

857
01:10:28,840 --> 01:10:30,580
[学生] 12。

858
01:10:30,580 --> 01:10:34,800
はい、12が返されるべきであり、12が返されます。

859
01:10:34,800 --> 01:10:43,350
3 xには置換される、6はyの置き換え、そして我々は12で2 * 6、返却されます。

860
01:10:43,350 --> 01:10:47,710
今度は何これは？何を返すべき？

861
01:10:47,710 --> 01:10:50,330
[学生] 14。理想的には>> 14。

862
01:10:50,330 --> 01:10:55,290
問題は、仕事を定義する方法をハッシュ、それは文字通りのコピー＆ペーストであることを忘れないことです

863
01:10:55,290 --> 01:11:00,160
これはのように解釈されることに何が起こっているので、ほとんどすべての

864
01:11:00,160 --> 01:11:11,270
1プラス6、2回1プラス6、2回3よりも3以下である。

865
01:11:11,270 --> 01:11:19,780
>> したがって、この理由は、ほとんどの場合、括弧内のすべてを包む。

866
01:11:22,180 --> 01:11:25,050
あなたは、ほとんどの場合、括弧内にラップする任意の変数。

867
01:11:25,050 --> 01:11:29,570
私はここでそれを行う必要がないことを知っているようにあなたがする必要がないケースがあります

868
01:11:29,570 --> 01:11:32,110
未満であるため、ほとんどはいつもちょうど仕事に行く、

869
01:11:32,110 --> 01:11:34,330
それも真ではないかもしれません。

870
01:11:34,330 --> 01:11:41,870
DOUBLE_MAX（1 == 2）のようなとんでもないものがある場合は、

871
01:11:41,870 --> 01:11:49,760
その後、3分の1以下と置き換え得るために起こっていることは、2に等しい等しい

872
01:11:49,760 --> 01:11:53,460
ので、それが1より小さい3をやろうとしている、その等しい2を行い、

873
01:11:53,460 --> 01:11:55,620
それは我々が望むものではありません。

874
01:11:55,620 --> 01:12:00,730
したがって、任意の演算子の優先順位の問題を防ぐために、

875
01:12:00,730 --> 01:12:02,870
常に括弧で包む。

876
01:12:03,290 --> 01:12:07,700
オーケー。そして、それはそれ、5:30です。

877
01:12:08,140 --> 01:12:12,470
あなたはPSETの質問を有したら、私達に知らせてください。

878
01:12:12,470 --> 01:12:18,010
それは楽しみであるべきであり、ハッカーのエディションには、はるかに現実的である

879
01:12:18,010 --> 01:12:22,980
昨年のハッカー版よりも、私たちはあなた方の多くはそれを試すことを願っています。

880
01:12:22,980 --> 01:12:26,460
昨年の非常に圧倒的でした。

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]