Практикум на ЭВМ (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