[Powered by Google Translate] [Раздел 3] [по-малко удобни] 

[Нейт Hardison] [Харвардския университет] 

[Това е CS50. [CS50.TV] 

Добре, нека да започнем. Добре дошли в 4-та седмица на CS50. Ако вие отворите уеб браузър и отворете pset 3, Катеря с CS50, отиваме да почне да ходи чрез секцията на въпросите там. Също като миналата седмица, ние ще се работи в CS50 пространства, ако ще дръпнете, че, както и, и ако отидете напред и да посетите тази връзка, че имам тук на върха. Това е време, за да започнете. Имаме малка програма хай тук. Нищо луд. Едно от първите неща, които искам да направя с вас днес е да отидете в продължение на няколко решения Проблем Set 1, вид например решения, само така можете да получите усещане за това какви на код персонал е писмено, какви код другите ученици пишете, и трябва да погледнете в него, защото знам, че е странно когато представи решение за проблем и да получите коментари собствената си версия, но понякога е полезно да се види как други хора го правеха, особено тези, които са приятни търсите. За по-голямата си част, аз бях наистина впечатлен с решения, че вие, момчета, произведени. Все още не съм започнаха да търсят най-Проблем Задайте своите 2s, но ако те са нещо като първи, това не означава нищо друго освен добри неща. 

Ако се вгледате в моите ревизии, нека започнем по целия път надолу към Ревизия 1, и ние ще хвърлим един бърз поглед на решение Марио. Ако се справим с това до тези програми, които отиваме да представи са верни. Не бяха проблеми с вярност на тези проблеми, но по-скоро, искаме да поговорим малко за различните въпроси на проектирането , които се използват тук. Едно от нещата, които беше интересно за решение е, че той използва тази нова конструкция, наречена паунд определи, понякога посочен като хеш определят. Позволете ми да се фокусирам върху него тук. A # определят ви позволява да дава имена на тези номера в програмата си. В този случай максималната височина на пирамида в Марио е 23, отколкото да сложат 23 в моя код ние ще се отнасят до това толкова трудно кодиране 23 - вместо това дава името MAX_HEIGHT на този номер, така че тук ми направи линия, докато всъщност може да се отнася до MAX_HEIGHT вместо да постави номер 23. Студентски] Какво е предимството на това? Това е чудесен въпрос. Един от тях е четивността. Едно от предимствата на използването на този # определят четливост. Когато чета този код, не мога да видя какво става. 

Мога да видя в това състояние, че ние тестваме за височината е <0, което бихме могли да се определя също така да бъде минимална височина или височина мин. Другото предимство е, че може да прочетете останалата част от линията, за да се види че ние сме също така проверка за да се уверите, че височината не е по-голяма от максимална височина, защото ние ще продължим, докато височината е по-голяма от максимална височина. Другото предимство е, ако намалите малко тук ако стартирате тази програма и аз го стартирате, да речем, с 23 сега, той ще отпечата всички 23 реда просто ей така. Но да кажа, че искаше да промени максимална височина, и сега искам да се ограничи максималната височина на пирамидите да само да кажа, човече, това беше фънки. # Включват <stdio.h>, # определят MAX_HEIGHT, и да кажем, че ние искахме тя да е равна на 10. Сега, в този момент, всичко, което трябваше да направя, е да го промените на това място. Мога да компилирате код, и сега ако се опитам и въведете 12, ще ме подкани отново. В този случай, ние сме само с помощта на MAX_HEIGHT веднъж. Не е толкова голяма караница да отида в и да я промените в линия, докато, ако имате нужда да. Но в програми, където сте се позовават на същия брой магия отново и отново, това # определят механизъм е много удобен защото просто го смените едно и също време в началото на файла - това е обикновено, където можете да ги и промяна прониква през останалата част от файла. 

Други неща, които исках да се отбележи в тази задача, че мислех, че изглеждаше много хубаво, един е именуване на променливите. Вие виждате, че тук имаме целочислени променливи, наречени ред и призова височина. Пространства, хешове, тя помага на кода малко по-разбираеми, прави малко по-разбираемо какво всъщност става. Това е в контраст с помощта, да речем, произволни букви или просто бръщолевене напълно. Окончателното нещо, което ще се отбележи, е, че за вериги, често тези итератор променливи, тези броячи, които се използват за вериги, Това е стандартна и конвенционално към тях започват или със и след това J и след това к и става от там, ако имате нужда от повече променливи, и това е само конвенция. Има много спогодби. Това зависи от език за програмиране, който използвате. Но в C, ние обикновено започват с аз. То няма смисъл да се използва, да речем, или б в зависимост от ситуацията. Това е за това. Ако сега издърпайте нагоре Преработка 2, ще видите друга Марио, и това е подобно на другия, че току-що видяхме, но го прави нещо готино. Ако се вгледаме в този раздел тук във вътрешния контур те използват някои луди тук синтаксиса точно в този ред. Това се нарича третичния оператор. Това е ако друго изявление, сбива в един ред. Условието е тази част в скоби. Това е равностойно да се каже, ако J <височина - I - 1. И тогава какво е съдържанието на това, ако блок ще бъде пространството и след това съдържанието на какво друго би било #. Това е по същество пространство, за да се възложи тази променлива. Това е пространство, в съдържанието на блока променлива, Ако това условие е изпълнено, и ако условието не е изпълнено, блок променлива получава #. И тогава, разбира се, вместо изграждане на целия низ и отпечатване на всичко в края на това решение го отпечатва един символ в даден момент. Много готино. 

Още няколко неща за гледане. Ние ще преминем към алчен. Сега, ако погледнем алчен, това първото решение използва тези # определя доста. Имаме една константа, определени за всяка от различни номера в тази програма. Имаме един цента за долар, една за четвърти, Dimes, Nickels и стотинките, и сега, ако ние превъртете надолу и прочетете кода, можем да видим обикновено трябва да направите, докато всичко печат контур. Вид на същността на този проблем е да осъзнават, че ви е необходимо да конвертирате поплавъка, че сте прочели от потребителя до цяло число точно да направите по математика, и това е така, защото с числа с плаваща запетая, като говорихме за лекция накратко, не е възможно точно да представлява всяка една стойност на броя линия защото има безкрайно много стойности между 3 и, да речем, 3.1 дори. Можете да имате 3,01 и 3,001 и 3,0001, и можеш да продължиш напред. Оказва се, че всеки път, когато работите с пари, вие често искате да го конвертирате в целочислен формат, така че да не губим пари и от този род неща. Правейки това и закръгляване е от ключово значение. Това решение използва съвършено ясно, голяма алгоритъм, които декрементирани броя на останалите цента, първо по тримесечия, след това от Dimes, а след това от петачета, след това от пари, и добавяне на броя на монети всеки път. 

Друго решение, което ще видим, както аз я увеличите и отидете на Преглед на четири, имаше много сходни началото, но вместо това е използвало дивизия и Министерството на отбраната точно тук, за да се изчисли броят на цента. Това, на броя на тримесечията е равен на броя на разделени от 25 цента, и причината това работи е така, защото правим целочислено деление, така че се изхвърля остатъка. [Student] Трябва ли да коментирате търсене? Това наистина зависи. Студентски Вие коментира повече от код тук. Да, и така има един куп различни философии за това. Моята лична философия е, че кодът е наистина истината, като код е какво всъщност се изпълнява на компютъра, и така вашия код трябва да се чете като е възможно да не налагат най-много коментари. Това каза, когато правите неща, които са вид на сложен математически или алгоритмично, че е добре да се коментира, така че можете да добавите допълнително измерение, допълнителен слой на всеки, който чете кода си. В тези решения, често те са коментирани по-силно само защото искаме да бъдем в състояние да ги разпространява и има хора, които ги вземете и да ги четат доста лесно. Но определено, бих се съгласил, че това е тежък. [Student] Но когато се съмнявате, отидете по-тежки? Когато се съмнявате, отидете по-тежки. Някои хора ще казват понякога връщането на 0 или нещо подобно. Мисля, че е смешен коментар. Ясно е, че това, което се случва. Нямам нужда от английски, за да ми каже, че. Понякога хората ще пишат неща като "kthxbai!" Това е вид сладък, но също така не- , който не прави разлика между коментиране точки или не. Тези коментари са просто ха, ха. Cool. 

В този момент, нека да започнем да работим по проблема 3 раздел от въпроси. Ако вие го направим отново, с миналата седмица, ние не отиваме да гледате късометражни филми в този раздел. Ще оставим вие направите това по собствения си път и се говори за въпросите. Но сега в този раздел отиваме да прекарат малко повече време говорим за по-малко от кодиране основите както направихме миналата седмица, и вместо това, ние отиваме да се съсредоточи повече върху малко повече на теорията, така че говорим за двоично търсене и след това сортиране. От тези от вас, които са били заедно с лекцията, Може ли някой да ми даде една рекапитулация на каква е разликата между двоично търсене и линейни търсене? Какво става? - Разбира се. Линейни търсения чрез всеки елемент в сортиран списък един по един по един по един по един, двоично търсене разделя списък в две групи, Проверява дали стойността на клавишите, че търсите е по-голямо или по-малко от стойността на средата че просто намери, и ако това е по-малко, то върви с долната списък и после разделя отново, същата функция по целия път надолу, докато се намери средата, за да бъде равна на самата стойност. Точно така. 

Защо ни е грижа? Защо говорим за двоично търсене в сравнение с линейна търсене? Да. Binary е много по-бързо, така че ако удвои размера на проблема е необходимо още една стъпка, а не два пъти повече. Точно така. Това е чудесен отговор. Linear търсене е много проверка на един елемент в даден момент, и както видяхме още в първия ден на лекцията когато Дейвид премина през неговия пример телефонния указател и изтръгна една страница от телефонния указател в даден момент и това, че отново и отново и отново, , че ще му отнеме много дълго време, за да се намери някой в ​​телефонния указател, освен ако, разбира се, той е търсил някой в ​​самото начало на азбуката. С двоично търсене, можете да отидете много по-бързо, и това не е само два пъти по-бързо, или три пъти по-бързо или четири пъти по-бързо. Но проблемът става по-малък и по-малки и по-малки много по-бързо. За да се убедите в това, ние ще започнем да говорим за това какво става когато пишем двоично търсене. Проблемът на ръка е, че ако имам масив от числа, да речем, 1, 2, 3, 5, 7, 23, 45, 78, 12,323, и след това 9 с тон на 0s след него, искаме да бъдем в състояние да разбера наистина бързо, което е в този масив от числа. Знам, че това изглежда малко глупаво и малко измислен, защото точно сега. Имаме масив, който не разполага с много елементи в нея, и ако питам някой от вас да разбера дали или не 23 е в масива, можете да направите това доста бързо само като погледна и ми казва "да" или "не". Аналоговият е да се помисли, представете си, ако това беше, да речем, електронна таблица на Excel с 10 000 реда, 20 хиляди редове. Разбира се, можете да направите командата F или F и да потърсите нещо. Можете също да използвате филтри за търсене и неща, но ако трябваше да се търсят чрез този файл ред по ред по ред, това ще ви отнеме много време, за да го намерите. Това е нещо като в примера за телефонния указател, твърде, където никой не гледа през телефон Книга първа страница в даден момент. Обикновено те не го отворите в средата, или в случай на много телефонни книги и речници, където всъщност са го въвели В първото писмо, флип, че първото писмо и да се открие и да започне да минава през там. 

Напомни ми на името си отново. >> Сам. Сам. Като Сам каза, че линеен процес на търсене ще бъде много бавен, и вместо с двоично търсене, начина, по който това работи е, че всеки път, когато отидете чрез повторение на нашия алгоритъм на търсене, отиваме да се разделят списъка на половина, по същество, в две по-малки списъци. И тогава на следващата итерация на цикъла, ние ще го разделят отново в други по-малки списъци. Както можете да видите, проблемът продължава все по-малък и по-малък защото пазим изхвърля половината от списъка всеки един момент. Как става това изхвърлете работа? Просто като напомняне, това, което ние отиваме да направите, ако бяхме компютър и ние бяхме, да речем, търсене на числото 5 в този списък е, че ние ще вземем редица в средата. В средата на този списък, защото има 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 номера, щяхме да изберете номер или на 4 или на 5-та позиция, и ние ще се обади, че в средата на нашия списък. Трансфер номер в средата. Тогава, точно както каза Сам, ние ще тестваме да се види, ако този брой е равен номера, на който искате да получите или нашите желания номер. Ако е еднакъв, то ние сме го намерили. Ние печелим. Ако не е равен, след това има няколко случаи. Двата случая са или номерът трябва да бъде по-голям от броя търсим, или това е по-малко от. Ако тя е по-голяма, ние се движат в дясно. И ако това е по-малко, ние се движат наляво. И тогава ние повторите целия процес отново или дясната половина или лявата половина на списъка. 

Първият проблем в раздел днес е да разбера как всъщност можем да започне да изразя това в C код. Имаме pseudocode тук. Какво ще започнете да правите е, че ще дръпне един чисто ново пространство, освен това преразглеждане, така че имаме тези бележки за по-късно, ще изтриете всичко това, и след това да копирате и поставяте от проблема, тази информация в нашите пространства, и да се надяваме, че това не се е разпаднала. Perfect. Ако вие направите това, копирате и поставите този код в новия си пространство, в празен. Нека се опитаме Даниел. Ако вие компилирате и стартирате тази програма, не работят? No. >> Какво говориш? Той казва, контрол достигне края на нищожно функция. Да, така че нека се опитам да я пуснете. Сте виждали преди? Знаете ли какво означава това? Добре, нека да изясним това малко. Той казва в file.c на линия 9, колона 1 имаме грешка, точно както ти каза, и то се казва, че това е, произтичащи от грешка предупреждение и предупреждение за връщане тип. Тя изглежда като нещо, което се случва с типът на връщане, което има смисъл. Имаме нищожно функция, което означава, че имаме функция , който не се връща невалидни. Празнота функция е тази, която изглежда по този начин: невалидни Foo (), и това е нищожно, защото типът на връщане е невалиден, което означава, че ако имахме нещо тук като връщане 1, щяхме да се получи грешка за това. Въпреки това, ние имаме нищожно функция. Нашата нищожно функция в този случай е нашата функция за търсене , защото има връщане тип булев. Когато се казва, че контролът достигне края на нищожно функция, това е, защото търсенето не да правят изявление за връщане. Това не е връщане нищо от тип булев. 

Ние можем да поправим това, и какво вие мислите търсене трябва да се върне по подразбиране? Каква трябва да бъде на стойност по подразбиране за връщане на търсенето? Защото това е, което ние можем да поставим в края. Шарлот, имаш ли? Вярно или невярно? >> Вярно или невярно. Кой? False. Не знам. False? Нека да опитаме. Защо бихте казали връщане фалшиви? Това е голяма интуиция. Шарлот] Не знам. Отиваме да се върне фалшиви в този случай, защото това ще бъде нашето подразбиране ако по някаква причина списъкът е празен или иглата че търсим не съществува. След това, в самия край, ако ние не се връщат вярно по-рано в тази функция, ние винаги знаем, че тази функция ще кажа Не, това не е в масива. Това не е в купа сено. Сега, ако се съставя и го пуснете да ме спаси това, за да можем да го издърпайте нагоре. Сега, ако си компилирате и изпълнявате нашата програма, то се натрупва. Ще ни малко ред. Ако ми излезе 4-ъ-ъ-о. Не се отпечата нищо. Изглежда, че всичко свърши добре. Трябва да се запълни тази инча Ние говорихме за алгоритъм в pseudocode преди малко. Нека видим, освен това, и аз ще дръпнете, че алгоритъм обратно отново. Нека да удари този човек. Не. Това е то. Как да постигнем това? Каква би била една добра стратегия за започване на този код? Вие трябва да изберете номер в средата. Как да вземем редица в средата на масива? Някакви предложения? [Student] Strlen разделена на 2. Strlen разделена на 2. Това е страхотно. Strlen работи със специални видове масиви. Какви масиви? String масиви, характер масиви. Това е, че един и същи вид на концепцията, че ние искаме да се прилагат, но не можем да използваме strlen, защото ние нямаме за масив от знаци. Ние имаме масив от цели числа. Но какво означава strlen за нас? Знаете ли какво става за нас? [Student] Strlen ни получава дължина. Точно така, това ни получава дължина. Strlen получава дължината на масива за нас. 

