Протокол по Програмиране и използване на компютри: едномерни масиви на езика С. Три задачи с готов код – търсене на максимум, обработка по условие и обръщане на масива

Комплект, който не се чете от кора до кора, а се отваря при нужда. Всеки от тридесет и петте файла решава една конкретна задача и се използва в мига, в който тя е зададена. Материалите вървят по трудност и повтарят пътя на един семестър – от най-простото пресмятане до алгоритми, които се преподават чак в края на курса. Първото равнище е за начинаещи. Тук са задачите, при които програмата чете няколко числа и извежда резултат: работа по формула, избор между стойности, извеждане на отделна цифра, повторение чрез цикъл. Всяка от тях е кратка и е подходяща за първите часове, когато езикът още се усвоява. Второто равнище е работата с масиви и заема почти една трета от целия комплект. Едномерните са застъпени с четири решения, а двумерните – с осем, което е сериозна разлика. Причината е ясна: двумерните затрудняват най-много, а тук са покрити всички обичайни случаи, включително обхождане по диагонал и по периметър, преминаване между двата вида масиви и една задача с многосъставно условие. Третото равнище е рекурсията – единадесет решени задачи, най-голямата група в комплекта. В нея са всички класически примери, които се падат на изпит, а също и няколко проверки върху число, масив и редица. Достатъчно е ученикът да прегледа тази папка, за да види как една и съща идея работи в различни случаи. Четвъртото равнище са трите пълни упражнения. Първото събира алчните алгоритми, работата с низове и цяла поредица от методи за сортиране, всеки с име и с готов код. Второто е за двоичните дървета, графите и построяването на оптимално дърво. Третото е теоретично и разглежда вероятностните алгоритми по видове, с примери и с раздел за генераторите на случайни числа. Именно тези три файла отличават комплекта от обикновена сбирка със задачи: те дават теорията, върху която стъпват най-трудните теми. Оформлението е еднакво навсякъде: условие с едно изречение, после пълен изходен код, готов за компилиране. Езикът е един и същ през целия комплект, а стилът на писане не се променя от файл на файл – което улеснява четенето на чужд код. За преподавателя това е готов набор за упражнения през целия семестър. Файловете се раздават поединично или по теми, без нужда от подготовка, а трите упражнения вършат работа като материал за лекция. За студента ползата е в подредбата по трудност: подготовката може да върви от началото към края или да започне направо от темата, която предстои да се изпитва. Готовият код служи за образец при писане на собствено решение по курсова задача.

Готов лабораторен протокол с три решени задачи. Всяка е дадена изцяло – условие, блокова схема и работеща програма, готова за въвеждане и изпробване. Именно тази пълнота го отличава. Студентът не получава указания как да реши задачата, а вижда завършеното решение и може да го сравни със своето. Материалът е първи протокол по програмиране и обхваща десет страници. Първата задача е за пресмятане на корените на уравнение от втора степен. Тя е и най-обширната, защото условието изрично изисква да се разгледат всички възможни стойности на коефициентите. Именно това я прави най-полезната от трите. Решението не се ограничава до обичайния случай, а обхожда последователно пет положения: когато два от коефициентите са нула, когато е нула само единият, когато е нула свободният член и накрая трите възможности според знака на дискриминантата. Особено ценна е частта за отрицателна дискриминанта. Тук програмата не спира с грешка, а пресмята комплексни корени, като реалната и мнимата част се въвеждат като отделни променливи още преди разклонението. Втората задача е за прост калкулатор с четирите основни действия. Решението стъпва на конструкция за избор по стойност на един знак, при която всеки случай е даден на отделен ред. Предвиден е и случаят, в който въведеният знак не съвпада с нито един от очакваните. Именно тази задача е удобна за начинаещи – кратка е, но показва две неща наведнъж: работа със символна променлива и разклонение с повече от два изхода. Третата задача е за пресмятане на функция, зададена с три различни израза в зависимост от това в кой участък попада входната стойност. Решението е изградено с последователни проверки, като при всеки случай се извежда и самият израз, по който е пресметнато. Всяка от трите програми е с еднакво устройство: обявяване на променливите, въвеждане с подкана към потребителя, пресмятане и извеждане на резултата, накрая спиране преди затваряне на прозореца. Приложена е и блокова схема към първата задача. Преподавателят получава готов протокол, годен за мерило при проверка, а трите задачи вършат работа и поединично като упражнения в час. Студентът получава три работещи решения, които може да въведе, да изпробва и да преработи според собственото си условие.

