Архив‎ > ‎Осень 2013‎ > ‎

Практикум на ЭВМ (171 группа, первый семестр)

Новости

  • 11.10 - состоится контрольная по пройденным темам: основы языка Си, сортировки, и т.п.
  • 01.09 - Пройти опрос
Успеваемость

Часть 1 - Си

Домашние задания

Задание 1. 13.09.2013 - оформление, основы Си
  1. Посчитать целую степень числа: a^n. 
  2. Реализовать проверку числа на простоту.
  3. Реализовать программу, проверяющую, является ли строка палиндромом.
Задание 2. 20.09.2013 - строки, сортировки, печать
  1. Самостоятельно реализовать следующие функции работы со строками:
    • int strlen(char*) - длина строки
    • strcpy(char* dst, char* src) - копирование строки
    • strcat(char* dst, char* src) - конкатенация строк
    • int strcmp(char* s1, char* s2) - лексикографическое сравнение строк. Результат сравнения: 0 - равны, <0 - первая меньше, >0 - первая больше.
  2. Реализовать сортировку пузырьком и ещё любые два алгоритма сортировки на выбор.
  3. Для реализованных сортировок проверить время выполнения в зависимости от следующих параметров:
     - от размера массива: маленький (<=10), средний (100-1000), большой (>10000)
     - от начального состояния массива: уже упорядоченный, "почти" упорядоченный, "случайный"
    Собрать полученные данные в сводную таблицу. Проанализировать.
  4. Напечатать таблицу размера NxN, в которой 
    - первая строка и первый столбец заполнены числом 1
    - любая другая ячейка образуется, как сумма соседних ячеек сверху и слева от неё, если они уже посчитаны.
Задание 3. 27.09.2013 - представление чисел в памяти. числа с плавающей точкой.
  1. Напечатать двоичное представление целого числа с использованием битовой арифметики:.
    Дополнительно: 
    • пропустить при печати ведущие нули;
    • проверить гипотезу про представление чисел в дополнительном коде;
    • проверить endianness вашего компьютера.
  2. Красиво напечатать числа float 
    1. Стандарт IEEE 754
    2. Пример печати числа  -0.05078125:
          0    -5
      (-1)  * 2   * 1.101
Задание 4. 04.10.2013 - стек вызовов, динамическая память, командная строка, файлы.
  1. Использовать уязвимость "переполнения буфера" в функции gets
    • Программа должна считывать строку функцией gets
    • В программе есть операторы printf("No") и printf("Yes")
    • Если нет переполнения буфера, то программа всегда должна печатать "No"
    • При специально подобранном входе, вызывающем переполнение буфера, выполнение программы должно изменяться так, чтобы напечаталось "Yes"
    • После печати сообщения "Yes" допустимо некорректное завершение программы
    • Вход может зависеть от используемого компилятора и ОС
    • Усложнённая версия: вызов gets и операторы printf должны быть в разных функциях
  2. Реализовать программу head - печать первых n строк входного файла.
    Программа должна работать аналогично одноименной утилите Linux (http://unixhelp.ed.ac.uk/CGI/man-cgi?head):
    • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
    • Программе можно передать необязательный параметр "-n <число>" задающий количество строк для вывода. По умолчанию - 10.
    • Если на входе менее n строк, то выводится всё содержимое.
  3. Реализовать программу sort - печать только строк входного файла в лексикографическом порядке возрастания.
    Программа должна работать аналогично одноименной утилите Linux (http://unixhelp.ed.ac.uk/CGI/man-cgi?sort):
    • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
    • * Длина строк не ограничена
  4. Реализовать программу uniq - печать только таких строк входного файла, которые не повторяют предшествующую ей строку. (удаление последующих дубликатов строки)
    Программа должна работать аналогично одноименной утилите Linux (http://unixhelp.ed.ac.uk/CGI/man-cgi?uniq):
    • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
Стековый калькулятор
Реализовать стековый калькулятор со следующими командами
  • число - положить число в стек
  • операция (+, -, *, /) - достать два числа из стека, применить к ним операцию, и положить результат в стек
  • pop - достать верхнее число со стека и напечатать
  • dup - удвоить верхнее число на стеке
  • exit - выход
Если в стеке нет достаточного числа операндов - сообщить об ошибке.
Каждая команда вводится отдельной строкой входного потока.

Рекурсивный спуск/грамматики
  1. Реализовать вычисление значения арифметического выражения (с операциями +, -, *, / и скобками) методом рекурсивного спуска
  2. Добавить в грамматику арифметических выражений:
    • возведение в степень (^) как право-ассоциативную операцию с приоритетом выше, чем у умножения
    • вызов функции, по аналогии с синтаксисом языка Си. Например: "sin(x)", "pow(2, 10)", "getc()"
Карты
Правила игры
  • Каждая карта имеет масть и значение
  • 4 масти: Spades (), Clubs (), Hearts (), Diamonds ()
  • Значения: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack (Валет), Queen (Дама), Король (King), Туз (Ace)
  • Каждой карте приписано числовое значение: 
    • 2-10 - значение по номиналу
    • Картинки (Jack, Queen, King) - 10 
    • Туз (Ace) - 11
  • Правила подсчета очков "на руке" у игрока:
    • Считается сумма значений всех карт (sum).
    • Предварительные очки: если набранная сумма не больше 21, то (21-sum), иначе (sum-21)*3
    • Окончательные очки: если все карты на руке одного цвета, то предварительная сумма делится пополам.
  • Во время игры доступны действия
    • Take - взять верхнюю карты колоды карту в руку.
    • Stop - прекратить игру, перейти к подсчету очков.
    • Drop <карта> <масть> - сбросить одну из карт на руке.
  • Если в какой-то момент сумма значений карт на руке у игрока превышает 21 - игра останавливается.
  • Цель игры - набрать как можно меньше очков.
Задача: написать "осторожного" игрока.
  • TBD



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