Как да стигнем до тази в нашата програма за двоично търсене? Как ще получите дължината на масив? [Student] Strlen? Можете да получите дължината на правилно форматиран низ C масив с strlen. Проблемът, обаче е, че ние нямаме масив низ. Ако погледнем назад в този кодекс, имаме цяло число масив. Откъде знаем колко време е? [Student] Има ли еквивалент на една крайна точка, като Int л или нещо? Оказва се, че всъщност не е, и така в известен смисъл, това е едно от тези неща, които е добре да се знае за C, , че няма начин да се получи дължината на масива ако всичко ти дам е масив. Причината за това работи със струни, причината strlen работи, е така, защото, ако е правилно форматиран низ, това, че ще има специална \ 0 характер в самия край. 

Можете също така да си представите, ако имате неправилно форматиран низ и там не \ 0 характер, а след това цялото нещо не работи. [Student] Може ли да добавите \ 0? Бихме могли в този случай. Можем да добавим някаква \ 0 или някакъв вид показваше характер и след това да го използвате. Но това не е съвсем ще работи защото е знак тип \ 0, и тук имаме цели числа. Другото нещо е, ако бяхме да се използва специален стойност като -1, за да отбележат края на масива тогава ние никога не може да се съхранява -1 в нашите целочислени масиви. Бихме се залепи. Оказва се, че единственият начин да получите дължината на масив в C е всъщност да го помня когато сте задали и след това преминават около масива така че всеки път, когато имат функция, която ще да свърша някаква работа на масив от цели числа или салове или удвоява или какво ли, Аз също трябва да даде функцията дължината на масива, и това е точно това, което сме направили тук, в функцията за търсене. Ако погледнете, какво сме направили, когато преминем в нашия масив, ние също преминават в дължината, размера. Тя просто се случва, че ние нарекохме тази променлива, този параметър или аргумент. Това се нарича списъкът с аргументите на функцията или списък параметър, и те са също така наречени аргументи и параметри. Хората използват различни термини по различно време. Понякога ги себе си разменете. Просто така се случи, че тази променлива тук се нарича по същия начин тази # дефинирате до тук. Но те не са едно и също нещо. Капитализация е от значение. 

