Problem Set 5: Три в одном

Objectives

  • Подготовиться к работе с математической библиотекой и арифметическими выражениями.
  • Понять представление чисел в памяти компьютера.
  • Научиться заканчивать программы, используя разные коды возврата в различных ситуациях.

Task 1: Self-Checkout

Конечно, вы уже видели кассы самообслуживания в Теско - место, где вы можете оплачивать приобретенные товары без кассира. Касса будет вам подсказывать в процессе подсчёта суммы за товары до тех пор пока не пройдёт оплата и не выдастся сдача в случае, если вы заплатили больше нужного.

Касса самообслуживания в Tesco.
Obr. 1: Касса самообслуживания в Tesco.

Мы не будем заниматься ни графическим интерфейсом кассы, ни процессом считывания штрих-кода товара, ничего другое. В данном случае нас будет интересовать заключительная часть - процесс оплаты покупателем и выдача сдачи, если покупатель дал больше, чем требовалось.

Программа сначала получит на вход сумму для покупки товаров. Данная сумма будет представлена положительным десятичным числом, для которого будет правдиво: 0 < сумма < 10000. Сумму будет представлять собой число в евро валюте, но самого символа евро на входе не будет. Таким образом, если суммой к оплате является сумма в 97.23 евро, то правильное число на входе будет именно 97.23, а не 9723 и тем более не округленное 97, и т.д.

Если сумма, полученная на входе не соответствует области определения, то программа должна сразу завершиться с кодом 1 и сообщением Wrong input!.

Для денег во всей нашей программе будет также правдиво следующее:

  • Если мы говорим о центах, то на экране они должны быть выписаны с точностью 2 места после запятой. Например, 50 центов будет выглядеть правильно как 0.50, но никак не 0.5 или 50, или 0.50000.
  • Если число не содержит в себе центов, то правильно оно должно быть выписано без части после запятой. Например, 100 евро будет выглядеть как 100, а не 100.00.

Затем программа начнем считывать банкноты и копейки, которым хочет покупатель заплатить. Касса самообслуживания может работать только со следующими номиналами банкнот и копеек: 100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02 и 0.01. Исходя из приведённого выше, с помощью введённых банкнот и копеек можно заплатить за любую покупку с точностью до одного цента. Порядок ввода денежных средств не имеет значения, при этом ввод средств одинакового номинала не является проблемой.

Считывание с клавиатуры закончится тогда, когда при вводе программа наткнётся на 0 или стандартный ввод закончится (считается EOF например комбинацией клавиш Ctrl+d).

Считывание банкнот покупателя.
Obr. 2: Считывание банкнот покупателя.

Примером такой последовательности денежных средств на сумму 103.23 евро может являться следующее:

20 0.10 10 0.01 0.02 10 20 1 10 0.5 20 0.5 10 1 0.10

Также можно ввести такую же сумму другими способами:

100 2 1 0.20 0.02 0.01

Программа для кассы затем определит, не заплатил ли покупатель больше суммы, составляющей его общую покупку. Если да, система начнет выдавать сдачу. При этом сдача будет выдаваться максимально возможным номиналом. В случае, если без повторения номинала при сдаче не обойтись, должно быть выдано столько, сколько нужно.

К примеру, если касса должна выдать сдачу на сумму 15.80 евро, тогда последовательность выдачи должна выглядеть именно так:

10 5 0.50 0.20 0.10

Program Examples

В следующем тексте будут приводиться примеры использования программы. Текст, выделенный жирным шрифтом представляет ввод пользователя, а рядок, начинающийся с '$' представляет командную строку.

В данном случае сумма к оплате составляет 37.57 евро. Покупатель постепенно внесёт необходимую сумму, а касса, в свою очередь, выдаст соответствующую сдачу.

$ ./tesco
Enter value of your bill: 37.57
Insert money for payment: 10 5 5 20
You have inserted: 40
To return: 2.43
Collect your payback: 2 0.20 0.20 0.02 0.01

Comment

Обратите внимание, что ввод пользователя не был закончен 0. В данном случае стандартный вводу был окончен (например, с помощью Ctrl+d).

