Структуры данных. Очередь

Для решения задачи по информатике (впрочем, это верно для лю-
бых задач) необходимо обработать известные исходные (входные) дан-
ные по некоторому составленному алгоритму. Под входными данными мы
понимаем имеющуюся у нас информацию о рассматриваемой задаче.
Мы можем хранить входные и промежуточные данные по разному.
Метод хранения данных существенным образом может влиять на выбор
алгоритма и наоборот, алгоритм может влиять на вид, в котором дан-
ные необходимо хранить в программе (т.е. на структуру данных).
Самая простая структура данных, известная всем — это массив (таб-
лица).
Рассмотрим еще одну из базисных структур данных.
Структура данных ‘очередь’.
Очередь в программировании, как и очередь в магазине, имеет
начало и конец. Если приходит новый элемент, то он становится в
конец очереди, если необходимо взять элемент из очереди, то он бе-
рется из ее начала. По другому говорят, что очередь — это структу-
ра типа FIFO — «First In — First Out» — первым зашел, первым вы-
шел.
Очередь будем представлять в виде массива. Пусть у нас есть
индекс первого — BEG и последнего — FIN элементов очереди (если
очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).
Очередь опишем так (все обозначения и процедуры даны на языке
Pascal):
type Queue=array[1..MaxQ] of element;
var Q: Queue;
Тут Queue — тип данных «очередь», Q — структура этого типа, MaxQ —
максимальное число элементов в очереди, element — какой-то тип
данных.
С очередью можно проводить операции:
вставка в очередь InQueue,
удаление из очереди OutQueue.

Procedure InQueue (var Q: Queue; var FIN: integer; x: element);
begin
FIN:=FIN+1; { на первое свободное место}
Q[FIN]:=x; { ставим элемент x }
end;

Procedure OutQueue (var Q: Queue; var BEG: integer;
var x: element);
begin

— 2 —

x:=Q[BEG]; { берем первый элемент }
BEG:=BEG+1; { и изменяем указатель }
{ на следующий за ним }
end;
Для большей корректности процедур требовалось бы еще прове-
рить перед удалением элемента, не пуста ли очередь, а перед встав-
кой элемента в очередь — не заполнен ли уже массив Queue пол-
ностью.
Продемонстрируем применение очереди при решении задач.
1. Даны обозначения двух полей шахматной доски (например, A5
и C2). Найти минимальное число ходов, которые нужны шахматному ко-
ню для перехода с первого поля на второе 0 1и сами ходы 0.
Раз перемещения коня будут проходить по шахматной доске, то
заведем соответствующий доске целочисленный массив A[1..8,1..8].
Первоначально положим все элементы этого массива нулевыми.
Идея решения основывается на использовании очереди. В качест-
ве элемента очереди element можно взять структуру следующего вида:
type element = record
x: integer;
y: integer;
end;
Тут element — это запись, состоящая из x-овой и y-овой координаты
коня на шахматной доске. Вначале в очередь помещается элемент, оп-
ределяющий исходное положение шахматного коня, а элемент массива
A, соответствующий этой клетке шахматной доски, помечается как по-
сещенный (например, в эту ячейку поставим 1).
На каждом из следующих шагов алгоритма (пока очередь не пуста
или не помечена конечная клетка) выполняются следующие действия.
1. Из очереди извлекается очередной элемент, определяющий неко-
торую позицию (x,y).
2. Находятся клетки в пределах поля, которые достижимы из (x,y)
одним ходом шахматного коня и которые еще не помечены.
3. Элементы, соответствующие найденным клеткам, помещаются в
очередь, а клетки помечаются как посещенные.
При этом метку желательно ставить такую, чтобы можно было
восстановить путь между полями. Для этого метку поля можно опреде-
лить как номер хода, на котором эта клетка была помечена (или по-
зицию поля, из которой клетка была помечена, или номер одного из 8
возможных ходов коня, сделав который конь попадает в эту позицию).
После этого восстановление маршрута коня не представляет особой

— 3 —

