Geum.ru

Кафедра Автономных Информационных и Управляющих Систем "утверждаю" Декан автф в. В. Губарев " " 2006 г рабочая программа

Вид материалаРабочая программа

Содержание


Символьные массивы
Наборы данных и последовательности
Функции с переменным количеством параметров.
Задачи вычислительного типа
Подобный материал:
1   2   3

Массивы.

1. Найти в массиве и вывести значение наиболее часто встречающегося элемента.

2. Найти в массиве элемент, наиболее близкий к среднему арифметическому суммы его элементов.

3. Разделить массив на две части, поместив в первую элементы, большие среднего арифметического их суммы, а во вторую - меньшие (части не сортировать).

4. Сформировать массив простых чисел, не больших заданного.

5. Сформировать массив простых множителей заданного числа.

6. Найти наименьшее общее кратное всех элементов массива (то есть числа, которое делится на все элементы).

7. Найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка).

8. Интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (части не сортировать).

9. Задан массив, определить значение k, при котором сумма |A(1)+A(2)+…A(k)-A(k+1)+…+A(N)| минимальна (то есть минимален модуль разности сумм элементов в правой и левой части, на которые массив делится этим k).

10. Заданы два упорядоченных по возрастанию массива. Составить из их значений третий, также упорядоченный по возрастанию (слияние).

11. Известно, что 1 января 1999 г. – пятница. Для любой заданной даты программа должна выводить день недели.

12. Известно, что 1 января 1999 г. – пятница. Программа должна найти все “черные вторники” и “черные пятницы” 1999 года (то есть – 13 числа).


Символьные массивы

1. Выполнить сортировку символов в строке. Порядок возрастания "весов" символов задать таблицей вида char ORD[] = "АаБбВвГгДдЕе1234567890"; Символы, не попавшие в таблицу, размещаются в конце отсортированной строки.

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

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

4. Заменить в строке принятое в Си обозначение символа с заданным кодом (например, \101) на сам символ (в данном случае - A).

5. Переписать в выходную строку слова из входной строки в порядке возрастания их длины.

7. Удалить из строки комментарии вида "/* ... */". Игнорировать вложенные комментарии.

8. Заменить в строке символьные константы вида 'А' на соответствующие шестнадцатеричные (т.е. 'А' на 0x41).

9. Заменить в строке последовательности одинаковых символов (не пробелов) на десятичное число, состоящее из двух десятичных цифр и соответствующее их количеству (т.е. “ abcdaaaaa xyznnnnnnn ” на “abcd5a xyz7n ”).

10. Найти в строке два одинаковых фрагмента (не включающих в себя пробелы) длиной более 5 символов и возвратить индекс начала первого из них (т.е. для “aaaaaabcdefgxxxxxxbcdefgwwwww” вернуть n=6 - индекс начала “bcdefg”).

11. Оставить в строке фрагменты, симметричные центрального символа, длиной более 5 символов (например, “dcbabcd”), остальные символы заменить на пробелы.

12. Найти во входной строке самую внутреннюю пару скобок {...} и переписать в выходную строку содержащиеся между ними символы. Во входной строке фрагмент удаляется.


Сортировки

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

1. Сортировка вставками, место помещения очередного элемента в отсортированную часть производить с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции.

2. Сортировка Шелла. Частичную сортировку с заданным шагом, начиная с заданного элемента оформить в виде функции. Алгоритм частичной сортировки - вставка погружением.

3. Сортировка разделением. Способ разделения: вычислить среднее арифметическое всех элементов массива и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).

4. Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.

5. "Быстрая" сортировка с итерационным циклом вычисления медианы. Для заданного интервала массива, в котором производится разделение, ищется медиана обычным способом. Затем выбирается та часть интервала между границей и медианой, в которой находится середина исходного интервала, и процесс повторяется.

6. Сортировка циклическим слиянием с использованием одного выходного и двух входных массивов. Для упрощения алгоритма и разграничения сливаемых групп в последовательности в качестве разделителя добавить “очень большое значение” (MAXINT).

7. Сортировка разделением. Способ разделения: интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).

