9.4 Cоставить прграмму на Asm для преобразования строчных букв в прописные

Строчные – 61h – 7Ah

Прописные – 41h - 5Ah

a -> 01100001 ; z ->01111010

A-> 01000001 ; Z ->01011010

.model small

.stack 100h

.data

N equ 10

Stroka db ‘askdienckd’

.code

Start:

Mov ax,@data

Mov ds,ax

Xor ax,ax

Mov cx,N

Lea bx,Stroka

M1: mov al,[bx]

Cmp al,61h

Jb Next

Cmp al,7ah

Ja next

And al,11011111b

Mov [bx],al

Next:

inc bx

dec cx

jnz M1

exit:

mov ax,4c00h

int 21h

end start

9.5

100подсетей

2000 узлов

100п/с₁₀=1100100₂ - 7 бит – используем для маски подсети

2000 узлов =11111010000 - 11 бит

7+11 = 18 бит

выбираем класс А

11111110₂=254₁₀

маска подсети 255.254.0.0

1+8+8=17 - “0”

2⁷-2=126п/с 126-100=26-запас подсетей

2¹⁷-2=131070

131070-2000=129070-запас узлов

10.1 Общие операции над деревьями. Процедуры добавления и удаления элемента. Количество листьев и узлов в дереве.

Существует 3 способа обхода бинарного дерева: в прямом порядке, в симметричном порядке, в обратном порядке.

В прямом порядке:

2. Попасть в корень 2 Пройти в прямом порядке левое поддерево 3 Пройти в прямом порядке правое поддерево

В симметричном порядке:

2. Пройти в симметричном порядке левое поддерево 2 Попасть в корень 3 Пройти в симметричном порядке правое поддерево

В обратном порядке:

2. Пройти в обратном порядке левое поддерево 2 Пройти в обратном порядке правое поддерево 3 Попасть в корень

Алгоритм поиска можно записать, пользуясь рекурсивным определением двоичного дерева в рекурсивном виде. Если искомый элемент Item меньше Tree^.Item, то поиск продолжается в левом поддереве, если равен – то поиск считается успешным, если больше – поиск продолжается в правом поддереве; поиск считается неудачным, если мы дошли до пустого поддерева, а элемент найден не был. Программу лучше писать рекурсивную для избежания избыточности. Каждый рекурсивный вызов размещает в стеке локальные переменные Item и Tree, а также адрес точки возврата из подпрограммы. В нерекурсивном варианте можно обойтись одной переменной Item и одной переменной Tree.

Восстановление сбалансированности.

Пусть имеется дерево, сбалансированное всюду, кроме корня, а в корне показатель сбалансированности по модулю равен 2-м. Такое дерево можно сбалансировать с помощью одного из четырех вращений. При этом высота дерева может уменьшиться на 1. Для восстановления баланса после удаления/добавления вершины надо пройти путь от места удаления/добавления до корня дерева, проводя при необходимости перебалансировку и изменение показателя сбалансированности вершин вдоль пути к корню. Можно доказать, что в других вершинах перебалансировка и изменение показателя сбалансированности не понадобятся.

Добавление элемента в сбалансированное дерево.

Схематично алгоритм вставки нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:

2. Поиск по дереву. 2 Вставка элемента в место, где закончился поиск, если элемент отсутствует. 3 Восстановление сбалансированности.

1-ый шаг необходим для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным. Первые два шага ничем не отличаются от алгоритма, приведенного в начале разделе.

3-ий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.

Удаление элемента из сбалансированного дерева.

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

1Поиск по дереву. 2 Удаление элемента из дерева. 3 Восстановление сбалансированности дерева (обратный проход).

1-ый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена. Первых два шага аналогичны удалению элемента, приведенному в начале раздела.

3-ий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.

Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, то есть порядка log(N) вершин. Доказательство того, что порядок числа вершин имеет такой аналитический вид, смотрите в следующем разделе.

Анализ операций над сбалансированным деревом.

Понятно, что в случае полного двоичного дерева (наилучший случай) мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):

Покажем, что h<log₂(N_h). Для этого необходимо и достаточно показать, что 2^h>N_h. Докажем последнее методом математической индукции.а) h=0: 2⁰>N₀=0; б) h=1: 2¹>N₁=1; в) h>1: Пусть 2^h-2>N_h-2 и 2^h-1>N_h-1. Тогда 2^h-2+2^h-1>N_h-2+ N_h-1.

И далее получаем 2^h>1+2^h-2+2^h-1>1+N_h-2+ N_h-1=N_h, что и требовалось доказать.

Таким образом, мы доказали, что алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)).

Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.

// симметричное рекурсивное прохождение узлов дерева

template <class T>

void Inorder (TreeNode<T> *t, void visit(T& item))

{

// рекурсивное прохождение завершает-ся на пустом поддереве

if (t != NULL)

{ Inorder(t->Left(), visit); // спуститься по левому поддереву

visit(t->data); // посетить узел

Inorder(t->Right(), visit); // спуститься по правому поддереву

}

}