Если покупатель не внесёт минимальной для покупки суммы, программа должна выдать сообщение Not enough money!.

$ ./tesco
Enter value of your bill: 37.57
Insert money for payment: 1 5 5 0
You have inserted: 11
Not enough money!

Если покупатель попробует ввести неправильную номиналом денежку, касса должна распознать данные "фальшивые" деньги и выписать на экран сообщение X is invalid!, где X представляет первую распознанную фальшивку. Программа после вывода на экран должна закончить свою работу со значением 1.

$ ./tesco
Enter value of your bill: 37.57
Insert money for payment: 25 25 0
25 is invalid!

Warning

В случае, если фальшивая монета или купюра будет записана с десятичной частью, на экран должно выписаться она и с десятичной частью на 2 места после запятой.
$ ./tesco
Enter value of your bill: 37.57
Insert money for payment: 37.57 99.99 0
35.57 is invalid!

Если покупатель внесёт сумму равную сумме к оплате, касса в таком случае должна выписать сообщение что сдача составляет 0 Евро.

$ ./tesco
Enter value of your bill: 27.52
Insert money for payment: 10 5 10 2 0.01 0.01 0.05 0.05 0.20 0.20
You have inserted: 27.52
To return: 0

Comment

Каждый вывод на экран должен заканчиваться символом перевода строки '\n'.

Assessment

За данное задание возможно получить макс 4 балла. Для успешного прохождения тестов очень важно, чтобы вывод вашей программы совпадал с описанным заданием выводом, поскольку тестирование будет заключаться в сопоставлении ваших результатов с нашими.

Warning

При тестировании оценивается каждый символ!

Comment

Вывод программы должен заканчиваться символом конца строки '\n'.

Task 2: Enemy in Sight!

Границы Королевства Семи на западе проходят по берегам Розового Моря. Для того, чтобы стране дать отпор возможному неприятелю, на побережье размещены на разном расстоянии друг от друга смотровые башни. Из них видна морская гладь, а также две ближайшие башни. В случае, если в поле зрения на море попадает вражеский корабль, с помощью триангуляции можно точно определить и послать координаты неприятеля артиллерии королевства.

Положение можно узнать в том случае, если вражеский корабль находится в поле обзора меж двух соседних смотровых башен. Дозорный на башне A может измерить угол между кораблём и соседней смотровой башней B. Аналогично, дозорный со второй башни B может измерить угол между кораблём и башней A. Зная позиции смотровых башен и двух измеренных углов, можно узнать точные координаты корабля в море.

Иллюстрация, объясняющая ситуацию на побережье
Obr. 3: Иллюстрация, объясняющая ситуацию на побережье

Потому перед вами стоит задача написать программу для Королевства Семи, которая позволит с помощью полученных данных определить позицию вражеского корабля. Для этого напишите 3 функции:

  • float to_radians(const int angle) - Конвертация градусов в радианы.
  • float get_watchtowers_distance(const int x1, const int y1, int float x2, int float y2) - Расчёт расстояния между двумя соседними смотровыми башнями.
  • float get_boat_distance(const float d, const int alpha, const int beta) - Расчёт дистанцию корабля до острова.

Task 2.1: Degrees and Radians

Напишите функцию float to_radians(const int angle) с параметром:

  • const int angle - представляет количество градусов(угол), это значение из интервала (0,360).

Функция должна вернуть значение угла в радианах. Если параметр представляет неправильное значение, функция вернёт -1.

Пример использования функции:

printf("%.3f\n", to_radians(45));
// prints: 0.785
printf("%.3f\n", to_radians(0));
// prints: -1.000

Task 2.2: Distance between Watchtowers

Напишите функцию float get_watchtowers_distance(const int x1, const int y1, const int x2, const int y2) с параметрами:

  • const int x1 - Представляет координату x башни A, это значение из интервала <0,1000>.
  • const int y1 - Представляет координату y башни A, это значение из интервала <0,1000>.
  • const int x2 - Представляет координату x башни B, это значение из интервала <0,1000>.
  • const int y2 - Представляет координату y башни B, это значение из интервала <0,1000>.

Функция вернёт значение, соответствующее расстоянию между смотровыми башнями на основе их координат. В случае, если хотя бы один из параметров неверный, функция возвращает -1.