8. Простое однократное слияние. Разделить массив на n частей и отсортировать их произвольным методом. Отсортированный массив получить путем однократного слияния упорядоченных частей. Для извлечения очередных элементов из упорядоченных массивов использовать массив из n индексов (по одному на каждый массив).

9. Сортировка подсчетом. Выходной массив заполняется значениями “-1”. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений “-1”. После чего оставшиеся в выходном массиве позиции со значением “-1” заполняются копией предыдущего значения.

10. Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.


Функции

Вариант задания реализовать в виде функции, использующей для работы со строкой только указатели и операции вида *p++, p++ и т.д.. Если функция возвращает строку или ее фрагмент, то это также необходимо сделать через указатель.

1. Функция находит в строке заданную подстроку и возвращает указатель на нее. С использованием функции найти все вхождения подстроки в строке.

2. Функция находит минимальный элемент массива и возвращает указатель на него. С использованием этой функции реализовать сортировку выбором.

3. Шейкер-сортировка с использованием указателей на правую и левую границы отсортированного массива и сравнения указателей (см.3.7).

4. Функция находит в строке пары одинаковых фрагментов и возвращает указатель на первый. С помощью функции найти все пары одинаковых фрагментов.

5. Функция находит в строке пары инвертированных фрагментов (например "123apr" и "rpa321") и возвращает указатель на первый. С помощью функции найти все пары.

6. Функция производит двоичный поиск места размещения нового элемента в упорядоченном массиве и возвращает указатель на место включения нового элемента. С помощью функции реализовать сортировку вставками.

7. Функция находит в строке десятичные константы и заменяет их на шестнадцатеричные с тем же значением, например "aaaaa258xxx" на "aaaaa0x102xxx".

8. Функция находит в строке символьные константы и заменяет их на десятичные коды, например "aaa'6'xxx" на "aaa54xxx".

9. Функция находит в строке самое длинное слово и возвращает указатель на него. С ее помощью реализовать размещение слов в выходной строке в порядке убывания их длины.

10. Функция находит в строке самое первое (по алфавиту) слово. С ее помощью реализовать размещение слов в выходной строке в алфавитном порядке.


Наборы данных и последовательности

Разработать две функции, одна из которых вводит с клавиатуры набор данных в произвольной последовательности и размещает в памяти в переменном формате. Другая функция читает эти данные и выводит на экран. Программа запрашивает и размещает в памяти несколько наборов данных при помощи первой функции, а затем читает их и выводит на экран при помощи второй. Размещение данных производить в статическом массиве байтов фиксированной размерности с контролем его переполнения.

1. Прямоугольная матрица вещественных чисел, предваренная двумя целыми переменными - размерностью матрицы.

2. Последовательность тестовых строк. Каждая строка ограничена символом \0, последовательность - двумя символами \0.

3. Последовательность строк символов. Каждая строка предваряется байтом - счетчиком символов. Ограничение последовательности - счетчик со значением 0.

4. Упакованный массив целых переменных. Байт-счетчик, имеющий положительное значение n, предваряет последовательность из n различных целых переменных, байт-счетчик, имеющий отрицательное значение -n, обозначает n подряд идущих одинаковых значений целой переменной. Пример:

-исходная последовательность: 2 3 3 3 5 2 4 4 4 4 4 8 -6 8

-упакованная последовательность: (1) 2 (-3) 3 (2) 5 2 (-5) 4 (3) 8 -6 8

5. Упакованная строка, содержащая символьное представление целых чисел. Все символы строки, кроме цифр, помещаются в последовательность в исходном виде. Последовательность цифр преобразуется в целую переменную, которая записывается в упакованную строку, предваренная символом \0. Конец строки - два подряд идущих символа \0. Пример:

-исходная строка: "aa2456bbbb6665"

-упакованная строка: 'a' 'a' '\0' 2456 'b' 'b' 'b' 'b' '\0' 6665 '\0' '\0'

6. Произвольная последовательность переменных типа char, int и long. Перед каждой переменной размещается байт, определяющий ее тип (0-char, 1-int, 2-long). Последовательность вводится в виде целых переменных типа long, которые затем “укорачиваются” до минимальной размерности без потери значащих цифр.

