[Powered by Google Translate] [Дел 3 - поудобно]
[Роб Бауден - Универзитетот Харвард]
>> [Ова е CS50. - CS50.TV]
>> Па првото прашање е чудно формулиран.
GDB ви овозможува "debug" програма, но, поточно, она што не го да ви направам?
Јас ќе ви одговорам дека еден, и јас не знам што точно се очекува,
па јас сум Сомневајќи се дека е нешто по должината на линиите на што ви овозможува да чекор по чекор
прошетка низ програмата, да разговарате со него, промена променливи, прават сите овие работи -
во основа целосно контрола на извршувањето на програмата
и врши увид секој даден дел од извршувањето на програмата.
Значи оние карактеристики ви овозможи да debug работи.
Во ред.
Зошто бинарни пребарување бараат низа да бидат подредени?
Кој сака да одговори на тоа?
[Студент] Поради тоа не функционира ако тоа не е сортирана. >> Да. [Смеа]
Ако тоа не е сортирани, тогаш е невозможно да го подели на половина
и знае дека сè на лево е помалку и се на правото
е поголема од средната вредност.
Па затоа треба да се решат.
Во ред.
Зошто е балон вид во О од n квадрат?
Дали некој прв сакате да им даде многу брз високо ниво преглед на она што меур вид е?
[Студент] Вие во основа поминат низ секој елемент и да се провери првите неколку елементи.
Ако тие се надвор од местото каде што можете да ги трампа, тогаш проверете на следните неколку елементи и така натаму.
Кога ќе стигне до крајот, тогаш знаете дека најголемиот елемент се наоѓа на крајот,
така да се игнорира дека еден тогаш продолжи да оди преку,
и секој пат кога ќе треба да се провери еден помалку елемент додека не направи никакви промени. >> Да.
Таа се вика меур вид, бидејќи ако флип низа на негова страна, па тоа е нагоре и надолу, вертикална,
тогаш големи вредности ќе потоне на дното и мали вредности ќе меур до врвот.
Тоа е како тоа го добило името.
И да, само одат преку.
Можете Продолжувам да одам преку низа, Замена на поголема вредност
за да се добие најголем вредности на дното.
>> Зошто е О од n квадрат?
Прво, дали некој сака да каже зошто тоа е О од n квадрат?
[Студент] Бидејќи за секој работи оди n пати.
Можете само да бидете сигурни дека сте ги направиле најголемите елемент на целиот пат,
тогаш мора да повторам дека за толку многу елементи. >> Да.
Значи имајте на ум она што големите О значи и она што големите Омега средства.
Големите О е како горна граница за тоа како бавно тоа всушност може да работи.
Значи, велејќи дека е О од n квадрат, тоа не е O на n или на друго место ќе биде во можност да се кандидира
во линеарна време, но тоа е О од n коцки
бидејќи тоа се граничи со О на n коцки.
Ако тоа е граничи со О на n квадрат, тогаш тоа е граничи и со n коцки.
Па тоа е N квадрат, а во апсолутна најлош случај таа не може да го направи подобро од n квадрат,
кој е зошто тоа е О на N квадрат.
Значи да се види мала математика како тоа излегува да биде n квадрат,
ако имаме пет нешта во нашата листа, прв пат колку свопови може да се потенцијално треба да се направи
со цел да се добие оваа? Да, всушност, само -
Колку свопови сме ние ќе треба да се направи во првиот рок на меурот вид преку низа?
[Студент] n - 1. >> Да.
>> Ако има 5 елементи, ние ќе треба да се направи n - 1.
Потоа на втората колку свопови сме ние ќе треба да се направи?
[Студент] n - 2. >> Да.
А третиот ќе биде n - 3, а потоа за погодност јас ќе напишам во последните две
како тогаш ние ќе треба да се направи 2 свопови и 1 swap.
Претпоставувам дека последната може или не, всушност може да треба да се случи.
Тоа е трампа? Не знам.
Значи овие се вкупните износи на свопови или барем споредби треба да се направи.
Дури и ако не трампа, се уште треба да се споредуваат вредностите.
Значи постојат n - 1 споредби во првиот рок преку низа.
Ако ги преуредите овие работи, да всушност го направи шест работи па работите магацинот убаво,
а потоа јас ќе сторам 3, 2, 1.
Па само преуредување овие суми, ние сакаме да видиме колку споредби правиме
во целиот алгоритам.
Значи, ако ние ги овие момци овде долу,
тогаш ние сме сè уште само собирање сепак многу споредби имало.
Но, ако ги сумира овие и ние сумира овие и ние сумира овие,
тоа е уште истиот проблем. Ние само сумира оние одредени групи.
>> Па сега ние сме собирање 3 на n. Тоа не е само 3 на n.
Тоа секогаш ќе биде n / 2 на n.
Па овде се случи да имаат 6.
Ако имавме 10 работи, тогаш можеме да го направите ова групирање за 5 различни пара работи
и завршуваат со N + N + N + N + N.
Па ти си секогаш ќе добиете n / 2 л, и така ова ние ќе го трошка до n квадрат / 2.
И така, иако тоа е фактор на половина, што се случува да дојде во
поради фактот дека низ секоја итерација во текот на низа ја споредиме 1 помалку
па тоа е како ние се добие повеќе од 2, но тоа се уште n квадрат.
Ние не се грижат за постојан фактор на половина.
Значи многу големи О работи како оваа се потпира на само вид на прави овој вид на математика,
прави аритметички суми и геометриски серии работи,
но повеќето од нив во овој курс се прилично јасна.
Во ред.
Зошто е вметнување вид со омега на n? Што значи омега значи?
[Двајца ученици зборува одеднаш - неразбирливо] >> Да.
Омега можете да замислите како долниот врзани.
>> Значи без оглед на тоа колку ефикасна вашата вметнување вид алгоритам е,
без оглед на листата што е донесен во, таа секогаш има да се споредат најмалку n работи
или таа има да iterate во текот n работи.
Зошто е тоа така?
[Студент] Затоа што ако листата е веќе сортирани, тогаш во текот на првата итерација
вие само може да гарантира дека првиот елемент е и најмалку важно,
и втората итерација вие само може да гарантира првите две се
затоа што не знаат дека остатокот од листата се подредени. >> Да.
Ако помине во сосема подредени листата, во најмала рака треба да се оди во текот на сите елементи
да се види дека ништо не треба да се пресели наоколу.
Па поминува преку листата и велејќи ох, ова е веќе сортирани,
тоа е невозможно за вас да знаете дека е сортирана додека не се провери секој елемент
да се види дека тие се во подредени цел.
Па на долниот граница на вметнување вид е омега на n.
Што е најлошото трчање време на спојување вид,
Најлошото е голема О повторно?
Па во најлош случај сценарио, како се спојат вид работи?
[Студент] N најавите n. >> Да.
Најбрз општо сортирање алгоритми се n најавите n. Вие не може да се направи подобро.
>> Постојат посебни случаи, и ако имаме време денес - но ние веројатно won't -
можеме да видиме оној кој го прави подобро од n најавите n.
Но во општата случај, не можете да го направите подобро од n најавите n.
И се спојат вид се случува да биде оној што треба да знаете за овој курс кој е n најавите n.
И така ние всушност ќе се спроведува тоа денес.
И, конечно, не повеќе од три реченици, како го прави селекција вид работа?
Дали некој сака да одговори, а јас ќе брои вашите реченици
затоа што ако поминат 3 -
Не се сеќавам некој избор вид?
Избор вид обично е прилично лесно да се сетам само од името.
Вие само iterate во текот на низа, најдете она што најголемата вредност е или најмалиот -
кој редослед ќе бидете сортирање внатре
Па да речеме ние сме сортирање од најмалите до најголемите.
Можете iterate во текот на низа, во потрага по она што минималната елемент е,
одберете ја, и потоа само да го трампа што е на прво место.
А потоа на вториот помине во текот на низа, погледнете за минимум елемент, повторно,
одберете ја, а потоа се разменуваат со она што е во втората позиција.
Значи ние сме само подигање и изборот на минималните вредности
и вметнување на нив во предниот дел на низа се додека не се подредени.
Прашања за тоа?
>> Овие неизбежно се појавуваат во форми што треба да пополните кога сте поднесување на pset.
Тоа се во основа на одговорите на овие.
Океј, па сега кодирање проблеми.
Јас веќе испратена преку е-мејл - никој ништо не добие овој е-мејл? Во ред.
Јас веќе испратена преку е-мејл просторот што ние ќе биде со користење,
и ако кликнете на моето име - па мислам дека ќе одам да биде на дното
поради наназад r - но ако кликнете на моето име ќе видите 2 ревизии.
Ревизија 1 ќе биде веќе копирани и атипичен кодот во простори
за пребарување нешто што ќе мора да ги спроведе.
И ревизија 2 ќе биде вид работа што ги спроведуваме после тоа.
Значи можете да кликнете на мојот верзии 1 и работи од таму.
И сега ние сакаме да се имплементира бинарни пребарување.
>> Сака ли некој да му го даде на pseudocode високо ниво објаснување
на она што ние ќе треба да направите за пребарување? Да.
[Студент] Вие само ги преземе средината на полето и види дали она што го барате
е помала од онаа или повеќе од тоа.
И, ако е помала, ќе се обратите на половина од тоа е помалку,
и ако тоа е повеќе, одете на половина од тоа е повеќе и ќе повторам дека додека вие само се една работа.
[Бауден] Да.
Забележиш дека нашите броеви низа е веќе сортирани,
и така тоа значи дека ние може да ги искористат предностите на тоа и ние прво да се провери,
Океј, јас сум во потрага по бројот 50.
За да можам да одам во средината.
Средината е тешко да се дефинира кога е парен број на нештата,
но ајде да речеме ние секогаш ќе скрати на средината.
Значи тука имаме 8 нешта, па на средината ќе биде 16.
Јас сум во потрага за 50, па 50 е поголем од 16.
Па сега јас во основа може да се третираат мојот низа како овие елементи.
Можам да фрлаат се што во текот од 16.
Сега, мојот низа е само овие 4 елементи, и јас повторувам.
Па тогаш сакам да се најде во средината, повторно, кој ќе биде 42.
42 е помалку од 50, па можам да фрлаат овие два елементи.
Ова е мојот останатите низа.
Одам да се најде среде повторно.
Претпоставувам дека 50 е лош пример, бидејќи јас секогаш беше фрлање работите на лево,
но со иста мерка, ако јас сум во потрага по нешто
и тоа е помалку од елементот Јас сум во моментов во потрага на,
тогаш јас ќе одам да фрлаат се што десно.
Па сега ние треба да се спроведе тоа.
Забележете дека ние треба да го поминат во големина.
Ние не може, исто така, треба да се хард-кодот големина.
Значи, ако ние се ослободи од таа # define -
Во ред.
Како можам убаво да дознаам што големината на броеви низа во моментов е?
>> Колку елементи се броеви низа?
[Студент] Броеви, загради,. Должина?
[Бауден] Тоа не постои во C.
Треба. Должина.
Низи немаат својства, така што не постои должина сопственост на низи
тоа само ќе ви даде сепак долго тоа се случува да биде.
[Студент] Види колку меморија има и подели со колку - >> Да.
Па како можеме да видиме колку меморија има тоа? >> [Студент] sizeof. >> Да, sizeof.
Sizeof е оператор кој нема да се вратат на големината на броеви низа.
И тоа ќе биде сепак многу броеви постојат моменти големината на целобројни
бидејќи тоа е колку меморија е всушност преземањето.
Значи, ако сакам бројот на нештата во низа,
тогаш јас ќе одам да сакате да го подели со големината на цел број.
Во ред. Така што ми овозможува да помине во големина тука.
Зошто треба да го поминат во големина на сите?
Зошто не можам само не се тука int големина = sizeof (стогот) / sizeof (int)?
Зошто ова не функционира?
[Студент] Тоа не е глобалната променлива.
[Бауден] haystack постои и ние поминува во бројки како сено,
и ова е вид на предзнак за она што е да дојде. Да.
[Студент] haystack е само повикување на него, па затоа ќе се врати колку е голема дека референцата е.
Да.
Се сомневам во предавање дека сте виделе на магацинот уште навистина, нели?
Ние само се зборува за тоа.
Така магацинот е местото каде што сите ваши променливи се случува да бидат складирани.
>> Секое меморија, која е наменета за локалните променливи се случува во магацинот,
и секоја функција добива свој простор на магацинот, свој магацинот рамка е она што се вика.
Значи главната има магацинот рамка, и во него се случува да постои оваа броеви низа,
и тоа ќе биде со големина sizeof (броеви).
Тоа се случува да имаат големина на броеви поделено со големина на елементи,
но дека сите животи во магацинот рамка главниот е.
Кога ние го нарекуваме пребарување, барај добива свој магацинот рамка,
свој простор за складирање на сите свои локални променливи.
Но, овие аргументи - па стогот не е копија на целиот спектар.
Ние не го положи во целата низа како копија во пребарувањето.
Тоа само поминува упатување кон таа низа.
Значи за пребарување може да пристапите до овие броеви преку оваа референца.
Тоа е уште пристапува на работите кои живеат во внатрешноста на оџакот рамка главната е,
но во основа, кога ќе дојде до покажувачи, која треба да биде наскоро,
тоа е она што покажувачи се.
Совети се само препораки за нештата, и можете да го користите совети како да пристапите работи
кои се во магацинот рамки други работи.
Па дури и броеви е локално до главна, ние се уште може да ја пристапите преку овој покажувач.
Но, бидејќи тоа е само покажувач и тоа е само појдовна референца,
sizeof (стогот) само се враќа на големина на референтните себе.
Тоа не го врати големината на нешто што е посочувајќи да.
Тоа не се вратат на вистинската големина на броеви.
И така ова не е оди на работа како што сакаме да.
>> Прашања за тоа?
Покажувачи ќе се качил во со значително повеќе крвави детали во недели да дојде.
И ова е причината зошто многу нешта што те гледам, повеќето интернет работи или вид работи,
тие се речиси сите ќе треба да ги преземе вистинските големина на низата,
бидејќи во C, немаме идеја што големината на низата е.
Ќе треба рачно да го помине внатре
А ти да не рачно да помине во целата низа, бидејќи сте само поминува во референтната
и не може да се добие со големина од референца.
Во ред.
Па сега ние сакаме да се спроведе она што беше објаснето.
Можете да работите на неа за една минута,
а вие не мора да се грижите за добивање на сето совршено 100% работи.
Само напишете ја сочинуваат половина pseudocode за тоа како мислите дека треба да работат.
Во ред.
Нема потреба да бидат целосно направено со ова сеуште.
Но, дали некој се чувствуваат удобно со она што тие имаат досега,
како нешто можеме да работиме со заедно?
Сака ли некој да волонтираат? Или јас случајно ќе го избере.
Тоа не мора да биде во право за секоја мерка, но нешто што може да го менува во работна состојба.
[Студент] Секако. >> Океј.
Така можете да заштедите на ревизија со кликнување на малата Зачувај икона.
Ти си Ramya, нели? >> [Студент] Да. >> [Бауден] Во ред.
Па сега јас да ја видите вашата ревизија и секој може да се повлече до ревизија.
И тука имаме - Добро.
Значи Ramya отиде со рекурзивен решение, што е дефинитивно добро решение.
Постојат два начини можете да го направите овој проблем.
Можете или да го направите iteratively или рекурзивно.
Повеќето проблеми ќе се судрите со кои може да се направи рекурзивно, исто така, може да се направи iteratively.
Па еве ние сме го направиле рекурзивно.
>> Дали некој сака да дефинира што значи да се направи функција рекурзивен?
[Студент] Кога ќе имаат функција се нарекува
а потоа се нарекува додека таа излегува со точни и вистинити. >> Да.
Рекурзивен функција е само функција која се нарекува себеси.
Постојат три големи нешта кои рекурзивен функција мора да има.
Првиот е очигледно, тоа се нарекува себеси.
Вториот е на база случај.
Па во одреден момент функцијата треба да престанат да повикуваат себе,
и тоа е она што на база случај е за.
Значи тука знаеме дека ние треба да престане, ние треба да се откажат во нашата пребарување
кога почеток еднаква на крајот - и ќе одиме над она што тоа значи.
Но, конечно, последната работа која е важна за рекурзивен функции:
функциите некако мора да се пријде на база случај.
Како и ако вие не сте всушност ажурирање ништо кога ќе се направи вториот рекурзивен повик,
ако сте буквално само повикување на функцијата повторно со истите аргументи
и без глобални променливи се промениле или ништо,
никогаш нема да стигне до база случај, во кој случај тоа е лошо.
Тоа ќе биде бесконечна рекурзија и магацинот претекување.
Но, тука можеме да видиме дека ажурирање се случува бидејќи ние сме ажурирање започне + крај / 2,
ние сме ажурирање на крајот аргумент тука, ние сме ажурирање на почетокот аргумент тука.
Значи во сите рекурзивните повици ние сме ажурирање нешто. Во ред.
Дали сакате да ни прошетка низ вашето решение? >> Секако.
Јас сум со користење SearchHelp, така што секој пат кога ќе се направи овој повик на функција
Имам почеток на тоа каде јас сум во потрага по во низа и на крајот
на тоа каде јас сум во потрага на низата.
>> На секој чекор каде што тоа е велејќи дека тоа е средината елемент, кој е почеток + крај / 2,
е дека еднаков на она што го барате?
И ако е така, тогаш ние го најде, и претпоставувам дека ќе поминуваат до нивото на рекурзија.
И ако тоа не е точно, тогаш провери дали средна вредност на низата е премногу голема,
во кој случај ние се погледне на левата половина од низата со одење од почеток до средината индекс.
А инаку тоа го правиме на крајот половина.
[Бауден] Во ред.
Тоа звучи добро.
Океј, па неколку работи, а всушност, ова е многу високо ниво работа
дека никогаш нема да треба да знаете за овој курс, но тоа е вистина.
Рекурзивен функции, секогаш слушам дека тие се лош договор
бидејќи ако рекурзивно себе се нарекуваш многу пати, ќе го добиете оџакот преливник
бидејќи, како што реков претходно, секоја функција добива свој магацинот рамка.
Значи секој повик на рекурзивен функција добива свој магацинот рамка.
Значи, ако направиме 1000 рекурзивните повици, ќе добиете 1000 магацинот рамки,
и брзо ќе доведе до кои имаат премногу магацинот рамки и работи едноставно се скрши.
Па затоа рекурзивен функции се генерално лоши.
Но, постои еден убав подмножество на рекурзивен функции наречен опашката рекурзивен функции,
и ова се случува да биде пример на една каде што ако на компајлерот забележува ова
и што треба, мислам дека - во ѕвекот ако помине тоа, О2 знаме
тогаш ќе забележите ова е опашка рекурзивен и да работи добро.
>> Тоа ќе повторна употреба на истиот магацинот рамка одново и одново за секој рекурзивен повик.
И така, бидејќи сте со користење на истите магацинот рамка, вие не треба да се грижите за
некогаш магацинот преплавени, а во исто време, како што рече пред,
каде што некогаш ќе се вратите точно, тогаш тоа треба да се вратат до сите овие магацинот рамки
и 10 повик за SearchHelp има да се вратат на 9-ти, има да се врати во 8.
Така што не треба да се случи кога функции се опашка рекурзивен.
И така она што ја прави оваа функција опашка рекурзивен е известување дека за секој даден повик за searchHelp
рекурзивен повик дека тоа е правење е она што е враќање.
Значи, во првиот повик да SearchHelp, ние или веднаш да се врати лажни,
веднаш да се врати точно, или ние правиме рекурзивен повик да се SearchHelp
каде што ние сме враќање е она што тој повик се враќа.
И не можевме да го направите ова, ако ние го сторивме нешто како int x = SearchHelp, враќање X * 2,
само некои случајни промени.
>> Па сега овој рекурзивен повик, ова int x = SearchHelp рекурзивен повик,
не е веќе опашка рекурзивен бидејќи тоа всушност мора да се вратат
назад кон претходниот магацинот рамка, така што таа претходниот повик на функција
тогаш може да се направи нешто со враќањето вредност.
Значи ова не е опашка рекурзивен, но она што го имавме пред е убаво опашка рекурзивен. Да.
[Студент] не втората база случај треба да се провери прво
бидејќи може да има ситуација каде што кога ќе го положат аргумент
ќе се започне = крај, но тие се на игла вредност.
Прашањето беше да не можеме да се кандидира во случај кога на крајот не е игла вредност
или започнете = крај, соодветно, почнете = крај
и не сте всушност проверени дека одредена вредност, сепак,
потоа започнете + крај / 2 е само ќе биде иста вредност.
Но, ние веќе се врати лажни и ние всушност никогаш не проверив вредност.
Значи, во најмала рака, во првиот повик, ако големината е 0, тогаш ние сакаме да се врати лажни.
Но, ако големината е 1, тогаш почетокот нема да се еднакви крајот,
и ние барем ќе провери еден елемент.
Но, мислам дека вие сте во право во тоа што може да завршат во случај кога започне + крај / 2,
почеток завршува се исти како почеток + крај / 2,
но никогаш не сме всушност проверени тој елемент.
>> Значи, ако ние прво се провери е средината елемент на вредноста што го барате,
тогаш може веднаш да се врати вистина.
Друго, ако тие се еднакви, тогаш нема точка за продолжување на
бидејќи ние сме само ќе да се ажурира на случај каде што сме на еден елемент низа.
Ако тоа еден елемент не е оној што го барате,
тогаш сè е во ред. Да.
[Студент] Работата е дека од големината е всушност поголем од бројот на елементи во низа,
веќе има офсет - >> Така ќе големината -
[Студент] Велат дека ако низата е големина 0, тогаш SearchHelp, всушност, ќе се провери стогот од 0
на првиот повик.
Низата има големина 0, па 0 е - >> Да.
Има уште нешто што - тоа би можело да биде добро. Ајде да мислам.
Значи, ако низата имаше 10 елементи и средната ние ќе да се провери е индекс 5,
па ние сме проверка 5, и да речеме дека вредноста е помала.
Па ние сме фрлање се далеку од 5 до денес.
Така на проектот + крај / 2 ќе биде нашиот нов крајот,
Така да, тоа е секогаш ќе остане надвор од крајот на низата.
Ако тоа е случај, ако тоа беше дури и или непарни, тогаш ние ќе провери, да речеме, 4,
но ние сме уште фрлањето -
Така да, крајот е секогаш ќе биде надвор од реалните крајот на низата.
Па елементи ние се фокусираме на, на крајот е секогаш ќе биде оној после тоа.
И така, ако проектот не секогаш еднаков крајот, ние сме во низа на големината 0.
>> Од друга работа јас мислев е ние сме ажурирање на почеток да се започне + крај / 2,
па ова е случај дека јас сум имаат проблеми со, каде започне + крај / 2
е елемент сме проверка.
Да речеме дека имавме оваа 10-елемент низа. Сеедно.
Така на проектот + крај / 2 ќе биде нешто како овој,
и ако тоа не е вредност, велат сакаме да се ажурира.
Вредноста е поголема, затоа сакаме да се погледне во оваа половина на низата.
Па како ние сме ажурирање почеток, ние сме ажурирање почеток до сега да биде овој елемент.
Но, ова сè уште може да работи, или во најмала рака, можете да направите почеток + крај / 2 + 1.
[Студент] Вие не треба да се започне + крај [недоловим] >> Да.
Ние веќе ја приметивте овој елемент и знаат дека тоа не е она што го барате.
Значи ние не треба да се ажурира на проектот да бидат на овој елемент.
Ние само може да го прескокнете и надградба на проектот да бидат на овој елемент.
А, постои ли некогаш случај, да речеме, дека ова беше крајот,
па потоа започнете би било ова, почнете + крај / 2 ќе биде тоа,
започне + крајот - Да, мислам дека може да заврши во бесконечна рекурзија.
Да речеме дека тоа е само низа од големината 2 или низа на големина 1. Мислам дека ова ќе функционира.
Па во моментов, проектот е тој елемент и крајот е 1 подалеку од него.
Па елемент кој ние ќе се провери е овој,
и тогаш кога ние ажурирање почеток, ние сме ажурирање на почеток да биде 0 + 1/2,
која ќе ни стави крај назад со почеток биде овој елемент.
>> Па ние сме проверка на истиот елемент одново и одново.
Значи ова е случај каде што секој рекурзивен повик, всушност, мора да се ажурираат нешто.
Значи ние треба да направите почеток + крај / 2 + 1, или на друго место не е случај
каде што ние не сме всушност ажурирање почеток.
Секој види тоа?
Во ред.
Дали некој има прашања за тоа решение или повеќе коментари?
Во ред. Дали некој има итеративен решение кое сите ние може да се погледне?
Дали сите ние го направи тоа рекурзивно?
Или, исто така претпоставувам дека ако нејзините се отвори, тогаш можеби ќе мора прескокнат вашиот претходниот.
Дали тоа автоматски спаси? Јас не сум позитивен.
Дали некој има итеративен?
Можеме да одиме низ него заедно, ако не.
Идејата се случува да бидат исти.
Итеративен решение.
Ние ќе сакате да се основа го стори истото идеја
каде што сакате да ги пратите на нови крајот на низата и нов почеток на низата
и го правам тоа одново и одново.
И ако она што ние следење на како на почетокот и на крајот секогаш се сечат,
тогаш ние не го најдете, а ние може да се врати лажни.
Па, како да го направам тоа? Некој има сугестии или код за мене да се повлече до?
[Студент] Дали време јамка. >> Да.
Ви се случува да сакаат да се направи јамка.
>> Дали имате кодот би можел да се повлече, или она што се ви се случува да навестиле?
[Студент] Јас мислам така. >> Ред. Ова го прави работите полесно. Што е вашето име?
[Студент] Лукас.
Ревизија 1. Во ред.
Ниско е она што се нарекува започне порано.
До не е она што се нарекува крајот порано.
Всушност, на крајот е сега во низа. Тоа е елемент што треба да се разгледа.
Толку ниско е 0, до е големината на низата - 1,
а ние сега се looping, и ние сме проверка -
Претпоставувам дека може да оди преку неа.
Што е вашето размислување преку ова? Прошетка нас преку вашиот код.
[Студент] Секако. Погледни го стогот вредност во средината и го Спореди со игла.
Па ако е поголема од вашата игла, тогаш ќе сакате да - ох, всушност, тоа треба да биде наназад.
Сте ќе сакате да го фрлаат на десната половина, и така да, тоа треба да биде на патот.
[Бауден] Значи ова треба да биде помал? Е дека она што го рече? >> [Студент] Да.
[Бауден] Во ред. Помалку.
Значи, ако она што го барате е помал од она што го сакаме,
тогаш да, ние сакаме да фрлаат левата половина,
што значи ние сме ажурирање сè што си размислува
со поместување ниско на правото на низата.
Ова изгледа добро.
Мислам дека тоа го има истиот проблем што рековме на претходната,
каде што ако ниска е 0 и до е 1, тогаш ниски + Стрелка горе / 2 ќе се постави да биде иста работа повторно.
>> И дури и ако тоа не е случај, тоа е уште поефикасен во најмала рака
само фрлаат на елементот ние само погледна кои знаеме е во ред.
Толку ниско + Стрелка горе / 2 + 1 - >> [студент] Тоа треба да биде на друг начин.
[Бауден] Или ова треба да биде - 1, а другиот треба да биде + 1.
[Студент] и таму треба да биде двојно изнесува знак. >> [Бауден] Да.
[Студент] Да.
Во ред.
И, конечно, дека сега имаме оваа + 1-1 работа,
е тоа - тоа не може да биде - тоа е што е можно за ниско да се заокружи со вредност поголема од се?
Мислам дека единствениот начин на кој може да се случи - Дали е можно? >> [Студент] Не знам.
Но, ако станува скратена, а потоа добива минус дека 1 и потоа - >> Да.
[Студент] Тоа веројатно ќе се збркана.
Мислам дека тоа треба да биде добро само затоа што
за тоа да се заокружи пониски тие ќе треба да бидат еднакви, мислам.
Но, ако тие се еднакви, тогаш ние не би го сторил додека јамка за да започнете со
и ние само ќе се врати на вредност. Па јас мислам дека ние сме добро сега.
Забележете дека иако овој проблем не е рекурзивен,
ист вид на идеи применува кога можеме да видиме како тоа толку лесно помага на самата
на рекурзивен решение од фактот дека ние сме само ажурирање на индекси одново и одново,
правиме проблемот помали и помали, ние се фокусираме на подмножество на низата.
[Студент] Ако ниска е 0 и до е 1, тие ќе бидат 0 + 1/2, кој ќе оди на 0,
а потоа еден ќе биде + 1, еден ќе биде - 1.
[Студент] Каде проверка еднаквост?
Како ако средината е всушност игла?
Ние не сме во моментов прави тоа? Ох!
Ако it's -
Да. Ние не може само да се направи тестот долу тука, бидејќи да речеме првиот средината -
[Студент] Тоа е всушност како да не фрлаат врзани.
Значи, ако фрлаат врзани, мора да го провери прво или whatever.
Ах. Да. >> [Студент] Да.
Така, сега имаме фрлени онаа што во моментов ја погледна,
што значи ние сега треба да имаат
ако (стогот [(низок + до) / 2] == игла), тогаш можеме да се вратат вистина.
И дали го ставам друг или само ако, тоа значи буквално истото
бидејќи тоа би се вратиле точно.
Затоа јас ќе се стави друго, ако, но тоа не е важно.
>> Па друго, ако ова, друг ова, и ова е заеднички нешто што правам
каде што дури и ако тоа е случај каде што сè е добро овде,
како ниски никогаш не може да биде поголема од горе, не вреди размислување околу тоа дали тоа е вистина.
Па може и да се каже додека ниските е помала или еднаква на
или додека ниските е помал од
Значи, ако тие се секогаш еднакви или ниско се случува да помине нагоре,
тогаш можеме да се пробие на овој циклус.
Прашања, грижи коментари?
Во ред. Ова изгледа добро.
Сега сакаме да го стори вид.
Ако одиме во мојата втора ревизија, гледаме истите броеви,
но сега тие веќе не се во подредени цел.
И ние сакаме да се спроведе вид користење на било кој алгоритам во О од n најавите n.
Значи кој алгоритам мислите дека треба да се спроведе тука? >> [Студент] Merge вид.
[Бауден] Да. Се спојат вид е О (n најавите л), па тоа е она што ние ќе треба да се направи.
И проблемот ќе биде прилично слични,
каде што лесно помага на самата да рекурзивен решение.
Ние, исто така може да излезе со итеративен решение ако сакаме,
но рекурзија ќе биде полесно тука и ние треба да направите рекурзија.
Претпоставувам ние ќе одиме преку спојување вид првиот,
иако постои една прекрасна видео на спојување вид веќе. [Смеа]
Значи се логирате вид постојат - Јас сум трошат толку многу на овој труд.
Ох, има само една лево.
Значи се логирате.
О, 1, 3, 5.
Во ред.
Спои се две одделни низи.
Поединечно овие две низи се двете подредени.
Значи оваа низа, 1, 3, 5, подредени. Оваа низа, 0, 2, 4, подредени.
Сега што се спојуваат треба да направите е да ги комбинирате во една низа која и самата е подредени.
Затоа сакаме низа на големина 6 што се случува да имаат овие елементи во него
во подредени цел.
>> И така ние може да ги искористат предностите на фактот дека овие две низи се подредени
да го направите ова во линеарна време,
линеарен пат значење ако оваа низа е големината x и ова е големината y,
тогаш вкупната алгоритам треба да бидат О (x + y). Во ред.
Значи предлози.
[Студент] би можеле да започнеме од лево?
Па ќе стави 0 надолу, а потоа на 1 и потоа тука си во 2.
Значи тоа е вид на како да имаш таб кој се движи на десно. >> [Бауден] Да.
За двете од овие низи ако ние само се фокусираат на најлева елемент.
Бидејќи и двете низи се подредени, ние знаеме дека овие 2 елементи
се најмалите елементи или во низа.
Тоа значи дека 1 од тие 2 елементи мора да бидат најмалиот елемент во нашиот спои низа.
Тоа само така се случува, дека најмалата е на десната страна на овој период.
Па ние се 0, внесете ја на левата бидејќи 0 е помала од 1,
па се 0, внесете ја во нашите првата позиција, а потоа ние ја ажурирате оваа
до сега се фокусира на првиот елемент.
И сега ние се повторува.
Па сега ние споредите 2 и 1. 1 е помала, па ние ќе вметнете 1.
Ние ажурирање на оваа покажувачот да укаже на овој човек.
Сега можеме да го направи тоа повторно, па 2. Ова ќе се ажурира, да ги споредиме овие 2, 3.
Ова надградби, тогаш 4 и 5.
Па тоа е логирате.
>> Тоа треба да биде прилично очигледно дека тоа е линеарна време, бидејќи ние само одиме низ секој елемент еднаш.
И тоа е најголемиот чекор кон спроведување логирате вид е тоа.
И тоа не е толку тешко.
Неколку работи кои треба да се грижите за е Да речеме дека ние се спојуваат 1, 2, 3, 4, 5, 6.
Во овој случај ние ќе завршат во сценарио каде ова се случува да бидат помали,
тогаш ние ја ажурирате оваа покажувач, ова ќе биде помал, ажурирање тоа,
ова ми е помал, а сега ќе мора да се признае
кога сте всушност снема елементи да се споредуваат со.
Бидејќи ние веќе се користи целата оваа низа,
се што е во оваа низа е сега само вметната во тука.
Значи, ако некогаш работат во точката каде што еден од нашите низи е целосно споени веќе,
тогаш ние само ги преземе сите елементи на други низа и вметнете ги во крајот на низата.
Па ние само може да се вметне 4, 5, 6. Во ред.
Тоа е една работа да внимаваш за.
Спроведување кои треба да бидат чекор 1.
Логирате сортирање потоа врз основа на тоа, тоа е 2 чекори, 2 смешни чекори.
Ајде само им даде на оваа низа.
Значи се логирате вид, чекор 1 е за рекурзивно да се скрши низа во половини.
Значи подели оваа низа во половини.
Сега имаме 4, 15, 16, 50 и 8, 23, 42, 108.
И сега ние го направи тоа повторно и ние поделени овие во половини.
Јас само ќе го направи на оваа страна.
Значи 4, 15 и 16, 50.
Ние ќе го стори истото одново тука.
И сега ние го подели на половина повторно.
И ние имаме 4, 15, 16, 50.
Па тоа е нашата база случај.
Откако низи се со големина од 1, тогаш ние престануваме со разделување во половини.
>> Сега што ќе правиме со ова?
На крајот ќе заврши ова исто така ќе се прекине во 8, 23, 42, и 108.
Па сега дека ние сме во овој момент, сега се чекор два на спојување вид е само спојување парови на листи.
Затоа сакаме да се спојат овие. Ние само повик се логирате.
Ние знаеме спојување ќе се вратат овие во подредени цел.
4, 15.
Сега ние сакаме да се спојат овие, и дека ќе се врати листа со оние во подредени цел,
16, 50.
Ние се спојат тие - Не можам да пишувам - 8, 23 и 42, 108.
Значи имаме спои парови еднаш.
Сега ние само се спојат повторно.
Забележете дека секоја од овие листи се подредени во себе,
а потоа ние едноставно може да се спојат овие листи за да добиете листа на големината 4 кој е сортирана
и се спојат овие две листи за да добиете листа на големина од 4 дека е сортирана.
И, конечно, можеме да се спојат овие две листи на големина од 4 да се добие една листа на големина 8, кој е сортирана.
Па да се види дека ова е целокупната n најавите n, ние веќе видовме дека спојувањето е линеарна,
па кога ние сме се занимаваат со спојување на овие, па како вкупната цена на спојување
за овие две листи е само 2 бидејќи -
Или добро, тоа е О од n, но n тука е само овие 2 елементи, така што е 2.
И овие 2 ќе биде 2 и овие 2 ќе биде 2 и овие 2 ќе биде 2,
па низ сите спои дека ние треба да се направи, на крајот ќе заврши прави n.
Како 2 + 2 + 2 + 2 е 8, кој е n,
па цената на спојување во овој сет е n.
А потоа истото тука.
Ние ќе се спојат овие 2, тогаш овие 2, и поединечно ова спојување ќе ги преземе четирите операции,
ова спојување ќе ги преземе четирите операции, но уште еднаш, меѓу сите овие,
на крајот ќе заврши спојување n вкупниот работи, и така овој чекор потребно n.
И така секое ниво потребно n елементи се спои.
>> И колку нивоа постојат?
На секое ниво, нашата низа расте со големина 2.
Тука нашите низи се со големина 1, тука тие се на големината 2, тука тие се на големината 4,
и конечно, тие се со големина од 8.
Значи, бидејќи тоа е удвојување, таму се случува да биде вкупно најавите n на овие нивоа.
Така е и со најавите n нивоа, секое индивидуално ниво преземање n вкупниот промет,
ние се добие најавите N N алгоритам.
Прашања?
Има луѓе веќе постигна напредок за тоа како да се спроведе ова?
Дали некој веќе во една држава каде што само можат да ги повлечат своите код?
Можам да дадам една минута.
Ова е ќе биде подолго.
Силно препорачувам повтори -
Вие не треба да направите рекурзија за спојување
бидејќи со рекурзија за спојување, ви се случува да мора да поминат еден куп на различни големини.
Можете да, но тоа е досадно.
Но рекурзија за вид сам по себе е прилично лесно.
Вие само буквално се јавите вид на левата половина, вид на десната половина. Во ред.
Секој има нешто што можам да се повлече до уште?
Или на друго место ќе ти дадам една минута.
Во ред.
Секој има нешто што може да работи со?
Или друг ние само ќе работат со овој и потоа се прошири од таму.
>> Секој имате повеќе од тоа што ќе можам да се повлече до?
[Студент] Да. Можете да се повлече до рудникот. >> Ред.
Да!
[Студент] Имаше многу услови. >> О, пука. Можете ли -
[Студент] морам да го спаси. >> Да.
Значи ние не го правел обединувањето одделно.
О, но тоа не е толку лошо.
Во ред.
Значи вид е сама по себе само повикување mergeSortHelp.
Објасни ни што mergeSortHelp прави.
[Студент] MergeSortHelp доста прави две главни чекори,
што е за сортирање секоја половина на низата, а потоа да се логирате двата од нив.
[Бауден] Океј, па ми даде една секунда.
Мислам дека ова - >> [студент] Јас треба да -
Да. Јас сум недостасува нешто.
Во логирате, сфаќам дека јас треба да се создаде нова низа
бидејќи не можев да го стори тоа во место. >> Да. Вие не може. Точни.
[Студент] Па јас создаде нова низа.
Го заборавив на крајот на логирате за да повторно се промени.
Во ред. Ни треба нов низа.
Во логирате вид, ова е скоро секогаш вистина.
Дел од трошоците за подобар алгоритам време мудро
е речиси секогаш има потреба да се користи малку повеќе меморија.
Па еве, не е важно како ќе го направите спојат вид,
вие неминовно ќе треба да користите некои дополнителна меморија.
Тој или таа создаде нова низа.
А потоа велиш на крајот ние само треба да го копирате нова низа во оригинална низа.
[Студент] Јас мислам така, да.
Јас не знам дали тоа работи во услови на броење со повикување или што -
Да, тоа ќе работат. >> [Студент] Во ред.
Се обидовте ли работи ова? >> [Студент] Не, сеуште не. >> Океј.
Обиди се со трчање, а потоа ќе зборуваме за тоа за една секунда.
[Студент] Јас треба да имаат сите на функција прототипи и над сè, иако, нели?
Функција прототипи. Ох, мислиш како - Да.
Сортирај повикува mergeSortHelp.
>> Значи, со цел за вид да се јавите mergeSortHelp, mergeSortHelp мора или да се дефинирани
пред вид или ние само треба прототип. Само копирајте го и ставете тоа.
И слично, mergeSortHelp е повикувајќи се спојуваат,
но спојување не е дефинирана, па ние само може да mergeSortHelp знаете
дека тоа е она што се спојуваат се случува да изгледа, и тоа е тоа.
Значи mergeSortHelp.
Имаме проблем тука, каде што ние немаме база случај.
MergeSortHelp е рекурзивен, па секој рекурзивен функција
ќе треба некој вид на база случај да знаете кога да прекинете рекурзивно се повикува.
Која е нашата база случај ќе биде тука? Да.
[Студент] Ако големината е 1? >> [Бауден] Да.
Значи како што видовме во право, таму, па престанавме да разделување низи
Откако ќе влезе во низи од 1 големина, кои неизбежно самите се подредени.
Значи, ако големина е еднаква на 1, знаеме низата е веќе сортирани,
па ние само може да се врати.
>> Забележете дека е празнина, па ние не се враќа ништо особено, ние само се вратат.
Во ред. Значи тоа е нашата база случај.
Претпоставувам нашата база случај, исто така, може да биде ако ние се случи да биде спојување низа на големина 0,
ние најверојатно сакаат да престанат во некоја точка,
па ние само може да се каже големина помала од 2 или помалку од или еднаква на 1
така што ова ќе работат за било која низа сега.
Во ред.
Значи тоа е нашата база случај.
Сега сакаш да одиме преку спојување?
Што прават сите овие случаи значи?
До тука, ние сме само го прават истото идеја, -
[Студент] Јас треба да се поминува големина со сите mergeSortHelp повици.
Јас додадов големина како дополнителен основните и тоа не е таму, како големина / 2.
[Бауден] О, големина / 2, големина / 2. >> [Студент] Да, а исто така во горната функција, како и.
[Бауден] Еве? >> [Студент] Само големина. >> [Бауден] О. Големина, големина? >> [Студент] Да.
[Бауден] Во ред.
Дозволете ми да мислам за една секунда.
Не трчаме во прашање?
Ние сме секогаш лекување на лево како 0. >> [Студент] бр
Тоа е во ред премногу. Жал ми е. Тоа треба да биде почеток. Да.
[Бауден] Во ред. Ми се допаѓа тоа подобро.
И крај. Во ред.
Па сега сакаш да одиме преку спојување? >> [Студент] Во ред.
Јас сум само одење преку оваа нова низа која сум создадена.
Нејзината големина е големината на делот од низа што ние сакаме да се решат
и се обидува да најде елементот што треба да се стави во нова низа чекор.
Па да го направат тоа, прво јас сум проверка, ако на левата половина од низата продолжува да има повеќе елементи,
и ако тоа не се случи, тогаш слезе дека друг услов, кој само вели дека
во ред, тоа мора да биде во вистинската низа, а ние ќе се стави дека во сегашниот индекс на newArray.
>> А потоа инаку, јас сум проверка, ако на десната страна на низата е завршена,
во кој случај јас само се стави во лево.
Тоа, всушност, не може да биде потребно. Јас не сум сигурен.
Но сепак, другите две проверка која од двете се помали во лево или десно.
И во секој случај, јас сум зголемување, кое случаеви јас прираст.
[Бауден] Во ред.
Што изгледа добро.
Дали некој има коментари или проблеми или прашања?
Значи четирите случаи кои треба да се донесе работите во само да биде - или тоа изгледа како пет -
но ние треба да се разгледа дали левата низа има снема на работите што треба да се логирате,
дали правото низа има снема на работите што треба да се спојат -
Јас сум укажува на ништо.
Па дали левата низа има снема на нештата или право низа има снема на нештата.
Тоа се два случаи.
Ние исто така ќе треба тривијални случај на тоа дали левицата работа е помалку од вистинската работа.
Тогаш ние сакаме да изберете од левата работа.
Тоа се случаи.
Значи ова беше во право, па тоа е тоа.
Низа лево. Тоа е 1, 2, 3. Во ред. Така да, тоа се четири работи што можеби ќе сакате да се направи.
И ние не ќе оди преку итеративен решение.
Јас не би препорачуваме -
Се спојат вид е пример на функција како што е не опашка рекурзивен,
тоа не е лесно да се направи тоа опашка рекурзивен,
но, исто така, дека не е многу лесно да се направи тоа итеративен.
Ова е многу лесно.
Оваа имплементација на спојување вид,
се спојат, без разлика што правиш, си оди за да се изгради логирате.
>> Значи се логирате вид изграден на врвот на спојување рекурзивно е само овие три линии.
Iteratively, тоа е повеќе досадни и потешко да се размислува за.
Но, забележуваат дека тоа не е опашка рекурзивен од mergeSortHelp - кога тоа се нарекува -
сеуште е потребно да се прават работите по овој рекурзивен повик се враќа.
Значи ова магацинот рамка мора да продолжи да постои дури и по повикување ова.
И тогаш кога ќе се јавите ова, магацинот рамка мора да продолжи да постои
бидејќи дури и откако тој повик, ние сеуште треба да се логирате.
И тоа е nontrivial да се направи овој опашка рекурзивен.
Прашања?
Во ред.
Па кога ќе се вратам да го решите - О, има две работи сакам да се покажуваат. Во ред.
Да се ​​вратам на вид, ние ќе го направите ова брзо.
Или пребарување. Вид? Вид. Да.
Да се ​​вратам на почетокот на вид.
Ние сакаме да се создаде алгоритам кој ги сортира низа користење на било кој алгоритам
во О од n.
Па, како е ова можно? Дали некој има било кој вид на -
Јас навести пред во -
Ако ние сме за да се подобри од N најавите n да О од n,
ние сме подобри нашите алгоритам време-мудар,
што значи она што сме ние ќе треба да направите за да се направи се за тоа?
[Студент] простор. >> Да. Ние ќе биде со користење на повеќе простор.
И дури и не само повеќе простор, тоа е експоненцијално повеќе простор.
Па мислам дека овој вид на алгоритам е псевдо нешто, псевдо polynom -
псевдо - Не можам да се сетам. Псевдо нешто.
Но, тоа е затоа што ние треба да ги користите толку многу простор
дека тоа е остварливо, но не е реална.
>> И како да се постигне тоа?
Ние може да се постигне ова, ако ние гаранција дека некој посебен елемент во низа
е под одредена големина.
Па да речеме дека големината е 200,
секој елемент во низата е под големина 200.
И ова е всушност многу реална.
Вие многу лесно може да имаат низа дека знаете се што е во него
ќе биде помалку од одреден број.
Како ако имате некои апсолутно масивни вектор или нешто
но знаете што се случува да биде помеѓу 0 и 5,
тогаш тоа ќе биде значително побрзо го направите тоа.
И врзани на било кој од елементите е 5,
па ова врзани, тоа е колку меморија ви се случува да биде во употреба.
Така врзани е 200.
Во теорија, секогаш постои врзана од цел број може да биде само до 4 милијарди долари,
но тоа е нереално, бидејќи тогаш ќе ни биде користење на просторот
од редот на 4 милијарди. Значи тоа е нереално.
Но тука ние ќе каже нашиот врзани е 200.
Трикот да го прави тоа во О на n е што направи уште низа наречен точки од обвинението за големината врзани.
Така, всушност, ова е кратенка за - Јас всушност не знам дали ѕвекот го прави ова.
Но во GCC во најмала рака - I'm претпоставувајќи ѕвекот го прави тоа премногу -
ова само ќе се иницијализира на целата низа да биде 0-ти.
Значи, ако јас не сакате да го направите тоа, тогаш јас поединечно не можеше да стори за (int i = 0;
з <врзани; i + +) и точки [i] = 0;
Па сега што е иницијализиран на 0.
Јас iterate над мојата низа,
и она што го правам е јас сум броење на бројот на секој - Ајде да одиме доле.
Имаме 4, 15, 16, 50, 8, 23, 42, 108.
Она што јас сум броење е бројот на појавувања на секоја од овие елементи.
Да, всушност, додадете неколку повеќе тука со некои повторува.
Значи вредноста имаме тука, вредноста на која ќе бидат низа [i].
Значи вредност може да биде 4 или 8 или whatever.
А сега сум броење колку од таа вредност сум видел,
па точки [вредност] + +;
По ова е направено, точки ќе изгледа нешто како 0001.
Да направиме точки [вредност] - ОБВРЗАНИ + 1.
>> Сега тоа е само за да сметка за фактот дека ние сме почнувајќи од 0.
Значи, ако 200 ќе биде нашиот најголем број,
тогаш 0-200 е 201 работи.
Значи точки, тоа ќе изгледа 00001 бидејќи имаме една 4.
Тогаш ќе имаме 0001, каде што ќе имаме 1 во 8 индекс на пребројувањето.
Ќе имаме 2 во 23 индексот брои.
Ќе имаме 2 во индекс 42 на број.
Значи можеме да го користиме брои.
Значи num_of_item = точки [i].
И така, ако num_of_item е 2, што значи ние сакаме да вметнете 2 на бројот i
во нашата подредени низа.
Значи ние треба да ги пратите на тоа колку ние сме во низа.
Значи индекс = 0.
Низа - јас само ќе го пишувам.
Точки -
низа [индекс + +] = i;
Е она што го сакам? Мислам дека тоа е она што сакам.
Да, ова изгледа добро. Во ред.
Значи не сите се разбере она што целта на мојот точки низа е?
Тоа е пребројување на бројот на појавувања на секоја од овие броеви.
Тогаш јас сум процесирањето над кој е важен низа,
и о позиција во точки низа
е бројот на i е дека треба да се појави во мојот подредени низа.
Тоа е зошто точки од обвинението за 4 ќе биде 1
и точки од 8 ќе биде 1, точки од обвинението за 23 ќе биде 2.
Значи тоа е колку од нив сакам да вметнете во мојот подредени низа.
Тогаш јас само го прават тоа.
Јас сум вметнување num_of_item јас е во моите подредени низа.
>> Прашања?
И така, повторно, ова е линеарна време, бидејќи ние сме само процесирањето над ова уште еднаш,
но тоа е, исто така, линеарна во она што овој број се случува да биде,
и така тоа во голема мера зависи од тоа што вашиот врзани е.
Со врзани на 200, тоа не е толку лош.
Ако вашиот врзани ќе биде 10.000, тогаш тоа е малку полошо,
но ако вашиот врзани ќе биде 4 милијарди долари, што е сосема нереално
и оваа низа се случува да мора да биде со големина од 4 милијарди долари, што е нереално.
Значи тоа е тоа. Прашања?
[Нечујни студент одговор] >> Океј.
Сфатив една работа кога се случува преку.
Мислам дека проблемот беше во Лукас и веројатно секој еден што сум го видел.
Јас сосема заборавивме.
Единственото нешто што сакав да коментира за е дека кога си имаш работа со нешта како индекси,
никогаш не навистина да се види ова кога сте пишување за телефонска линија,
но технички, секогаш кога си имаш работа со овие индекси,
сте доста секогаш треба да се справи со непотпишана цели броеви.
Причината за ова е кога си имаш работа со потпишан цели броеви,
па ако имаш 2 потпишан цели броеви и ќе им додадете заедно
и тие завршуваат премногу голем, тогаш ќе заврши со негативен број.
Значи тоа е она број overflow е.
>> Ако додадам 2 милијарди и 1 милијарда, јас се заокружи со негативни 1 милијарда долари.
Тоа е како цели броеви работат на компјутери.
Значи проблемот со користење на -
Тоа е во ред, освен ако е ниска се случува да биде 2 милијарди и до случува да биде 1 милијарда евра,
тогаш ова ќе биде негативен 1 милијарда, а потоа ние ќе делиме дека од 2
и завршуваат со негативни 500 милиони.
Значи ова е само прашање ако се случи да биде во потрага преку низа
милијарди нешта.
Но ако ниска + нагоре случува да преливник, тогаш тоа е проблем.
Веднаш штом ќе ги направи непотпишана, а потоа 2 милијарди плус 1 милијарда е 3 милијарди долари.
3 милијарди поделено со 2 е 1,5 милијарди евра.
Па штом тие се непотпишана, сè е совршено.
И така тоа е исто така прашање кога сте пишување вашиот за петелки,
а всушност, тоа веројатно го прави тоа автоматски.
Тоа ќе всушност само се развикам.
Значи, ако овој број е премногу голема за да биде во само еден број, но тоа ќе се вклопуваат во една непотпишана цел број,
тоа ќе се развикам, па затоа никогаш навистина работи во прашање.
Можете да видите дека индексот никогаш нема да биде негативен,
и така кога сте процесирањето преку низа,
скоро секогаш може да се каже непотпишана int i, но навистина не треба.
Се одвиваат работите да работат доста само како добро.
Во ред. [Шепоти] Колку е часот?
На последната работа што сакав да покаже - и јас само ќе го направи тоа навистина брзо.
Знаеш како сме # define па ние # можат да се дефинираат MAX како 5 или нешто?
Да не MAX. # Define ОБВРЗАНИ како 200. Тоа е она што беше порано.
Што ги дефинира константа, која е само ќе бидат копирани и атипичен
каде и да се случи да се напише врзани.
>> Значи ние всушност може да направи повеќе со # дефинира.
Ние # можат да се дефинираат функции.
Тие не се навистина функции, но ние ќе ги наречеме функции.
Еден пример би бил нешто како MAX (x, y) е дефиниран како (x <y y: x). Во ред.
Значи треба да се навикнеш на тројната оператор синтакса,
но е x помалку од y? Врати y, друго се вратат х.
Така можете да видите што може да направи овој посебна функција,
и функцијата може да биде како bool MAX зема 2 аргументи, да се вратите ова.
Ова е еден од оние кои најчесто гледам направи вака. Ги нарекуваме макроа.
Ова е макро.
Ова е само синтакса за тоа.
Можете да напишете макро да правите што сакате.
Вие често видите макроа за дебагирање printfs и работи.
Така еден вид на printf, постојат специјални константи во C како црта линија црта,
2 подвлекува линија црта,
и таму е исто така мислам 2 подвлекува функции. Тоа може да биде тоа. Нешто слично.
Тие работи ќе биде заменет со името на функцијата
или бројот на линијата која сте.
Најчесто, ти пишувам дебагирање printfs дека овде би можел потоа само напиши
Debug и тоа ќе печати бројот на линијата и функција што се случи да биде во
дека се сретнал дека DEBUG изјава.
И ти исто така може да печати други работи.
Значи едно нешто што треба да внимаваш за е ако се случи да # define DOUBLE_MAX
како нешто како 2 * y и 2 * x.
Така и за која било причина, ви се случи да се направи тоа многу.
Така го прават тоа макро.
Ова е всушност скршена.
Јас би го нарекол тоа со нешто како DOUBLE_MAX (3, 6).
Значи она што треба да се вратат?
[Студент] 12.
Да, 12 треба да се вратат, а 12 се враќа.
3 добива заменува за x, 6 добива заменува за y и се враќаме 2 * 6, кој е 12.
Сега, она што за ова? Што треба да се вратат?
[Студент] 14. >> Идеално, 14.
Прашањето е во тоа како хаш дефинира работата, се сеќавам тоа е буквално Copy и Paste
на доста сè, така што тоа се случува да се толкува како
е 3 помалку од 1 плус 6, 2 плус пати 1 6, 2 пати 3.
>> Значи за оваа причина што речиси секогаш заврши што е во загради.
Секоја променлива скоро секогаш заврши во загради.
Има случаи каде што не треба, како знам дека не треба да го направите тоа тука
бидејќи помалку отколку што е доста секогаш само оди на работа,
иако тоа дури и не може да биде вистина.
Ако има нешто смешно како DOUBLE_MAX (1 == 2),
тогаш тоа се случува да се заменува со 3 помалку од 1 еднаква изнесува 2,
и така, тогаш тоа ќе направи 3 помалку од 1, не дека еднаквото 2,
која не е она што го сакаме.
Значи, со цел да се спречи било кој оператор предност проблеми,
секогаш заврши во загради.
Во ред. И тоа е тоа, 5:30.
Ако имате било какви прашања во врска со pset, ги споделите со нас.
Тоа треба да биде забавно, како и хакер издание исто така е многу пореалистичен
од хакер издание на минатата година, па се надеваме дека многу од вас го испробаш.
Минатата година беше многу големо.
>> [CS50.TV]