Задачи на семестр, осень 2009, 145 группа

Достаточно продвинутые задачи, которые можно делать вместо домашних работ

Задачи можно делать и начать сдавать до 15 ноября. Задачи необязательны. У каждой задачи есть балл, который определяет, какие плюсы даёт её успешная сдача:

2 балла - 1 любая задача из любого домашнего задания

3 балла - 2 любые задачи из любого домашнего задания

4 балла - домашнее задание целиком

5 баллов - домашнее задание целиком

6 баллов - домашнее задание целиком + любая задача

7 баллов - 2 любых домашних задания
Решение большинства из этих задач предполагает активное взаимодействие с преподавателем - уточнение требований, обсуждение возможных способов решений, планирование и показ промежуточных результатов. Формулировки намеренно даны размыто, требования могут меняться прямо в процессе решения (как и в реальной жизни).

[6 баллов] Написать архиватор, основанный на алгоритме Хаффмана. На вход параметром командной строки он должен принимать ключ, указывающий, что делать - архивировать или разархивировать, и имя файла. В результате работы должен быть создан файл, содержащий заархивированный/исходный текст, в зависимости от режима работы.
[4 балла] Найти информацию по сортировке Шелла или сортировке кучей и реализовать её
[7 баллов] Реализовать библиотеку для работы с длинными числами (описание типа данных для представления длинных чисел и функции, реализующие операции над ними) и простой стековый калькулятор на её основе. Библиотека должна быть оформлена отдельным модулем, с .h и .cpp-файлами.
[6 баллов] Реализовать библиотеку для работы с матрицами, реализовать на её основе вычисление n-го числа Фибоначчи за O(log n). Библиотека должна быть оформлена отдельным модулем, с .h и .cpp-файлами.
[7 баллов] Дана строка, представляющая математическое выражение. Посчитать его производную, по возможности упростить результат. Например, на x^2 + x + 1 должно выводиться 2*x + 1. Должны быть поддержаны минимум +, -, *, /, возведение в степень, скобки.
[2 балла] Написать программу генерации всех перестановок длины N
[где-то 6 баллов] <Здесь будет задача про интерпретатор ассемблера или стековой машины. Кто знает, что такое Форт, может сделать что-то подобное.>
[4 балла] Существуют способы обойти шахматным конем доску 8х8, побывав на каждом поле только один раз. Составить программу подсчета числа способов обхода, с выводом всех путей обхода. В этой задаче доска может быть размера от 1х1 до 10х10, так что путей обхода может и не быть.
[7 баллов] Реверси. Написать "движок" реверси - функцию, которая будет печатать доску после каждого хода и вызывать "бота", передавая ему содержимое доски, написать самого бота. Бот возвращает индекс поля, на которое он ставит фишку. Учесть при написании движка, что за чёрных и за белых могут играть разные боты. Желательно, чтобы боты играли хорошо, поэтому рекомендуется использовать алгоритм с просмотром на несколько ходов вперёд.
[2 балла] Написать программу, которая переставляет цифры натурального числа таким образом, чтобы образовалось наименьшее число, записанное этими же цифрами.
[4 балла] Реализовать свою функцию printf. Она получает на вход строку (или файл), форматную строку (содержащую %i, %c, %s, %*i, %*c, %*s и символы, не являющиеся спецификациями формата), массив void* с параметрами, и число - количество переданных параметров. На выходе она модифицирует первый параметр, выводя туда отформатированную строку.
[5 баллов] Реализовать свою функцию scanf. Она получает на вход строку (или файл), форматную строку (содержащую %i, %c, %s, %*i, %*c, %*s и символы, не являющиеся спецификациями формата), массив void* с параметрами, и число - количество переданных параметров. На выходе она модифицирует массив аргументов, заполняя его данными, полученными из первого параметра.

[3 балла] Дан массив с коэффициентами многочлена от x. Требуется написать программу, "красиво" выводящую этот многочлен на консоль. Например, многочлен, представляемый коэффициентами 1 5 -10, выводится так:

	2
x		+	5	x	-	1	0

[3 балла] Алгебраическая структура из N элементов с бинарной операцией '*' задана своей таблицей Кэли, т.е. матрицей K[NxN], где K[i,j] = a[i]*a[j].
а) Определить наиболее точно тип структуры: группоид, полугруппа, моноид, группа, абелева группа;
б) случай группы: вложить данную структуру в какую-нибудь группу перестановок.
[4 балла] В n-мерном аффинном пространстве проведены две прямые, каждая из которых задана точкой и вектором направления. Определить, пересекаются ли эти прямые, и в случае пересечения вычислить угол между ними.

Разделы

Персональные инструменты

Задачи на семестр, осень 2009, 145 группа

Действия с Документом