7. Последовательность структурированных переменных типа struct man { char name[20]; int dd,mm,yy; char addr[]; }; Последняя компонента представляет собой строку переменной размерности, расположенную непосредственно за структурированной переменной. Конец последовательности - структурированная переменная с пустой строкой в поле name.

8. То же самое, что п.4.5, но для шестнадцатеричных чисел.

-исходная строка: "aa0x24FFbbb0xAA65"

-упакованная строка: 'a' 'a''\0' 0x24FF 'b' 'b' 'b' '\0' 0xAA65 '\0' '\0'

9. В упакованной строке последовательность одинаковых символов длиной N заменяется на байт со значением 0, байт со значением N и байт - повторяющийся символ. Конец строки обозначается через два нулевых байта.

10. Произвольная последовательность строк и целых переменных. Байт со значением 0 - обозначает начало строки (последовательность символов, ограниченная нулем). Байт со значением N является началом последовательности N целых чисел. Конец последовательности - два нулевых байта.


Функции с переменным количеством параметров.

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

1. Целая переменная - счетчик, затем последовательность вещественных переменных. Функция возвращает сумму переменных.

2. Последовательность целых положительных переменных, ограниченная переменной со значением -1. Функция возвращает максимальную из них.

3. Последовательность переменных различных типов. Перед каждой переменной находится целая переменная - идентификатор типа: 1-целое, 2-длинное целое, 3-вещественнное, 0-конец последовательности. Функция возвращает сумму значений параметров.

4. Первый параметр - строка, в которой каждый символ “*” обозначает место включения строки, являющейся очередным параметром. Функция выводит на экран полученный текст.

5. Первый параметр - форматная строка, в которой каждая цифра обозначает тип очередного параметра: 1-целое, 2-длинное целое, 3-вещественнное. Функция возвращает сумму значений параметров.

6. Каждый параметр - строка, последний параметр - NULL. Функция возвращает строку в динамической памяти, содержащую объединение строк-параметров.

7. Последовательность вещественных положительных переменных, ограниченная переменной со значением -1. Функция возвращает динамический массив, содержащий значения этих переменных.

8. Последовательность указателей на вещественные переменные, ограниченная NULL.. Функция возвращает динамический массив указателей на эти переменные.

9. Последовательность вещественных массивов. Сначала идет целый параметр - размерность массива (int), затем непосредственно последовательность значений типа double. Значение целого параметра - 0 обозначает конец последовательности. Функция возвращает сумму всех элементов.

10. Последовательность вещественных массивов. Сначала идет целый параметр - размерность массива (int), затем указатель на массив значений типа double (имя массива). . Значение целого параметра - 0 обозначает конец последовательности. Функция возвращает сумму всех элементов.

Функция создает и возвращает динамический массив соответствующим содержимым.


Задачи вычислительного типа

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

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

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

char a1[]="364543453";

char s[20];