сложности.
Для быстрой проверки, попадают ли клетки, достижимые из
(x,y), на шахматное поле или нет можно сделать следующее: окаймим
матрицу A двумя граничными слоями. Получим A[-1..10,-1..10]. За-
полним эти два граничных слоя числами -1. После этого проверка
принадлежности поля шахматной доске аналогична проверке на нера-
венство содержимого поля -1.
Константу MaxQ в определении очереди можно положить равной
64, так как в очереди не может быть более 64 элементов (на доске
64 клетки и клетка в очередь может ставиться не более 1 раза).
Данный метод решения задачи называется «поиском в ширину»: на
первом этапе мы находим все клетки, непосредственно достижимые из
начальной; на втором этапе мы находим все клетки, достижимые из
начальной за два шага (или, что то же — все клетки, достижимые из
клеток, полученных на первом этапе), и т. д. до тех пор, пока не
будет найдено решение (или установлено, что его не существует).
Объясните, почему описанная выше структура данных «Очередь»
не применима для решения задачи #2.
2. Начиная с клетки А1 обойти ходом коня всю шахматную доску,
посетив каждую клетку ровно один раз.
Попытайтесь предложенным методом решить следующие задачи.
3. На олимпиаду прибыло N человек. Некоторые из них знакомы
между собой. Незнакомые люди могут познакомиться только через об-
щего знакомого. Можно ли опосредованно перезнакомить их всех между
собой, если вводится, кто с кем знаком.
В этой задаче размер очереди MaxQ достаточно взять равным N.
Всех можно перезнакомить между собой, если, например, человека 1
можно познакомить со всеми остальными.
Задача #4 предлагалась на 9-ой латвийской республиканской
олимпиаде по информатике.
4. Пусть есть три мерных стакана объемом 100 мл каждый. Пер-
вые два стакана имеют по 4 метки (риски). Каждая риска показывает
объем, отмеренный от дна стакана до этой риски. Объем написан ря-
дом с риской (см. рисунок 0 11). Первоначально первый стакан содержит
100 мл жидкости, а два остальные — пустые. Написать программу, ко-
торая определяет, можно ли отмерить один миллилитр жидкости, и,
если можно, находит минимальное количество шагов-переливаний, не-
обходимое для этого. После каждого переливания либо один из двух
участвующих в переливании стаканов должен стать пустым, либо со-
держать жидкость до метки.

— 4 —

Glasses
рис.

Входные данные: четыре целых положительных числа, которые со-
ответствуют меткам на двух первых мерных стаканах. Для каждой мет-
ки V имеет место неравенство 1<=V<=100.
Пример: 37 13 71 100
Вывод: напечатать строку «Да», если можно отмерить один мил-
лилитр жидкости и «Нет» в противном случае. Если ответ «Да», то
выдать минимальное количество переливаний.
Пример: Да 8
Проверьте свою программу на приведенных 10-и тестах:

# Метки Вывод
1 100 16 99 2 Да 1
2 35 100 65 10 Нет
3 32 64 100 17 Да 27
4 14 63 98 100 Нет
5 13 95 25 29 Да 3
6 17 37 57 77 Да 14
7 8 6 4 2 Нет
8 19 86 5 87 Да 2
9 49 41 87 5 Да 6
10 100 7 79 72 Да 55

Замечание: У нас три стакана по 100 мл в каждом. Поэтому мож-
но было бы конечно отображать текущее состояние тройкой чисел (a,
b, c), соответствующей объемам жидкости в каждом из трех стаканов.
Для этого понадобилась бы матрица С[0..100, 0..100, 0..100] разме-
ром 1030301 элемент.
Но обратим внимание на то, что объем жидкости ровно 100 мл и
поэтому количество в третьем стакане есть 100-a-b. Следовательно,
текущее состояние полностью описывается парой (a,b) и мы можем
обойтись двумерным массивом С[0..100, 0..100].
Рассматриваемую структуру данных можно применять и при залив-
ке изображений:
15. На экране заданы замкнутый контур и точка внутри него.
Закрасить фигуру, ограниченную контуром, указанным цветом.
Заданную точку ставим в очередь.
Пока очередь не пуста повторяем следующие операции:

— 5 —

