Приложение 1. Шаблон титульного листа для оформления контрольной работы

 

 

Новосибирский государственный технический университет

 

Кафедра вычислительной техники

 

 

 

 

Пояснительная записка

к контрольной работе

по дисциплине “Программирование”

 

 

Группа: ОТЗ - 125

Курс 3

Семестр: 5

Студент:

Преподаватель: Юн С.Г.

Дата проверки работы:

 

 

Новосибирск 2005

Приложение 2. вариантЫзаданий контрольной работы

Задача 1.

Варианты:

1. Разработать программную рекурсивную функцию поиска целого числа в массиве, содержащем n целых чисел. Результат функции – число чисел в массиве, равных заданному.
2. Разработать программную рекурсивную функцию, вычисляющую сумму первых n целых чисел в массиве, размерность которого больше или равна n/
3. Разработать программную рекурсивную функцию, выводящую на печать числа 1,2, …, n для заданного числа n.
4. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.
5. Разработать программную рекурсивную функцию, выводящую на печать в обратном порядке цифры целого положительного десятичного числа.
6. Разработать программную рекурсивную функцию, выводящую на печать n символов латинского алфавита в возрастающем лексикографическом порядке.

Пример: ABCD при n = 4.

1. Разработать программную рекурсивную функцию, преобразующую положительное целое десятичное число в восьмеричное представление и выводящую его на печать.
2. Разработать программную рекурсивную функцию бинарного поиска в массиве заданного значения.
3. Разработать программную рекурсивную функцию power (x, n), для вычисления xⁿ , использующую следующие рекуррентные отношения:

x⁰ = 1,

xⁿ = (x^n/2)², если n >0 и n – четное число,

xⁿ = x*(x^n/2)², если n >0 и n – нечетное число,

 

1. Разработать программную рекурсивную функцию вычисления f(n), если:

f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 3, f(5) = 5,

f(n) = f(n-1) +3*f(n-5) для n > 5

1. Разработать программную рекурсивную функцию вычисления наибольшего общего делителя

nod (a,b) при a >b, использующую следующие рекуррентные отношения:

b, если (a mod b) = 0

nod (a,b) =

nod (b, a mod b), если nod (a,b) ≠ 0

 

1. Разработать программную рекурсивную функцию вычисления функции Аккермана, использующую рекуррентные отношения:

b + 1, если a = 0

Acker (a,b) = Acker (a - 1,1), если b = 0

Acker (a - 1, Acker (a,b - 1)), если a ≠ 0, b ≠ 0

 

1. Разработать программную рекурсивную функцию вычисления числа Фибоначчи, использующую рекуррентные отношения:

f(1) = 1, f(2) = 1,

f(n) = f(n-1) +f(n-2) для n > 2

 

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

Задача 2.

Варианты:

1. Поиск в строке по образцу и замена на другой образец. Предусмотреть поиск всех включений образца.
2. Поиск и удаление образца из строки. Предусмотреть поиск всех включений образца.
3. Функция возвращает динамический массив указателей на слова во входной строке, отсортированные по длине (массив содержит указатели на копии слов из исходной строки).
4. Функция возвращает динамический массив указателей на слова во входной строке, отсортированные по алфавиту (массив содержит указатели на копии слов из исходной строки).
5. Склеивание двух указанных строк.
6. Включение заданной строки в массив упорядоченных строк с сохранением упорядоченности.
7. Формирование дополнительного массива указателей на все вхождения заданного образца в массиве строк.
8. Уплотнение строк за счет удаления лишних пробелов между словами и удаления пустых строк.
9. Функция получает массив вещественных чисел. Размерность массива - формальный параметр. Функция создает динамический массив указателей на переменные в этом массиве и выполняет сортировку указателей (без перемещения указуемых переменных).
10. Выравнивание длины всех строк текста по наиболее длинной строке за счет равномерной вставки дополнительных пробелов между словами.
11. Формирование дополнительного массива указателей на отдельные слова в строках. В массиве не должно быть указателей на одинаковые слова.
12. Функция находит в строке заданную подстроку и возвращает динамический массив указателей на все вхождения этой подстроки.
13. Функция находит в строке фрагменты, содержащие последовательность одинаковых символов длиной более 3 в возвращает динамический массив указателей на такие фрагменты.
14. Функция находит в строке фрагменты, симметричные относительно центрального символа, длиной 7 и более символов (например, "abcdcba") и возвращает динамический массив указателей на начала этих фрагментов.
15. Функция возвращает динамический массив указателей на слова во входной строке, отсортированные по длине (массив содержит указатели на копии слов из исходной строки).

