Илюхина А.Г. Теория вычислительных процессов и структур - файл n1.docx

приобрести
Илюхина А.Г. Теория вычислительных процессов и структур
скачать (170.8 kb.)
Доступные файлы (1):
n1.docx171kb.05.06.2012 06:39скачать

n1.docx

  1   2   3   4   5   6
Министерство Российской Федерации по связи и информатизации

 Санкт-Петербургский государственный университет телекоммуникаций

им. проф. М.А. Бонч-Бруевича

 

А.Г. Илюхина

 Теория вычислительных процессов и структур

Методические рекомендации к лабораторным работам

220400


Содержание:

Лабораторная работа 1.Моделирование процесса рекурсивного вызова

Лабораторная работа 2. Моделирование процесса вычисления логической функции

Лабораторная работа 3. Моделирование работы конечного автомата, реализация автомата как устройства

Лабораторная работа 4. Программная реализация работы конечного автомата

Лабораторная работа 5. Разработка фрагмента синтаксического анализатора

Лабораторная работа 6. Моделирование работы стекового автомата

Лабораторная работа 7. Изучение работы программы LEX, генератора лексических анализаторов

Лабораторная работа 8. Разработка лексического анализатора при использовании программы LEX

Приложение. Теоретический материал по теме "Формальные языки и грамматики"

Лабораторная работа 1

Моделирование процесса рекурсивного вызова

Цель: исследование механизма рекурсивного вызова и возврата

Выполнение работы

    1. Решить предложенную задачу с использованием рекурсии.

    2. Разработать способ представления рекурсивного вызова. На рис.1 представлен пример отображения рекурсивного вызова и возврата для задачи "числа Фиббоначи".

    3. Написать программу, которая отображает на экране каждый шаг рекурсии. Необходимо:

Варианты заданий

    1. Описать рекурсивную функцию pow(x,n), которая вычисляет величину xn , согласно формуле

xn=1, при n=0;

xn=1/ xn, при n<0;

xn=x* xn-1, при n>0.

    1. Рекурсивно описать функцию C(m,n), где 0  m  n, для вычисления биномиального коэффициента Cmn по следующей формуле:

C0n= Cnn=1, Cmn= Cmn-1+ Cm-1n-1 при 0<m<n.

    1. Описать логическую функцию ПОТОМОК(А,В), проверяющую, является ли человек с именем В потомком (ребенком, внуком, правнуком) человека с именем А.

    2. Описать рекурсивную функцию, которая методом деления отрезка пополам находит с заданной точностью корень уравнения F(X)=0 на отрезке [a,b].

    3. Описать функцию MIN(X) для определения минимального элемента вектора X, введя вспомогательную рекурсивную функцию MIN1(K), находящую минимум среди последних элементов вектора Х, начиная с K-го.

    4. Описать рекурсивную логическую функцию SIMM(S,I,J), проверяющую, является ли симметричной часть строки, начиная с I-го и заканчивая J-м ее элементом.

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

    6. Описать рекурсивную функцию, подсчитывающую количество цифр в тексте, заданном во входном файле (за текстом следует точка).

    7. Напечатать в обратном порядке заданный в файле текст.

    8. Дана последовательность ненулевых чисел, за которой следует ноль. Напечатать сначала все отрицательные числа, а затем - все положительные.

    9. Во входном файле записана формула следующего вида:

<формула>::=<цифра> | <формула><знак><формула>

<знак> ::=+ | - | *

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

Ввести эту формулу и вычислить ее значение.

    1. Лабиринт может быть задан матрицей соединений, в которой для каждой пары комнат указано, соединены ли они коридором. Даны матрицы соединений для лабиринта из n комнат и номера комнат i, j (1<=i<=n, 1<=j<=n). Построить путь из комнаты с номером i в комнату с номером j.

    2. Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей n*n, элемент aij которой равен некоторому отрицательному числу, если города i и j не соединены дорогой, и длине пути в противном случае.

а) для i- го города найти кратчайшие маршруты в остальные города;

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

  1. Во входном файле задан текст, за которым следует точка.Проверить, является ли он правильной записью формулы (см. задачу 13).

  2. Дано n различных чисел, напечатать все возможные перестановки этих чисел.

  3. На шахматной доске расставить 8 ферзей так, чтобы они не били друг друга. Написать программу, которая печатает:

а) одну такую расстановку;

б) все 92 таких расстановки.

  1. Во входном файле записано логическое выражение следующего вида:

<лог.выр>::=<истина> | <ложь> | <операция>(<операнды>)

<операция>::=not | and | or

<операнды>::=<операнд> | <операнд><операнды>

<операнд>::=<лог.выр>.

Ввести выражение и вычислить его значение.

  1. Во входном файле задан текст, за которым следует точка. Проверить, удовлетворяет ли структура текста следующему определению:

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

<элемент>::= а | б | (<текст>) | [<текст>] | {<текст>}

  1. Ханойские башни. Имеются три колышка A, B,C и n дисков разного размера, пронумерованных с 1 по n в порядке возрастания. Сначала все диски надеты на колышк А. Требуется перенести их на С, используя В как вспомогательный. Диски можно переносить только по одному. Больший диск нельзя ставить на меньший.

 Задача:

Задана последовательность чисел Фиббоначи (1 1 2 3 5 8 13 21 …), где текущий элемент равен сумме двух предыдущих. Найти n-е число.

Программа:

program Fib_N;

Var

N:integer;

Function fib(n:integer): integer;

Begin

If (n=1) or (n=2) then fib:=1

Else fib:=fib(n-1)+fib(n-2);

End;

Begin

Read(n);

Writeln(fib(n));

End;

 

Модель рекурсивного вызова:

http://dvo.sut.ru/libr/cvti/i097iluh/1.gif
  1   2   3   4   5   6


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации