Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания icon

Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания




НазваМетодические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания
Сторінка8/8
Дата конвертації26.02.2013
Розмір1.33 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8
Тема 17:^ ОЧЕРЕДИ, СТЕКИ, ДВОИЧНЫЕ ДЕРЕВЬЯ

17.1 Для работы с очередью, т.е. последовательностью элементов, в которую элементы всегда добавляются коней:, а удаляются из начала («первым пришел—первым ушел»), нужны обычно следующие –операции:

ОЧИСТОЧ(Q)—создать пустую очередь Q (очистить очередь);

ПУСТОЧ(Q)-проверить является ли очередь Q пустой;

ВОЧЕРЕДЬ(Q,х)-добавить в конец очереди ^ Q элемент;

ИЗОЧЕРЕДИ(Q,х)-удалить из очереди Q первый элемент, присвоив его параметру х.

Требуется для каждого из указанных ниже представлений очереди описать на Паскале соответствующий тип очередь, считая, что все элементы очереди имеют некоторый тип ТЭО, и реализовать в виде процедур или функций перечисленные операции над очередью (если операция по тем или иным причинам не может быть выполнена, следует передать управление некоторой процедуре ОШИБKA(k), считая ее уже описанной, где к—номер ошибки: 1—переполнение очереди, 2—исчерпание очереди).

Представление очереди (n—целая константа>1):

а)* для каждой очереди отводится свой массив из п компонент типа ТЭО, в котором элементы очереди занимают группу соседних компонент, индексы первой и последней из которых запоминаются (рис. 16, а); при этой, когда очередь достигает правого края массива, все ее элементы сдвигаются к левому краю;

б) аналогичное представление, но массив как бы склеивается в кольцо, поэтому если очередь достигает правого края массива, то новые элементы записываются в начало массива (рис. 16,6);

в) для каждой Очереди создается свой однонаправленный список из элементов типа ТЭ0 при этом запоминаются ссылки на первое и последнее звенья списка (рис. 16, в).

17.2 Используя очередь (считать уже описанными тип очередь при подходящем типе ТЭО, функцию ПУСТОЧ и процедуры ^ ОЧИСТОЧ, ВОЧЕРЕДЬ и ИЗОЧЕРЕДИ—cм.

17.1 решить следующую задачу (решение описать в виде процедуры).

a)*type FR=file of real;

За один просмотр файла f типа FR и без использования дополнительных файлов напечатать элементы файла f в следующем порядке: сначала—все числа, меньшие а, затем—все числа из отрезка [a,b], и наконец—все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел и b—заданные числа, а

б) Содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g перенося при этом






a)







б)

Рис. 16

в конец каждой строки все входящие в нее цифры (с сохранением исходного взаимного порядка как среди цифр, так и среди остальных литер строки),

в) type имя = (Анна,....Яков);

дети=расked* array [имя,имя]

of boolean;

потомки=file of имя;

Считая заданными имя ^ И и массив Д типа дети (Д[х,у]=иие, если человек по имени y является ребенком человека по имени х), записать в файл П типа потомки имена всех потомков человека с именем И в следующем порядке: сначала—имена всех его детей, затем—всех его внуков, затем всех правнуков и т. д.

17.3 Для работы со стеком, т. е. последовательностью элементов, в которой элементы всегда добавляются в конец и удаляются из конца («последним пришел —первым ушел») нужны обычно следующие операции:

ОЧИСТЕK(S)—создать пустой стек S (очистить стек);

ПУCTEK(S)—проверить, является ли стек S пустым;

BCTEK(S,x)—добавить в конец стека S элемент х:

ИЗСТЕКA(S,x)—удалить из очереди S последний элемент, присвоив его параметру х.

Требуется для каждого из указанных ниже представлений стека описать на Паскале соответствующий тип стек, считая, что все элементы стека имеют некоторый тип ТЭС, и реализовать в виде процедур или функций перечисленные операции над стеком (если операция по тем или иным причинам невыполнима, следует передать управление некоторой процедуре ошибка(k), считая ее уже описанной, где k—номер ошибки: 1—переполнение стека 2— исчерпание стека).

Представление стека (п— целая константа>1)

