[Powered by Google Translate] [Одељак 3] [мање комфорни]
>> [Нејт Хардисон] [Универзитет Харвард]
>> [Ово је ЦС50.] [ЦС50.ТВ]
>> У реду, хајде да почнемо.
Добродошли на Недељи 4 од ЦС50.
Ако ви отворите веб прегледач и отворити псет 3,
Јагма за ЦС50, ми ћемо кренути
кроз град питања тамо.
Баш као и прошле недеље, ми ћемо радити у ЦС50 Спацес,
ако такође ћете повући да се као добро,
и ако напред и посетите овај линк који сам добио овде на врху.
То је време да почнете.
Имамо нашу малу хи програм овде. Ништа луд.
Једна од првих ствари које желим да урадим са вама данас иде преко неколико решења
проблему сет 1, врста пример решења,
само тако можете добити осећај за оно што врсте код особља пише,
какве код других ученика пишете,
и да ли сте погледајте на њега, јер знам да је чудно
када пошаљете решење за проблем сету и добити коментаре
на сопственој верзији, али понекад је корисно видети како други људи то урадио,
посебно они који су лепо изгледа.
За највећи део, био сам заиста импресиониран са решењима које ви произведених.
Још увек нисам почео гледајући своје 2с проблематичних сету, али ако су нешто као први,
то не значи ништа осим добрих ствари.
>> Ако погледате моје ревизија, почнимо скроз доле на Ревизија 1,
а ми ћемо да се брзо погледамо Марио решење.
Ако повучете ово, ови програми да ћемо да представимо тачни.
Није било проблема са исправност ових проблема, већ
желимо да разговарамо мало о различитим питањима дизајна
који су се овде користе.
Једна од ствари која је била занимљива о решењу
је да се користи ову нову конструкцију зове фунта дефинисати,
понекад се такође назива хеш дефинисати.
Дозволите ми да увећате томе овде.
# Дефине вам омогућава да дају имена тих бројева у вашем програму.
У овом случају, максимална висина пирамиде у Марио
је 23 и уместо стављања 23 у мом коду,
бисмо позвати на то као хард кодирање 23 -
Уместо тога, ова даје име МАКС_ХЕИГХТ на тај број,
тако да овде у мом уради вхиле петље
ви у ствари можете да погледате МАКС_ХЕИГХТ
уместо да се број 23 за
[Студентски] Шта је предност тога?
То је велико питање.
Један је читљивост.
Предност коришћења ове # дефине је читљивост.
Када читам овај код, видим шта се дешава.
>> Ја могу да видим у том стању овде да вршимо тестирање
за висину као <0, што смо могли да се дефинишу
да буде минимална висина или мин висина.
Друга предност је у томе што сам тада може да чита остатак линије да бисте видели
да смо и ми проверава да бисте се уверили да је висина није већа од максималне висине,
зато ћемо наставити док је висина већа од максималне висине.
Друга предност је-ако сам умањили мало овде-
ако покренете овај програм и ја га покренете, рецимо, са 23 сада,
она ће штампати све 23 редове тек тако.
Али рећи да сам хтео да променим максималну висину,
а сада желим да ограниче максималну висину пирамида
да буде само рећи: човек, то је фанки.
# Инцлуде, # дефине МАКС_ХЕИГХТ,
и рецимо ми смо желели да поставите је једнак 10.
Сада у овом тренутку, све што сам морао да урадим је промените га у једној локацији.
Могу компајлирате код, и сада ако покушам и упишите у 12,
то ће ме питати поново.
У овом случају, ми само користимо МАКС_ХЕИГХТ једном.
Није да је велик муке да иде у
и променити га у вхиле петље, ако вам је потребно.
Али у програмима где сте референцирање исти чаробни број
изнова и изнова, овај # дефине механизам је заиста згодно
јер сте само то променити једну време на врху датотека обично је где сте ставили их-
а промена перцолатес кроз остатак датотеке.
>> Друге ствари које сам желео да констатује у овом задатку који сам мислио изгледао заиста лепо,
један је именовање променљивих.
Овде се види да имамо целе променљиве се зову ред и зове висина.
Размаци, хашх, то помаже да код мало више читљивим,
чини мало више разумљиво шта се заправо дешава.
Ово је у супротности са коришћењем, рецимо, случајних слова
или само Гоббледигоок заједно.
Коначна ствар коју ћу истаћи је да у за петље,
Често ови итератор променљиве, ови бројачи које користите у вашој за петље,
то је стандардна и конвенционална да их почне са било и и затим Ј, а затим к
и иде даље од тамо ако вам је потребно више променљивих
и ово је само конвенција.
Постоји много конвенција.
То зависи од програмског језика који користите.
Али у Ц, што обично почињу са ја.
То нема смисла да користи, рецимо, или б
у зависности од ситуације.
То је то за овај један.
Ако сада попните Ревизија 2, видећете другу Марио,
и ово је један сличан другом који смо управо видели,
али ипак нешто кул.
Ако гледамо на овом делу овде унутра унутрашњи фор петљи,
они користе неки луди тражите синтаксу право у овој линији.
Ово се зове тернарни оператор.
То је, ако други изјава кондензује у једној линији.
Услов је тај део у загради.
То је еквивалент говорећи, ако ј <висине - и - 1.
И шта онда садржина да ако блок ће бити су простор
а затим садржај шта друго би се ово #.
То је у суштини је додељивање простора да ове променљиве.
То је стављање простор у садржају блок променљиве,
Ако је овај услов испуњен, а ако услов није испуњен,
онда блок променљива добија ово #.
И онда, наравно, уместо изградње читав низ
и штампање све се на крају ово решење је штампа један карактер у једном тренутку.
Прилично кул.
>> Други пар ствари да гледају. Ми ћемо прећи на похлепан.
Сада, ако погледамо похлепан, ово прво решење
користи ово # дефинише прилично мало.
Имамо једну константу дефинисано за сваки од различитих бројева у овом програму.
Имамо једну за центи по долару, један за квартала, затамни, новчиће, и паре,
и сада ако померите надоле и прочитате код,
можемо видети стандардне уради док све петље штампе напоље.
Некако у срж овог проблема је схватила да
Ви треба да конвертујете пловак који сте прочитали у од корисника на цео број
да се тачно уради математику, а то је зато што
са покретним зарезом бројевима, као што смо причали у предавању на кратко,
није могуће прецизно представљају сваки вредност на линији број
јер постоји бесконачно много вредности између 3 и, рецимо, 3.1 чак.
Можете имати 3,01 и 3,0001 3.001 и, као и да наставимо.
Испада кад радите са новцем, често желите да га конвертујете
у цео формат, тако да не губиш паре и такве ствари.
Доинг то и заокруживање био кључ.
Ово решење користи савршено једноставан, одличан алгоритам
која декрементира број преосталих центи, прво по кварталима,
онда Димес, затим новчиће, затим пенија,
и додавање броја кованица сваки пут.
>> Друго решење које ћемо видети, као што сам умањите и идите на ревизији 4,
имала веома сличан почетку, али уместо да се користи ДИВ и МОД
овамо да израчунамо број центи.
Ово је број квартала једнак броју центи подељен 25,
а разлог је зато што то ради радимо цео поделу,
тако да је одбацивање било остатак.
[Студентски] Да ли морамо да коментарише претрагу?
То стварно зависи.
[Студентски] Ти коментаришући више него код овде.
Да, па постоји гомила различитог филозофије на ово.
Моја лична филозофија је да је ваш код је заиста истина,
као коду је оно што се заправо извршавање на рачунару,
и тако ваш број треба да буде читљив, што је могуће да се не захтевају толико коментара.
То је рекао, када се раде ствари које су некако незгодно математички
или алгоритамски, добро је да коментарише оне тако да можете
додаје нову димензију, екстра лаиер ко чита свој код.
У овим решењима, често су коментарисали теже само зато
желимо да будемо у стању да их дистрибуирају и да их људи покупи
и прочитајте их прилично лако.
Али дефинитивно, ја бих се сложио да је то тешко.
[Студентски] Али када су у недоумици, ићи теже?
Када сте у недоумици, ићи теже.
Неки људи ће понекад кажу 0 повратка или нешто слично томе.
Мислим да је то смешно коментар.
Јасно да је то оно што се дешава.
Не треба енглеском да ми кажеш.
Понекад људи ће писати такве ствари "ктхкбаи!"
То је сладак, али и не-
то није прављење разлике између коментаришући поена или не.
Ове врсте су коментари само ха, ха.
Кул.
>> У овом тренутку, хајде да почну да раде на проблему Сет 3 део питања.
Ако ви повуците поново ово,
као и прошле недеље, нећемо да гледамо шорц у овом одељку.
Пустићемо ви то у своје слободно време и разговарати о питањима.
Али сада, у овом одељку ћемо потрошити мало више времена
говоримо о мање од кодних основа
као што смо урадили прошле недеље, а уместо тога, ми идемо да се усредсреде на
мало више од теорије, тако да причамо о бинарном претрагом и затим сортирање.
Од оне који су после, заједно са предавања,
може неко да ми дају рекапитулацију онога разлика
између бинарног претраживања и линеарне трагања?
Шта се дешава? Наравно.
Линеарни претраге претражује сваки елемент у сортиране листе
један по један по један по један по један,
и бинарна претрага дели листу у 2 групе,
Проверава да ли вредност кључева које сте у потрази за је већи или мањи од средње вредности вредности
који сте управо нашли, и ако је мања, то иде са нижим листи
и онда дели то поново, да ли иста функција
скроз доле док не пронађе средину буде једнака самој вредности.
Тачно.
>> Зашто нас брига?
Зашто причамо о бинарном претрази у односу на линеарне претраге?
Да.
Бинарни је много брже, па ако се удвостручи величину проблема
потребно је још један корак пре него дупло више.
Управо тако.
То је одлично решење.
Линеарна претрага је веома проверава један елемент у једном тренутку,
и као што смо видели на првог дана предавања
када је Давид прошао кроз његов пример телефонског именика
и поцепао се једну страницу у именику истовремено
и задржао да ради изнова и изнова и изнова,
то ће му узети заиста дуго времена да пронађе некога у телефонском именику,
осим, ​​наравно, он је тражио некога на самом почетку писма.
Са бинарном претрагом, можете ићи много брже,
и то не само дупло брже или 3 пута брже или 4 пута брже.
Али проблем постаје мањи и мањи и мањи много брже.
Да би илустровали ово, ми ћемо почети разговор о томе шта се дешава
када пишемо бинарну претрагу.
Проблем при руци је да ако имам низ бројева,
кажу, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
и онда 9 са тону 0с после њега,
желимо да буде у стању да схвати веома брзо оно што је у
Овај низ бројева.
Знам да ово изгледа мало блесаво и помало вештачка,
јер управо сада јесте.
Имамо низ који нема баш много елемената у њој,
и ако питам неку од вас да схватим да ли је или није
23 је у низу, можете то урадити врло брзо
само поглед на ово и говорио ми да или не.
Аналогни размотрити је замислити да је ово, рецимо,
Екцел табеле са 10.000 редова, 20.000 редова.
Наравно, можете да урадите Ф команде или контроле Ф и изгледају нешто горе.
Такође можете да користите филтере и претрагу ствари,
али ако сте морали да погледате кроз тај фајл линију по линију по линију,
било би вам потребно доста времена да га пронађу.
То је као у примеру именику, такође, где је
нико не гледа кроз телефонски странице књиге један по један.
Типично, они могу да отворе на средини,
или у случају много телефонских књига и речника где
стварно сте га унели у првом писму,
ви окренете се том првом писму и отворити и кренути путем тамо.
>> Подсети ме зовеш >> Семе..
Сем.
Као Сам рекао, да је линеарно претраживање процес ће бити веома спор,
и уместо са бинарном претрагом, начин ово ради јесте да
сваки пут идемо кроз итерације нашег потрази алгоритма,
ћемо поделити листу на пола, у суштини,
на две мање листе.
А онда на следећој итерацији петље, ми ћемо га поделити поново
у другим мањим листама.
Као што можете да видите, проблем постаје све мањи и мањи
јер ми би одбацивање половину листе сваки пут.
Како то одбацују ради?
Баш као подсетник, шта ћемо да радимо ако је рачунар
и били смо, рецимо, у потрази за бројем 5 на овој листи
јесте да ћемо изабрати број у средини.
У средини ове листе, јер су 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 бројева,
ћемо изабрати број ни на 4. позицији, или на 5. позицији,
и ми бисмо назвати средину нашој листи.
Изаберите број у средини.
Затим, као што Сам рекао, ми ћемо тестирати да видимо да ли је тај број једнак
до броја који желимо да или нашој жељени број.
Ако је исти, онда смо га нашли. Ми побеђујемо.
Ако није једнак, онда постоји неколико случајева.
Два случаја су или број мора бити већи од броја смо гледали,
или је то мање од.
Ако је већа, ми смо прешли на десну страну.
И ако је мање, ми смо прешли на леву страну.
А онда поновите читав процес
на било десној половини или левој половини листе.
>> Први проблем у делу данашње је да схвати
како ми заправо можемо почети да изрази ово у Ц коду.
Ми смо овде на Псеудокод.
Шта ћемо почети радимо је да ћу подићи потпуно нови простор,
сачувате ову ревизију, тако да ми имамо ове белешке за касније,
ћемо избрисати све ово, а затим копирајте и налепите од проблема скупа
ове информације у нашим просторима, а надамо се ово не пукне.
Савршено.
Ако ви све то, копирајте и налепите овај код у свој нови простор,
у празном један.
Хајде да пробамо Данила. Ако компајлирати и покренути овај програм, да ли ради?
Но >> Шта то говори?
Он каже да контрола достигне крај нон-воид функција.
Да, па ћу покушати покрећући га.
Јесте ли видели ово раније? Да ли знате шта то значи?
Ок, хајде да сецира ово мало.
Он каже на филе.ц на линији 9, колона 1 имамо грешку, баш као што си рекао,
и каже да је то проистиче из грешке упозорења и повратка типа упозорења.
Изгледа да се нешто дешава са повратном типу, што има смисла.
Имамо нон-воид функцију, што значи да имамо функцију
да не врати празнину.
Празнина функција је онај који изгледа овако:
воид Фоо (), а то је празнина, јер повратак тип празнина,
што значи да ако имамо нешто овде
као повратак 1, ми бисмо добили грешку компајлер за ово.
Међутим, ми имамо нон-воид функцију.
Наш нису неважећи функција у овом случају је наша функција претраге
јер има повратну тип Боол.
Када се каже да је контрола достигне крај нон-воид функција,
то је зато што тражи нема изјаву повратка.
Није се враћа ништа типа Боол.
>> Можемо то да средим, и шта ви мислите
Претраживање би требало да се врати по дефаулту?
Шта би требало да буде стандардна повратна вредност претрагу?
Јер то је оно што можемо да ставимо на крају.
Шарлот, да ли имате било-?
Тачно или нетачно >> Тачно или нетачно.
Који?
Нетачно. Не знам.
Лажно? Хајде да пробамо.
Зашто би сте рекли повратак лаж? То је сјајно интуиција.
[Шарлот] ја не знам.
Ми ћемо да се врати фалсе у овом случају, јер ће ово бити наша стандардна
ако из неког разлога је листа празна, или игла
да тражимо не постоји.
Затим, на самом крају, ако ми се не врати тачно раније у овој функцији,
увек знамо да ће ова функција рећи Не, то није у низу.
То није у пласту сена.
Сада, ако се компајлирати и покренути га, пусти ме спаси то тако можемо повући се.
Сада, ако се компајлирати и покренути наш програм, она гради.
Ми смо добили нашу малу промпт.
Ако сам погодио 4-ух-ох.
Није одштампати ништа. Изгледа као да је све завршило добро.
Морамо да попуните овај унутра
Разговарали смо о алгоритма у Псеудокод пре мало.
Да видим, осим тога,
а ја ћу повући тај алгоритам назад поново.
Хајдемо овог типа. Јок.
Ту је.
Како да радимо ово?
Шта ће бити добра стратегија за почетак искључите ову шифру?
Морате да изаберете број у средини.
Како да изаберете број у средини низа?
Свака сугестија?
[Студентски] стрлен подељено са 2.
Стрлен подељено са 2. То је велика један.
Стрлен ради са специјалним врстама низова.
Које врсте низова?
Стринг низови, карактер низови.
То је то иста врста концепта који желимо да се пријаве,
али не можемо да користимо стрлен јер немамо низ знакова.
Имамо низ Интс.
Али шта значи стрлен добити за нас?
Да ли знате шта она добија за нас?
[Студентски] стрлен нам добија дужину.
Тачно, то нам добија дужину.
Стрлен добија дужину низа за нас.
>> Како ћемо се да у нашем програму бинарном претрагу?
Како бисте добили дужину низа?
[Студентски] стрлен?
Можете добити дужину правилно форматирана Ц гудачког низа са стрлен.
Проблем је, међутим, јесте да ми немамо низ ниске.
Ако се осврнемо на овом шифром, имамо овај цео низ.
Како да знамо колико је то?
[Студентски] Да ли постоји еквивалент за један крајње тачке, као што су инт л или тако нешто?
Испоставило се да заправо није, и тако на неки начин, ово је
једна од оних ствари које је само добро знају о Ц,
да не постоји начин да се дужина низа
ако су сви ти дам је низ.
Разлог ради са жицама, разлог стрлен радови,
јер ако је ниска правилно форматиран,
она ће имати ту посебну \ 0 карактер на самом крају.
>> Такође можете да замислите да имате правилно форматирану ниску
и ту нема \ 0 карактер, онда се цела ствар не ради.
[Студентски] Да додате \ 0?
Ми смо могли у овом случају.
Могли бисмо додати некакав \ 0
или неки означава карактер и онда то користити.
Али то није сасвим иде на посао
зато \ 0 је за цхар тип,
и овде имамо Интс.
Друга ствар је да смо били користити посебну вредност
као -1 до означити крај низа
онда никада не би могао држати у нашим -1 целих низова.
Биће нам заглавила.
Испоставило се да је једини начин да добијете дужину
од низа у Ц је заправо да се сетим
када га подесите, а затим га прође около са низом
тако да кад год имам функцију која се дешава да неки посао
на низ целих или флоатс или дубл или шта сте ви,
Такође је потребно да се функција дужину низа а,
и то је управо оно што смо овде урадили за претрагу функцију.
Ако погледате шта смо урадили кад прођемо у нашем низу овде,
такође проћи у дужини, величина.
Једноставно се догоди да смо овде назива ову променљиву,
овај параметар или аргумент.
Ово се зове аргумент листу или у функцији је параметар листу,
и то се такође називају аргументи или параметре.
Људи користе различите термине у различитим временима.
Понекад их замените себе.
Тако се дешава да управо ова варијабла овде је слично имену
ово # дефине овде.
Али они нису иста ствар.
Капитализација не материју.
>> Ако погледате шта се дешава овде, ми изјављујемо
наш инт низ, који смо се зове бројеви.
Успели смо дали нашу величину, што одговара нашим # дефине се на врху.
То ће бити 8.
И онда када смо онда позвати нашу функцију за претрагу доле,
пролазимо у броју желимо да тражи, које смо од вас затражи,
стечен од корисника.
Пролазимо у низу, овај број,
и онда морамо да прође на величину низа,
и онда вредност величине 8 добија складишти
или проследити ову целобројну променљиву зове величине.
Имамо величину низа.
Сада, ако се вратимо на оно што смо причали раније,
Мислим Мисси довео до тачке да је оно што нам је потребно да урадите је да на дужину низа
и поделите га са 2, а то ће нам дати средину.
Хајде да видимо.
Могу ли неко написати ово и сачувајте је у њиховом простору?
Шта мислите о Лејлом?
Могу ли да вам пишем ово у?
Напишите прву линију где узмете дужину низа и добити средину
и чувајте га у новом променљивој.
Ја ћу вам дати пар секунди. Јесте ли спремни?
[Студентски нечујан]
Наравно, могао сам да те израчунати средину
у пласту сена низа унутар претрагу функције
користи дужину низа пласту сена, што је величина променљива?
Ништа незгодно овде.
[Леила] Само величина / 2 и само-
И спаси га и притисните Саве дугме овде на врху,
и ми ћемо га подигне.
Савршено.
Ту смо. Страва.
>> Као што је, да ли ће то саставити?
[Леила] Не, то треба да буде већа.
[Нејт] Да, па шта треба да урадимо?
[Леила] Као инт средину, или тако нешто.
Страва. Да, хајде да урадимо то, инт средину = величина.
Хоће ли ово састави?
Хајде да избришете овај коментар и да га са пута.
Шта неће саставити о томе?
Ми не радимо ништа са цео број,
тако да морамо да штампате или нешто слично томе.
Да, баш тако.
Ми ћемо добити неискоришћени променљиву.
Шта друго неће радити о овоме?
Мислим да сте рекли нешто, Сам. Зарезом.
Да, ја сам нестала та зарезом.
То ће бити константна ствар у целом току мандата.
Коначна ствар коју ћу урадити је да ћу ставити мало белог простора на обе стране
овог оператора овде, пошто је то типично како радимо
према нашем стилу водича.
Имамо средину нашег низа.
Сада, ако се вратимо сећам нашег алгоритма,
шта је други корак који смо морали да урадимо када смо средину?
[Студентски] Ако је већа [нечујан].
Да, па морамо да урадимо неку врсту поређења, а шта ми радимо овде у односу?
Рекли сте да ако је већи од. Шта је то у тој реченици се односи на?
Број који се појављује, ако је већа од средње вредности, а затим идите до низа?
Тачно, тако да је број који се појављује када-
Игла, тако да смо у односу на игле,
и шта смо у односу према иглу?
Зато игла је оно што тражимо.
Ми смо га пореде доћи до средину.
>> Али нема смисла да проверите да ли
Ако игла = средину?
Да ли то смисла?
Да ли неко не слаже?
Хајде да га дају пробати, ако (игла == средину).
[Студентски] Да ли иф је нашао.
[Нејт] принтф ("Нашли смо га \ н");
Иначе-Идем да почнемо да радимо овде нешто друго.
Ја ћу почети постављање протезе око ако изјаве свих времена
Управо зато, ако додамо још ствари, онда
не добити преводиоце.
Да, Сем. Имаш право.
Проблем је у томе што средину представља позицију у низу,
али могу да га представљају вредност у том положају низа.
То је велика ствар.
Да ли су сви чули шта је рекао Сем?
Он је рекао да је средину, као што је
представља само позицију у низу, али то није стварна елемент у низу.
Ако мислите о коду као писани сада,
ако погледамо овај низ овде доле, која има 8 елемената у њој,
шта је вредност средину ће бити у овој функцији?
[Студентски] 4.
[Нејт] 4.
Ако тражимо број 4 -
а ми само да покренете овај код и стави мало тужну фацу овде
јер нисмо пронашли да је-ако смо покренули овај код
као што је сада, уплоад га, зграда, пусти ме доле померање,
и ако тражимо број 4,
смо га пронашли, али нисмо добили то принтф да.
Један од разлога је што нисмо вратили истина,
али смо заиста пронашли број 4?
И Сем не говори.
Шта смо сазнали?
Ми заиста нашли средину, који, ако се погледа низа доле,
то ће бити елемент у индексу 4 да гледамо,
који је 23.
>> Како ћемо заиста добити тај елемент у средини
а не само сама средину?
[Студентски] Ми бисмо унели знак или тако нешто?
Шта би то урадили, само из радозналости?
Можеш ли елаборирати мало више?
Морате да трансформишу позицију у броју,
па мораш да нека веза-Ја мислим да је то знак, али то не може бити.
Да, то је добра ствар.
Ми смо радили доста ових конвертовања позицијама у карактера, ове знакове,
у прва два сета проблема.
Испада да је овде, ово је скоро слична
приступ ИТХ карактер у низу, ако то има смисла.
Овде желимо да приступимо елемент средње вредности.
Како то да урадимо?
Кевин, да ли имате предлоге како бисмо могли да урадимо то?
Могли пласт уради, отворена заграда, средином, затворене заграде.
Можеш ли написати да је за нас?
Сачувај га овде, а ми ћемо повући то.
Гледамо у овој линији 9,
и ми смо схватили да не желимо да упоредимо иглу на средини,
али уместо тога, желимо да упоредимо иглу
до елемента на позицији средину у нашем пласту сена низа.
Кул.
Ту смо.
Да, то изгледа прилично добро, ако је (игла == пласту сена [средину]).
Ми смо га нашли.
Сада, ако смо покренули код-ве'лл бацк уп мало-
она саставља, он трчи, а сада ако тражимо 4,
нисмо га пронашли, јер сада ми заправо добијамо број 23.
Добијамо је вредност 23, и то је оно што смо у односу на наше иглом.
Али то је добро. То је корак у правом смеру.
>> То је оно што ми покушавамо да урадимо.
Ми не покушавамо да се упореди иглу против позиције у низу
већ против актуелних елемената у низу.
Ако се осврнемо уназад сад опет на следећем кораку у нашем алгоритма,
шта је следећи корак?
Леила је већ поменуто кратко.
[Студент] Проверите да ли је већи или мањи од, а затим одлучите који начин да се креће.
[Нејт] Да, па како бисмо то урадили?
Можеш ли да уложимо Ја ћу спасити ову ревизију,
и онда ако се стави у неке линије које ће то урадити.
Да, Шарлот >> имам једно питање..
Зар не би требало да буде средишња тачка - 1, јер је прва ствар
је 0 то индексиран, па ако ставимо 4, то није уствари лик тражимо?
Да, а други проблем који је,
То је велики улов, јер оно што се дешава завршити дешава евентуално
ако ми наставимо и ми никада не прилагоди на почетку?
Претпостављам да бисмо могли завршити раде покушава да приступи
елеменат на 8. позицији низа,
која је у овом случају не постоји.
Ми ћемо желети да урадите неку врсту обрачуна због чињенице
да имамо неку нулту индексирање.
[Шарлот] Жао ми је, мислио сам средину - 1 у угластим заградама.
Можемо да урадимо то.
Вратићемо се овом питању у само мало.
Када почнемо да дође до стварног петље,
то је кад смо стварно ћете видети у игри.
За сада, можемо да урадимо ово, али ти си потпуно у праву.
То нула индексирање ће имати ефекат који нам је потребно да се објасни.
Хајде да видимо.
>> Како је већи него и мање од-?
[Студентски] Ја се како то да урадите веће или мање од дела.
Ја само нисам био сигуран шта да штампате уколико сматрају да је то мање него пласту сена средину или већи од.
Овде можете да сачувате оно што И'ве-
[Нејт] Да, ако сачувате оно што имаш, а ми ћемо га подигне.
Ту смо.
[Студентски] И ја сам ставио питање марака за оно што нисам знао.
[Нејт] То изгледа сјајно.
Овде имамо упитнике, јер ми још увек не знамо
шта ћемо урадити још доста.
Шта би ми желимо да урадимо-упс, имамо неке протезу све фанки на нас.
Ми ћемо исправите ове заграде.
Ту смо.
И тако шта желимо да урадимо, према речима нашег алгоритма,
ако не нађемо иглу?
Рецимо, у случају да је игла је мање од онога што гледамо. Кевин.
Само погледајте на левој половини.
Добро, па ћемо ставити коментар овде који каже: "погледај у левој половини."
А ако је казаљка већа од пласту сена у средини, шта желимо да урадимо?
[Студентски] Онда се осврнемо на десној половини.
Поглед на десној половини, "погледај десној половини."
Није превише запуштена.
Ок, тако да у овом тренутку, ствари су изгледа прилично добро.
Проблем са шифром као писани је шта?
[Студент] Немаш крајње тачке за половине.
Добро, не морамо крајње тачке за половине.
Такође смо само да идем кроз ово једном.
Ми само ћемо да погледамо један вредношћу.
Или елемент постоји, или није.
У циљу комплетирања ово, ми ћемо морати да урадимо неку врсту понављања.
Морамо да понавља док не видимо да
ни елемент је ту зато што смо сузили и коначно га нашао,
или то није тамо, јер смо гледали кроз све ствари
у одговарајућим половине низу и утврдили да ништа није тамо.
>> Кад год имам ово понављање дешава, шта ћемо користити?
[Студентски] петља.
Нека врста петље. Да.
[Студентски] Можемо направити уради док петља и да то ради, а затим, док
игла није једнако-Нисам сигуран где сам ишао са тим.
Али нешто као да урадим док се то не деси једнака вредност коју корисник улаз.
Да, па хајде да видимо како би то могло се писати?
Рекли сте да је користите уради док петља.
Одакле почети радити?
[Студентски] Одмах након величине / 2.
[Нејт] Добро, а шта ћемо да радимо?
Ми ћемо испунити у време касније.
Шта ћемо да радимо?
[Студент] Зар не желимо да урадимо све ствари имамо у ако делу?
[Нејт] Који све ове ствари, сјајно.
Копирање и лепљење.
О, човече.
Хајде да видимо да ли ово ради, ако можемо картица овоме.
Дивно.
Ок, и то тако да штедимо ви га имате.
У реду, а ми ћемо да урадимо ово, док-
шта је, а услов сте били после?
[Студентски] Док се игла не равноправни, тако као знак узвика.
Али нисам сигуран тачно шта је то још.
[Нејт] Да, ово је један од начина да се то уради.
Сем, да ли имате коментар?
[Сам] Сетио сам се кад сам погледао видео,
Узео сам снимак једног од налик када смо урадили Псеудокод за њега,
било је неких веза између мак и мин.
Мислим да је то нешто као да мак све мање од мин.
Имам га.
[Сам] Или желите да максимално није мање од минута, или нешто слично,
јер би то значило да сте тражили све.
>> Да, па шта то звучи као мак и мин су мислили?
[Сам] Вредности које-целих бројева који ће се променити
у односу на место где смо ставили средину.
Управо тако.
[Сам] У том тренутку, то ће [нечујан] израчунати мак и мин.
Средину је ово мак и мин идеја.
Да ли то смисла људи?
Ако бисмо кренули да гледамо како ћемо да урадимо ово итерацију,
ти си потпуно у праву да желимо да користимо неку врсту уради вхиле петље.
Али претпостављам да ако се сетимо шта се дешава на месту овог низа
а шта се заправо догађа-Идем да пишем овде,
на првом итерацији бинарног претраживања, имамо-
Ја ћу користити Б и Е да означи почетак.
И онда крај нашег низа.
Ми знамо да је почетак на 4 овамо,
и ми знамо да је крај на 108.
Реци ми у потрази за број 15.
Први пут кад смо то урадили, као што смо раније видели,
средину је или ће бити 16 или 23
зависно од тога колико смо израчунали ствари.
Пошто равномерно поделе у средини би нам овај простор
између 16 и 23, не можемо га поделити равномерно
или дели га и добити на прави вредношћу.
Ми ћемо погледати 16 година.
Ми ћемо схватити: "Хеј, 16> 15 које тражимо."
Да онда погледамо на левој половини низа
шта ћемо завршити радите је одбацивање
цела ова горњи део
и рекао: "Добро, сада наша крајња ће бити овде."
Наредна итерација петље наше, ми сада гледамо у овом низу,
ефикасно пошто одбацују овај део, јер сада
ако узимате средину да буде разлика између почетка и краја,
нађемо нашу средину да буде 8,
који онда можемо да тестирамо 8 да видимо где је у односу на број тражимо,
15, 15 сматрају да је већи,
тако да морамо да пређемо на десној део листе,
што знамо, јер смо људи и можемо га видети.
Ми знамо да је право део ће бити где смо га пронашли,
али рачунар не зна то, па шта ћемо урадити је заправо ћемо
су ово иде горе, а сада је почетак и крај
су на истом месту, тако да је средиште постаје само број на листи у том тренутку,
што је 15, а ми смо га нашли.
Да ли то бацају светлост на коме је цела ова мак и мин нотација иде,
праћење крајњих тачака низа како да схватим
како да сузите ствари доле?
>> Шта ће се десити ако ово није једнако 15 сада?
Шта ако смо у потрази за 15 и, уместо тога, овај број је такође 16?
Ми бисмо рекли, "О, то је већа.
Желимо да се вратимо на лево. "
И ми би преместили своју е са десне стране,
на којој тачки имамо крајње тачке које ће бити у конфликту.
То не би било у стању да тражи било више елемената
јер сада имамо крајње тачке и нашу почетак тачку
наш максимум и наша мин, сада су окренути.
Ми тражимо кроз цео низ. Ми не можемо наћи ништа.
То је тачка у којој би желели да кажу: "У реду, ми ћемо зауставити овај алгоритам.
Нисмо нашли ништа. Ми знамо да то није овде. "
Како је ово иде?
[Студентски] Како тачно значи рачунар пребацили крај?
Како је крај завршити пре почетка?
Крајњи завршава пре почетка
због математике да ћемо да урадимо сваки пут кад смо то урадили.
Начин на који смо заменили је ако погледате први пут смо урадили замену
где имамо почетак у 4 и крај
скроз доле на 108 и наша средину, рецимо, на 16 -
Идем да вратите назад у 15-ако тражимо од 15,
знали смо да оно што смо радили када смо проверили 16 и видела да је већа
и желео да одбаци цео десни део листе,
Видели смо да је оно што смо хтели да урадимо је да преместите ову е овде.
Ефективно, е добио преселио у један пред средину.
Исто тако, када смо радили ову итерације алгоритма
и средину је у 8,
утврдили смо да је 8 <15, па смо хтели да померите б
један поред средину.
Сада, почетак и крај су обе заједно у овом 15 година.
>> Ако бисмо се дешава да тражимо неку другу вредност, а не 15,
или ако је уместо тога био 15 16,
би смо открили да је е желимо да се крећу један пре средину.
Сада е бити тамо окренути мање од б.
Прошетајмо кроз колико смо заправо завршити овај алгоритам кодирања.
Знамо да желимо да имамо тај обрачун средње вредности.
Ми такође знамо да ми желимо да пратимо почетак и крај низа
нашег садашњег низа тако да можемо да схватимо
где је овај Лева половина листе је и где десна половина листе је.
Ми то радимо са било започети и завршити,
или можемо назвати их мин и мак.
Ја ћу користити почети и завршити овај пут.
Када смо почели, ако погледамо назад у нашем примеру доле,
наш почетак је постављена на самом почетку низа, као природан.
Шта индекс је ово? Шта треба да почне да се наша?
Данијел.
[Данијел] Пласт [0].
[Нејт] Да, тако да смо могли да једнако пласту сена [0].
Проблем је, међутим, да ово нам даје не на позицију првог елемента.
То нам даје индекс првог елемента, односно стварне вредности у тој првој позицији.
[Студент] То ће претворити у .20?
[Нејт] Шта ће урадити је-добро, то неће учинити било претварања.
Шта ће урадити је да ће ускладиштити 4 у почетак,
а онда ће бити тешко правити поређења против почне
јер бегин ће одржати вредност 4,
што је почетак нашег низу,
али желимо да пратимо индекса у низу
за разлику од вредности.
Ми заправо ћете користити 0, овако.
За крај низа-Цхарлотте донео ово мало раније.
Ово је место где ћемо узети у обзир нула индексирање.
>> Шарлот, шта је крај низа?
Шта је индекс на крају?
[Шарлот] Величина - 1.
Да, и које величине треба да користимо?
Треба ми користимо величину капитала или малим величину?
Капитал величине.
У том случају, могли бисмо да користимо величину капитала.
Ако бисмо хтели да би ова функција буде преносив
и користите ову функцију у другим програмима,
заправо може користити малим величину.
То је у реду.
Али Шарлот је потпуно у праву да ми желимо да имамо величину - 1.
У овом тренутку,
[Студентски] Како то да можете да користите велико величине?
Како то да смо могли да користимо велико величине?
Испада да су ово # дефинише заиста,
испод хаубе, као што је текст пронашли и заменили, ако то има смисла.
Када саставите кода, предобрада фаза
од компајлера иде преко фајла,
и изгледа за свуда да сте написали капитала величину,
и замењује тај текст буквално са 8, баш тако.
У том смислу, ово је веома разликује од променљивој.
Она не заузима никакву простор у меморији.
То је једноставан текст замене трик.
У овом случају, ми ћемо користити величину.
Одавде не желим да урадим неку врсту понављања,
а ми смо на правом путу са нашим до-вхиле петље.
Желимо да урадимо нешто док стање не држи више,
и као што смо раније видели, видели смо да је стање
био је заиста то не желимо крај
бити мање него почне.
>> Ово је наш заустављања стање.
Ако се то деси, желимо да се заустави и прогласи као, "Хеј, нисмо нашли ништа."
Да изразимо то, ми не желимо да користимо неку петљу.
У том случају, да ли би до-вхиле петље, за петљу, док је петља?
Имамо овде уради док петља.
Да ли ви као таквом приступу?
Да ли мислите да би требало да покушамо другачији приступ?
Кевин, било мисли?
Могли смо петљу вхиле јер знамо максимум
бити већа него на почетку мин аниуаис.
Да, па нема иницијализација који треба да се деси.
Ови до-вхиле петље су сјајно када морате да покрене нешто
пре тога тестирање, а овде
знамо да нећемо да реинитиализинг како почињу и завршавају
свака рунда петље.
Знамо да желимо да их покрене, а затим проверите нашу стање.
У том случају, ја заправо идем са једноставним вхиле петље.
Испоставило се да су до-вхиле петље користи прилично ретко.
Много места ни не предајем не вхиле петље.
Они су добри за руковање корисника улаз, тако да смо видели доста њих до сада.
Али за нормално и док петље су много чешћи.
Испоставило се да је овај услов како је написано
неће заиста нам учинити много добра, и зашто је то тако?
Жао ми је, ја не знам твоје име.
Ја сам Џери >> Извини.
То је Б-О-Р-У-ја.
Ох, у реду.
Ја не видим на мојој листи.
Ох, то је зато што, ох, то има смисла.
Да ли имате идеју зашто се ово вхиле петље можда неће радити како треба,
како је написано у стању?
[Џери] Мислиш, као да желите све ствари после тога у-?
Да, тако да је то један.
Можда ћемо морати да стави све ове ствари у вхиле петље, што је потпуно тачно.
Друга ствар која је мало проблематично, међутим, да се овај услов не ради.
[Студентски] Мораш да га окренете.
Добро, па ово стање никада неће бити истина у почетку начин смо причали о томе.
Желимо да урадимо нешто до краја <почетак,
али желимо да урадимо нешто, док
почети ≤ крај.
>> Тамо је то преокрет логике.
Ја сам крив за израду тих грешака све време.
[Студентски] Зашто то мора да буде мања или једнака?
Зато немој те се случај да морамо да
где је био само један елемент, а ми смо били доле,
и ми смо гледали само на 15 у нашем низу?
И наш почетак и наш крајњи били исти елемент.
Желимо да се уверите да носимо тај случај.
Ако смо стрејт мање него,
само би могли да пређемо на 2-елемента низа.
Када смо стигли до тог последњег елемента, ако је то наш елеменат, ми никада га пронаћи.
Сада овде можемо тачно урадити као што сте рекли.
Можемо почети плоппинг ствари право у сред нашег вхиле петље.
Можемо бућ у нашој средини.
Можемо узети све ово, ако изјаве,
исчупа из овог до-вхиле петље,
плоп их у,
очистите ствари мало,
и ја ћу ићи напред и сачувајте ову ревизију.
И у овом тренутку, ми смо веома близу.
Сем.
Мислим да сте такође имати Инт средиште = величина - 1/2.
Имаш га, величине - 1/2.
Да ли постоји још нешто што треба да промените о тој линији?
То је била добра прилика.
>> Шта величина ради? Да ли ћемо икада мења величину?
Да би линију овако, морамо да променимо величину.
Морамо да промените величину сваки пут идемо около за петљу.
Али запамтите, када смо ишли кроз нашем примеру само мало раније,
и ми смо имали почетком у 4
и крај свега начин на који тамо код 108?
Како смо израчунали средину?
Да ли користимо величину?
Или смо користили почињу и завршавају се уместо тога?
То је разлика између краја и почетка.
Тачно, и како тачно треба да напишем да, Шарлот?
Само крај - да почне.
Не би требало да уради - 1
јер - 1 је укључен у крају и почиње већ.
[Нејт] Одлично, ти си потпуно у праву.
Ми не треба да урадите - 1, јер је - 1 је укључен
и чинили када смо иницијализовати променљиву крај.
>> Има ли још нешто морам да урадим синтаксички да ова линија има смисла?
[Студентски] плус почети >> Плус почети.
[Студентски] На крају.
Јер то је само пола израчунава дужину.
Треба додати да почне.
[Нејт] Шта би то израчунали за нас?
Ако размишљамо о крају на овом првом итерације петље,
Крај ће бити у положају индексу 7.
Почните у положају 0.
Запамтите, ми тражимо било
Позиција 3 или 4 позиције.
Ако погледамо ову математику, само да би се мало више опипљив,
ставио овде неке бројеве, имамо 7, 0,
па 7 - 0, а затим / 2
је 3 у целобројног поделе, тј.
Онда морамо да онда додате наш почети?
Ми не у овом случају.
На првом итерацијом, то ће бити у реду, јер је 0 бегин.
Али, као што смо напредак, ми смо заиста све само треба
крај - бегин / 2.
Постоји још једна трик овде, а то је наиме један од приоритета.
[Студентски] Да ли нам треба заграде?
[Нејт] Управо тако, и то је зато што ако ми не стави ове заграде,
онда ова линија ће бити уместо тумачити
као (крај) - (бегин / 2), који се дефинитивно не желим.
Пази за оне примат правила.
[Студентски] Зашто се не заврши + почети?
Зашто се не заврши + почети?
[Студентски] Зашто то није тако?
Зашто би било +?
Мислим да си у праву.
[Студентски] Зато што је просек?
[Нејт] Крај + почне, ти си потпуно у праву.
Вау, тотално гоофед. У праву си.
Ако смо радили на минус, желели да додате почне поново ин
У том случају, ви сте у праву да желимо да узме просек од две,
па смо се да их додате, за разлику од њих одузимање.
[Студентски] То би такође радити ако си крај - бегин / 2 + почети.
То би, ако се уради Верујем да јесте.
>> На пример, ако смо гледали почетак,
и ми смо га померио овде
до 15 година.
Сада почните је на позицији 2.
Крај је на позицији 7.
Ако их одузима, добијамо 5.
Поделите то са 2, добијамо 2.
А онда додамо 2 назад,
и да нас стигне до 4. позиције,
што је овде, што је средишња тачка.
[Студентски] Да ли треба да се брине о омоту?
У ком смислу не треба да се брине о завијање?
Ако је збир или разлика између
зависности од тога како ћемо то урадити није ни број.
Тада рачунар збуни било када је 2,5;
Не крећете лево или десно да бисте утврдили који је средиште?
Имам га.
Испада да са целобројног поделе,
ми никада не добијају ове плутајуће тачке бројеве.
Ми никада добили децималу.
То је потпуно одбачен.
Ако имате рачунар дели два инт променљиве,
и један је 7, а други је 2,
нећете добити 3,5 као резултат.
Она ће добити 3.
Остатак ће бити одбачени, тако да ефективно је заокруживање-
Није круг него спрат, ако ви момци су упознати са тим у математици,
где сте у потпуности одбаци децималу,
па ви сте у суштини то скраћивања до најближег
цела позиција, на најближи цео број.
[Студентски] Али онда је то проблематично јер ако имате низ од 7 елемената
онда то аутоматски узима 3. елемент из средину уместо 4..
Како да се носимо са тим?
То је проблематично, јер ако смо имали низ 7,
то би узели 3. уместо 4..
Можете ли објаснити мало више?
[Студентски] Јер ако имате 7 елементе онда 4. елемент
ће бити средишња тачка, зар не?
Запамтите свој коментар о томе нула индексиран, мада.
[Студентски] Аха, тако да је у позицији 3. То би било средину.
Да.
Ох, у реду. Видим шта хоћеш да кажеш.
То је чудно, јер смо навикнути на цео овај појам
отарасили децимале.
То је велика ствар.
Хајде да завршимо ово.
Добили смо нашу средину израчунати.
>> Ми смо тестирање да видимо да ли је наша игла је једнака средњој вредности.
Ми смо штампања да смо га пронашли, али стварно, шта желимо да урадимо у овој ситуацији?
Успели смо пронашли, тако да желимо да позивалац зна да смо га нашли.
Имамо функцију која је Буловим откуцан функција.
Начин на који смо сигнал позиваоцу наше функције које смо спремни да идемо
је кажемо: "Хеј, то је истина."
Како бисмо то урадили, Кевина?
Ви климате главом >> [Кевин] Додај повратак истина..
[Нејт] Тачно, врати истина.
Сада, ако то није равноправна, како би ми гледамо на левој половини?
Било који идеја?
Стела, ани идеас?
Потребно је да подесите нову позицију за крај.
Да.
Зато морамо да урадимо позицију средину - крај.
Сјајно.
Морамо да поставите нову позицију за крај
да погледамо на левој половини.
То је оно што смо причали раније, где
Држим да се вратимо на овај пример.
Имам почети овде, и онда имам на крају скроз овамо.
>> Опет, ако тражимо 15, а наша средишња тачка је на 16,
и ми схватамо, "Упс, 16 је већа.
Ми желимо да пређемо на левој половини. "
Ми би онда померите крај 15,
а ми да је један одузимајуци од средину
и постављање да као наш нови крај.
Исто тако, ако желимо да погледамо на десној половини, како бисмо то урадили?
Да ли имате неку идеју?
[Студентски] Само подесите почети да средиште + 1.
[Нејт] Одлично.
И сада, у случају да не нађемо ништа,
то гет води брига за нас?
Данијел, то се брину за нас?
[Данијел] Но
[Нејт] Ако можемо успети кроз читав низ и не нађемо ништа,
где би то бити збринути, или би требало да бринемо о томе?
[Данијел], док стање.
[Нејт] Да, док је стање, тачно.
Она ће се побринути да пролазите кроз цео низ ако не нађемо ништа.
Ова док петља ће се завршити.
Никада неће смо наишли овај услов,
и можемо вратити лажна.
Ми такође можемо оставити ово ако овде овако
јер ако ово ако изјава истинита,
и наша функција ће вратити,
па смо у суштини ћемо прекинути ову функцију у овом тренутку
када смо се вратили истина.
Али шта се дешава са овом структуром овде?
Хоће ли овај посао у потпуности, или постоји неки логичан мана тамо?
>> Постоји нека грешка у логично тамо, начином на који се то поставили.
Шта би то могло бити?
[Студентски] Зашто вам треба - и + 1с?
То поставља нашу палету и да буде наш нови лево и десно пола пола.
[Студентски] Али зашто ниси могао да то уради без - 1с и + 1с?
[Нејт] Могли бисмо да једнако средину?
Шта може бити проблематично због тога?
[Студентски] Претпостављам да је неефикасно, јер сте проверу вредност која је већ потврђено.
[Нејт] Тачно, тако Сам је потпуно у праву.
Ако поставите крај и почети једнака средину
уместо - 1 и + 1 рефлецтивели,
у неком тренутку у будућности ћемо завршити проверу поново средину.
[Студентски] Почела сам псет, а онда сам имао нешто такво
где сам заборавио + 1, и заглавио у бесконачну петља.
Тачно, зато што у неком тренутку да никад ћеш се почети и завршити
да заиста преклапају.
Кул.
Постоји још једна логична мана, а то је да овај дефинитивно бити
иф.
Зашто би то могло бити?
>> Разлог је, ако то није иф-да ли сте видели да је, Кевин?
[Кевин] Да, јер ти мењају крајње тачке.
[Нејт] Управо тако.
Мењамо крајње тачке,
и ако је написано овако-ве'лл направи размак између-
он ће проверити овај случај.
Овај случај, ако то успе, ће прекинути ван функције.
Онда ће проверити овај следећи случај,
и ако то успе, то ће прилагодити крајње тачке,
а онда ће наставити и проверите овај случај.
Али, у овом тренутку, не желимо да се настави проверу.
Срећом, ми нисмо овде поново средину,
и ми знамо да овај случај неће успети.
Али ми дефинитивно желимо да ставимо иф тамо
иако то можда у овом случају
јер нисмо прилагођавање средину, да ли би то направити разлику?
Не, зато што ови случајеви су све искључиви.
Опет, моја грешка.
Ми не, мислим, треба овај иф.
Можемо му дати покушати покренути га и види шта се дешава.
Зграда, дошло је до грешке.
То је вероватно зато што сам напустио ово б је и Е је овде.
Да ли имате било више оних који су горе на врху?
То не личи на њега.
Ми смо умањили, граде,
тамо иде, па сад ако трагамо за 15,
Да.
Пусти ме унутра увећали
15, да. Можемо га поново покренете.
Отпремање изворни код, изградњу, трчање.
Можемо тражити нешто попут 13,
а ми не добијамо ништа штампање, тако да то није налаз да је за нама.
То је одлично, јер то није у нашој листи.
>> Сада су ван времена.
То ће бити за ову недељу.
Хвала за придруживање, и видимо се касније.
>> [ЦС50.ТВ]