>> Джейсон Хіршхорна: Ласкаво просимо на тиждень три, все.
У нас є зайнятий, але цікаво Розділ попереду нас.
Отже, спочатку, тому що ми зробили деякі Headway з курсу, але ми як і раніше
вже багато навчання залишилося зробити, я збираюся показати вам, хлопці деякі ресурси
що повинно виявитися неймовірно корисними, як ви не тільки наблизитися до свого
Проблема встановлює, але і переварити всі матеріал ми даємо вам хлопці в
лекції та шорти і розділ.
>> Тоді ми збираємося провести першу 20 25 хвилин розділі переходячи
GDB, які ви можете мати або не мати використаний на цій стадії, але це
неймовірно корисний інструмент, який буде допомогти вам налагодження програм.
Багато хто з вас, можливо, використовували Printf в середина вашої програми, щоб з'ясувати
, Що змінна рівних.
GDB навіть краще, ніж Printf і не зіпсувати свій код, тому що вам
запустити його на виконуваний файл.
Таким чином, ми пройдемося по 10 найкориснішим команди, що потрібно для GDB, і ми
йдете на вправи разом так в задачі встановити три і за його межами, ви
можна використовувати GDB для налагодження ваші програми.
І, нарешті, ми збираємося перейти на деякі сортування і пошуку алгоритмів
що ви бачили в лекції, і ми збирається насправді код, а не тільки
псевдокод, але код бінарний пошук, бульбашкового сортування, і вибір роду.
>> Отже, спочатку я хочу піти над ресурсами.
Це великий список, і це менше шрифту, тому що я мав безпосереднє відношення до
поміститися на тут.
Але це не тільки допоможе вам, знову ж, з проблемних наборів і
перетравлення інформації ви дізналися, але виразно, прийшов час вікторини, вони будуть
бути неймовірно корисними.
Отже, спочатку лекція зазначає.
Якщо ви йдете в cs50.net/lectures і перейдіть до конкретної тижня і дня,
ви побачите, що є записи для кожного лекції, яка є не просто
стенограма, але відредагована версія , Що було покрито в лекції з кодом
фрагменти і інші корисні ласі шматочки.
Я дуже рекомендую рух над тими.
І те, як добре, що є вихідний код наявних у кожної лекції.
І знову ж, ці гірки будуть також можна ознайомитися на сайті cs50.net/sections
в цей вечір.
>> Так другий є шорти щотижня, що кришка теми, як правило, від 5 до 15
хвилин у довжину.
А ті, сподіваюся, дасть вам відмінний підручник з різних тем.
По-третє -
і це є новим у цьому рік - це study.cs50.net.
Якщо ви ще не перевірили його, я настійно рекомендуємо вам зробити це.
Ви добираєтеся, щоб вибрати тему.
У нас є десятки питань там.
Так, наприклад, ви вибираєте функції.
Це дає вам кілька слайдів і зазначає на функціях.
Ті, насправді слайди, що ТФ рекомендується використовувати під час нашого
презентації в розділі.
Там також поради та рекомендації щодо роботи з функціями, і є
проблеми практики, які допомагають Ви працюєте з функцій.
Ми також даємо вам посилання на мало Функції і час, що функції
придумали в лекції.
Так study.cs50.net, новий це рік, фантастичний ресурс.
>> Далі, у мене є людина, яка є керівництво Команда, що ви можете працювати на
командного рядка.
Так що якщо у вас є які-небудь питання про Команда, наприклад, рандів, які ми
зіткнувся минулого тижня під розділі і ви, швидше за все зустрічаються в
ваша проблема встановити, проходячи генерувати код, але якщо ви введете чоловіка
рандів, ви отримаєте сторінку, розповідає вам все про рандів.
Це дає вам те, що потрібно, параметри він приймає, а також про доходи
Тип і короткий опис цієї функції.
>> Так перевірте рандів.
Це може бути трохи багатослівним і заплутаним, так що іноді я вважаю, що
просто погуглити, що я хочу знати, кращий спосіб, щоб знайти відповідь.
Так практиці з Google.
Отримати добре Google.
Він стане вашим найкращим другом.
>> А також Google, якщо ви не можете знайти його на Google, cs50.net/discuss, це
форум.
Швидше за все, якщо у вас є запитання, один з ваших 700 + однолітками також має, що
питання і, можливо, попросив це вже в обговорити
форумів і він відповів.
Так що якщо у вас є спільні питання або у вас є питання, що ви думаєте
може бути, інші люди, можливо, зіткнетеся з, перевірити cs50.net/discuss.
>> Нарешті, останні два, якщо ви хочете поговорити з реальною людиною, офісу
години з понеділка по п'ятницю.
Там також онлайн години роботи для студентів розширення.
І останнє, але, звичайно, не в останню чергу, мені, знак оклику.
У всіх вас є мою контактну інформацію.
НЕ Якщо вам потрібно що-небудь, будь ласка, ніколи соромтеся звертатися до мене.
Завжди не соромтеся робити це.
Дуже мало хто з вас, які додали мене на Gchat, так що викликає розчарування,
але, сподіваюся, це зміниться між в цьому і наступному розділі.
Будь-які питання досі на ресурси?
Великий.
>> Нарешті, ще один роз'єм для зворотний зв'язок, sayat.me/cs50.
Ви можете дати мені анонімний зворотного зв'язку про те, як я роблю.
Це було дійсно корисним минулого тижня.
Я отримав кілька зауважень від вас, хлопці відразу після розділу, плюс від
інші студенти, які дивилися його протягом тижня, і це
був неймовірно попереджувальний.
Я збираюся спробувати обмежити моє використання слово "солодкий", але я покажу мій
ентузіазм і хвилювання в інших відносинах.
Але були й інші додаткові основні результати впливу,
як плюси, так і дельта.
Тому, будь ласка, я даю ви, хлопці, зворотній зв'язок на ваших проблемних множин.
Не соромтеся, щоб дати мені зворотний зв'язок на моєму вченні.
Я тут для вас, хлопці.
>> Великий.
Це все, що у мене є для Перший розділ.
Хто-небудь є будь-яка питання досі?
І у мене є до відома для центр управління.
Студенти розширення вже Messaged мене кажучи що вони не отримують ніякого аудіо,
але це з моїх силах, щоб виправити.
Так, ми сподіваємося, що отримує вирішене найближчим часом.
Якщо ви дивитеся онлайн, привіт, але ви не можете почути мене.
>> Отже, спочатку ми збираємося пройти через GDB.
GDB, як я натякнув на раніше, є інструментом налагодження
набагато краще, ніж Printf.
Таким чином, щоб почати роботу з GDB, ви, хлопці, якщо Ви хочете відкрити свій прилад
і прийняти файл, який я послав по електронній пошті до вас раніше - цей файл буде також
доступні в Інтернеті в небагато -
і запустити GDB. / ім'я файлу.
Перш за все, звичайно, у вас є для компіляції подати, тому що GDB працює тільки на
виконувані файли.
>> Але якщо ви хочете, щоб почати GDB, перше, що ви робите,
запуску GDB. / Цезар.
Так ось назва програми ми знаходимося збирається піти з ним прямо зараз.
Так що я збираюся писати зробити Цезаря, який дасть мені виконуваний файл
тут виділені зеленим кольором.
А потім я збираюся запустити GDB. / Cesar.
>> І там ви йдете.
Ви бачите у нас є деякий текст розповідав мені про версії GDB, даючи мені
деякі відомості про гарантії, і тоді ми є запрошення ВВП, який виглядає начебто
зразок нашої командного рядка рядку але ви бачите, що це відкрито
Хлопець, GDB, поруч дужка.
Перш ніж ми продовжимо й налагодження цей файл що я посилав до вас усіх, давайте подивимося на
деякі корисні команди так у нас є почуття того, що ми збираємося розповісти.
>> Ці команди перераховані тут в Порядок, в якому я зазвичай використовують їх.
Так що я почала мою програму, запустивши ГПБ. / Ім'я програми,
в цьому випадку, Цезар.
І то перше, що я роблю 99,9% частину часу типу брейк маю на увазі.
Це встановлює точку зупину на основний.
По суті, те, що ви робите там є програма збирається зупинятися на
Основним так що ви можете приступити до вивчення його лінію за рядком, а не працює все
шлях до кінця.
Ви можете розбити в різних точках ваш код, але головним, як правило,
гарне місце для початку.
>> Наступна команда запуску запускається.
Це починається програму запущеною, і якщо вам потрібно ввести командний рядок
аргументи, ви запустите його таким команду.
Запуск з аргументами.
Так, оскільки ми збираємося за версію з С, що програма ви, хлопці,
написав для PSet два -
цей, звичайно, має деякі помилки в ньому, що, сподіваюся, ми знайдемо -
ми збираємося запустити запустити з деякою команди аргументи командного рядка, тому що Цезар,
як ви, хлопці, знаєте, за проблеми встановити специфікацію, займає деякий
аргументи командного рядка.
>> Наступна пара команд, наступний один насправді називається наступна.
Це один забере у вас рядок за рядком через вашу програму.
Так удару п, то введіть відніме у вас на наступний рядок, виконання
попередня рядок.
Крок приймає вас не тільки Наступний рядок, але це
відніме у вас всередині функції.
Так що якщо ви написали функцію в ваш код або якщо ви хочете, щоб дослідити
щоб я, наприклад, ви можете натиснути с, а замість того, щоб наступному рядку
файл, який ви збираєтеся через право Тепер, ви дійсно будете крок у
ця функція і подивитися свій код.
>> Список показує вам, в дуже зручною для користувачів формат, 10 або близько того лінії навколо
де ви в даний час в коді так що ви можете побачити файл
замість того, щоб поміняти назад і вперед між різними видами.
Друк, як Printf, як випливає з назви.
Це показує те, що змінна дорівнює.
>> Інформація місцеві жителі дійсно корисно.
Це спеціальна версія друку.
Інформація місцеві жителі показує вам всі місцеві змінні, друкує їх все для вас
що в даний час доступні.
Так що я, як правило, замість того, щоб роздрукувати чотири змінні, які я
цікаво, якщо я в циклі, для Наприклад, я просто пишу інформація місцевих жителів,
і він буде показати мені, що мій лічильник я дорівнює, а також масиву, що я
працює на рівних.
>> Нарешті, як і раніше.
Введення перерву зупиняється вам в точці розриву.
Ви можете йти по лінії від лінія з низкою й кроку.
Продовжити запускає програму, щоб ваш наступний не порушувати пункт або до завершення, якщо
більше немає точок розриву.
Відключення видаляє точки зупину, якщо вам вирішив перерву в основне було
недоречно, ви хочете встановити його в іншому місці.
І, нарешті д, кинути палити, отримує з GDB.
>> Так ця програма,. / Цезар, ми збираємося переглядати прямо зараз, і ми
збираєтеся використовувати GDB, щоб знайти що помилки в цій програмі.
Я побіг цю програму раніше з Перевірте 50, і я отримав один похмурий погляд.
Все це існувало, це скомпільовано, пройшло багато випробувань, але для
чомусь, він не проходив п'ятий тест, звертаючись BARFOO, все кришки, в
Е-Д-У-І-Р-Р, усі великі, з використанням три якості ключа.
Я отримав досить близько.
Я вийшов на одну букву.
Таким чином, є деякі невеликі помилки в тут.
Я подивився через мій код.
Я не міг зрозуміти його.
Будемо сподіватися, що ви, хлопці, можете допомогти мені з'ясувати, що ця помилка є.
>> Так от помилка, що ми пошук.
Давайте рухатися в GDB.
Знову ж, я біг GDB. / Цезаря, так що тепер ми перебуваємо в GDB.
І те, що це перший що я повинен робити?
Я тільки що вступив GDB.
Хтось дав мені хороший Команда для входу.
>> СТУДЕНТ розмови Загальна.
>> Джейсон Хіршхорна: Перерва основною.
Фантастика.
Давайте введіть що дюйм
Ви, хлопці, можете дивитися тут або слідувати разом на ваших комп'ютерах.
Перерва основний, і ви побачите, Точка розриву була встановлена ​​на рівні -
це дає мені деякі дивні адреси пам'яті, і це також дає мені номер рядка.
Якби я був, щоб озирнутися назад на цей файл, Я зрозумів би, що основні
сталося на лінії 21.
Те, що я повинен працювати далі?
Чи працює моя програма?
Ні.
Так що я повинен працювати далі?
>> СТУДЕНТ: Запустіть.
>> Джейсон Хіршхорна: Запустіть.
Чи повинен я просто Run Run, або повинні Я додати деякі інші речі в?
>> СТУДЕНТ: Запуск з аргументом.
>> Джейсон Хіршхорна: Запуск з команда аргументи.
А так як я налагодження дуже специфічна так, я повинен вказати, що
лінія аргумент командного.
Так що я буду дійсно працюють три, які, знову ж, вихідний я отримав від Виїзд 50.
Починаючи програму.
Ми проходимо через пару рядків.
Тепер ви побачите, що ми знаходимося на лінії 21.
Як я знаю, що ми знаходимося на лінії 21?
Тому що якщо ви подивитеся наліво мого вікна терміналу, є
він говорить лінію 21.
І це дає мені, насправді, код, який на лінії 21.
Так що я обмовився раніше.
Основне насправді не на лінії 21.
Головна перебуває пару рядків вище 21.
Але в рядку 21, це де ми ламати.
Цей рядок коду має ще не виконане.
Це важливо.
Лінія ви бачите має не був виконаний ще.
Це наступна рядок коду Ви збираєтеся виконати.
>> Так що наступного лінія, як ви, хлопці, мабуть, знайомі з, це
перевірка стану, щоб побачити, якщо у мене є вступив аргумент командного рядка.
І щоб я: що є другим частина, що робиш?
Що таке для мене?
>> СТУДЕНТ: Зміна його в ціле число.
>> Джейсон Хіршхорна: Вибачте?
>> СТУДЕНТ: Вона змінюється аргумент на ціле число.
>> Джейсон Хіршхорна: Так, щоб я змінює аргумент v1 з рядка в ціле число.
А потім що ж це перевірка?
>> СТУДЕНТ: Якщо є друга аргумент командного рядка, в сторону
від запуску програми.
>> Джейсон Хіршхорна: І що У другій половині цього
Перевірки логічне вираження?
Ця частина тут, щоб я?
>> СТУДЕНТ: Якщо він негативний.
>> Джейсон Хіршхорна: Переконавшись, що?
>> СТУДЕНТ: Переконавшись, що це, по суті, позитивним.
>> Джейсон Хіршхорна: Абсолютно вірно.
Це перевірка того, якщо це негативним, і, якщо вона негативна, я
є відчуття, наступний рядок міць бути мені кричати на користувача.
Так що давайте вдарив кінець виконати цю лінію.
Ми не бачимо, що лінія, що ви, хлопці, може бути, очікував побачити кричати на
Користувач, а потім повертаються, тому що ця лінія не був виконаний.
Я увійшов 3.
Так що я, справді, введіть два команду аргументи командного рядка, і 3
більше нуля.
Таким чином, ми побачили, що лінія, ми виконали, але ми не крок
всередині, якщо умови.
>> Так що тепер, поряд, я бачу, я встановлюю внутр ключовим одно до я аг v1.
Так що це мені створенні ключ змінної.
Так що якщо я роздрукувати ключ прямо зараз, тому що що дозволяє побачити
значення у змінній, Ключ дорівнює 47.
Це дивно, але звичайно, це тому, що у мене немає
виконується цю лінію ще.
Так що тепер, якщо я вдарив п, виконати цей рядок, і зробити ключ друку, ключ буде дорівнює 3,
що ми і очікуємо, що він складе.
>> Отже, ще раз, в GDB, лінії, яку ви бачу, ви ще не виконана.
Ви повинні вдарити н або з або ряд з інших команд справді
виконати цей рядок.
Ключ для друку.
Ключа на 3.
Досі так добре.
Рядок являє собою простий текстовий.
Давайте виконаємо цю лінію.
Я отримую рядок від користувача.
>> Давайте подивимося, на мій Виїзд 50, я введіть BARFOO усі великі літери, так
це те, що я ввожу.
Якби я зараз друкувати звичайний текст.
Ви побачите, що вона дорівнює рядок.
Це дає мені деяку іншу дивну шестнадцатиричную число, але це відбувається в
Справа в тому, що моя рядок BARFOO.
Якби я хотів, щоб побачити, які ключові склав в ця точка, як я міг перевірити ключ?
>> СТУДЕНТ: ключ друку.
>> Джейсон Хіршхорна: ключ друку, саме так.
А насправді, є ярлик.
Якщо ви втомилися від ввівши друк, Ви можете просто ввести с.
Так р ключовим робить точно такий же речі.
І знову ж, я бачу, що дорівнює 3.
>> Якби я хотів, щоб з'ясувати, що обидва ключа і BARFOO склав водночас
але я втомився від набравши кожен один індивідуально, я
могли б ввести інформація місцевих жителів.
Це дає мені ключові дорівнює 3.
Звичайний текст одно BARFOO.
Це також дає мені ці два дивні речі у верхній частині, ця змінна я і
ця змінна н.
>> Ті, які реально існуючих в моїй основної програми.
Ми не зіткнулися з ними ще, а в якості попереднього перегляду, тим
існують в моєму циклі.
Тому в даний момент, вони рівні якийсь загадковий номери, тому що вони не були
ініціалізації поки немає, але вони все ще існують в пам'яті, так що вони просто встановити
до деякого значення сміття.
Але ми бачимо ключ в простій текст прямо там.
>> Так що я збираюся виконати цю лінію, Лінія 34, для петлі.
Ми збираємося, щоб перейти в цикл, натиснувши н.
І ми всередині циклу.
Ми знаходимося в нашій першій перевірки.
І знову ж, це повинен роду виглядати вам знайомі, тому що це було
Програма Цезар, який був написаний, але знову ж, є якась помилка.
>> І тепер, якщо я зроблю інформація місцевих жителів, тому що я всередині, що цикл, ви побачите
що я дорівнює нулю, як ми очікуємо.
Це те, що ми поставили його в і ініціалізації це в циклі.
н дорівнює 6.
Це також має сенс, тому що ми встановлюємо це до STRLEN звичайного тексту.
Так що я хотів зробити інформація місцевих жителів або друк до змінної часто, щоб переконатися, що
все завжди те, що Я очікую, що він дорівнює.
У цьому випадку, все те, що я очікую, що він дорівнює.
>> Отже, давайте почнемо переміщення через це для петлі.
Лінія Я на це лінія 36, при звичайному текст, який я більше і рівнини
текст, який я менше або дорівнює р.
Я знаю, що моя проблема не в мій перший Лист, це з другим листом.
Якщо ми оглянемося назад при заїзді 50, В йде в E штрафу.
Я беру А і залишаючи його в якості , Не змінюючи його словами Д. Отже
щось не так з друга літера.
Так що я збираюся рухатися там через секунду.
>> Але якби я хочу, щоб перевірити, який рівнину Текст я склав в цей конкретний
так, я думаю, що це має бути що?
Те, що повинно звичайний текст я рівнятися в цьому Перший раунд через цикл?
>> СТУДЕНТ: Нуль?
>> Джейсон Хіршхорна: Звичайний текст з I?
Таким чином, він повинен бути капітал B. Я, звичайно, дорівнює нулю, але звичайний текст
Кронштейн нулю замкнутий кронштейн дорівнює B тому рядки, як ми бачили минулого тижня,
є масив, тому ми отримуємо Перший символ від цього.
Отже, ще раз, якщо я роздрукував простий текст Я, я, по суті, отримати символ
Б. І це акуратно, чи не так?
Я насправді не простий текстовий I. Це не одна з змінних, які я поставив
або ініціалізації, але ви можете роздрукувати з цілого ряду речей
якщо ви хочете, щоб.
>> Але давайте перейдемо через.
Якщо звичайний текст я більше А і простий текст I менше або дорівнює
Z, який чітко вірно, тому що у нас є капітал Б. Я збираюся запустити
деякі команди на ньому.
Ми бачили, що математика минулого тижня, так що ми будемо приймаємо це як належне, що він працює
Право згідно Перевірте 50.
>> Ці фігурні дужки, перший показав, що я виходив, якщо
стан, а другий показав що я виходу для циклу.
І ось тепер, коли я вдарив Далі, ми побачимо ми повернулися в цикл знову.
Ми збираємося через цикл знову.
Давайте насправді крок в секунду ітерація для циклу і типу
Інформація місцеві жителі.
>> Таким чином, ми знаходимося в другій ітерації нашого циклу.
Я дорівнює 1, який ми очікуємо.
N дорівнює 6, який ми очікуємо.
Ключ одно 3, що ми очікуємо.
І звичайний текст, ви побачите, дорівнює EARFOO зараз, а не BARFOO більше, тому що
в нашій попередній ітерації, B був змінений на капітал E. Таким чином, ми збираємося
зіткнутися з проблемою, так що це Тут ми збираємося
зануритися в налагодженні.
Але хто-небудь є які-небудь питання про те, що ми зробили до сих пір?
Фантастика.
>> Таким чином, ми збираємося виконати це, якщо стан, звичайний текст кронштейн Я закрив
Кронштейн більше А і простий текст я менше або дорівнює Z. Але перш
Я йду в це, тому що це, де Я знаю, що моя помилка, я хочу вказати
з простого тексту I. Так давайте поставимо роздруківку.
Він робить рівнятися символів A, так що здається досі, все добре, і добре.
>> Так що я очікую цю лінію за моєю логікою, ця лінія повинна бути правдою.
Це заголовна буква.
Але якби я вдарив п, ми розуміємо, що це лінія, по суті, не був виконаний.
Я зістрибнув на інше, якщо.
Чому це сталося?
>> СТУДЕНТ: Тому що у вас є ваш стан звичайного тексту більше
чому, не більше або дорівнює.
>> Джейсон Хіршхорна: Так у мене був свій звичайний текст Я більше, що не більше
або дорівнює.
Отже, ясно, столиця не зробив викликати це, якщо умова, і ми зробили
не ввійти в нього, і ми зробили не зробили необхідні зрушення.
Так ось воно що, насправді.
Я зрозумів, мій баг.
Я не міг повернутися в моєму початковому файлі, змінити його, і оновлювати його і
запустити Перевірте 50 разів.
>> Але ми побачимо, як раз для педагогіка'S заради, якщо я продовжую.
Решта, якщо не виконує або, але що замість дорівнює є команда
це не змінює.
Так що це не змінилося взагалі, і якщо я друкувати звичайний текст тут, ми побачимо збирається
через що цикл не став, по суті, змінити цю другий символ взагалі.
Він як і раніше столиця А.
>> Отже, ще раз, ми налагоджена нашу помилку.
Ми зрозуміли, що є логіка відсутня.
І ми налагоджена його загодя до фактичного виконання цієї лінії,
але ви б помітили, якби ми просто вдарив Далі і перейти до що ще, якщо,
це означає, що, що якщо умова не відповідає дійсності.
Ми не, насправді, отримати результат ми очікували.
Таким чином ми могли б бути запропоновано, було ми не були так проникливі, щоб дивитися на
що якщо умова і перевірити, якщо, по суті, наша умова слід оцінити в
правда в поточному контексті.
>> От і все, для налагодження цю програму.
Хто-небудь є запитання?
Що команда, яку я міг вразити кинути GDB?
Питання: А потім я буде запропоновано, кинути в будь-якому випадку?
Так чи ні.
Я вдарю так, і я буду пішли GDB.
>> Так, щоб був швидкий грунт, щоб GDB.
Насправді, в реальному сценарії, Я зробив це в робочий час.
Я GDBed цей точний програму в Прийомні години з студентом.
І якщо ми повернемося до команд, які ми бачили раніше, ми використовували розмови Загальна, перший
, Що ми зробили.
Ми використовували біг з аргументами командного рядка, Друге, що ми зробили.
Ми використовували наступний багато рухатися нам по лініях.
І знову, коротка версія з наступного є н.
Ось в дужках сірим кольором на слайді.
>> Ми не використовували крок, але ми не зробили обов'язково повинні в цьому випадку.
Але ми могли б використовувати його в трохи пізніше на сьогодні, якщо ми налагодженні, для
Наприклад, бінарний пошук, коли двійковий Пошук викликається в окремий
Функція але є деякі помилки з ним.
Ми збираємося хочете, щоб увійти в заклик до бінарного пошуку і
насправді його налагодження.
Перерахуйте ми не використали або тому, що у нас було гарне почуття нашого коду, але якщо я
дійсно хотіли отримати уявлення про те, який код я був навколо, я міг би просто використовувати список.
>> Роздрукувати ми використовували, інформація місцевих жителів, які ми використали.
Продовжити ми не повинні використовувати в цьому так, при цьому ми не повинні використовувати
відключити, але ми зробили використання кинути.
Знову ж, ці 10 команд, практикувати їх.
Якщо ви розумієте, ці 10 команд, ви повинні бути встановлені для налагодження будь
видавати з GDB.
>> Таким чином, ми збираємося піти на, знову ж таки, Суть розділі сьогодні, переходячи
ці сортування і пошуку алгоритми.
Перш, ніж ми це зробити, знову ж таки, всі питання, коментарі, побоювання за GDB?
Так як всі збираєтеся використовувати GDB, а не Е?
Так що все, заради навчань, в все киває їхні голови право
зараз, так що я буду бачити Вас в робочий час і все ТФ буде бачити Вас і
вони скажуть, покажи мені, як використовувати GDB, і ви зможете
показати їм, чи не так?
Вид?
Може бути, ми сподіваємося.
Круто.
>> Так що ми збираємося переїхати в сортування та пошуку.
Ви побачите мене є список вже відсортований для нас, але, що не збирається
, Має місце завжди.
Таким чином, у проблемі встановити специфікації для Проблема встановити три, у вас є шорти
що ви можете дивитися, і це насправді просить вас дивитися ці шорти.
Крім того, в лекції минулого тижня, ми перейшли багато з цих алгоритмів, тому я
не збираюся витрачати час у класі відбувається над цими алгоритмами знову або малюнок
картинки про те, як вони алгоритми роботи.
Знову ж, що інформація, яку ви можете повторно годинник лекція, або, що інформація
захоплюється чудово на шортах на ці результати, все
які доступні в cs50.net.
>> Так замість цього, що ми збираємося зробити, це написати ці програми.
У нас є відчуття, ментальну модель, про те, як вони працюють, і так, що ми збираємося
зробити, це кодувати їх по-справжньому.
Ми збираємося перетворити цю ментальну модель, ця картина, якщо хочете, в
Фактичний код.
І якщо ви були трохи збентежені або туманно на ментальної моделі, я повністю
зрозуміти.
>> Ми насправді не збирається перейти до кодом відразу.
Таким чином, хоча це запрошення на цьому слайді запитує вам код бінарний пошук, і
насправді, повторюваний версія бінарний пошук, перше, що я
дійсно хочемо вас зробити, це написати деякий псевдокод.
Так у вас є ця ментальна модель про те, як бінарний пошук роботи.
Вийміть лист паперу, якщо у вас є один легко доступні, або відкрити
текстовий редактор, і я хотів би все написати.
Візьміть чотири хвилини, щоб написати псевдокод для бінарного пошуку.
>> Знову ж, думаю про те, що ментальної моделі.
Я прийду навколо, якщо у вас є питання і ми можемо зробити картину з.
Але спочатку, перш ніж ми почнемо програмування, Я хотів би написати
псевдокод для бінарного пошуку тому, коли ми почати, у нас є деякі напрямки, як
туди, де ми повинні очолити.
>> СТУДЕНТ: Чи можна вважати, масив значення, які ми отримуємо вже відсортовані?
>> Джейсон Хіршхорна: Так що для бінарного пошуку працювати - відмінний питання - ви
повинні прийняти у відсортований масив значень.
Так припустити, що це буде працювати.
Ми повернемося до цього слайда.
Ви побачите в порфіру функції декларація BOOL binary_search внутр
значення, внутр значення, Int N.
Це має виглядати знайомим, якщо ви вже підійшов або отримали ваш
руки брудні з безліччю проблем.
>> Але це ваше оголошення функції.
Знову ж, не потрібно турбуватися про що багато чого в цей момент.
Те, що я дійсно хочу, щоб ви зробити, це прийняти чотири хвилини до псевдокоду двійковий
пошук, а потім ми підемо більше, що у складі групи.
І прийду навколо.
Якщо у вас є питання, будь ласка вільно підняти руку.
>> Чому б вам не взяти більше двох хвилин закінчити псевдокод?
Я знаю, це може здатися смішним, що ми витрачаємо стільки часу на
те, що навіть не насправді в С, але особливо для них більш
складні алгоритми і проблема набори, які ми повинні з'ясувати,
починаючи з псевдокод не турбуючись про синтаксис, просто турбуючись про
логіка, неймовірно попереджувальний.
І таким чином, ви не вирішуючи два неймовірно важкі проблеми відразу.
Ти просто зосередитися на логіці, а то ви переїхати в синтаксисі.
>> ОК.
Почнемо переживає псевдокод.
Я написав тут, двійковий Пошук псевдокод.
Ми напишемо це на сісти разом.
Або я напишу, і ви будете давати мені Запрошення мені потрібно.
Так хто-небудь може дати мені перший лінія псевдокоде ви
написав для бінарного пошуку?
Так, Енні?
>> СТУДЕНТ: У той час як довжина Список більше нуля.
>> Джейсон Хіршхорна: У той час як довжина зі списку більше нуля.
І знову ми бачимо деякі C-дивлячись синтаксичні речі на тут.
Але більше це англійською мовою.
Хто-небудь є які-небудь лінію, вони поставили до цього в їх псевдо-код?
>> СТУДЕНТ: Отримати масив з упорядковано числа.
>> Джейсон Хіршхорна: Ви написали "отримати Масив відсортованих чисел. "Пер
Оголошення функції, ми будемо проходження масив відсортованих чисел.
>> СТУДЕНТ: [нерозбірливо].
>> Джейсон Хіршхорна: Так ми будемо мати, що.
Але так, якщо у нас не було, що ми необхідно буде розібратися наш масив
номера, тому що бінарний пошук працює тільки на впорядковані масиви.
Таким чином, хоча довжина списку дорівнює нулю, я збирається поставити в деяких фігурних дужок
, Щоб вона виглядала трохи більше, як С. Але в той час, здається, відображення на
в той час як петлі, так що всередині цього час петлі, що нам потрібно
зробити для бінарного пошуку?
>> Хтось, хто не дав мені відповісти ще, але хто це написав?
>> СТУДЕНТ: До середини списку.
>> Джейсон Хіршхорна: Том.
До середини списку.
І додаткове питання, що ми робимо тільки ми знаходимося в
середина списку?
>> СТУДЕНТ: Зробіть перевірку будь то номер, який ви шукаєте.
>> Джейсон Хіршхорна: Відмінно.
Перейти середину списку і перевірити якщо наша цінність є -
фантастичним.
Хто-небудь що-небудь ще це було інакше, ніж це?
Ось саме.
>> Перше, що ми робимо в бінарний пошук буде йти в середині списку і
перевірте, якщо наша цінність є.
Так що я вважаю, якщо наша значення там, що ж нам робити?
>> СТУДЕНТ: Повернімося до нуля [нерозбірливо].
>> Джейсон Хіршхорна: Так, якщо наш значення є, ми знайшли його.
Таким чином, ми можемо сказати деякий шлях, проте це функція визначена, ми говоримо користувачу
ми знайшли його.
Якщо його там немає, хоча, це де це стає складніше.
Так що, якщо його там немає, хтось інший, хто працював над бінарного пошуку або
має уявлення про те, в даний час, що ми будемо робити?
>> СТУДЕНТ: Питання.
>> Джейсон Хіршхорна: Да?
>> СТУДЕНТ: Яке масив вже відсортований?
>> Джейсон Хіршхорна: Так, ми припускаємо, масив вже відсортований.
>> СТУДЕНТ: Так то ви повинні перевірити, якщо значення, яке ви бачите більше, ніж
значення, яке ви хочете, ви можете переміщати до середини іншій половині.
>> Джейсон Хіршхорна: Так що, якщо середина список більше ніж те, що ми
шукаєте, то ми що?
Ми рухаємося, де?
>> СТУДЕНТ: Ви хочете, щоб перейти до половина списку з
цифри нижчі, ніж це.
>> Джейсон Хіршхорна: Так ми будемо зателефонуйте, що ліва.
Так що якщо середній більше, ми можемо шукати Ліва половина списку.
А потім при пошуку, що я маю на увазі при пошуку?
>> СТУДЕНТ: [нерозбірливо].
>> Джейсон Хіршхорна: Ми йдемо в середині.
Ми фактично повторити цю річ.
Ми повертаємося через нашу час циклу.
Я дам вам останній -
інакше, якщо, середній менше, ніж ми, що ми робимо тут?
>> СТУДЕНТ: Ідіть направо.
>> Джейсон Хіршхорна: Пошук право.
Це виглядає добре, але хто-небудь є все, що ми може бути відсутнім або бути
все інше, що ви поклали в псевдо-код?
Так що це те, що ми до цих пір.
У той час як довжина списку більше нуля, ми збираємося піти
в середині списку і перевірити, якщо наша цінність є.
>> Якщо середній більше, ми збираємося пошук наліво, ще, якщо середина
Проте, ми збираємося шукати право.
Так ми всі були трохи знайомі з терміни, які ми використовуємо в інформатиці
та інструменти у нас є.
Але ви вже помітили, ми були кажучи по-англійськи, але ми виявили,
багато речей, які, здавалося, карта на інструменти, які є в нашій кодування набір інструментів.
Так прямо з місця в кар'єр, ми не збирається ще насправді код.
>> Що ми бачимо тут англійською мовою, що карти на що ми можемо написати в C?
>> СТУДЕНТ: У той час як.
>> Джейсон Хіршхорна: У той час як.
Так що це в той час як тут, карти на ні до чого?
>> СТУДЕНТ: у той час як петля.
>> Джейсон Хіршхорна: у той час як цикл?
Або можливо, в більш загальному плані, петля.
Ми хочемо зробити щось знову і знову.
Так що ми збираємося, щоб закодувати петлю.
І ми вже знаємо, тому що ми зробили це пару раз, і ми
є багато прикладів там, як насправді писати
цей показник для петлі.
Так що повинно бути досить легко.
Ми повинні бути в змозі отримати, що почав досить швидко.
>> Що ще ми бачимо тут?
Які ще структури синтаксису, речі що ми знайомі з в С, ми
вже є відчуття основі від слів, які ми використовували?
Так, Анна?
[Нерозбірливості]
жартую.
Анна, йти вперед.
>> СТУДЕНТ: Якщо і в іншому місці.
>> Джейсон Хіршхорна: Якщо і інше - прямо тут.
Так що ж ті, схожий?
>> СТУДЕНТ: якщо ще заяві.
>> Джейсон Хіршхорна: Так, умови, чи не так?
Таким чином, ми, ймовірно, потрібно написати деякі умови.
І знову, хоча, можливо, плутаючи при по-перше, ми як правило, мають сенс зараз
як написати умов і Синтаксис для умов.
І якщо ми не робимо, ми просто подивитися Синтаксис умов, вирізати і вставляти
що, тому що ми знаємо, що потрібно умова тут.
Будь-які інші речі, які ми бачимо, що відображення на речі, які ми, можливо, буде потрібно зробити в C?
Так, Aleha?
>> СТУДЕНТ: Це може бути очевидно, , Просто перевірка, якщо
значення одно щось.
>> Джейсон Хіршхорна: Так як же ми перевіряємо і - для цього заходимо в середині списку
і перевірити, якщо наша цінність є?
Як ми це робимо, що в C?
Що синтаксис для цього?
>> СТУДЕНТ: Так само, одно.
>> Джейсон Хіршхорна: Так само, одно.
Так що це перевірка, ймовірно, буде бути рівності, рівних.
Тому ми розуміємо, що необхідно, що десь.
А насправді, просто при її написанні, ми бачимо ці інші речі.
Ми збираємося мати, щоб зробити деякі Оператори порівняння в там -
фантастичним.
Так що насправді виглядає, по великий, ми не писали
слово C коду ще.
Але ми отримали ментальну модель вниз через лекції та тих шортах.
>> Ми написали псевдо-код у вигляді групи.
І вже, у нас є 80%, якщо не 90% того, що нам потрібно зробити.
Тепер нам просто потрібно закодувати він, який знову,
нетривіальна проблема, яка потребує вирішення.
Але принаймні ми застрягли на логіці.
Принаймні, зараз, коли ми йдемо в робочий час, Я можу сказати, я знаю, що мені потрібно
зробити, але ви можете нагадати мене синтаксису?
Або навіть якщо робочий час переповнені, вам Чи може Google для синтаксису, а
ніж застрявання на логіці.
>> І знову, замість того, щоб вирішувати логіка і синтаксис проблеми все
відразу, часто набагато краще розірвати ці два жорсткі проблеми геть в
дві більш керовані ті й робити псевдо-код, а потім код на мові C.
Отже, давайте подивимося, що я зробив для псевдо-код загодя.
>> У той час як довжина списку більше нуля, подивіться на середині
зі списку.
Якщо число знайдено повернувся правда, ще якщо число вище, пошук зліва.
Інакше, якщо число менше, пошук Добре, повернення помилковим.
Так що виглядає майже ідентично, якщо не майже ідентичний тому, що ми написали.
Насправді, Том, що ви спочатку сказав, порушуючи середині списку, і якщо
число знайдено в двох тверджень насправді, що я зробив.
>> Я об'єднав їх там.
Я повинен був слухати Ви вперше.
Отже, це псевдо-код у нас є.
Якщо ви хочете зараз, вибачте, перейдіть Повернемося до нашого початкового завдання.
Давайте коду binary.c.
Так реалізації ітеративний версію бінарний пошук, використовуючи наступні
Оголошення функції.
>> І вам не потрібно копіювати його вниз тільки поки.
Я насправді відбувається, щоб відкрити прямо тут binary.c.
Так що є оголошення функції в середині екрана.
І ви побачите, я взяв псевдо-код від на моїх сторін, але практично ідентичні
до чого ми писали, і покласти, що в для вас.
Так що тепер, давайте п'ять хвилин закодувати цю функцію.
>> І знову ж, якщо у вас є які-небудь питання, підніміть руку, дайте мені знати, я буду
прийти.
>> СТУДЕНТ: [нерозбірливо].
>> Джейсон Хіршхорна: Так що я взяв двійковий Визначення пошук в
вгору, на лінії 12.
Ось що я отримав для своїх слайда.
А потім все це псевдо-код, я просто скопіювати і вставити на слайді,
псевдо-код слайд.
Я все ще не чуючи [нерозбірливо].
>> Так що якщо ви закінчили реалізація, я хочу, щоб перевірити його.
Мені по електронній пошті вам файл helpers.h раніше в цьому класі.
І вона буде доступна онлайн, а також для завантаження для людей, що дивляться
на цей раз розділ затримується.
І я просто використав загальний розподіл Код від pset3.
Так що я взяв find.C, використовувати свій helpers.h файл Замість файлу helpers.h
що дав у коді розподілу.
>> І я повинен був зробити одна зміна в find.C замість виклику просто
Пошук, телефонуйте binary_search.
Так що, якщо ви хочете перевірити свій код, знаю, що це, як це зробити.
Справді, коли ми будемо проводити цей код Прямо зараз, я просто зробив копію
мій каталог pset3, знову ж, вивантажено Помічники файли, а потім зробив, що
змінити в find.C зателефонувати binary_search а не просто пошук.
>> Джейсон Хіршхорна: Так.
У Вас є запитання?
>> СТУДЕНТ: Nevermind.
>> Джейсон Хіршхорна: Не турбуйтеся.
Ну, давайте почнемо.
Ми будемо кодувати це як група.
Ще одне зауваження.
Знову ж, це може легко бути замінені в для завдання встановити три.
У мене є helpers.h файл, який, швидше ніж helpers.h нам дають,
заявляє бінарний пошук, міхур роду, і вибір роду.
І в find.c ви помітите на лінії, що це таке, лінія 68, ми називаємо двійковий
пошук, а не пошук.
Отже, ще раз, код, який доступний онлайн або код, який ви
створення прямо зараз можна легко поміняти місцями протягом р набір 3, щоб перевірити його.
>> Але спочатку, давайте код бінарний пошук.
Наша оголошення функції, ми повернемося логічне значення.
Візьмемо ціле під назвою значення.
Візьмемо масив цілих чисел з ім'ям значення, і ми беремо п
розмір масиву.
У рядку 10, прямо тут, у мене є Різке включають stdbool.h.
Хто-небудь знає, чому це там?
Так, що це рядок коду робити?
>> СТУДЕНТ: Вона дозволяє використовувати повертається тип BOOL.
>> Джейсон Хіршхорна: Абсолютно вірно.
>> СТУДЕНТ: Чи це бібліотека, яка дозволяє використовувати тип повертається BOOL.
>> Джейсон Хіршхорна: Так різке включають stdbool.h лінія дає мені деякі
визначення та оголошення для речей що я маю право використовувати в
ця бібліотека.
Так серед тих, каже, що є Цей тип називається логічний, і це може бути
істинним або хибним.
Так ось що, що лінія робить.
І якщо у мене не було, що лінія, я б потрапити в біду за написання цього
Слово прямо тут, логічний, прямо там.
Абсолютно вірно.
Тому мені потрібно, що в цьому коді.
ОК.
Так що це, знову ж, є повторюваним версія, що не рекурсивний один.
Так давайте почнемо.
>> Давайте почнемо з цього першого лінія псевдо-код.
І, сподіваюся, ми будемо - чи ні, ми сподіваємося.
Ми збираємося піти по кімнаті.
Ми підемо построчно, і я допоможу Ви з'ясовуєте лінію, що нам потрібно
написати перший.
Таким чином, хоча довжина списку більше нуля.
Почнемо в передній частині.
Яку лінію я повинен написати тут, в коді?
>> СТУДЕНТ: У той час як дужка N більше 0.
>> Джейсон Хіршхорна: У той час як н великий, ніж 0.
Таким чином, п розмір списку, і ми перевіряємо, якщо -
>> [Вставляючи ГОЛОСИ]
>> Джейсон Хіршхорна: - Вибачте?
>> СТУДЕНТ: Як ми знаємо, що п-розмір списку?
>> Джейсон Хіршхорна: Вибачте.
За специфікації PSet, пошук і як би діє вам потрібно написати,
N є розмір списку.
Я забув пояснити, що тут.
Але так. N є розмір список, в цьому випадку.
Таким чином, хоча п більше 0.
ОК.
Це може виявитися трохи проблематично хоча, якщо так буде продовжуватися.
Тому що ми будемо продовжувати, щоб знати Розмір списку протягом усього цього
Функція, але сказати, що ми почнемо з масивом 5 цілих чисел.
І ми проходимо через, і ми зараз скоротився до
масив з 2 цілих чисел.
Які 2 цілі числа, що?
Розмір 2 тепер, коли ми хочемо дивитися, але яких 2 є те, що?
Чи має це сенс, на це питання?
>> ОК.
Я попрошу його знову.
Таким чином, ми почнемо з цього масиву 5 цілі числа, п дорівнює 5, чи не так?
Ми будемо працювати до кінця тут.
ми, ймовірно, змінити розмір, Право, як справи йдуть на.
Що те, що ми говоримо, що хочемо зробити.
Ми не хочемо шукати повний річ знову.
Так сказати, що ми змінити його на 2.
Беремо половину списку Це дивно.
Так просто взяти 2.
Так що тепер п дорівнює 2.
Я прошу вибачення за бідних сухого стирання маркери.
Чи не так?
І ми шукаємо за списком знову зі списком розміру 2.
Ну, наш масив і раніше розміру 5.
Ми говоримо, ми тільки хочемо, щоб пошук 2 місця в ньому.
Отже, які 2 місця це таке?
>> Чи має це сенс?
Чи є вони ліві 2 місця?
Чи є вони правильні 2 місця?
Чи є вони середні 2 місця?
Ми розбили проблему вниз, але ми насправді не знаю, яка частина
проблема, яку ми все ще дивимося, тільки за наявності цих 2 змінні.
Так що ми повинні трохи більш, а п більше 0.
Ми повинні знати, де, що п в нашому фактичному масиві.
>> Так хто-небудь є зміниться на цій лінії?
Велика частина цієї лінії абсолютно правильно.
Є ще одне доповнення?
Чи можемо ми поміняти щось для п до зробити цю лінію трохи краще?
Угу?
>> СТУДЕНТ: Чи можете ви ініціалізувати змінну як довжини до п, то будемо використовувати
пізніше в функції?
>> Джейсон Хіршхорна: Так ініціалізації змінної довжини п,
і ми використовуємо це пізніше?
Але тоді ми просто оновити довжину і ми ще зіткнулися з цією проблемою, де ми
скоротити довжину нашої проблеми, але ми ніколи не знаємо, де, власне,
що довжина відображається на.
>> СТУДЕНТ: Хіба це не відбудеться пізніше, коли ви говорите, пошук зліва,
пошук не так?
Ви збираєтеся перейти на інший Область Ваших -
>> Джейсон Хіршхорна: Ми збираємося піти в область, але як ми знаємо,
які повинні йти?
Якщо у нас є тільки масив і це п, як ми знаємо, де
перейти в масиві.
У задній частині, так?
>> СТУДЕНТ: У вас є, начебто, нижче межа і верхня межа змінної або
щось в цьому роді?
>> Джейсон Хіршхорна: ОК.
Так що це ще одна ідея.
Замість того щоб просто відстежувати розмір, ми відстежуємо нижнього і
верхня межа змінної.
Так як же нам розрахувати розмір від нижня межа і верхня межа?
>> [Вставляючи ГОЛОСИ]
>> Джейсон Хіршхорна: віднімання.
А також відстежувати нижня і праву кордону, дайте нам знати,
ми пошуку цих двох?
Невже ми пошуку ці два сюди?
Невже ми пошуку середню два?
Напевно, не дві середні, тому що це, по суті, є бінарний пошук.
Але тепер ми зможемо отримати розмір, але й межі масиву.
По суті, якщо у нас є гігант Телефонна книга, ми зірвати його навпіл.
Тепер ми знаємо, де, що менше, Телефонна книга.
Але ми насправді не розриваючи Телефонна книга в два рази.
Нам все ще потрібно знати, де Нові кордони нашої проблеми.
Хто-небудь є які-небудь питання про це?
Так?
>> СТУДЕНТ: Чи буде це працювати, створюючи змінна, я, що ви потім просто перенести
позиція я по відношенню до його поточне положення і довжина, п?
>> Джейсон Хіршхорна: А що це я?
>> СТУДЕНТ: Як я бути як свого роду -
Як би Ви ініціалізувати я бути середнє положення масиву.
А потім, якщо значення в положенні я в середина масиву в встановлено,
бути менше, ніж значення, вам потрібно, я зараз стає довжина масиву, а також
значення я розділив на 2.
Мовляв, бачите, ви швидкість I -
>> Джейсон Хіршхорна: Вірно.
>> СТУДЕНТ - до -
>> Джейсон Хіршхорна: Так що я майже впевнений, що буде працювати.
Але справа в істота, необхідно два фрагменти інформації тут.
Ви можете зробити це з початку і кінця, або ви можете зробити це з розміром, а потім
деякі маркер.
Але ви повинні дві частини інформації тут.
Ви не можете пройти з тільки один.
Чи означає це, має сенс?
>> Так що ми збираємося, щоб пройти, і ми збираємося зробити [нерозбірливо]
і створити деякі маркери.
Так Що ви пишете в коді?
>> СТУДЕНТ: Я тільки що сказав, внутр кордон один одно 0.
>> Джейсон Хіршхорна: Давайте назвемо що внутр, починаючи.
>> СТУДЕНТ: ОК.
>> Джейсон Хіршхорна: Це робить більше сенсу для мене.
І?
>> СТУДЕНТ: Я сказав, я думаю, Int закінчується.
>> Джейсон Хіршхорна: десяткового закінчується.
>> СТУДЕНТ: Я думаю, п мінус 1, або щось в цьому роді.
Мовляв, останній елемент.
>> Джейсон Хіршхорна: Таким чином, ви писали, внутр починаючи дорівнює 0, крапка з комою, і міжнар
закінчення одно п мінус 1, крапку з комою.
Так по суті, що ми робимо тут, 0 перше місце.
І, як ми знаємо, в масивах, вони не йдуть до п, вони йдуть до н мінус 1.
Так у нас є деякі межі нашого масиву.
І ці первинні межі, трапляється, початкові кордону нашої проблеми.
ОК.
Так це звучить добре.
Тоді, якщо ми повернемося до цієї лінії, у той час як довжина списку більше 0,
що, замість того, щоб п, повинні ми ставимо тут?
>> СТУДЕНТ: Написати закінчуючи мінус початок.
>> Джейсон Хіршхорна: У той час як закінчення мінус починають більше 0?
ОК.
І ми могли б, якщо б ми хотіли зробити це трохи краще, ніж
ще ми могли зробити?
Якби ми хотіли, щоб прибрати цей код небагато?
Як ми можемо позбутися 0?
Це просто питання стилю.
Це правильно, просто зараз.
>> СТУДЕНТ: наприкінці не дорівнює початок?
>> Джейсон Хіршхорна: Ми можемо зробити що?
>> [Вставляючи ГОЛОСИ]
>> СТУДЕНТ: Ending більше?
>> Джейсон Хіршхорна: Так.
Ми можемо просто зробити той час як закінчення більше, ніж початку.
Вірно.
Ми додали починають з іншого боку про це, і ми позбулися 0.
Так що це просто виглядає трохи чистіше.
ОК.
Так, в той час як довжина списку дорівнює 0, ми писали що, в той час як закінчення більше
ніж початок.
Ми збираємося поставити в наш необхідності фігурні дужки, і то перше, що
ми хочемо зробити, це подивитися на їх у невеликій списку.
Ви?
Ви можете дати мені -
>> СТУДЕНТ: Якщо дужка значення квадратна дужка -
>> Джейсон Хіршхорна: Якщо дужки значення квадратна дужка.
>> СТУДЕНТ: Кінцівка розділити на 2.
>> Джейсон Хіршхорна: Ending?
>> СТУДЕНТ: Я бачу проблему з вашим -
>> Джейсон Хіршхорна: ОК.
Ну, подивіться на середині.
Звідки ми знаємо, що середина?
Так.
Отже, дозвольте мені видалити цей код.
Звідки ми знаємо, що середина?
У чому, коли у вас є початок і кінець, як ви знаходите
середній?
>> СТУДЕНТ: Ви в середньому.
>> СТУДЕНТ: Ви додати їх разом, а потім -
>> Джейсон Хіршхорна: Додайте їх разом, а потім?
>> СТУДЕНТ: І ви в середньому.
Розділіть його на 2.
>> Джейсон Хіршхорна: Додайте їх разом і розділити на 2.
Так внутр середнього рівних?
Том, ви можете дати його мені?
>> СТУДЕНТ: Починаючи плюс закінчення -
>> Джейсон Хіршхорна: Початок плюс закінчення.
>> СТУДЕНТ: Всі, кронштейн, ділиться на 2.
>> Джейсон Хіршхорна: Всі, в дужках, ділиться на 2.
Так що це дає мені середину ні про що, правильно?
>> СТУДЕНТ: Крім того, необхідно, щоб закруглити його.
>> Джейсон Хіршхорна: Що ви значить, мені потрібно округлити його?
>> [Вставляючи ГОЛОСИ]
>> СТУДЕНТ: Тому що, якщо Це дивне число, то це все одно, -
>> Джейсон Хіршхорна: Ну, добре.
Так що я міг оточити його.
Але якщо це непарне число, 5, я можу приймаюча значення 1, від середини.
Або, якщо це парне число, а, що це краще так.
Якщо це 4, у нас є тільки 4, я можу взяти перший "середній", цитата, кінець цитати або
другий «середній» один.
Або буде працювати для бінарного пошуку, так що я насправді не потрібно округлити його.
Але є одна річ, яку я потрібно дивитися на цій лінії.
Ми не могли б зрозуміти це, але ми повернемося до нього.
Тому що ця лінія насправді ще необхідний ще одну річ.
>> Але досі, ми написали чотири рядки коду.
Ми отримали наш початок і закінчуючи маркери.
У нас є час циклу, яка відображає безпосередньо до нашої псевдокоде.
Ми дивимося на середині, яка відображає безпосередньо на нашому псевдокоде.
Я б сказав, це йде до середини зі списку, цей рядок коду.
А потім, коли ми йдемо в середині список, наступне, що ми повинні зробити,
це перевірити, якщо наша цінність є для псевдокод ми писали раніше.
>> Отже, як же ми перевіряємо, якщо наша цінність знаходиться в середині списку?
Ви.
Чому б вам не зробити це?
>> СТУДЕНТ: Якщо наша цінність є в середині дорівнює
все, що ми встановити -
Я маю на увазі дорівнює дорівнює -
>> Джейсон Хіршхорна: Це -
ОК.
>> СТУДЕНТ: Я не впевнений, що Мінлива ми шукаємо
бо, хоча, тому, що -
>> [Вставляючи ГОЛОСИ]
>> СТУДЕНТ: [нерозбірливо].
>> Джейсон Хіршхорна: Абсолютно вірно.
За оголошенні функції, ми шукаємо значення.
Так ми шукаємо значення в масиві значень.
Таким чином, ви абсолютно праві.
Ви будете робити, якщо вона відкрита дужка значення кронштейн середній закритий кронштейна рівних
дорівнює вартості, а всередині Що ж ми повинні робити?
Якщо наша цінність там, що ми повинні зробити?
>> [Вставляючи ГОЛОСИ]
>> СТУДЕНТ: Повернутися до нуля.
>> Джейсон Хіршхорна: Повернутися правда.
>> СТУДЕНТ: Повернутися правда.
>> Джейсон Хіршхорна: Михайло, що ж це лінія робити?
>> СТУДЕНТ: [нерозбірливо] програма запуску його курс, і що закінчилася, і
у Вас є, що вам потрібно робити?
>> Джейсон Хіршхорна: Програма або що?
У цьому випадку?
>> СТУДЕНТ: Функція.
>> Джейсон Хіршхорна: Функція.
І ось, щоб повернутися до того, що називається це і дати йому значення, правда.
Абсолютно вірно.
Головна.
Що повертається тип з основної, Майкл?
>> СТУДЕНТ: внутр, ціле?
>> Джейсон Хіршхорна: внутр, точно.
Ціле.
Це був просто питання, щоб переконатися, ви, хлопці, були на ньому.
Що це, як правило, повернутися, якщо всі працюють добре?
>> СТУДЕНТ: Нуль.
>> Джейсон Хіршхорна: Нуль.
Абсолютно вірно.
>> СТУДЕНТ: Якщо це просто повертає істину, немає інформації приділяється
про те, що -
О, це просто кажу, що це значення всередині масиву.
>> Джейсон Хіршхорна: Абсолютно вірно.
Ця програма не дає інформації від того, де саме це значення.
Це тільки говорять, так, ми знайшли це, чи ні, ми не знайшли його.
Так що, якщо число знайдено, повернутися вірно.
Ну, насправді ми просто зробили, що дійсно швидко з цієї одного рядка коду.
Так що я буду рухатися, що лінію псевдокоде.
>> СТУДЕНТ: Не потрібно змінити масив?
Вона повинна бути значень, а не вартість, чи не так?
>> Джейсон Хіршхорна: Вибачте.
Спасибо.
>> СТУДЕНТ: Так.
>> Джейсон Хіршхорна: Ця лінія повинні бути значення.
Абсолютно вірно.
ОК.
Таким чином, ми дивилися на середньому списку.
Якщо число знайдено повернення правда.
Продовжуючи з нашим псевдокоде, якщо середній більше, пошук залишилося.
Так що мені довелося тут, якщо число вище, пошук залишилося.
Костянтин, ви можете дати мене цей рядок коду?
>> СТУДЕНТ: Якщо значення середині -
>> Джейсон Хіршхорна: Так що, якщо значення -
якщо відкрито дужка значення кронштейн середній закриває дужка -
>> СТУДЕНТ: менше, ніж значення?
>> Джейсон Хіршхорна: Менше ніж.
>> СТУДЕНТ: менше значення.
>> Джейсон Хіршхорна: Значення.
Ну, насправді, ви хочете перевірка номера -
Вибачте.
Це трохи збиває з пантелику.
Але ще, якщо число в середина списку більше.
>> СТУДЕНТ: О, добре.
>> Джейсон Хіршхорна: Я буду змінити цю ситуацію.
Інакше, якщо середній вище, ми Для пошуку ліворуч, добре?
І що ж нам робити всередині це, якщо стан?
>> СТУДЕНТ: Чи можу я зробити невелика зміна в умова, змінити його на інше, якщо?
>> Джейсон Хіршхорна: Інакше, якщо?
ОК.
Так що це код буде виконуватися про те ж.
Але хороша річ про використання, якщо, ще якщо, в іншому випадку або, якщо інакше, якщо, ще
означає, що тільки один з тих, збирається бути перевірені, не всі три з них,
потенційно.
І це робить його трохи приємніше на комп'ютері, це
виконання вашої програми.
>> Так [? Костянтин,?]
ми всередині цієї лінії, інакше, якщо значення, кронштейн середнього закриває дужка
більше, ніж значення.
Що ми повинні зробити?
Ми повинні шукати ліву.
Як ми це робимо?
Я збираюся дати вам почати.
>> У нас є ці дві речі, звані починаючи і закінчуючи.
Так що має статися до початку?
Якщо ви хочете знайти зліва від Список, ми отримуємо наш Початок струму.
Що нам потрібно зробити?
>> СТУДЕНТ: Покладемо початок в середині плюс 1.
>> Джейсон Хіршхорна: Так що, якщо ми пошук ліву?
>> СТУДЕНТ: На жаль, середній мінус -
так кінцівка буде середнім мінус 1 і початок -
>> Джейсон Хіршхорна: А що відбувається з самого початку?
>> СТУДЕНТ: Він залишається тим же самим.
>> Джейсон Хіршхорна: Так значення залишається незмінним.
Якщо ми шукаємо ліву, ми з використанням тих же початок -
Абсолютно вірно.
І закінчуючи?
На жаль, те, що робить закінчуючи одно знову?
>> СТУДЕНТ: Близький мінус 1.
>> Джейсон Хіршхорна: Близький мінус 1.
Тепер, чому мінус 1, а не тільки середній?
>> СТУДЕНТ: середина з картина вже, бо ми мали
перевірив, що це поза?
>> Джейсон Хіршхорна: Це Абсолютно вірно.
Середина з картини.
Ми вже перевірили середину.
Таким чином, ми не хочемо "середину", цитату кінець цитати, щоб продовжувати бути в
Масив, що ми шукаємо.
Так що це фантастично.
>> Інакше, якщо значення кронштейн середнього більше ніж значення закінчуючи рівних
середній мінус 1.
Джефф, що з цього приводу останньому рядку?
>> СТУДЕНТ: інше.
Значення середнього менше вартості?
>> Джейсон Хіршхорна: Ми будемо ви даєте мені ще.
Так що якщо ви не дасте мені -
>> СТУДЕНТ: Отже, починаючи буде середнім плюс 1.
>> Джейсон Хіршхорна: Починаючи одно середній плюс 1, знову ж таки, за те ж саме
Причина, по якій Костянтин дав нам раніше.
І врешті-решт, хто не дав мене рядок коду ще?
Повернутися помилкове, Aleha, що ми пишемо тут?
>> СТУДЕНТ: Повернутися хибним.
>> Джейсон Хіршхорна: Повернутися хибним.
І ми повинні зробити це, тому що якщо ми не знайдеш його, ми повинні сказати, ми
не знайшли його.
І ми сказали, що ми збираємося повернутися логічний, так що ми безумовно повинні повернутися
BOOL десь.
>> Так що давайте запуском цього коду.
Я насправді збирається -
так що ми в терміналі.
Ми очистити наше вікно.
Давайте зробимо все.
Ми виявили, що одна помилка.
Там в помилку в рядку 15, очікується Крапка з комою в кінці
Декларація.
Отже, що ж я можу забути?
>> СТУДЕНТ: Крапка з комою.
>> Джейсон Хіршхорна: Крапка з комою прямо тут.
Я думаю, що був код Тома.
Так Том, [нерозбірливо].
Жартую.
Давайте ж зробити все знову.
>> СТУДЕНТ: Що каталог Dropbox ми повинні бути в для цього?
>> Джейсон Хіршхорна: Таким чином, ви можете просто дивитися на цей біт.
Але знову ж, якщо ви хочете, щоб перемістити це код в ваш каталог pset3 спробувати
це, ось що я зробив.
Якщо ви помітите тут - шкода, хороший питання.
>> [? LS,?]
У мене є тут код find.c з коду дистрибутива на цьому тижні.
У мене є helpers.h.
У мене є Make-файл, який я насправді злегка змінена, щоб включити ці нові
файли ми пишемо.
Все, що код буде доступний, що не код розподіл, але новий
Зробити файл, новий файл helpers.h буде бути доступні в Інтернеті для скачування.
Знову ж, так що ті, є додаткові коди у нас є.
>> Так що все, за цієї лінії, робить знайти, двійковий, вибір міхур - марки
всі троє і компілює в це виконуваний код знахідка.
Так взагалі, ми не хочемо, щоб прямо в check50.
Ми хочемо, щоб виконати деякі тести самостійно.
Але саме так ми можемо прискорити цей трохи, check50 2013 pset3.find пройде
в helpers.c-- моє погане.
>> У мене немає, що просто зараз.
Так що ми насправді збирається запустити код по-справжньому.
Usage.find /, ви знаєте, що це означає?
>> СТУДЕНТ: Вам потрібен другий командного рядка на ньому.
>> Джейсон Хіршхорна: мені потрібно Другий командного рядка.
І відповідно до специфікації, мені потрібно ввести те, що ми шукаємо.
Отже, давайте поглянемо на 42.
Ми будемо тримати його у відсортований, тому що ми не написано функцію сортування ще -
42, 43, 44.
>> І управління D не знайшли Голка в копиці сіна.
Це погано.
Це безперечно є.
Давайте спробуємо щось ще.
Може бути, це тому, що я поклав це на самому початку.
>> Давайте зробимо 41, 42, 43.
Там ми йдемо.
Це його знайшли.
Скажімо наприкінці зараз, просто так що ми можемо бути ретельним -
40, 41, 42.
Не знайшли голку.
Так що я говорив про це раніше.
На жаль, я знав, що це повинно було трапитися.
>> Але в педагогічних цілях, це добре, щоб дослідити його.
Це не працює.
З деяких причин, він не може знайти його.
Ми знаємо, що там, але ми не знаходячи його.
Таким чином, одна річ, яку ми могли зробити, це пройти через GDB, щоб знайти його, але робить нікого,
минаючи GDB, є Почуття, де ми облажалися?
[? Маду? ?]
>> СТУДЕНТ: Я думаю, що це може бути, коли закінчується дорівнює початку, і це
просто список з одного елемента.
Тоді він просто ігнорує його замість фактично перевіряючи його.
>> Джейсон Хіршхорна: Це Абсолютно вірно.
Коли закінчення дорівнює початок, ми ще є елемент в нашому списку?
>> СТУДЕНТ: Так.
>> Джейсон Хіршхорна: Так, насправді, ми є один і тільки один елемент.
І це, швидше за все, відбудеться, коли, за коді ми тестували, ми знаходимося в
Передня частина стозі сіна або, по крайней кінець сіна.
Ось де початок і закінчення збирається одно
один, з бінарного пошуку.
Таким чином, в цих двох випадках він не працює, тому закінчив дорівнював початку.
>> Але якщо закінчуючи дорівнює початку, Чи це, в той час як цикл виконати?
Це не так.
І ми могли б перевірили що знову ж через GDB.
Так як ми можемо виправити цей код, тому що коли той час як закінчення дорівнює
починаючи, ми також хочемо, щоб цей в той час як петля для запуску.
>> Так що виправлення ми можемо зробити, щоб вирівняти 18?
>> СТУДЕНТ: [нерозбірливо] більше або дорівнює.
>> Джейсон Хіршхорна: Абсолютно вірно.
У той час як закінчення більше або дорівнює початку.
Так що тепер, ми впевнені, щоб отримати, що кут випадок в кінці.
І давайте подивимося.
Давайте запустимо цей ще раз.
>> Давайте зробимо все.
Знову ж, вам доведеться просто слідувати разом тут.
Знайти 41 на цей раз.
Просто тримати його у відповідність.
>> Знайти 42.
Скажімо на початку -
42, 43, 44.
Ми знайшли його.
Так, щоб було дійсно зміна ми повинні були зробити.
>> Це було багато кодування ми тільки що зробив, бінарний пошук.
Хто-небудь є будь-які питання перед Я перейду в лінії ми писали в
бінарний пошук або як ми вважали, то, що ми не з'ясовували?
Перш ніж ми перейдемо, я також хочу відзначити , Що за великим рахунком, ми зіставили
наша псевдо-код від одного до один на наш код.
>> У нас дійсно були, що складна річ щоб з'ясувати, з
починаючи і закінчуючи.
Але якби ви не зрозуміли, що з, ви написав би в значній мірі
ідентичні код, за винятком ці два верхніх рядках.
І тоді ви б зрозуміли, коли Ви зробили це в стримувань і випадках, які
потрібно щось ще.
Так що навіть якщо ви дотримувалися наших псевдо-код рядка до рядка, ви б вже
отримали всі, крім двох ліній код, який ви мали написати.
>> І я був би готовий посперечатися, що ви, хлопці, б все зрозумів, що з
досить швидко, що вам потрібно, щоб покласти свого роду маркером туди, щоб з'ясувати
, Де ви були.
Це знову ж, є сила робити псевдо-код загодя.
Так що ми можемо зробити логіку, а потім ми можемо турбуватися про синтаксис.
>> Якби ми були збентежені про логіку при спробі записати цей код в C,
ми отримали б все зіпсував.
А потім ми будемо ставити питання про логіка і синтаксис і зчеплення
їх всі разом.
І ми отримали б втраченим в тому, що може швидко стати
дуже важке завдання.
Так давайте перейдемо тепер до вибору виду.
>> У нас є 20 хвилин в запасі.
Тому у мене є відчуття, що ми не зможемо пройти через всі вибору роду
і бульбашкового сортування.
Але давайте принаймні, спроба закінчити вибору роду.
Так реалізації вибір роду допомоги Наступний оголошення функції.
>> Знову ж, це взято з Проблема встановити специфікацію.
Int значення є дужки, є масив цілих чисел.
І int.n є розмір цього масиву.
Рода Вибір збирається сортувати цей масив.
>> Так відповідно до нашої ментальної моделі відбору роду, ми тягнемо -
Спочатку ми пройдемося за списком першим Час, знайти найменше число,
покласти його на початку, знайти другу найменше число, покласти його в
Друга позиція, якщо ми хочемо начебто в порядку зростання.
Я не змушую вас писати псевдо-код прямо зараз.
>> Але перш, ніж ми робимо код як клас в п'ять хвилин, ми збираємося написати
псевдо-код, тому ми повинні деякий сенс від того, де ми йдемо.
Так намагатися записати псевдо-код за своїм розсудом.
А потім намагайтеся повернути, що псевдо-код в код.
Ми зробимо це в якості групи через п'ять хвилин.
>> І, звичайно, дайте мені знати, якщо у вас є які-небудь питання.
>> СТУДЕНТ: Що це?
>> Джейсон Хіршхорна: Подивіться, як далеко ви можете отримати в більш двох хвилин.
Я розумію, ви не будете бути в змозі закінчити.
Але ми підемо на це в групі.
>> Ви все кодування так [нерозбірливо], тому я шкода, щоб призупинити, що ви робите.
Але давайте пройдемо це як групи.
І знову, бінарний пошук, ви всі дають мені один, якщо не більше рядків коду.
Спасибі Вам за це.
Ми збираємося зробити те ж саме тут, код разом як група.
>> Так вибір роду - давайте напишемо У результаті швидкої псевдо-код.
За ментальної моделі, може хтось дати мені перша лінія псевдо-код, будь ласка?
Що я хочу зробити?
>> СТУДЕНТ: У той час як список вийшов з ладу.
>> Джейсон Хіршхорна: Добре, тоді як Список вийшов з ладу.
А що ви маєте на увазі "не в порядку?"
>> СТУДЕНТ: У той час як [нерозбірливо]
не сортуються.
>> Джейсон Хіршхорна: У той час як список вийшов з ладу, що ж нам робити?
Дайте мені другу лінію, будь ласка, Маркус.
>> СТУДЕНТ: Так знайти наступний найменше число.
Це буде з відступом.
>> Джейсон Хіршхорна: Так знайти Наступний найменше число.
А потім хтось ще?
Як тільки ми знайдемо наступний за величиною число, що ж нам робити?
Я збираюся сказати, знайти найменше число.
Це те, що ми хочемо зробити.
>> Так що знайдіть найменше число.
Тоді що ж нам робити?
>> СТУДЕНТ: [нерозбірливо], щоб початку.
>> Джейсон Хіршхорна: Вибачте?
>> СТУДЕНТ: Помістіть його в початку списку.
>> Джейсон Хіршхорна: Так помістіть його в початок списку.
І що ж нам робити, щоб речі що було на початку
зі списку, чи не так?
Ми перезапису щось.
Так де ж ми ставимо, що?
Так, Анна?
>> СТУДЕНТ: Де найменший число було?
>> Джейсон Хіршхорна: Так поклав початок списку, де
Найменше число було.
Таким чином, хоча цей список не в порядку, знайти найменше число, помістіть його в
початок списку, покласти початок списку, де
Найменше число було.
Маркус, ви можете перефразувати цю лінію в той час як список не в порядку?
>> СТУДЕНТ: У той час як число були відсортовані?
>> Джейсон Хіршхорна: Отже, для того, щоб знаю, що номери не були
упорядковано, що ми повинні зробити?
Скільки нам потрібно пройти через цей список?
>> СТУДЕНТ: Так що я думаю цикл, або в той час як, в той час перевірили номера менше
ніж довжина списку?
>> Джейсон Хіршхорна: ОК, це добре.
Я думаю, що misphrased моє питання погано.
Я просто намагаюся отримати на ми збираємося повинні піти
через весь список.
Таким чином, хоча цей список не в порядку, для мене це важко зіставити на.
Але в принципі, це, як Я думаю про це.
Пройдіть весь список, знайти найменше число, помістіть його в
починаючи - насправді, ви праві.
Скажімо їх обох.
>> Таким чином, хоча цей список не в порядку, ми потрібно йти через весь список
один раз, знайти найменше число, місце це на початку списку, покласти
початок списку, де Найменше число було, а потім, якщо
Список як і раніше не в порядку, у нас повинні пройти через це
Процес знову, чи не так?
Ось чому вибір роду, середа Великий-O відбіркового роду, хто?
>> СТУДЕНТ: Н в квадраті.
>> Джейсон Хіршхорна: Н в квадраті.
Тому що, як Маркус і я просто зрозумів, тут, ми збираємося повинні
пройтися по списку список кількість разів.
Так переживає щось Довжина п п число разів
насправді н квадрат.
>> Так що це наш псевдокод.
Це виглядає дуже добре.
Хто-небудь є які-небудь питання про псевдокоде?
Тому що насправді вибір роду повинні ймовірно, прийти 12:59, коду з
псевдокод.
Тому всі питання про Логіка псевдокоде?
Будь ласка, попросіть його зараз.
>> Рода Вибір - в той час як список з порядку, ми збираємося пройти через це
і знайти найменше кожен раз і поклав його в передній.
Таким чином, хоча цей список не в порядку, може небудь дати мені цей рядок коду, який
не дав мені пару рядків коду ще, будь ласка?
Це звучить як що?
>> СТУДЕНТ: Це цикл.
>> Джейсон Хіршхорна: Це звучить подобається цикл.
Добре, ви можете дати мені для циклу?
Для -
>> СТУДЕНТ: я дорівнює 0.
>> Джейсон Хіршхорна: я або -
що ж нам не вистачає?
Те, що відбувається прямо тут?
>> СТУДЕНТ: Int.
>> Джейсон Хіршхорна: Абсолютно вірно.
(INT = 0; -
>> СТУДЕНТ: <п; я + +).
>> Джейсон Хіршхорна: прибив його, Джефф.
Ми збираємося за списком, чи не так?
Ми бачили, що код раніше.
Прекрасно.
Так давайте поставимо наші фігурні дужки тут.
Я збираюся поставити деякі Фігурні дужки тут.
>> Таким чином, хоча це 0, ми повинні піти через весь список.
Таким чином, кожен раз, коли ми пройдемося за списком, що ми хочемо, щоб відстежувати?
>> СТУДЕНТ: Якщо будь-які свопи зроблені.
>> Джейсон Хіршхорна: Знайти найменше число.
Таким чином, ми, ймовірно, слід відстежувати найменше число кожного разу.
Так лінія я можу зробити, щоб відстежувати найменшого числа?
Aleha, як я можу тримати трек-то?
>> СТУДЕНТ: Почніть нову змінну.
>> Джейсон Хіршхорна: Почніть нову змінну.
Так давайте створимо змінну.
Який вид?
>> СТУДЕНТ: Int.
>> Джейсон Хіршхорна: Int.
Давайте назвемо це найменший.
І те, що робить його рівним, коли ми тільки починають свою діяльність?
Ми не пішли по списку ще.
Ми знаходимося в першій частині список в наш перший раз до кінця.
Що його рівним, найменше число?
>> СТУДЕНТ цінностей, які я.
>> Джейсон Хіршхорна: цінностей, які я.
Це звучить цілком правильно, чи не так?
Найменше число на початку де ми знаходимося.
Так що тепер у нас є маленький, і ми повинні пройти через весь список і
порівняти це маленький з усім іншим.
Так що ми йдемо за списком знову?
Майкл?
>> СТУДЕНТ: Вам потрібно зробити другий цикл.
>> Джейсон Хіршхорна: Інший цикл.
Давайте зробимо це.
Дайте мені код.
>> СТУДЕНТ: Для циклу -
для найменших -
просто Int J, не могли б ви сказати?
= 0; таким чином, що -
>> Джейсон Хіршхорна: Ну, якщо ми хочемо пройти через весь список -
>> СТУДЕНТ: J <п, J + +).
>> Джейсон Хіршхорна: Фантастика.
Ми збираємося пройти через цикл ще раз.
І як ми можемо знайти найменше число?
Том?
У нас є поточний найменше число, так як ми можемо знайти новий маленький?
>> СТУДЕНТ: Ми можемо перевірити, якщо найменша число у нас є більше, ніж
значення кронштейн J.
>> Джейсон Хіршхорна: Так що, якщо найменшим більше, ніж значення кронштейна у.
Так що, якщо наша нинішня маленький більше -
Я збираюся рухатися ці два рядки коду там на секунду.
Тому що, перш ніж робити які-небудь заміну, ми потрібно йти через весь список.
Так що це псевдокод повинні насправді бути поза що внутрішня циклу.
Так що через весь список.
Якщо маленький більше то значення J і що?
>> СТУДЕНТ: Тоді маленький дорівнює значення J.
>> Джейсон Хіршхорна: Фантастика.
Один швидкий питання -
в перший раз ми йдемо через цю петлю, я збирається рівнятися 0, J збирається
рівним 0, як тільки ми сюди потрапили.
Таким чином, ми збираємося порівнювати ряд собі.
Хіба що ефективніше?
Ні, це не зовсім ефективно.
Так само наша J потрібно йти від 0 до п кожен раз?
Чи завжди ми повинні перевірити через весь список?
[Нерозбірливості]?
>> СТУДЕНТ початку я замість цього.
>> Джейсон Хіршхорна: J банку почати з чого?
>> СТУДЕНТ: я.
>> Джейсон Хіршхорна: J можете почати з I.
Так що тепер ми порівнюємо починаючи з тією, яку ми перебуваєте.
Але навіть тоді, є те, що в якості ефективним, наскільки це можливо?
>> СТУДЕНТ: + 1.
>> Джейсон Хіршхорна: + 1, здається, найбільш ефективним, тому що ми
вже є я.
Ми про те, що, як маленький в рядку 15.
Ми збираємося почати з наступний автоматично.
Так ми проходимо цикл.
Ми підемо через кожен раз.
Ми підемо через кількість разів.
Тепер ми отримали через це внутрішня циклу.
У нас є найменше значення рятує.
Нам потрібно, щоб помістити його на початку списку.
Так як я можу розмістити його на початку списку?
Що таке змінна, яка посилається на початку списку?
Ми перебуваємо в цій зовнішньої цикл, ну і що відноситься до
початку списку?
>> СТУДЕНТ цінностей, які я.
>> Джейсон Хіршхорна: Абсолютно вірно.
Значення я це початок -
або шкода, не почало.
Це було оману.
Це місце, де ми знаходимося на початку несортоване частину списку.
Так оцінює я.
А що значить, що рівні?
>> СТУДЕНТ: Найменший.
>> Джейсон Хіршхорна: Значення я дорівнює що?
>> СТУДЕНТ: Найменший.
>> Джейсон Хіршхорна: Найменший.
Абсолютно вірно.
Таким чином, ми помістивши його на початку зі списку, і тепер ми повинні поставити
початок списку, де найменше число було.
Так як я можу написати, де Найменше число було?
Значення що?
>> СТУДЕНТ: 0.
>> Джейсон Хіршхорна: Невеликий число це на 0?
>> СТУДЕНТ: Так.
>> Джейсон Хіршхорна: Що робити, якщо маленький число було наприкінці
це несортоване список?
>> СТУДЕНТ: На жаль, якою було питання?
>> Джейсон Хіршхорна: Де найменше число?
Ми взяли найменший і поклав його на починаючи з цієї лінії прямо тут.
>> СТУДЕНТ: Він повинен мати збережена в деяких -
>> СТУДЕНТ: Значення J.
>> Джейсон Хіршхорна: Ну, це не обов'язково значення J.
Це навіть не існує на даний момент.
>> СТУДЕНТ: Ви повинні оголосити змінна раніше і
потім призначити його -
коли ви знайдете найменше число, призначити індекс цього числа в
деяка змінна або щось на зразок цього.
>> Джейсон Хіршхорна: Так може ви говорите, що знову?
>> СТУДЕНТ: Отже, де ви заявили Int маленький, ви повинні також оголосити Int
найменший індекс = я, або щось в цьому роді.
>> Джейсон Хіршхорна: То де я десяткового маленький, я повинен не тільки відслідковувати
вартості, але розташування.
внутр smallest_location = в цьому так, ми просто роблять я.
Нам потрібно знати, де він знаходиться.
Ми дісталися до кінця коду, і ми зрозумів, що ми поняття не мали, де це було.
І так знову, ми відображення це на 12:59.
Ви, хлопці, що кодують це на свій страх і волі ймовірно, отримати до тієї ж проблеми.
Як, чорт візьми, я знаходжу це?
І тоді ви зрозумієте, почекайте, я потрібно відстежувати, що.
>> Так що, якщо маленький більше ніж значення J.
Ми встановили маленький дорівнює значень у.
Що ще нам потрібно змінити?
Костянтин, що ще зробити, ми повинні змінити?
>> СТУДЕНТ: Розташування.
>> Джейсон Хіршхорна: Абсолютно вірно.
Так дайте мені цей рядок в коді.
>> СТУДЕНТ: smallest_location = у.
>> Джейсон Хіршхорна: Абсолютно вірно.
А потім впав в кінці, якщо ми хочемо поклав початок списку, де
найменше число було, як ми див. де
Найменше число було?
Маркус?
>> СТУДЕНТ: Найменше число було розташований в маленькій місці.
>> Джейсон Хіршхорна: Так при значеннях smallest_location.
І що ж ми поставити там?
Початок Список, що це таке?
>> СТУДЕНТ: Ну, ми дійсно не знаємо, більше, тому що ми переписав.
Так що це помінялися місця з цих двох ліній?
При перемиканні ці дві лінії навколо.
>> Джейсон Хіршхорна: Отже, ми не більше, тому що ми скинути лінію
до значень я до маленьких.
Таким чином, ми втратили цю початкове значення.
Так ви сказали своп ці дві лінії.
Так що тепер поклав початок списку де найменше число було.
Так smallest_location дорівнює цінності я.
Це рухається початку цього несортоване частину списку на
маленький місце.
А потім в значення я ми рухаємося що найменше число.
>> Чи має це сенс, чому ми повинен був зробити, що своп?
Ми б переписані це значення - інша справа, ви б, напевно,
зрозумів, і знайти в ВВП.
Таким чином, ми подбали всі псевдокод.
Чи є щось ще, що ми потрібно написати тут?
Хто-небудь може думати ні про що?
>> СТУДЕНТ: Як ви знаєте, коли ви закінчите?
>> Джейсон Хіршхорна: Як ми знаєте, коли ми закінчимо?
Велике питання.
Так як же нам знати, коли ми закінчили.
>> СТУДЕНТ: Створіть змінну, щоб тримати рахунок з, якщо є своп зробив чи ні
і пройти через прохід.
>> Джейсон Хіршхорна: ОК.
Це було б працювати в бульбашкового сортування.
Але для вибору роду, якщо ми не будемо зробити обмін, що може бути просто
тому що найменше значення в ньому його правильне розташування.
Ми могли б мати список 1, 2, 4, 3.
Вдруге через ми не робитиме ніяких свопів.
Ми будемо на числа 2, але ми будемо ще потрібно, щоб продовжувати йти.
Так що нам потрібно відстежувати, коли ми зробили, або ж ми просто хочемо, щоб піти
поки це не буде закінчено?
>> СТУДЕНТ: Ми можемо просто піти поки вона не буде закінчена.
>> Джейсон Хіршхорна: Ми можемо просто йти, поки це не закінчено.
У бульбашкового сортування, ви абсолютно праві, Джефф і Aleha, з вашим рішенням -
це здорово, щоб відстежувати, скільки свопи ви зробили, тому що в міхур
роду, якщо ви насправді не роблять ніяких свопів, ви закінчите, і ви можете можливо скоротити ваші
Проблема трохи вниз.
Але для вибору роду, ви, дійсно треба йти до кінця в
список кожен раз навколо.
>> Таким чином, це те.
У нас є дві хвилини залишилося.
Давайте зробимо все.
Дозвольте мені просто відкрити Знайти тут і зробити упевнений, що я насправді виклику -
Я не називаю бульбашкову сортування.
Давайте змінимо це в мій вибір роду.
зробити все. / знайти.
Давайте дізнаємося 42.
На цей раз ми збираємося пройти несортоване список, тому що вона може вирішити
по-перше, відповідно до кодом знайти - повинні розібратися Перший, що використовують нашу функцію сортування, а потім
шукати щось.
Пальці схрещені всіх.
>> О боже мій.
Ей, моє серце билося.
Так що це правильно.
Справді, якщо ми побігли це більш широко, код, наскільки я можу
сказати, абсолютно правильно.
Є деякі пропозиції, Я б за вас.
Наприклад, 15 і 16, здається трохи зайвим.
Здається, що ви не обов'язково необхідно зберегти і ті.
Якщо у вас є найменше місці, ви можете легко знайти найменше значення по
просто набравши значення I.
>> Так що, якщо б я мав бути класифікації коду, який я фактично буде, я б
ймовірно, зняти точку, якщо ви включені обидва з них, тому що вам
не потрібно обох з них.
Якщо у вас є місце, ви можете дуже легко отримати значення.
І, здається, трохи дивно зберігати їх обох.
Може бути, навіть не взяти точку, але звичайно коментувати, що це може бути,
НЕ стилістичний вибір Ви повинні зробити.
Звичайно, код і раніше працює на відмінно.
>> Тому, на жаль, ми не зробили дістатися до бульбашкового сортування.
Я шкодую про це.
Ми зробили фінішну вибору роду.
Хто-небудь є які-небудь остаточні питання про вибір роду?
>> Добре, перш, ніж ми качан, я хочу, щоб ви відкрити свій Chrome браузер.
На жаль, це було просто кричущим плагін для одного типу інтернет-браузера.
Ви можете відкрити будь-який тип браузера, але це, ймовірно, буде Chrome.
І піти в цей наступному веб-сайті -
sayat.me/cs50.
Якщо ви не друкуєте на комп'ютері Прямо зараз, ви чітко
не роблю це, Том.
>> І, будь ласка, зробити це або прямо зараз або протягом наступного години -
дати мені деяку зворотний зв'язок.
Це тільки розділ два.
У нас є ще багато разом, тому я є багато місця для поліпшення.
Я сподіваюся також зробив деякі речі добре.
Таким чином, ви можете змусити мене відчувати себе все так погано, але якщо Ви також хочете, щоб дати мені смайлик
особа, я був би вдячний, що добре.
Заповніть, що дюйма
>> І з однієї хвилини наліво, що було три тижні.
Я буду стояти за деякий час якщо у вас є які-небудь питання.
Я побачу вас, хлопці в лекції завтра.