суббота, 30 ноября 2019 г.
среда, 27 ноября 2019 г.
пятница, 8 ноября 2019 г.
Основы логики
Высказывание - предложение, относительно которого можно однозначно сказать: истинно оно или ложно.
Рассмотрим результат выполнения основных логических операций ("И", "ИЛИ" и "НЕ") для двух высказываний A и B:
Значения A | Значения B | A И В | A ИЛИ B | НЕ A |
---|---|---|---|---|
Ложь | Ложь | Ложь | Ложь | Истина |
Ложь | Истина | Ложь | Истина | Истина |
Истина | Ложь | Ложь | Истина | Ложь |
Истина | Истина | Истина | Истина | Ложь |
Множество и логика.Для обозначения логической операции «ИЛИ» будем использовать символ «|», для логической операции «И» – символ «&», "НЕ" - "~", количество элементов в множестве A - k(A).
Операция над множествами A и B | Иллюстрация на кругах Эйлера | Условие принадлежности элементов x | Количество элементов |
---|---|---|---|
Объединение A ∪B | x ∈ A | x ∈ B | k(A∪B)=k(A)+k(B)-A∩B | |
Пересечение A∩B | x ∈ A & x ∈ B | ||
Дополнение | x ~ B |
среда, 6 ноября 2019 г.
Двоичное дерево
Двоичное дерево
1) пустая структура — это двоичное дерево;
2) двоичное дерево — это корень и два связанных с ним отдельных двоичных дерева (левое и правое поддеревья).
Приминение:
- поиск в большом массиве данных;
- сортировка данных;
- вычисление арифметических выражений;
- оптимальное кодирование данных (метод сжатия Хаффмана)
Опишем дерево из примера с помощью словаря Python:
In [60]:
tree = {
'val': 6,
'right':{
'val': 8,
'right': { 'val': 9, 'right': {}, 'left': {} },
'left': { 'val': 7, 'right': {}, 'left': {} } },
'left':{
'val': 3,
'right': { 'val': 4, 'right': {}, 'left': {} },
'left': { 'val': 1, 'right': {}, 'left': {} } } }
Обход и вывод дерева
Обойти дерево — это значит «посетить» все узлы по одному разу. Существуют несколько способов обхода двоичного дерева. Например: "правый — корень — левый" (симметричный обход):
- обойти правое поддерево
- посетить корень
- обойти левое поддерево
Как видим, это рекурсивные алгоритм. Он должн заканчиваться без повторного вызова, когда текущий корень — пустое дерево. При выводе элементов, обход будем сочетать с выводом отступа '\t' - n раз:
In [61]:
def OutTree(x,n):
if x:
OutTree( x['right'], n+1 )
print( '\t'*n,x['val'] )
OutTree( x['left'], n+1 )
OutTree(tree,0)
9 8 7 6 4 3 1
Деревья поиска
- слева от каждого узла находятся узлы, ключи которых меньше или равны ключу данного узла;
- справа от каждого узла находятся узлы, ключи которых больше или равны ключу данного узла.
In [24]:
def FindInTree(x,y,n): # x - элемент, y - дерево, n - кол-во шагов
if y:
if x==y['val']:
print('Элемент',x,'найден за',n,
n>4 and 'шагов' or
n>1 and 'шага' or'шаг')
elif x<y['val']: FindInTree(x,y['left'],n+1)
else: FindInTree(x,y['right'],n+1)
else:
print('Элемент',x,'не найден. Проверено за',n,
n>4 and 'шагов' or
n>1 and 'шага' or'шаг')
FindInTree( 8, tree, 0)
FindInTree( 5, tree, 0)
FindInTree( 4, tree, 0)
Элемент 8 найден за 1 шаг Элемент 5 не найден. Проверено за 3 шага Элемент 4 найден за 2 шага
Вычисление арифметических выражений
Сначала выражение, записанное в линейном виде (в одну строку), нужно "разобрать" и построить соответствующее ему дерево. Затем в результате прохода по этому дереву от листьев к корню вычисляется результат. Пример: 40 - 2 3 - 4 5 В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.
Алгоритм построения дерева:
- найти последнюю выполняемую операцию
- if операций нет:
- создать узел-лист (число)
- return
- поместить найденную операцию в корень дерева
- построить левое поддерево
- построить правое поддерево
Программа получения дерева Tree из строки s:
In [145]:
def prt(x): # Функция определения приоритета:
# "число" - 3; "+-" - 1 или "*/" - 2
return (x in '+-') and 1 or (x in '*/') and 2 or 3
def last(s): # Функция определения последней операции (минимального приоретета)
# В какой позиции строки s она находиться
minPtr=3; k=3
for i in range(len(s)):
if prt(s[i])<=minPtr:
minPtr=prt(s[i])
k=i
return k
def makeTree(s):
y={}
if any(s):
k = last(s)
y['val'] = s[k]
y['left'] = makeTree( s[ :k] )
y['right'] = makeTree( s[k+1: ] )
return y
s = '40 - 2 * 3 - 4 * 5'.split()
Tree = makeTree(s)
OutTree(Tree,0)
5 * 4 - 3 * 2 - 40
Теперь вычислим выражение по дереву. Если в корне нахо- дится знак операции, её нужно применить к результатам вычисления поддеревьев:
- n1 = значение левого поддерева
- n2 = значение правого поддерева
- результат = операция (n1, n2)
In [147]:
def calcTree(x):
if x['left']:
n1 = calcTree(x['left'])
n2 = calcTree(x['right'])
op = x['val']
return op=="+"and n1+n2 or op=="-"and n1-n2 or op=="*"and n1*n2 or n1//n2
else: return int(x['val'])
calcTree(Tree)
Out[147]:
14
Подписаться на:
Сообщения (Atom)
-
Решения задач школьного этапа Всероссийской олимпиады школьников по информатике (9-11 классы) Московская область, 21-22 октября 2019 ...
-
Программирование разветвляющихся алгоритмов Неполное (сокращенное) ветвление Задача 1 Сколько k автомобилей понадобиться, чтобы...