Архив‎ > ‎Весна 2009‎ > ‎

Практикум на ЭВМ (161, 2 семестр)

Правила

На данный момент используем WinHugs. В сети МатМеха его можно найти в папке \\FS4\teachers\victorp\public\Haskell\

Критерии

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

Задания

Первая группа

Первая группа заданий включает набор задач на освоение синтаксиса языка Хаскель

  1. Факториал
  2. Длина списка
  3. Добавление элемента в конец списка
  4. Инвертировать список
  5. Числа Фибоначи: последовательность, начинающаяся с двух 1, в которой каждое следующее число является суммой двух предыдущих.
    1. Найти список всех чисел Фибоначчи, используя формулу для i-го числа.
      Подсказка 1: [1..] - список всех натуральных чисел.
      Подсказка 2: для тестирования используйте функцию take. 
    2. Найти список всех чисел Фибоначчи через рекурентное соотношение
      Подсказка: Если уже есть список из n членов, из него легко получить список из n+1 члена.
    3. Найдите сумму всех четных чисел Фибоначчи, не превосходящих 4 000 000
      Замечание: можно воспользоваться функциями even или mod. Синтаксический сахар `mod` - делает из функции операцию.
  6. Простые числа
    1. Найти список всех простых чисел через тест на простоту.
    2. Найти список всех простых чисел решетом Эратосфена.
    3. Найти наибольший простой делитель числа 600851475143.
      Замечание: за приемлемое время, не больше минуты.
  7. Оставить в списке только элементы, удовлетворяющие условию.
  8. Реализовать алгоритм "Быстрой сортировки": для некоторого элемента списка, отсортированный по возрастанию список - это отсортированный список элементов меньших данного, за которыми следует данный элемент, за которым отсортированный список элементов не меньших данного.
    Замечание: функцию для сравнения элементов можно передать аргументом.
  9. Реализовать аналог стандартной функции map через foldl или foldr

Ввод/Вывод

Задачи на стандартный ввод/вывод в языке Хаскель
  1. head - вывести в стандартный поток вывода первые n строк из входа.
  2. tail - вывести в стандартный поток вывода последние n строк из входа.
  3. sort - вывести в стандартный поток вывода все строки из входа, отсортированные в лексикографическом порядке.
  4. uniq - вывести в стандартный поток вывода все строки из входа, пропуская все последовательно повторяющиеся строки кроме одной.
Программы должны работать аналогично одноименным утилитам из Linux:
  • Каждая из программ имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться их стандартного потока ввода.
  • head и tail можно передать необязательный параметр "-n <число>" задающий количество строк для вывода. По умолчанию - 10.
  • Если во входе head и tail менее n строк, то выводится весь вход.

Компилятор/Ассемблер

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

  1. Реализовать на описанном языке ассемблера алгоритм нахождения НОД
  2. Реализовать вычислитель как функцию :: [Instruction String] -> [Int]

(будет дополнено позже)

Успеваемость

Ссылки

Подстраницы (1): Язык ассембера VitASM
Comments