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

Новости

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

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

2013-2014.SE.171

Часть 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 - первая больше.
    1. Реализовать сортировку пузырьком и ещё любые два алгоритма сортировки на выбор.
    2. Для реализованных сортировок проверить время выполнения в зависимости от следующих параметров:
    3. - от размера массива: маленький (<=10), средний (100-1000), большой (>10000)
    4. - от начального состояния массива: уже упорядоченный, "почти" упорядоченный, "случайный"
    5. Собрать полученные данные в сводную таблицу. Проанализировать.
    6. Напечатать таблицу размера NxN, в которой
    7. - первая строка и первый столбец заполнены числом 1
    8. - любая другая ячейка образуется, как сумма соседних ячеек сверху и слева от неё, если они уже посчитаны.

Задание 3. 27.09.2013 - представление чисел в памяти. числа с плавающей точкой.

    1. Напечатать двоичное представление целого числа с использованием битовой арифметики:.
    2. Дополнительно:
    • пропустить при печати ведущие нули;
    • проверить гипотезу про представление чисел в дополнительном коде;
    • проверить endianness вашего компьютера.
  1. Красиво напечатать числа float
    1. Стандарт IEEE 754
      1. Пример печати числа -0.05078125:
        1. 0 -5
        2. (-1) * 2 * 1.101

Задание 4. 04.10.2013 - стек вызовов, динамическая память, командная строка, файлы.

    1. Использовать уязвимость "переполнения буфера" в функции gets
      • Программа должна считывать строку функцией gets
      • В программе есть операторы printf("No") и printf("Yes")
      • Если нет переполнения буфера, то программа всегда должна печатать "No"
      • При специально подобранном входе, вызывающем переполнение буфера, выполнение программы должно изменяться так, чтобы напечаталось "Yes"
      • После печати сообщения "Yes" допустимо некорректное завершение программы
      • Вход может зависеть от используемого компилятора и ОС
      • Усложнённая версия: вызов gets и операторы printf должны быть в разных функциях
    2. Реализовать программу head - печать первых n строк входного файла.
    3. Программа должна работать аналогично одноименной утилите Linux (http://unixhelp.ed.ac.uk/CGI/man-cgi?head):
      • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
      • Программе можно передать необязательный параметр "-n <число>" задающий количество строк для вывода. По умолчанию - 10.
      • Если на входе менее n строк, то выводится всё содержимое.
  1. Реализовать программу sort - печать только строк входного файла в лексикографическом порядке возрастания.
  2. Программа должна работать аналогично одноименной утилите Linux (http://unixhelp.ed.ac.uk/CGI/man-cgi?sort):
      • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
      • * Длина строк не ограничена
  3. Реализовать программу uniq - печать только таких строк входного файла, которые не повторяют предшествующую ей строку. (удаление последующих дубликатов строки)
  4. Программа должна работать аналогично одноименной утилите 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