а) для каждого стека отводится свой массив из п компонент типа ТЭС, в начале которого располагаются элементы стека, при этом запоминается индекс компоненты массива, занятой последним элементом стека (рис. 17, а);






а)




…….

б)

Рис 17

б) для каждого стека создается свой однонаправленный список, в котором элементы стека располагаются в обратном порядке (рис. 17,б).

17.4. Используя стек (считать уже описанными тип стек при TЭC=char, функцию ПУСТЕК и процедуры ^ ОЧИСТЕК, ВСТЕК и ИЗСТЕКА—см. 17.3), решить следующую задачу (решение описать в виде процедуры или функции).

а) Напечатать содержимое текстового файла t, выписывая литеры каждой его строки в обратном порядке.

б) Проверить, является ли содержимое текстового файла t правильной записью формулы следующего вида:

<формула>::=<терм> | <терм>+<формула>|

<терм>—<формула>

<терм>::=<имя>|(формула)|[<формула>]|

{<формула>}

<имя>::=x|y|z

в)* В текстовом файле f записана без ошибок формула следующего вида!

<формула>::=<цифра> \ М<формула><формула>)

m(<формула>,< формула >) f

<цифра>::= 0|1|2|3|4||5|6|7|8|9

где М обозначает функцию max, a m—mln.

Вычислить (как целое число) значение данной формулы (например, М(5,m(6,8)) —»6).

г) В текстовом файле LOG записано без ошибок логическое выражение (ЛВ) в следующей форме!

<ЛВ>::=true|Ы8е|false|(┐ЛВ>)|(<ЛВ>∆< ЛВ >)| :.

<лв> v <лв>

где знаки "┐, ∆и V обозначают соответственно отрицание, конъюнкцию и дизъюнкцию.

Вычислить (как boolean) значение этого выражения.

17.5 Используя очередь и или стек (считать уже описанными их типы и операции над ними—см. 17.1 и 17.3), решить следующую задачу (решение описать в виде процедуры).

В текстовом файле t записан текст, сбалансированный по круглым скобкам:

<текст>::= <пусто>| <элемент> <текст>

<элемент>::=<буква> |<текст>

Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров позиций:

а) закрывающих скобок;

б) открывающих скобок.

Например, для текста А+(45—F(X)*(B—С)) надо напечатать) ...

а)8 10; 12 16; 3 17;

б)3 17; 8 10; 12 16.

17.6 Под «выражением» будем понимать конструкцию следующего вида:

<выражение>::=<терм>|

<терм><знак+—><вьгражение>

<терм>::=<множитель> |<множитель><терм>

<множитель>::=<чнсло> | <переменная> | (<выражевие>) |

<множитель> ↑<число>

<число>::=<цифр а>

<переменная>::=<буква>

где знак ↑ обозначает операцию возведения в степень.

Постфиксной формой еаписи выражения а∆b называется запись, в которой знак операции размещен за операндами! аЬ∆. Примеры:

a-b →ab-

a*b+c →ab*c+

a*(b+c) →abc+*

a+b↑c↑d*e →abc↑d↑e*+

а) Описать функцию value(postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в постфиксной форме в текстовом файле postfix.

Использовать следующий алгоритм вычисления. Выражение просматривается слева направо. Если встречается операнд (число), то его значение (как целое) заносится в стек, а если встречается знак операции, то из .стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция и ее результат записывается в стек. В конце концов в стеке оста­нется только одно число—значение всего выражения.

б) Описать процедуру translate(infix,postfix), которая переводит выражение, записанное в обычной (инфиксной) форме в текстовом файле infix, в постфиксную форму и в таком виде записывает его в текстовый файл postfix.

Использовать следующий алгоритм перевода. В стек записывается открывающая скобка, и выражение просматривается слева направо. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она. заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая также удаляется из стека, и все эти знаки (в порядке их извлечения) записываются в файл postfix. Когда же встречается знак операции, то из конца стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки опе­раций, старшинство которых больше или равно старшинству дайной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В завключение выполняются такие же действия, как если бы встретилась закрывающая скобка.

в) Описать (нерекурсивную) процедуру lnjixprint(postfix), которая печатает в обычной (инфиксной) форме выражение, записанное в постфиксной форме в текстовом файле postfix. (Лишние скобки желательно не печатать.)