Пример использования функции:

printf("%.2f\n", get_watchtowers_distance(76,316,57,516));
// prints: 200.90
printf("%.2f\n", get_watchtowers_distance(252,240,889,104));
// prints: 651.36
printf("%.2f\n", get_watchtowers_distance(152,253,89,1104));
// prints: -1.00

Task 2.3: Boat Distance

Напишите функцию float get_boat_distance(const float d, const int alpha, const int beta) с параметрами:

  • const float d - представляет расстояние между смотровыми башнями, это значение из интервала <0,1000>.
  • const int alpha - представляет угол между кораблём врага и башней B, это значение из интервала (0,90).
  • const int beta - представляет угол между кораблём врага и башней A, это значение из интервала (0,90).

Функция вернёт значение, соответствующее расстоянию корабля неприятеля от острова на основе расстояния между двумя смотровыми башнями, углов между кораблем и башнями. В случае, если хотя бы один из параметров неверный, функция вернёт -1.

Пример использования функции:

printf("%.2f\n", get_boat_distance(200.9,17,17));
// prints: 30.71
printf("%.2f\n", get_boat_distance(70.34,25,8));
// prints: 7.60
printf("%.2f\n", get_boat_distance(152.2,20,90));
// prints: -1.00

Program Input

Программа на входе получит координаты обеих башен A и B, углы между соседними башнями и кораблём Alpha и Beta. Для данных правдиво:

  • Начальная точка координат (точка (0,0)) находится в нижнем левом углу (юго-запад).
  • Координаты башен (x,y) могут быть только в интервале <0,1000>.
  • y координаты башен не могут равняться.
  • Углы между башнями и кораблём Alpha и Beta могут быть только значениями из интервала (0,90).

Program Output

Вывод программы будет следующим:

  • Расстояние корабля до острова - число с точностью в 2 знака после запятой.
  • Координаты корабля (x,y) (могут быть представлены подобно координатам башен только числами из интервала <0,1000>).

В случае, если хоть одно из условий не соблюдается, программа выпишет на экран -1.

Program Examples

Ниже в тексте приведены примеры использования программы. Текст, выделенный жирным шрифтом представляет ввод пользователя. Строка, начинающаяся знаком $, представляет командную строку.

Формат ввода/вывода представлен ниже:

$ ./triangulation
Ax Ay Alpha
Bx By Beta
d Cx Cy

Ax и Ay представляют координаты первой башни A. Bx и By представляют координаты второй башни B. Cx и Cy представляют координаты корабля, округленные до сотых.

Угол Alpha представляет угол с перспективы башни A между башней B и кораблём неприятеля C. Угол Beta представляет угол с перспективы башни B между башней A и кораблём неприятеля C.

Значение d представляет расстояние корабля до берега (линия между A и B) округленное до сотых.

Ниже примеры использования программы:

$ ./triangulation
76 316 17
57 516 17
30.71 97.07 418.90
$ ./triangulation
252 240 25
889 104 8
70.34 414.21 277.29
$ ./triangulation
152 253 125
89 1104 89
-1

Comment

Вывод программы заканчивается символом перевода строки '\n'.

Comment

Для лучшей визуализации задачи рекомендуем использовать программу GeoGebra. Она поможет вам быстрее проверить правильность вашей реализации.

Assessment

За полностью правильное решение задания можно получить max. 3 балла. Для успешного тестирования вашей реализации очень важно, чтобы вывод вашей программы был одинаковый с выводом, описанный заданием.

Warning

Оценивается каждый символ!

Comment

Вывод программы заканчивается символом перевода строки '\n'.

Task 3: Oh, Math Again...

Хоть у программы не будет какого-то конкретного вывода на экран, вам следует написать 2 функции:

  • short int gcd(const short int a, const short int b) - найдёт наименьший общий делитель a и b.
  • long int lcm(const int a, const int b) - найдёт наименьший общее кратное a и b.

Task 3.1: Greatest Common Divisor

Напишите функцию short int gcd(const short int a, const short int b) с параметрами:

  • const short int a - ненулевое число из интервала <-1000,1000>
  • const short int b - ненулевое число из интервала <-1000,1000>