Материал, който събира пет различни начина за подхождане към една задача и показва защо всеки от тях се появява там, където предходният се проваля. Именно тази последователност държи изложението. Всеки нов подход не е представен сам за себе си, а като отговор на недостатък на предишния — така се вижда логиката, по която са възникнали. Темата обхваща основните подходи в проектирането на алгоритми и е събрана на седем страници. Първата част е за разделянето на подзадачи. Тя започва с трите стъпки на метода, а после веднага минава към конкретен пример — умножение на две многоразредни числа. Именно този пример е най-силната част. Показано е как обичайният начин изисква определен брой умножения, как едно преобразуване спестява едно от тях и как оттам сложността пада. Изводът е проверен и с числа — две четириразредни числа, при които се брои колко умножения излизат по всеки от двата начина. Следва пълното извеждане на общата зависимост. То минава през няколко последователни замествания и завършва с разглеждане на три случая според съотношението между два параметъра. При всеки случай е получена отделна оценка. Втората част въвежда следващия подход и обяснява кога предходният не върши работа — когато броят на подзадачите зависи от размера на входа. Третата част е за търсенето с връщане назад. Тя стъпва изцяло на една задача — пресичане на пустиня с ограничен запас от гориво. Задачата е решавана постъпателно, като на всяка стъпка се пита къде трябва да стои поредният склад, а отговорът за предходния се използва при следващия. Особено ценен е този начин на изложение. Читателят не получава готова формула, а върви заедно с разсъждението, докато решението се самоизгради. Четвъртата част е за постъпателните алгоритми, разгледани чрез две различни разграничения, а после и чрез задача за връщане на пари, представена в номерирани стъпки. Петата част е за вероятностните алгоритми. Разграничени са от обичайните, обяснено е кое ги прави такива, а после са изброени три техни разновидности. Приведена е и формула за получаване на случайни числа, следвана от примерна програма. Материалът съдържа три чертежа и множество изрази, а на места е даден и код. За преподавателя това е готова опора за няколко часа, при която всяка част върши работа и поединично. Студентът получава петте подхода на едно място, с по един разработен пример при всеки.

Не само условия, а и решения. Към задачите за изпит са приложени девет сканирани листа с ръкописни решения, в които всяка стъпка от преобразуването се вижда така, както се пише на изпит. Задачи за изпит по АСЛС с решения. Материалът се състои от две части. Първата е самият изпитен лист с условията, оформен с полета за имена, група и номер, точно както се раздава на изпит. Втората са сканираните решения на ръка. Условията обхващат петнадесет задачи, подредени в няколко ясно обособени типа. Първият тип изисква най-проста двустъпална реализация на схема, зададена графично чрез две изходни функции и три входни променливи. Вторият тип е най-многоброен и изисква реализация на зададена функция само с три входови логически матрици. Функциите са дадени чрез номерата на конституентите, като всяка от тях е върху пет променливи, което прави задачата сериозна още на етапа на минимизацията. Третият тип изисква реализация само с три мултиплексора, а четвъртият е върху реализация с дешифратор с минимален брой входове. Петият тип поставя ограничение върху елементната база и изисква най-проста реализация само с определени логически елементи, включително елемент за сума по модул две. Шестият тип е обърнат по логика: вместо да се реализира функция по зададени конституенти, се иска да се състави карта по схема, която вече е дадена. При тези задачи схемата е изчертана с дешифратор и мултиплексор и изрично е уточнено кой вход е младши и коя променлива е старша, което е решаващо за правилния отговор. Решенията покриват четиринадесет от задачите и са разположени на девет листа. При част от тях на един лист са събрани по няколко задачи от един и същи тип. Стойността им е в пълнотата. При задачите за минимизация се виждат всички междинни преобразувания на израза ред по ред, прилагането на правилата, попълнените карти с отбелязаните обединения и получената минимална форма, а накрая и начертаната схема с елементите. При задачите с логически матрици са изчертани самите матрични структури с точките на свързване. При обърнатите задачи е съставена пълната таблица на истинност с всички комбинации и от нея е попълнена картата. На едно място в решенията има и червена бележка на проверяващия, от която личи къде точно се допуска типична грешка. За преподавателя: готов набор от условия по шест различни типа задачи, подходящ за съставяне на изпитен вариант или за упражнение. Решенията служат за сверяване, а бележката на проверяващия показва често срещан пропуск. За студента: условия и решения на едно място, с видими междинни стъпки, а не само с крайни отговори. Подходящ за подготовка за изпит, за упражняване на минимизацията, за самопроверка и за ориентир какво точно се очаква да бъде начертано.

