Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Рекурсия и исключения

1) Задание на использование исключений (C-модель, Microsoft Specific). Вам необходимо будет реализовать программу по тем задача, которые вы так замечательно решали на практической работе:

• Сумма элементов массива;
• Поиск максимального элемента в массиве;
• Переворот строки.

Необходимо создать две версии функций для каждой из задач: рекурсивную и не рекурсивную. Затем вы запускаете и оцениваете время выполнения каждой из версий функций для каждого вида задачи (оценку времени вести в миллисекундах). Размер массива (строки) должен изменяться по правилу 100 – 1000 – 10000 – и так далее, разумеется, что на определенной стадии рекурсивные версии функций работать не будут. Вам необходимо будет отловить исключение и в таблице результатов напротив этого вида испытания вывести “n/a” – not/available.

Вывод результата в виде:

Испытание: сумма элементов массива
Сумма элементов:	Рекурсивная версия	Нерекурсивная версия
Кол-во элементов: 100	x1 ms.	x2 ms.
Кол-во элементов: 1000	x3 ms.	X4 ms.
...	..	...
Испытание: сумма элементов массива
...	..	...

2) Задание на использование исключений (С++-модель, стандарт ISO). Мы возвращаемся к одной из старых задач, где использовали класс CHuman. Как вы помните в составе данного класса есть три поля: ФИО, возраст, вес. Нигде и ни у кого из вас не было проверок на корректность данных параметров. Необходимо ограничить значения параметров следующими границами:

• вес в диапазоне 5-200 кг;
• возраст – 1-120 лет;
• имя не должно содержать цифр, только буквы и пробелы.

В том случае если при вызове конструктора или вызове метода вида setXXXParameter будет задано неправильное значение, то следует выбрасывать исключение.

Необходимо создать массив из 100 объектов CHuman заполнить их случайным образом и выполнить их сортировку любой из ранее вами реализованных шаблонных функций. Но при этом перед вызовом сортировки мы имитируем ошибку исходных данных, один любой элемент массива с вероятностью 50% должен быть равен NULL. Разумеется что в подобном случае сортировка будет невозможна и должно генерироваться исключение, которое должно перехватываться там откуда был сделан вызов функции сортировки с выводом на экран номера строки и имени файла где произошел сбой (смотрите дополнение к метод. пособию, # 2, последняя страница).

Рекомендуемая иерархия исключений:



3) Вычислить следующие цепные дроби:



Значение n – глубина вложенности дроби задается пользователем. Значения 2,1,2,1,1,4 называются неполными частными и вычисляются по следующему правилу:

 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, ..
 

последовательность неполных частных задается следующим перечислением:

 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13

к сожалению, в настоящее время для этой последовательности не известно никакой зависимости, элементы задаются как последовательность констант.

4) Необходимо создать рекурсивную версию функции вычисляющей значение функции Фибоначчи. Пример ряда приводится далее:

 1, 1 , 2 , 3 , 5 , 8 , 13 , 21, …

Пользователь вводит значение числа n – на экран выводится значение Fib (n), отсчет начинается от единицы, т.е. Fib(1) = 1 и далее согласно примеру.

5) Во время поездки на поезде девочка заменила в названии поезда каждую букву ее номером в русском алфавите и получила запись из единиц и двоек "211221-21221". Определить откуда и куда идет поезд, для этого вывести все возможные варианты расшифровки названий пунктов прибытия и отбытия на экран.

« Структуры данных и алгоритмы. Практика. Основы рекурсии

Структуры данных и алгоритмы. Практика. Динамические структуры данных. Стек. Очередь »