Извлекаем точку из очереди. Для нее находим назакрашенные со-
седние точки, являющиеся внутренними точками контура. Закрашиваем
их и помещаем в очередь.
Этот алгоритм не является самым эффективным и на практике
обычно пользуются другими, более быстрыми.
Для решения некоторых задач требуется заводить не одну оче-
редь, а несколько (приведенная ниже задача взята из книги А.Шеня
«Программирование: теоремы и задачи»).
16. Напечатать в порядке возрастания первые n натуральных чи-
сел, в разложение которых на простые множители входят только числа
2, 3, 5. 0
Введем три очереди x2, x3, x5, в которых будем хранить эле-
менты, которые в 2 (3, 5) раз больше напечатанных, но еще не напе-
чатаны. Пусть переменные BEG2, BEG3 и BEG5 являются указателями на
начало этих очередей, a FIN2, FIN3, FIN5 — на конец. Определим
процедуру Print_and_Add (напечатать и добавить в очереди)
procedure Print_and_Add (t: integer);
begin
writeln (t);
InQueue(x2, FIN2, 2*t);
InQueue(x3, FIN3, 3*t);
InQueue(x5, FIN5, 5*t);
end;
и функцию Next (посмотреть следующий элемент)
function Next (Q: Queue; BEG: integer): integer;
begin
Next:=Q[BEG];
end;

Алгоритм программы:
1) сделать x2, x3, x5 пустыми
2) Print_and_Add(1);
3) k := 1;
k — число напечатанных в порядке возрастания минимальных
членов нужного множества; в очередях находятся элементы,
вдвое, втрое и впятеро большие напечатанных, но не напеча-
танные, расположенные в возрастающем порядке;
4) while k <> n do begin
x := min (Next(x2,BEG2), Next(x3,BEG3), Next(x5,BEG5));
Print_and_Add (x);

— 6 —

k := k+1;
Удалить x из тех очередей, где он был очередным;
end;

Рассмотрим наименьший из ненапечатанных элементов множества;
пусть это x. Тогда он делится нацело на одно из чисел 2, 3, 5, и
частное также принадлежит множеству. Значит, оно напечатано. Зна-
чит, x находится в одной из очередей и, следовательно, является в
ней первым (меньшие напечатаны, а элементы очередей не напечата-
ны). Напечатав x, мы должны его изъять и добавить его кратные.
Как мы видим, структура данных «очередь» часто применяется
для алгоритма поиска в ширину. Однако иногда для поиска в ширину
очередь явно можно и не заводить.
Рассмотрим задачу 6-й Международной олимпиады по информатике.
17. На рис.2 изображен треугольник, состоящий из чисел. Напи-
шите программу, которая вычисляет наибольшую сумму чисел, располо-
женных на пути, начинающемся в верхней точке треугольника и закан-
чивающемся на основании треугольника.
— Каждый шаг пути может осуществляться вниз по диагонали влево
или вниз по диагонали вправо.
— Число строк в треугольнике больше 1 и не превышает 100.
— Треугольник составлен из целых чисел от 0 до 99.

27
23 8
28 1 0
22 7 4 4
24 5 2 6 5

рис.2
Входные данные
Первым числом во входном файле с именем INPUT.TXT является коли-
чество строк в треугольнике. Пример файла исходных данных для при-
веденного на рис.2 треугольника представлен ниже.
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

— 7 —

Выходные данные
В выходной файл с именем OUTPUT.TXT записывается только наибольшая
сумма в виде целого числа. Ниже приведен файл OUTPUT.TXT для опи-
санных выше исходных данных.
30
Путь начинается в верхней точке треугольника. Если бы в треу-
гольнике была одна строка, то число из первой строки и давало бы
искомый результат.
Если бы в треугольнике было 2 строки, то в первый элемент
второй строки можно попасть только сверху справа (сумма чисел пути
7+3=10), а во второй элемент второй строки — только сверху слева
(сумма 7+8=15).
Пусть мы для каждого элемента i-й строки знаем наибольшую
сумму чисел для пути, начинающегося в верхней точке треугольника и
заканчивающегося в этом элементе. Вычислим такие суммы для (i+1)-й
строки.
В любой элемент (i+1)-й строки мы можем попасть только из
элементов i-й строки, лежащих над ним. Получаем, что наибольшая
сумма пути, заканчивающегося в данном элементе (i+1)-й строки есть
величина этого элемента плюс максимум из суммы путей, заканчиваю-
щихся в элементах i-й строки, расположенных сверху по диагонали
слева или сверху по диагонали справа.
Тут мы опять применяем «поиск в ширину»: на первом шаге мы
находим все наибольшие суммы путей в треугольнике из одной строки;
на втором шаге — наибольшие суммы путей в треугольнике из двух
строк, и т. д. до тех пор, пока не будет найдено решение для за-
данного треугольника.
В данном случае нам нет необходимости заводить очередь, так
как элементы треугольника уже хранятся по строкам в порядке, соот-
ветствующем порядку обработки элементов очереди.

