[Powered by Google Translate] [Частина 4] [менш комфортно]
[Nate Хардісон] [Harvard University]
[Це CS50.] [CS50.TV]
>> Гаразд, ласкаво просимо до розділу.
У розділі цього тижня ми збираємося зробити кілька речей.
Ми йдемо до першого поставленого завдання резюме 2,
яка є набором Цезаря і Віженер проблеми.
І тоді ми будемо занурюватися в огляд Вікторина 0
і витратити трохи часу, резюмуючи, що ми говорили про
У кожному з лекцій досі, і ми також робимо кілька проблем
від вікторинах попереднього року.
Таким чином, ви, хлопці, є хороший спосіб підготуватися до цього.
>> Для початку, я завантажив кілька хороших рішень
за попередній набір проблем, завдань 2, в цьому просторі.
Якщо ви, хлопці, всі потрапили на цю посилання,
і якщо ви клацніть своє ім'я та натисніть на моєму першому перегляді
Ви побачите caesar.c, а це саме те, що я дивлюся.
Давайте поговоримо про це дуже швидко.
Це всього лише приклад вирішення.
Це не обов'язково ідеальне рішення.
Є багато різних способів, щоб написати це,
але є кілька речей, які я хотів би підкреслити
що я бачив, як я сортуванню, найпоширеніші помилки, які я думаю,
це рішення робить дуже хорошу роботу в зверненні.
>> Перший з якоїсь заголовок коментаря у верхній частині.
У рядках з 1 по 7 ви бачите деталі,
що саме ця програма робить.
Хороша стандартна практика, коли ви пишете код C
незалежно від того, ваша програма міститься в одному файлі або
Чи він розбитий на кілька файлів, щоб мати якийсь
орієнтовна коментар на самому верху.
Це теж для людей, які виходять і написати код в реальному світі.
Це де покладуть інформацію про авторське право.
Нижче наведені # включає в себе.
За рядку 16 є ця # визначити, що ми повернемося в тільки трохи.
І ось одного разу функція починається, як тільки основні старти,
тому що ця програма була все що містяться в одній функцією
Найперше, що відбувається, і це дуже ідіоматичні і типові програми C
, Яка приймає в аргументи командного рядка-це те, що він одразу перевіряє
>> за кількістю аргументів, агдс.
Ось тут ми бачимо, що ця програма очікує 2 аргументи точно.
Пам'ятайте є те, що перший аргумент, що це особливий
це завжди ім'я програми, яка запускаються,
ім'я виконуваного файлу.
І так, що вона робить це не дозволяє користувачеві запустити програму
з більшою або меншою кількістю аргументів.
Тому ми хочемо, щоб перевірити це відразу тому, що
ми не можемо фактично отримати доступ до цієї ARGV масиву прямо тут надійно
поки ми не перевіряли, наскільки вона велика.
>> Одна з найбільш розповсюджених помилок я бачив, був би люди відразу йдуть в
і захоплення ARGV [1].
Вони захопити ключові аргументи з масиву і не до я перевірити на ньому,
а потім вони зроблять тест на агдс, а також наступний тест,
Чи не першим аргументом було дійсно ціле, в той же час,
і це не працює, тому що у випадку, якщо немає аргументів,
Ви будете захопити аргумент, що там немає або спробу захопити один, що ні.
>> Інша велика річ, яку ви повинні були помітити, що
Ви завжди хочете, щоб роздрукувати якийсь корисний повідомлення про помилку
користувачеві орієнтуватися них.
Я впевнений, що ви всі запуску програм, де раптом він виходить з ладу,
і ви отримаєте цей смішний маленький діалог, який спливає і говорить:
щось страшенно загадковим і, можливо, дає вам код помилки або щось в цьому роді
що не має сенсу.
Це де ви дійсно хочете, щоб забезпечити щось корисне
і орієнтовані на користувача, так що, коли вони запустити його вони йдуть "О," обличчя долонею.
"Я точно знаю, що робити. Я знаю, як це виправити".
>> Якщо ви не друкувати повідомлення, то в підсумку ви насправді
залишаючи користувачеві піти вивчати вихідний код
щоб з'ясувати, що пішло не так.
Є також кілька разів, що ви будете використовувати різні коди помилок.
Тут ми просто використовували один говорять, що сталася помилка,
відбулася помилка, сталася помилка.
Більше програм, часто програм, які викликаються іншими програмами,
повернеться якийсь спеціальний код помилки в різних сценаріях
програмно повідомити, що ви б інакше
просто використовувати хороший англійський повідомлення для.
Cool.
Як ми працюємо вниз, ви бачите, ми витягти ключ із.
Ми перевіряємо, щоб побачити, якщо ключ підходить.
Ми отримали повідомлення від користувача.
Тому ми робимо це в цьому циклі зробити в той час і це те, що ми покриємо
В небагато, але виявляється, що якщо ввести контроль D
коли ви одержуєте GetString рядки на термінал
що це насправді робить це він посилає спеціальний символ
в програмі.
Це називається ELF або символ кінця файлу.
І в цьому випадку, наша рядок повідомлення буде нульовим,
так що це було не те, що ми перевіряли в завдання поставив перед собою.
>> Але, як ми продовжимо, тепер, коли ми почали говорити про покажчики
і динамічне виділення пам'яті в купі,
перевірка на нуль щоразу, коли у вас є функція, яка може
повернути нульове значення, як те, що ви хочете отримати в звичку робити.
Це тут, перш за все для ілюстрації.
Але коли ви бачите GetString в майбутньому,
так від проблеми Set 4, Ви будете хотіти мати це на увазі.
Знову ж таки, це не є проблемою для задач 3 або, так як ми не покривається ще.
І, нарешті, ми добираємося до цієї частини, де ми перейдемо до основної цикл шифрування,
і є кілька речей, що тут відбувається.
По-перше, ми перебору всієї рядки повідомлення.
Тут ми зберегли StrLen виклик у стан,
які багато хто з вас вказали не великий шлях.
Виявляється, в цьому випадку він також не велика,
Частково тому, що ми, змінивши вміст самого повідомлення
всередині циклу, так що якщо у нас є повідомлення, що це 10 символів,
Вперше ми починаємо цикл, що для StrLen повернеться і що?
10.
>> Але якщо ми потім змінити повідомлення, сказати, що ми змінити своє 5-й символ,
і кидаємо в \ 0 символ в 5-ій позиції,
на подальшою ітерації StrLen (повідомлення) не повернеться, що він зробив
самий перший раз, коли ми повторний,
але замість цього повернути 5, тому що ми кинули в тому, що нульовий термінатор,
і довжиною струни визначається
становищем, що \ 0.
У цьому випадку, це відмінний спосіб піти, тому що ми змінивши її на місце.
Але ви помітили, що це насправді дивно проста для шифрування
якщо ви можете отримати математику правильно.
Все, що потрібно, щоб перевірити, чи справді лист, що ви дивитеся на
це верхній або нижній регістр.
>> Тому ми тільки повинні перевірити, що і у нас немає для перевірки
це альфа справа в тому, що
Якщо символ у верхньому регістрі або, якщо це рядкова
то це безперечно букви,
тому що у нас немає прописних і рядкових знаків.
Інша річ, яку ми робимо, і це трохи складно-
це ми змінили стандартний шифр Цезаря формулою
, Які ми дали в специфікації поставленого завдання.
У чому різниця тут у тому, що ми вичитали
У верхньому регістрі капіталу випадок, і тоді ми додаткового капіталу
Резервне в кінці.
>> Я знаю, деякі з вас зробили це в коді.
Хто-небудь з вас зробити це в ваших уявленнях?
Ви зробили це. Чи можете ви пояснити, що це робить, Sahb?
Шляхом вирахування його, тому що ви зробили мод відразу після нього,
ви повинні прийняти його, так що таким чином ви отримаєте [кашель] позиція.
А потім, додавши його пізніше ви перейшла той, який ви хотіли.
Так, саме так.
Що Sahb сказав, що коли ми хочемо додати
наше повідомлення, і наші ключові разом
, А потім мод, який, мод, який по NUM_LETTERS,
якщо ми не будемо масштабувати наші повідомлення у відповідні 0 до 25 Діапазон перше,
Потім ми могли б у кінцевому підсумку отримати дійсно дивний номер
тому, що цінності, які ми дивимося на те, коли ми дивимося на повідомлення [я],
Коли ми дивимося на го характеру наших текстових повідомлень,
це значення десь у цьому від 65 до 122 Діапазон
на основі ASCII значення для верхнього регістру від А до Z рядкові.
І тому, коли ми мода це на 26 або NUM_LETTERS,
так як це був наш # визначити в правому верхньому тут,
що збирається дати нам значення, яке в 0 до 25 діапазон,
і нам потрібен спосіб, щоб потім масштабувати, які підтримують
і отримати його у відповідні ASCII діапазону.
Найпростіший спосіб зробити це, щоб просто масштабувати всі вниз
в 0 до 25 Діапазон Почнемо з того,
, А потім перекласти все назад в кінці.
>> Ще одна поширена помилка, що я бачив, люди біжать в тому, що
якщо ви насправді не зробити це прямо зараз масштабування
і ви додаєте повідомлення і ключові разом і додати їх, скажімо,
в символ змінної, проблема з цим
це повідомлення, оскільки [я] є відносно велике число, щоб почати з-
пам'ятайте, що це щонайменше 65, якщо це символ верхнього регістру-
якщо у вас є великий ключ, скажімо, щось на зразок 100,
і ви додаєте ці 2 разом в підписаних символ ви збираєтеся отримати переповнення.
Ви збираєтеся отримати значення, яке перевищує 127,
, Яка є найбільшим значення, символ може зберігати змінна.
Знову ж таки, чому ви хочете зробити таку річ з самого початку.
Деякі люди отримали навколо цієї справи робити, якщо ще й тестування
щоб побачити, якщо вона буде переповнення перш ніж зробити це,
але таким чином отримує від усього цього.
І тоді в цьому рішенні ми виводимо весь рядок в самому кінці.
Інші люди роздрукувати символ за один раз. Обидва є дивовижними.
На даний момент, ви, хлопці, є які-небудь питання, жодних коментарів з цього приводу?
Що вам подобається, що вам не подобається?
>> У мене було питання.
Може бути, я пропустив його під час вашого пояснення, але як ця програма
пропустити простору для підключення ключа до довжини тексту?
Це всього лише шифр Цезаря. >> Ех, шкода, що так.
Так, ми бачимо, що.
В шифр Цезаря ми обійшли, тому що
Ми тільки перевернув символів.
Ми тільки повернути їх, якщо вони були верхньому або нижньому регістрі.
Ви, хлопці, відчував себе досить добре з цього приводу?
Ви можете скопіювати цей будинок, бери,
порівняти його з тим, що ви, хлопці написали.
Безумовно не соромтеся, надсилайте запитання на цю тему теж.
І знову ж, розумію, що мета тут з вашою проблемою встановлює
Не щоб ви, хлопці, щоб написати ідеальний код для безлічі проблем.
Це досвід. Так.
>> Повернутися до робити під час циклу, якщо він дорівнює нулю,
так нульового просто нічого не значить, вони просто натисніть Enter?
Null це спеціальне значення вказівника,
і ми використовуємо нуль, коли ми хочемо сказати,
у нас є покажчик змінної, яка вказує на немає.
І зазвичай це означає, що ця змінна, ця змінна повідомлення
порожньо, і тут, тому що ми використовуємо CS50 особливий тип рядка,
що CS50 тип рядки?
Чи бачили ви, що це таке, коли Девід відкинув капюшон в лекції?
Це фанки-це покажчик, вірно?
Добре, да. >> Це символ *.
І так насправді ми могли б замінити цю
прямо тут з символів повідомлень *,
і так GetString функція, якщо вона не успішно отримати рядок від користувача,
він не може розібрати рядок, і в одному випадку, в якому він не може розібрати рядок
, Якщо користувач вводить символ кінця файлу, контрольна D,
який не те, що ви зазвичай робите, але якщо це відбудеться,
то функція поверне це значення, як спосіб сказати
"Ей, я не отримати рядок".
Що станеться, якщо ми не ставимо повідомлення = NULL,
яких є те, що ми не робили ще?
Чому б це було тут проблема?
Тому що я знаю, що ми трохи поговорили в лекції про витоки пам'яті.
Так, давайте зробимо це, і давайте подивимося, що станеться.
>> Питання Василя Блаженного було те, що станеться, якщо ми насправді не
це повідомлення = NULL тест?
Давайте прокрутки вгору до вершини.
Ви, хлопці, можете прокоментувати це.
Насправді, я врятую його в перегляді.
Це буде 3-тя редакція.
Що ви повинні зробити, щоб запустити цю програму, вам доведеться натиснути цю значок із зображенням шестерні тут,
і ви будете мати, щоб додати аргументи до нього.
Ви повинні дати йому головний аргумент, так як ми хочемо передати в аргументі командного рядка.
Тут я збираюся дати йому номер 3. Мені подобається 3.
Тепер масштабування назад, запустивши програму.
Це працює, компіляція, будівництво.
Тут ми йдемо. Він очікує запиту.
Якщо я ввожу щось подібне привіт-де пройшло?
О, моя програма займає надто багато часу для запуску. Я був jawing занадто довго.
Ось він іде.
Зараз я набираю в привіт.
Ми бачимо, що він шифрує належним чином.
Тепер, що станеться, якщо ми робимо швидку GetString повернути NULL?
Пам'ятаєте, я казав, що ми зробили це, натиснувши управління D в той же час.
Я прокручування вгору тут. Ми будемо запускати його знову.
Будівництво. Там він йде.
Тепер, коли я вдарив управління D
Я отримав цей рядок, яка говорить opt/sandbox50/bin/run.sh, помилки сегментації.
Хіба ви, хлопці, бачили, що раніше?
>> [Студент] Чому немає->> Вибачте?
[Студент] Чому немає дампа пам'яті в цьому випадку?
Дамп це-питання чому немає дампа тут?
Питання в тому, що там може бути, але дамп являє собою файл
, Який отримує зберігається на жорсткому диску.
У цьому випадку ми відключили дампи
на бігу сервер, так що ми не були люди сегментам розломів
і створення тонн дампи пам'яті.
Але ви можете отримати.
Основні звалища така штука, що часто можна відключити,
і іноді ви робите.
Сегментація вина, щоб відповісти на ваше запитання, Василь,
говорить, що ми спробували отримати доступ до покажчика
, Які не були встановлені, щоб вказати на що-небудь.
Пам'ятайте, Бінки у відео, коли Бінки намагається
перейти до покажчика, який не вказуючи на що-небудь?
У цьому випадку я думаю, технічно покажчик вказує на щось.
Це вказує на нульовий, який є технічно 0,
але, що називається в сегменті, який не доступний
за вашою програмою, так що ви отримаєте помилку сегментації
тому що ви не доступу до пам'яті, який в діючий сегмент
як сегмент купі або стеку сегмент або сегмент даних.
Cool.
Будь-які питання про Цезаря?
>> Давайте рухатися далі. Давайте подивимося на перегляд 2 дуже швидко.
Ось Віженер.
Тут, в Віженер
Ми пройдемо через це досить швидко, тому що, знову ж таки,
Віженер і Цезаря дуже схожі.
Заголовок коментаря раніше,
# Визначити це перш уникнути використання цих магічних чисел.
Приємно те, що ми хочемо, щоб перейти до
різних алфавіту або щось на зразок цього.
Замість того, щоб йти вручну змінювати всі 26 в коді
ми могли б змінити це 27 чи кинути його вниз
якби ми використовували різні алфавіти, різні мови.
Знову ж таки, у нас є ця перевірка кількість аргументів,
і дійсно можна майже прийняти це як шаблон.
Практично кожен програмі ви повинні написати-
якщо він приймає аргументи командного рядка-деяка послідовність ліній
, Який читається як це на самому початку.
Це одне з перших випробувань розсудливість ви хочете зробити.
>> Ось те, що ми робили, було ми переконалися, що
Ключове слово дійсно було, і це була друга перевірка, що ми і зробили.
Зверніть увагу ще раз, що ми відокремилися від цього ARGC і 2.
Зверніть увагу, що в цьому випадку одна річ, яку ми повинні були зробити, було, замість
використання, щоб я, ми хотіли перевірити весь рядок,
і для того, щоб робити, що ви насправді потрібно йти по одному символу
за рядком.
Там немає хороший спосіб називати щось на ній
тому що навіть, наприклад, щоб я поверне 0
якщо він не може розібрати ціле, так що навіть не працює.
Знову ж таки, гарне повідомлення про те, користувачеві саме те, що сталося.
Тоді тут, знову ж таки, ми також обробляємо випадок, коли
Користувач вводить в елемент керування D випадковий характер.
>> І тоді Шарлотта було питання раніше про те, як нам вдасться пропустити простору
У нашому рядок тут.
Це було почасти схоже на те, що ми зробили з Myspace програми
що ми зробили в розділі, і те, як це працює
те, що ми відстежували кількість листів, які ми бачили.
Коли ми йшли через рядок повідомлення, як ми йшли по одному символу,
Ми відстежували індекс як частину нашого циклу, і тоді ми також відстежували
кількість букв, так що без спеціальних символів, без цифр, без пробілів
що ми бачили в окремій змінній.
А потім це рішення змінює ключ
щоб отримати фактичний ключ ціле, і він робить це на льоту,
Право, перш ніж він потім іде для шифрування фактичний характер повідомлення.
Є деякі рішення, які були абсолютно відмінними також
що б змінити вверх при перевірці дії ключа.
На додаток до переконавшись, що характер і ключове слово
був літери Виявилося також, що в ціле
В 0 до 25 діапазон потім пропустити того, щоб зробити це пізніше в цьому циклі.
Знову ж таки, ви бачите тут, це дійсно точно такий же код
які ми використовували в Цезарь в цій точці.
Ти робиш одне й те ж, так що реальний трюк є з'ясування того,
як включити ключове слово в ціле.
>> Одна річ, яку ми зробили тут, що кілька щільних
це ми повторили цю фразу, я думаю, ви могли б назвати його,
3 окремих рази на 58 ліній, 59 і 61.
Може хто-небудь пояснити, що саме ця фраза робить?
Це доступі характер, як ви сказали.
Так, це [нерозбірливо] символів в ключових слів,
і тому це число букв бачив, тому що ви тільки рухаючись уздовж
Ключове слово раз ви бачили лист,
так що це буде ефективно пропустити просторів тощо.
Так, саме так.
А потім, як тільки ви бачили ключове слово порожнім ви просто мода, щоб ви повернутися навколо.
Саме так. Це ідеальне пояснення.
Що Кевін сказав, що ми хочемо, щоб індекс в ключове слово.
Ми хочемо, щоб num_letters_seen характер, якщо хочете,
Але якщо num_letters_seen перевищує довжину ключового слова,
Так ми повернемося у відповідному діапазоні ми використовуємо мод оператора
ефективно обернути навколо.
Наприклад, як в короткостроковій, наше ключове слово бекон,
і це 5 букв.
Але ми бачили 6 букв в нашій текстом в цій точці
і зашифровані 6.
Ми в кінцевому підсумку доступ до num_letters_seen,
, Що на 6, мод довжина ключового слова, 5,
і таким чином ми отримаємо 1, і так, що ми будемо робити це ми будемо
доступ до першого в характері нашого ключового слова в цій точці.
>> Гаразд, будь-які питання по Віженер
перш ніж рухатися далі?
Ви, хлопці, відчував себе досить добре з цього приводу?
Круто, велике.
Я хочу, щоб переконатися, що ви, хлопці отримують шанс побачити код
що ми думаємо, виглядає добре, і є шанс дізнатися від нього.
Це буде останньою ми будемо використовувати прогалини в даний час,
і ми збираємося переходити зараз, і я збираюся піти в cs50.net/lectures
так що ми можемо зробити трохи огляду вікторини.
Кращий спосіб Я думаю, що почати робити тест огляд
повинен прийти до цієї лекції сторінці, cs50.net/lectures,
і під кожним із заголовків тиждень, так що якщо я дивлюся тут на Тижні 0,
Я бачу, що у нас є список питань, які ми обговорювали на тиждень 0.
>> Якщо будь-яка з цих тем здається незнайомій для вас
ви безумовно хочете, щоб повернутися і прочесати лекції і, можливо,
навіть побіжно лекції, дивитися їх знову, якщо ви хочете
щоб відчувати себе за те, що відбувається з кожним з цих тем.
Скажу додатково в цьому році один з прохолодних ресурси у нас є
Саме ці шорти, які ми створили, і якщо ви подивитеся на Тижні 0,
у нас немає всіх темах, але у нас є досить багато з них,
деякі з них складніше, тому спостерігати ці шорти знову
це хороший спосіб, щоб ви до швидкості.
Зокрема, я збираюся поставити в роз'єм для 3 на дні, так як я зробив ті.
Але якщо ви боретеся з двійкової, біти, шестигранні, в такому ж роді,
двійкових є прекрасним місцем для початку.
ASCII ще один, це добре, щоб переглянути теж.
Ви навіть можете слідкувати за мною в 1,5 рази швидкість, якщо я буду занадто повільним для вас.
Так як це відгук, не соромтеся робити це.
>> Просто, щоб почати дуже швидко, ми збираємося пройти через пару таких вікторини проблеми
просто швидко відтоку через них.
Наприклад, давайте подивимося на проблеми 16, що у мене прямо тут на дошці.
У нас це наступний розрахунок в двійковій,
і ми хочемо показати яку роботу.
Гаразд, я збираюся дати цьому постріл.
Ви, хлопці, повинні слідувати разом з папером,
і ми будемо робити це дуже швидко.
Ми хочемо, щоб виконати наступні розрахунки в двійковій системі.
У мене 00110010.
І я збираюся додати до нього 00110010.
Для геніїв математики слідуючи вздовж будинку,
Це фактично множенням на 2.
Давайте почнемо.
Ми збираємося слідувати тій же алгоритм того, що ми робимо
коли ми додаємо десяткових чисел.
Дійсно Єдина різниця в тому, що ми петля назад навколо
коли у нас буде 1 + 1, а не тільки ми отримаємо до 10.
>> Якщо ми почнемо з правого боку, дуже швидко, що перша цифра?
[Студент] 0. >> [Nate H.] 0.
Великий, друга цифра?
[Студент] 1.
[Nate H.] Це 1? 1 + 1 є?
[Студент] 10.
[Nate H.] Точно, так в чому ж цифру, що я пишу прямо під 2 одиниці складаються?
[Студент] 1, 0 або 0, а потім провести 1.
[Nate H.] 0 і нести 1, точно.
Далі один вгору, Василь, ви вгору.
Який третій? >> [Василь] 1.
[Nate H.] 1, досконалим. Кевін?
[Кевін] 0. >> [Nate H.] 0, Шарлотта?
[Charlotte] 0. >> [Nate H.] Так, і що мені робити?
[Студент] 1.
[Nate H.] І що мені робити? І тоді я несу 1.
Perfect, Sahb? >> [Sahb] Тепер у вас є 1.
[Nate H.] І я роблю щось тут?
[Sahb] Тоді для наступного у вас є 1, тому що ви переноситься на 1.
[Nate H.] Великий, так що тут ми можемо закінчити це.
Cool.
[Студент] Лі 0 + 0 = 0?
0 + 0 = 0.
1 + 1, як ви сказали, 10, або 1, 0, а.
10 є неправильним, тому що мені 10 означає число 10,
і це примха, як ми, представляючи його, коли ми пишемо це.
Уявімо число 2, 1, 0, а число 10 трохи відрізняється.
>> Що почасти добре про бінарних те, що є насправді не так багато
випадках потрібно вчитися.
Там в 0 + 0 = 0, 0 + 1 = 1,
1 + 1 = 0, а потім виконати 1,
а потім ви можете побачити тут, на третьому стовпці праворуч
у нас було це 1, 1, 1.
А 1 + 1 + 1 1,
і ви несете іншу 1.
Коли ви робите двійковій Крім того, досить проста.
Я зроблю ще пару цих розсудливість перевірити себе
перш ніж ви йдете, тому що це
ймовірно, те, що ми бачимо на вікторину.
Тепер давайте зробимо це наступного також.
Давайте зробимо проблеми 17.
Ми збираємося перетворити наступним двійкового числа в десяткове.
У мене 10100111001.
Пам'ятаєте, в двійковому відео, яке я зробив
Я йшов через пару прикладів, і я показав, як
все працює, коли ви робите це в десятковій системі.
Коли ви працюєте в десяткове подання Я думаю, що ми
На даний момент в нашому житті так побіжно говорить на це, що
це досить легко замазати механіку того, як вона дійсно працює.
>> Але щоб зробити швидке резюме, якщо у мене є номер 137
В дійсності це означає і знову ж таки, це в десяткове подання-
число 137 у десятковій означає, що у мене є 1 х 100 + 3 х 10 + 7 х 1.
Це все перебування на екрані.
І потім, якщо ви подивитеся на ці цифри прямо тут,
100, 10 і 1, ви бачите, що вони насправді всі повноваження 10.
У мене є 10 ², 10 ¹, і від 10 до нуля.
У нас подібного роду речі в двійковій,
винятком того, що наша база, як ми його називаємо, становить 2 замість 10.
Ці 10s, що я написав тут на дні,
це 10 ², 10 ¹, 10 до нуля, 10, наша база,
і показник, 0, 1, або 2,
випливає з положення цифри в номері, що ми пишемо.
1, якщо ми подивимося на це, це 1, у 2-й позиції.
3 в 1-й позиції, а 7 знаходиться в 0-й позиції.
Ось як ми отримаємо різні показники нижче для нашої бази.
>> Після всього цього МИ-насправді, ви знаєте, що?
Ми зробимо все, де ж мій скасувати кнопку йти?
Там він йде.
Я люблю цю річ скасувати.
Після цього я думаю, для мене принаймні
Найпростіший спосіб почати перетворення двійкового числа
або шістнадцяткове число, де база знаходиться в 16
, А не 10 або 2, щоб йти вперед і пишемо
баз і індексів для всіх чисел в моїй двійкового числа у верхній частині.
Якщо ми почнемо зліва направо знову,
яка є своєрідною парадоксально,
Я зміню Back To Black тут, у нас є 2 до 0-я позиція,
а то у нас 2 ¹, 2 ²,
а потім від 2 до 3, від 2 до 4, 2 до 5, 6,
7, 8, 9 і 10.
Ці цифри я виписав всі показники.
Я лише написав баз тут в перші 3 тільки для простору.
>> На даний момент я збираюся йти вперед і насправді я збираюся стерти
речі, які ми зробили в десятковій, якщо це нормально.
Ви все зрозумів.
Ті з вас, дивитися онлайн Я впевнена, що зможе перемотати мене, якщо хочете.
Перемикання назад на перо.
Отже, що ми можемо зробити, якщо ви, хлопці, не повністю до швидкості на свої сили 2,
це абсолютно здорово.
Це буває. Я розумію.
Я колись на співбесіду, де мені сказали, що я повинен знати всі ступені числа 2
вгору через 2 до 30.
Це була не робота в мене є.
У будь-якому випадку, ви, хлопці, можете йти вперед і робити математику тут,
але з бінарними це дійсно не має сенсу,
і також не має сенсу з десяткової або шестнадцатеричной або,
робити математику, де у вас є нулі.
Ви можете бачити, у мене 0 тут, сюди 0, 0 тут, 0 тут, 0 тут, 0 тут.
Чому це могло б ніякого сенсу робити фактичні математики
Для розрахунку відповідної потужності 2 на цю посаду?
Саме так, як сказала Шарлотта, це буде 0.
Міг би також зекономити час, якщо обчислення ступеня числа 2 не є вашою сильною стороною.
У цьому випадку нам потрібно тільки обчислити його для 2 до 0, що-?
[Студент] 1.
[Nate H.] 1, 2 до 3, який є-?
[Студент] 8. >> [Nate H.] 8.
Від 2 до 4?
[Студент] 2. Мені дуже шкода, 1.
[Nate H.] 2 до 4, 16, точно.
Від 2 до 5, Кевін? >> 32.
[Nate H.] 32, від 2 до 8?
[Студент] 32 х 8, 256.
[Nate H.] Perfect.
І від 2 до 10?
[Студент] 1024.
[Nate H.] Так, 1024.
>> Після того як ми отримали ці цифри ми можемо підвести їх все.
І це, де це дійсно важливо зробити кілька речей.
Один з них йдуть повільно і перевірити вашу роботу.
Ви можете сказати, що є 1 в кінці цього числа,
так що я обов'язково повинні отримати непарне число, як мій результат,
тому що всі інші збираються бути парними номерами
враховуючи, що це двійкове число.
Інша річ, яку потрібно зробити, це якщо ви дістатися до цієї точки на випробувальному
і ви написали її так далеко
і ви працюєте поза часом
подивіться на кількість очок, що ця проблема стоїть.
Ця проблема, як ви можете бачити, якщо я сальто назад з моїм ноутбуком дійсно швидко-
ця проблема стоїть 2 очки, так що це не з того
Ви повинні йти через, якщо ви дійсно мало часу.
Але ми будемо повернутися до iPad, і ми будемо пройти через це дуже швидко.
>> Мені подобається робити невеликі числа спочатку
тому що я вважаю, що простіше.
Мені подобається 32 і 8, тому що вони йдуть разом досить легко, і ми отримуємо 50.
16 і 1 отримує 17.
Там ми отримаємо 57,
і тоді ми зможемо зробити все інше з цього, так що ми можемо зробити, 57, 156.
Підемо.
Людина, добре, давайте подивимося.
У нас було 57, 256 і 1024.
На даний момент, я б просто пройти.
Я поняття не маю. Я чітко потрібно читати на цьому.
7, 6, 4, Ви отримуєте 17.
1, 5, 5, 2, 13.
Тоді ми отримаємо 3, а потім ми отримуємо 1.
1337.
Пасхальне яйце, ніхто?
Ніхто визнати цей номер?
Кріс визнається числа. Що це значить, Кріс?
[Chris] Leet.
Leet, так що якщо ви подивитеся на це, схоже, Літ.
Хакер речі. Слідкуйте за такого роду речі по середньострокового або тест, а.
Якщо ви бачите такі речі, і ви ставите питанням "А"
, Що може насправді щось означають.
Я не знаю. Девід любить покласти його дюйма
Це хороший спосіб перевірити його осудність.
Як добре, я бачу, що відбувається.
>> Ось тиждень 1 0/Week речі.
Якщо повернутися до наших ноутбуком зараз,
зменшити масштаб, і пару інших речей.
Там в ASCII, які ми робили багато з проблемою набору.
Це поняття капіталу A. Що це насправді?
Знаючи це десяткове число.
65 є те, що він відображається в таблиці ASCII,
і ось тому, як комп'ютер пише він,
і це, як ми вже сходить з фактичної записи
характер капіталу і характер нижнього регістра
У деяких з цих рішень і проблема набору, що ви робили.
Кілька інших речей.
У нас є заяви, логічні вирази, умови, цикли, змінні і потоків.
>> Ті, все, здається, має сенс по більшій частині?
Деякі з цієї термінології трохи наляканим в рази.
Мені подобається думати, заяви, як здебільшого те, що закінчується крапкою з комою.
Такі заяви, як х = 7, яка встановлює змінну
Імовірно називається х = 7.
Імовірно х також тип, який може зберегти номер 7,
так що Int або, можливо, теркою або коротка або символ,
щось на зразок цього.
Логічний вираз використовує ці подвійні одно
і вибуху дорівнює або не дорівнює, менше, більше, ніж,
менше або дорівнюють, все в такому ж роді.
Умови тобто, якщо інше звітності.
Я пам'ятаю, що ви не можете мати інше без відповідних якщо.
Крім того, ви не можете мати ще, якщо без відповідних якщо.
Петлі, нагадаємо 3 види петель ми були в вас молотком
за останні пару секцій та проблеми безлічі.
Використання ж час, коли ви отримуєте користувальницького введення,
використання в той час як петлі, поки певний умова істинно,
, А потім за допомогою цих циклів, якщо вам потрібно
знати, які ітерації циклу ви зараз знаходитеся, як я думаю про це.
Або якщо ви робите для кожного символу в рядку я хочу щось зробити,
Для кожного елемента в масиві я хочу щось зробити, щоб цього елемента.
>> Теми та події.
Ці які ми не так явно в C,
але пам'ятайте, це з нуля.
Це поняття, що мають різні сценарії.
Це теж це поняття трансляції події.
Деякі люди не використовували мовлення в своїх проектах на початковому етапі,
який повністю прохолодно,
але ці 2 різні способи обробки цього більше проблем, паралелізм,
який є, як ви отримуєте програм для виконання
або, здавалося б виконати в той же час?
Різні завдання, що виконуються в той час як інші завдання також працює.
Це, як ваша операційна система, здається, працює.
Ось чому, хоча, наприклад,
У мене є мій браузер працює, я також можете включити Spotify і грати пісні.
Це більше, концептуальні речі, щоб зрозуміти.
Я хотів би поглянути на теми, коротко
Якщо ви хочете дізнатися більше про це.
>> Давайте подивимося, я вважаю, що можна було б
Проблема про це в одному з них.
Знову ж таки, я думаю, що теми і події, не те, що ми розглянемо в C
тільки тому, що це значно важче, ніж в Scratch.
Ви не повинні турбуватися про неї, але, безумовно, розуміють концепції,
зрозуміти, що відбувається.
Перш ніж рухатися далі, будь-які питання на тиждень 0 матеріалів?
Кожен відчував себе досить добре?
Розуміння змінних і що таке змінна?
>> Рухаємося далі. Тиждень 1.
Кілька речей тут, які не були особливо покриті
У вікторині відгук обов'язково, а також більш концептуальні речі, щоб думати.
По-перше, це поняття про те, що вихідний код, компілятори і об'єктний код є.
Хто-небудь? Василя.
Є об'єктно-код я маю на увазі вихідного коду є те, що ви поклали в брязкіт,
і об'єктний код є те, що дзвоном ставить так, що ваш комп'ютер може прочитати програму.
Саме так.
Вихідний код код C, що ви насправді надрукувати.
Код об'єкту є те, що ви виходите з брязкіт.
Це 0 та 1, що в двійковому форматі.
Тоді що ж відбувається, коли у вас є кілька об'єктних файлів,
сказати, що ви збираєте проект або програма, яка використовує декілька файлів вихідного коду,
які за угодою надається. із розширенням файлу.
Ось чому у нас є caesar.c, vigenère.c.
Якщо ви пишете Java програми ви даєте їм розширення. Java.
Python програми мають розширення. Ру часто.
>> Якщо у вас є декілька. С файлами, ви їх компіляції.
Clang випльовує все це двійковий сміття.
Потім, тому що ви тільки хочете 1 програма
у вас є компонувальник посиланню всі ці об'єктні файли разом
в 1 виконуваний файл.
Це також те, що відбувається, коли ви використовуєте CS50 бібліотеці, наприклад.
Бібліотека CS50 є і те. Ч. файл заголовка
що ви читаєте, що # includecs50.h.
І тоді це також спеціальний файл бібліотеки двійкових
, Який було складено це 0 і 1,
і що-л прапор, тому, якщо ми повернемося до наших просторів і ми дивимося дуже швидко
на те, що тут відбувається, коли ми дивимося на нашу команду брязкіт,
те, що ми отримали, це наш вихідний код файлу прямо тут.
Це купа прапорів компілятора.
І тоді в самому кінці, ці-л прапори посилання в
фактичні двійкові файли на ці 2 бібліотеки, CS50 бібліотеки, а потім математичну бібліотеку.
>> Розуміння кожного типу файлів мети "
В процесі компіляції є те, що ви хочете, щоб мати можливість
дати хоча б детальний огляд.
Вихідний код приходить дюйма Код об'єкта виходить.
Файли Код об'єкта зв'язати разом, і ви отримаєте гарний, виконуваний файл.
Cool.
Це також, де ви можете отримати помилки в декількох точках
В процесі компіляції.
Це коли, наприклад, якщо ви візьмете цю зв'язок прапор,
CS50 прапор, і ви опустіть його в просторі або коли ви працюєте ваш код,
це де ви отримаєте помилку в стадії компонування,
і компонувальник буде сказати: "Ей, ви називається функцією GetString
, Який в CS50 бібліотеки ».
"Ви сказали мені, що в CS50 бібліотека, і я не можу знайти код для нього."
Ось де ви повинні зв'язати його, і це окрема
від помилки компілятора, тому що компілятор дивиться на синтаксис і такого роду речі.
Це добре, щоб знати, що відбувається, коли.
>> Інші речі, щоб знати.
Я б сказав, ви безумовно хочете, щоб поглянути на короткому на приведення зроблено Йорданії
щоб зрозуміти, що цілими знаходиться під капотом,
які символи знаходяться під капотом.
Коли ми говоримо про ASCII, і ми насправді дивимося на таблицю ASCII,
що це робить дає нам під капотом погляд
на те, як комп'ютер насправді являє капіталу та цифри 7
і кома і знак питання.
Комп'ютер також має спеціальні способи представлення
число 7, як число.
Це має особливе спосіб представлення числа 7 як число з плаваючою точкою,
і тих, хто дуже різні.
Приведення те, як ви кажете комп'ютер "Гей, я хочу вам конвертувати
від одного представлення до іншого поданням ".
Чому б нам не подивитися на це.
>> Я хотів би також поглянути на коротких по бібліотеках і короткий на компілятори.
Ці розмови про процес компіляції,
що бібліотека, і перейти на деякі з цих питань, які ви могли б запитав.
Питання по тиждень 1 матеріал?
Чи є теми тут, що в зневіру ви хочете, щоб покрити?
Я намагаюся, щоб продути більшість з них раніше тим, щоб ми могли дістатися до
покажчиків і зробити трохи рекурсії.
Думки?
Все, що для покриття?
Час для деяких шоколад може бути?
Ви, хлопці, працюєте через нього.
Я буду тримати потягуючи каву.
2-й тиждень.
Гарне слово, хороший виклик.
У 2-й тиждень, ми говорили трохи більше про функції.
>> У перші кілька комплектів проблеми ми дійсно не писати ніяких функцій на всіх
крім якому функція?
[Студент] Main. >> Головне, точно.
І так ми бачили різні костюми, що основною носить.
Там в одній, в якій він не приймає аргументів,
і ми просто скажемо, порожнечу в круглих дужках,
і тоді є інший, де ми хочемо приймати аргументи командного рядка,
і, як ми бачили, що там у вас є Int ARGC і ARGV масив рядків
або тепер, коли ми насправді піддається рядки, щоб бути символ *, що
ми збираємося, щоб почати писати його як символ * ARGV, а потім дужки.
У задачі Set 3, ви, хлопці, бачили купу функцій,
і ви реалізували купу функцій, малювати, дивитися вгору, сутичка.
Прототипи були написані там для вас.
>> Те, що я хотів розповісти про тут з функціями дуже швидко
є те, що існує 3 частин до них всякий раз, коли ви пишете функцію.
Ви повинні вказати тип значення, що повертається функції.
Ви повинні вказати ім'я функції, а потім ви повинні вказати
Список аргументів або списку параметрів.
Наприклад, якщо б я написати функцію, щоб підвести підсумки купу цілих чисел
, А потім повернутися до мене суму, що було б мого повернення типу
якби я хотів, щоб підвести цілих чисел, а потім повернути суму?
Тоді ім'я функції.
Якщо я піду вперед і написати в зелений, ця частина повертається типу.
Ця частина назви.
А потім в дужках
Тут я даю аргументи,
Часто скорочено аргументи, які іноді називаються параметрами для параметрів.
І якщо у вас є, ви просто вказуєте один.
Якщо у вас кілька ви розділите кожен з комою.
І для кожного аргументу, ви даєте йому 2 речі, які, Кевін?
[Кевін] Ви повинні дати типу, а потім ім'я.
І то ім'я, і ​​ім'я це ім'я, яке ви збираєтеся використовувати
посилатися на цей аргумент в межах суми функцій,
в межах функції, які ви в даний час написання.
>> Ви не повинні, наприклад, якщо я збираюся підбивати підсумки,
скажімо, масив цілих чисел-Ми робимо Int масиву,
і я дам собі деякі фігурні дужки там-
Потім, коли я передати масив в сумі функцій
Я передаю його в першу позицію списку аргументів.
Але масив, який я проходжу в не повинна мати назву обр.
Обр буде, як я посилатися на цей аргумент в тілі функції.
Інша справа, що ми повинні взяти до уваги,
і це трохи відрізняється від функції, але я думаю, це важливий момент,
є те, що в C, коли я пишу цю функцію, як
Звідки я знаю, скільки елементів у цьому масиві?
Це свого роду питання з підступом.
Ми говорили про це трохи в розділі минулого тижня.
Як мені дізнатися кількість елементів всередині масиву в C?
Чи є спосіб?
>> Виявляється, що немає ніякого способу дізнатися.
Ви повинні передати його окремо.
Існує трюк, який ви можете зробити
якщо ви знаходитеся в тій же функцією, в якій масив був оголошений,
і ви працюєте зі стеком масиву.
Але це працює, тільки якщо ви знаходитеся в тій же функції.
Після того як ви передати масив в іншу функцію або якщо ви оголосили масив
а ви ставите цей масив у купі, ви використовували Танос
і в такому ж роді, то всі ставки вимкнені.
Тоді вам насправді потрібно обійти
спеціальний аргумент або інший параметр
кажу вам, як великий масив.
У цьому випадку, я хотів би використовувати кому-Пробачте, це буде від екрану тут-
і я б перейти в інший аргумент
і називати його Int довжина по довжині.
>> Одна річ, яка може прийти на тест
просить вас написати чи здійснювати певну функцію називають щось.
Якщо ми не дамо вам прототип, так що це все справа тут,
весь цей бардак називається оголошення функції або прототип функції,
це одна з перших речей, які ви хочете, щоб прибити, якщо вона не дано
Вам відразу на вікторину.
Інший трюк я дізнався, що
сказати, що ми дійсно дають вам прототип функції, і ми говоримо: "Гей, ти повинен писати".
Усередині фігурних дужках, що у вас на тест
Якщо ви помітите, що є возвращаемого типу, і ви помітите, що тип возвращаемого
це щось інше, ніж порожнеча, яка означає, що функція не повертає нічого,
те, що ви безумовно хочете зробити, це написати
свого роду повернення заяви в самому кінці функції.
Повернення, і в цьому випадку, ми будемо ставити порожню, тому що ми хочемо, щоб заповнити порожні.
Але це отримує вас думати в правильному напрямку, про те, як я буду підходити до цієї проблеми?
І це нагадує вам, що ви будете мати, щоб повернути значення
зухвалій функції.
>> Так. >> [Студент] Чи стиль застосовується, коли ми пишемо код на вікторину?
Такі, як відступ і в такому ж роді? >> [Студент] Так.
Ні, не так багато.
Я думаю, що багато-це те, що ми будемо уточнити на вікторину в день,
але, як правило турбуючись про # включає в себе і в такому ж роді, це вид ззовні.
[Студент] Вам потрібно коментувати свої рукописні код?
Вам потрібно коментувати свої рукописні код?
Коментуючи це завжди добре, якщо ви турбуєтеся про часткову кредитної
або ви хочете повідомити про свій намір грейдер.
Але я, знову ж таки, буде уточнити на вікторину себе і в той день, вікторини,
Але я не вірю, що ви будете зобов'язані писати коментарі, немає.
Як правило, немає, але це безумовно та річ, де
Ви можете повідомити ваші наміри, як "Гей, це куди я йду з ним".
І іноді це може допомогти з частковим кредиту.
Cool.
>> Василя.
[Василь] У чому різниця між оголошенні, скажімо, внутр мову
в аргументах або параметрах у порівнянні з оголошенням змінної всередині функції?
Wow, кава пішов у дихальне горло.
[Василь] Як яке речей, які ми хочемо помістити в аргументах.
Так, це велике питання.
Як ви вибираєте те, що речі, які ви хочете помістити в міркуваннях
проти того, що речі, які ви повинні робити всередині функції?
У цьому випадку ми включили обидва цих якості аргументів
тому що вони те, що той, хто збирається використовувати функцію суми
Необхідно вказати ці речі.
>> Сума функція, про яку ми говорили, не має можливості дізнатися,
наскільки великий масив вона отримує від свого абонента або той, хто використовує суму функцію.
Він не має можливості дізнатися, як великий, що масив.
Тому ми пройти в цьому довжина прямо тут в якості аргументу
тому, що це те, що ми в основному говорять викликає функції,
хто збирається використовувати функцію суми, "Гей, ви не тільки повинні дати нам масив
цілих чисел, ви також повинні сказати нам, як великий масив, який Ви дали нам ".
[Василь] Ті, обидва будуть аргументи командного рядка?
Ні, це фактичні аргументи, які ви передаєте в функцію.
>> Дозвольте мені зробити нову сторінку тут.
[Василь] Як ім'я буде проходити-
[Nate H.] Якщо у мене є Int основних (недійсними),
і я збираюся поставити в моєму поверненні 0 вниз тут на дні,
і сказати, що я хочу, щоб викликати функцію суми.
Я хочу сказати, Int х = SUM ();
Щоб використовувати функцію суми я повинен пройти як в масиві, що я хочу, щоб підвести підсумок
і довжина масиву, так що це, де
припускаючи, що я був масив цілих чисел,
сказати, що я Int numbaz [] = 1, 2, 3,
вид використання, який порубав синтаксис там же,
те, що я хотів би зробити це в сумі я хотів би перейти в
як numbaz і № 3
розповісти суму функцію "Добре, ось масив, який я хочу, щоб ви підвести".
"Ось його розміру."
Чи має це сенс? Я відповів на ваше запитання?
>> Багато в чому це відбувається паралельна, що ми робимо з основними
коли у нас є аргументи командного рядка.
Така програма, як шифр Цезаря, наприклад, що необхідно
аргументи командного рядка не зміг би нічого зробити.
Не знаю, як для шифрування, якщо Ви не сказати йому, що ключ до використання
або якщо ви не сказали йому, що рядок, яку ви хотіли зашифрувати.
Підказка для введення, це де у нас є 2 різних механізмів
для прийняття вході в від користувача, для прийняття інформації від користувача.
Для задач 1 ми бачили, це GetInt, GetString, GetFloat шляху
наведення для введення, і це називається використанням стандартного вхідного потоку.
Це трохи відрізняється.
Це те, що ви можете зробити за один раз, на відміну від
коли ви запускаєте програму, при запуску програма працює.
Аргументи командного рядка усіх зазначених при запуску програми, запущеної.
Ми змішування двох з них.
Коли ми використовуємо аргументи функції, це так само, як аргументи командного рядка до основного.
Це при виклику функції ви повинні сказати йому,
що саме йому потрібно для того, щоб виконувати свої завдання.
Ще одна хороша річ, щоб дивитися на, і я дам вам подивитися на це у вільний час,
і вона була покрита у вікторині, було це поняття за рамки
і локальних змінних в порівнянні з глобальними змінними.
У звернути увагу на це.
>> Тепер, коли ми стаємо на цю інші речі,
3 тижні ми почали говорити про пошуку і сортування.
Пошук і сортування, принаймні, CS50,
дуже введенням в деякі з найбільш теоретична частина комп'ютерної науки.
Проблема пошуку, завдання сортування
великий, канонічної проблеми.
Як ви знаходите певного числа в масиві мільярдів чисел?
Як знайти конкретне ім'я в телефонній книзі
, Яка зберігається на вашому ноутбуці?
І тому ми введемо це поняття асимптотичного часу роботи
дійсно кількісно, ​​як довго, як важко ці проблеми є,
Як довго вони приймають рішення.
В, я вважаю, 2011 вікторині є проблема, що я думаю достоїнств
покриття дуже швидко, що це, проблема 12.
О ні, це Omega.
>> Тут ми говоримо про максимально можливу час виконання
для конкретного алгоритму, а потім мінімально можливий час виконання.
Це Omega і O в дійсності є лише ярлики.
Вони позначень клавіш для говорячи
як швидко в кращому випадку буде наш алгоритм виконання,
і як повільно в гіршому випадку буде наш алгоритм бігти?
Давайте зробимо декілька з них, і вони були також покриті
в короткостроковій про асимптотичних позначень, які я дуже рекомендую.
Джексон зробив дуже хорошу роботу.
З бінарний пошук, ми говоримо про бінарного пошуку як алгоритм,
і ми зазвичай говоримо про це з точки зору його великий O.
Що таке Big O?
Що таке мінімально можливий час виконання двійкового пошуку?
[Студент] N ²?
Закрити, я думаю, схоже на те.
Це набагато швидше, ніж це.
[Студент] Двійкові? >> Да, бінарний пошук.
[Студент] Це журнал с.
Вхід п, так що ж увійти п маєте на увазі?
Це половини цього кожній ітерації.
Точно, так і в мінімально можливий випадок,
говорять, що якщо у вас є відсортований масив
мільйон цілих чисел і номер, який ви шукаєте
це або перший елемент масиву або самий останній елемент масиву.
Пам'ятайте, що алгоритм двійкового пошуку роботи, дивлячись на середній елемент,
бачачи якщо це матч, який ви шукаєте.
Якщо це так, то великий, ви його знайшли.
>> У кращому випадку, як швидко робить виконання двійкового пошуку?
[Студенти] 1.
1, це постійне час, велика O 1. Так.
[Студент] У мене є питання. Коли ви говорите увійти п, ви маєте на увазі по відношенню до основи 2, правильно?
Так, так от інша річ.
Ми говоримо, § п, і я думаю, коли я навчався в середній школі
Я завжди вважав, що журнал був основою 10.
Так, так так, увійти підставі 2 зазвичай це те, що ми використовуємо.
Знову ж таки, повертаючись до бінарний пошук, якщо ви шукаєте або
елемента в самому кінці або елемент на самому початку,
тому що ви починаєте в середині, і тоді ви скидаєте
Залежно від того, половина не відповідають критеріям, що ви шукаєте,
і ви переходите до наступного половини і наступну половину і наступна половина.
Якщо я шукаю найбільший елемент в мільйон цілих чисел
Я збираюся вдвічі скоротити його на самий журналу 1 мільйона разів
перш ніж я, нарешті, протестувати і побачити, що елемент я шукаю
знаходиться у великій чи у вищій індекс масиву,
і що буде журнал п, увійти в 1 млн. разів.
>> Bubble роду.
Хлопці, ви пам'ятаєте алгоритм бульбашкового сортування?
Кевін, ви можете дати мені швидке повторення того, що сталося в алгоритм сортування міхур?
[Кевін] В основному це проходить через все, що в списку.
Він дивиться на перших двох.
Якщо перший більше, ніж другий його свопи них.
Потім він порівнює другої і третьої, те ж саме, свопи,
Третій і четвертий, на всьому шляху вниз.
Великі номери будуть слідувати до кінця.
І після однак багато петлі ви зробили.
Точно, так що Кевін сказав, що ми будемо спостерігати великі числа
Пузир до кінця масиву.
Наприклад, ви заперечуєте йти з нами через цю Наприклад, якщо це наш масив?
[Кевін] Ви будете приймати 2 і 3.
3 більше, ніж 2, так що ви поміняти їх місцями.
[Nate H.] Право, таким чином, ми переставляємо їх, і таким чином ми отримуємо 2, 3, 6, 4 і 9.
[Кевін] Тоді ви порівняєте 3 і 6.
3 менше, ніж 6, так що ви залишите їх,
і 6 і 4, потрібно поміняти їх місцями тому що 4 менше, ніж 6.
[Nate H.] Право, так що я отримую 2, 3, 4, 6, 9.
[Кевін] і 9 більше, ніж 6, так що ви залишите його.
І ви повернулися б через це знову.
>> [Nate H.] Чи можу я зробити у цей момент? >> [Кевін] Немає
І чому я не робив в цей момент?
Тому що він схожий на мого масив відсортований. Я дивлюся на це.
[Кевін] пройти через це знову і переконайтеся, що немає більше свопи
перш ніж ви зможете повністю зупинити.
Саме, тому потрібно продовжувати йти до кінця і переконайтеся, що немає свопів
що ви можете зробити в цій точці.
Це було дійсно просто пощастило, як ви сказали, що ми закінчили
тільки того, щоб зробити 1 прохід, і ми сортуються.
Але для цього, в загальному випадку, ми насправді повинні робити це знову і знову.
І справді, це був приклад кращому випадку,
як ми бачили в проблемі.
Ми бачили, що найкраще справу N.
Ми пішли через масив 1 раз.
Що це найгірший можливий випадок для цього алгоритму?
[Кевін] N ².
І що це схоже? Що б масив схоже, що б узяти п ² час?
[Кевін] [нерозбірливо] відсортований.
Саме, тому, якщо у мене була маса 9, 7, 6, 5, 2,
Спочатку 9 буде міхур на всьому шляху вгору.
Після 1 ітерації ми б 7, 6, 5, 2, 9.
Тоді 7 буде пузиритися, 6, 5, 2, 7, 9, і так далі, і так далі.
>> Ми повинні пройти через весь масив п раз,
і ви можете отримати трохи більш точним, ніж це
тому що як тільки ми переїхали в 9 все, аж до останньої в його можливому положенні
Ми знаємо, що ми ніколи не повинні порівнюватися з цим елементом знову.
Як тільки ми починаємо пузириться 7 до
Ми знаємо, що ми можемо зупинити лише 7 є правом до 9
оскільки ми вже в порівнянні з 9 до неї.
Якщо ви робите це в розумний спосіб це не по-справжньому, я думаю, що багато часу.
Ви не збираєтеся, щоб порівняти всі можливі [нерозбірливо] комбінаціях
кожен раз, коли ви проходите через кожну ітерацію.
Але все ж, коли ми говоримо про це верхня межа ми говоримо, що
Ви дивитеся на п ² порівняння весь шлях до кінця.
>> Давайте повернемося, і так як ми починаємо отримувати трохи менше за часом
Я б сказав, ви повинні обов'язково пройти решті частини цієї таблиці,
заповнити все це.
Подумайте про приклади. Подумайте про конкретні приклади.
Це дійсно зручно й корисно зробити.
Намалюйте його.
Це свого роду таблицю, як ви йдете через в області комп'ютерних наук
Ви повинні дійсно почати знаємо, що ці напам'ять.
Ці види питань, які ви отримаєте в інтерв'ю.
Це різні речі, які добре б знати,
і думати про тих крайніх випадках, дійсно, з'ясовуючи, як подумати про
знаючи, що для бульбашкового сортування в самий невідповідний масиву
сортувати тим, що це той, який у зворотному порядку.
>> Покажчики. Давайте трохи поговоримо про покажчики.
В останні кілька хвилин тут ми маємо
Я знаю, це те, що поряд з файлового введення / виводу, що є відносно новим.
Коли ми говоримо про покажчиків з цієї причини ми хочемо говорити про покажчики
Тому що, один, коли ми працюємо в C
ми дійсно на досить низькому рівні в порівнянні з більшістю сучасних мов програмування.
Ми насправді здатний маніпулювати перемінними в пам'яті,
з'ясувати, де вони фактично знаходяться в межах нашої пам'яті.
Після того як ви пішли на взяття операційна система класів, які ви побачите,
, Що це, знову ж, свого роду абстракцією.
Це не насправді.
У нас є віртуальна пам'ять, що приховує ці деталі від нас.
>> Але зараз можна припустити, що якщо у вас є програма,
Наприклад, коли ви почати показ шифр Цезаря програму
Я переключитися назад на мій IPad дійсно швидко-
, Що на самому початку вашої програми, якщо у вас, скажімо,
4 гігабайтами оперативної пам'яті на вашому ноутбуці,
Ви отримаєте відкладіть цей шматок, і ми називаємо це RAM.
І він починається в місце, де ми збираємося називати 0,
і закінчується в місці, яке ми будемо називати 4 гігабайт.
Я дійсно не можу писати. Людина, який зламав.
Коли ваша програма виконує
Операційна система вирізує оперативної пам'яті,
і він визначає різні сегменти для різних частин програми для житла
Тут, внизу цієї області є своєрідною нічийною землі.
Коли ви йдете трохи далі тут
у вас є насправді місце, де
Код для життя програми.
Це фактично двійковий код, виконуваний файл, що насправді завантажується в пам'ять
коли ви запустите програму, і вона живе в сегменті коду.
І, як ваша програма виконується процесором дивиться на цей сегмент коду
щоб з'ясувати, що є така інструкція?
Яка наступна рядок коду мені потрібно виконати?
>> Там також сегмент даних, і це, де ці константи рядків
отримати зберігається, що ви використовуєте.
А потім далі вгору там це місце називається купою.
Ми доступу до пам'яті там за допомогою Танос,
, А потім на самому верху вашої програми
є стек,
а от де ми грали протягом більшої частини початку.
Це не в масштабі або нічого.
Багато це дуже залежить від машини,
залежить від операційної системи, але це відносно, як всі отримують розбитий вгору.
Коли ви запустите програму, і ви оголосите змінну х
Я збираюся зробити ще одну коробку вниз, і це буде оперативної пам'яті.
І я збираюся подивитися.
Ми будемо малювати зубчасті лінії, щоб вказати, це всього лише невелика частина оперативної пам'яті
і не всі про нього, як ми малюємо на самому верху.
>> Якщо я заявляю, ціла змінна називається х,
те, що я насправді отримати відображення
, Які зберігаються в таблиці символів моєї програми
, Який з'єднує ім'я х в цю область пам'яті, яку я намалювала
прямо тут, між вертикальними смугами.
Якщо у мене є рядок коду, в моїй програмі, яка говорить х = 7
Процесор знає "О, добре, я знаю, що х життя в цьому місці в пам'яті."
"Я збираюся піти далі і написати 7 існує".
Як він знає, що розташування це в пам'яті?
Добре, що все це робиться під час компіляції.
Компілятор піклується про розподіл де кожна із змінних збираєтеся піти
і створення спеціальних відображення або, швидше, поєднання точок
між символом і куди він іде, ім'я змінної
і де він буде жити в пам'яті.
Але виявляється, що ми дійсно можемо отримати до нього доступ в наших програмах.
Це стає важливим, коли ми починаємо говорити про деяких структур даних,
яка є концепція, що ми збираємося ввести пізніше.
>> Але зараз, як ви можете знати, що я можу створити покажчик на це місце, х.
Наприклад, я можу створити змінну-покажчик.
Коли ми створюємо покажчик змінної ми використовуємо позначення зірки.
У цьому випадку, це говорить, що я збираюся створити покажчик на Int.
Це типу як і будь-який інший.
Ми даємо йому змінної, як у,
, А потім покласти його рівним адресу, за адресою.
У цьому випадку, ми можемо встановити у указують на х
приймаючи адресою х, які ми робимо з цим амперсанд,
, А потім покласти у указують на це.
Те, що це по суті робить це, якщо ми подивимося на нашу RAM
це створює окрему змінну.
Це буде називати його у,
і коли цей рядок коду виконується
це насправді збирається створити невеликий покажчик, який ми зазвичай використовують, як стріла,
і він встановлює у указують на х.
Так.
[Студент] Якщо х це вже покажчик, ви б просто зробити
Int * у = х, замість того, амперсанд?
Так.
Якщо х це вже покажчик, то ви можете встановити 2 покажчиків дорівнюють один одному,
У цьому випадку у не буде вказувати на х,
але це буде вказувати на будь х вказує.
На жаль, ми поза часом.
>> Що я можу сказати на даний момент, ми можемо поговорити про це в автономному режимі,
Але я б сказав, почати працювати через цю проблему, № 14.
Ви можете побачити там вже трохи заповнений для вас тут.
Ви можете бачити, що, коли ми заявляємо, 2 покажчиків, Int * х * й в,
і зауважимо, що вказує * Поруч із змінною було те, що було зроблено в минулому році.
Виявляється, що це схоже на те, що ми робимо в цьому році.
Це не має значення, де ви пишете *, коли ви оголошенні покажчика.
Але ми написали * поряд із типом
тому що це робить його дуже ясно, що ви оголошенні змінної-покажчика.
Ви можете бачити, що оголошення 2 покажчика дає нам 2 коробки.
Ось коли ми встановлюємо х одно Танос
що це говорить у скасуванні пам'яті в купі.
Цей маленький ящик прямо тут, це коло, знаходиться в купу.
X вказує на це.
Зауважимо, що у ще не вказуючи ні до чого.
Щоб отримати пам'ять для зберігання числа 42 в х
ми будемо використовувати те, що позначення?
[Студент] * х = 42.
Точно, * х = 42.
Це означає, слідуйте за стрілкою і кинути 42 в там.
Тут, де ми встановлюємо у і х ми у вказуючи на х.
Знову ж таки, це просто подобається те, що Кевін сказав, де ми встановлюємо у одно х.
Y не вказує на х.
Швидше, це вказує на те, що X вказує на, а також.
>> І, нарешті, в останньому вікні є 2 можливих речей, які ми могли б зробити.
Один з них ми могли б сказати * х = 13.
Інша справа, ми могли б сказати, Алекс, ви знаєте, що ми могли б зробити тут?
Можна сказати, * х = 13 або-
[Студент] Можна сказати, що Int.
[Nate H.] Якщо це були зараховані до Int змінна, яку ми могли б зробити це.
Ми могли б також сказати, у * = 13, тому що вони обидва вказують на те ж місце,
, Щоб ми могли використовувати або змінну туди добратися.
Так. >> [Студент] Що би це виглядало, якщо ми просто скажемо Int х 13?
Це було б оголосити нову змінну х, яка не буде працювати.
Ми повинні були б зіткнення, тому що ми оголосили х, щоб бути дороговказом тут.
[Студент] Якщо ми просто повинні були це заява сама по собі те, що це буде виглядати з точки зору кола?
Якби ми мали х = 13, то ми повинні були б коробку, і замість того, щоб стрілка
виходячи з вікна ми зробити це, як тільки 13.
[Студент] в поле. Добре.
>> Спасибі за увагу і удачі на Quiz 0.
[CS50.TV]