Ако погледнем какво се случва тук, ние заявяваме INT масив, който сме призовани номера. Съм го дал размера, който съответства на нашата # определят най-отгоре. Ще бъде 8. И тогава, когато ние след това се свържете с нашата функция за търсене по-долу, минаваме в числото, което ще искате да търсите, за които сме подканени, придобили от потребителя. Минаваме в масива, тези номера, и след това ние също трябва да премине в размер на масива, и след това се записва стойността на размер 8 или предава тази целочислена променлива наречена размер. Имаме размера на масива. Сега, ако се върнем към това, което се говори за по-рано, Мисля, Missy до точката, че това, което трябва да направим, е да получите дължината на масива и го разделете на две, и това ще ни даде средата. Да видим. Мога ли има някой, пиша това и да го запишете в тяхното пространство? Какво ще кажете за Лейла? Мога ли да ти пиша това? Напишете първия ред, където можете да вземете дължината на масива и да получите средата и да го съхранява в нова променлива. Ще ви дам няколко секунди. Готови ли сте? [Student чува] Разбира се, може да съм се изчисли средната точка на купа сено масив във вътрешността на функцията за търсене използвайки дължината на купа сено масив, който е размерът променлива? Нищо сложно тук. [Leila] Размерът / 2 и току-що И да го запишете, и натиснете бутона Save тук на върха, и ние ще го издърпайте нагоре. Perfect. Точно така. Страхотно. 

