Практические занятия по курсу ОиМП — различия между версиями
(→C++) |
(→Задание 3. Контейнеры. vector и list (18.10 - 1.11)) |
||
Строка 57: | Строка 57: | ||
===Задание 3. Контейнеры. vector и list (18.10 - 1.11)=== | ===Задание 3. Контейнеры. vector и list (18.10 - 1.11)=== | ||
− | [http://official.contest.yandex.ru/contest/ | + | [http://official.contest.yandex.ru/contest/762/enter/ Обработка последовательностей.] Нужно решить 15 (из 18) любых задач. Перед выполнением обязательно прочитайте требования к решениям: |
# '''Важно!''' В каждой задаче используйте vector или list даже если задачу можно решить без использования контейнера. Половину задач решите, используя список, половину используя вектор. | # '''Важно!''' В каждой задаче используйте vector или list даже если задачу можно решить без использования контейнера. Половину задач решите, используя список, половину используя вектор. | ||
# Давайте функциям и переменным понятные имена. Такие, чтобы по имени можно было понять что они делают. | # Давайте функциям и переменным понятные имена. Такие, чтобы по имени можно было понять что они делают. | ||
Строка 67: | Строка 67: | ||
# При передаче параметров в функции пишите const везде, где это возможно; передавайте по ссылке везде, где это уместно. | # При передаче параметров в функции пишите const везде, где это возможно; передавайте по ссылке везде, где это уместно. | ||
# Везде, где это уместно, пишите ''шаблоны функций''. | # Везде, где это уместно, пишите ''шаблоны функций''. | ||
+ | Требования обязательны, но проверяться они не будут. То есть, за программу не удовлетворяющую требованиям выше, я не снижу оценку. Этот контест --- это возможность попрактиковаться в написании красивого кода (и поспрашивать что красиво, а что нет) перед второй домашней работой в которой, скорее всего, оценки за некрасоту кода будут снижаться. Я не буду прицельно смотреть сданные вами решения, ибо предполагаю, что когда вам что-то непонятно, вы сами покажите код и спросите какие есть замечания. | ||
====Необязательное задание==== | ====Необязательное задание==== |
Версия 01:43, 18 октября 2014
О курсе
Алгоритм подсчёта итоговой оценки по курсу
В курсе предусмотрены следующие виды работ: четыре домашние работы, контрольная и экзамен. За каждую из шести работ выставляется оценка от 0 до 10 включительно. При этом 20% от оценки за домашнюю работу составляет оценка за текущие работы:
<оценка за текущую работу> = (<количество выполненных обязательных заданий в установленный срок> + 0.5 * <количество выполненных обязательных заданий позже установленного срока> + 0.3 * <количество выполненных необязательных заданий>) / <количество обязательных заданий>
<итоговая оценка за текущую работу> = min(<оценка за текущую работу>, 10)
<итоговая оценка за домашнюю работу (ИОДР)> = 0.8 * <оценка за домашнюю работу> + 0.2 * <итоговая оценка за текущие работы>
<итоговая оценка по курсу> = 0.6 * (<ИОДР 1> + <ИОДР 2> + <ИОДР 3> + <ИОДР 4>)/4 + 0.15 * <оценка по контрольной работе> + 0.25 * <оценка за экзамен>
C++
Среда разработки
Лучше всего использовать Eclipse. Инструкция по созданию проекта Eclipse.
Если не получится установить или запустить, то можно:
- Использовать Visual Studio (только для тех, кто в ней уже работал).
- Использовать онлайн компилятор: compileonline или ideone. В ideone требуется поменять язык с Java на C++11. В обоих компиляторах требуется в поле ввода stdin вписать значения, которые подаются программе на вход. Например, для первой программы из примера ниже, можно написать "24" (без кавычек), для второй "0.2 1.1".
Примеры программ
Требуется спросить у пользователя его возраст, а затем вывести возраст и 1, если он больше 20, и 0, если меньше или равен.
#include <iostream> using namespace std; int main() { cout << "How old are you?" << endl; int age; // объявление целочисленной переменной в которой будет храниться возраст cin >> age; // чтение с консоли cout << "Your age: " << age << ", it's more than 20: " << (age > 20) << endl; }
Пользователь вводит два вещественных числа step и bound. Требуется вывести вещественные все числа через пробел, начиная с 0 с шагом step и не превосходящие bound.
#include <iostream> using namespace std; int main() { double step; double bound; cin >> step >> bound; for (double d=0; d < bound; d += step) { cout << d << " "; } }
Задание 1 Основные конструкции С++ (08.10 - 22.10)
Введение в C++. Нужно сделать 9 любых задач из 10.
Задание 2. Функции (11.10 - 21.10)
Функции в C++. Нужно сделать 7 любых задач из 8.
Задание 3. Контейнеры. vector и list (18.10 - 1.11)
Обработка последовательностей. Нужно решить 15 (из 18) любых задач. Перед выполнением обязательно прочитайте требования к решениям:
- Важно! В каждой задаче используйте vector или list даже если задачу можно решить без использования контейнера. Половину задач решите, используя список, половину используя вектор.
- Давайте функциям и переменным понятные имена. Такие, чтобы по имени можно было понять что они делают.
- Не используйте однобуквенных имён переменных, кроме имён для счётчиков цикла (i, j, k, ...).
- Не используйте транслит при именовании переменных.
- Старайтесь вынести логические блоки в отдельные функции. Подсказка: чтение вектора (списка) должно быть оформлено как отдельная функция.
- Решение каждого задания должно быть оформлено в отдельной функции.
- Для каждой функции пишите комментарий с пояснением что делает эта функция. В комментарии можно описать входные и выходные значения.
- При передаче параметров в функции пишите const везде, где это возможно; передавайте по ссылке везде, где это уместно.
- Везде, где это уместно, пишите шаблоны функций.
Требования обязательны, но проверяться они не будут. То есть, за программу не удовлетворяющую требованиям выше, я не снижу оценку. Этот контест --- это возможность попрактиковаться в написании красивого кода (и поспрашивать что красиво, а что нет) перед второй домашней работой в которой, скорее всего, оценки за некрасоту кода будут снижаться. Я не буду прицельно смотреть сданные вами решения, ибо предполагаю, что когда вам что-то непонятно, вы сами покажите код и спросите какие есть замечания.
Необязательное задание
Задачи можно решать в любом порядке и можно решить не все. Старайтесь использовать понятные имена функций и переменных. Избегайте транслит.
- Напишите функцию, которая заполняет вектор случайными элементами.
- Напишите функцию, которая принимает на вход два вектора и возвращает true, если они равны, и false в противном случае.
- Напишите функцию, которая принимает на вход вектор и сортирует его пузырьком.
- Напишите функцию, которая принимает на вход вектор и сортирует его поиском максимума.
- Напишите функцию, которая принимает на вход вектор и сортирует его слиянием.
- Напишите функцию, которая принимает на вход вектор и сортирует его быстрой сортировкой.
- Выведите время работы каждой из функций сортировки для векторов разной длины.
Питон
Полезные ссылки
Для выполнения заданий необходимо установить интерпретатор Python.
Задачи, которые точно нужно уметь решать.
Рекомендации по выполнению
- Не используйте wildcard imports (from <module> import *), см. PEP8.
- Знак присваивания обособляйте пробелами с двух сторон. Плохо: a=b. Хорошо: a = b.
- Если требуется сравнить два числа с плавающей точкой (float) на равенство, то сравнивайте модуль их разницы с некоторым eps: |d1 - d2| < 0.0000001.
Задание 1. Ввод-вывод (4.09 - 20.09)
Список обязательных задач для каждого студента.
Задание 2 (6.09 - 20.09)
Перед выполнением задания нужно установить библиотеку Pillow.
Замечание. Доступ к элементам pixels осуществляется так: pixels[i,j].
Бонусные задачи
- Реализуйте масштабирование.
- Реализуйте отражение.
- Реализуйте размытие.
- Напишите свой фильтр для обработки изображений.
Задание 3 (13.09 - 27.09)
Решите 20 любых задач из контеста Ввод-вывод.
Бонусное задание. Шифрование RSA
- Реализуйте алгоритм создания открытого и секретного ключей.
- Реализуйте алгоритмы шифрования и дешифрования. Проверьте, что они работают.
- Реализуйте алгоритм взлома. Функция должна принимать аргументы c, n и m (см. обозначения в Википедии) и возвращать d, приватный ключ, такое что m == c^d mod n.
- Научитесь замерять время выполнения каждой из четырёх функций (функции генерации ключей, шифрования, дешифрования и взлома).
- Выберите некоторое значение m, например, m=100. Выведите таблицу:
n=11*13=143 | n=17*31=527 | n=109*157=17113 | n=3557*2579=9173505 | n=3533*3571=12616343 | |
---|---|---|---|---|---|
e=3 | |||||
e=17 | |||||
e=257 | |||||
e=65537 |
На пересечении i-ой строки и j-ого столбца должно стоять четыре неотрицательных числа --- время работы каждого из четырёх алгоритмов при заданных e и n. Если данное e не взаимно просто с n, поставить прочерк.
Задание 4 (18.09 - 2.10)
Если в вашей фамилии чётное число букв, то решите все чётные задачи из контеста Обработка текста, иначе все нечётные.
Домашнее задание 1 (26.09 - 6.10)
Первое большое домашнее задание. Каждому студенту требуется сделать пять задач из 20. Список обязательных задач здесь.
При оценке домашнего задания будут учитываться оценки за задания 1-4.
Копия домашней работы. Если вы что-то решили/нашли ошибку после окончания срока сдачи домашней работы, вы можете отправить решения туда, чтобы проверить их. Эти результаты не будут учтены при оценке домашней работы.
Внимание! После 6.10 задания 1-4 и первая домашняя работа не принимаются.