Skip to content

Задачи 1 семестр

Jump to bottom Edit New page
Semyon edited this page Mar 2, 2016 · 1 revision

Задачи по практике.

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

03.09.2015--07.09.2015

  1. Инициализировать рабочее окружение. Оформить тестовый pr: всё, что получилось после инициализации рабочей папки.

07.09.2015-14.09.2015

  1. Вычислить значение выражение x^4+x^3+x^2+x+1 "наивным" способом. main x = значение_выражения. Реализовать чтение x из консоли и вывод результата в консоль.

  2. Вычислить значение выражение x^4+x^3+x^2+x+1, применив минимальное число умножений. main x = значение_выражения. Реализовать чтение x из консоли и вывод результата в консоль.

  3. Вычислить индексы элементов массива, не больших, чем заданное число. main inArray num = outArray (массив индексов)

  4. Вычислить индексы элементов массива, лежащих вне диапазона, заданного двумя числами.
    main inArray lowBound highBound = outArray (массив индексов)

  5. Дан массив длины 2. Поменять местами нулевой и первый элементы, не используя дополнительной памяти/переменных. main inArray = outArray

  6. Поменять местами i-й и j-й элементы массива не используя дополнительной памяти/переменных. main inArray i j = outArray (исходный массив, где поменяны местами i-й и j-й элементы)

14.09.2015-28.09.2015

  1. Реализовать вычисление n-ого числа Фибоначчи рекурсивным методом. main n = fibN (n-ое число Фибоначчи)

  2. Реализовать вычисление n-ого числа Фибоначчи итеративным методом. main n = fibN (n-ое число Фибоначчи)

  3. Реализовать вычисление n-ого числа Фибоначчи итеративным методом, но не используя ref-переменных (и mutable) и других мутабельных структур. Подсказка: нужно использовать рекурсию. main n = fibN (n-ое число Фибоначчи)

  4. Реализовать вычисление n-ого числа Фибоначчи через перемножение матриц "наивным" методом. main n = fibN (n-ое число Фибоначчи)

  5. Реализовать вычисление n-ого числа Фибоначчи через перемножение матриц за логарифм. main n = fibN (n-ое число Фибоначчи)

  6. Реализовать вычисление всех чисел Фибоначчи до n-ого включительно. main n = outArray (массив, хранящий все числа Фибоначчи до n-ого включительно)

  7. Для задач 8-13 построить общий график, показывающих зависимость времени вычисления от n. Графики должны быть "понятными". Как минимум в том смысле, что после взгляда на них, должно быть понятно, какой из алгоритмов быстрее, а какой медленнее. Использовать FSharp.Charting.

28.09.2015-5.10.2015

  1. Реализовать самостоятельно тип List.

  2. Реализовать функцию вычисления длины, которая работает с типом List из предыдущей задачи. main: List -> int

  3. Реализовать тип MyString, который представляет строку как List из символов.

  4. Реализовать фунркцию toMyString: string -> MyString.

  5. Определён тип Tree.

    type Tree =
    | Node of int * TreeList
    | Leaf of int

TreeList -- List из деревьев (см. предыдущие задачи). Реализовать функцию, вычисляющую наибольший и наименьший элементы в листьях. main: Tree -> (int*int)

12.10.2015-19.20.2015

  1. Переименовать ранее созданный тип List в MyList. Обратите внимание, что все остальные задачи должны остаться работоспособными.

  2. Реализовать сортировку пузырьком для типа MyList. Результирующий список должен быть отсортирован по возрастанию. main: MyList<int> -> MyList<int>

  3. Реализовать сортировку Хоара (quicksort) "в функциональном стиле": использовать списки и рекурсию.
    main: MyList<int> -> MyList<int>

  4. Реализовать сортировку Хоара (quicksort) без использования дополнительных массивов и других вспомогательных структур данных. Результирующий массив должен быть отсортирован по возрастанию. main: array<int> -> array<int>

  5. Построить графики производительности для сортировок, реализованных ранее и стандартных Array.sort и List.sort. Учесть результаты предыдущей домашней работы по построению графиков.

26.10.2015-02.11.2015

  1. Выбрать одну задачу из списка: 10, 13, 14, 18, 19, 21, 22, 23 ,24. Представить, что это курсовая работа. Подготовить презентацию и сделать доклад.

02.11.2015-09.11.2015

  1. Реализовать вычислитель для нормальных алгорифмов Маркова. Задать входной язык (лексика, синтаксис). Результат -- грамматика. Можно в комментариях в шапке файла. Затем создать парсер входного языка. Парсер можно создавать любым способом кроме взятия готового. Реализовать интерпретатор и набор тестов.

09.11.2015-16.11.2015

  1. Вывести в консоль битовое представление типа float. main: float -> unit

  2. Вывести в консоль битовое представление типа int. main: int -> unit

  3. Вывести в консоль битовое представление типа int64. main: uint -> unit //После предыдущих задач надо знать, какие биты что означают.

  4. Реализовать операцию сложения в длинной арифметике. Для представления больших чисел здесь и далее используем MyList, знак выделен отдельно, ведущих нулей нет. (type Num = sign * MyList) sum: Num -> Num -> Num

  5. Реализовать операцию умножения в длинной арифметике. mult: Num -> Num -> Num

16.11.2015-23.11.2015

  1. Адаптировать задачи 8-14 под длинную арифметику.

23.11.2015-30.11.2015

  1. Для задачи 32(14) предоставить следующие элементы документации. Подразумевается, что в задаче 32(14) у вас есть много реализвций фйнкций для вычисления чисел Фибоначчи, адаптированных к длинной арифметике и визуализация, согласно задаче 14.
  • Требования
    • Зачем
    • Сценарий
    • Функции
  • Тесты
  • Диаграма модулей
  1. Штрафная. Разработать для задачи 26 архитектуру, позволяющую независимо использовать различные источники для задания правил и программы (файл, строка, ввод с консоли). Нарисовать соответствующую диаграму модулей. Реализовать разработанную архитектуру. Продемонстрировать неснолько сценариев (несколько различных способов получения входных данных).
Add a custom footer
Add a custom sidebar
Clone this wiki locally