ЧАСТЬ II

При работе с очередью начало очереди будет сдвигаться к концу
массива и может возникнуть ситуация, когда мы не сможем вставить в
очередь новый элемент, хотя в массиве есть свободные ячейки. Для
избежания этого можно сделать очередь кольцевой — т.е. считать,
что за последним элементом массива с индексом MaxQ следует первый
элемент массива. Таким образом, если в массиве есть пустые ячейки,
то можно выполнить операцию вставки в очередь.
Напишите самостоятельно процедуры вставки и удаления элемен-
тов в кольцевую очередь.
Рассмотрим еще одну задачу, связанную с очередями.
11. Фоpма тела задана матpицей А pазмеpности MxN. Элементы
матpицы — натуpальные числа. Элемент А(i,j) соответствует высоте
гоpизонтальной квадpатной площадки pазмеpа 1×1 относительно нижне-
го основания. Нижнее основание фоpмы горизонтально. 0
Опpеделить объем невытекшей воды, если
a) Тело опускается полностью в воду, затем поднимается;
Пример:
15 3 1
А = 5 2 5
12 5 5
После подъема вода останется только во внутреннем углублении,
над элементом А(2,2)=1.
Объем воды равен 1. 0
Окаймим матрицу A[1..N, 1..M] нулями: введем дополнительные
нулевые 0-ю и (N+1)-ю строки и 0-й и (M+1)-й столбцы.
Находим максимальный элемент D в матрице A. Пока все элементы
в матрице A не станут равны D, повторяем следующую последователь-
ность действий:
а) Находим в матрице минимальный ненулевой элемент z (если их
несколько, то берем любой из них), и заносим его в очередь (оче-
редь сначала пустая). Если этот минимальный ненулевой элемент z=D,
то СТОП.
Обозначим через p минимальную высоту граничных элементов об-
ласти, заполненной элементами со значением z. Сначала полагаем
p=D.
б) Для каждого еще не просмотренного элемента очереди (пусть
в матрице этот элемент находится в позиции (i,j)) повторяем следу-
ющее:
Для каждого соседа (сверху, снизу, справа, слева) данного
элемента (i,j) проводим проверку-просмотр:
ЕСЛИ (сосед <> z)
ТО P=min{P,сосед}
ИНАЧЕ ЕСЛИ сосед еще не просмотрен
ТО координата соседа — в очередь (в очереди появился
еще один непросмотренный элемент с высотой z)
т.е. мы ищем минимальную высоту окаймляющих элементов области, заполненной
элементами со значением z.
Фрагмент программы поиска:
const Delta : array [1..4,1..2] of integer =
((0,1),(1,0),(-1,0),(0,-1));
{ Delta — возможные смещения соседних клеток от текущей клетки }
Current, neighbor : element;
z : integer;
….
{ Будем обозначать то, что элемент в матрице уже просмотрен }
{ умножением его на -1 }
{ минимальный ненулевой элемент матрицы имеет значение z }