Готова курсова задача, при която програмата анализира друга програма. Тя чете чужд изходен код и преброява колко коментара и колко оператора съдържа той. Именно тази необичайна постановка отличава материала. Обичайните упражнения работят с числа или с текст; тук предмет на обработка е самият език за програмиране. Материалът обхваща единадесет страници и съдържа условието и пълния изходен код. Условието изисква четири различни режима на работа, изброени изрично. Те се получават от съчетаването на два избора — откъде се чете и къде се извежда резултатът. Поставено е и допълнително изискване решението да бъде разделено на отделни функции. Именно това разделяне е основното достойнство на решението. Обявени са седем функции, всяка с точно определена задача, а главната програма съдържа само едно извикване. Средището е функцията за разпознаване. Тя получава един ред и проверява за наличие на десетки различни знаци и съчетания — от четирите основни аритметични действия до съставните присвоявания и логическите връзки. Особено внимателна е обработката на случаите, при които един и същи знак може да означава различни неща. Предвидено е разграничаването между деление и начало на коментар, между присвояване и сравнение, между събиране и увеличаване с единица. Отделна функция извежда двата резултата, а четири други изпълняват по един от режимите. Особено полезна е проверката на името на файла. Програмата не приема каквото и да е име, а изисква то да завършва с определено разширение, като задава въпроса отново, докато условието не бъде изпълнено. Менюто е оформено с рамка от знаци и изброява пет възможности, включително изход от програмата. Четенето от файл е организирано по редове, както изисква условието, а при въвеждане от клавиатурата е предвиден начин за указване на края. Кодът е обявен изцяло преди определенията на функциите, което позволява те да се извикват в произволен ред. Преподавателят получава готова курсова работа, годна за мерило при проверка, а отделните функции вършат работа и поединично като задачи в час. Студентът получава завършено решение с ясно разделение на подзадачи — образец за това как се строи по-голяма програма, а не отделно упражнение.

Осем страници, в които една структура от данни е разгледана от определението до три готови алгоритъма с код – точно каквото трябва за изпит по програмиране. Материалът е конспектен, но не е сбит до неразбираемост. Всяко понятие е въведено с определение и онагледено с пример, а алгоритмите не са само описани – дадени са с реален код и с проследено числено изпълнение. Първата част е терминологична и обхваща в плътна последователност всичко, което се пита: определението за граф, разликата спрямо дървото, видовете дъги и графи, инцидентност и съседство, степен на връх с отделните ѝ разновидности при ориентиран граф, път, дължина, прост път, цикъл, свързаност и подграфи. Означенията са въведени поред и се използват последователно нататък. Втората част е за представянето в паметта и е разделена на три подхода. Статичните са три на брой, всеки с приложена схема. Динамичното е дадено с готови структури, а комбинираното – с още една декларация. Тук е и бележката кога кой подход е за предпочитане. Следва списък с осемте основни операции, а веднага след него – деветте аксиоми, при които те са определени. Последната аксиома важи само за единия вид графи и това е изрично уточнено. Такова изброяване рядко се среща събрано на едно място. Средището са трите алгоритъма и всеки е разгърнат по един и същи начин. Първият е за най-къс път и е представен с постановка, с описание на работата чрез поддържане на множество, с числен пример и с масивите, използвани в него, а после и с пълен програмен код. Накрая е дадена сложността при двата начина на представяне. Вторият е за топологично сортиране. Тук е обяснено защо резултатът рядко е единствен, приведени са няколко възможни подредби, дадени са трите стъпки и е посочен обратният вариант на същия алгоритъм. Третият е за най-дълъг път и започва с практическа задача от разработването на програмен продукт, преведена в термините на графа. След трите стъпки и сложността следва напълно проследено числено изпълнение по стъпки, а накрая – указание как алгоритъмът се реализира рекурсивно. За преподавателя това е готова опора за няколко учебни часа, която не изисква подготовка. Трите алгоритъма вършат работа и поединично – като материал за упражнение или като тема за самостоятелна работа. За студента ползата е ясна: целият изпитен въпрос е събран на едно място, а програмният код и проследените числени примери спестяват търсенето по няколко източника. Материалът се преговаря непосредствено преди изпит и върши работа при курсова задача.