add (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. Последовательность целых переменных различной размерности типов char, int, long кодируется следующим образом: перед каждым числом размещаются 2 бита, определяющие размерность числа - 00 - конец последовательности, 01 - char, 10 - int, 11 - long. Разработать функции упаковки и распаковки массива переменных типа long с учетом количества значащих битов и с определением коэффициента уплотнения. Пример: 01 xxxxxxxx 10 xxxxxxxxxxxxxxxx 01xxxxxxxx 00

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

10. Кодирование массива, содержащего последовательности одинаковых битов. При обнаружении изменения значения очередного бита по сравнению с предыдущим в последовательность записывается 6 разрядное значение счетчика (n<6) длины последовательности одинаковых битов. n=0 обозначает конец последовательности. Пример (исходная последовательность битов задана справа налево): 000000001111111000000000000 - 001100 000111 001000 000000


Списки.

1. Включение элементов в двусвязный циклический список с сохранением упорядоченности.

2. Включение элементов в односвязный список с сохранением упорядоченности.

3. Включение элементов в двусвязный список с сохранением упорядоченности.

4. Сортировка односвязного циклического списка путем исключения первого элемента и включения в новый список с сохранением его упорядоченности.

5. Сортировка односвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка.

6. Сортировка двусвязного циклического списка путем перестановки соседних элементов.

7. Элемент односвязного списка содержит указатель на строку в динамической памяти. Написать функции просмотра списка и включения очередной строки с сохранением упорядоченности по длине строки и по алфавиту.

8. Элемент односвязного списка содержит массив из 4 целых переменных. Массив может быть заполнен частично. Все значения целых переменных хранятся в порядке возрастания. Написать функцию включения значения в элемент списка с сохранением упорядоченности. При переполнении массива создается новый элемент списка и в него включается половина значений из переполненного.

9. Элемент двусвязного циклического списка содержит указатель на строку в динамической памяти. Написать функции просмотра списка и включения очередной строки с сохранением упорядоченности по длине строки и по алфавиту.


Объектно – ориентированное программирование

1. Конструкторы и деструкторы¸ конструкторы с параметрами.

2. Наследование¸ инкапсуляция¸ полиморфизм.

3. Классы, структуры и объединения.

4. Встраиваемые функции. Встраиваемые функции в объявлении класса.

5. Присваивание объектов. Передача объектов функциям. Объекты в качестве возвращаемого значения функций.

6. Массивы объектов. Использование указателей на объекты. Указатель this.

7. Операторы new и delete.

8. Ссылки. Передача ссылок на объекты. Ссылка в качестве возвращаемого значения функции.

Независимые ссылки и ограничения на применение ссылок.

9. Перегрузка конструкторов. Создание и использование конструкторов копий. Перегрузка и неоднозначность.

10. Аргументы по умолчанию. Определение адреса перегруженной функции.

12. Основы перегрузки операторов. Перегрузка операторов отношения и логических операторов. Перегрузка унарных операторов. Перегрузка, бинарных операторов.

13. Дружественные оператор-функции. Дружественные классы. Дружественные функции

14. Особенности использования оператора присваивания. Перегрузка оператора индекса массива

15. Управление доступом к базовому классу. Защищенные члены класса. Виртуальные базовые классы.

16. Конструкторы, деструкторы и наследование. Множественное наследование.

17. Система ввода/вывода C++. Форматируемый ввод/вывод. Манипуляторы ввода/вывода. Пользовательские функции ввода- вывода.

18. Классы, структуры и объединения.

19. Встраиваемые функции. Встраиваемые функции в объявлении класса.

20. Управление доступом к базовому классу. Защищенные члены класса. Виртуальные базовые классы.

21. Ссылки. Передача ссылок на объекты. Ссылка в качестве возвращаемого значения функции.

Независимые ссылки и ограничения на применение ссылок.


Задачи

1. Напишите программу, в которой класс tools представляет учетные карточки выданных инструментов. В карточке хранятся фамилия получателя, название, учетный код и количество выданных экземпляров инструмента. Функция main ( ) должна продемонстрировать работу с этой картотекой – создание, заполнение и просмотр карточек.

2. Напишите программу, в которой класс fq представляет очереди вещественных чисел фиксированной длины. Этот класс должен содержать конструктор и три рабочие функции – добавление в очередь, извлечение из очереди и показ содержимого очереди. Функция main ( ) должна создать две очереди, полностью заполнить их числами, а затем извлечь из них по пять чисел и показать оставшееся содержимое очередей.

3. Библиотечный файл time.h содержит функцию clock ( ), которая возвращает число тактов, прошедших с момента запуска программы. Для пересчета этого числа в секунды нужно его разделить на коэффициент CLK_TCK. Используя функцию clock ( ), напишите программу, в которой класс timer содержит элементы для имитации секундомера – начало и конец измеряемого промежутка времени, функции запуска, останова и отображения измеренного промежутка времени, а также конструктор и деструктор. Используйте деструктор для вывода на экран времени жизни объекта

4. Напишите программу, в которой функция main ( ) циклически распределяет вводимые с клавиатуры символы по трем стекам до тех пор, пока не будет введен символ 'Z', потом извлекает и показывает элементы третьего стека, затем второго стека и, наконец, элементы первого стека. Стек нужно представить как объект класса stack, в котором имеются функции push (поместить в стек) и pop (вытолкнуть из стека), а также конструктор и деструктор. Память для стека выделяется динамически, а его размер задается параметром конструктора.