Задача 3.

Реализовать список и функции работы с ним. В зависимости от варианта с помощью рекурсивных алгоритмов реализовать операции:

· вывод на экран содержимого списка ShowData(),

· поиск элемента с заданным значением в списке. Результат функции GetPos() – указатель на найденный элемент.

· очистка списка Clear()

· удаление элемента с заданным значением из списка Delete().

С помощью итерационных алгоритмов реализовать операции:

· получение значения элемента в заданной позиции списка GetData(),

· получение номера позиции в списке элемента с заданным значением GetPos(),

· очистка списка Clear()

· включение нового элемента в список Insert(),

· удаление элемента с заданным номером позиции из списка Delete().

Варианты:

1. Односвязный неупорядоченный список. Рекурсивные алгоритмы операций.
2. Односвязный неупорядоченный список. Итерационные алгоритмы операций.
3. Односвязный упорядоченный список. Рекурсивные алгоритмы операций.
4. Односвязный упорядоченный список. Итерационные алгоритмы операций.
5. Двухсвязный неупорядоченный список. Рекурсивные алгоритмы операций.
6. Двухсвязный неупорядоченный список. Итерационные алгоритмы операций.
7. Двухсвязный упорядоченный список. Рекурсивные алгоритмы операций.
8. Двухсвязный упорядоченный список. Итерационные алгоритмы операций
9. Циклический односвязный неупорядоченный список. Рекурсивные алгоритмы операций.
10. Циклический односвязный неупорядоченный список. Итерационные алгоритмы операций.
11. Циклический односвязный упорядоченный список. Рекурсивные алгоритмы операций.
12. Циклический односвязный упорядоченный список. Итерационные алгоритмы операций.
13. Циклический двухсвязный неупорядоченный список. Рекурсивные алгоритмы операций.
14. Циклический двухсвязный неупорядоченный список. Итерационные алгоритмы операций.
15. Циклический двухсвязный упорядоченный список. Рекурсивные алгоритмы операций.
16. Циклический двухсвязный упорядоченный список. Итерационные алгоритмы операций.

Задача 4.

Программа должна содержать функцию обхода дерева с выводом его содержимого, функцию добавления вершины дерева (ввод), а также дополнительную функцию, если таковая указана в варианте.

Варианты:

1. Вершина двоичного дерева содержит указатель на строку. Строки в дереве не упорядочены. Функция включает вершину в дерево с новой строкой в ближайшее свободное к корню дерева место. (То есть дерево будет сбалансированным). Реализовать функцию поиска в дереве строки максимальной длины.

2. Вершина двоичного дерева содержит массив целых из 4 элементов и два указателя на правое и левое поддерево. Массив целых в каждом элементе упорядочен, дерево в целом также упорядочено. Функция включает в дерево целую переменную с сохранением упорядоченности.

 

3. Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддерево. Строки в дереве упорядочены по возрастанию по алфавиту. Написать функций включения строки. Реализовать функцию поиска заданной строки.

4. Элемент дерева содержит либо данные (строка ограниченной длины), либо указатели на правое и левое поддеревья. Строки в дереве упорядочены. Написать функцию включения новой строки. (Обратить внимание на то, что элемент с указателями не содержит данных, и при включении новой вершины вершину с данными следует заменить на вершину с указателями).

 

5. Вершина дерева содержит целое число и 4 указателя на поддеревья. Целые в дереве не упорядочены. Функция включает вершину в дерево с новой целой переменной в ближайшее свободное к корню дерева место. (То есть дерево сбалансировано). Реализовать функцию поиска максимального значения в дереве.

6. Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.

7. Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддерево. Строки в дереве упорядочены по возрастанию длины строки. Написать функций включения строки.

8. Вершина дерева содержит целое число и 4 указателя на поддеревья. Целые в дереве не упорядочены. Функция включает вершину в дерево с новой целой переменной в ближайшее свободное к корню дерева место. (То есть дерево сбалансировано).

9. Вершина дерева содержит указатель на строку и динамический массив указателей на потомков. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция при включении строки создает вершину, наиболее близкую к корню.

10. Вершина дерева содержит динамический массив целых значений и два указателя на потомков. Значения в дереве не упорядочены. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция включает новое значение в свободное место в массиве ближайшей к корню вершины.

