tasks234
.pdfЗадания для вычислительного практикума I семестр 2011/2012 уч. год
ТРЕБОВАНИЯ К ПРОГРАММАМ
1.Необходимо точно выполнять условия задач, при сомнениях --
консультироваться с преподавателем. Программы представляются в исходных текстах.
2.Программы должны быть написаны самостоятельно.
3.Текст программы должен быть откомментирован. В заголовке указать
имя автора, группу, формулировку задания. Имена переменных, функций и
проч. должны иметь осмысленные имена. Желательно объявление переменной снабжать комментарием о ее назначении.
4.Следует структурировать программу, разбивая ее на (относительно)
независимые части. Осуждается порочная практика размещения многих
операторов в одной строке.
5.Длинные программы (свыше 200 строк) следует разбивать на несколько
файлов и создавать проект. Это обязательное требование, так как умение работать с проектами квалифицированному программисту
необходимо.
6.Интерфейс программы должен быть достаточно удобен для пользователя. Программа должна быть снабжена удобным интерфейсом
на базе меню.
7.Программа должна компилироваться без ошибок и предупреждений при
всех включенных сообщениях компилятора.
8.Программы реализуются на языке С++ БЕЗ использования классов.
9.Программы должны быть хорошо протестированы перед сдачей.
10.Сроки сдачи: 1-я программа - до 15 октября,
2-я программа - до 7 ноября,
3-я программа - до 1 декабря,
4-я программа - на зачетной неделе
11. См. также отдельные требования в разделах.
=========================================================================
I. ЗАДАЧИ НА ОДНОМЕРНЫЕ СТРУКТУРЫ
=========================================================================
1.Для заданного текста определить длину содержащейся в нем максимальной серии символов, отличных от букв.
2.Расстояние между двумя словами равной длины - это количество
позиций, в которых различаются эти слова. В заданном предложении найти пару наиболее далеко удаленных слов заданной длины.
3.Отредактировать заданное предложение, удаляя из него те слова, которые встречаются в предложении заданное число раз
4.Найти самое длинное общее слово двух заданных предложений.
5.Отредактировать заданное предложение, удаляя из него те слова,
которые уже встречались в предложении раньше.
6.Для встречающихся в заданном тексте пар рядом расположенных
символов указать сколько раз встречается в тексте каждое из таких
двухбуквенных сочетаний.
7.Даны два предложения. Найти самое короткое из слов первого предложения, которого нет во втором предложении.
8.Найти самое длинное симметричное слово заданного предложения.
9.Напечатать множество слов, которые встречаются в каждом из двух заданных предложений.
10.Для каждого из слов заданного предложения указать, сколько раз оно
встречается в предложении.
11.Напечатать в алфавитном порядке все латинские строчные буквы,
входящие хотя бы в одно слово заданного текста.
12.Отредактировать заданное предложение, удалив из него слова,
которые уже встречались ранее.
13.Из заданного текста выбрать и напечатать те символы, которые встречаются в нем ровно один раз ( в том порядке, в котором они
встречаются в тексте).
14.Отредактировать заданное предложение, удаляя из него все
слова с нечетными номерами и переворачивая слова с четными номерами.
15. Даны два предложения. Найти все слова, которые есть в одном из них, но
отсутствуют в другом предложении.
=========================================================================
II. ЗАДАЧИ НА ДВУМЕРНЫЕ СТРУКТУРЫ
=========================================================================
ТРЕБОВАНИЯ к задачам данного раздела:
1.Программа должна осуществлять анализ командной строки. Если при запуске программе переданы параметры, то первый из них - имя файла, из которого
следует брать исходные данные. Если параметры не переданы, то ввод
осуществляется из стандартного потока ввода.
2.Результат должен представлять собой функцию (отличную от функции main() ),
решающую поставленную задачу. Исходные данные (как правила, матрица и ее размеры) передаются в эту функцию в качестве параметров.
Функция main() должна быть демонстрацией возможностей написанной программы.
При необходимости можно вводить вспомогательные функции.
=========================================================================
16. Среди тех строк целочисленной матрицы, которые содержат только
нечетные элементы, найти строку с максимальной суммой модулей элементов.
17.Подсчитать количество строк заданной целочисленной матрицы NxN, являющихся перестановкой чисел 1,2...N (т. е. содержащих каждое из чисел 1,2...N ровно один раз.
18.Среди столбцов заданной целочисленной матрицы, содержащих только
такие элементы, которые по модулю не больше 10, найти столбец с
минимальным произведением элементов.
19. Массивом char[M][N] кодируется поле, на котором расположено
несколько прямоугольников. Каждый состоит из целого числа клеток, разные прямоугольники не накладываются друг на друга и не соприкасаются. Разные прямоугольники могут состоять из разных символов. Один и тот же прямоугольник не может состоять из различных символов. Пустые квадраты поля кодируется символом '.'. Подсчитать число прямоугольников разных типов.
Пример:
###...??..+.
###.=.??..+.
###.......+.
.....???....
???.......==
???...####..
Для этого поля программа должна выдать ответ:
#-прямоугольников: 2
?-прямоугольников: 3 +-прямоугольников: 1
=-прямоугольников: 2
20. Характеристикой столбца целочисленной матрицы назовем сумму
модулей его отрицательных нечетных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик.
21.Для заданной матрицы размером NxN найти такие k, что k-я строка матрицы совпадает с k-м столбцом.
22.Написать программу, работающую с 2-х мерным динамическим массивом
вещественных чисел, границы которого могут быть произвольными целыми числами (не обязательно от 0 до n):
struct arr |
// двумерный массив |
{double** base;
int d1_lower, d1_higher;
int d2_lower, d2_higher;
};
Напишите функции:
void init(arr& t, int d1_l, int d1_h, int d2_l, int d2_h, double initial);
//разместить в памяти 2-x-мерный массив t
//c границами от d1_l до d1_h по первой размерности и от d2_l до
//d2_h по второй размерности и заполнить его значением initial
int kill(arr& t);
// освободить память, занятую 2-мерным массивом t
double get(arr a, int i, int j);
//получить значение массива a в координатах i, j.
//При неверных границах выдавать сообщение об ошибке.
void put(arr a, int i, int j, double d);
//поместить в координаты i, j массива a элемент d.
//При неверных границах выдавать сообщение об ошибке.
double find_max(arr a);
// Найти максимум в массиве a.
void print(arr a);
// Распечатать массив c указанием координат элементов.
Следующий код:
arr a;
init (a, 2, 5, -2, 2, -1);
put (a, 2, 0, get(a, 2, 0) + 10); cout << find_max(a) << endl; print(a);
kill(a);
должен выдать на печать примерно следующее: 9
|
-2 |
-1 |
0 |
1 |
2 |
2 |
-1 |
-1 |
9 |
-1 |
-1 |
3 |
-1 |
-1 |
-1 |
-1 |
-1 |
4 |
-1 |
-1 |
-1 |
-1 |
-1 |
5 |
-1 |
-1 |
-1 |
-1 |
-1 |
23.Начиная из центра, обойти по спирали все элементы матрицы NxN, распечатывая их в порядке обхода.
24.Для заданной целочисленной квадратной матрицы найти максимум
среди сумм элементов диагоналей, параллельной главной диагонали.
25.Начиная с элемента a_11 обойти по спирали квадратную матрицу NxN, распечатывая элементы в порядке обхода.
26.Найти максимальный среди всех элементов тех строк заданной
матрицы, которые упорядочены (либо по возрастанию, либо по убыванию).
27.По заданной квадратной матрице NxN построить вектор длиной 2n-1, элементы которого - максимумы элементов диагоналей, параллельных
главной.
28.Напечатать элементы заданной матрицы размером NxN в следующем порядке
._. ._.
\.\.\.\.
\.\.\! !\. ... \.\.
.\.\. \!
!\.\.\.
.\.\.\.\.
~~
начиная с правого верхнего угла.
29. Напечатать элементы заданной матрицы размером NxN в следующем
порядке
._. ._. .
././././ .
!/././ ./!
././ ... ././. !/ ./././!
././././.
~~
начиная с левого верхнего угла.
30. Расстояние между k - й и l - й строками матрицы A(NxN)
определяется как
N |
|
|
__ |
|
|
\ |
|
|
r = / |
( | a | * | a | ) |
|
~~ |
kj |
lj |
j=1 |
|
|
Указать номер строки, максимально удаленной от первой строки заданной
матрицы.
=========================================================================
III. ЗАДАЧИ НА ДИНАМИЧЕСКИЕ ТИПЫ ДАННЫХ
=========================================================================
ТРЕБОВАНИЯ к задачам данного раздела:
1.Если в задаче этого раздела не указан тип списка, считать
его однонаправленным.
2.В задачах на списки должен быть реализован весь набор операций абстрактного типа данных "список" и все эти операции должны
демонстрироваться в интерфейсной части программы.
3.Программа обязательно должна быть разбита на модули: отдельный модуль -- демонстрация возможностей (функция main() и вспомогательные),
отдельный модуль -- реализация списка (дерева), еще один модуль -- решение поставленной задачи на базе реализованного
списка (дерева).
=========================================================================
31.Реализуйте однонаправленный список вещественных чисел. Программа должна
находить среднее арифметическое элементов,
заменять все вхождения числа x на число y, менять местами первый и последний элементы, проверить, упорядочены ли числа в списке по возрастанию.
32.Реализуйте стек строк. Реализуйте очередь стеков строк.
33.Реализуйте список строк. Написать следующие функции для пары списков:
а. сравнить списки на равенство
б.определить, входит ли первый список во второй в. скопировать в конец списка второй список
34.Реализуйте список строк. Напишите функции для подсчета количества слов в списке:
а. начинающихся и оканчивающихся одной и той же буквой
б.начинающихся с той же буквы, что и следующее слово
в.совпадающих с последним словом.
35.Реализуйте список вещественных чисел. Написать следующие функции: а. проверить, есть ли в нем два одинаковых элемента б. перенести в начало его последний элемент
в.перенести в конец его первый элемент
г.вставить в список сам в себя вслед за первым вхождением числа x
36.Реализуйте список строк. Написать следующие функции:
а.обращение списка (изменить ссылки в списке так, чтобы элементы оказались расположены в противоположном порядке)
б.из каждой группы подряд идущих элементов оставить только один в. оставить в списке только первые вхождения одинаковых элементов
37.Реализуйте список пар вещественных чисел. Написать функции, которые по спискам l1 и l2 создают новый список, включающий
а. пары списка l1, первая координата которых встречается как вторая
координата у пар списка l2
б.пары (x,y) списка l1 встречающиеся в виде (y,x) в списке l2
в.пары (x,y) x<y списка l1
38.Реализуйте список вещественных чисел. Написать функции, которые по спискам l1 и l2 создают новый список, включающий по одному разу
числа, которые
а. входят одновременно в оба списка б. входят хотя бы в один из списков
в.входят в один из списков l1 и l2, но в то же время не входят в
другой из них
г.входят в список l1, но не входят в список l2.
39.Реализовать список вещественных чисел. Написать функции:
а. Проверка, является ли список упорядоченным по неубыванию.
б. Сортировка списка по возрастанию.
в. Объединение двух упорядоченных по неубыванию списков в один упорядоченный по неубыванию список.
г. Вставка числа в неубывающий список с сохранением упорядоченности списка.
40.а. Реализовать список строк.
б. Целое число представляется строкой цифр. Написать функцию,
упорядочивающую по неубыванию числа в непустом списке целых чисел с S разрядами.
41.Дан список слов среди которых есть пустые. Написать функции:
а.переставляющие местами первое и последнее непустые слова
б. печатать текст из первых букв непустых слов
в. удалить из непустых слов первые буквы
г.определить количество слов в непустом списке, отличных от последнего
42.Иерархический список - последовательность, состоящая из строк или иерархических списков. Начало и конец списка будем
обозначать символами ( и ). Разделять элементы списка будем запятой.
Написать следующие функции:
а. Дана строка, обозначающая иерархический список. Строка содержит
маленькие латинские буквы, скобки и запятые. Пример такой строки:
"((a,b),c,(),b)". Преобразовать такую строку в иерархический список.
б. проверка вхождения строки в иерархический список в. печать всех строк, входящих в иерархический список на любой глубине
г.проверка на равенство двух списков
43.Написать набор функций, позволяющих работать с бинарным деревом вещественных чисел.
а. Ввести дерево из файла. Формат ввода: в каждой строке файла - одно число с плавающей точкой, перед которым могут стоять символы
табуляции. Пусть в какой-то строке стоит число n в позиции k.
Тогда потомки числа n стоят в последующих строках в позиции (k+1).
Пример. Следующий файл:
5
6
7
8
-10
-5
9
11
13
кодирует дерево
5
/\
/\
69
/ |
\ |
|
/ |
\ |
7 |
|
8 |
11 |
13 |
/\
-10 -5
б. Определить число вхождений числа k в бинарное дерево
в. Напечатать наибольший элемент непустого дерева
44. Написать набор функций, позволяющих работать с бинарным деревом вещественных чисел:
а.Ввести дерево из файла. Формат ввода: в каждой строке файла - одно
число, перед которым могут стоять символы табуляции. Пусть в какой-то
строке стоит число n в позиции k. Тогда потомки числа n стоят в последующих строках в позиции (k+1). Пример. Следующий файл:
5
6
7
8
-10 -5
9
11
13
кодирует дерево
5
/\
/\
69
/ |
\ |
|
/ |
\ |
7 |
|
8 |
11 |
13 |
/\
-10 -5
б. Вычислить сумму элементов непустого дерева
в. Напечатать элементы всех листьев дерева
г.Определить число ветвей в самом длинном из путей от корня дерева до листьев.
45.Написать набор функций, позволяющих работать с бинарным деревом вещественных чисел:
а.Ввести дерево из файла. Формат ввода: в каждой строке файла - одно
число, перед которым могут стоять символы табуляции. Пусть в какой-то строке стоит число n в позиции k. Тогда потомки числа n стоят в
последующих строках в позиции (k+1). Пример. Следующий файл:
5
6
7
8
-10 -5
9
11
13
кодирует дерево
5
/\
/\
69
/ |
\ |
|
/ |
\ |
7 |
|
8 |
11 |
13 |
/\
-10 -5
б. Посчитать высоту и количество элементов в дереве
в. Напечатать путь от корня дерева до заданного элемента
г. Напечатать элементы дерева заданного уровня (уровень 0 -- корень дерева, уровень 1 -- потомки корня и т.п.)
=========================================================================
СЛОЖНЫЕ ЗАДАЧИ
=========================================================================
46. МАТЕМАТИЧЕСКИЕ ФУНКЦИИ
Имеется фиксированный набор базовых функций (арифметика, sin, cos, tg, exp, log).
Необходимо работать с вещественными функциями от одного аргумента, которые являются суперпозициями базовых.
Разработать библиотеку для работы со структурами данных, реализующими такие функции.
Набор операций над функцией:
-сложение, умножение, вычитание, деление;
-возведение в целочисленную степень;
-суперпозиция функций;
-вычисление значения функции при заданном аргументе (предусмотреть обработку ситуации, когда аргумент лежит вне области определения);
-инициализацию функции символьной строкой
func_init( f, "exp(x) + (x^2 - 4.4*x^3) / cos(x)" );
-преобразование "функции" из внутреннего представления в символьную
строку;
-вычисление производной функции (результат -- функция).
Внутреннее представление "функции" -- дерево.
47. ПОЛИНОМЫ - 1
Разработать набор функций для работы с полиномами от
одной переменной с вещественными коэффициентами.
Действия над полиномами:
-сложение, умножение, вычитание;
-возведение в целую степень;
-взятие коэффициента при заданной степени;
-определение степени полинома;
-вычисление значения по заданному аргументу;
-суперпозиция полиномов;
-инициализация символьной строкой;
pol_init( f, " x^12 + 2 * x^11 - 3 * x + 17 " );
в записи полинома символьной строкой переменная всегда
обозначается символом "x". Лишние пробелы игнорируются.
-преобразование из внутреннего представления в символьную строку;
-вычисление производной;
-вычисление первообразной (с нулевой константой);
Внутреннее представление -- список пар (коэф,степень).
При выполнении всех операций необходимо приводить подобные.
48. ПОЛИНОМЫ - 2
Разработать набор функций для работы с полиномами вещественными
коэффициентами.
Действия над полиномами те же, что и в задаче 47
Внутреннее представление полинома -- массив.
При выполнении всех операций необходимо приводить подобные.
49. ДЛИННЫЕ ЧИСЛА
Реализуйте набор функций для работы с целыми числами с неограниченным
числом цифр. Число хранится в двоичном виде, память под массив данных должна выделяться динамически.
Действия над длинными числами:
-сложение, вычитание, умножение, деление нацело, взятие остатка, деление с остатком, возведение в целую степень;
-операции сравнения двух длинных чисел;
-инициализация символьной строкой
bigint_init( i, "12345678901234567890");
-преобразование из внутреннего представления в символьную строку;
-взятие абсолютной величины числа.
50. ШИФРОВКА
Реализовать программу шифровки и дешифровки по алгоритму DES Национального
бюро стандартов США (описание можно найти в книге: Дейтел Г. Введение в
операционные системы. Том 2. М.: Мир, 1987.). Программа должна шифровать бинарный файл произвольной длины и декодировать закодированный файл.
Ключ шифровки сохраняется отдельно от шифруемого файла.
51. ШАХМАТЫ
Написать программу, решающую задачи "мат в N ходов".
Входные данные - файл с записью позиции. Результат - файл с записью начальной позиции и ходами сторон.
Написать программу, наглядно демонстрирующую шахматные ходы.
Программа должна иметь графический интерфейс. Входными данными программы является файл с записью начальной позиции и ходов
в шахматной нотации.
52. ФОРМАТИРОВАНИЕ ТЕКСТА
Написать программу, читающую текст из файла и выводящую его в другой файл
отформатированным -- в процесс форматирования пользователь не вмешивается. В исходном тексте абзацы разделены пустыми строками. Во входном файле
могут встречаться строки, которые не записываются в выходной файл,