Функция вернёт наибольший общий делитель чисел. Возвращает -1, если:

  • Число a равняется 0 или число b равняется 0
  • Число a меньше -1000 или больше чем 1000
  • Число b меньше -1000 или больше чем 1000

Пример использования функции:

printf("%d\n", gcd(16,12));
// prints: 4
printf("%d\n", gcd(-21,-35));
// prints: 7
printf("%d\n", gcd(2,0));
// prints: -1

Task 3.2: Lowest Common Multiple

Напишите функцию long int lcm(const int a, const int b) с параметрами:

  • const int a - положительное число из интервала <1,10000>
  • const int b - положительное число из интервала <1,10000>

Функция возвращает значение, соответствующее наибольшему общему кратному чисел a и b. Возвращает -1, если:

  • Число a меньше 0 или Число b меньше 0
  • Число a больше 10000 или Число b больше 10000

Пример использования функции:

printf("%d\n", lcm(3,4));
// prints: 12
printf("%d\n", lcm(16,12));
// prints: 48
printf("%d\n", lcm(6,0));
// prints: -1

Assessment

За полностью правильное решение задания можно получить max. 3 балла. Количество баллов зависит от результатов тестов, которые пройдёт ваша реализация программы, будут проверяться:

  • Вывод вашей программы с эталонным.
  • Сама функциональность (отдельных функций).

Warning

Оценивается каждый символ!

Comment

Вывод программы заканчивается символом перевода строки '\n'.

PMinimal Requirements to Succeed

  • Проекта должен быть сдан не позднее дедлайна на git репозиторий git.kpi.fei.tuke.sk (см. ниже).
  • Во время компиляции недопустимы любые ошибки! Сборка проекта будет проводиться компилятором gcc со следующими аргументами:
gcc -std=c11 -Werror -Wall -lm 
  • В конечной реализации не должно быть ни одной глобальной переменной.

Project Submission

Задание сдайте не позднее 25.11.2018. Последние тесты будут запущены в полночь.

Задание сдаётся с помощью системы контроля версий Git на сервере git.kpi.fei.tuke.sk.

Название проекта должно быть точно в виде: zap-2018.

Проект должен сохранять иерархию файлов:

.
├── ps5
│   ├── common.c
│   ├── tesco.c
│   └── triangulation.c
└── README

Отдельные файлы означают:

  • README соотв. README.md - файл, в котором указана группа, которую вы посещаете на практических занятиях:
GROUP : C1
  • /ps5/tesco.c - Код программы для задания - Касса самообслуживания.
  • /ps5/triangulation.c - Код программы для задания - Враг на горизонте!.
  • /ps5/common.c - Код программы для задания - Ох, снова эта математика...

Warning

Важно, чтобы иерархия файлов соответствовала предписанной. Если какой-то из файлов находится в другом каталоге, это будет считаться ошибкой.

Warning

Соблюдайте регистр названия файлов README соотв. README.md.

Comment

Если в каталогах будут находиться другие файлы, ошибкой это считаться не будет.

Assessment and Testing

Задание оценивается max. 10 баллами, из них max. 4 балла за первое задание, max. 3 балла за второе и max. 3 балла третье. Количество баллов будет зависеть от результатов тестов, будут проверяться:

  • Иерархия файлов (находятся ли в репозитории все нужные файлы).
  • Функционал вашей реализации.

Сборка будет осуществляться с помощью компилятора gcc со следующими параметрами:

gcc -std=c11 -Werror -Wall -lm

Ошибкой будет считаться:

  • Использование глобальной переменной.
  • Ошибки во время компиляции (предупреждения трактуются как ошибки).
  • Если ваша реализация не пройдёт каким-то из тестов.

Тестирование проектов будет проходить каждые 3 часа, а именно: 0300, 0600, 0900, 1200, 1500, 1800, 2100 и 2400.

Проекты пройдут проверку на плагиат, поэтому руководствуйтесь правилами этического кодекса! В случае выявления плагиата, вы рискуете быть выгнанными с предмета!

Additional Resources

  1. What Every Computer Scientist Should Know About Floating-Point Arithmetic