11. Вершина дерева содержит массив целых и два указателя на правое и левое поддерево. Значения в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу " левое поддерево - вершина - правое поддерево". Разработать функции включения и получения значения элемента по заданному логическому номеру.

11. Вершина двоичного дерева содержит указатель на строку. Строки в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу " левое поддерево - вершина - правое поддерево". Разработать функции включения и получения значения элемента по заданному логическому номеру.

Задача 5.

Варианты:

1. Разработать программную функцию умножения целых переменных произвольной длины с использованием операций сложения и сдвига (проверить на переменных типа long).

2. Разработать программную функцию деления целых чисел произвольной длины с использованием операций вычитания и проверки на знак результата (проверить на переменных типа long).

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

Пример вызова функции:

char a1[]="364543453";

char s[20];

mul (a1,"345353",s);

4. Разработать программные функции сложения и вычитания чисел произвольной длины, представленных непосредственно строками цифр:

Пример вызова функции:

char a1[]="364543453";

char s[20];

add (a1,"345353",s);

5. Разработать программную функцию кодирования и декодирования строки символов, содержащей цифры, в последовательность битов. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает, что за ней следует байт (2 цифры) с кодом символа, отличного от цифры.

6. Разработать программную функцию сложения чисел в следующей форме представления. Число произвольной длины представлено в двоично-десятичной системе. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает конец последовательности цифр.

7. Разработать программную функцию вычитания чисел в следующей форме представления. Число произвольной длины представлено в двоично-десятичной системе. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает конец последовательности цифр.

8. Разработать программную функцию упаковки и распаковки массива переменных типа long с учетом количества значащих битов. Последовательность целых переменных различной размерности типов char, int, long кодируется следующим образом: перед каждым числом размещаются 2 бита, определяющие размерность числа - 00 - конец последовательности, 01 - char, 10 - int, 11 - long.

Пример: 01 xxxxxxxx 10 xxxxxxxxxxxxxxxx 01xxxxxxxx 00

9.. Разработать программную функцию упаковки и распаковки массива переменных типа long с учетом количества значащих битов. Последовательность целых переменных различной размерности кодируется следующим образом: перед каждым числом размещаются 5 битов, определяющие количество битов в следующем за ним целом числе. 00000 - конец последовательности

Пример: 01000 xxxxxxxx 00011 xxx 10000 xxxxxxxxxxxxxxxx 00000

10. Разработать программную функцию кодирования массива, содержащего последовательности одинаковых битов. При обнаружении изменения значения очередного бита по сравнению с предыдущим в последовательность записывается 6 разрядное значение счетчика (n<6) длины последовательности одинаковых битов. n=0 обозначает конец последовательности.

Пример (исходная последовательность битов задана справа налево): 000000001111111000000000000 - 001100 000111 001000 000000

11. Разработать программную функцию упаковки и распаковки строки. Используются следующие правила кодирования: большие латинские буквы упаковываются в виде 5-битных кодов по 3 символа в одну целую переменную типа int. При этом старший бит устанавливается в 1. Остальные символы упаковываются по одному в целую переменную со значением старшего бита - 0.

12. Разработать программную функцию упаковки и распаковки строки. Используются следующие правила кодирования: большие, маленькие латинские буквы, цифры и знаки кодируются 3 группами 5-битных кодов. Значения 29,30,31 используются для “переключения” с группы на группу при наличии в строке символов различных групп. Коды упаковываются по 3 в одну целую переменную типа int.

13. Разработать программную функцию упаковки и распаковки строки с определением наиболее часто встречающихся символов. Используются следующие правила кодирования: первые 15 наиболее часто встречающихся символов кодируются 4-битными кодами от 0000 до 1110. Код 1111 обозначает, что следующие за ним 8 бит кодируют один из остальных символов.

14. Разработать программную функцию упаковки и распаковки строки с определением наиболее часто встречающихся символов. Используются следующие правила кодирования: если в последовательности встречается бит 0, то за ним идет 3-битовый код первых 8 наиболее часто встречающихся символов (000... 111). За битом 1 - следует обычный 8-битный код остальных символов.

15. Разработать программные функции упаковки и распаковки строки с определением наиболее часто встречающихся символов. Используются следующие правила кодирования: первый наиболее часто встречающийся символ кодируется битом 0. Бит 1 кодирует группу из всех остальных символов. Код 10 кодирует второй по частоте символ, 11 - группу всех остальных и т.д..