^ В упражнениях 17.7—17.14 использовать двоичные деревья (рис. 18) при следующем их описаним

type ТЭД=...; {тип элементов дерева} дерево=↑веришна;

вершина =record элем:ТЭД;

лев,прав:дерево

end;

В этих упражнениях Т, Т1 и Т2 обозначают деревья, а Евеличину типа ТЭД.

17.7 Используя очередь или стек (считать уже описанными их типы и операции над ними—см. 17.1 и 17.3), описать процедуру или функцию, которая





Рис. 18

а) присваивает параметру ^ Е элемент из самого левого листа непустого дерева Т (лист—вершина, из которой не выходит ни одной ветви);

б)* определяет число вхождений элемента Е в дерево Т;

в) вычисляет среднее арифметическое всех элементов непустого дерева Т (ТЭД=rеа1)

г) заменяет в дереве Т все отрицательные элементы на их абсолютные величины (ТЭД=rеа1);

д) меняет местами максимальный и минимальный элементы непустого дерева 7, все элементы которого различны (ТЭД=rеа1);

с) печатает элементы из всех листьев дерева Т (ТЭД=reаl)

ж)* печатает все элементы дерева Т по уровням! сначала—из корня дерева, затем (слева направо)—из вершин, дочерних по отношению к корню, затем (также слева направо)—из вершин, дочерних по отношению к этим вершинам, и т. д. (ТЭД=integer);

з) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с элементом Е; если Е не входит в Т, за ответ принять —1;

и) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной 0-го уровня).



17.8. Описать рекурсивную функцию или процедуру, которая:

а) определяет, входит ли элемент Е в дерево Т

б)* определяет число вхождений элемента Е в дерево T;

в) вычисляет сумму элементов непустого дерева Т (ТЭД=rеа1);

г) находит величину наибольшего элемента непустого дерева Т (ТЭД=rеа1);

д) печатает элементы из всех листьев дерева Т (ТЭД= char);

е)* определяет максимальную глубину непустого дерева T, т. е. число ветвей в самом длинном из путей от корня дерева до листьев;

ж) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной 0-го уровня).

17.9. Рекурсивно и нерекурсивно описать логическую функцию equal(T1T2), проверяющую на равенство деревья Т1 и Т2.

17.10* Описать процедуру сору(Т,Т1) которая строит T1—копию дерева Т.

17.11 Описать процедуру create(T,n), где n—положительное целое число, которая строит Т—дерево, показанное на рис. 19.

  1. Описать логическую функцию same(T)t определяющего, есть ли в дереве Т хотя бы два одинаковых элемента.

  2. Формулу вида '

<формула>::=<термйнал> |

(<формула><знак><формула>)
<знак>::=+ |— |*

<тернинал>::=0|1 |2|3|4 |5 | 6|7|8 |9

можно представить в виде двоичного дерева («дерева-формулы») с ТЭД=char согласно следующим правилам:формула из одного терминала (цифры) представляется; деревом из одной вершины с этим терминалом, а формула вида



Рис. 20 Рис. 21

(f1 s f2)—деревом, в котором корень—это знак s, а левое и правое поддеревья — это соответствующие представления формул , f1 и f2. (На рис. 20 показано дерево-формула, соответствующее формуле (5*(3+8)).)

Описать рекурсивную функцию или процедуру, которая!

a) вычисляет (как целое число) значение дерева-формулы ^ Т;

б) по формуле из текстового файла f строит соответствующее дерево-формулу Т;

b) печатает дерево-формулу Т в виде соответствующей формулы;

г) проверяет, является ли двоичное дерево Т деревом- формулой. .

17.14 Пусть в дереве-формуле (см. упр. 17.13) в качестве терминалов используются не только цифры, но и буквы, играющие, роль переменных. Описать процедуру, которая:

а)* упрощает дерево-формулу T, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f),(f—0),

(f*1) и (1*f), на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f*0) и (0*f),—. на вершину с 0;

б) преобразует дерево-формулу ^ Т, заменяя в нем все поддеревья, соответствующие формулам (f1± f2)*f3) и (f1*(f2±f3), на поддеревья, соответствующие формулам

((f1* f3) ± (f2* f3)) ((f1* f2) ± (f1* f3))

в) выполняет в. Дереве- формуле Т преобразования, обратные преобразованиям из п. б;