Както е, това ще компилирам? [Leila] Не, тя трябва да бъде по-висока. [Nate] Да, така, какво трябва да направим? [Leila като INT средата или нещо такова. Страхотно. Да, нека да го направим, вътр средата = размер. Това ще компилирам? Нека да изтриете този коментар и да го измъкнем от пътя. Това, което не ще се съставят за това? Ние не правим нищо с цяло число, така че ние трябва да го отпечатате или нещо подобно. Да, точно така. Ще получите неизползван променлива. Какво друго не ще да работи за това? Мисля, че каза нещо, Сам. Точка и запетая. Да, аз съм липсват тези точка и запетая. Тя ще бъде постоянно нещо по време на курса на срока. Последното нещо, което ще направя е Ще сложа някои празно пространство от двете страни на този оператор тук, тъй като това е обикновено как го правим според нашия стил на ръководство. Имаме средата на нашия масив. Сега, ако ние си спомняме обратно към нашия алгоритъм, това, което е втората стъпка, която ние трябваше да направим, след като имаме средата? [Студентски] Ако тя е по-голяма чува. Да, така трябва да направим някакво сравнение, и това, което се сравняват тук? Ти каза, че ако е по-голямо. Какво е това в това изречение, отнасящи се до? Броят, който идва, ако това е по-голяма от средната точка, след това отидете до масива? Точно така, така че броят, който идва, когато ние Игла, така че ние сме в сравнение с иглата, и какво се сравняват срещу иглата? Тъй като иглата е това, което търсим. Ние сме в сравнение с стигнем до средната точка. 

Но има ли смисъл да се провери, за да видите ако игла = средата? Това прави ли смисъл? Дали някой не? Нека да го пробвам, ако (игла == средата). [Student] ФОРМАТ го намери. [Nate] ФОРМАТ ("Открихме го \ N"); В противен случай съм да започнем да правим нещо по-различно тук. Отивам да започне поставянето на скоби наоколо, ако отчети през цялото време просто защото, ако ние добавяме повече неща, а след това ние не се съставителите. Да, Сам. Имаш една точка. Проблемът е, че средата представлява позиция в масива, но можете да получите да представляват стойността в това положение на масива. Това е страхотна точка. Знаете всички чуя какво каза Сам? Той каза, че средата е представлява само една позиция в масива, но това не е действителната елемент в масива. Ако смятате, че за код, както е написано точно сега, ако се вгледаме в този масив, който има осем елементи в нея, каква е стойността на средата ще бъде в тази функция? Student [4]. [Nate] 4. Ако търсим номер 4 - и ние можем само да изпълните този код и сложи малко тъжно лице тук , защото не можахме да намерим - ако ни свърши този код както е сега, да го качите, изграждане, позволете ми да превъртите надолу, и ако търсим номер 4, ние го намерихме, но ние не се получи това, за да ФОРМАТ да. Една от причините е, че ние не се върне вярно, но ние наистина номер 4? И Сам казва не. Какво открихте? Ние наистина се намери средата, която ако се вгледаме в масива тук, ще бъде елемент при индекс 4, че ние не търсим на , което е 23. 

Как да се получи в действителност този елемент в средата а не само на средата? [Student] ще влезе Чар или нещо? Какво ще направите, просто от любопитство? Мога ли казали малко повече? Трябва да се трансформира позиция в брой, така че трябва да се направи някаква връзка мисля, че е Чар, но тя не може да бъде. Да, това е добра отправна точка. Ние сме били прави много на този конвертиращия позиции в символа, тези символи, през първите две проблемни комплекти. Оказва се, че тук, това е почти подобен на достъп до ItH знак в низ, ако това има смисъл. Тук искаме за достъп до елемент на средата. Как да го направим? Кевин, имате ли някакви предложения как бихме могли да направим, че? Можете да направите купа сено, отворена скоба, по средата, затворена скоба. Можеш ли да напишеш, че за нас? Запишете го тук, и ние ще се дръпне, че до. Търсим по тази линия 9, и ние сме осъзнавайки, че ние не искаме да се сравни иглата на средата, но вместо това, ние искаме да се сравни иглата за елемент на позиция средата в рамките на нашата купа сено масив. Cool. Точно така. Да, това изглежда доста добре, ако (игла == купа сено средата). Ние го намерихме. Сега, ако бягаме код ние ще резервен малко съставя, той работи и сега, ако ние с нетърпение за 4 ние не го намери, защото сега сме всъщност да е номер 23. Ние сме получаване на стойност 23, и това е, което ние сме в сравнение с нашата игла. Но това е добре. Това е стъпка в правилната посока. 

Това е, което ние се опитваме да направим. Ние не се опитваме да се сравни игла срещу позиции в масива , а по-скоро срещу действителните елементи в масива. Ако се върнем отново в следващата стъпка в нашия алгоритъм, каква е следващата стъпка? Лейла вече го споменах за кратко. [Student], за да видите, ако това е по-голямо или по-малко и тогава да реши по какъв начин да се движат. [Nate] Да, така че как ще правим това? Може ли да поставите в някои Ще спаси тази ревизия, и тогава, ако в някои линии, които ще направите това. Да, Шарлот. >> Аз имам един въпрос. Ако не е средата - 1, защото първото нещо, което е е 0 индексирани, така че ако сложим 4, това не е всъщност характер търсим? Да, и друг проблем с това е че е страхотен улов, защото какво ще се случва вероятно ако ние продължим да се движим и ние никога не коригира първоначално? Предполагам, че това, което може да свърши това се опитва да получи достъп елемента в 8-ма позиция на масива, което в този случай не съществува. Ние ще искате да направите някаква на отчитане на факта, че имаме някои нула индексиране. Шарлот За съжаление, имах предвид средната точка - 1 в квадратните скоби. Ние можем да направим това. Ще се върнем на този въпрос само за малко. След като започнете да стигнем до действителната примка, това е, когато ние наистина ще видите това влезе в игра. За момента можем да направим това, но вие сте напълно прав. Това нула индексирането ще имат ефект, който ние трябва да се отчита. Да видим. 

Как е по-голяма от по-малко от? [Student] се как да се направи по-голяма от и по-малко, отколкото част. Просто не бях сигурен какво да отпечатате, ако откриете, че тя е по-от купа сено средата или по-голяма от. Тук мога да спася това, което I've- [Nate] Да, ако освен това, което имаш, и ние ще го издърпайте нагоре. Точно така. Студентски] И аз въпросителни знаци за това, което аз не знаех. [Nate] Това изглежда страхотно. Тук имаме въпросителни знаци, защото ние все още не знаем какво ще да направи доста още. Какво бихме искали да направи Опа, ние имаме някои скоби фънки върху нас. Ние ще коригира тези скоби. Точно така. И така, какво искаме да направим, според нашия алгоритъм, ако ние не намерим иглата? Кажете в случай, че иглата е по-малко от това, което търсим в. Кевин. Само погледнете в лявата половина. Добре, така че ние ще сложи коментар тук, който казва: "погледнете в лявата половина." И ако иглата е по-голяма от купа сено в средата, какво искаме да направим? [Student] Тогава търсите в дясната половина. Погледнете в дясната половина ", в дясната половина." Не е твърде занемарено. Добре, така че в този момент, нещата са доста добре. Проблемът с кода, както е написано, е какво? Студентски] не са крайни точки за двете половини. Точно така, ние нямаме крайни точки за двете половини. Ние също така само ще да мине през този път. Ние само ще изглежда в един средата. Или елемент е там, или не е така. За да се завърши това, ние ще трябва да направите някакво повторение. Трябва да продължим да повтарят, докато не открием, че или елемент е там, защото сме свива и най-накрая го намерих, или не там, защото сме погледна през всички неща, в съответните половинки на масива и е установено, че нищо не е там. 

Когато имаме това повторение става, какво ще да се използва? Студентски] контур. Някакъв вид на линията. Да. [Student] Може ли да се направи направи линия, докато и да го направи това и след това, докато иглата не не е равно съм сигурен къде отивам с това. Но нещо като, че толкова дълго, тъй като не е равно на стойността, която приноса на потребителите. Да, така че нека видим, как това може да се пишат? Ти каза, че нека използваме направи линия, докато. Къде трябва да започнете? [Student] Веднага след размера / 2. [Nate] Добре, и какво ще правим? Ние ще попълним, докато по-късно. Какво ще правим сега? [Student] Не искаме да направим всички неща, които имаме, ако част? [Nate] направи всички тези неща, чудесно. Копиране и поставяне. О, човече. Да видим дали това работи, ако можем раздела това отново. Beautiful. Добре, и освен това, така че вие ​​го. Добре, а ние ще направим това, докато- какво е състояние, докато сте били след? Студентски] Докато иглата не е равно, така че като удивителен знак. Но аз не съм сигурен точно какво е това все още. [Nate] Да, това е един от начините да го направя. Сам, имате ли коментар? [Сам си спомних, когато гледах клипове, Взех една снимка на един на подобно, когато направихме pseudocode за него, имаше някаква връзка между максимална и минимална. Мисля, че беше нещо подобно ако максимумът е все по-малко, отколкото мин. Ясно. [Сам или подобни, ако Макс не е по-малко от мин. или нещо подобно, защото това би означавало, че сте търсили всичко. 

Да, така че това, което се звучи като максимум и минимум, отнасящи се до? [Сам] Стойности, които числа, които ще се променят в сравнение с където поставяме на средата. Точно така. [Сам В този момент, тя ще [се чува изчисляване на макс и мин. Midpoint това е макс и идеята мин. Това прави ли смисъл хора? Ако бяхме да започнем да гледаме как ние ще направим тази итерация, сте напълно прав, че ние искаме да използваме някакъв направи линия, докато. Но предполагам, че ако си припомним какво се случва на мястото на този масив и какво всъщност се случва Тръгвам да пиша тук в първата итерация на двоично търсене, имаме Отивам да използвате Б и Д за да се обозначи началото. И след края на нашия масив. Ние знаем, че началото е в четири право тук, и ние знаем, че краят е 108. Кажем, че сме за номер 15. Първи път правим това, както видяхме по-рано, средата или ще бъде 16 или 23 в зависимост от това как ще се изчисли нещата. Тъй като равномерно се раздели в средата ще ни даде това място между 16 и 23, ние не може равномерно, тя се разделя или да го разделите и получите в истински средата. Ние ще разгледаме 16. Ще осъзнаете, "Хей, 16> 15 търсим." За след това погледнете в лявата половина на масива какво ще свърши това е изхвърлянето тази цялата горна част и каза: "Добре, сега нашата крайна точка ще бъде тук." Следващата итерация на нашата линия, ние сме вече в този масив, ефективно изхвърли тази част, защото сега ако ние сме като средната точка да бъде разликата между началото и края, ние намираме нашата средата да бъде 8, тогава ще можем да тествате 8, за да видите къде е по отношение на броя търсим, 15, ще разберете, че 15 е по-голяма, така че ние трябва да се премести в дясната част на списъка, което знаем, защото ние сме хора и можем да го видим. Ние знаем, че дясната част ще бъде, когато го намерим, но компютърът не знае това, така че това, което ние ще направим, е, че ние действително ще са това, и сега в началото и края са на същото място, така че средата става само номер в списъка, в този момент, което е с 15, а ние сме го намерили. Ли това, че хвърли малко повече светлина върху това, когато цялата тази макс и обозначения мин. ще следене на крайните точки на масива, за да разбера как да се стесни нещата? 

Какво би се случило, ако това не е равно на 15? Какво ще стане, ако търсим за 15, а вместо това, тази цифра също бяха 16? Бихме казали: "О, това е по-голяма. Ние искаме да се върнем в ляво ". И ние бихме се движи нашата надясно, в който момент имаме крайна точка, това би било противоречива. Тя не би могла да се търси повече елементи защото сега имаме нашата крайна точка и точка началото нашата макс и мин, сега се обърна. Ние търсим през целия масив. Не можем да намерим нищо. Това е точката, в която ние бихме искам да кажа: "Добре, отиваме да се спре този алгоритъм. Не намерихме нищо. Знаем, че не е тук. " Как ще? [Student] Как точно компютъра да превключите в края? Как края преди началото? Края завършва преди началото на поради по математика, че ние ще направим всеки път, когато правим това. Начинът, по който суап е, ако се вгледате в първи път правим това суап където имаме началото на 4 и в края по целия път надолу към 108 и средата, да речем, на 16 - Отивам да се върнете обратно към 15-ако ние не търсим за 15, ние знаехме, че това, което направихме, когато ние проверихме 16 и видях, че тя е по-голяма и искаше да изхвърли цялата дясна част на списъка, видяхме, че това, което искахме да направим е да преместите тази електронна тук. Ефективно, електронна започна да се преди средата. По същия начин, когато ние направихме тази итерация на алгоритъма и средната точка е на 8, ние открихме, че 8 <15, така че ние искахме да се движат б един миналото средата. Сега, в началото и края са и двете заедно в този 15. 

Ако бяхме се случва да се търси някаква друга стойност, а не 15, или, ако това 15 вместо 16, щяхме да установи, че д искаме да се движи един преди средата. Сега д ще бъде там обърна по-малко от б. Нека разгледаме как всъщност стигаме до кодиране този алгоритъм. Ние знаем, че искаме да имаме това изчисление средата. Знаем също, че искаме да следите в началото и края на масива на текущата масив, за да можем да разберем когато това лявата половина на списъка е и когато дясната половина на списъка. Ние правим това с начало и край, или можем да ги наречем мин. и макс. Ще започне и да завърши този път. Когато започнем, ако погледнем назад към нашия пример тук, нашата Началото бе поставено в самото начало на масива, като естествена. Какво индекс е това? Какво трябва да ни започне да се? Даниел. Даниел] Haystack [0]. [Nate] Да, така бихме могли да го настроите равна на купа сено [0]. Проблемът, обаче, е, че това дава не ни позицията на първия елемент. Това ни дава индекса на първия елемент или действителната стойност в тази първа позиция. [Student] Това ще се превърнат в 0.20? [Nate] Какво ще направите, е добре, че няма да направи никакво конвертиране. Това, което ще направим, е, че ще съхранява 4 започне, и след това ще бъде трудно да се правят сравнения срещу започне защото започваме ще се проведе на стойност от 4 който е началото на нашата масив, но ние искаме да следите индексите в масива за разлика от стойностите. Ние всъщност ще се използва 0, нещо такова. За края на масива-Charlotte доведе до малко по-рано. Това е мястото, където ще се вземе предвид нула индексиране. 

Шарлот, какъв е края на масива? Какъв е индексът на края? Шарлот] Размер - 1. Да, и кой размер трябва да се използват? Трябва да използваме капитала размера или малки размери? Капитал размер. В този случай, можем да използваме размера на капитала. Ако искахме тази функция, за да бъдат преносими и използвате тази функция в други програми, ние всъщност може да използвате малки размер. Всичко е наред. Но Шарлот е напълно прав, че искаме да имаме размер - 1. В този момент- [Student] Как е, че можете да използвате главни размер? Как е, че бихме могли да използваме главна размер? Оказва се, че тези # определя наистина, под капака, текст, като намери и замени, ако това има смисъл. Когато вие компилирате кода си, предварителна обработка фаза на компилатора отива във файла, и да го търси навсякъде, където сте написали капитал размер, и го заменя този текст буквално с 8, просто ей така. В този смисъл, това е много по-различен от променлива. Не заемат място в паметта. Това е един прост трик за подмяна на текст. В този случай, ние ще използваме размер. От тук искам да правя някакво повторение, и ние сме на прав път с нашата направи линия, докато Искаме да направим нещо, докато състояние не притежава повече, и както видяхме по-рано, видяхме, че това условие наистина е, че ние не искаме в края да бъде по-малко от началото. 

Това е ни спиране състояние. Ако това се случи, ние искаме да се спре и да се декларира като: "Хей, не сме намерили нищо." За да изрази това, ние искаме да използва някакъв вид на линия. В този случай, ще го направи линия, докато, цикъл, цикъл, докато? Имаме направи линия, докато тук. Мислите ли, хора като този подход? Мислите ли, че трябва да се опитаме различен подход? Кевин, някакви мисли? Бихме могли да имат цикъл, докато, защото знаем, максимум ще бъде по-голяма от мин. В началото все пак. Да, така че не е инициализация, че трябва да се случи. Тези направи докато вериги са страхотни, когато трябва да се инициализира нещо преди това тестване, докато тук ние знаем, че ние няма да запази reinitializing както започват и завършват всеки кръг от веригата. Ние знаем, че искаме да ги инициализира, тогава вижте нашето състояние. В този случай, аз ще отида с един прост цикъл, докато. Оказва се, че направи, докато се използват затворени контури доста рядко. На много места, дори не се научи да докато цикли. Те са добри за работа с приноса на потребителите, така че съм виждал много от тях до този момент. Но нормално и вериги са много по-често. Оказва се, че това състояние, както е записано не наистина ще ни направи много добре, и защо е така? Съжалявам, аз не знам името ти. Аз съм Джери. >> Съжаляваме? Това е B-O-R-U-I. О, добре. Не виждаш ли в моя списък. О, това е, защото-о, това има смисъл. Имате ли представа защо този цикъл, докато не може да работи, както е предвидено, както е написано с условието? [Джери] Искаш да кажеш, че искаш всички неща, след това в най-? Да, така че това е един. Може би трябва да постави всички тези неща в линия, докато, което е напълно вярно. Другото нещо, което е малко по-проблематично, обаче, е, че това условие не работи. [Student] Трябва да го обърнете. Надясно, така че това условие не никога няма да бъде вярно първоначално начина, по който ние говорихме за това. Искаме да направим нещо до края на <започне, но искаме да направим нещо, докато да започне ≤ края. 

Е, че обратното на логиката. Аз съм виновен за извършването на тези грешки през цялото време. Студентски Защо това трябва да бъде по-малка или равна на? Защото помните ли случай, че ние трябва да се където имаше само един елемент, и ние бяхме, и ние търсехме точно в 15 в нашия масив? И нашият началото и краят ни бяха на един и същ елемент. Ние искаме да сме сигурни, че ние се справят с този случай. Ако ние направихме направо по-малко от ние само ще бъде в състояние да стигнете до 2-елемент на масива. След като слезе на последния елемент, ако това беше нашата елемент, ние никога няма да го намерите. Сега тук, можем да направим точно като теб казваха. Можем да започнем цопване неща точно в средата на нашата линия, докато. Ние можем да цоп в нашия средата. Ние можем да вземем всички от тях, ако отчети, да ги измъкне от това направи линия, докато, цоп в тях почистване нещата малко, а аз ще отида напред и спести тази ревизия. И в този момент, ние сме доста близо. Сам. Аз мисля, че също трябва да имат INT средата = размер - 1/2. Взех го, размер - 1/2. Има ли нещо друго, което трябва да се промени за тази реплика? Това беше добър улов. 

Какво означава размер направя? Ние непрекъснато променящите се размер? За да се запази линията по този начин, ние трябва да промените размера. Ние трябва да промените размера всеки път, когато обикалят за цикъл. Но не забравяйте, когато бяхме става чрез нашия пример само малко по-рано, и имахме началото на 4 и края начина, по който в продължение на 108? Как да се изчисли средната точка? Ние използваме размер? Или сме използвали започне и да свърши вместо? Това е разликата между края и началото. Точно така, и как точно трябва да пиша, че Шарлот? Само крайните започне. Може би не трябва да направите - 1 защото 1 е включен в края и началото вече. [Nate] Great, вие сте напълно прав. Ние не трябва да направите - 1, защото това един е включен и да се отчита, когато се инициализира променлива края. 

Има ли нещо друго, което трябва да направите, синтактично да има тази линия да има смисъл? [Студентски] Plus започне. >> Plus започнем? [Student] В края. Тъй като се изчислява само на половината от дължината. Вие трябва да добавите началото. [Nate] Какво ще се изчисли за нас? Ако мислим за края на тази първа итерация на цикъла, края ще бъде в състояние индекс 7. Започнете да е в позиция 0. Не забравяйте, че ние не търсим или позиция 3 или позиция 4. Ако погледнем на този по математика, просто за да бъде малко по-осезаема, постави някои цифри тук имаме 7, 0, така 7 - 0, и след това / 2 е 3 целочислено деление. Тогава ще се наложи след това да добавите обратно започне? Ние не правим в този случай. На първата итерация, ще бъде добре, защото започнете е 0. Но докато напредваме, ние правим наистина всичко, просто трябва края Начало / 2. Има един друг трик тук, и това е именно една от предимство. [Student] Имаме ли нужда от скоби? [Nate] Точно така, и това е така, защото ако ние не използваме тези скоби, тогава тази линия ще се тълкува вместо (край) - (начало / 2), която определено не искам. Внимавай за тези правила за предимство. [Student] Защо не е края + започнем? Защо не е края + започнем? [Student] Защо да не е? Защо да е +? Мисля, че си прав. [Student] Защото това е средно? [Nate] End + започне, вие сте напълно прав. Уау, аз напълно goofed. Прав си. Ако правим минус, ние ще искате да добавите започне отново. В този случай, вие сте много прав, че ние искаме да се средната стойност на двете, така че ние искаме да ги добавите, за разлика от тях се изважда. [Student] Тя също така ще работи, ако свърши - започва / 2 + започне. Би било, ако правим така мисля. 

Например, ако търсим най започне, и ние го премести тук до 15. Сега започнете е на позиция 2. Енд е на позиция 7. Ако успеем да ги изваждате, ще получите 5. Разделете на две, ще получите 2. И след това се прибавят 2 обратно, и това ни получава на 4-то място, което е точно тук, което е средата. [Student] Трябва ли да се грижи за опаковане? В какъв смисъл трябва да се грижи за опаковане? Ако сумата или разликата между в зависимост от това как го правим не е четно число. След това компютърът се обърква дали, когато е 2,5; да се движите на ляво или на правото да се определи коя е средата? Ясно. Оказва се, че с целочислено деление, ние никога не получите тези числа с плаваща запетая. Ние никога няма да получите знак след десетичната запетая. Напълно изхвърли. Ако имате компютър разделя две INT променливи, и един е 7, а другата е 2, вие няма да получите 3.5 като резултат. Тя ще получат 3. Останалата част ще бъде изхвърлен, така че е ефективно закръгляне не е кръгла, а по-скоро етаж, ако вие сте запознати с тази по математика, , където можете напълно да изхвърли знак след десетичната запетая, и така сте по същество тя съкращаване до най-близкото цялата позиция, до най-близкото цяло число. [Student Но след това, че е проблематично, защото, ако имате масив от 7 елемента това автоматично прави 3-ти елемент на средата вместо на 4-ти. Как да се справим с това? Това е проблематично, тъй като, ако имахме масив от 7 , че ще вземете 3-та вместо на 4-та. Бихте ли обяснили малко повече? [Студентски] Защото, ако има седем елементи и след това на 4-ти елемент ще бъде средата, нали? Спомни си коментар за е нулева индексира. [Студентски Да, така в позиция 3. Това би било средата. Да. О, добре. Виждам, какво искаш да кажеш. Това е доста странно, тъй като ние свикне с това цялата идея за да се отървете от знака след десетичната запетая. Това е страхотна точка. Да приключваме нещата. Изчислили сме, средата ни. 

В момента тестваме за да видите дали нашата иглата е равна на средната стойност. Ние сме печат, че ние го намерихме, но наистина, какво искаме да направим в тази ситуация? Сме го намерили, така че ние искаме да позволи на повикващия знаят, че ние го намерихме. Имаме функция, която е булев въвели функция. Начинът, по който сигнализира на обаждащия се на нашата функция, че ние сме готови да отидете ние казваме: "Хей, това е вярно." Как ще го направим, Кевин? Вие кимна главата си. >> Кевин] Добави връщане вярно. [Nate] Точно така, върнете вярно. Сега, ако това не е равен, как ще търсим в лявата половина? Някакви идеи? Стела, някакви идеи? Трябва да се създаде нова позиция за края. Да. Така че ние трябва да направим позицията на средата - края. Велики. Трябва да зададете нова позиция за края да погледнете в лявата половина. Това е това, което говорихме преди, когато Продължавам да се връщам на този пример. Имам започват от тук, а след това имам до края целия път тук. 

Отново, ако търсим 15 и средата ни е на 16, и ние осъзнаваме, "Oops, 16 е по-голяма. Искаме да се премести в лявата половина. " Ние тогава ще се движат в края на 15, и ние го правим от един от средата и настройка, че като нова нашия край. По същия начин, ако искаме да изглеждаме в дясната половина, как ще правим това? Имате ли някаква идея? [Student] Трябва само да зададете започне до средата + 1. [Nate] Велики. И сега, в случай, че не намери нищо, това да се грижи за нас? Даниел, не че да се грижи за нас? Даниел] Не [Nate] Ако го направят чрез целия масив и ние не откриваме нищо, къде ще се вземат грижи, или трябва да се грижи за него? Даниел] а състояние. [Nate] Да, а състояние, точно така. Тя ще се грижи през целия масив, ако ние не откриваме нищо. Този цикъл, докато ще приключи. Ние никога няма да са се натъкнали на това условие, и можем да се върнем фалшива. Можем също така да оставите това, ако тук по този начин защото ако това, ако твърдение е вярно, а функцията ще се върне и така ние ще същество прекратите тази функция в този момент когато се върнем вярно. Но какво се случва с тази структура? Това ще работи изцяло, или има някаква логическа недостатък там? 

Има някои логически недостатък там, с начина, по който тя е създадена. Какво би могло да бъде? [Student] Защо ви е необходимо - и + 1s? Това определя нашата масив да бъде нашият нов лявата половина и дясната половина. [Student] Но защо не можа да го направиш без - 1s и + 1s? [Nate] Бихме могли да я определя като равна на средната точка? Какво може да бъде проблематично за това? [Студентски] Предполагам, че е неефективен, защото сте проверка стойност, която вече е била проверена. [Nate] Точно така, така че Сам е напълно прав. Ако зададете края и започват равна на средната точка вместо на 1 и + 1 замислено, в някакъв момент в бъдеще ще се окажете отново проверка на средата. [Student започнах pset, а след това имах нещо подобно Забравих + 1, и се заби в безкраен цикъл. Точно така, защото в един момент никога не започваш да се започне и да свърши действително да се припокриват. Cool. Има един по-логично недостатък и това е, че това определено трябва да бъде на друго, ако. Каква може да е причината за това? 

Причината е, ако това не е друго, ако видя, Кевин? [Кевин Да, защото си променя крайната точка. [Nate] Точно така. Ние сме променят крайната точка, и ако е написана така Ще пространства между- той ще провери този случай. Този случай, ако успее, ще се откажем от функцията. След това ще провери следващия случай, и ако това успее, тя ще коригира крайната точка, и след това ще продължи и проверете този случай. Но в този момент, ние не искате да продължите проверката. За щастие, ние не сме нулиране на средата, и ние знаем, че този случай няма да успее. Но ние определено искаме да се постави друг, ако там въпреки че мощ в този случай тъй като ние не сме за адаптиране на средата, че ще направи разликата? Не, защото тези случаи са изключителни. Отново ми е зле. Не, мисля, че се нуждаят от този друг, ако. Ние можем да го пробвам и да го стартирате и да видим какво ще се случи. Сграда, но е станала грешка. Това е може би, защото съм оставил тези б и д тук. Трябва ли повече от тези на на върха? Това не изглежда като него. Отдалечаване, изграждане, там тя отива, така че сега, ако търсим за 15, Да. Нека я увеличите инча 15, да. Ние можем да се кандидатира отново. Качване на изходния код, изграждане, работи. Можем да търсим нещо като 13, и ние не получите нищо печат, така че не е намирането на това за нас. Това е страхотно, защото това не е в нашия списък. 

Ние сме сега от време. Това ще бъде за тази седмица. Благодаря за присъединяване, и ще се видим по-късно. 

[CS50.TV]