Харвардски курс CS50 в Грозни
Създайте програма, която ще търси число сред определен брой други числа.
Разгръщане
Изтегли
Файлът generate.c реализира програма, която използва "генератор на псевдослучайни числа" (използвайки функцията drand48), за да генерира цял куп случайни числа (всъщност псевдослучайни, защото компютърът не може да генерира наистина произволни числа) по едно на ред, всяко в рамките на [0, LIMIT), където LIMIT (limit, limit) е константа (дадено и непроменливо число), зададена във файла. Тези. всяко число, по-голямо или равно на 0 и по-малко от LIMIT.
Компилирайте програмата, като изпълните кода по-долу.
Сега го стартирайте така.
Трябва да сте наясно с правилното използване на програмата, както е показано по-долу.
Този ред ни казва, че тази програма очаква един или два аргумента на командния ред. Първият аргумент n - трябва да присъства; той определя колко псевдослучайни числа трябва да бъдат генерирани. Вторият аргумент s не е задължителен (затова е поставен в квадратни скоби); ако е предоставено, то ще обозначи числото, което ще бъде използвано от генератора на псевдослучайни числа като „семе“ (това, което се засява, за да се получи реколта). Зародишът се използва на входа на генератора на псевдослучайни числа, засягайки неговия изход. Например, ако засадите семе в drand48, като първо използвате srand48 (друга функция, предназначена да "сее" семе в drand48), като използвате например аргумента 0 и след това извикате функцията drand48 три пъти - drand48 може да върне 0,170828, след това 0,749902 и 0,096372. Но ако заредите drand48, като първо извикате функцията srand48 с помощта нааргумент 1 и след това да извика drand48 три пъти - drand48 сега може да върне 0.041630, след това 0.454492 и 0.834817. Но ако заредите отново drand48, като извикате srand48 с аргумент 0, след което извикате drand48 три пъти следващия път, получавате отново 0.170828, след това 0.749902 и 0.096372! Вижте, не е толкова случайно.
Стартирайте тази програма отново, но този път със стойност като 10 за n, както е показано по-долу. Трябва да се появи списък от 10 псевдослучайни числа.
Стартирайте програмата трети път, като използвате същата стойност за n и ще видите списък с различен набор от стойности. Сега опитайте да стартирате програмата, като зададете стойността на s (т.е. 0), както е показано по-долу.
Изпълнете отново същата команда:
Обзалагам се, че отново сте видели същата последователност от числа? О, да, това се случва, ако не използвате различни семена за генератор на псевдослучайни числа.
Ако генерирането вече не се компилира, поставете на пауза и вижте къде може да сте сгрешили.
Сега не забравяйте, че make автоматизира компилирането на вашия код, така че не се налага ръчно да въвеждате clang заедно с многото му аргументи. Забележете как make пише и изпълнява команда с приличен размер вместо вас, което е изходът. Но тъй като вашата програма нараства по размер, make вече няма да може да компилира вашия код сам. Ще трябва да започнете да казвате на make как да компилира вашата програма, особено когато става въпрос за множество изходни файлове (т.е. .c). И сега ще разчитаме на "Makefiles" - конфигурационни файлове, които казват на make точно кои стъпки да използва.
Как make знае как да компилира програмата "generate" в този случай? Всъщносттой използва конфигурационния файл, който създадохме по-рано. Нека отворим Makefile, който се намира в същата папка като generate.c. Този Makefile е основно списък с правила, които написахме за вас, казвайки ви "направете" как да създадете програма за "генериране" от файла generate.c. Съответните редове са показани по-долу.
Първият ред казва на make, че "целта", наречена генериране, трябва да бъде създадена чрез извикване на командата от втория ред. Имайте предвид, че празнината в началото на втория ред не е последователност от интервали, а еднократно натискане на бутона "tab". За съжаление е важно за make командите да започват с "tab", така че бъдете внимателни и се уверете, че не ги променяте на интервали или ще попаднете на странни грешки! Флагът -Werror или аргументът казва на clang да третира предупрежденията (лошо), сякаш са грешки (много по-лошо), за да ви принуди (по добър, поучителен начин!) да ги коригирате.
Сега вижте find.c. Обърнете внимание, че тази програма очаква един аргумент от командния ред: "игла", който ще бъде търсен в "стек" от стойности. След като приключите с кода, можете да компилирате програмата, като изпълните командата по-долу.
Забележете, като погледнете изхода на командата, че make всъщност направи следното.
Вие също компилирахте програма, която включва не един, а два .c файла: helpers.c и find.c. Как make разбра какво да прави? Отново отворете Makefile, за да видите кой стои зад всичко това. Съвпадащите редове се показват по-долу.
Съгласно зависимостите, подразбиращи се по-горе (след двоеточието), всички промени в find.c, helpers.c или helpers.h ще принудят make да преизгради програмата "find" следващия път, когато бъде извиканакато цел.
Стартирайте програмата, като напишете следното.
Ще бъдете помолени да предоставите малко сено (т.е. някои цели числа), една "сламка" наведнъж. След като ви писне да предоставяте цели числа, натиснете ctrl-d на клавиатурата, за да изпратите на програмата символ EOF (край на файл или край на файл). Този символ ще накара функцията на библиотеката CS50 get_int да върне INT_MAX, константа, която според find.c ще накара find да спре да иска сено. След това програмата ще започне да търси игла в сеното, което сте предоставили, като в крайна сметка ще ви уведоми дали първата е намерена в последната. Накратко, той търси в масива някаква стойност. Най-малкото да го намери, но едва ли ще успее още! И ето ви изхода. Скоро ще разберете каква е вашата задача.
Оказва се, че можете да автоматизирате този процес на предоставяне на сено, макар и чрез „опаковане“ на изхода от генериране и предоставянето му като вход за намиране. Например, командата по-долу предава 1000 псевдослучайни числа към програмата за намиране, която след това ги търси за числото 42 .
Обърнете внимание, че като опаковате изхода от генериране в find по този начин, вие всъщност няма да видите номера на програмата за генериране, но ще можете да видите заявките на find.
Като алтернатива можете да "пренасочите" генерирания изход към файл, като използвате командата по-долу.
След това можете да изпратите съдържанието на файла като вход към програмата за намиране, като използвате командата.
Нека приключим с разглеждането на Makefile. Погледнете долния ред.
Тази цел указва, че можете да създадете програми за генериране и намиране, като просто напишете следното.
Освен това, следното ще даде същия резултат (защото makeсъздава първата цел на Makefile по подразбиране).
О, ако можехте да разрешите този набор от проблеми с една команда! И накрая, вижте тези последни редове в Makefile:
Тази цел ви позволява да изтриете всички файлове, чиито имена завършват на .o или са наречени core (повече за това много скоро!), да намерите или генерирате, като просто въведете командата по-долу.
Не добавяйте *.c към последния ред на Makefile! (Защо?)
Имайте предвид, че в find.c main извиква търсене, функция, декларирана в helpers.h. За съжаление, забравихме да внедрим напълно тази функция в helpers.c! Погледнете helpers.c и ще видите, че търсенето винаги връща false, независимо дали има стойност в стойностите. За да сме сигурни, можем да поставим съдържанието на helpers.h и helpers.c в самия find.c. Но понякога е по-добре програмите да се разпространяват в множество файлове, особено ако някои от функциите са „полезни функции“, от които други програми може да се нуждаят в бъдеще – като тези в библиотеката CS50.
Също така имайте предвид, според helpers.h, че прототипът за търсене изглежда така:
И сортираният прототип е като този:
И двете функции приемат масив от стойности като един от аргументите си, а цяло число n е размерът на дадения масив. Това е така, защото когато предавате функция за масив, трябва да предавате нейния размер отделно; не можете да направите извод за размера на масив от самия масив.
Завършете прилагането на програмата за търсене, като продължите да пишете програмите за търсене и сортиране в helpers.c.
Вашият код трябва незабавно да върне false, ако n не е положително.
Вашият код трябва да върне true (вярно), ако стойността е в стойностите, и - false (false), ако стойността не е в стойностите.
Време на изпълнение на вашия кодтрябва да бъде в границите на O(log n).
Вашата програма трябва да сортира номерата на масива, дадени й, от най-малкото към най-голямото.
Времето за изпълнение на вашия код трябва да бъде в O(n 2 ), където n е размерът на масива.