Перш, ніж братися за завдання, перегляньте лекції 7-8 , прочитайте та вникніть у « Додаткові матеріали третього тижня ». Вони присвячені алгоритмам пошуку (лінійному та бінарному), сортування (багато їх!), а також роботі дебаггера (уміння працювати з дебаггером для налагодження програм – надзвичайно важлива навичка!). Якщо з лекціями та теорією все пішло, як треба, ви легко відповісте на перевірочні питання:
Чому бінарний пошук потребує відсортованого масиву?
Чому оцінка сортування бульбашкою дорівнює O(n2)?
Чому оцінка сортування вставками це Ω (n)?
Як працює сортування вибором? Опишіть у трьох реченнях (або менше).
Яка верхня межа (найгірший випадок) часу роботи сортування злиттям?
Дебаггер GDB дозволяє налагодити програму. А якщо сформулювати конкретніше, що він дозволяє робити?
Цілі
Навчитися працювати з проектами, які містять кілька файлів
Навчитися читати чужий вихідний код
Засвоїти різні алгоритми та рекурсивні функції
Більшість із цих цілей формально оцінити практично нереально. Тому, з погляду формальної перевірки завдань, тут мало здасться вам складним. Тим не менш, нагадуємо: навчитися програмування можна лише постійно практикуючись! Тому закликаємо вас не просто вирішити завдання, а й витратити додаткові час та зусилля та реалізувати всі ті алгоритми, які були розглянуті цього тижня. Уперед!
Починаємо
Нагадаємо, для вирішення практичних завдань на першому і другому тижні ви писали програми з нуля і створабо власні каталоги pset1 і pset2 за допомогою команди mkdir . Для практичного завдання третього тижня потрібно завантажити дистрибутив (або «дистро», ми так його називаємо), написаний нами, і додати туди власні рядки коду. Спочатку вчитайтеся в наш код і спробуйте його зрозуміти. Найважливіша навичка цього тижня – навчитися читати чужий код. Отже, вставте на cs50.io і виконайте команду update50 в термінальному вікні, щоб переконатися в актуальності версії робочого простору. Якщо ви випадково закрабо термінальне вікно і не можете його знайти, зайдіть в меню View і переконайтеся, що навпроти пункту Console стоїть галочка (поставте її, якщо це не так). Клацніть на(+), всередині зеленого кола на рамці термінального вікна, виберіть New Terminal . Після цього виконайте команду cd ~/workspace та переконайтеся, що ви знаходитесь усередині директорії workspace (це ваш каталог). Після цього виконайте команду: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip щоб завантажити ZIP-архів завдання у ваш робочий простір (wget - команда linux для завантаження). Якщо все ок, у рядку ви побачите таку фразу: 'pset3.zip' saved Переконайтеся, що ви дійсно завантажабо pset3.zip, виконавши команду: ls а потім запустіть unzip pset3.zip , щоб розархівувати файл. Якщо ви ще раз запустите команду ls , ви також побачите директорію pset3 . Перейдіть до неї, виконавши команду cd pset3 , а потім знову запитайте перегляд вмісту директорії: ls ви побачите, що в цій директорії є дві піддиректорії: fifteen find Вже інтригує!
Пошук
Давайте тепер пірнемо в одну з цих піддиректорій. Для цього виконаємо команду: cd ~/workspace/pset3/find Якщо ви виведете вміст цієї папки на екран (ви вже напевно пам'ятаєте, як це робити), ось що ви повинні побачити: helpers.c helpers.h Makefile find.c generate.c Ух ти, файлів вистачає. Але не турбуйтесь, зараз ми з ними розберемося. У файлі generate.c розміщено код програми, яка використовує "генератор псевдовипадкових чисел» (генерація за допомогою функції drand48 ) щоб згенерувати велику кількість випадкових (справді кажучи, псевдовипадкових, комп'ютери не можуть працювати з чистою випадковістю!) чисел, і розмістити їх по одному в рядку Скомпілюйте програму: make generate Тепер запустіть її, виконавши команду: ./generate Програма видасть вам таке повідомлення: Usage: generate n [s] Це означає, що програма очікує один або два аргументи командного рядка Використання першого, n, обов'язково, це число означає скільки псевдовипадкових чисел ви хочете створити. Параметр s не є обов'язковим, на що вказують квадратні дужки Число s можна назвати «насінням» для генератора псевдовипадкових чисел. викликавши srand48 (ще одна функція, мета якої полягає в "посіві" drand48) з аргументом, скажімо, 1, а потім викличете drand48 три рази, drand48 може повернути 2728, потім 29785, потім 54710. Tсли ви замість попереднього, викличете srand48 з аргументом, скажімо, 2, а потім знову використовуєте drand48 три рази, drand48 може повернути 59797, потім 10425, потім 37569. Але якщо ви повторно «посієте» drand48, викликаючи srand48 знову з аргументом 1, ви знову отримаєте 2728, потім 29785, потім 54710! Бачите, все відбувається зовсім невипадково. Запустіть програму ще раз, цього разу, скажімо, n=10, як показано нижче; ви побачите список із 10 псевдовипадкових чисел. ./generate 10 Давайте запустимо програму втретє з тим самим значенням n; ви повинні побачити інший список із 10 цифр. Тепер спробуйте запустити програму із двома параметрами. Давайте візьмемо s = 0, як показано нижче. ./generate 10 0 Тепер запустіть ту ж команду ще раз: ./generate 10 0 Можна навіть не сперечатися: ви знову побачабо ту саму «випадкову» послідовність із десяти цифр. Ось що станеться, якщо ви не мінятимете «насіння» генератора псевдовипадкових чисел. Тепер подивимося на програму generate.c(Пам'ятаєте, як?). Коментарі на початку файлу пояснюють загальну функціональність програми. А ось сам код ми, схоже, забули прокоментувати. Уважно вчитайтеся в код, і читайте його доти, доки не вловите сенс кожного рядка. Після цього прокоментуйте цей код замість нас, замінюючи кожен TODO фразою, що описує ціль чи функціональність відповідного рядка чи рядків коду. (Примітка: unsigned int - це "беззнаковий" int, тобто він не може бути негативним). Щоб отримати більш детальну інформацію про rand або srand, виконайте: man drand48 або man srand48 Після того, як у generate.c прокоментуєте все, що можна, перекомпілюйте програму, щоб переконатися, що ви нічого не зламали: make generate Якщо generate більше не компіліться, чиніть, що зламали: )! Нагадаємо: команда make автоматизує компіляцію коду, тому вам не доведеться виконувати команду clang вручну підставляючи купу перемикачів. Але насправді make просто спрощує нам введення, а насправді за ним захований той самий clang із потрібними нам параметрами. Однак коли ваші програми стануть більшими за розміром, make не зможе більше з'ясувати з контексту, як компілювати код. У такому випадку вам доведеться вказати, як потрібно скомпілювати програми, особливо якщо вони пов'язані з використанням різних вихідних файлів (наприклад, .c). Для вирішення цієї проблеми ми використовуватимемо файли конфігурації (Makefiles), які точно вказують make, що потрібно робити. Як команда make дізналася, як нам слід компілювати generate? Насправді команда використовувала файл конфігурації, який ми вже написали. Цей файл називається Makefile і він лежить у тій директорії, що і generate.c . Makefile — це список правил, що вказують, як створити файл generate з generate.c. У файлі ви знайдете, зокрема, відповідні рядки: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Перший рядок каже make, що "мета" під назвою generate повинна бути створена шляхом виклику команди з другого рядка. Більше того, перший рядок вказує make, що generate залежить від generate.c, сенс якого в тому, що make тільки перезбиратиме generate в ході наступних запусків, якщо цей файл був змінений. Непоганий трюк для економії часу, чи не так? Насправді, виконайте команду нижче, якщо ви не змінювали generate.c . make generate Вам повідомлять, що generate вже оновлено до поточної версії. Зауваження : відступ на початку другого рядка не є послідовністю прогалин, це, скоріше, знак табуляції. На жаль, make вимагає, щоб командам передували знаки табуляції, тому будьте обережні, щоб не змінити їх на прогалини, інакше ви зіткнетеся з незрозумілими помилками! Прапор -Werror каже команді clangвважати попередження (погано) помилками (ще гірше), так що ви будете змушені (у хорошому, навчальному значенні!) виправити їх. Тепер подивимося на файл find.c. Зверніть увагу, ця програма чекає на один аргумент командного рядка: "голку", яку потрібно знайти в «стозі сіна» значень. Після цього перегляньте код і скомпілюйте програму, виконавши команду нижче. make find make практично вивів для нас наступне: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Зверніть увагу! Щойно ви скомпілювали додаток, що складається з одного, а з двох файлів : helpers.c і find.c. Як про це дізналася make? Щоб зрозуміти це, знову відкрийте файл Makefile, щоб зрозуміти, що там насправді відбувається. Відповідні рядки нижче. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Під залежністю (після двокрапки) можна розуміти те, що всі зміни у файли find.c , helpers.c , або helpers.h змусять make перезбирати find наступного разу, коли вона буде викликана для цих цілей. Тепер запустіть цю програму, виконавши, наприклад, наступне: ./find 13 Після цього вам надійде пропозиція надати якийсь стог (тобто цілі числа) і подавати їх по одній соломинці за раз. Як тільки ви втомитеся від введення чисел, натисніть комбінацію клавіш Ctrl-D . Ця комбінація надішле програмі символ кінця файлу (EOF, end-of-file). Символ змусить функцію GetInt з бібліотеки CS50 повернути константу INT_MAX , а вона, у свою чергу, в find.c змусить find припинити набирати «стіг». Тепер програма буде шукати голку в тому стозі сіна, що ви надали, і зрештою вона повідомить, чи її знайшли. Коротко говорячи, програма виконує пошук деякого значення в масиві. Принаймні, вона винна, але загвоздка в тому, що поки що вона нічого не знайде! Але тут на допомогу приходьте! Про важливість вашої ролі поговоримо трохи згодом. Насправді процес надання стогу можна автоматизувати хоча б по "злиттю" виводу generate у find як вхідні дані. Наприклад, команда нижче передає 1000 псевдовипадкових чисел find, яка потім шукає серед цих значень 42. ./generate 1000 | ./find 42 Зверніть увагу: коли generate передає вихідні дані find, ви не бачите числа generate, але ви побачите роботу find. В якості альтернативи, ви можете "перенаправити" висновок generate у файл за допомогою такої команди: ./generate 1000 > numbers.txt Вміст цього файлу можна перенаправити на вхід find за допомогою команди: ./find 42 < numbers.txt Давайте ще раз подивимося на код у Makefile і звернемо увагу на наступний рядок: all: find generate Це означає, що ви можете зібрати generate і find, виконавши наступну команду: make all Більше того, команда під цим рядком еквівалентна команді над нею, оскільки make будує перший запис Makefile за замовчуванням. make Якби ви могли звести всі ці практичні завдання до однієї команди! Але нажаль! Нарешті, зверніть увагу на ці останні рядки в Makefile: clean: rm -f *.o a.out core find generate Цей запис дозволяє видалити всі файли, які закінчуються на .o або називаються core (це ми пояснимо трохи пізніше!), а також запустити програми find або generate просто виконавши рядок: make clean Якщо захочете експериментувати , то ось із чим будьте обережні: не додавайте, скажімо, *.c в цей останній рядок Makefile! (Чому?) Усі рядки, які починаються зі знака # - це просто коментарі.
Завдання 1: Search
Настав час для дечого цікавого! Зверніть увагу, find.c викликає search , функцію, оголошену в helpers.h . На жаль, ми забули реалізувати цю функцію повністю у helpers.c ! (Треба зазначити, що ми могли б помістити вміст helpers.h і helpers.c в один find.c. Але іноді краще розділяти програми на кілька файлів. Особливо якщо деякі функції, точніше функції-утиліти, можуть виявитися корисними і для інших програм. Як, наприклад, функції з бібліотеки CS50: Погляньте на helpers.c і ви побачите, що search завжди повертає значення false, незалежно від того, чи занесено дане значення value у values. , якщо value входить у values і false, якщо value не входить у values. Подбайте про те, щоб повернути false відразу, якщо n не є позитивним Коли ви будете готові до перевірки правильності, спробуйте викликати наступну команду: Оскільки одне з чисел, ./generate 1000 50 | ./find 127 виведених за допомогою generate, коли «засіювали» 50, рівно 127 ./generate 1000 50 | ./find 128 , ваш код повинен знайти "голку"! має знайти «голку». Проведіть й інші тести, запускаючи generate з якимсь насінням, аналізуючи вихідні дані, та шукаючи «голку», яка має бути у «стогу». Зверніть увагу, що main у find.c написана таким чином, що find повертає 0, якщо «голка» знайдена, інакше — повертає 1. Ви можете перевірити так званий вихідний код, який main повертає при виконанні Після запуску деяких інших команд echo $? . Наприклад, якщо ваша реалізація search - правильна, якщо ви запустите ./generate 1000 50 | ./find 127 echo $? Ви побачите 0, поки 127 є серед тих 1000 чисел, виведених за допомогою generate з насінням 50, тому написаний пошук search повинен повернути true. У цьому випадку main (написаний нами) має повернути 0 (тобто завершити роботу). Якщо ж ви задасте наступні вхідні дані, ./generate 1000 50 | ./find 128 echo $? Ви побачите 1, оскільки 128 не знаходиться серед тих 1000 чисел, які були виведені за допомогою generate з насінням 50. У цьому випадку search (написаний вами) поверне false, і main (написаний нами) поверне 1 ( і з тим закінчить роботу. Січете логіку? Коли все буде готове для перевірки за допомогою check50, виконайте таку команду: check50 2015.fall.pset3.find helpers.c До речі, не варто звикати до тестування коду за допомогою check50 перед власним тестуванням. Все-таки check50 не насправді не існує, тому запуск коду з вашими власними вхідними вибірками, порівняння фактичного висновку до очікуваних вихідних даних, — найкраща звичка, яку можна знайти на цьому етапі. Правда-правда, не набувайте шкідливої залежності! Якщо вам цікаво пограти з реалізацією find, виконаною асистентами CS50, виконайте таку команду: ~cs50/pset3/find
Сортування
Лінійний пошук - це не те, що по-справжньому вражає, але з перших лекцій (а в сьомий ми знову повторабо цей трюк!) Ви пам'ятаєте, що знайти голку в копиці сіна можна набагато швидше. Тільки спершу треба відсортувати наш стог сіна. Зверніть увагу: find.c викликає sort , функцію, оголошену в helpers.h . На жаль, ми "забули" реалізувати цю функцію повною мірою в helpers.c ! Загляньте в helpers.c і ви побачите, що відбувається миттєве повернення sort, хоча функція main з find дійсно передає їй фактичний масив. Тепер пригадайте синтаксис оголошення масиву. Ви не лише вказуєте тип елементів цього масиву, але й задаєте його розмір у квадратних дужках. Так ми робимо для haystack у find.c : int haystack [MAX]; Але у проходженні масиву ви тільки вказуєте його назву. І ми це робимо так само, коли проходимо haystack, щоб виконати sort в find.c : sort (haystack, size); (Здогадайтеся, чому ми передаємо розмір цього масиву окремо?) Коли ми оголошуємо функцію, яка приймає як аргумент одномірний масив, не потрібно вказувати розмір масиву . Так само ми цього не робабо, коли оголошували sort в helpers.h (і helpers.c): void sort (int values [] int n); Реалізуйте sort, так щоб функція дійсно відсортувала масив чисел від менших до більших. Потрібно, щоб час її роботи дорівнював O (n 2 ), де n - розмір масиву. Швидше за все, ви захочете реалізувати метод бульбашкового сортування, сортування вибором або вставкою, оскільки ми вивчабо їх на третьому тижні. Проте важливо відзначити: "правильного" способу реалізації не існує для цих алгоритмів. Є безліч варіацій. Насправді, ви завжди можете поліпшити їх, якщо вважаєте за потрібне, доки ваша реалізація зійдеться до O (n 2 ). Проте, експерименти залиште для тіла функції, а з метою спрощення перевірки не змінюйте нашу декларацію sort. Вона має виглядати так: void sort (int values [] int n); Оскільки функція повертає значення типу void, вона повинна повертати відсортований масив. Натомість, вона повинна "деструктивно" сортувати фактичний масив, яким вона «пробігає», переміщуючи його елементи. На четвертому тижні ми обговорюватимемо, що масиви передаються не за значенням, а за посиланням. Тобто sort не отримає копії масиву, а сам вихідний масив. Хоча ви не можете змінити нашу декларацію sort, ви завжди можете визначити свою власну функцію в helpers.c, яку потім можна буде викликати з sort. Виберіть самі, як краще протестувати реалізацію вашого sort. Не варто забувати, що printf та GDB вам допоможуть! І не забувайте, що ви можете створити ту ж послідовність псевдовипадкових чисел знову і знову, явно вказуючи значення насіння для generate.
Бінарний пошук, поради
Перше, що необхідно розуміти про функцію find — ми вже маємо написаний код (дистрибутив). Ми просто заповнюємо деякі прогалини в існуючому коді. Програма find.c запитує введення чисел (тобто заповнити «стіг»), а потім шукає в ньому «голку» на запит користувача, використовуючи для цього sort і search — функції, визначені в helpers.c . Таким чином, find вже написана, нам потрібно написати helpers . Отже, ось що нам потрібно зробити:
Реалізувати пошук. Ця функція повинна повертати true, якщо значення знайдено в стогу і false, якщо його там немає.
Реалізувати sort, функцію, яка сортує масив значень.
Спочатку пошук реалізовано як лінійний. Але ви можете зробити краще. Алгоритм лінійного пошуку виконується за час О(n) . Ваше завдання – написати алгоритм бінарного пошуку. Час виконання — O(log n) . Однак його проблема в тому, що йому на вхід потрібно подавати відсортовані дані, інакше він не працюватиме. Ви пам'ятаєте приклад із розірваною книгою, і, мабуть, знаєте, чому так. Якщо ви пройшлися бінарним пошуком по елементах і їх більше не залишилося (тобто в цьому "стозі" нашої "голки" просто немає), потрібно, щоб функція повернула false. Бінарний пошук можна реалізувати ітеративно чи рекурсивно (про рекурсію Девід Малан розповів у восьмій лекції).
Після цього виконайте команду 
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