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

Практикум на ЭВМ, весна 2013, 171


Новости

  • 02.04.2013 - Опубликованы комментарии к некоторым заданиям на F#.

Часть 1 - Си/Интерпретатор SVM

Задание 1.
  • Написать алгоритм нахождения наибольшего общего делителя на языке ассемблера.
    В задаче закодировать входные данные - 2330 и 3770, как первые две инструкции ldc.
Задание 2.
  • Реализовать интерпретатор SVM
Задание 3. На языке ассемблера SVN реализовать следующие задачи:
  • Посчитать сумму чётных чисел Фибоначчи не превосходящих 2000000.
  • Найти 10001-ое простое число.
  • * Найти наибольший простой делитель числа 208574561.
Задание 4. Design Document
  • Написать документ описывающий предложения по реализации процедур, вызовов и передачи параметров при вызовах в языке ассемблера и виртуальной машине SVN.
    Хороший документ должен содержать следующую информацию:
    • Заголовок, автор (группа)
    • Введение - пара предложений с описанием контекста документа (что это все про SVM) 
    • Постановка задачи: мотивация для введения реализации процедур и требования к ним. 
    • Основная часть (предложение): рассмотреть синтаксис и семантику команд, которые предлагается ввести.
    • Заключение: анализ того, что получилось.
    • Приложение: примеры программ с использованием предложенного синтаксиса.
      (Можно не выносить в приложения, а оставить в основной части.)

Инфраструктурное

Для выкладывания заданий каждый должен создать логин на сайте https://github.com и репозиторий для заданий. 
  • Все задания должны быть выложены в репозиторий на github.
Задание git-training: записаться в список в репозитории https://github.com/vpolozov/git-training

Часть - 2: F#

Задание 1: Введение в синтаксис F#/ императивное программирование  на F#
  • Решить первые 10 проблем projecteuler.net
  • * Либо решить любые 3 проблемы с projecteuler.net с количеством сдавших менее 10000.
Замечание 1. Для реализации некоторых заданий точности типа int (int32) может не хватить. Но есть несколько целочисленных альтернатив:
    • int64 - 64-битное знаковое целое. Пример записи литерала: 123456L
    • bigint - целое число произвольной точности (синоним для System.Numerics.BigInteger - http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx). Пример записи литерала: 123456I
или не целочисленных:
    • float - аналог double в Си. Не рекомендуется для точных вычислений и десятичной арифметики. Пример: 123.456
    • decimal - десятичное число с плавающей точкой: 127 бит - 1 бит знак, 96 битовое целое число (~ ±7.9×1028), и оставшиеся биты могут принимать значения 0-28, что соответствует количеству знаков после запятой. Пример: 123.456M
Для конвертации типа, как правило, можно использовать функцию с тем же именем. Например, "int x" -  приведение к целому, "float n" - приведение к типу float.
Подробнее про литералы различных типов можно посмотреть тут: http://msdn.microsoft.com/en-us/library/dd233193.aspx

Задание 2: Без использования изменяемых значений (mutable, ref и т.п.) реализовать следующие функции:
  • Добавление элемента в конец списка
    addToEnd :: 'a -> list 'a -> list 'a
  • Конкатенация списков
    append :: 'a list -> 'a list -> 'a list
  • "Перевернуть" список
    reverse :: 'a list -> 'a list
    Постараться сделать за O(n) операций
  • Поиск элемента в списке по предикату
    find :: ('a -> bool) -> 'a list -> 'a option
  • Реализовать функцию map, применяющую любую функции к каждому элементу списка
    map :: ('a -> 'b) -> 'a list -> 'b list
    используя либо библиотечную функцию  List.foldBack либо List.fold
  • Для всех функций написать тесты, например, как функцию (unit -> bool)
Задание 3: Создать алгебраический тип данных (АДТ) соответствующий бинарному дереву поиска и реализовать следующие функции для работы с ним:
  • добавление элемента в дерево
  • проверка, есть ли такой элемент в дереве
  • удаление элемента из дерева
  • "красивая" печать дерева
    Задание 4: Реализовать библиотеку длинной арифметику используя объектно-ориентированный подход :
    • Тип, соответствующий целому числу со знаком без ограничений по длине.
    • Операции реализовать как методы (члены, member) данного типа:
      • Сложение
      • Вычитание
      • Умножение
      • * Деление
      Успеваемость

      2012-2013.IT.171


      Comments