Рекуррентное определение выражений. Алгоритм анализа и вычисления выражений (программа ”калькулятор”).
Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Значение любой такой функции можно определить, вычисляя все ее значения начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения.
Рекуррентные выражения используются, в частности, для определения сложности рекурсивных вычислений.
Калькулятор анализирует и вычисляет выражения методом рекурсивного спуска. Этот алгоритм лежит в основе работы многих компиляторов и, разобравшись с ним, вы лучше поймете как строятся выражения в С++. В нем можно задавать выражения типа x=y=5; x=x+(6/17+2.5)*y; l=2*pi*x и т.д. Выражение заканчивается с окончанием строки или символом ‘;’. Увидев ‘;’ или конец строки калькулятор распечатает результат, а увидев новое имя заведет соответствующую переменную. Кроме того, в нем сразу определены две константы pi и e.
Прежде чем строить программу, анализирующую выражения, необходимо дать формальное определение выражений, подлежащих анализу. Для применения алгоритма рекурсивного спуска наиболее подходящим является рекурсивное определение:
Выражение:
Терм + выражение или
Терм - выражение или
Терм
Терм: атом / терм или
атом * терм или
атом
Атом: Число или
Имя или
Имя = Выражение или
- атом или
(выражение) или
Раскрывая это определение обычным языком можно сказать, что выражение может состоять из нескольких слагаемых (термов). Терм может состоять из нескольких сомножителей (атомов). Атом — это число, переменная, выражение присваивания, выражение с унарным минусом или выражение в скобках. Рекурсия определения заключается в том, что каждое понятие определяется через себя, а атом определяется еще и через выражение.
Рекурсией в программировании называется вызов функцией самой себя прямо (в теле функции расположен вызов себя) или косвенно (функция вызывает функцию, которая вызывает функцию, которая… и в одной из этих функций расположен вызов самой первой функции!!!).
| 13.Средства обработки текстовых данных. Форматирование строк в C++ и C#. Эффективность формирования строк и класс StringBuilder в C#.
Обработка текстовых данных весьма важна.
Форматирование строк в C#:
displayTextBox.Text += String.Format("{0:D2}:{1:D2}:{2:D2}", DateTime.Now.Hour, DateTime.Now.Minute, DateTime.Now.Second);
Форматирование строк в C++:
SPRINTF
#include <stdio.h>
1)int sprintf(buffer, format-string[, argument...]); 2)char *buffer;
1)память для хранения вывода char *format-string; 2)строка управления форматом
Функция sprintf форматирует и запоминает наборы символов и значений в buffer. Каждый аргумент argument (если он есть), преобразуется и выводится согласно соответствующей спецификации формата в format-string. Format-string состоит из порядковых символов и имеет ту же самую форму и функцию, что аргумент format -string для функции printf.
Функция sprintf возвращает количество символов, записанных в buffer.
Пример.
#include <stdio.h>
char buffer[200];
int i, j; double fp; char *s = "computer"; char c;
/* форматирует и печатает различные данные */
j = sprintf(buffer, "%s\n", s); j + = sprintf(buffer+j, "%c\n", c); j + = sprintf(buffer+j, "%d\n",i); j + = sprintf(buffer+j, "%f\n",fp);.
Эффективность формирования строк и класс StringBuilder в C#:
При операции s += t остаются три объекта: s, s (новое = s+t) и t. При множественных операциях сложения строк получается много лишних объектов. Для решения этой проблемы и более эффективного использования ресурсов существует класс StringBuilder в C#.
Данный класс предоставляет подобный строке объект, значение которого является изменяемой последовательностью знаков.
Большинство методов, изменяющих экземпляр данного класса, возвращают ссылку на тот же экземпляр. Поскольку ссылка на экземпляр возвращается, имеется возможность вызвать метод или свойство по ссылке.
Емкостью StringBuilder считается максимальное количество знаков, которое экземпляр может хранить в любой момент времени.
Емкость можно увеличить или уменьшить с помощью свойства Capacity или метода EnsureCapacity, но она не может быть меньше значения свойства Length.
Эффективность операции объединения для объектов String или StringBuilder зависит от того, как часто происходит выделение памяти.
класс String является предпочтительным для операции объединения, если фиксированное количество объектов String объединено.
Объект StringBuilder является предпочтительным для операции объединения, если произвольное количество строк объединено.
17. Обработка исключений. Правила перехвата исключений. Назначение системы обработки исключений. Для чего система обработки исключений не предназначена.
Хорошая система обработки ошибок должна:
· предоставлять единый механизм обработки,
· локализовать код обработки ошибок, отделив его от основного алгоритма,
· позволять передавать управление на “компетентный” уровень иерархии программы.
Использовать систему обработки ИС не следует:
· если в блоке try ничего нет;
· в случае неуверенности выполнимости алгоритма вообще.
подход для обработки исключений опирается на 3 основных понятия: “генерация исключения”, “охраняемый код” и “обработчик исключения”.
Пример!Предположим, класс CMyClass имеет оператор преобразования к целым. Пусть определена операция деления объекта CMyClass на целое. Очевидно, что делить на 0 нельзя. Поэтому в операторе деления выполняется проверка на 0. Если знаменатель равен 0, то вместо деления генерируется исключение (оператор throw). На этом обработка ошибки в операторе деления заканчивается.
int operator / (CMyClass o, int i) {
if (i!= 0)
return o/i;
else
throw EDevisionByZero(); // Генерируется исключение
}
// Основной алгоритм
void main() {
CMyClass myObj;
int x=0;
try { // Охраняемый блок
...//вычисляем k
x = myObj/k;
...//используем x...
}
catch(EDevisionByZero) { // Обработчик исключения
... // Обработать исключение}}
блок try. Этот блок называется “ охраняемым кодом ”. За охраняемым кодом следуют обработчики исключений, которые начинаются словом catch.
там, где можно принять решение о методе обработки исключения, код помещается в охраняемый блок. За охраняемым блоком следует блок обработчиков исключений. Система обработки ошибок при получении исключения прерывает выполнение основного алгоритма и передает управление непосредственно обработчикам, расположенным за ближайшим (по иерархии) блоком охраняемого кода.
Проще всего “вбросить” (throw) объект, характеризующий исключение в систему обработки ошибок.
Это может быть любой объект или ссылку на глобальный объект или даже указатель на него.
Хорошей практикой считается построить иерархию классов исключений. Базовый класс Exception содержит целочисленное поле под код ошибки и строковое поле под текст сообщения об ошибке. Остальные члены иерархии просто наследуют от базового класса.
19.Наследование, иерархии классов и обобщенная обработка данных. Чистый полиморфизм (полиморфизм виртуальных методов). Интерфейсы и абстрактные классы.
Рассмотрим различие понятий потомок и подкласс. Если бы классы предки всегда были public, как в Delphi, то класс потомок всегда был бы подклассом предка (обязательно имеет все те же поля, методы и свойства, плюс некоторые другие). В случае же со скрытым предком это не так. Будучи потомком, класс не является подклассом своего предка.
Основное предназначение наследования– повторное использование кода – то, что было реализовано для одного класса (предка) может многократно использоваться в других классах
(его потомках).
Еще одна функция наследования - построение иерархии абстрагирования понятий. Т.е. можно вообразить функцию, которая работает с классом CFurniture и любым из его потомков (т.е. использует лишь поля и методы CFurniture).
Полиморфизм означает в программировании “один интерфейс – много реализаций”. Например, суммирование для строк и чисел – совершенно разные операции, но нам привычно и удобно обозначать их одной операцией сложения.
Другой вид полиморфизма – шаблоны.
наиболее существенную роль играет полиморфизм виртуальных методов или как его иногда называют, чистый полиморфизм.
Пусть перед нами поставлена задача разработать программу, которая поможет компоновать расстановку мебели в помещении. Т.е. пользователь набирает несколько предметов мебели, задает размеры помещения и пытается с помощью нашей программы моделировать расположение мебели.
Первая проблема – где хранить (в каком контейнере) выбранные предметы мебели? Можно под каждый вид мебели создать список и хранить весь набор в отдельных списках, например, стулья, столы, шкафы, диваны, кровати, кресла и т.п. Это вызовет проблему, если появится новый тип мебели, да и сама программа будет сложна.
Другой вариант решения – организовать все классы мебели в иерархию, во главе которой находится класс CFurniture. Тогда, потенциально, мы могли бы поместить выбранный набор в список указателей на объекты CFurniture. Пока что это решение выглядит проще и более универсально.
Интерфейсы и абстрактные классы
Что если мы хотим объявить класс, от которого будет построена целое семейство потомков, но сам класс реализовывать нет смысла – объекты такого типа бессмысленны и создаваться не могут. Примерами могут быть классы CFigure и CFurnuture. Невозможно нарисовать фигуру вообще или предмет мебели. Это всегда их конкретизация, прямоугольник, стол и т.п.
Для отражения такой картины в C++ могут объявляться абстрактные методы. Вот пример объявления.
class CFigure {
public: virtual void Draw(CWnd *hWnd) = 0;};
Т.е. мы знаем, что метод Draw будет переопределен в каждом классе – потомке CFigure. Поэтому он объявлен как virtual. А на то, что его реализация отсутствует указывает = 0 после объявления.
Классы, у которых нет полей данных, а все методы виртуальные и абстрактные называются абстрактными классами или интерфейсами. Интерфейсам не нужны конструкторы и деструкторы – объекты этого типа создаваться не могут. Их единственная роль – задать интерфейс использования потомков.
20.Рекурсия. Рекуррентные структуры данных и рекурсивные алгоритмы. Алгоритм просмотра дерева каталогов файловой структуры.
рекурсия — способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи.
Пример
 при n > 0 и n! = 1 при n = 0
Задача «Ханойские башни».
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Рекуррентные структуры данных и рекурсивные алгоритмы:
Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Значение любой такой функции можно определить, вычисляя все ее значения начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения.
· Рекурсивные алгоритмы:
· Нахождение факториала заданного числа
· Поиск наибольшего элемента в массиве
· Поиск в упорядоченном массиве (двоичный поиск)
· Ханойские башни
· Размен крупной купюры по манеткам
· Деревья. Изучение рекурсии неразрывно связано с изучением рекурсивно определяемых структур данных, называемых деревьями (trees). Деревья используются как для упрощения понимания и анализа рекурсивных программ, так и в качестве явных структур данных. В свою очередь, рекурсивные программы используются для построения деревьев. Глобальная связь между ними (и рекуррентными отношениями) используется при анализе алгоритмов.
Алгоритм просмотра дерева каталогов файловой структуры
Создаем функцию которая получает список файлов F(string path) перебираем все файлы. Если у файла атрибут что она папка то F(имя файла) иначе возвращаемся.
|