while BEG<>FIN+1 do begin
OutQueue(Q,BEG,Current);
for i:=1 to 4 do begin
neighbor.x:=Current.x+Delta[i,1];
neighbor.y:=Current.y+Delta[i,2];
if A[neighbor.x,neighbor.y]=z
then
begin
InQueue(Q,FIN,neighbor);
A[neighbor.x,neighbor.y]:=-z;
end
else p:=min(abs(A[neighbor.x,neighbor.y]),p);
end;
end;
Если в очереди нет больше непросмотренных элементов, то, если
pz, то высчитываем, сколько воды поместится в
«бассейн» с глубиной дна z и с высотой ограждающего бордюра p:
Объем = (p-z)* количество просмотренных элементов в очереди.
Добавляем полученный объем к ранее найденному объему воды,
заполняющему матрицу до высоты x и заполняем в матрице элементы,
соответствующие просмотренным элементам из очереди, значением p
(«Доливаем» воды в «бассейн» до уровня p).
Переход на пункт а).
Суммарный полученный объем воды и является искомым.
Напишите программу самостоятельно для поставленной задачи, и
для случая, когда задача ставится следующим образом.
Опpеделить объем невытекшей воды, если в позицию (i 40 1,j 40 1) вы-
ливается объем воды V.
Очереди часто применяются для решения задач, связанных с по-
иском в лабиринтах.
12. Лабиринт задается матрицей C размера N*M, где C[i,j]=1,
если через клетку (i,j) можно пройти и C[i,j]=0 иначе. Из текущей
клетки (i,j) можно идти только в одном из четырех направлений —
вверх, вниз, вправо, влево.
Из заданной клетки (x,y) найти кратчайший путь из лабиринта.
Клетку (x,y) ставим в очередь и применяем алгоритм поиска в
ширину. Как только мы достигнем границы матрицы C — мы найдем
кратчайший путь из лабиринта. Для того, чтобы его выписать, необ-
ходимо проследить, каким образом мы попали в эту граничную точку
из начальной.
13. Матрица размера N*M определяет некоторый лабиринт. B мат-
рице элемент 1 обозначает стену, а 0 определяет свободное место. В
первой строке матрицы определяются входы x(i), а в последней -1 вы-
ходы y(i), i=1,..,k, которые должны быть нулевыми элементами.
Необходимо определить, можно ли
а) провести k человек от входа x(i) до выхода y(i) соот-
ветственно, i=1,..,k, таким образом, чтобы каждое свободное место
посещалось не более одного раза.
б) то же, но человека можно выводить чеpез любой из выходов.
Примечание: Движение в лабиринте осуществляется только по
вертикали или горизонтали.
Легко заметить, что для существования решения необходимо про-
водить людей от самого левого входа к самому левому выходу,от са-
мого правого — к правому и т.д. Поэтому приведем решение только
для случая а).
Основная стратегия человека, вошедшего в самый левый вход,
состоит в прохождении лабиринта, используя наиболее левые свобод-
ные места лабиринта, т.е. он должен двигаться, держась правой ру-
кой за «стенку» лабиринта. Этот процесс можно формализовать следу-
ющим образом. Находясь в очередной позиции лабиринта, он должен
помнить, с какой стороны он пришел сюда (слева, справа, сверху,
снизу), и, руководствуясь этой информацией, выбрать следующее наи-
более предпочтительное направление в новую позицию (куда он может
пойти и где еще не был). При этом все посещенные клетки помечают-
ся. Легко заметить, что если в позицию попали сверху, то наилучшим
направлением будет налево, затем вниз, и наконец направо. Именно в
таком порядке непосещенные клетки и следует ставить в очередь.
Аналогично можно определить последовательность наилучших направле-
ний для других случаев.
Таким образом находится (если он есть) путь через лабиринт
для человека, вошедшего через самый левый вход. Клетки пути, по
которым он прошел, считаются запрещенными для посещения.
Пути через лабиринт ищутся описанным способом для каждого из
входов x(i), i=1, …, k.
Часто в задачах встречается следующая конструкция — есть дома
и дороги, их соединяющие; у каждой дороги есть длина. По другой
терминологии такая конструкция называется графом, дома называются
«вершинами», дороги — «ребрами» или «дугами», а длина дороги —
«весом ребра» или «весом дуги». Таким образом фраза ‘Найти мини-
мальный вес пути между вершинами s и k в графе’ может быть переве-
дена так: ‘Есть дома и дороги их соединяющие. Также заданы длины
дорог. Найти кратчайшую длину пути от города s до города k, если
двигаться можно только по дорогам’. Если по дороге можно двигаться
только в одном направлении (дорога с односторонним движением), то
ей соответствует в графе направленная дуга, и граф в этом случае
называется ориентированным.
Приведем несколько задач, сформулированных и в терминах «до-
мов», и в терминах графов, при решении которых применяются очере-
ди.
14. Вводится N — количество домов и К — количество дорог. Дома
1пронумерованы от 1 до N. Каждая дорога определяется двумя номерами
1домов — концов дороги. Определить, можно ли попасть по этим доро-
1гам из дома i в дом j.
Эта задача стандартно решается алгоритмом поиска в ширину.
Ищем дома, достижимые из i за один шаг, затем — за два шага, и
т.д. до тех пор, пока не будет достигнут дом j или пока очередь не
станет пустой (что соответствует отсутствию решения).
15 . Вводится N — количество домов и К — количество дорог. Все
дороги с односторонним движением. Дома пронумерованы от 1 до N.
Каждая дорога определяется двумя номерами домов — началом и концом
дороги. Найти все дома, лежащие на кольцевых маршрутах, начинаю-
щихся и заканчивающихся в вершине 1.
Дом с номером i лежит на кольцевом маршруте если
— существует путь из дома 1 в дом i;
— существует путь из дома i в дом 1.
Сначала найдем все дома, в которые можно попасть из дома 1.
Для этого воспользуемся алгоритмом поиска в ширину и структурой
данных очередь. Обозначим множество этих домов через X.
Затем найдем все дома, из которых можно попасть в дом 1. Для
этого сначала поменяем направление всех дорог на противоположное,
а потом опять же воспользуемся алгоритмом поиска в ширину из дома
1. Обозначим множество домов, достижимых из первого по дорогам с
измененным направлением движения через Y.
Пересечение множеств X и Y дает решение поставленной задачи.
Следующие 2 задачи взяты из книги А.Шеня «Программирование:
теоремы и задачи».
16. Известно, что ориентированный граф связен, т. е. из любой
вершины можно пройти в любую по ребрам. Кроме того, из каждой вер-
шины выходит столько же ребер, сколько входит. Доказать, что су-
ществует замкнутый цикл, проходящий по каждому ребру ровно один
раз. Составить алгоритм отыскания такого цикла.
Змеей будем называть непустую очередь из вершин, в которой
любые две вершины соединены ребром графа (началом является та вер-
шина, которая ближе к началу очереди). Стоящая в начале очереди
вершина будет хвостом змеи, последняя — головой. На рисунке змея
изобразится в виде цепи ребер графа, стрелки ведут от хвоста к го-
лове. Добавление вершины в очередь соответствует росту змеи с го-
ловы, взятие вершины — отрезанию кончика хвоста.
Вначале змея состоит из единственной вершины. Далее мы следу-
ем такому правилу:
while змея включает не все ребра do begin
if из головы выходит неиспользованное в змее ребро
then begin
удлинить змею этим ребром
end
else begin
{голова змеи в той же вершине, что и хвост}
отрезать конец хвоста и добавить его к голове
{«змея откусывает конец хвоста»}
end;
end;
Докажем, что мы достигнем цели.
1) Идя по змее от хвоста к голове, мы входим в каждую вершину
столько же раз, сколько выходим. Так как в любую вершину входит
столько же ребер, сколько выходит, то невозможность выйти означа-
ет, что голова змеи в той же точке, что и хвост.
2) Змея не укорачивается, поэтому либо она охватит все рёбра,
либо, начиная с некоторого момента, будет иметь постоянную длину.
Во втором случае змея будет бесконечно «скользить по себе». Это
возможно, только если из всех вершин змеи не выходит неиспользо-
ванных ребер. В этом случае из связности следует, что змея прохо-
дит по всем ребрам.
17. Доказать, что для всякого n существует последовательность
нулей и единиц длины 5n со следующим свойством: если «свернуть ее
в кольцо» и рассмотреть все фрагменты длины n (их число равно 5n ),
то мы получим все возможные последовательности нулей и единиц дли-
ны n.
Рассмотрим граф, вершинами которого являются последователь-
ности нулей и единиц длины (n-1). Будем считать, что из вершины x
ведет ребро в вершину y, если x может быть началом, а y — концом
некоторой последовательности длины n. Тогда из каждой вершины вхо-
дит и выходит два ребра. Цикл, проходящий по всем ребрам, и даст
требуемую последовательность.
Решите самостоятельно, используя очередь, следующую задачу:
18. Даны обозначения двух полей шахматной доски (например, A5
1и C2). Может ли шахматный конь перейти с первого поля на второе за
11) N ходов (N вводится);
12) четное число ходов;
13) нечетное число ходов.

И. Волков

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>