г) cтроит дерево-формулу ^ Т1 —производную дерева- формулы Т' по переменной, однобуквенное имя которой являет значением литерного параметра v.

17.15 Предложить и описать на Паскале представление в виде двоичного дерева для формул из упр-. 17.13, в которых в качестве терминалов используются любые неотрицательные целые числа. Для такого представления реализовать те же операции, что и в упр. 17.13.

17.16 Деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины Находятся вершины с элементами, меньшими элемента из этой вершины, а справа— с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения); пример такого дерева показан на рис. 21.

Считая описанными тип дерево (см. выше) и тип файл

type файл=file of ТЭД;

определить функцию или процедуру, которая;

а) проверяет, входит ли элемент Е в дерево поиска Т;

б) записывает в файл f элементы дерева поиска ^ Т в порядке их возрастания;

в) добавляет к дереву поиска Т новый элемент Е, если его не было в T;

г) по файлу f, все элементы которого различны, строит соответствующее дерево поиска Т.

17.17 Во внешнем текстовом файле PROG записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и или цифр. Напечатать в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождении в текст программы. (Учесть, что в идентификаторах одноименные прописные и строчные буквы отождествляются, что внутри литерных

значений, строк-констант и комментариев последовательности из букв и цифр не являются идентификаторами, и что в записи вещественных чисел может встретиться буква Е или е.)

Для хранения идентификаторов использовать дерево поиска, элементами которого являются пары—идентификатор и число его вхождений в текст программы.

  1. решить предыдущую задачу, но вместе с каждым идентификатором печатать в возрастающем порядке номера всех строк текста программы, в которых он встречается.

  2. Решить задачу 17.17 при условии, что максимальная длина идентификаторов заранее не известна.

17.20 Решить задачу 17.18 при условии, что максимальная длина идентификаторов заранее не известна.

1   2   3   4   5   6   7   8



Схожі:

Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания и задания по дисциплине «Статистика. Часть 1» для студентов экономических специальностей всех форм обучения печ
Статистические показатели, Статистическое наблюдение, Сводка и группировка статистических данных, Средние величины Методические указания...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания для самостоятельной подготовки студентов всех специальностей запорожье, зиэит, 2003
Защита населения в чрезвычайных ситуациях мирного и военного времени / Методические указания для самостоятельной работы студентов...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания к подготовке и защите магистерских работ по специальности
Методические указания к подготовке и защите магистерских работ по специальности 050206 «Менеджмент внешнеэкономической деятельности»...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодичні вказівки до них. Для студентів ycix спеціальностей ycix форм навчання
Методические указания и задания по курсу «Введение в профессию» для слушателей подготовительных курсов всех форм обучения
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания к выполнению курсовой работы по дисциплине «Основы маркетинга» для студентов 2 курса дневной формы обучения
Бобрушева В. В. Методические указания к выполнению курсовой работы по дисциплине «Основы маркетинга» для студентов 2 курса дневной...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания и контрольные задания по дисциплине «основы программирования и алгоритмические языки» для студентов заочной формы обучения
Методические указания и контрольные задания по дисциплине «основы программирования и алгоритмические языки» для студентов заочной...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания рассмотрены и утверждены на заседании кафедры Технология машиностроения
Технологические методы проектирования и производства заготовок деталей машин для студентов специальностей 09. 0202, 09. 0203 дневной...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания по оформлению технической и научной документации для студентов специальности
Автоматизация проектирования компьютерных систем. Методические указания по курсовому проектированию для студентов специальности “Компьютерные...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания к практическим занятиям №1÷7 по дисциплине: "Размерный анализ технологических процессов" для студентов специальности 09. 0202
Размерный анализ технологических процессов для студентов специальности 09. 0202 «Технология машиностроения» дневной и заочной форм...
Методические указания для студентов всех форм обучения Киев -2006 Тема1 : числовые типы. Оператор присваивания iconМетодические указания к практическим занятиям и разделу курсового проекта по дисциплинам «Детали машин» и«Прикладная механика» для студентов технических специальностей
«Детали машин» и «Прикладная механика» для студентов технических специальностей дневной и заочной форм обучения/Перераб. В. И. Пахалюк,...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи