С помощью деревьев можно представлять произвольные арифметические выражения. Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу √ операция. В общем случае дерево при этом может оказаться не бинарным.
Однако если число операндов любой операции будет меньше или равно двум, то дерево будет бинарным. Причем если все операции будут иметь два операнда, то дерево окажется строго бинарным.
Рис.. Представление арифметического выражения произвольного вида в виде дерева.
Рис. Представление арифметического выражения в виде бинарного дерева
Бинарные деревья могут быть использованы не только для представления выражений, но и для их вычисления. Для того чтобы выражение можно было вычислить, в листьях записываются значения операндов.
Затем от листьев к корню производится выполнение операций. В процессе выполнения в узел операции записывается результат ее выполнения. В конце вычислений в корень будет записано значение, которое и будет являться результатом вычисления выражения.
Помимо арифметических выражений с помощью деревьев можно представлять выражения других типов. Примером являются логические выражения. Поскольку функции алгебры логики определены над двумя или одним операндом, то дерево для представления логического выражения будет бинарным
Рис. Вычисление арифметического выражения с помощью бинарного дерева
Рис. Представление логического выражения в виде бинарного дерева
Рассмотрим как связаны спрособы обхода дерева с различными формами записи выражения.Терминология способов охода дерева «префиксный», «инфиксный», «постфиксный» явно связана с обходом бинарного дерева, представляющего арифметическое выражение с бинарными операциями. Пусть, например, дано арифметическое выражение
Соответствующее бинарное дерево.
Рис. Бинарное дерево, представляющее
Тогда три варианта обхода этого дерева порождают три известные формы записи арифметического выражения:
1) КЛП — префиксную запись
2) ЛКП — инфиксную запись (без скобок, необходимых для задания последовательности выполнения операций)
3) ЛПК — постфиксную запись
ЛЕКЦИЯ 12. ГРАФЫ ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ. СПОСОБЫ ЗАДАНИЯ И РЕАЛИЗАЦИЯ
Цели и задачи лекции: показать способы задания и реализация графов
Основные рассматриваемые вопросы. Основные определения. Способы задания и реализация графов. Наличие циклов, связность.
Граф G — это упорядоченная пара (V, Е), где V- непустое множество вершин, Е — множество пар элементов множества V, называемое множеством ребер.
Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным (орграфом).
Если дуга е ведет от вершины vl к вершине v2, то говорят, что дуга е инцидентна вершине v2, а вершина v2 являются смежной вершине vv В случае неориентированного графа ребро е является инцидентной обеим вершинам vl и v2, а сами вершины — взаимно смежными.
Путь — это любая последовательность вершин орграфа такая, что в этой последовательности вершина в может следовать за вершиной а, только если существует дуга, следующая из а в в .
Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом. Граф, в котором отсутствуют циклы, называется ациклическим.
Петля — дуга, соединяющая некоторую вершину сама с собой.
— Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов.
При дальнейшем изложении будем предполагать, что вершины графа обозначены символьной строкой и всего их до п, а ребер — до т. Каждое ребро и каждая вершина имеют вес — целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.
Матрица смежности — это двумерный массив V, размером пХп:
При этом vij=0, если вершина i не смежна вершине; vij=весу ребра (дуги), если вершина i смежна вершине j, vij=весу петли.
Пространственная сложность этого способа V(n)
O(n 2 ). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.
Матрица инцидентности — это двумерный массив U размером пХт:
При этом uij=0, если вершина i не инцидентна ребру j, uij=весу ребра, если вершина инцидентна ребру j.
Пространственная сложность этого способа V(n, m)
O(n*m). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине х».
Списки смежных вершин — это одномерный массив размером п, содержащий для каждой вершины указатели на списки смежных с ней вершин:
Weight: integer; <вес ребра>
Next: PNode;
TAdjacencyList = array [l..n] of record
NodeWeight: integer; <вес вершины>
Name: string;
Пространственная сложность этого способа Fmax(w)
0(w 2 ). Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под п соседей для каждой вершины. Можно и сам массив представить в виде динамического списка, но это не имеет особого смысла, так как граф обычно является статичной (неизменяемой) структурой.
Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с х».
Список ребер — это одномерный массив размером т, содержащий список пар вершин, инцидентных с одним ребром графа:
Пространственная сложность этого способа V(m)
O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.
PBranch = A TBranch;
Next: PNode; <следующая вершина>end; TBranch = record
Пространственная сложность этого способа V(n, m)
Дата добавления: 2018-05-02 ; просмотров: 866 ; ЗАКАЗАТЬ РАБОТУ
Инструкция . При вводе с клавиатуры используйте следующие обозначения:
| Клавиша | Оператор | |
|---|---|---|
| ! | ¬ | Отрицание (НЕ) |
| | | | | Штрих Шеффера (И-НЕ) |
| # | ↓ | Стрелка Пирса (ИЛИ-НЕ) |
| * | & | Конъюнкция (И) |
| + | v | Дизъюнкция (ИЛИ) |
| ^ | ⊕ | Исключающее ИЛИ, сумма по модулю 2 (XOR) |
| @ | → | Импликация (ЕСЛИ-ТО) |
| % | ← | Обратная импликация |
| = | ≡ ( |
, ↔)
bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.
Правила ввода логической функции
- Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
- Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
- Максимальное количество переменных равно 10 .
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
Составьте деревья для вычисления логических выражений и таблицы истинности этих выражений:
Лучший ответ:
Первое рис.1
Второе рис.2
Другие вопросы:
Решите уровнение (9-2х)(2х-9)*34^5
В каких вычислениях есть ошибки ? Исправь их. Задание 37 .
Молочный завод отправил в магазин 56 ящиков сливочного масла, по 20 кг в каждом. За день продали одну седьмую часть этого масла. Сколько килограммов масла осталось ?
В двух корзинах 120 яблок. После того как из этих корзин взяли яблок поровну, в одной корзине осталось 24 яблока, а в другой 36. Сколько яблок было в каждой корзине?166 задача
Срочно. помогите пожалуйста решить интеграл методом интегрирования по частям. S arcsinx dx