1 00:00:00,000 --> 00:00:03,332 >> [Гуляе музыка] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Пэн: Сардэчна запрашаем у тыдзень 3 падзелу. 3 00:00:06,490 --> 00:00:09,550 Дзякуй, што вы, хлопцы, ўсе, хто прыходзіў на у гэтым больш ранні час пачатку сёння. 4 00:00:09,550 --> 00:00:11,466 Мы атрымалі добры, трохі інтымная група сёння. 5 00:00:11,466 --> 00:00:14,570 Так што спадзяюся, мы дабяромся да аздабленне, мабыць, рана, 6 00:00:14,570 --> 00:00:15,780 трохі крыху раней. 7 00:00:15,780 --> 00:00:22,057 Так хутка, проста некаторыя Анонсы парадку дня сёння. 8 00:00:22,057 --> 00:00:23,890 Перш чым мы пачнем, мы збіраюся проста перайсці 9 00:00:23,890 --> 00:00:28,910 некаторыя кароткія матэрыяльна-тэхнічных пытанняў, PSET пытанні, Інструктаж, такія рэчы, як, што. 10 00:00:28,910 --> 00:00:30,250 І тады мы будзем ныраць прама ў. 11 00:00:30,250 --> 00:00:34,710 Мы будзем выкарыстоўваць адладчык GDB пад назвай, каб пачаць развянчання наш код, які Дэвід 12 00:00:34,710 --> 00:00:36,550 растлумачыў у лекцыі ў іншы дзень. 13 00:00:36,550 --> 00:00:39,420 Мы пойдзем на працягу чатырох відаў роду. 14 00:00:39,420 --> 00:00:42,310 Мы пойдзем на іх даволі хутка так як яны даволі інтэнсіўна. 15 00:00:42,310 --> 00:00:45,710 Але ведайце, што ўсе слайды і Зыходны код заўсёды анлайн. 16 00:00:45,710 --> 00:00:50,810 Так што не саромейцеся, у вашым чытанні, каб вярнуцца назад і зірнуць на гэта. 17 00:00:50,810 --> 00:00:53,930 >> Мы пойдзем праз асімптатычнай абазначэння, якія 18 00:00:53,930 --> 00:00:55,944 гэта проста мудрагелісты спосаб сказаць "час аўтаномнай працы", 19 00:00:55,944 --> 00:00:58,360 дзе ў нас ёсць вялікі O, якая Дэвід растлумачыў у лекцыі. 20 00:00:58,360 --> 00:01:01,550 І ў нас таксама ёсць Omega, які гэта ніжняя мяжа часу выканання. 21 00:01:01,550 --> 00:01:06,450 І мы будзем казаць трохі больш у глыбіні пра тое, як гэтыя працы. 22 00:01:06,450 --> 00:01:10,160 І, нарэшце, мы пойдзем па бінарнага пошуку, таму што многія з вас, хто ўжо 23 00:01:10,160 --> 00:01:15,190 зірнуў на вашых psets, напэўна, ведаеце, што што гэта пытанне, які знаходзіцца ў вашым PSET. 24 00:01:15,190 --> 00:01:17,470 Такім чынам, вы будзеце ўсе будуць шчаслівыя што мы разгледзім гэта сёння. 25 00:01:17,470 --> 00:01:20,610 >> І, нарэшце, за ваш раздзел зваротнай сувязі, я на самой справе 26 00:01:20,610 --> 00:01:23,000 засталося каля 15 хвілін пры канец проста перайсці 27 00:01:23,000 --> 00:01:27,730 лагістыка pset3, якія-небудзь пытанні, можа быць, трохі кіраўніцтвам, калі хочаце, 28 00:01:27,730 --> 00:01:28,990 перш чым мы пачнем праграмаванне. 29 00:01:28,990 --> 00:01:30,890 Так давайце паспрабуем атрымаць праз матэрыял даволі хутка. 30 00:01:30,890 --> 00:01:33,880 І тады мы можам правесці некаторы час прымаючы больш пытанняў для PSET. 31 00:01:33,880 --> 00:01:35,230 ДОБРА. 32 00:01:35,230 --> 00:01:39,570 >> Хутка, таму толькі нешматлікія Анонсы перш чым мы пачнем сёння. 33 00:01:39,570 --> 00:01:45,410 Па-першае, сардэчна запрашаем, каб зрабіць гэта праз два вашых psets. 34 00:01:45,410 --> 00:01:49,432 Я глянуў на your-- Так, давайце атрымаць апладысменты для гэтага аднаго. 35 00:01:49,432 --> 00:01:51,140 На самай справе, я быў вельмі, сапраўды ўражаны. 36 00:01:51,140 --> 00:01:55,800 Я ацэньваюцца першы PSET для вас, хлопцы на мінулым тыдні і вы, хлопцы, зрабілі неверагоднае. 37 00:01:55,800 --> 00:01:58,290 >> Стыль быў на момант акрамя некалькіх заўваг. 38 00:01:58,290 --> 00:02:00,660 Пераканайцеся, што вы заўсёды Каментуючы свой код. 39 00:02:00,660 --> 00:02:03,040 Але вашы psets былі на кропцы. 40 00:02:03,040 --> 00:02:05,549 І трымаць яго. 41 00:02:05,549 --> 00:02:08,090 І гэта добра для грэйдэра ў бачыць, што вы, хлопцы, пакласці 42 00:02:08,090 --> 00:02:10,704 як шмат намаганняў у вашым стылі і ваш дызайн у кодзе 43 00:02:10,704 --> 00:02:12,120 што мы хацелі б, каб вы бачыце. 44 00:02:12,120 --> 00:02:16,450 Так я перадаю па маёй падзякі для астатніх ТП. 45 00:02:16,450 --> 00:02:19,210 >> Аднак ёсць Некалькі пытанняў Танто 46 00:02:19,210 --> 00:02:22,010 Я проста хачу, каб перайсці на што як бы жыццё 47 00:02:22,010 --> 00:02:24,900 і шмат іншага ТП «жыве крыху лягчэй. 48 00:02:24,900 --> 00:02:28,220 Па-першае, я заўважыў гэта міма week-- як многія з вас 49 00:02:28,220 --> 00:02:32,301 былі працуе на check50 код, перш чым прадставіць? 50 00:02:32,301 --> 00:02:32,800 ДОБРА. 51 00:02:32,800 --> 00:02:36,690 Такім чынам, кожны павінен рабіць check50, because-- secret-- мы на самай справе 52 00:02:36,690 --> 00:02:41,540 запусціць check50 як частка нашай праваце скрыпты для тэставання кода. 53 00:02:41,540 --> 00:02:45,480 Так што, калі ваш код не атрымоўваецца check50, па ўсёй верагоднасці, 54 00:02:45,480 --> 00:02:47,570 гэта, верагодна, будзе пацярпець няўдачу таксама наш чэк. 55 00:02:47,570 --> 00:02:49,320 Часам вы, хлопцы, ёсць правільныя адказы. 56 00:02:49,320 --> 00:02:52,200 Маўляў, у прагныя, некаторыя з ў вас ёсць правільныя лічбы, 57 00:02:52,200 --> 00:02:53,960 Вы проста раздрукаваць некаторыя дадатковыя рэчы. 58 00:02:53,960 --> 00:02:55,940 І, што дадатковы матэрыял на самай справе не праходзіць праверку, 59 00:02:55,940 --> 00:02:58,440 таму што кампутар не ведаю, што ён шукае. 60 00:02:58,440 --> 00:03:00,981 І так будзе проста запусціць праз, бачыць, што ваш вывад не 61 00:03:00,981 --> 00:03:03,810 адпавядае таму, што мы чакаем адказ быць, і адзначце, што гэта няправільна. 62 00:03:03,810 --> 00:03:06,560 >> І я ведаю, што адбылося ў некаторыя з вашых выпадках на гэтым тыдні. 63 00:03:06,560 --> 00:03:09,870 Так што я вярнуўся і ўручную regraded код кожнага. 64 00:03:09,870 --> 00:03:12,780 У будучыні, хоць, Калі ласка, пераканайцеся, што 65 00:03:12,780 --> 00:03:14,570 што вы працуеце праверыць 50 на кодзе. 66 00:03:14,570 --> 00:03:17,970 Таму што гэта свайго роду болі ў ТП каб вярнуцца і ўручную рэкласіфікацыя 67 00:03:17,970 --> 00:03:21,197 кожны PSET для кожнага адзін, трохі прапусціў асобнік. 68 00:03:21,197 --> 00:03:22,530 Так што я не здымаў ні аднаго ачка. 69 00:03:22,530 --> 00:03:25,210 Я думаю, што, можа быць, зняў адзін ці два для праектавання. 70 00:03:25,210 --> 00:03:27,710 У будучыні, хоць, калі Вы не спраўляюцца check50, 71 00:03:27,710 --> 00:03:31,330 кропкі будуць прынятыя ад правільнасці. 72 00:03:31,330 --> 00:03:35,020 >> Акрамя таго, у psets за пятніцах апоўдні. 73 00:03:35,020 --> 00:03:38,990 Я думаю, што ёсць сем хвілін ў канцы ільготнага перыяду, што мы даем вам. 74 00:03:38,990 --> 00:03:42,434 За час Гарвардскага, яны дазволілі сем хвілін позна, каб усім. 75 00:03:42,434 --> 00:03:44,350 Дык вось у Ельскім універсітэце, мы будзем прытрымлівацца, што добра. 76 00:03:44,350 --> 00:03:47,910 Але даволі шмат, у 00:07, калі ваш PSET гэта не ў тым, 77 00:03:47,910 --> 00:03:49,720 гэта будзе адзначаны як позна. 78 00:03:49,720 --> 00:03:53,160 І таму, хоць яна адзначаецца а позна, я TA-- 79 00:03:53,160 --> 00:03:54,870 ранейшаму будзе класіфікацыі вашыя psets. 80 00:03:54,870 --> 00:03:56,760 Такім чынам, вы ўсё яшчэ будзеце бачыць гатунак з'яўляюцца. 81 00:03:56,760 --> 00:03:58,820 Тым не менш, вядома, што ў канец семестра, 82 00:03:58,820 --> 00:04:02,270 усе пазнейшыя psets будзе проста аўтаматычна абнуляецца з дапамогай кампутара. 83 00:04:02,270 --> 00:04:04,490 >> Мы робім гэта па дзвюх прычынах. 84 00:04:04,490 --> 00:04:09,220 Адзін з іх, часам мы атрымліваем папрасіў прабачэння, як адгаворкі дэканатаў, 85 00:04:09,220 --> 00:04:10,762 пазней, што я не ведаю, пра яшчэ. 86 00:04:10,762 --> 00:04:13,761 Такім чынам, мы хацелі, каб пераканацца, што мы класіфікацыі усё толькі ў тым выпадку, як, я 87 00:04:13,761 --> 00:04:15,080 адсутнічае дараваць дэкана. 88 00:04:15,080 --> 00:04:17,000 А па-другое, майце на розум, вы ўсё яшчэ можаце 89 00:04:17,000 --> 00:04:19,370 падзенне адзін PSET, што валодае поўнымі пункту размах. 90 00:04:19,370 --> 00:04:21,430 І такім чынам, мы хацелі, каб ацэнка усе вашы psets толькі 91 00:04:21,430 --> 00:04:24,730 каб пераканацца, што ваш асцылографа ёсць і вы спрабуеце іх. 92 00:04:24,730 --> 00:04:29,150 Такім чынам, нават калі гэта позна, вы ўсё яшчэ будзеце атрымаць крэдыт для вобласці бачнасці кропак, я думаю. 93 00:04:29,150 --> 00:04:33,730 >> Так Мараль гісторыя, зрабіць Пераканайцеся, што ваш psets ў па часе. 94 00:04:33,730 --> 00:04:38,350 І калі яны не знаходзяцца ў на час, ведаю, што гэта не выдатна. 95 00:04:38,350 --> 00:04:41,678 Так, перш чым я рухацца далей, хто-небудзь ёсць любыя пытанні, якія тычацца зваротнай сувязі Pset? 96 00:04:41,678 --> 00:04:42,178 Так. 97 00:04:42,178 --> 00:04:43,630 >> АЎДЫТОРЫЯ: Вы сказалі, мы можа ўпасці адзін з psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Пэн: Так. 99 00:04:44,296 --> 00:04:47,050 Так што ў цэлым дзевяць psets на працягу семестра. 100 00:04:47,050 --> 00:04:50,610 І калі ў вас ёсць вобласць points-- так проста сфера, 101 00:04:50,610 --> 00:04:53,567 даволі шмат, вы спробай выканання Праблема, вы пакласці ў час, 102 00:04:53,567 --> 00:04:56,150 вы паказваеце, што вы маеце прадэманстравалі вы чыталі спецыфікацыі. 103 00:04:56,150 --> 00:04:57,191 Гэта даволі шмат магчымасцяў. 104 00:04:57,191 --> 00:04:59,370 І калі вы выконваеце Сфера пункту, мы 105 00:04:59,370 --> 00:05:03,360 можа ўпасці самая нізкая адным з поўным аб'ёме. 106 00:05:03,360 --> 00:05:06,790 Дык вось у вашых інтарэсах, каб запоўніць і паспрабаваць усё PSET. 107 00:05:06,790 --> 00:05:10,320 >> Нават калі upload-- ні адзін з ім працаваць, загружаць іх усе. 108 00:05:10,320 --> 00:05:13,711 І тады мы будзем, мы спадзяемся, змогуць даць вам некаторыя з гэтых кропак назад. 109 00:05:13,711 --> 00:05:14,210 Прахладны. 110 00:05:14,210 --> 00:05:16,780 Любыя іншыя пытанні? 111 00:05:16,780 --> 00:05:17,840 Выдатна. 112 00:05:17,840 --> 00:05:21,960 >> Па-другое, офіс hours-- некалькі хуткія нататкі аб працоўных гадзін. 113 00:05:21,960 --> 00:05:24,300 Такім чынам, спачатку прыходзяць у пачатку тыдня. 114 00:05:24,300 --> 00:05:26,909 Ніхто не калі-небудзь у Прыёмныя гадзіны па панядзелках. 115 00:05:26,909 --> 00:05:28,700 Christabel прыйшлі да Прыёмныя гадзіны мінулай ноччу. 116 00:05:28,700 --> 00:05:29,691 Так, Christabel. 117 00:05:29,691 --> 00:05:32,190 І што мы маем у офісе гадзін мінулай ноччу, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> АЎДЫТОРЫЯ: У нас было марозіва. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Пэн: Так што гэта правільна, мы павінны былі марозіва на офісных гадзін ўчора ўвечары. 120 00:05:36,160 --> 00:05:39,390 Хоць я не магу абяцаць вам, што мы будзем мець марозіва ў працоўны час 121 00:05:39,390 --> 00:05:43,230 кожны тыдзень, што я магу абяцаць вам, з'яўляецца тое, што будзе значна 122 00:05:43,230 --> 00:05:45,380 лепш студэнт суадносіны TA. 123 00:05:45,380 --> 00:05:47,650 Як законна, гэта як тры да аднаго. 124 00:05:47,650 --> 00:05:50,350 Прымаючы пад увагу, што з кантрастуюць Чацвер, у вас ёсць каля 150 125 00:05:50,350 --> 00:05:52,830 сапраўды падкрэсліў дзяцей і не марозіва. 126 00:05:52,830 --> 00:05:55,360 І гэта проста не прадуктыўна для ўсіх. 127 00:05:55,360 --> 00:05:58,730 Так Мараль гэтай гісторыі ў тым, прыйсці крыху раней у працоўны час і добрыя рэчы 128 00:05:58,730 --> 00:06:00,310 адбудзецца. 129 00:06:00,310 --> 00:06:02,110 >> Акрамя таго, быць гатовымі, каб задаць пытанні. 130 00:06:02,110 --> 00:06:03,200 Ты ведаеш? 131 00:06:03,200 --> 00:06:05,420 Незалежна ад таго, ТАЯ, я думаю, казалі, 132 00:06:05,420 --> 00:06:10,710 мы атрымлівалі пару студэнтаў якія прыходзяць у чацвер на, быццам бы, 10:50 133 00:06:10,710 --> 00:06:15,100 ня прачытаўшы спецыфікацыю быўшы, як мне дапамагчы, дапамажы мне. 134 00:06:15,100 --> 00:06:18,200 На жаль, у той момант, ёсць не так шмат мы можам зрабіць, каб дапамагчы вам. 135 00:06:18,200 --> 00:06:19,590 Так што прыязджайце ў пачатку тыдня. 136 00:06:19,590 --> 00:06:22,040 Прыходзьце крыху раней, каб працоўны час. 137 00:06:22,040 --> 00:06:23,350 Будзьце гатовыя задаваць пытанні. 138 00:06:23,350 --> 00:06:25,310 Пераканайцеся, што вы, як студэнт, знаходзяцца там, дзе 139 00:06:25,310 --> 00:06:27,620 Вы павінны быць так, што ТП можа накіроўваць вас разам 140 00:06:27,620 --> 00:06:32,850 што і гадзіны офіса павінны быць вылучаныя для. 141 00:06:32,850 --> 00:06:37,380 >> Па-другое, так што я ведаю прафесараў хацеў здзівіць нас з тэстамі. 142 00:06:37,380 --> 00:06:39,439 Я быў прафесарам тыя як, йо, дарэчы, 143 00:06:39,439 --> 00:06:41,230 памятаеце, што сярэднетэрміновай ў вас ёсць наступны панядзелак. 144 00:06:41,230 --> 00:06:42,855 Так, я не ведаю, пра тое, што сярэднетэрміновай. 145 00:06:42,855 --> 00:06:45,630 Так што я збіраюся быць, што ТАЯ што нагадвае вам усё, што віктарыну 146 00:06:45,630 --> 00:06:47,270 0-- таму што, вы ведаеце, мы CS. 147 00:06:47,270 --> 00:06:50,730 Цяпер, калі мы зрабілі масівы, вы атрымаеце чаму гэта віктарына 0, не віктарыны 1, а? 148 00:06:50,730 --> 00:06:51,320 ДОБРА. 149 00:06:51,320 --> 00:06:52,490 О, я атрымаў некаторыя смяшкі на тым, што адзін. 150 00:06:52,490 --> 00:06:53,120 ДОБРА. 151 00:06:53,120 --> 00:06:59,710 >> Так віктарыны 0 будзе 14 кастрычніка, калі Вы знаходзіцеся ў раздзеле панядзелак-сераду 152 00:06:59,710 --> 00:07:02,920 і 15 кастрычніка, калі вы знаходзіцеся ў раздзел аўторак-чацвер. 153 00:07:02,920 --> 00:07:05,630 Гэта не распаўсюджваецца на тых з вас, у Гарвардзе 154 00:07:05,630 --> 00:07:10,350 who-- Я думаю, вы ўсё будзеце прымаць вашыя апытанні на 14-м. 155 00:07:10,350 --> 00:07:13,560 >> Так што, так, на наступным тыдні, калі Дэвід, у лекцыі, ідзе, 156 00:07:13,560 --> 00:07:15,747 ды, так пра гэта Тэст на наступным тыдні, вы ўсё 157 00:07:15,747 --> 00:07:17,580 не будуць шакаваныя, таму што вы прыйшлі ў раздзеле 158 00:07:17,580 --> 00:07:19,664 і вы ведаеце, што ваш Тэст 0 на працягу двух тыдняў. 159 00:07:19,664 --> 00:07:21,580 І мы будзем мець водгук сесій і ўсё. 160 00:07:21,580 --> 00:07:26,360 Так што не турбуйцеся аб баяцца за гэта. 161 00:07:26,360 --> 00:07:29,890 Любыя пытанні before-- якія-небудзь пытанні на ўсіх тычацца тэхнічных пытанняў, 162 00:07:29,890 --> 00:07:32,591 класіфікацыі, офісная гадзін, секцыі? 163 00:07:32,591 --> 00:07:33,090 Так. 164 00:07:33,090 --> 00:07:35,100 >> АЎДЫТОРЫЯ: Так віктарыны будзе на лекцыі? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Пэн: Так. 166 00:07:35,766 --> 00:07:39,460 Так віктарыны, я думаю, 60 хвілін, выдзеленыя ў гэтым часовым інтэрвале 167 00:07:39,460 --> 00:07:42,240 што вы будзеце проста ўзяць у лекцыйным зале. 168 00:07:42,240 --> 00:07:44,810 Такім чынам, вы не павінны прыйсці ў на, быццам бы, выпадковага 07:00 PM. 169 00:07:44,810 --> 00:07:46,140 Гэта ўсё добра. 170 00:07:46,140 --> 00:07:47,100 Так. 171 00:07:47,100 --> 00:07:50,060 Прахладны. 172 00:07:50,060 --> 00:07:50,840 >> Добра. 173 00:07:50,840 --> 00:07:54,330 Такім чынам, мы збіраемся, каб ўвесці паняцце для вас 174 00:07:54,330 --> 00:08:00,760 На гэтым тыдні, што Дэвід ўжо накшталт з закранулі ў лекцыі на мінулым тыдні. 175 00:08:00,760 --> 00:08:02,010 Гэта называецца GDB. 176 00:08:02,010 --> 00:08:05,570 І, як многія з вас, у той час як у курс напісання psets, 177 00:08:05,570 --> 00:08:09,981 заўважыў вялікую кнопку, якая кажа "Адладка" на верхняй часткі IDE? 178 00:08:09,981 --> 00:08:10,480 ДОБРА. 179 00:08:10,480 --> 00:08:13,770 Так што цяпер мы на самай справе атрымаць, каб раскапаць таямніца які то кнопкі на самай справе 180 00:08:13,770 --> 00:08:14,270 робіць. 181 00:08:14,270 --> 00:08:16,790 І я гарантую вам, што гэта прыгожая, прыгожая рэч. 182 00:08:16,790 --> 00:08:20,740 >> Так да гэтага часу, я думаю, там было дзве рэчы 183 00:08:20,740 --> 00:08:23,320 студэнты былі, як правіла, рабіць пры адладцы psets. 184 00:08:23,320 --> 00:08:27,635 Адзін з іх, яны альбо дадаць у Е () - так кожныя некалькі ліній, 185 00:08:27,635 --> 00:08:29,760 яны дадаюць у Е () - ой, што гэта зменная? 186 00:08:29,760 --> 00:08:32,551 О, што гэта зменная now-- і вы, здаецца, убачыць прагрэсаванне 187 00:08:32,551 --> 00:08:33,940 ваш код, як гэта працуе. 188 00:08:33,940 --> 00:08:37,030 Ці другі спосаб зрабіць дзяцей што яны проста напісаць цэлую рэч 189 00:08:37,030 --> 00:08:38,610 а затым перайсці, як гэта ў рэшце рэшт. 190 00:08:38,610 --> 00:08:39,970 Спадзяюся, гэта працуе. 191 00:08:39,970 --> 00:08:44,851 Я гарантую вам, GDB лепш чым абодва з гэтых метадаў. 192 00:08:44,851 --> 00:08:45,350 Так. 193 00:08:45,350 --> 00:08:46,980 Так што гэта будзе ваш новы лепшы сябар. 194 00:08:46,980 --> 00:08:51,780 Таму што гэта прыгожая рэч якія візуальна адлюстроўвае як 195 00:08:51,780 --> 00:08:54,850 што ваш код робіць у пэўны момант 196 00:08:54,850 --> 00:08:57,486 а таксама тое, што ўсе вашыя зменныя правядзення, 197 00:08:57,486 --> 00:08:59,610 як тое, што іх значэння, ў гэтай канкрэтнай кропцы. 198 00:08:59,610 --> 00:09:02,670 І такім чынам, вы можаце сапраўды ўсталяваць кропкі супыну ў кодзе. 199 00:09:02,670 --> 00:09:04,350 Вы можаце запусціць праз лінію за лініяй. 200 00:09:04,350 --> 00:09:07,324 І GDB будзе проста для Вы, адлюстроўваецца для вас, 201 00:09:07,324 --> 00:09:09,490 тое, што ўсе вашыя зменныя якія, што яны робяць, 202 00:09:09,490 --> 00:09:10,656 што адбываецца ў кодзе. 203 00:09:10,656 --> 00:09:13,240 І такім чынам, гэта так лягчэй ўбачыць 204 00:09:13,240 --> 00:09:17,120 што замест адбываецца з-тав PRINTF або запісваючы свае заявы. 205 00:09:17,120 --> 00:09:19,160 >> Такім чынам, мы будзем рабіць прыклад гэта пазней. 206 00:09:19,160 --> 00:09:20,660 Такім чынам, гэта здаецца трохі абстрактным. 207 00:09:20,660 --> 00:09:23,490 Не турбуйцеся, мы не будзем рабіць прыклады. 208 00:09:23,490 --> 00:09:29,170 І так, па сутнасці, тры найбуйнейшых, Найбольш выкарыстоўваюцца функцыі вам трэба ў GDB 209 00:09:29,170 --> 00:09:32,500 з'яўляюцца Далей, пераступіць і крок у кнопкі. 210 00:09:32,500 --> 00:09:34,860 Я збіраюся ўзначаліць ёсць, на самай справе, прама цяпер. 211 00:09:34,860 --> 00:09:40,930 >> Так можа вы, хлопцы, усе бачыць, што ці я павінен павялічыць трохі? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 У спіну, вы можаце бачыць, што? 214 00:09:44,470 --> 00:09:45,730 Ці павінен я павялічыць? 215 00:09:45,730 --> 00:09:46,480 Проста трохі? 216 00:09:46,480 --> 00:09:49,390 ОК, крута. 217 00:09:49,390 --> 00:09:50,280 Там мы ідзем. 218 00:09:50,280 --> 00:09:50,960 ДОБРА. 219 00:09:50,960 --> 00:09:57,000 >> Так што я, вось, мая Рэалізацыя для прагны. 220 00:09:57,000 --> 00:10:01,430 І ў той час як многія з вас, хлопцы пісалі прагныя у той час як завесы form--, што 221 00:10:01,430 --> 00:10:04,890 гэта цалкам прымальна спосаб зрабіць it-- іншы спосаб зрабіць гэта, каб проста 222 00:10:04,890 --> 00:10:06,280 падзяліць на модулю. 223 00:10:06,280 --> 00:10:09,290 Таму што тады вы можаце мець свой значэнне, а затым мець свой рэшту. 224 00:10:09,290 --> 00:10:11,150 І тады вы можаце проста дадаць усё гэта разам. 225 00:10:11,150 --> 00:10:13,390 Ці логіка, што я раблю тут сэнс для ўсіх, 226 00:10:13,390 --> 00:10:14,117 перш чым мы пачнем? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Выгляд? 229 00:10:17,980 --> 00:10:18,710 Прахладны. 230 00:10:18,710 --> 00:10:19,210 Выдатна. 231 00:10:19,210 --> 00:10:21,290 Гэта даволі сэксуальная частка кода, я б сказаў. 232 00:10:21,290 --> 00:10:23,502 Як я ўжо сказаў, Давід, у лекцыі, праз некаторы час, 233 00:10:23,502 --> 00:10:25,960 вы ўсё пачынаеце бачыць код як нешта, што прыгожа. 234 00:10:25,960 --> 00:10:29,950 І часам, калі вы бачыце прыгожы Код, гэта такі выдатны адчуванне. 235 00:10:29,950 --> 00:10:35,410 >> Так, аднак, у той час як гэты код вельмі прыгожа, гэта не працуе належным чынам. 236 00:10:35,410 --> 00:10:37,750 Так што давайце працаваць check50 на гэтым. 237 00:10:37,750 --> 00:10:39,440 Праверце 50 20-- уп. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Гэта pset2? 241 00:10:44,990 --> 00:10:46,870 Так. 242 00:10:46,870 --> 00:10:47,520 О, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 ДОБРА. 245 00:10:52,890 --> 00:10:53,900 Такім чынам, мы працаваць check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> І, як вы, хлопцы, можаце паглядзець тут, гэта няздольнасць пару выпадкаў. 248 00:11:07,170 --> 00:11:10,165 І для некаторых з вас, у Вядома рабіць свае праблемныя наборы, 249 00:11:10,165 --> 00:11:11,110 вы, як, ах, чаму яно не працуе. 250 00:11:11,110 --> 00:11:13,318 Чаму гэта працуе для некаторых значэння, але не для іншых? 251 00:11:13,318 --> 00:11:17,760 Ну, GDB будзе дапамагчы вам зразумець чаму гэтыя ўваходы не працавалі. 252 00:11:17,760 --> 00:11:18,320 >> ДОБРА. 253 00:11:18,320 --> 00:11:21,640 Такім чынам, давайце паглядзім, адно з правярае мяне няўдачу ў check50 254 00:11:21,640 --> 00:11:24,920 быў уваходнае значэнне 0,41. 255 00:11:24,920 --> 00:11:27,830 Такім чынам, правільны адказ, што вы павінны атрымліваць гэта 4. 256 00:11:27,830 --> 00:11:33,090 Але замест таго, што я раздрукоўкі гэта 3-н, што няправільна. 257 00:11:33,090 --> 00:11:36,190 Так што давайце проста запусціць ўручную, проста пераканайцеся, што check50 працуе. 258 00:11:36,190 --> 00:11:36,940 Давайце зробім ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ой, я павінен зрабіць прагны. 261 00:11:43,340 --> 00:11:43,840 Там мы ідзем. 262 00:11:43,840 --> 00:11:44,381 Цяпер ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Колькі належыць? 265 00:11:47,670 --> 00:11:49,550 Давайце зробім 0.41. 266 00:11:49,550 --> 00:11:52,590 І так, мы бачым тут што гэта выснова 3 267 00:11:52,590 --> 00:11:55,160 калі правільны адказ, На самай справе, павінна быць 4. 268 00:11:55,160 --> 00:12:01,460 Так што давайце ўвесці GDB і паглядзець, як мы можа ісці аб фіксацыі гэтай праблемы. 269 00:12:01,460 --> 00:12:03,992 >> Такім чынам, першы крок у заўсёды адладкі кода 270 00:12:03,992 --> 00:12:05,950 гэта ўсталяваць кропку супыну, або кропка, у якой вы 271 00:12:05,950 --> 00:12:09,079 хачу кампутара ці адладчык, каб пачаць глядзець. 272 00:12:09,079 --> 00:12:11,120 Так што, калі вы сапраўды не ведаю, што ваша праблема, 273 00:12:11,120 --> 00:12:14,670 Звычайна, тыповы, што мы хочам, каб зрабіць, гэта ўсталяваць кропку супыну на наш асноўны. 274 00:12:14,670 --> 00:12:18,520 Так што, калі вы, хлопцы, можаце бачыць гэта чырвоная кнопка побач, 275 00:12:18,520 --> 00:12:22,860 Так, гэта было мне усталяваўшы супыну для галоўнай функцыі. 276 00:12:22,860 --> 00:12:24,130 Я націсніце што. 277 00:12:24,130 --> 00:12:26,130 >> І тады я магу пайсці да маёй кнопкі Debug. 278 00:12:26,130 --> 00:12:27,036 Я ўдарыў гэтую кнопку. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Дазвольце мне аддаліцца, калі я магу. 281 00:12:36,555 --> 00:12:38,020 Там мы ідзем. 282 00:12:38,020 --> 00:12:40,730 Такім чынам, мы маем тут, панэль справа. 283 00:12:40,730 --> 00:12:43,680 Я прашу прабачэння, хлопцы ў спіну, вы не магу бачыць вельмі добра. 284 00:12:43,680 --> 00:12:49,090 Але па сутнасці, усё гэта права панэль робіць 285 00:12:49,090 --> 00:12:53,130 з'яўляецца адсочванне і выдзелены лінія, якая з'яўляецца радок кода 286 00:12:53,130 --> 00:12:56,640 што кампутар у дадзены момант, а таксама ўсе вашы зменныя 287 00:12:56,640 --> 00:12:57,600 сюды. 288 00:12:57,600 --> 00:13:00,487 >> Такім чынам, вы атрымалі цэнтаў, манеты, п, абвешчаныя на розныя рэчы 289 00:13:00,487 --> 00:13:01,070 ў гэтай кропцы. 290 00:13:01,070 --> 00:13:04,850 Не турбуйцеся, таму што ў нас няма на самай справе не ініцыялізацыі іх да любых пераменным яшчэ. 291 00:13:04,850 --> 00:13:07,200 Такім чынам, у вашым кампутары, ваш Кампутар проста бачачы, 292 00:13:07,200 --> 00:13:14,376 ой, 32767 быў апошні выкарыстоўваная функцыя гэтай прасторы памяці ў маім кампутары. 293 00:13:14,376 --> 00:13:16,000 І так вось дзе цэнтаў ў цяперашні час. 294 00:13:16,000 --> 00:13:19,360 Але ні што калі-то вы не запусціце код, яна павінна стаць ініцыялізацыі. 295 00:13:19,360 --> 00:13:24,110 >> Так давайце пройдзем, лінію лінія, тое, што тут адбываецца. 296 00:13:24,110 --> 00:13:25,350 ДОБРА. 297 00:13:25,350 --> 00:13:29,400 Так тут з'яўляюцца тры кнопкі, якія я толькі што патлумачыў. 298 00:13:29,400 --> 00:13:34,090 Вы павінны гуляць, ці функцыю Run, Кнопка, у вас ёсць Крок за кнопку, 299 00:13:34,090 --> 00:13:36,600 і ў вас таксама ёсць Крок у кнопкі. 300 00:13:36,600 --> 00:13:41,260 І, па сутнасці, усе тры ім проста прайсці праз код 301 00:13:41,260 --> 00:13:42,690 і рабіць розныя рэчы. 302 00:13:42,690 --> 00:13:45,680 >> Так звычайна, калі вы адладкі, мы не хочам, каб проста націснуць Play, 303 00:13:45,680 --> 00:13:47,930 таму Гульня будзе проста запусціць код да канца гэтага. 304 00:13:47,930 --> 00:13:49,070 І тады ў вас не будзе на самой справе ведаю, што ваша праблема 305 00:13:49,070 --> 00:13:51,432 ёсць, калі вы не ўсталюеце некалькі кропак супыну. 306 00:13:51,432 --> 00:13:53,890 Калі вы ўсталюеце некалькі кропак супыну, гэта будзе проста аўтаматычна 307 00:13:53,890 --> 00:13:56,030 бегчы ад адной кропкі супыну, да іншага, каб у наступны. 308 00:13:56,030 --> 00:13:58,030 Але ў гэтым выпадку мы ў толькі, што адзін, таму што мы 309 00:13:58,030 --> 00:13:59,970 хачу працаваць наш шлях зверху ўніз ўніз. 310 00:13:59,970 --> 00:14:04,830 Такім чынам, мы збіраемся, каб ігнараваць гэтую кнопку цяпер для мэтаў гэтай праграмы. 311 00:14:04,830 --> 00:14:08,230 >> Так Крок над функцыяй толькі пераступае кожнага радка 312 00:14:08,230 --> 00:14:11,510 і кажа вам, што кампутар робіць. 313 00:14:11,510 --> 00:14:14,630 Крок у функцыі ідзе у рэальнай функцыі 314 00:14:14,630 --> 00:14:16,000 гэта на радку кода. 315 00:14:16,000 --> 00:14:19,070 Так, напрыклад, як Е (), , Якая з'яўляецца функцыяй, праўда? 316 00:14:19,070 --> 00:14:21,980 Калі б я хацеў, каб фізічна крок у функцыі Е (), 317 00:14:21,980 --> 00:14:25,610 Я б на самой справе ісці ў частцы Код, дзе Е () была напісана і паглядзець, 318 00:14:25,610 --> 00:14:26,730 тое, што там адбываецца. 319 00:14:26,730 --> 00:14:29,924 >> Але, як правіла, мы мяркуем, што код, які мы даем вам працы. 320 00:14:29,924 --> 00:14:31,340 Мы мяркуем, што Е () працуе. 321 00:14:31,340 --> 00:14:33,170 Мы мяркуем, што GetInt () працуе. 322 00:14:33,170 --> 00:14:35,170 Такім чынам, няма ніякай неабходнасці крок у гэтых функцый. 323 00:14:35,170 --> 00:14:37,170 Але калі ёсць функцыі што вы пішаце самі 324 00:14:37,170 --> 00:14:39,060 што вы хочаце, каб праверыць , Што адбываецца, 325 00:14:39,060 --> 00:14:41,200 Вы хацелі б крок у гэтай функцыі. 326 00:14:41,200 --> 00:14:43,940 >> Так што цяпер мы толькі збіраемся пераступіць гэты кавалак кода. 327 00:14:43,940 --> 00:14:44,485 Такім чынам, давайце паглядзім. 328 00:14:44,485 --> 00:14:46,547 О, друк, "Аб Хай, як шмат змен належыць? " 329 00:14:46,547 --> 00:14:47,130 Мы не хвалюе. 330 00:14:47,130 --> 00:14:49,830 Мы ведаем, што працуе, такім чынам, мы крок за яе. 331 00:14:49,830 --> 00:14:53,290 >> Так п, якая з'яўляецца нашым паплавок, што мы ў initialized-- або declared-- 332 00:14:53,290 --> 00:14:56,810 наверсе, мы цяпер роўная, што GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Такім чынам, давайце пераступіць што. 334 00:14:57,810 --> 00:14:59,580 І мы бачым, на Ніжняя тут, праграма 335 00:14:59,580 --> 00:15:03,360 падахвочвае мяне да ўваходу значэнне. 336 00:15:03,360 --> 00:15:08,580 Такім чынам, давайце Увядзіце значэнне мы хочам праверыць тут, што 0,41. 337 00:15:08,580 --> 00:15:09,160 Выдатна. 338 00:15:09,160 --> 00:15:12,780 >> Так што цяпер N-- вы, хлопцы, бачыце тут, на bottom-- гэта 339 00:15:12,780 --> 00:15:15,140 stored--, таму што мы яшчэ не акругляецца, гэта 340 00:15:15,140 --> 00:15:19,540 захоўваюцца ў гэтым, як гігант паплавок, які ,4099999996, 341 00:15:19,540 --> 00:15:22,550 які знаходзіцца досыць блізка да нашага Мэты, прама зараз, да 0,41. 342 00:15:22,550 --> 00:15:26,090 І тады мы ўбачым у далейшым, як мы працягваць прасоўванне па праграме, 343 00:15:26,090 --> 00:15:29,850 Пасля тут, н стала круглявыя і цэнтаў стала 41. 344 00:15:29,850 --> 00:15:30,350 Выдатна. 345 00:15:30,350 --> 00:15:32,230 Такім чынам, мы ведаем, што праца нашай акруглення ст. 346 00:15:32,230 --> 00:15:34,700 Мы ведаем, што ў нас ёсць правільнае лік цэнтаў, 347 00:15:34,700 --> 00:15:36,990 так што мы ведаем, што гэта на самай справе не праблема. 348 00:15:36,990 --> 00:15:40,050 >> Такім чынам, мы па-ранейшаму крочыць у гэтай праграме. 349 00:15:40,050 --> 00:15:40,900 Мы ідзем сюды. 350 00:15:40,900 --> 00:15:46,139 І так пасля гэтага радка кода, мы павінны ведаць, колькі чвэрці ў нас ёсць. 351 00:15:46,139 --> 00:15:46,680 Мы пераступіць. 352 00:15:46,680 --> 00:15:52,040 І вы бачыце, мы, на самой справе, ёсць адзін чвэрць, таму што мы вычыталі 25 353 00:15:52,040 --> 00:15:53,790 з нашага пачатковага значэння 41. 354 00:15:53,790 --> 00:15:55,890 І ў нас ёсць 16 застаецца нашым цэнтаў. 355 00:15:55,890 --> 00:15:58,830 >> Ці разумее ўсё, як праграма пакрокавага 356 00:15:58,830 --> 00:16:02,980 і чаму цэнтаў стала 16 і чаму, у цяперашні час, манеты стаў 1? 357 00:16:02,980 --> 00:16:04,610 Усе наступнае, што логіка? 358 00:16:04,610 --> 00:16:05,110 Прахладны. 359 00:16:05,110 --> 00:16:07,860 Так, як у дадзены момант, Рабочая праграма, праўда? 360 00:16:07,860 --> 00:16:09,797 Мы ведаем, што гэта менавіта рабіць тое, што мы хочам. 361 00:16:09,797 --> 00:16:11,880 І мы на самай справе не павінны раздрукаваць, ах, які 362 00:16:11,880 --> 00:16:14,430 з'яўляецца цэнтаў на дадзены момант, што манеты ў гэтай кропцы. 363 00:16:14,430 --> 00:16:17,170 >> Мы працягваем ісці па праграме. 364 00:16:17,170 --> 00:16:18,100 Крок за. 365 00:16:18,100 --> 00:16:18,620 Прахладны. 366 00:16:18,620 --> 00:16:19,700 Мы ідзем па дзесяць цэнтаў. 367 00:16:19,700 --> 00:16:20,200 Выдатна. 368 00:16:20,200 --> 00:16:22,367 Мы бачым, што гэта заняло ад $ 0.10 за капейкі. 369 00:16:22,367 --> 00:16:23,450 І цяпер у нас ёсць дзве манеты. 370 00:16:23,450 --> 00:16:25,260 Гэта правільна. 371 00:16:25,260 --> 00:16:31,555 >> Пяройдзем драбяза, і мы бачым што мы атрымалі, тыя, што засталіся цэнтаў. 372 00:16:31,555 --> 00:16:32,680 Хм, гэта дзіўна. 373 00:16:32,680 --> 00:16:37,540 Да тут праграмы, я павінен быў каб аднялі мае драбяза. 374 00:16:37,540 --> 00:16:39,400 Можа быць, я проста не быў робіць гэты радок права. 375 00:16:39,400 --> 00:16:42,190 І, на жаль, вы можаце ўбачыць тут, таму што мы ведаем, 376 00:16:42,190 --> 00:16:44,360 што мы ўступаем праз лініі 32 і 33, 377 00:16:44,360 --> 00:16:50,560 вось дзе наша праграма няправільна было зменныя працаваць. 378 00:16:50,560 --> 00:16:55,136 Такім чынам, мы можам паглядзець і ўбачыць, аб, Я аднімання цэнтаў тут, 379 00:16:55,136 --> 00:16:57,010 але я на самой справе не дадаючы да маёй кошту манеты. 380 00:16:57,010 --> 00:16:57,860 Я дадаю да цэнтаў. 381 00:16:57,860 --> 00:17:00,234 І я не хачу, каб дадаць да цэнтаў, я хачу, каб дадаць да манетах. 382 00:17:00,234 --> 00:17:05,420 Так што, калі мы мяняем што манеты, мы атрымалі рабочую праграму. 383 00:17:05,420 --> 00:17:06,730 Я магу запусціць check50. 384 00:17:06,730 --> 00:17:11,063 Вы можаце проста выйсці з GDB правы тут і затым запусціць check50 зноў. 385 00:17:11,063 --> 00:17:11,938 Я мог бы проста зрабіць гэта. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Я павінен зрабіць прагны. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 І вось, гэта друк з правільнага адказу. 390 00:17:22,819 --> 00:17:26,569 >> Такім чынам, як вы, хлопцы, можаце бачыць, GDB гэта сапраўды магутны інструмент 391 00:17:26,569 --> 00:17:29,940 калі ў нас так шмат кода адбываецца, і так шмат зменных 392 00:17:29,940 --> 00:17:32,510 што гэта цяжка для нас, як чалавеку, каб адсочваць. 393 00:17:32,510 --> 00:17:35,360 Кампутар, у GDB адладчык, мае магчымасць 394 00:17:35,360 --> 00:17:37,020 каб адсочваць усе. 395 00:17:37,020 --> 00:17:40,480 Я ведаю, у Visionaire, вы, хлопцы, верагодна, магчыма, трапілі некаторыя памылкі сегментацыі 396 00:17:40,480 --> 00:17:43,150 таму што вы беглі па-за межамі вашага масіва. 397 00:17:43,150 --> 00:17:46,510 У прыкладзе Цэзара, гэта менавіта тое, што я тут рэалізавана. 398 00:17:46,510 --> 00:17:50,060 >> Так што я забыўся, каб праверыць што б адбылося, калі б я 399 00:17:50,060 --> 00:17:52,510 не маюць два аргументу каманднага радка. 400 00:17:52,510 --> 00:17:53,880 Я проста не ставілі ў гэтым чэку. 401 00:17:53,880 --> 00:17:57,380 І таму, калі я бягу Debug-- я паставіў мой супыну направа там. 402 00:17:57,380 --> 00:17:58,055 Я бягу Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> ДОБРА. 405 00:18:16,550 --> 00:18:17,050 Так. 406 00:18:17,050 --> 00:18:20,350 Так на самой справе, GDB павінен быў , Што сказаў мне, што 407 00:18:20,350 --> 00:18:22,300 быў збой сегментацыі там. 408 00:18:22,300 --> 00:18:24,883 Я не ведаю, што адбываецца тут, але, калі я пабег, 409 00:18:24,883 --> 00:18:25,590 яна працуе. 410 00:18:25,590 --> 00:18:29,410 Пры запуску радкоў кода праз і GDB можа проста раптам кінуць на вас, 411 00:18:29,410 --> 00:18:31,540 ісці і глядзець тое, што чырвоны памылка. 412 00:18:31,540 --> 00:18:33,930 Гэта вам скажу, эй, ты была памылку сегментацыі, 413 00:18:33,930 --> 00:18:38,550 Гэта азначае, што вы спрабавалі атрымаць доступ прастору ў масіве, што не існуе. 414 00:18:38,550 --> 00:18:39,050 Так. 415 00:18:39,050 --> 00:18:43,280 >> Такім чынам, у наступнай праблеме устаноўленыя на гэтым тыдні, вы, хлопцы, 416 00:18:43,280 --> 00:18:45,600 верагодна, будзе шмат зменныя з якая плавае вакол. 417 00:18:45,600 --> 00:18:48,560 Вы не збіраецеся быць упэўнены, што Усе яны маюць на ўвазе ў пэўны момант. 418 00:18:48,560 --> 00:18:53,560 Так GDB сапраўды дапаможа вам у высвятляючы тое, што яны ўсё зраўнаваўся 419 00:18:53,560 --> 00:18:55,940 і быць у стане бачыць, што візуальна. 420 00:18:55,940 --> 00:19:01,995 Хто блытаць ад таго, як небудзь з гэтага працаваў? 421 00:19:01,995 --> 00:19:02,495 Прахладны. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Добра. 424 00:19:10,620 --> 00:19:14,260 Такім чынам, пасля таго, што мы збіраецца пагрузіцца 425 00:19:14,260 --> 00:19:17,562 у чатыры розных тыпы гатункаў на гэтым тыдні. 426 00:19:17,562 --> 00:19:19,520 Як многія з вас, перш за ўсё, перш чым мы пачнем, 427 00:19:19,520 --> 00:19:23,020 прачытаў усю спецыфікацыю для pset3? 428 00:19:23,020 --> 00:19:23,824 ДОБРА. 429 00:19:23,824 --> 00:19:24,740 Я ганаруся вамі, хлопцы. 430 00:19:24,740 --> 00:19:29,110 Вось як палова класа, які значна больш, чым у мінулы раз. 431 00:19:29,110 --> 00:19:33,950 >> Так што выдатна, таму што, калі мы кажам пра змест 432 00:19:33,950 --> 00:19:36,170 у lecture-- або прабачце, у section-- Мне падабаецца 433 00:19:36,170 --> 00:19:38,210 звязаць шмат, што таму да таго, што гэта PSET 434 00:19:38,210 --> 00:19:40,210 і як вы хочаце, каб ажыццявіць, што ў вашым PSET. 435 00:19:40,210 --> 00:19:42,400 Так што, калі вы прыходзіце, якія маюць чытаць спецыфікацыі, ён будзе 436 00:19:42,400 --> 00:19:45,510 будзе нашмат прасцей для вас, каб зразумець, тое, што я кажу пра тое, калі я кажу, 437 00:19:45,510 --> 00:19:48,720 эй, гэта можа быць сапраўды добрае месца для рэалізацыі такога роду. 438 00:19:48,720 --> 00:19:52,870 Так што тыя, з вас, хто чытаў особое_разрешение ведаю, што, як частка вашага PSET, 439 00:19:52,870 --> 00:19:54,900 Вы будзеце мець, каб напісаць тып роду. 440 00:19:54,900 --> 00:19:58,670 Так што гэта можа быць вельмі карысна для многіх з вас сёння. 441 00:19:58,670 --> 00:20:01,760 >> Такім чынам, мы пачнем з таго, па сутнасці, самы просты тып 442 00:20:01,760 --> 00:20:04,580 з роду, выбар роду. 443 00:20:04,580 --> 00:20:06,800 Тыповы алгарытм як мы ісці аб гэтым 444 00:20:06,800 --> 00:20:10,460 is-- Давід праз іх усё ў лекцыя, так што я буду хутка рухацца ўздоўж 445 00:20:10,460 --> 00:20:13,900 here-- сутнасці, вы ёсць масіў значэнняў. 446 00:20:13,900 --> 00:20:17,170 І тады вы знойдзеце маленькі малокомплектных значэнне 447 00:20:17,170 --> 00:20:20,200 і вы памяняць гэта значэнне з першы малокомплектных значэнне. 448 00:20:20,200 --> 00:20:22,700 А потым вы проста паўтараць з астатняй частцы спісу. 449 00:20:22,700 --> 00:20:25,740 >> І вось нагляднае тлумачэнне пра тое, як гэта будзе працаваць. 450 00:20:25,740 --> 00:20:30,460 Так, напрыклад, калі мы павінны былі пачаць з масівам з пяці элементаў, індэкс 451 00:20:30,460 --> 00:20:35,910 Ад 0 да 4, з 3, 5, 2, 6, і 4 значэння змешчаны ў array-- гэта прама цяпер, 452 00:20:35,910 --> 00:20:38,530 мы проста будзем лічыць, што яны ўсе без сартавання 453 00:20:38,530 --> 00:20:41,130 таму што мы не зведалі ў адваротным выпадку. 454 00:20:41,130 --> 00:20:44,130 >> Бо выбар роду будзе праца, што б перш 455 00:20:44,130 --> 00:20:46,800 праходзяць праз цалкам у малокомплектных масіва. 456 00:20:46,800 --> 00:20:49,120 Было б выбраць найменшае значэнне. 457 00:20:49,120 --> 00:20:51,750 У гэтым выпадку, 3, правы Цяпер, з'яўляецца найменшай. 458 00:20:51,750 --> 00:20:52,680 Ён атрымлівае да 5. 459 00:20:52,680 --> 00:20:55,620 Няма, 5 не болей than-- або прабачце, не менш за 3 than--. 460 00:20:55,620 --> 00:20:57,779 Такім чынам, мінімальнае значэнне па-ранейшаму 3. 461 00:20:57,779 --> 00:20:58,695 І тады вы атрымаеце 2. 462 00:20:58,695 --> 00:21:00,990 Кампутар бачыць, ой, 2 менш, чым 3. 463 00:21:00,990 --> 00:21:02,750 Цяпер 2 павінна быць мінімальная значэнне. 464 00:21:02,750 --> 00:21:06,630 І так 2 свопы з гэтай першай велічыні. 465 00:21:06,630 --> 00:21:10,702 >> Такім чынам, пасля аднаго праходу, мы сапраўды бачым што 2 і 3 мяняюцца месцамі. 466 00:21:10,702 --> 00:21:13,910 І мы толькі збіраемся працягваць рабіць Гэта зноў з астатняй часткай масіва. 467 00:21:13,910 --> 00:21:17,660 Такім чынам, мы збіраемся, каб проста запусціць праз Апошнія чатыры індэксы масіва. 468 00:21:17,660 --> 00:21:20,670 Мы ўбачым, што 3 наступны мінімальнае значэнне. 469 00:21:20,670 --> 00:21:23,240 Такім чынам, мы збіраемся, каб памяняць што з 4. 470 00:21:23,240 --> 00:21:26,900 І тады мы проста будзем працягваць не праходзіць праз да, у рэшце рэшт, вы 471 00:21:26,900 --> 00:21:33,730 трапіць у адсартаваным масіве, у якім 2, 3, 4, 5, 6 і ўсе сартуюцца. 472 00:21:33,730 --> 00:21:37,530 Усе разумеюць Ці логіку пра тое, як працуе выбар роду? 473 00:21:37,530 --> 00:21:39,669 >> Вы проста ёсць нейкі мінімальнага значэння. 474 00:21:39,669 --> 00:21:41,210 Вы адсочваць, што гэта такое. 475 00:21:41,210 --> 00:21:45,170 І кожны раз, калі вы знойдзеце яго, вы памяняць яго з першым значэннем у array-- 476 00:21:45,170 --> 00:21:48,740 або, не першы value-- наступнае значэнне ў масіве. 477 00:21:48,740 --> 00:21:50,150 Прахладны. 478 00:21:50,150 --> 00:21:55,460 >> Такім чынам, як вы, хлопцы, накшталт бачыў з мімаходам, 479 00:21:55,460 --> 00:21:58,450 мы збіраемся псевдокод гэта. 480 00:21:58,450 --> 00:22:02,510 Так што, калі вы, хлопцы, у задняй хочаце ўтвараюць групу, кожны ў табліцы 481 00:22:02,510 --> 00:22:06,170 могуць утвараць мала партнёра, я збіраюся каб даць вам, хлопцы, як тры хвіліны 482 00:22:06,170 --> 00:22:08,190 проста казаць праз логіка, на англійскай мове, 483 00:22:08,190 --> 00:22:14,161 аб тым, як мы маглі б рэалізаваць псевдокод напісаць выбару роду. 484 00:22:14,161 --> 00:22:14,910 І ёсць цукеркі. 485 00:22:14,910 --> 00:22:16,118 Калі ласка, прыходзьце і атрымаеце цукерку. 486 00:22:16,118 --> 00:22:19,520 Калі вы знаходзіцеся ў спіне і вы хочаце цукеркі, я магу кінуць цукеркі на вас. 487 00:22:19,520 --> 00:22:22,850 На самай справе, зрабіць you-- халаднавата. 488 00:22:22,850 --> 00:22:23,552 О, прабачце. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 ДОБРА. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Так што, калі мы хацелі б, а клас, запісы псевдокод 493 00:25:27,140 --> 00:25:30,466 пра тое, як можна было б падысці гэтая праблема, проста не саромейцеся. 494 00:25:30,466 --> 00:25:32,340 Я проста хадзіць, а ў парадку, спытаеце групы 495 00:25:32,340 --> 00:25:35,065 на наступным радку што мы павінны рабіць. 496 00:25:35,065 --> 00:25:37,840 Так што, калі вы, хлопцы, жадаеце, каб пачаць выключаны, то, што першае, што 497 00:25:37,840 --> 00:25:40,600 рабіць, калі вы спрабуеце ажыццявіць спосаб вырашыць гэтую праграму 498 00:25:40,600 --> 00:25:43,480 выбарачна адсартаваць спіс? 499 00:25:43,480 --> 00:25:46,349 Давайце выкажам здагадку, што мы толькі што ёсць масіў, добра? 500 00:25:46,349 --> 00:25:49,088 >> АЎДЫТОРЫЯ: Вы хочаце, каб стварыць некаторыя роду [неразборліва], што вы 501 00:25:49,088 --> 00:25:50,420 праходзіць праз увесь масіве. 502 00:25:50,420 --> 00:25:51,128 >> ANDI Пэн: Права. 503 00:25:51,128 --> 00:25:54,100 Такім чынам, вы будзеце жадаць, каб ітэрацыі праз кожны прасторы, правільна? 504 00:25:54,100 --> 00:26:05,490 Так, вялікі. 505 00:26:05,490 --> 00:26:08,600 Калі вы, хлопцы, жадаеце, каб даць мне Наступны line-- так, у спіну. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> АЎДЫТОРЫЯ: Праверце іх усё для самых маленькіх. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Пэн: Там мы ідзем. 509 00:26:14,248 --> 00:26:17,438 Таму мы хочам, каб прайсці і праверыць бачыць, што мінімальнае значэнне, праўда? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Я збіраюся скарачаць, што "мін." 512 00:26:24,840 --> 00:26:27,658 Што вы, хлопцы, жадаеце рабіць пасля Вы знайшлі мінімальнае значэнне? 513 00:26:27,658 --> 00:26:28,533 >> АЎДЫТОРЫЯ: [неразборліва] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Пэн: Так што вы збіраецеся хочуць пераключыць яго з першага гэтым масіве, 516 00:26:33,150 --> 00:26:33,650 дакладна? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Гэта пачатак, я збіраюся сказаць. 519 00:26:46,850 --> 00:26:47,220 Добра. 520 00:26:47,220 --> 00:26:50,386 Так што цяпер вы памяняліся першым Адзін з іх, што вы хочаце зрабіць пасля гэтага? 521 00:26:50,386 --> 00:26:54,840 Так што цяпер мы ведаем, што гэта адно тут павінны быць найменшае значэнне, ці не так? 522 00:26:54,840 --> 00:26:58,310 Тады ў вас ёсць дадатковы адпачынак масіва, што гэта малокомплектных. 523 00:26:58,310 --> 00:27:01,569 Так што вы хочаце зрабіць тут, калі вы хлопцы, жадаеце, каб даць мне наступны радок? 524 00:27:01,569 --> 00:27:04,610 АЎДЫТОРЫЯ: Такім чынам вы хочаце перабраць праз астатнюю частку масіва. 525 00:27:04,610 --> 00:27:05,276 ANDI Пэн: Так. 526 00:27:05,276 --> 00:27:09,857 І так, што ж пераборы выгляд мае на ўвазе мы, напэўна, трэба? 527 00:27:09,857 --> 00:27:10,440 Які тып of-- 528 00:27:10,440 --> 00:27:12,057 >> АЎДЫТОРЫЯ: О, дадатковая зменная? 529 00:27:12,057 --> 00:27:13,890 ANDI Пэн: Магчыма іншы цыкл, ці не так? 530 00:27:13,890 --> 00:27:28,914 Такім чынам, мы, верагодна, захочуць для перабору through-- выдатна. 531 00:27:28,914 --> 00:27:31,830 І тады вы будзеце ісці назад і верагодна, праверыць мінімум раз 532 00:27:31,830 --> 00:27:32,100 дакладна? 533 00:27:32,100 --> 00:27:34,975 І вы збіраецеся паўтараць гэта, таму што завесы толькі збіраецца 534 00:27:34,975 --> 00:27:36,010 трымаць працуе, праўда? 535 00:27:36,010 --> 00:27:39,190 >> Такім чынам, як вы, хлопцы, можаце бачыць, мы проста агульны псевдокод 536 00:27:39,190 --> 00:27:41,480 аб тым, як мы хочам, каб гэтая праграма глядзець. 537 00:27:41,480 --> 00:27:46,646 Гэта ітэрацыя тут, тое, што мы як правіла, трэба напісаць у кодзе 538 00:27:46,646 --> 00:27:49,270 калі мы хочам, каб ітэрацыі праз Масіў, які тып структуры? 539 00:27:49,270 --> 00:27:51,030 Я думаю, Кристабель ўжо казаў гэта раней. 540 00:27:51,030 --> 00:27:51,500 >> Залы: для завесы. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Пэн: для цыкла? 542 00:27:52,160 --> 00:27:52,770 Дакладна. 543 00:27:52,770 --> 00:27:56,060 Так гэта, напэўна, будзе цыкл. 544 00:27:56,060 --> 00:27:59,240 Што такое праверка тут збіраецца значыць? 545 00:27:59,240 --> 00:28:02,536 Як правіла, калі вы хочаце, каб праверыць калі што-небудзь што-небудзь else-- 546 00:28:02,536 --> 00:28:03,270 >> АЎДЫТОРЫЯ: Калі. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: калі, праўда? 548 00:28:06,790 --> 00:28:10,790 А потым своп тут, мы будзем перайсці пазней, таму што Давіда 549 00:28:10,790 --> 00:28:12,770 прайшоў праз гэта ў лекцыі, а таксама. 550 00:28:12,770 --> 00:28:14,580 А потым другі ітэрацыі implies-- 551 00:28:14,580 --> 00:28:15,120 >> АЎДЫТОРЫЯ: Яшчэ цыкл. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Пэн: --another цыкл, дакладна. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Так што, калі мы шукаем на гэта правільна, мы 555 00:28:22,000 --> 00:28:24,680 можна ўбачыць, што мы, верагодна, спатрэбіцца укладзены цыкл 556 00:28:24,680 --> 00:28:28,330 з умоўным заявай у там а затым фактычнае кавалак кода, які гэта 557 00:28:28,330 --> 00:28:31,360 збіраецца памяняць значэння. 558 00:28:31,360 --> 00:28:35,980 Так што я проста наогул напісана псевдокод код тут. 559 00:28:35,980 --> 00:28:38,910 І тады мы на самай справе адбываецца фізічна, як клас, 560 00:28:38,910 --> 00:28:40,700 паспрабаваць ажыццявіць гэта сёння. 561 00:28:40,700 --> 00:28:42,486 Давайце вернемся ў гэты IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Ой-ой. 564 00:28:50,230 --> 00:28:51,754 Чаму гэта не-- там. 565 00:28:51,754 --> 00:28:52,253 ДОБРА. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Выбачайце, дазвольце мне паспрабаваць павялічыць трохі больш. 568 00:28:57,500 --> 00:28:59,310 Там мы ідзем. 569 00:28:59,310 --> 00:29:05,060 Усё, што я раблю тут, я стварыў Праграма называецца "выбар / sort.c." 570 00:29:05,060 --> 00:29:10,860 Я стварыў масіў з дзевяці Значэння, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 У цяперашні час, як вы можаце Разумееце, яны не ўпарадкаваны. 572 00:29:14,370 --> 00:29:17,880 н будзе лік, кажа вам суму значэнняў 573 00:29:17,880 --> 00:29:18,920 ў вас ёсць у вашым масіве. 574 00:29:18,920 --> 00:29:20,670 У гэтым выпадку, у нас ёсць дзевяць значэнняў. 575 00:29:20,670 --> 00:29:23,760 І я толькі што атрымаў цыкл тут што выводзіць малокомплектных масіў. 576 00:29:23,760 --> 00:29:28,370 >> І ў рэшце рэшт, я таксама атрымаў для цыкл, які друкуе яго зноў. 577 00:29:28,370 --> 00:29:32,070 Так, тэарэтычна, калі гэтая праграма працуе правільна, у рэшце рэшт, 578 00:29:32,070 --> 00:29:35,670 Вы павінны ўбачыць друкаваны цыкл у якім 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 усё правільна ў парадку. 580 00:29:39,310 --> 00:29:43,410 >> Такім чынам, мы атрымалі наш псевдокод тут. 581 00:29:43,410 --> 00:29:46,090 Хто-небудзь хоча, мэтай якіх я проста пайду прасіць volunteers-- 582 00:29:46,090 --> 00:29:49,540 скажыце мне дакладна, што калі ўвесці мы хочам, каб, па-першае, проста ітэрацыі 583 00:29:49,540 --> 00:29:52,840 па пачатак гэтага масіва? 584 00:29:52,840 --> 00:29:55,204 Што радок кода я верагодна, тут трэба? 585 00:29:55,204 --> 00:29:56,990 >> АЎДЫТОРЫЯ: [неразборліва] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Пэн: Так, адчуваю, бясплатна, мэтай якіх прабачце, вам 587 00:29:59,010 --> 00:30:02,318 не павінны стаяць up-- пачуццё свабодна падняць свой голас няшмат. 588 00:30:02,318 --> 00:30:08,190 >> АЎДЫТОРЫЯ: Для INT я роўная 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Пэн: Так, добра. 590 00:30:10,690 --> 00:30:15,220 >> АЎДЫТОРЫЯ: я менш даўжыні масіва. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Пэн: Так што майце на супраць тут, таму што мы 592 00:30:19,630 --> 00:30:23,060 ня ёсьць функцыя, якая кажа нам даўжыня масіва, 593 00:30:23,060 --> 00:30:25,790 у нас ужо ёсць Значэнне, якое захоўвае, што. 594 00:30:25,790 --> 00:30:27,920 Дакладна? 595 00:30:27,920 --> 00:30:31,010 Яшчэ адна рэч, каб трымаць у mind-- ў масіве 596 00:30:31,010 --> 00:30:33,940 з дзевяці значэнняў, якія індэксы? 597 00:30:33,940 --> 00:30:38,720 Давайце проста скажам, гэты масіў 0 да 3. 598 00:30:38,720 --> 00:30:41,500 Вы бачыце, што апошні Індэкс самой справе 3. 599 00:30:41,500 --> 00:30:45,530 Гэта не 4, хоць ёсць чатыры значэння ў масіве. 600 00:30:45,530 --> 00:30:49,866 >> Так тут, мы павінны быць вельмі асцярожныя, таго, што наша ўмова для даўжыні 601 00:30:49,866 --> 00:30:50,490 будзе. 602 00:30:50,490 --> 00:30:51,948 >> АЎДЫТОРЫЯ: не было б н мінус 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Пэн: Гэта адбываецца п мінус 1, дакладна. 604 00:30:54,440 --> 00:30:57,379 Ці мае гэта сэнс, чаму гэта п мінус 1, ўсё? 605 00:30:57,379 --> 00:30:58,920 Гэта таму, што масівы роўныя нулю, індэксаваная. 606 00:30:58,920 --> 00:31:02,010 Яны пачынаюцца з 0 і запусціць да н мінус 1. 607 00:31:02,010 --> 00:31:03,210 Так, гэта крыху больш складана. 608 00:31:03,210 --> 00:31:03,730 ДОБРА. 609 00:31:03,730 --> 00:31:05,929 І then-- 610 00:31:05,929 --> 00:31:08,054 АЎДЫТОРЫЯ: Isnt'1, што ўжо паклапаціліся, хоць, 611 00:31:08,054 --> 00:31:11,400 , Проста не кажу "менш або роўна "і проста кажу" менш "? 612 00:31:11,400 --> 00:31:13,108 >> ANDI Пэн: Гэта вельмі добрае пытанне. 613 00:31:13,108 --> 00:31:13,630 Так што, так. 614 00:31:13,630 --> 00:31:17,410 Але таксама, такім чынам, што мы рэалізацыі праверкі права, 615 00:31:17,410 --> 00:31:19,120 вам трэба параўнаць два значэння. 616 00:31:19,120 --> 00:31:21,009 Такім чынам, вы на самой справе хочаце, каб пакінуць "на" пусты. 617 00:31:21,009 --> 00:31:23,050 Таму што, калі вы параўнайце гэта адно, вы не збіраецеся 618 00:31:23,050 --> 00:31:25,530 ёсць што-небудзь пасля яго параўнаць, праўда? 619 00:31:25,530 --> 00:31:27,460 Так. 620 00:31:27,460 --> 00:31:29,297 Так я ++. 621 00:31:29,297 --> 00:31:30,380 Давайце дадамо нашы дужкі ст. 622 00:31:30,380 --> 00:31:30,880 Упс. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Выдатна. 625 00:31:34,710 --> 00:31:39,117 Такім чынам, мы маем пачатак нашай знешняй завесы. 626 00:31:39,117 --> 00:31:41,450 Так што цяпер мы, верагодна, хочаце, каб стварыць зменную для захоўвання 627 00:31:41,450 --> 00:31:43,085 трэк найменшай значэннем, праўда? 628 00:31:43,085 --> 00:31:45,751 Хто-небудзь хоча, каб даць мне радок кода, якая будзе гэта рабіць? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Што нам трэба, калі мы збіраемся хочуць, каб захаваць што-небудзь? 631 00:31:53,570 --> 00:31:55,047 >> Права. 632 00:31:55,047 --> 00:31:57,630 Можа быць, лепш, што назва будзе be-- "Тэмп" цалкам works-- 633 00:31:57,630 --> 00:32:00,655 можа быць, больш трапна назваў бы, калі мы хочам, каб маленькі value-- 634 00:32:00,655 --> 00:32:01,624 >> АЎДЫТОРЫЯ: Мін. 635 00:32:01,624 --> 00:32:02,790 ANDI Пэн: мін, там мы ідзем. 636 00:32:02,790 --> 00:32:05,230 мін будзе добра. 637 00:32:05,230 --> 00:32:08,340 І вось што нам рабіць хачу, каб ініцыялізаваць яго? 638 00:32:08,340 --> 00:32:09,620 Гэта крыху больш складана. 639 00:32:09,620 --> 00:32:13,580 Таму што цяпер на пачатак гэтага масіва, 640 00:32:13,580 --> 00:32:15,730 Вы яшчэ не глядзелі ні на што, ці не так? 641 00:32:15,730 --> 00:32:19,200 Так што, аўтаматычна, калі мы толькі на я роўная 0, 642 00:32:19,200 --> 00:32:22,302 тое, што мы хочам, каб ініцыялізаваць наш першы мінімальнае значэнне для? 643 00:32:22,302 --> 00:32:22,802 АЎДЫТОРЫЯ: я. 644 00:32:22,802 --> 00:32:24,790 ANDI Пэн: я, дакладна. 645 00:32:24,790 --> 00:32:27,040 Christabel, чаму мы хочам ініцыялізаваць яго я? 646 00:32:27,040 --> 00:32:28,510 >> АЎДЫТОРЫЯ: Таму што, ну, мы, пачынаючы з 0. 647 00:32:28,510 --> 00:32:31,660 Так, таму што мы не маем нічога, каб параўнаць гэта, мінімум будзе ў канчатковым выніку 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Пэн: Точно. 649 00:32:32,451 --> 00:32:34,400 Такім чынам, яна зусім дакладна. 650 00:32:34,400 --> 00:32:36,780 Таму што ў нас на самай справе не паглядзеў на што-небудзь яшчэ, 651 00:32:36,780 --> 00:32:38,680 мы не ведаем, што наша мінімальнае значэнне. 652 00:32:38,680 --> 00:32:41,960 Мы хочам, каб проста ініцыялізаваць яго я, што, у цяперашні час, прама тут. 653 00:32:41,960 --> 00:32:44,750 І, як мы па-ранейшаму рухацца ўніз гэты масіў, 654 00:32:44,750 --> 00:32:48,122 мы ўбачым, што, адзін з Дадатковы праход, я павялічвае. 655 00:32:48,122 --> 00:32:49,830 І так у гэтай кропцы, я, верагодна, будзе 656 00:32:49,830 --> 00:32:52,329 хочуць быць мінімальным, таму што гэта будзе што заўгодна 657 00:32:52,329 --> 00:32:54,520 пачатак неотсортированной масіва. 658 00:32:54,520 --> 00:32:55,270 Прахладны. 659 00:32:55,270 --> 00:32:58,720 >> Так што цяпер мы хочам, каб дадаць для цыклу тут гэта 660 00:32:58,720 --> 00:33:03,225 збіраецца паўтараць праз малокомплектных або астатняя частка гэтага масіва. 661 00:33:03,225 --> 00:33:05,808 Хто-небудзь хоча, каб даць мне радок кода, якая будзе гэта рабіць? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- што нам трэба тут? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Што збіраецца ісці ў гэтым для цыкла? 666 00:33:18,820 --> 00:33:19,465 Так. 667 00:33:19,465 --> 00:33:21,590 АЎДЫТОРЫЯ: Такім чынам, мы хацелі б мець розны лік, 668 00:33:21,590 --> 00:33:25,080 таму што мы бяжым да канца масіва замест I, так што, магчыма 669 00:33:25,080 --> 00:33:25,760 J. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Пэн: Так, J гучыць добра для мяне. 671 00:33:27,301 --> 00:33:27,850 Роўна? 672 00:33:27,850 --> 00:33:33,930 >> АЎДЫТОРЫЯ: Так бы я плюс 1, таму што Вы пачынаеце на наступным значэння. 673 00:33:33,930 --> 00:33:40,395 А потым да end-- так зноў, J з'яўляецца менш, чым п мінус 1, а затым J ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Пэн: Выдатна. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> А потым тут, мы збіраемся хочаце каб праверыць, калі наша ўмова выконваецца, 677 00:33:52,750 --> 00:33:53,250 дакладна? 678 00:33:53,250 --> 00:33:55,740 Таму што вы хочаце, каб змяніць мінімальнае значэнне 679 00:33:55,740 --> 00:33:58,700 калі гэта на самай справе менш, чым вы параўноўваеце яго, праўда? 680 00:33:58,700 --> 00:34:01,146 Так што мы збіраемся хочаце тут? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Праверце, каб бачыць. 683 00:34:04,897 --> 00:34:06,730 Які выгляд заявы мы, верагодна, будзе 684 00:34:06,730 --> 00:34:08,389 ці хочаце выкарыстоўваць, калі мы хачу сёе-тое праверыць? 685 00:34:08,389 --> 00:34:09,360 >> АЎДЫТОРЫЯ: калі заяву. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: калі заяву. 687 00:34:10,485 --> 00:34:13,155 Так if-- і тое, што будзе ўмова, што мы хочам у 688 00:34:13,155 --> 00:34:13,988 нашай, калі заяву? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> АЎДЫТОРЫЯ: Калі значэнне J менш, чым значэнне i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Пэн: Точно. 692 00:34:24,600 --> 00:34:27,480 Так if-- так што гэта масіў называецца "масіў". 693 00:34:27,480 --> 00:34:27,980 Выдатна. 694 00:34:27,980 --> 00:34:30,465 Так што, калі array-- што гэта было? 695 00:34:30,465 --> 00:34:31,090 Скажыце, што яшчэ раз. 696 00:34:31,090 --> 00:34:39,590 >> АЎДЫТОРЫЯ: Калі масіў-J менш Масіў-я, то мы б змяніць мін. 697 00:34:39,590 --> 00:34:41,590 Такім чынам, мін будзе к. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Пэн: Ці мае гэта сэнс? 700 00:34:47,249 --> 00:34:48,670 ДОБРА. 701 00:34:48,670 --> 00:34:52,929 А цяпер сюды, мы на самай справе хочам рэалізаваць абмен, праўда? 702 00:34:52,929 --> 00:34:58,285 Так Нагадаем, што ў лекцыі, што Давід, калі ён спрабаваў абмяняць the--, што было 703 00:34:58,285 --> 00:34:59,996 it-- апельсінавы сок і milk-- 704 00:34:59,996 --> 00:35:01,150 >> АЎДЫТОРЫЯ: Гэта было агідна. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Пэн: Так, гэта было свайго роду брута. 706 00:35:02,816 --> 00:35:05,310 Але гэта было даволі добра Канцэпцыя дэманстрацыі час. 707 00:35:05,310 --> 00:35:08,430 Так што думайце аб вашых каштоўнасцяў тут. 708 00:35:08,430 --> 00:35:10,794 Вы атрымалі масіў з мін, масіў I, 709 00:35:10,794 --> 00:35:12,460 або тое, што мы спрабавалі памяняць тут. 710 00:35:12,460 --> 00:35:15,310 І вы, верагодна, не можа заліць іх у адзін з адным, у той жа час, так? 711 00:35:15,310 --> 00:35:17,180 Так што мы збіраемся каб трэба стварыць тут 712 00:35:17,180 --> 00:35:19,126 для таго, каб правільна памяняць значэння? 713 00:35:19,126 --> 00:35:19,820 >> АЎДЫТОРЫЯ: часовая пераменная. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Пэн: часовая пераменная. 715 00:35:21,370 --> 00:35:22,570 Так давайце зробім Int тэмп. 716 00:35:22,570 --> 00:35:25,681 Глядзі, гэта было б лепш Час, мэтай якіх эй, што гэта было? 717 00:35:25,681 --> 00:35:26,180 ДОБРА. 718 00:35:26,180 --> 00:35:29,800 Так што гэта было б лепш час назваць зменную "Тэмп". 719 00:35:29,800 --> 00:35:30,730 Так давайце зробім Int тэмп. 720 00:35:30,730 --> 00:35:32,563 Што мы збіраемся SET TEMP роўную тут? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 АЎДЫТОРЫЯ: Мін? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Пэн: Гэта крыху больш складана. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Гэта на самай справе не мае значэння, у рэшце рэшт. 727 00:35:44,880 --> 00:35:47,690 Гэта не мае значэння, што заказ вы вырашыце памяняць у 728 00:35:47,690 --> 00:35:50,862 так доўга, як вы робіце, што вы адсочваць тое, што вы падпампоўкі. 729 00:35:50,862 --> 00:35:52,250 >> АЎДЫТОРЫЯ: Гэта можа быць масіў я. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Пэн: Так, давайце зробім масіў-I. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 І тады тое, што наступная радок кода мы хочам мець тут? 733 00:35:59,305 --> 00:36:00,680 АЎДЫТОРЫЯ: масіў я роўная масіва-J. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Пэн: І, нарэшце? 736 00:36:08,070 --> 00:36:12,070 АЎДЫТОРЫЯ: масіў J роўная масіва я. 737 00:36:12,070 --> 00:36:14,525 АЎДЫТОРЫЯ: Ці масіва J роўна Масіў-temp-- або тэмпературы. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI Пэн: ОК. 740 00:36:19,430 --> 00:36:21,510 Так што давайце працаваць і паглядзім, калі ён будзе працаваць. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Дзе, што адбываецца? 743 00:36:39,335 --> 00:36:40,210 О, што гэта праблема. 744 00:36:40,210 --> 00:36:44,320 Глядзі, на лініі 40, мы спрабуе выкарыстоўваць масіў-J? 745 00:36:44,320 --> 00:36:47,022 Але дзе J існуе толькі ў? 746 00:36:47,022 --> 00:36:48,402 >> АЎДЫТОРЫЯ: На працягу цыклу. 747 00:36:48,402 --> 00:36:49,110 ANDI Пэн: Права. 748 00:36:49,110 --> 00:36:51,730 Так што мы збіраемся трэба зрабіць? 749 00:36:51,730 --> 00:36:53,170 >> АЎДЫТОРЫЯ: Вызначыць яго межамі the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 АЎДЫТОРЫЯ: Так, я думаю, вы павінны выкарыстаць іншы, калі заяву, ці не так? 752 00:37:00,610 --> 00:37:05,230 Так як, калі minimum-- Усё ў парадку, дайце мне падумаць. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Пэн: Хлопцы, паспрабуйце зірнуць Давайце 755 00:37:09,990 --> 00:37:11,270 см, што гэта тое, што мы можам зрабіць тут? 756 00:37:11,270 --> 00:37:11,811 >> АЎДЫТОРЫЯ: ОК. 757 00:37:11,811 --> 00:37:15,900 Такім чынам, калі мінімальная не роўная j-- так што калі мінімальная яшчэ i-- 758 00:37:15,900 --> 00:37:17,570 то мы б не памяняць. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Пэн: Ці значыць гэта, роўна я? 761 00:37:24,712 --> 00:37:25,920 Што вы хочаце сказаць тут? 762 00:37:25,920 --> 00:37:30,494 >> АЎДЫТОРЫЯ: Ці так, калі мінімум не роўнае I, да. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI Пэн: ОК. 765 00:37:40,210 --> 00:37:42,040 Ну, што вырашае, накшталт, нашы праблемы. 766 00:37:42,040 --> 00:37:47,265 Але гэта яшчэ не вырашыць Праблема што адбудзецца, калі j-- так J 767 00:37:47,265 --> 00:37:49,890 не існуе па-за ім, тое, што Вы хочаце, каб мы з ім рабіць? 768 00:37:49,890 --> 00:37:50,698 Аб'явіць яго межамі? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Давайце паспрабуем гэта працуе. 771 00:38:02,730 --> 00:38:04,435 Ой-ой. 772 00:38:04,435 --> 00:38:06,200 Наша роду не працуе. 773 00:38:06,200 --> 00:38:10,060 >> Як вы можаце бачыць, нашу пачатковую Масіў былі тыя значэння. 774 00:38:10,060 --> 00:38:14,800 І пасля гэтага ён павінен мець быў у 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Гэта не працуе. 776 00:38:15,530 --> 00:38:16,030 Ах. 777 00:38:16,030 --> 00:38:17,184 Што мы робім? 778 00:38:17,184 --> 00:38:17,850 АЎДЫТОРЫЯ: Адладка. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Пэн: Добра, мы можам паспрабаваць. 781 00:38:23,370 --> 00:38:25,030 Мы можам адладзіць. 782 00:38:25,030 --> 00:38:26,042 Агледзіце няшмат. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Давайце ўсталюем наш пункт супыну. 785 00:38:33,656 --> 00:38:37,280 Давайце like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Так, таму што мы ўжо ведаем, што гэтыя лініі, 15 праз 22, 787 00:38:40,444 --> 00:38:43,610 якія working--, таму што ўсё, што я раблю проста перабіраючы і printing-- 788 00:38:43,610 --> 00:38:45,406 Я магу ісці наперад і прапусціць гэта. 789 00:38:45,406 --> 00:38:47,280 Давайце пачнем з лініі 25. 790 00:38:47,280 --> 00:38:48,712 ААП дазвольце мне пазбавіцца ад гэтага. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> АЎДЫТОРЫЯ: Так кропкі супыну дзе пачынаецца адладка? 793 00:38:54,057 --> 00:38:54,890 ANDI Пэн: Ці прыпынкаў. 794 00:38:54,890 --> 00:38:55,670 АЎДЫТОРЫЯ: Ці прыпынкаў. 795 00:38:55,670 --> 00:38:55,930 ANDI Пэн: Так. 796 00:38:55,930 --> 00:38:58,640 Вы можаце ўсталяваць кропкі супыну і некалькі ён можа проста скакаць ад аднаго да іншага. 797 00:38:58,640 --> 00:39:01,590 Але ў гэтым выпадку мы не ведаем, дзе памылка адбываецца. 798 00:39:01,590 --> 00:39:03,780 Такім чынам, мы проста хочам пачаць зверху ўніз. 799 00:39:03,780 --> 00:39:05,020 Так. 800 00:39:05,020 --> 00:39:05,550 ДОБРА. 801 00:39:05,550 --> 00:39:08,460 >> Так гэтая лінія тут, мы можам умяшацца. 802 00:39:08,460 --> 00:39:11,499 Вы можаце ўбачыць тут, мы атрымалі масіў. 803 00:39:11,499 --> 00:39:13,290 Тыя значэння што ў масіве. 804 00:39:13,290 --> 00:39:16,360 Вы бачыце, што, як індэкс 0, адпавядае value-- аб, 805 00:39:16,360 --> 00:39:17,526 Я збіраюся паспрабаваць, каб павялічыць. 806 00:39:17,526 --> 00:39:20,650 На жаль, гэта сапраўды цяжка каб see-- па індэксе масіва 0, 807 00:39:20,650 --> 00:39:24,090 мы маем значэнне 4 і Затым гэтак далей, і гэтак далей. 808 00:39:24,090 --> 00:39:25,670 У нас ёсць лакальныя зменныя. 809 00:39:25,670 --> 00:39:28,570 Зараз я роўная 0, што мы хочам, каб гэта было. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> І так давайце трымаць пакрокавае. 812 00:39:33,690 --> 00:39:36,850 Наш мінімальны роўны 0, якія мы таксама хочам, каб гэта было. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 І тады мы ўваходзім наш другі для цыкл, калі масіў J менш, чым масіў-I, 815 00:39:45,560 --> 00:39:46,380 які яго не было. 816 00:39:46,380 --> 00:39:48,130 Гэтак жа вы бачыце, як што прапусціў што? 817 00:39:48,130 --> 00:39:52,430 >> АЎДЫТОРЫЯ: так павінна, калі Мінімальны ўсе that-- не вынікае, што 818 00:39:52,430 --> 00:39:55,424 быць унутры першым цыкл? 819 00:39:55,424 --> 00:39:57,340 ANDI Пэн: Не, таму што Вы ўсё яшчэ хочаце, каб праверыць. 820 00:39:57,340 --> 00:40:00,329 Вы хочаце, каб зрабіць параўнанне кожны Час, нават пасля запуску праз яго. 821 00:40:00,329 --> 00:40:02,620 Вы не проста хочаце, каб зрабіць гэта на першым праход. 822 00:40:02,620 --> 00:40:05,240 Вы хочаце, каб зрабіць гэта з кожны праход зноў. 823 00:40:05,240 --> 00:40:07,198 Такім чынам, вы хочаце, каб праверыць Ваш стан ўнутры. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Такім чынам, мы толькі збіраемся трымаць працуе праз тут. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Я дам вам падказку хлопцам. 828 00:40:18,420 --> 00:40:23,910 Гэта звязана з тым, што пры Вы правяраеце ваш ўмоўны, 829 00:40:23,910 --> 00:40:26,600 Вы не правяраючы для правільнага азначніка. 830 00:40:26,600 --> 00:40:32,510 Так што цяпер вы праверка Індэкс масіва J менш, чым масіў 831 00:40:32,510 --> 00:40:33,970 Індэкс I. 832 00:40:33,970 --> 00:40:36,580 Але тое, што ты робіш на пачатак для цыкла? 833 00:40:36,580 --> 00:40:38,260 Вы не усталяваўшы J, роўны I? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Так, так што мы на самай справе можам выйсці з адладчыка тут. 836 00:40:45,415 --> 00:40:47,040 Такім чынам, давайце зірнем на нашым псевдокоде. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- мы збіраемся пачаць у я роўная 0. 839 00:40:52,580 --> 00:40:54,760 Мы збіраемся ісці да н мінус 1. 840 00:40:54,760 --> 00:40:58,040 Давайце праверым, мы мелі гэта права? 841 00:40:58,040 --> 00:40:59,580 Так, гэта было ў парадку. 842 00:40:59,580 --> 00:41:02,080 >> Такім чынам ўнутры тут, мы створым мінімальнае значэнне 843 00:41:02,080 --> 00:41:03,630 і ўсталяваць, што ў I роўныя. 844 00:41:03,630 --> 00:41:04,950 Хіба мы гэта робім? 845 00:41:04,950 --> 00:41:06,270 Так, гэта зрабіў. 846 00:41:06,270 --> 00:41:10,430 У цяперашні час у нашай унутранай завесы для, мы збіраецца рабіць J роўная я ў п мінус 1. 847 00:41:10,430 --> 00:41:11,950 Хіба мы гэта робім? 848 00:41:11,950 --> 00:41:15,540 На самай справе, мы зрабілі гэта. 849 00:41:15,540 --> 00:41:19,922 >> Так, аднак, што мы тут параўнання? 850 00:41:19,922 --> 00:41:20,925 >> АЎДЫТОРЫЯ: J + 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Пэн: Точно. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 І тады вы будзеце жадаць, каб усталяваць мінімальная роўная J плюс 1, а. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Так што я прайшоў праз гэта вельмі хутка. 856 00:41:32,640 --> 00:41:36,190 Як вы, хлопцы разумеюць чаму гэта J + 1? 857 00:41:36,190 --> 00:41:36,890 ДОБРА. 858 00:41:36,890 --> 00:41:40,700 >> Такім чынам, у вашым масіве, у Ваш першы праход праз, 859 00:41:40,700 --> 00:41:44,850 Ваш цыкл, для Int я роўная 0, давайце проста 860 00:41:44,850 --> 00:41:46,740 выказаць здагадку, што гэта не была змененая яшчэ. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 У нас ёсць масіў, цалкам, усяго чатыры малокомплектных элементы, праўда? 863 00:41:56,760 --> 00:42:00,760 Таму мы хочам, каб ініцыялізаваць я раўняцца 0. 864 00:42:00,760 --> 00:42:03,650 І я маю намер проста праходзяць праз гэтую пятлю. 865 00:42:03,650 --> 00:42:08,560 І таму ў першым праходзе, мы збіраемся ініцыялізаваць зменную "мін" 866 00:42:08,560 --> 00:42:11,245 што таксама роўна I, таму што мы не мець мінімальнае значэнне. 867 00:42:11,245 --> 00:42:12,870 Дык вось у цяперашні час роўны 0, а таксама. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 І тады мы будзем ісці да канца. 870 00:42:17,640 --> 00:42:19,270 І мы хочам, каб ітэрацыі зноў. 871 00:42:19,270 --> 00:42:22,900 Цяпер, калі мы знайшлі, што наш мінімальны ёсць, мы хочам, каб перабору 872 00:42:22,900 --> 00:42:25,190 зноў, каб убачыць, калі гэта параўнанне, ці не так? 873 00:42:25,190 --> 00:42:40,440 Так J, вось, ідзе на роўнае I, які з'яўляецца 0. 874 00:42:40,440 --> 00:42:46,320 І потым, калі масіў J плюс я, што гэта той, які далей зноў, як менш 875 00:42:46,320 --> 00:42:49,270 чым тое, што ваш бягучы мінімум значэнне, вы хочаце памяняць месцамі. 876 00:42:49,270 --> 00:42:56,850 >> Так што давайце проста сказаць, што мы атрымаў, як, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Прама цяпер, я роўная 0 і J роўны 0. 878 00:43:01,610 --> 00:43:05,210 І гэта наша мінімальнае значэнне. 879 00:43:05,210 --> 00:43:09,950 Калі масіў-J плюс i-- так што калі адзін гэта пасля таго, што мы, гледзячы на 880 00:43:09,950 --> 00:43:13,450 больш, чым адзін перад гэтым, гэта стане мінімум. 881 00:43:13,450 --> 00:43:18,120 >> Дык вось, мы бачым, што 5 ня менш, чым. 882 00:43:18,120 --> 00:43:19,730 Дык гэта будзе, каб не быць 5. 883 00:43:19,730 --> 00:43:23,580 Мы бачым, што 1 менш, чым 2, ці не так? 884 00:43:23,580 --> 00:43:32,970 Такім чынам, зараз мы ведаем, што наша мінімум будзе значэнне індэкса на 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Да? 886 00:43:34,030 --> 00:43:39,170 А потым, калі вы атрымліваеце тут, Вы можаце памяняць правільныя значэння. 887 00:43:39,170 --> 00:43:42,610 >> Так што, калі вы, хлопцы, проста маючы J раней, вы не гледзячы на ​​тое 888 00:43:42,610 --> 00:43:43,260 пасля яе. 889 00:43:43,260 --> 00:43:44,520 Вы шукалі на тое ж самае значэнне, што 890 00:43:44,520 --> 00:43:46,290 Таму ён проста нічога не рабіў. 891 00:43:46,290 --> 00:43:49,721 Ці мае гэта сэнс для ўсіх, Таму нам трэба што плюс 1 там? 892 00:43:49,721 --> 00:43:50,220 ДОБРА. 893 00:43:50,220 --> 00:43:53,345 Зараз давайце проста запусціць праз яго, каб зрабіць што астатняя частка кода з'яўляецца правільным. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Чаму, што здарылася? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ах, гэта мін прама тут. 898 00:44:16,364 --> 00:44:17,780 Мы параўноўвалі няправільнае значэнне. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 О, няма. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Ах да, тут мы былі абмен няправільныя значэння, а таксама. 903 00:44:33,482 --> 00:44:34,940 Таму што мы шукалі ў I і J. 904 00:44:34,940 --> 00:44:36,440 Тыя, каго мы правяралі. 905 00:44:36,440 --> 00:44:39,160 Мы на самай справе хочам, каб памяняць месцамі Мінімальны ток мінімум, 906 00:44:39,160 --> 00:44:40,550 з тым, што адзін звонку. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 І, як вы, хлопцы, можаце ўбачыць ўніз тут, у нас ёсць адсартаваны масіў. 909 00:45:05,402 --> 00:45:07,110 Гэта проста было зрабіць з той факт, што, калі 910 00:45:07,110 --> 00:45:09,350 мы правяралі Значэння, якія мы параўноўвалі, 911 00:45:09,350 --> 00:45:11,226 мы не глядзелі на правільныя значэння. 912 00:45:11,226 --> 00:45:13,850 Мы шукалі ў тым жа самым тут, на самай справе не яго замены. 913 00:45:13,850 --> 00:45:17,135 Вы павінны глядзець на адзін наступны да яго, а затым вы можаце памяняць. 914 00:45:17,135 --> 00:45:19,260 Дык вось тое, што было свайго роду праслухоўванне наш код, перш чым. 915 00:45:19,260 --> 00:45:22,460 І тое, што я зрабіў тут ёсць усё, адладчык мог бы зрабіць для вас 916 00:45:22,460 --> 00:45:23,810 Я проста зрабіў гэта на дошка, таму што гэта лягчэй 917 00:45:23,810 --> 00:45:26,320 каб убачыць, а не спрабаваць для павелічэння маштабу адладчыка. 918 00:45:26,320 --> 00:45:29,391 Ці мае гэта сэнс для ўсіх? 919 00:45:29,391 --> 00:45:29,890 Прахладны. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Добра. 922 00:45:35,410 --> 00:45:41,070 Мы можам рухацца далей да размовы аб асімптатычнай абазначэння, якія 923 00:45:41,070 --> 00:45:44,580 гэта проста фантазіі спосаб сказаць выканання ўсіх гэтых відаў. 924 00:45:44,580 --> 00:45:47,650 Так што я ведаю Дэвіда, у лекцыі, закрануў аўтаномнай працы. 925 00:45:47,650 --> 00:45:52,124 І ён пайшоў праз увесь формуле аб тым, як разлічыць час аўтаномнай працы. 926 00:45:52,124 --> 00:45:53,040 Не турбуйцеся пра гэта. 927 00:45:53,040 --> 00:45:54,660 Калі вы сапраўды цікава пра тое, як гэта працуе, 928 00:45:54,660 --> 00:45:55,810 не саромейцеся гаварыць са мной пасля падзелу. 929 00:45:55,810 --> 00:45:57,560 Мы можам прайсці праз формулы разам. 930 00:45:57,560 --> 00:46:00,689 Але ўсе вы, хлопцы, павінны сапраўды ведаю, што п у квадраце больш за 2 931 00:46:00,689 --> 00:46:01,980 гэта тое ж самае, як н у квадраце. 932 00:46:01,980 --> 00:46:04,710 Таму што найбольшы нумар, паказчык расце больш за ўсё. 933 00:46:04,710 --> 00:46:06,590 І так для нашых мэтаў, Усе мы клапоцімся пра 934 00:46:06,590 --> 00:46:09,470 з'яўляецца тое, што гіганцкі нумар, які расце. 935 00:46:09,470 --> 00:46:13,340 >> Так што ў лепшым выпадку выканання адборачнага роду? 936 00:46:13,340 --> 00:46:15,830 Калі вы збіраецеся мець для перабору спісу 937 00:46:15,830 --> 00:46:18,712 а затым перабору астатнія гэтага спісу, 938 00:46:18,712 --> 00:46:20,420 колькі разоў Вы збіраецеся верагодна, 939 00:46:20,420 --> 00:46:24,612 у горшым case-- ў лепшым выпадку, sorry-- запусціць праз? 940 00:46:24,612 --> 00:46:27,070 Можа быць, лепш спытаць каб спытаць, што гэта горшы выпадак 941 00:46:27,070 --> 00:46:28,153 выканання адборачнага роду. 942 00:46:28,153 --> 00:46:29,366 АЎДЫТОРЫЯ: п у квадраце. 943 00:46:29,366 --> 00:46:30,740 ANDI Пэн: Гэта н квадрат, правільна. 944 00:46:30,740 --> 00:46:36,986 Так просты спосаб думаць пра гэта, як, у любы час у вас ёсць два ўкладзеных цыклаў для, 945 00:46:36,986 --> 00:46:38,110 гэта будзе н у квадраце. 946 00:46:38,110 --> 00:46:40,386 Таму што не толькі ты якая праходзіць праз раз, 947 00:46:40,386 --> 00:46:42,260 ў вас ёсць, каб вярнуцца і бегчы праз яго 948 00:46:42,260 --> 00:46:44,980 зноў ўнутры для кожнага значэння. 949 00:46:44,980 --> 00:46:48,640 Такім чынам, у гэтым выпадку, вы працуеце п раз н квадрат, які is-- прабачце, 950 00:46:48,640 --> 00:46:50,505 п разоў п, роўны п у квадраце. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> І накшталт таксама трохі унікальным у тым сэнсе 953 00:46:56,360 --> 00:46:59,774 што гэта не мае значэння, калі гэтыя Значэння ўжо ў парадку. 954 00:46:59,774 --> 00:47:01,440 Ён па-ранейшаму збіраецца запусціць праз любым выпадку. 955 00:47:01,440 --> 00:47:03,872 Давайце проста сказаць, што гэта быў 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Незалежна ад таго, ці з'яўляецца ён у парадак, гэта ўсё роўна б прабег 957 00:47:07,080 --> 00:47:08,620 і да гэтага часу правяраецца мінімальнае значэнне. 958 00:47:08,620 --> 00:47:10,100 Гэта зрабіла б такое ж колькасць праверак 959 00:47:10,100 --> 00:47:12,780 кожны раз, нават калі ён на самай справе не чапаць. 960 00:47:12,780 --> 00:47:16,940 >> Такім чынам, у такім выпадку, лепшым і горшым Час аўтаномнай працы фактычна эквівалентныя. 961 00:47:16,940 --> 00:47:19,160 Такім чынам, чаканы выканання селекцыйнага гатунку, 962 00:47:19,160 --> 00:47:23,790 якія мы пазначаем сімвалам тэта, тэта, у дадзеным выпадку, 963 00:47:23,790 --> 00:47:24,790 Таксама будзе н квадрат. 964 00:47:24,790 --> 00:47:26,480 Усе гэтыя тры будзе н квадрат. 965 00:47:26,480 --> 00:47:29,653 Гэта ўсё зразумела, чаму серада выканання п квадраце? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Добра. 968 00:47:33,980 --> 00:47:39,120 Так што я проста хачу, каб хутка бегчы праз астатнюю частку гатункаў. 969 00:47:39,120 --> 00:47:41,137 Алгарытм бурбалка sort-- памятаеце, 970 00:47:41,137 --> 00:47:43,220 гэта было першым Дэвід падышоў у лекцыі. 971 00:47:43,220 --> 00:47:46,000 Па сутнасці, вы крок праз увесь спіс 972 00:47:46,000 --> 00:47:48,950 і вы swap-- вас усяго Параўнанне двух адначасова. 973 00:47:48,950 --> 00:47:51,350 І калі гэта больш, чым вы проста памяняць іх месцамі. 974 00:47:51,350 --> 00:47:53,590 Так што, калі гэта больш, вы б памяняць. 975 00:47:53,590 --> 00:47:56,180 Я атрымаў афіцыйнае права тут. 976 00:47:56,180 --> 00:47:59,100 >> Так што давайце проста сказаць, што вы былі 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Вы б параўнаць 8 і 6. 978 00:48:00,571 --> 00:48:01,570 Вы павінны былі б памяняць іх месцамі. 979 00:48:01,570 --> 00:48:02,610 Вы б параўнаць 8 і 4. 980 00:48:02,610 --> 00:48:03,609 Вы павінны былі б памяняць іх месцамі. 981 00:48:03,609 --> 00:48:07,000 Калі ў вас ёсць, каб памяняць 8 і 2, змяніць іх. 982 00:48:07,000 --> 00:48:10,760 Такім чынам, у такім сэнсе, вы можаце бачыць, згуляная на працягу доўгага перыяду часу, 983 00:48:10,760 --> 00:48:13,730 як значэння роду бурбалка канцы, які з'яўляецца, чаму мы называем яго 984 00:48:13,730 --> 00:48:15,320 пузырьковый сартаванне. 985 00:48:15,320 --> 00:48:19,950 >> Мы проста запусціць праз раз на наш другі праход, і наш трэці праход, 986 00:48:19,950 --> 00:48:21,150 і наш чацвёрты праход. 987 00:48:21,150 --> 00:48:25,820 Па сутнасці, пузырьковый сартаванне працуе толькі да таго часу, пакуль не робяць ніякіх больш свопы. 988 00:48:25,820 --> 00:48:31,109 Так што ў гэтым сэнсе, гэта проста агульная псевдокод для яго. 989 00:48:31,109 --> 00:48:32,650 Не турбуйцеся, гэта не ўсё будзе на сайце. 990 00:48:32,650 --> 00:48:34,990 Мы не павінны на самай справе пайсці з гэтай нагоды. 991 00:48:34,990 --> 00:48:38,134 >> Мы проста ініцыялізаваць лічыльнік пераменная, якая пачынаецца з 0. 992 00:48:38,134 --> 00:48:39,800 І мы перабору ўсяго масіва. 993 00:48:39,800 --> 00:48:43,420 І калі адно значэнне, калі гэта is-- значэнне больш, чым дадзенае значэнне, 994 00:48:43,420 --> 00:48:44,610 Вы збіраецеся памяняць іх месцамі. 995 00:48:44,610 --> 00:48:46,860 І тады ты проста працягваць ісці. 996 00:48:46,860 --> 00:48:47,970 І вы збіраецеся разлічваць. 997 00:48:47,970 --> 00:48:50,845 І вы толькі збіраецеся працягваць рабіць гэта ў той час лічыльнік больш 998 00:48:50,845 --> 00:48:53,345 чым 0, што азначае, што кожны раз, калі ў вас ёсць, каб памяняць, 999 00:48:53,345 --> 00:48:55,220 Вы ведаеце, вы хочаце пайсці таму і яшчэ раз праверыць. 1000 00:48:55,220 --> 00:48:59,510 Вы хочаце, каб трымаць праверку, пакуль вы не ведаеце, што вы не павінны памяняць больш. 1001 00:48:59,510 --> 00:49:05,570 >> Так што самы лепшы і горшы Справа сераду выканання для пузырьковый сартавання? 1002 00:49:05,570 --> 00:49:09,300 І hint-- гэта на самай справе адрозніваецца ад выбару віду ў сэнсе 1003 00:49:09,300 --> 00:49:11,810 што гэтыя два адказы не супадаюць. 1004 00:49:11,810 --> 00:49:14,709 Падумайце аб тым, што будзе адбывацца ў выпадак, калі ён быў ужо адсартаваны. 1005 00:49:14,709 --> 00:49:16,500 І думаць пра тое, што адбудзецца, калі ён быў 1006 00:49:16,500 --> 00:49:18,372 у выпадку, у якім ён не быў адсартаваны. 1007 00:49:18,372 --> 00:49:20,580 І вы можаце запусціць выгляд праз што, чаму адбываецца. 1008 00:49:20,580 --> 00:49:22,954 Я дам вам, хлопцы, як, 30 секунд, каб думаць пра гэта. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> ДОБРА. 1011 00:49:53,540 --> 00:49:57,462 Хто-небудзь ёсць здагадка, што ў у горшым выпадку час выканання пузырьковый сартавання з'яўляецца? 1012 00:49:57,462 --> 00:49:57,962 Так. 1013 00:49:57,962 --> 00:50:07,810 >> АЎДЫТОРЫЯ: было б, як, п раз п мінус 1 ці нешта падобнае? 1014 00:50:07,810 --> 00:50:10,650 Маўляў, кожны раз, калі ён працуе, гэта проста, як адзін своп менш 1015 00:50:10,650 --> 00:50:10,960 што б гэта ні было. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Пэн: Так, так Вы цалкам маеце рацыю. 1017 00:50:12,668 --> 00:50:15,940 І гэта той выпадак, калі ваш Адказ на самой справе больш складаная 1018 00:50:15,940 --> 00:50:17,240 чым мы павінны даць. 1019 00:50:17,240 --> 00:50:19,772 Дык гэта будзе run-- Я збіраюся сцерці ўсё гэта тут. 1020 00:50:19,772 --> 00:50:20,480 Ці ўсё добра? 1021 00:50:20,480 --> 00:50:21,869 Ці магу я сцерці гэта? 1022 00:50:21,869 --> 00:50:22,368 ДОБРА. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Вы збіраецеся працаваць праз п раз у першы раз, ці не так? 1025 00:50:30,320 --> 00:50:33,200 І яны збіраюцца запусціць праз п мінус 1 ў другі раз, праўда? 1026 00:50:33,200 --> 00:50:37,130 І тады вы будзеце трымаць адбываецца, п мой 2, і гэтак далей. 1027 00:50:37,130 --> 00:50:40,210 Дэвід зрабіў гэта ў лекцыі, дзе, калі вы дадалі ўсе гэтыя каштоўнасці, 1028 00:50:40,210 --> 00:50:48,080 Вы атрымліваеце тое, што гэта like-- yeah-- больш за 2, што істотна зніжае проста 1029 00:50:48,080 --> 00:50:49,784 да п квадраце. 1030 00:50:49,784 --> 00:50:51,700 Вы збіраецеся атрымаць дзіўна доля там. 1031 00:50:51,700 --> 00:50:53,892 І так проста ведаю, што п квадраце заўсёды 1032 00:50:53,892 --> 00:50:55,350 мае прыярытэт над фракцыяй. 1033 00:50:55,350 --> 00:50:58,450 І таму ў гэтым выпадку горшага выканання будзе н у квадраце. 1034 00:50:58,450 --> 00:51:00,210 Калі б гэта было ў парадку змяншэння парадак, думаю, вам, 1035 00:51:00,210 --> 00:51:02,530 павінны зрабіць своп кожны раз. 1036 00:51:02,530 --> 00:51:05,170 >> Што б, патэнцыйна, у лепшым выпадку выканання? 1037 00:51:05,170 --> 00:51:08,580 Давайце проста сказаць, што калі спіс ужо быў ў парадку, што б падчас выканання будзе? 1038 00:51:08,580 --> 00:51:09,565 >> АЎДЫТОРЫЯ: п. 1039 00:51:09,565 --> 00:51:10,690 ANDI Пэн: Гэта н, дакладна. 1040 00:51:10,690 --> 00:51:11,600 І чаму гэта п? 1041 00:51:11,600 --> 00:51:13,850 АЎДЫТОРЫЯ: таму што вы проста павінны праверыць на кожным раз. 1042 00:51:13,850 --> 00:51:14,770 ANDI Пэн: Точно. 1043 00:51:14,770 --> 00:51:17,150 Такім чынам, у лепшым выканання, калі гэты спіс быў ужо 1044 00:51:17,150 --> 00:51:20,270 sorted-- скажам 1, 2, 3, 4-- вы проста прайсці, вы б праверыць, 1045 00:51:20,270 --> 00:51:21,720 вы ўбачыце, ох, усе яны апраўдаліся. 1046 00:51:21,720 --> 00:51:22,636 У мяне не было, каб памяняць. 1047 00:51:22,636 --> 00:51:23,370 Я скончыў. 1048 00:51:23,370 --> 00:51:26,500 Такім чынам, у гэтым выпадку, гэта проста п або колькасць крокаў, якія вы проста 1049 00:51:26,500 --> 00:51:29,870 павінен быў праверыць у першым спісе. 1050 00:51:29,870 --> 00:51:33,990 >> І пасля гэтага, мы цяпер трапіў сартаванне ўстаўкамі, дзе 1051 00:51:33,990 --> 00:51:39,260 алгарытм, па сутнасці, падзяліць гэта ў адсартаваным і малокомплектных часткі. 1052 00:51:39,260 --> 00:51:42,810 А потым адзін за адным, неотсортированной значэння 1053 00:51:42,810 --> 00:51:46,880 ўстаўляецца ў адпаведных пазіцыі ў пачатку спісу. 1054 00:51:46,880 --> 00:51:52,120 >> Так, напрыклад, у нас ёсць Спіс 3, 5, 2, 6, 4 зноў. 1055 00:51:52,120 --> 00:51:54,750 Мы ведаем, што гэта ў цяперашні час малокомплектных, таму што мы толькі што 1056 00:51:54,750 --> 00:51:57,030 пачаў глядзець на яго. 1057 00:51:57,030 --> 00:52:00,610 Мы глядзім і мы ведаем, што першае значэнне сартуецца, праўда? 1058 00:52:00,610 --> 00:52:04,190 Калі вы толькі гледзячы на ​​масіў Памер аднаго, вы ведаеце, што гэта сартуецца. 1059 00:52:04,190 --> 00:52:08,230 >> Такім чынам, мы ведаем, што Астатнія чатыры малокомплектных. 1060 00:52:08,230 --> 00:52:10,980 Мы ідзем праз, і мы бачым, што значэнне. 1061 00:52:10,980 --> 00:52:11,730 Давайце вернемся. 1062 00:52:11,730 --> 00:52:13,130 Глядзіце, што значэнне 5? 1063 00:52:13,130 --> 00:52:14,110 Мы глядзім на яго. 1064 00:52:14,110 --> 00:52:15,204 Мы параўноўваем яго да 3. 1065 00:52:15,204 --> 00:52:17,870 Мы ведаем, што гэта больш, чым 3, так што мы ведаем, што гэта сартуецца. 1066 00:52:17,870 --> 00:52:22,940 Такім чынам, мы цяпер ведаем, што першыя два сартуюцца, а апошнія тры не з'яўляюцца. 1067 00:52:22,940 --> 00:52:24,270 >> Мы зірнем на 2. 1068 00:52:24,270 --> 00:52:25,720 Спачатку мы правяраем яго 5. 1069 00:52:25,720 --> 00:52:26,700 Гэта менш, чым 5? 1070 00:52:26,700 --> 00:52:27,240 Гэта не так. 1071 00:52:27,240 --> 00:52:29,510 Такім чынам, мы павінны трымаць гледзячы ўніз. 1072 00:52:29,510 --> 00:52:30,940 Тады вы праверыць 2 ад 3. 1073 00:52:30,940 --> 00:52:31,850 Гэта менш, чым? 1074 00:52:31,850 --> 00:52:32,350 Няма. 1075 00:52:32,350 --> 00:52:35,430 Такім чынам, вы ведаеце, што 2 павінен быць устаўлены у пярэдняй і 3 і 5 1076 00:52:35,430 --> 00:52:38,200 абодва павінны быць выцесненыя. 1077 00:52:38,200 --> 00:52:42,190 Зрабіце гэта зноў 6 і 4. 1078 00:52:42,190 --> 00:52:48,962 І мы проста сочыце сутнасці, дзе мы проста праверыць, праверыць, праверыць. 1079 00:52:48,962 --> 00:52:51,170 І пакуль гэта не ў праве пасаду, мы б проста 1080 00:52:51,170 --> 00:52:54,890 устаўце яго ў правільным становішчы, які з'яўляецца, дзе імя прыйшоў. 1081 00:52:54,890 --> 00:52:59,830 >> Так што гэта проста алгарытм, псевдокод такой, накшталт, 1082 00:52:59,830 --> 00:53:04,990 аб тым, як мы будзе ажыццяўляць сартаванне ўстаўкамі. 1083 00:53:04,990 --> 00:53:05,954 Псевдокод тут. 1084 00:53:05,954 --> 00:53:06,620 Гэта ўсё ў Інтэрнэце. 1085 00:53:06,620 --> 00:53:10,720 Не турбуйцеся, калі вы, хлопцы, спрабуючы скапіяваць гэта ўніз. 1086 00:53:10,720 --> 00:53:14,500 Такім чынам, яшчэ раз, тое ж самае, што question-- будзе лепшым і горшым аўтаномнай працы 1087 00:53:14,500 --> 00:53:16,120 для ўстаўкі роду? 1088 00:53:16,120 --> 00:53:17,750 Гэта вельмі падобна на апошняе пытанне. 1089 00:53:17,750 --> 00:53:20,479 Я дам вам, хлопцы, як, 30 секунд, каб думаць пра гэта, а таксама. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> ОК ці хто-небудзь хоча даць мне горшы выканання? 1092 00:53:50,071 --> 00:53:50,570 Так. 1093 00:53:50,570 --> 00:53:51,490 >> АЎДЫТОРЫЯ: п у квадраце. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Пэн: Гэта н квадраце. 1095 00:53:52,573 --> 00:53:53,730 І чаму гэта п квадраце? 1096 00:53:53,730 --> 00:53:57,562 >> АЎДЫТОРЫЯ: Таму што ў зваротны парадак, у вас ёсць 1097 00:53:57,562 --> 00:54:02,619 прайсці праз п разоў п, is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI Пэн: Так, менавіта так. 1099 00:54:03,660 --> 00:54:06,610 Гэтак жа, як і ў пузырьковый сартавання. 1100 00:54:06,610 --> 00:54:08,720 Калі гэты спіс у парадку змяншэння, вы 1101 00:54:08,720 --> 00:54:11,240 прыйдзецца праверыць першы раз. 1102 00:54:11,240 --> 00:54:13,470 А потым з кожным дадатковая кошт, вы 1103 00:54:13,470 --> 00:54:16,390 прыйдзецца праверыць яго супраць кожны значэнне, праўда? 1104 00:54:16,390 --> 00:54:20,290 І так у цэлым, вы збіраецеся зрабіць А.М. раз н-пас іншы п прайсці, што 1105 00:54:20,290 --> 00:54:21,750 ў п квадраце. 1106 00:54:21,750 --> 00:54:22,860 Што можна сказаць аб лепшым выпадку? 1107 00:54:22,860 --> 00:54:24,360 Так. 1108 00:54:24,360 --> 00:54:28,840 >> АЎДЫТОРЫЯ: N мінус 1, паколькі Першы ўжо ў квадрат. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Пэн: Так, блізка. 1110 00:54:30,270 --> 00:54:31,850 Адказ на самай справе п. 1111 00:54:31,850 --> 00:54:37,189 Паколькі ў той час як Першы сартаваць, яна не можа яго actually-- 1112 00:54:37,189 --> 00:54:38,980 мы проста пашанцавала, у што прыклад, што 2 1113 00:54:38,980 --> 00:54:40,930 адбылося найменшая колькасць. 1114 00:54:40,930 --> 00:54:43,680 Але не заўсёды будзе так. 1115 00:54:43,680 --> 00:54:48,040 Калі 2 ужо адсартаваныя ў пачатку але вы паглядзіце, і ёсць 1 тут, 1116 00:54:48,040 --> 00:54:49,144 1 будзе падняць яго. 1117 00:54:49,144 --> 00:54:51,060 І гэта будзе ў канчатковым да таго сутыкнуўся ў любым выпадку. 1118 00:54:51,060 --> 00:54:56,250 >> Такім чынам, у лепшым выпадку, гэта на самай справе проста будзе н. 1119 00:54:56,250 --> 00:54:59,090 Калі ў вас ёсць 1, 2, 3, 4, 5, 6, 7, 8, вы 1120 00:54:59,090 --> 00:55:00,940 збіраецца запусціць праз што ўвесь спіс адразу 1121 00:55:00,940 --> 00:55:03,430 каб праверыць, калі ўсё ў парадку. 1122 00:55:03,430 --> 00:55:07,390 Гэта ўсё ясна, на які працуе раз адбору, а? 1123 00:55:07,390 --> 00:55:09,960 Я ведаю, што іду праз гэта вельмі хутка. 1124 00:55:09,960 --> 00:55:13,330 Але дакладна ведаю, што, калі вы ведаеце, агульныя паняцці, вы павінны быць добра. 1125 00:55:13,330 --> 00:55:16,070 ДОБРА. 1126 00:55:16,070 --> 00:55:19,790 Так што я проста дам вам, хлопцы, можа быць, як, хвіліну, каб пагаварыць з вашымі суседзямі 1127 00:55:19,790 --> 00:55:21,890 на тое, што толькі некаторыя з асноўных адрозненняў 1128 00:55:21,890 --> 00:55:23,540 паміж гэтымі тыпамі гатункаў. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Мы пойдзем над тым у бліжэйшы час. 1131 00:56:25,570 --> 00:56:26,444 АЎДЫТОРЫЯ: О, добра. 1132 00:56:26,444 --> 00:56:27,320 ANDI Пэн: Так. 1133 00:56:27,320 --> 00:56:28,380 ДОБРА. 1134 00:56:28,380 --> 00:56:33,420 Прахладны, давайце зноў склікаць як клас. 1135 00:56:33,420 --> 00:56:34,330 ДОБРА. 1136 00:56:34,330 --> 00:56:37,579 Так што гэта было свайго роду адкрытае пытанне ў тым сэнсе, 1137 00:56:37,579 --> 00:56:39,120 што ёсць шмат адказаў на іх. 1138 00:56:39,120 --> 00:56:40,746 І мы будзем ісці над некаторымі з іх коратка. 1139 00:56:40,746 --> 00:56:43,411 Я проста хацеў, каб вы, хлопцы думаючы пра тое, што дыферэнцыраваны 1140 00:56:43,411 --> 00:56:44,530 усе тры тыпу гатункаў. 1141 00:56:44,530 --> 00:56:47,440 І пачуў я, таксама, вялікі question-- што ж сартавання зліццём зрабіць? 1142 00:56:47,440 --> 00:56:50,110 Вялікае пытанне, таму што гэта тое, што мы ў наступным пакрыцця. 1143 00:56:50,110 --> 00:56:52,850 >> Так аб'яднаць роду з'яўляецца адзін выгляд, што функцыі 1144 00:56:52,850 --> 00:56:56,100 вельмі па-рознаму ад іншых відаў. 1145 00:56:56,100 --> 00:56:58,180 Як вы, хлопцы, можаце see-- зрабіў Давід, што дэма 1146 00:56:58,180 --> 00:57:01,130 дзе ён усё крута шумы, бачачы, як аб'яднаць 1147 00:57:01,130 --> 00:57:04,010 Сартаваць пабег, як бясконца хутчэй, чым двух іншых тыпаў? 1148 00:57:04,010 --> 00:57:04,510 ДОБРА. 1149 00:57:04,510 --> 00:57:07,580 Так гэта таму, што зліццё Сартаваць рэалізуе гэты разрыў 1150 00:57:07,580 --> 00:57:11,020 і заваяваць канцэпцыю, што мы казалі пра многае ў лекцыі. 1151 00:57:11,020 --> 00:57:14,550 У тым сэнсе, што мы хацелі б працаваць разумнейшы, а не цяжэй, калі вы падзеліце 1152 00:57:14,550 --> 00:57:18,120 і заваяваць праблемы, і зламаць іх ўніз, а затым пакласці іх разам, 1153 00:57:18,120 --> 00:57:19,930 добрыя рэчы заўсёды адбываюцца. 1154 00:57:19,930 --> 00:57:21,960 >> Так так, што зліваюцца Сартаваць па сутнасці працуе 1155 00:57:21,960 --> 00:57:24,660 з'яўляецца тое, што дзеліць малокомплектных масіў напалову. 1156 00:57:24,660 --> 00:57:26,500 А потым ён атрымаў дзве палоўкі масіваў. 1157 00:57:26,500 --> 00:57:28,220 І гэта як раз тыя сартуе дзве палоўкі. 1158 00:57:28,220 --> 00:57:31,750 Ён проста трымае дзялення напалову, у палова, напалам пакуль усё не будзе адсартаваны 1159 00:57:31,750 --> 00:57:33,680 а затым рэкурсіўна ставіць усё гэта разам. 1160 00:57:33,680 --> 00:57:36,550 >> Так што гэта сапраўды абстрактнай. 1161 00:57:36,550 --> 00:57:38,750 Так што гэта проста трохі псевдокода. 1162 00:57:38,750 --> 00:57:41,040 Ці мае гэта сэнс у так, як гэта працуе? 1163 00:57:41,040 --> 00:57:43,870 Так што давайце проста сказаць, у вас ёсць масіў п элементаў, правільна? 1164 00:57:43,870 --> 00:57:45,450 Калі п менш, чым 2, вы можаце вярнуцца. 1165 00:57:45,450 --> 00:57:49,040 Таму што вы ведаеце, што, калі ёсць толькі адна рэч, яна павінна быць адсартаваныя. 1166 00:57:49,040 --> 00:57:52,600 У адваротным выпадку, вы сартаваць левую палову, а затым адсартаваць правую палову, 1167 00:57:52,600 --> 00:57:54,140 і тады вы зліваюцца. 1168 00:57:54,140 --> 00:57:56,979 >> Так у той час як выглядае на самай справе лёгка, у рэчаіснасці, думаць пра гэта гэта 1169 00:57:56,979 --> 00:58:00,270 выгляд цяжка. Таму што вы, як ну вось накшталт працуе на сябе. 1170 00:58:00,270 --> 00:58:00,769 Дакладна? 1171 00:58:00,769 --> 00:58:02,430 Гэта працуе на сябе. 1172 00:58:02,430 --> 00:58:05,479 Так што ў гэтым сэнсе, Дэвід закрануў на рэкурсіі ў класе. 1173 00:58:05,479 --> 00:58:07,270 І гэта паняцце мы пагаворым пра больш. 1174 00:58:07,270 --> 00:58:11,430 Гэта што гэта, гэтыя дзве лініі Тут, на самай справе гэта проста праграма 1175 00:58:11,430 --> 00:58:13,860 кажу гэта, каб запусціць сябе з другога ўваход. 1176 00:58:13,860 --> 00:58:17,230 Такім чынам, замест запуску сябе з паўната п элементаў, 1177 00:58:17,230 --> 00:58:20,530 Вы можаце разбіць яго ўніз ў левая палова і правая палова 1178 00:58:20,530 --> 00:58:22,680 а затым запусціць яго зноў. 1179 00:58:22,680 --> 00:58:26,050 >> І тады мы будзем глядзець на яго візуальна, таму што я візуальны вучань. 1180 00:58:26,050 --> 00:58:27,270 Гэта працуе лепш для мяне. 1181 00:58:27,270 --> 00:58:29,890 Такім чынам, мы будзем глядзець на наглядным прыкладзе тут. 1182 00:58:29,890 --> 00:58:36,237 >> Скажам, мы маем масіў, шэсць Элементы, 3, 5, 2, 6, 4, 1, ня адсартаваныя. 1183 00:58:36,237 --> 00:58:37,820 Добра, ёсць шмат на гэтай старонцы. 1184 00:58:37,820 --> 00:58:43,179 Так што, калі вы, хлопцы, можаце паглядзець на Першы крок тут, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 Вы можаце падзяліць яго напалову. 1186 00:58:44,220 --> 00:58:45,976 У вас ёсць 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Вы ведаеце, што гэта вам aren't-- не ведаю, калі яны сартуюцца ці не, 1188 00:58:48,850 --> 00:58:52,517 так вы трымаеце разбіваючы іх у палове, напалову, напалову, пакуль у рэшце рэшт, 1189 00:58:52,517 --> 00:58:53,600 ў вас ёсць толькі адзін элемент. 1190 00:58:53,600 --> 00:58:56,790 І адзін элемент заўсёды сартуюцца, праўда? 1191 00:58:56,790 --> 00:59:01,560 >> Такім чынам, мы ведаем, што 3, 5, 2, 4, 6, 1, самі па сабе, сартуюцца. 1192 00:59:01,560 --> 00:59:05,870 І зараз мы можам пакласці іх назад разам. 1193 00:59:05,870 --> 00:59:07,510 Такім чынам, мы ведаем 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Ставім іх разам. 1195 00:59:08,510 --> 00:59:09,617 Мы ведаем, што гэта адсартаваны. 1196 00:59:09,617 --> 00:59:10,450 У 2-х да гэтага часу там. 1197 00:59:10,450 --> 00:59:11,830 Мы можам паставіць 4 і 6 разам. 1198 00:59:11,830 --> 00:59:13,996 Мы ведаем, што гэта сартуецца, такім чынам, мы пакласці, што разам. 1199 00:59:13,996 --> 00:59:14,940 А 1 ёсць. 1200 00:59:14,940 --> 00:59:18,720 >> А потым вы проста паглядзіце на гэтыя дзве палоўкі прама тут. 1201 00:59:18,720 --> 00:59:21,300 Вы маеце 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Вы можаце проста параўнаць пачатак усяго. 1203 00:59:23,465 --> 00:59:26,340 Таму што вы ведаеце, што гэта сартуецца і вы ведаеце, што гэта сартуецца. 1204 00:59:26,340 --> 00:59:29,360 Тады вы не павінны нават параўнаць 5, вы проста параўнаць 3. 1205 00:59:29,360 --> 00:59:32,070 А 2 менш, чым 3, так Вы ведаеце, 2 неабходна перайсці ў канец. 1206 00:59:32,070 --> 00:59:33,120 >> Тое ж самае там. 1207 00:59:33,120 --> 00:59:34,740 1-неабходна перайсці сюды. 1208 00:59:34,740 --> 00:59:37,330 А потым, калі вы ідзяце, каб пакласці гэтыя два значэння разам, 1209 00:59:37,330 --> 00:59:39,950 Вы ведаеце, што гэта сартуецца і Вы ведаеце, што сартуецца. 1210 00:59:39,950 --> 00:59:43,240 Так то 1 і 2, 1 складае менш за 2. 1211 00:59:43,240 --> 00:59:45,570 Гэта сведчыць аб тым, што 1 павінны пайсці на канцы гэтага 1212 00:59:45,570 --> 00:59:47,480 нават не гледзячы на ​​3 ці 5. 1213 00:59:47,480 --> 00:59:50,100 А потым у 4, вы можаце проста праверыць, што ідзе прама тут. 1214 00:59:50,100 --> 00:59:51,480 Вы не павінны глядзець на 5. 1215 00:59:51,480 --> 00:59:52,570 Тое ж самае з 6. 1216 00:59:52,570 --> 00:59:55,860 Вы ведаеце, што гэта проста 6-- не павінны быць разгледжаны. 1217 00:59:55,860 --> 00:59:57,870 >> І таму ў гэтым шляху, вы толькі выратаваць сябе 1218 00:59:57,870 --> 00:59:59,526 шмат крокаў, калі вы параўноўваеце. 1219 00:59:59,526 --> 01:00:02,150 Вы не павінны параўноўваць кожны Элемент з іншымі элементамі. 1220 01:00:02,150 --> 01:00:05,230 Вы проста параўнайце супраць тых што вам трэба, каб параўнаць яе з. 1221 01:00:05,230 --> 01:00:06,870 Так што нібыта абстрактнай канцэпцыі. 1222 01:00:06,870 --> 01:00:10,540 Не турбуйцеся, калі гэта не дастаткова ўдару вас прама яшчэ. 1223 01:00:10,540 --> 01:00:14,740 Але, як правіла, гэта як сартаванне зліццём працуе. 1224 01:00:14,740 --> 01:00:17,750 Пытанні, простых пытанняў, перш, чым я рухацца далей? 1225 01:00:17,750 --> 01:00:18,550 Так. 1226 01:00:18,550 --> 01:00:22,230 >> АЎДЫТОРЫЯ: Дык вы сказалі, што вы бераце 1, а затым 4 і 6 1227 01:00:22,230 --> 01:00:23,860 і паклаў іх у. 1228 01:00:23,860 --> 01:00:26,800 Так не those-- ня Вы шукаеце на іх 1229 01:00:26,800 --> 01:00:28,544 як асобныя элементы, а не як у цэлым? 1230 01:00:28,544 --> 01:00:29,210 ANDI Пэн: Так. 1231 01:00:29,210 --> 01:00:32,020 Так, што адбываецца з'яўляецца тое, што вы ў асноўным 1232 01:00:32,020 --> 01:00:33,650 ствараюць зусім новы масіў. 1233 01:00:33,650 --> 01:00:36,690 Такім чынам, вы ведаеце, што, вось, у мяне ёсць два масіва памерам 3, праўда? 1234 01:00:36,690 --> 01:00:39,600 Такім чынам, вы ведаеце, што мой адсартаваны масіў павінен мець шэсць элементаў. 1235 01:00:39,600 --> 01:00:42,270 Такім чынам, вы проста стварыць Новы аб'ём памяці. 1236 01:00:42,270 --> 01:00:44,270 Дык вы накшталт як быўшы марнатраўным памяці, 1237 01:00:44,270 --> 01:00:46,186 але гэта не мае значэння таму што гэта так мала. 1238 01:00:46,186 --> 01:00:48,590 Такім чынам, вы глядзіце на 1 і вы паглядзіце на 2. 1239 01:00:48,590 --> 01:00:50,770 І вы ведаеце, што 1 менш, чым 2. 1240 01:00:50,770 --> 01:00:53,840 Такім чынам, вы ведаеце, што 1 павінны ісці ў пачатак усіх тых. 1241 01:00:53,840 --> 01:00:55,850 >> Вы нават не трэба глядзець на 3 і 5. 1242 01:00:55,850 --> 01:00:57,400 Такім чынам, вы ведаеце, 1 ідзе туды. 1243 01:00:57,400 --> 01:00:59,300 Тады вы ў асноўным адсекчы 1. 1244 01:00:59,300 --> 01:01:00,370 Гэта, быццам бы, памёр для нас. 1245 01:01:00,370 --> 01:01:03,690 Тады мы проста павінны 2, 3, 5, а затым 4 і 6. 1246 01:01:03,690 --> 01:01:06,270 І тады вы ведаеце, што вы параўнаць 4 і 2, 1247 01:01:06,270 --> 01:01:07,560 ой, 2 павінны пайсці туды. 1248 01:01:07,560 --> 01:01:09,685 Такім чынам, вы пляснуць 2 ўніз, рубіце яго. 1249 01:01:09,685 --> 01:01:12,060 Тады вы проста ёсць 3 і 5 у 4 і 6. 1250 01:01:12,060 --> 01:01:14,650 І вы проста трымаць яго драбненне пакуль вы не пакласці іх у масіве. 1251 01:01:14,650 --> 01:01:17,110 >> АЎДЫТОРЫЯ: Дык ты проста заўсёды Параўноўваючы [неразборліва]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Пэн: Точно. 1253 01:01:17,710 --> 01:01:19,590 Так што ў гэтым сэнсе, вы проста параўнанне, па сутнасці, 1254 01:01:19,590 --> 01:01:21,240 адзін нумар супраць іншы нумар. 1255 01:01:21,240 --> 01:01:22,990 І таму што вы ведаеце што гэта сартуецца, вам 1256 01:01:22,990 --> 01:01:24,350 не прыйдзецца шукаць праз ўсе нумары. 1257 01:01:24,350 --> 01:01:25,870 Вы проста павінны паглядзець на першы. 1258 01:01:25,870 --> 01:01:27,582 І тады вы можаце проста пляснуць іх уніз, таму што вы ведаеце, 1259 01:01:27,582 --> 01:01:29,640 яны належаць, дзе яны павінны належаць. 1260 01:01:29,640 --> 01:01:31,030 Так. 1261 01:01:31,030 --> 01:01:32,920 Добры пытанне. 1262 01:01:32,920 --> 01:01:35,290 >> І потым, калі любы з вас трохі амбіцыйны, 1263 01:01:35,290 --> 01:01:38,660 не саромейцеся, каб паглядзець на гэты код. 1264 01:01:38,660 --> 01:01:40,680 Гэта на самай справе фізічная рэалізацыя 1265 01:01:40,680 --> 01:01:42,150 пра тое, як мы павінны напісаць сартавання зліццём. 1266 01:01:42,150 --> 01:01:44,070 І вы можаце бачыць, гэта вельмі мала. 1267 01:01:44,070 --> 01:01:46,310 Але ідэі, якія ляжаць у гэта даволі складаная. 1268 01:01:46,310 --> 01:01:50,865 Так што, калі вы адчуваеце, як малюнак на гэта у выкананні хатніх заданняў сёння, не саромейцеся. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> ДОБРА. 1271 01:01:54,740 --> 01:01:58,070 Так і Давід падышоў гэта ў лекцыі. 1272 01:01:58,070 --> 01:02:00,660 Што ў лепшым выпадку Час аўтаномнай працы, у горшым выпадку час аўтаномнай працы, 1273 01:02:00,660 --> 01:02:05,680 і чаканыя аўтаномнай працы ад сартавання зліццём? 1274 01:02:05,680 --> 01:02:07,260 Праз пару секунд, каб падумаць. 1275 01:02:07,260 --> 01:02:11,198 Гэта даволі цяжка, але выгляд інтуітыўным, калі вы думаеце пра гэта. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Добра. 1278 01:02:23,054 --> 01:02:25,269 >> Залы: у горшым выпадку п п часопіса? 1279 01:02:25,269 --> 01:02:26,060 ANDI Пэн: Точно. 1280 01:02:26,060 --> 01:02:29,380 І чаму гэта п п ўвайсці ў сістэму. 1281 01:02:29,380 --> 01:02:32,230 >> АЎДЫТОРЫЯ: Хіба гэта не таму, што ён становіцца экспанентна хутчэй, 1282 01:02:32,230 --> 01:02:35,390 так што гэта, як функцыі, якія а проста быць п 1283 01:02:35,390 --> 01:02:37,529 квадрат або што-то? 1284 01:02:37,529 --> 01:02:38,320 ANDI Пэн: Точно. 1285 01:02:38,320 --> 01:02:40,750 Такім чынам, прычына, па якой выканання на гэта н часопіса 1286 01:02:40,750 --> 01:02:44,310 п because--, што ты рабіць ва ўсіх гэтых крокаў? 1287 01:02:44,310 --> 01:02:46,190 Вы проста секчы яго напалову, праўда? 1288 01:02:46,190 --> 01:02:48,750 І таму, калі мы робім увайсці, усё, што ён робіць 1289 01:02:48,750 --> 01:02:53,150 дзеліць праблему напалову, у два разы, у два разы, у больш за палову. 1290 01:02:53,150 --> 01:02:56,430 І ў гэтым сэнсе, вы можаце выгляд з ліквідаваць лінейную мадэль 1291 01:02:56,430 --> 01:02:57,510 што мы выкарыстоўвалі. 1292 01:02:57,510 --> 01:03:00,254 Таму што, калі вы нарэзаць рэчы ў палове, гэта часопіс. 1293 01:03:00,254 --> 01:03:02,420 Вось толькі матэматычны спосаб прадстаўлення яго. 1294 01:03:02,420 --> 01:03:06,310 >> І, нарэшце, у канцы, вы проста зрабіць адзін апошні пас праз 1295 01:03:06,310 --> 01:03:07,930 паставіць ўсе з іх у парадку, праўда? 1296 01:03:07,930 --> 01:03:10,330 І так, калі вы проста павінны праверыць адну рэч, гэта п. 1297 01:03:10,330 --> 01:03:13,420 І так ты накшталт множання разам. 1298 01:03:13,420 --> 01:03:17,660 Так што гэта, як вы атрымалі, што канчатковы праверыць п сюды з бярвёны п 1299 01:03:17,660 --> 01:03:18,390 тут. 1300 01:03:18,390 --> 01:03:21,060 І калі памножыць ім, што гэта н н ўвайсці ў сістэму. 1301 01:03:21,060 --> 01:03:26,100 >> І так у лепшым выпадку і горшыя Корпус і чакаецца, усё п п ўвайсці ў сістэму. 1302 01:03:26,100 --> 01:03:27,943 Гэта таксама, як іншага роду. 1303 01:03:27,943 --> 01:03:30,090 Гэта як выбар роду у тым сэнсе, што 1304 01:03:30,090 --> 01:03:32,131 Не мае значэння, што ваш Спіс, гэта проста будзе 1305 01:03:32,131 --> 01:03:34,801 каб зрабіць тое ж самае кожны раз. 1306 01:03:34,801 --> 01:03:35,300 ДОБРА. 1307 01:03:35,300 --> 01:03:39,950 Такім чынам, як вы, хлопцы, можаце бачыць, нават калі расліны, якія мы пайшлі through-- п 1308 01:03:39,950 --> 01:03:41,660 квадрат, гэта не вельмі эфектыўна. 1309 01:03:41,660 --> 01:03:47,060 І нават у гэтым п п часопіса не самым эфектыўным. 1310 01:03:47,060 --> 01:03:49,720 Калі вы, хлопцы, цікава, ёсць механізмы сартавання 1311 01:03:49,720 --> 01:03:54,310 якія з'яўляюцца настолькі эфектыўна, што яны амаль практычна плоскім ў рэжыме выканання. 1312 01:03:54,310 --> 01:03:55,420 >> У вас ёсць некаторыя часопіс N. 1313 01:03:55,420 --> 01:03:58,190 У вас ёсць некаторыя часопіс часопіса N. 1314 01:03:58,190 --> 01:04:00,330 Мы не дакранаемся іх у гэтым класе цяпер. 1315 01:04:00,330 --> 01:04:02,663 Але калі вы, хлопцы, цікава, не саромейцеся Google, што 1316 01:04:02,663 --> 01:04:04,392 найбольш эфектыўныя механізмы сартавання. 1317 01:04:04,392 --> 01:04:06,350 Я не ведаю, ці ёсць некаторыя сапраўды смешныя, 1318 01:04:06,350 --> 01:04:09,860 like-- ёсць некаторыя сапраўды смешныя, якія людзі робяць. 1319 01:04:09,860 --> 01:04:12,210 І вы дзівіцеся, як яны калі-небудзь думалі пра гэта. 1320 01:04:12,210 --> 01:04:15,730 Так Google, калі ў вас ёсць запасны Час, на тое, што некаторыя пацешныя спосабы 1321 01:04:15,730 --> 01:04:17,730 што people-- а таксама эфектыўныя ways-- людзі 1322 01:04:17,730 --> 01:04:20,371 змаглі рэалізаваць разнастайныя. 1323 01:04:20,371 --> 01:04:20,870 ДОБРА. 1324 01:04:20,870 --> 01:04:22,880 І вось толькі маленькі зручны графік. 1325 01:04:22,880 --> 01:04:26,850 Я ведаю ўсё пра цябе, да гэтага віктарыне 0, будзе ў вашай пакоі, верагодна, спрабуе 1326 01:04:26,850 --> 01:04:27,960 запомніць гэта. 1327 01:04:27,960 --> 01:04:30,940 Так што прыемна там для вас, хлопцы. 1328 01:04:30,940 --> 01:04:37,120 Толькі не забывайце, логіку, made-- Таму гэтыя лічбы былі адбываецца. 1329 01:04:37,120 --> 01:04:39,870 Калі вы заўсёды губляецца, проста пераканайцеся, упэўнены, што вы ведаеце, што гатунку. 1330 01:04:39,870 --> 01:04:40,820 І вы можаце запусціць праз іх у сваім розуме 1331 01:04:40,820 --> 01:04:42,903 каб высветліць, чаму тыя, адказы адказы на гэтыя пытанні. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Добра. 1334 01:04:47,600 --> 01:04:49,680 Такім чынам, мы збіраемся, каб перамясціць на, нарэшце, пошуку. 1335 01:04:49,680 --> 01:04:51,638 Таму што, як тых з вас, хто чытаў PSET, 1336 01:04:51,638 --> 01:04:55,175 пошук таксама з'яўляецца часткай Праблема гэтым тыдні задае. 1337 01:04:55,175 --> 01:04:57,300 Вам будзе прапанавана ажыццявіць два тыпу пошукаў. 1338 01:04:57,300 --> 01:05:00,070 Адным з іх з'яўляецца лінейны пошук і адзін двайковы пошук. 1339 01:05:00,070 --> 01:05:01,760 >> Такім чынам, лінейны пошук даволі лёгка. 1340 01:05:01,760 --> 01:05:04,070 Вы проста хочаце, каб пошук элемента з спісу, каб убачыць, калі вы яго атрымаеце. 1341 01:05:04,070 --> 01:05:05,444 Вы проста павінны перабору. 1342 01:05:05,444 --> 01:05:08,170 І калі ён роўны тое, вы можаце проста вярнуць яго, праўда? 1343 01:05:08,170 --> 01:05:10,890 Але той, што мы найбольш зацікаўлены ў размове аб 1344 01:05:10,890 --> 01:05:14,550 гэта бінарны пошук, права, якое з'яўляецца падзяляй і ўладар механізм, які 1345 01:05:14,550 --> 01:05:18,190 Дэвід дэманстраваў ў лекцыі. 1346 01:05:18,190 --> 01:05:20,810 >> Памятаеце прыклад тэлефоннай кнігі што ён працягвае выхоўваць, 1347 01:05:20,810 --> 01:05:23,960 той, які ён накшталт змагаліся трохі на мінулы год, 1348 01:05:23,960 --> 01:05:27,530 дзе вы падзеліце задачу на палове, у два разы, у два разы, зноў і зноў, 1349 01:05:27,530 --> 01:05:30,730 пакуль вы не знойдзеце тое, што вы шукаеце? 1350 01:05:30,730 --> 01:05:33,727 І вы атрымалі час выканання, што добра. 1351 01:05:33,727 --> 01:05:35,810 І вы можаце бачыць, гэта значна больш эфектыўным 1352 01:05:35,810 --> 01:05:39,080 чым любы іншы тып пошуку. 1353 01:05:39,080 --> 01:05:41,880 >> Такім чынам, шлях, які мы б ісці аб рэалізацыі двайковага пошуку 1354 01:05:41,880 --> 01:05:46,510 ёсць, калі ў нас было мноства, Індэкс 0 да 6, сем элементаў, 1355 01:05:46,510 --> 01:05:49,790 мы можам глядзець у сярэдзіне, right-- прабачце, калі наша пытанне first-- 1356 01:05:49,790 --> 01:05:53,840 калі мы хочам, каб задаць пытанне аб, ня масіў ўтрымлівае элемент 7, 1357 01:05:53,840 --> 01:05:56,840 Відавочна, быўшы людзей, і які мае такі маленькі масіў, гэта проста для нас 1358 01:05:56,840 --> 01:05:58,210 каб сказаць так. 1359 01:05:58,210 --> 01:06:05,750 Але шлях да рэалізацыі двайковы Пошук будзе выглядаць у сярэдзіне. 1360 01:06:05,750 --> 01:06:08,020 >> Мы ведаем, што індэкс 3 сярэдні, таму што мы 1361 01:06:08,020 --> 01:06:09,270 ведаю, што ёсць сем элементаў. 1362 01:06:09,270 --> 01:06:10,670 Што 7 дзеліцца на 2? 1363 01:06:10,670 --> 01:06:12,850 Вы можаце адсекчы што дадатковы 1. 1364 01:06:12,850 --> 01:06:14,850 Вы атрымалі 3 у сярэдзіне. 1365 01:06:14,850 --> 01:06:17,590 Так масіў з 3 роўна 7? 1366 01:06:17,590 --> 01:06:18,900 Гэта не так, праўда? 1367 01:06:18,900 --> 01:06:21,050 Але мы можам зрабіць пару чэкаў. 1368 01:06:21,050 --> 01:06:25,380 Гэта масіў з 3 менш, чым 7 або гэта масіў з 3 больш, чым 7? 1369 01:06:25,380 --> 01:06:27,240 >> І мы ведаем, што гэта менш, чым 7. 1370 01:06:27,240 --> 01:06:30,259 Такім чынам, мы ведаем, што, ну, яна павінна не можа быць у левай палове. 1371 01:06:30,259 --> 01:06:32,300 Мы ведаем, што гэта павінна быць у правай палове, праўда? 1372 01:06:32,300 --> 01:06:34,662 Такім чынам, мы можам проста адсекчы палову масіва. 1373 01:06:34,662 --> 01:06:36,370 Мы нават не павінны глядзець на яго больш. 1374 01:06:36,370 --> 01:06:38,711 Таму што мы ведаем, што палова нашага problem-- 1375 01:06:38,711 --> 01:06:41,210 мы ведаем, што адказ знаходзіцца ў правая палова нашай задачы. 1376 01:06:41,210 --> 01:06:42,580 Такім чынам, мы проста паглядзіце на гэта цяпер. 1377 01:06:42,580 --> 01:06:44,860 >> Так што цяпер мы глядзім на Сярэдзіна тое, што засталося. 1378 01:06:44,860 --> 01:06:46,880 Гэты паказчык 5. 1379 01:06:46,880 --> 01:06:50,200 Мы робім тое ж самае яшчэ раз праверку і мы бачым, што гэта менш. 1380 01:06:50,200 --> 01:06:52,050 Такім чынам, мы глядзім у левай частцы, што. 1381 01:06:52,050 --> 01:06:53,430 І тады мы бачым, што чэк. 1382 01:06:53,430 --> 01:06:57,600 Ці з'яўляецца значэнне масіва ў Індэкс 4 роўная 7? 1383 01:06:57,600 --> 01:06:58,260 Гэта. 1384 01:06:58,260 --> 01:07:03,580 Такім чынам, мы можам вярнуцца так, таму што мы знайшлі значэнне ў нашым спісе. 1385 01:07:03,580 --> 01:07:06,738 Ці шлях я прайшоў што сэнс усім? 1386 01:07:06,738 --> 01:07:08,760 ДОБРА. 1387 01:07:08,760 --> 01:07:11,670 Я дам вам, хлопцы, можа быць, як, тры, чатыры хвіліны, каб высветліць, 1388 01:07:11,670 --> 01:07:13,270 як псевдокод гэта. 1389 01:07:13,270 --> 01:07:18,070 >> Такім чынам, уявіце, я папрасіў вас напісаць Функцыя называецца пошук (), што вярнуўся 1390 01:07:18,070 --> 01:07:20,640 значэнне, лагічнае значэнне, што гэта праўда ці false-- як, 1391 01:07:20,640 --> 01:07:22,970 дакладна, калі вы знайшлі значэнне, хлусня, калі вы не зрабілі. 1392 01:07:22,970 --> 01:07:25,230 І тады вы былі прайшоў у кошту вы 1393 01:07:25,230 --> 01:07:28,410 шукалі ў каштоўнасці, якія гэта array-- аб, я вызначана паставіць 1394 01:07:28,410 --> 01:07:29,410 што ў няправільным месцы. 1395 01:07:29,410 --> 01:07:29,580 ДОБРА. 1396 01:07:29,580 --> 01:07:31,829 У любым выпадку, што павінна быць быў справа значэнняў. 1397 01:07:31,829 --> 01:07:36,280 А потым Int N гэты лік элементаў у гэтым масіве. 1398 01:07:36,280 --> 01:07:39,430 Як бы вы ісці аб спробе у псевдокоде гэтую праблему ў? 1399 01:07:39,430 --> 01:07:41,630 Я дам вам, хлопцы, як тры хвіліны, каб зрабіць гэта. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Не, я думаю, што ёсць only-- так, ёсць адна прама тут. 1402 01:08:02,595 --> 01:08:03,261 АЎДЫТОРЫЯ: Ці магу я? 1403 01:08:03,261 --> 01:08:04,388 ANDI Пэн: Так, у мяне ёсць ты. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Гэта працуе? 1406 01:08:11,050 --> 01:08:12,290 ОК, крута. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> ДОБРА. 1409 01:10:44,720 --> 01:10:47,630 Усе правільныя хлопцы, мы збіраецца утаймаваць яго. 1410 01:10:47,630 --> 01:10:49,730 ДОБРА. 1411 01:10:49,730 --> 01:10:54,020 Так выкажам здагадку, што ў нас ёсць гэтая выдатная трохі масіў з п значэнняў ў ім. 1412 01:10:54,020 --> 01:10:55,170 Я не маляваць лініі. 1413 01:10:55,170 --> 01:10:58,649 Але як бы мы ісці аб спрабую напісаць гэта? 1414 01:10:58,649 --> 01:11:00,440 Хто-небудзь хоча даць мне першую лінію? 1415 01:11:00,440 --> 01:11:02,814 Калі вы хочаце, каб даць мне Першы радок гэтага псевдокода. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> АЎДЫТОРЫЯ: [неразборліва] 1418 01:11:08,430 --> 01:11:10,138 АЎДЫТОРЫЯ: Вы хацелі для перабору through-- 1419 01:11:10,138 --> 01:11:11,094 АЎДЫТОРЫЯ: Проста яшчэ адзін цыкл? 1420 01:11:11,094 --> 01:11:11,760 АЎДЫТОРЫЯ: --для. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Пэн: Так што гэта адно крыху больш складана. 1423 01:11:17,780 --> 01:11:23,130 Падумайце about-- вы хочаце трымаць працуе гэты цыкл 1424 01:11:23,130 --> 01:11:27,950 зноў і зноў, пакуль, калі? 1425 01:11:27,950 --> 01:11:30,819 >> АЎДЫТОРЫЯ: Да [неразборліва] значэнне роўна гэтага значэння. 1426 01:11:30,819 --> 01:11:31,610 ANDI Пэн: Точно. 1427 01:11:31,610 --> 01:11:33,900 Такім чынам, вы можаце на самой справе проста write-- мы можам нават спрасціць яго больш. 1428 01:11:33,900 --> 01:11:35,630 Мы можам проста зрабіць той час як цыкл, праўда? 1429 01:11:35,630 --> 01:11:39,380 Такім чынам, вы можаце проста loop-- мы ведаем, што гэта нейкі час. 1430 01:11:39,380 --> 01:11:42,850 Але цяпер, я збіраюся сказаць "пятлю" - праз што? 1431 01:11:42,850 --> 01:11:46,640 Цыкл until-- што наш заканчваючы стан? 1432 01:11:46,640 --> 01:11:47,510 Я думаю, што я чуў. 1433 01:11:47,510 --> 01:11:48,530 Я чуў, хто-небудзь сказаць. 1434 01:11:48,530 --> 01:11:51,255 >> Аўдыторыя: Значэнні роўная сярэдзіну. 1435 01:11:51,255 --> 01:11:52,255 ANDI Пэн: Скажы гэта яшчэ раз. 1436 01:11:52,255 --> 01:11:54,470 АЎДЫТОРЫЯ: Ці, да Значэнне вы шукаеце 1437 01:11:54,470 --> 01:11:58,470 Для роўная сярэдняга значэння. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Пэн: Што рабіць, калі гэта не там? 1439 01:12:00,280 --> 01:12:03,113 Што рабіць, калі значэнне вы шукаеце для на самай справе не ў гэтым масіве? 1440 01:12:03,113 --> 01:12:05,890 АЎДЫТОРЫЯ: Вы вяртаецеся 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Пэн: Але тое, што мы хочам, каб цыкл да калі ў нас ёсць стан? 1442 01:12:08,850 --> 01:12:09,350 Так. 1443 01:12:09,350 --> 01:12:11,239 >> АЎДЫТОРЫЯ: пакуль ёсць толькі адно значэнне? 1444 01:12:11,239 --> 01:12:13,530 ANDI Пэн: Вы можаце цыкл until-- так што вы ведаеце, што вы 1445 01:12:13,530 --> 01:12:15,714 будзе мець максімальную значэнне, ці не так? 1446 01:12:15,714 --> 01:12:18,130 І вы ведаеце, што вы збіраецеся мець значэнне мін, праўда? 1447 01:12:18,130 --> 01:12:20,379 Таму што таксама, гэта тое, што Я забыўся сказаць, перш чым, 1448 01:12:20,379 --> 01:12:22,640 што нешта, што гэта крытычна бінарнага пошуку 1449 01:12:22,640 --> 01:12:24,182 з'яўляецца тое, што ваш масіў ўжо адсартаваныя. 1450 01:12:24,182 --> 01:12:26,973 Таму што няма ніякага спосабу рабіць гэта, калі яны проста выпадковыя значэння. 1451 01:12:26,973 --> 01:12:29,190 Вы не ведаеце, калі адзін гэта больш, чым іншыя, праўда? 1452 01:12:29,190 --> 01:12:32,720 >> Такім чынам, вы ведаеце, што ваш Макс і Вашы хвілін тут, праўда? 1453 01:12:32,720 --> 01:12:35,590 Калі вы збіраецеся быць рэгулявання Ваш макс ў вашых хвілін і mid-- 1454 01:12:35,590 --> 01:12:38,470 давайце выкажам здагадку, ваш Значэнне сярэдняга правільна here-- 1455 01:12:38,470 --> 01:12:43,910 Вы збіраецеся ў асноўным цыкл датуль, мінімальная ня 1456 01:12:43,910 --> 01:12:47,510 прыкладна тое ж самае, як ваш макс, прама ці калі ваш максімум не тое ж самае, як ваш мін. 1457 01:12:47,510 --> 01:12:48,040 Дакладна? 1458 01:12:48,040 --> 01:12:51,340 Таму што, калі гэта адбудзецца, вы ведаеце, што Вы ў канчатковым выніку трапіў у такое ж значэнне. 1459 01:12:51,340 --> 01:12:59,135 Дык вы не хочаце, каб завесы, пакуль ваш мін менш або роўна, мэтай якіх упс, 1460 01:12:59,135 --> 01:13:01,510 не менш або роўна, інакш around-- Макс. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Хіба што сэнс? 1463 01:13:16,160 --> 01:13:18,810 Я ўзяў некалькі спробаў, каб атрымаць гэта права. 1464 01:13:18,810 --> 01:13:21,869 Але цыкл, пакуль ваш максімальнага значэння па сутнасці амаль няма 1465 01:13:21,869 --> 01:13:23,410 чым або роўна вашай мінімум, праўда? 1466 01:13:23,410 --> 01:13:25,201 Вось калі вы ведаеце, што вы сышліся. 1467 01:13:25,201 --> 01:13:29,290 АЎДЫТОРЫЯ: Калі ваша максімальная значэнне менш, чым мінімум? 1468 01:13:29,290 --> 01:13:31,040 ANDI Пэн: Калі вы трымаеце рэгулюючы яго, што 1469 01:13:31,040 --> 01:13:32,380 гэта тое, што мы збіраемся каб рабіць у гэтым. 1470 01:13:32,380 --> 01:13:33,460 Ці мае гэта сэнс? 1471 01:13:33,460 --> 01:13:35,750 Мінімальная і максімальная проста цэлыя лікі, мы, верагодна, 1472 01:13:35,750 --> 01:13:39,260 збіраецца хочаце стварыць, каб трымаць трэк, дзе мы шукаем. 1473 01:13:39,260 --> 01:13:41,790 Паколькі масіў існуе незалежна ад таго, што мы робім. 1474 01:13:41,790 --> 01:13:45,030 Маўляў, мы на самай справе не фізічна отрубание масіва, праўда? 1475 01:13:45,030 --> 01:13:47,261 Мы проста рэгулюючы дзе мы шукаем. 1476 01:13:47,261 --> 01:13:48,136 Ці мае гэта сэнс? 1477 01:13:48,136 --> 01:13:48,472 >> АЎДЫТОРЫЯ: Так. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Пэн: ОК. 1479 01:13:49,110 --> 01:13:57,090 Так што, калі гэта ўмова нашай завесы, тое, што мы хочам ўнутры гэтай завесы? 1480 01:13:57,090 --> 01:13:58,700 Што мы збіраемся быць жаданне зрабіць? 1481 01:13:58,700 --> 01:14:02,390 Так што цяпер, у нас ёсць макс і мін, права, 1482 01:14:02,390 --> 01:14:04,962 верагодна, створана дзе-то тут. 1483 01:14:04,962 --> 01:14:07,170 Мы збіраемся, верагодна, хочаце знайсці сярэдзіну, праўда? 1484 01:14:07,170 --> 01:14:08,450 Як мы збіраемся, каб быць магчымасць знайсці сярэдзіну? 1485 01:14:08,450 --> 01:14:09,491 Што mathematical-- 1486 01:14:09,491 --> 01:14:11,079 АЎДЫТОРЫЯ: Макс плюс мін падзеленыя на 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI Пэн: Точно. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Ці мае гэта сэнс? 1490 01:14:21,620 --> 01:14:25,780 І вы, хлопцы, зразумець, чаму мы не проста use--, чаму мы зрабілі гэта 1491 01:14:25,780 --> 01:14:27,850 а не рабіць проста п дзеліцца на 2? 1492 01:14:27,850 --> 01:14:30,310 Гэта таму, што п з'яўляецца значэнне што збіраецца застацца тое ж самае. 1493 01:14:30,310 --> 01:14:30,979 Дакладна? 1494 01:14:30,979 --> 01:14:34,020 Але, як мы скарэкціруем нашу мінімум і Максімальныя значэння, яны збіраюцца змяніць. 1495 01:14:34,020 --> 01:14:36,040 І ў выніку, наш сярэдні збіраецца мяняць занадта. 1496 01:14:36,040 --> 01:14:37,873 Дык вось чаму мы хочам зрабіць гэта прама тут. 1497 01:14:37,873 --> 01:14:38,510 ДОБРА. 1498 01:14:38,510 --> 01:14:41,600 >> А потым, у цяперашні час, што мы знайшлі our-- так. 1499 01:14:41,600 --> 01:14:44,270 >> АЎДЫТОРЫЯ: Проста хутка question-- калі вы кажаце, мін і макс, 1500 01:14:44,270 --> 01:14:46,410 мы мяркуючы, што гэта ўжо адсартаваныя? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Пэн: Так, гэта на самай справе перадумовай для бінарнага пошуку, 1502 01:14:48,400 --> 01:14:49,816 што вы павінны ведаць, што гэта сартуецца. 1503 01:14:49,816 --> 01:14:53,660 Менавіта таму-то, вы пішаце ў вашым Праблема ўсталяваць да вашага бінарнага пошуку. 1504 01:14:53,660 --> 01:14:55,910 ДОБРА. 1505 01:14:55,910 --> 01:14:58,876 Так што цяпер мы ведаем, дзе наша сярэдзіна з'яўляецца тое, што вы хочаце зрабіць тут? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> АЎДЫТОРЫЯ: Мы хочам, каб параўнаць што да іншага. 1508 01:15:04,319 --> 01:15:05,110 ANDI Пэн: Точно. 1509 01:15:05,110 --> 01:15:12,280 Такім чынам, вы будзеце параўноўваць з сярэдзіны да значэння, ці не так? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 І што гэта кажа нам, калі мы параўноўваем? 1512 01:15:18,670 --> 01:15:22,226 Што мы хочам рабіць далей? 1513 01:15:22,226 --> 01:15:25,389 >> АЎДЫТОРЫЯ: Калі гэтае значэньне большае чым сярэдзіне, мы хочам, каб адрэзаць яго. 1514 01:15:25,389 --> 01:15:26,180 ANDI Пэн: Точно. 1515 01:15:26,180 --> 01:15:33,940 Такім чынам, калі значэнне больш чым сярэдзіне, мы 1516 01:15:33,940 --> 01:15:36,550 захоча змяніць гэтыя Мінімальны і вычарпаны, праўда? 1517 01:15:36,550 --> 01:15:38,980 Што мы хочам змяніць? 1518 01:15:38,980 --> 01:15:42,145 Так што, калі мы ведаем, што дзесьці значэнне тут, што вы ў нас змяніць? 1519 01:15:42,145 --> 01:15:44,758 Мы хочам змяніць нашу Мінімальны быць у сярэдзіне, ці не так? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 А потым яшчэ, калі ён знаходзіцца ў гэтым палова, што мы хочам змяніць? 1522 01:15:54,292 --> 01:15:55,306 >> АЎДЫТОРЫЯ: Ваша максімальная. 1523 01:15:55,306 --> 01:15:55,972 ANDI Пэн: Так. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 А потым вы проста трымаць цыкл, праўда? 1526 01:16:04,680 --> 01:16:08,920 Таму што цяпер, пасля адной ітэрацыі праз, у вас ёсць макс тут. 1527 01:16:08,920 --> 01:16:10,760 І тады вы можаце пералічыць сярэдзіне. 1528 01:16:10,760 --> 01:16:11,990 І тады вы можаце параўнаць. 1529 01:16:11,990 --> 01:16:14,766 І вы збіраецеся працягваць не да хвілін і Maxes 1530 01:16:14,766 --> 01:16:15,890 істотна сышліся. 1531 01:16:15,890 --> 01:16:17,890 І вось, калі вы ведаеце, што Вы патрапілі ў канец. 1532 01:16:17,890 --> 01:16:20,280 І альбо вы знайшлі яго ці вы не ў гэтай кропцы. 1533 01:16:20,280 --> 01:16:23,170 >> Ці мае гэта сэнс для ўсіх? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 ДОБРА. 1536 01:16:26,770 --> 01:16:27,900 Гэта вельмі важна, таму што вы будзеце мець 1537 01:16:27,900 --> 01:16:29,760 каб напісаць гэта ў кодзе сёння. 1538 01:16:29,760 --> 01:16:32,660 Але вы, хлопцы, ёсць вельмі добры пачуццё, што вы павінны рабіць, 1539 01:16:32,660 --> 01:16:34,051 і гэта добра. 1540 01:16:34,051 --> 01:16:34,550 ДОБРА. 1541 01:16:34,550 --> 01:16:38,840 Такім чынам, мы атрымалі каля сямі хвіліны засталося падзел. 1542 01:16:38,840 --> 01:16:43,170 Такім чынам, мы будзем казаць аб гэта PSET, што мы будзем рабіць. 1543 01:16:43,170 --> 01:16:46,410 Такім чынам, PSET падзелены на дзве паловы. 1544 01:16:46,410 --> 01:16:50,230 Першая палова ўключае рэалізацыі знаходку 1545 01:16:50,230 --> 01:16:54,210 у якім Вы пішаце, лінейны пошук, А бінарны пошук, і алгарытм сартавання. 1546 01:16:54,210 --> 01:16:56,690 >> Такім чынам, гэта з'яўляецца першым раз у PSET дзе 1547 01:16:56,690 --> 01:17:00,050 мы будзем даваць вам, хлопцы, што называецца Код размеркавання, які з'яўляецца код 1548 01:17:00,050 --> 01:17:02,740 што мы папярэдне напісана, але проста пакінулі некалькі кавалкаў ад 1549 01:17:02,740 --> 01:17:04,635 для Вас, каб скончыць запіс. 1550 01:17:04,635 --> 01:17:07,510 Такім чынам, вы, хлопцы, калі вы глядзіце на гэта Код, вы маглі б атрымаць сапраўды страшна. 1551 01:17:07,510 --> 01:17:08,630 Калі вы проста хочаце, Ах, я не ведаю, што робіць, 1552 01:17:08,630 --> 01:17:11,670 Я не ведаеце, як, здаецца, што так складана, ах, расслабіцца. 1553 01:17:11,670 --> 01:17:12,170 Добра. 1554 01:17:12,170 --> 01:17:12,930 Чытайце спецыфікацыю. 1555 01:17:12,930 --> 01:17:16,920 Спецыфікацыя будзе растлумачыць вам дакладна што ўсе гэтыя праграмы робяць. 1556 01:17:16,920 --> 01:17:20,560 >> Напрыклад, generate.c праграма што прыйдзе з вашага PSET. 1557 01:17:20,560 --> 01:17:24,060 Вы на самой справе не маюць да яе дакрануцца, але Вы павінны разумець, што ён робіць. 1558 01:17:24,060 --> 01:17:28,550 І generate.c, усё гэта робіць, альбо генерацыі выпадковых лікаў 1559 01:17:28,550 --> 01:17:32,400 ці вы можаце даць яму насеньне, як у умоўны нумар, які ён прымае, 1560 01:17:32,400 --> 01:17:34,140 і генеруе больш лік. 1561 01:17:34,140 --> 01:17:37,170 Такім чынам, ёсць пэўны спосаб, каб ажыццявіць generate.c, у якім 1562 01:17:37,170 --> 01:17:42,760 вы можаце проста зрабіць кучу лічбаў для вас, каб праверыць свае іншыя метады на. 1563 01:17:42,760 --> 01:17:45,900 >> Так што, калі вы хочаце, каб для Напрыклад, праверыць свае знаходкі, 1564 01:17:45,900 --> 01:17:48,970 Вы хацелі б, каб запусціць generate.c, генераваць кучу лічбаў, 1565 01:17:48,970 --> 01:17:50,880 а затым запусціць функцыю памочнікаў. 1566 01:17:50,880 --> 01:17:53,930 Ваша функцыя памочнікі дзе вы на самай справе фізічна напісання кода. 1567 01:17:53,930 --> 01:17:59,330 І думаю, памочнікаў у выглядзе файла бібліятэкі Вы пішаце, што знаходка тэлефануе. 1568 01:17:59,330 --> 01:18:02,950 І так на працягу helpers.c, вы будзеце зрабіць пошуку і сартаванні. 1569 01:18:02,950 --> 01:18:06,500 >> І тады вы будзеце па сутнасці проста пакласці іх усё разам. 1570 01:18:06,500 --> 01:18:10,350 Спецыфікацыя скажа вам, як пакласці, што ў камандным радку. 1571 01:18:10,350 --> 01:18:14,880 І вы зможаце праверыць, ці з'яўляецца не ваша сартавання і пошуку працуюць. 1572 01:18:14,880 --> 01:18:15,870 Прахладны. 1573 01:18:15,870 --> 01:18:18,720 Хто-небудзь ужо пачалася, і сустракаемыя праблемы або пытанні 1574 01:18:18,720 --> 01:18:20,520 яны маюць цяпер з гэтым? 1575 01:18:20,520 --> 01:18:21,020 ДОБРА. 1576 01:18:21,020 --> 01:18:21,476 >> АЎДЫТОРЫЯ: Пачакайце. 1577 01:18:21,476 --> 01:18:21,932 У мяне ёсць пытанне. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Пэн: Так. 1579 01:18:22,844 --> 01:18:28,390 >> АЎДЫТОРЫЯ: Так што я пачаў рабіць лінейны пошук у helpers.c 1580 01:18:28,390 --> 01:18:29,670 і гэта не было сапраўды працуе. 1581 01:18:29,670 --> 01:18:34,590 Але потым я даведаўся, мы проста павінны выдаліць яго і зрабіць бінарны пошук. 1582 01:18:34,590 --> 01:18:36,991 Так ці не ўсё роўна, калі ён не працуе? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Пэн: Кароткі адказ: не. 1585 01:18:41,510 --> 01:18:42,642 Але так як мы не-- 1586 01:18:42,642 --> 01:18:44,350 АЎДЫТОРЫЯ: Але ніхто не на самай справе праверкі. 1587 01:18:44,350 --> 01:18:46,058 ANDI Пэн: Мы ніколі не ўбачыце, што. 1588 01:18:46,058 --> 01:18:49,590 Але вы, верагодна, хочаце, каб што ваш пошук працы. 1589 01:18:49,590 --> 01:18:51,700 Таму што, калі ваш лінейны пошук не працуе, 1590 01:18:51,700 --> 01:18:54,410 то хутчэй за ўсё, ваш бінарны Пошук не будзе працаваць, як добра. 1591 01:18:54,410 --> 01:18:56,646 Таму што ў вас ёсць падобнае Логіка ў іх абодвух. 1592 01:18:56,646 --> 01:18:58,020 І няма, гэта не мае значэння. 1593 01:18:58,020 --> 01:19:01,300 Такім чынам, адзінымі вы ўключыце у з'яўляюцца свайго роду і бінарны пошук. 1594 01:19:01,300 --> 01:19:02,490 Так. 1595 01:19:02,490 --> 01:19:06,610 >> А таксама, шмат дзяцей былі спрабуючы сабраць helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Вы на самой справе не дапускаюцца каб зрабіць гэта, таму што helpers.c 1597 01:19:09,550 --> 01:19:11,200 не мае асноўную функцыю. 1598 01:19:11,200 --> 01:19:13,550 І таму вы павінны толькі быць на самай справе кампіляцыі 1599 01:19:13,550 --> 01:19:18,670 генераваць і знайсці, таму што знайсці званкі helpers.c і функцыі ў ёй. 1600 01:19:18,670 --> 01:19:20,790 Так што робіць адладку боль у задніцы. 1601 01:19:20,790 --> 01:19:22,422 Але гэта тое, што мы павінны рабіць. 1602 01:19:22,422 --> 01:19:23,880 АЎДЫТОРЫЯ: Вы проста зрабіць усё, праўда? 1603 01:19:23,880 --> 01:19:27,290 ANDI Пэн: вы можаце проста зрабіць усё як добра, так. 1604 01:19:27,290 --> 01:19:28,060 ДОБРА. 1605 01:19:28,060 --> 01:19:32,570 Дык вось яно што ў плане таго, што PSET просіць, каб вы ўсё робіце. 1606 01:19:32,570 --> 01:19:35,160 Калі ў вас ёсць якія-небудзь пытанні, калі ласка, вольным спытаць мне пасля падзелу. 1607 01:19:35,160 --> 01:19:37,580 Я буду тут, як, 20 хвілін. 1608 01:19:37,580 --> 01:19:40,500 >> І так, Pset-х сапраўды не так ужо дрэнна. 1609 01:19:40,500 --> 01:19:41,680 Вы, хлопцы, павінна быць у парадку. 1610 01:19:41,680 --> 01:19:43,250 Яны, проста прытрымлівайцеся рэкамендацый. 1611 01:19:43,250 --> 01:19:47,840 Выгляд ёсць пачуццё, па логіцы, тое, што павінна адбывацца, і вы будзеце ў парадку. 1612 01:19:47,840 --> 01:19:48,690 Ці не занадта страшна. 1613 01:19:48,690 --> 01:19:50,220 Там вельмі шмат кода ўжо напісана. 1614 01:19:50,220 --> 01:19:53,011 Ці не занадта страшна, калі вы не зразумець, што ўсё гэта значыць. 1615 01:19:53,011 --> 01:19:54,749 Калі гэта шмат, гэта цалкам нармальна. 1616 01:19:54,749 --> 01:19:55,790 І прыйшлі да офіснай гадзін. 1617 01:19:55,790 --> 01:19:57,520 Мы дапаможам вам зірнуць. 1618 01:19:57,520 --> 01:20:00,810 >> АЎДЫТОРЫЯ: з дадатковымі Функцыі, мы глядзім тыя да? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Пэн: Так, тыя ў кодзе. 1620 01:20:03,417 --> 01:20:05,750 У гульні 15, палова з гэта ўжо напісана для вас. 1621 01:20:05,750 --> 01:20:09,310 Так што тыя функцыі ўжо ў кодзе. 1622 01:20:09,310 --> 01:20:12,020 Так. 1623 01:20:12,020 --> 01:20:12,520 Добра. 1624 01:20:12,520 --> 01:20:14,000 Ну, ўдачы. 1625 01:20:14,000 --> 01:20:15,180 Гэта агідна дзень. 1626 01:20:15,180 --> 01:20:19,370 Так спадзяюся, вы, хлопцы, не адчуваць сябе занадта дрэнна аб знаходжанні ўнутры і кадавання. 1627 01:20:19,370 --> 01:20:22,133