Problem Set 5: Tri v jednom

Ciele

  • Precvičiť si prácu s matematickou knižnicou a aritmetickými výrazmi.
  • Porozumieť reprezentácii čísiel v pamäti počítača.
  • Naučiť sa ukončovať programy pomocou rozličných návratových kódov pri rozličných situáciách.

Úloha 1: Samoobslužná pokladňa

Určite ste už videli v Tescu samoobslužné pokladne - priestor, kde bez pokladníka dokážete za nakúpený tovar zaplatiť sami. Pokladňa Vás sama bude pekne navigovať počas celého procesu spočítavania položiek až po zaplatenie hodnoty Vášho nákupu a vrátenia výdavku v prípade, ak ste zaplatili viac.

Samoobslužná pokladňa v Tescu.
Obr. 1: Samoobslužná pokladňa v Tescu.

Nás však nebude zaujímať grafické rozhranie pokladne, ani spôsob, ako vie, či zákazník položku z košíka presunul do baliaceho priestoru, ani načítavanie kódov položiek pomocou čiarového kódu. My sa v tomto prípade plne sústredíme na záverečnú časť - na platbu zákazníka hotovosťou a vydanie výdavku, pokiaľ zákazník zaplatil viac, ako mal.

Váš program na začiatku načíta sumu za celkový nákup. Táto suma bude reprezentovaná kladným desatinným číslom, pre ktoré bude platiť, že 0 < suma < 10000. Suma bude v našich končinách predstavovať sumu v Eurách, ale symbol Eura alebo akákoľvek zmienka o mene sa vo vstupe nachádzať nebude. Ak teda celkovú hodnotu nákupu bude predstavovať suma 97.23 Eur, správny vstup bude reprezentovaný hodnotou 97.23 a nie 9723, ani zaokrúhlene 97 alebo s použitím meny 97.23 Eur.

Ak suma, ktorú bankomat načíta, nie je z uvedeného rozsahu, program okamžite svoju činnosť ukončí s návratovým kódom 1 a hláškou Wrong input!.

Pre peniaze budú v celom programe platiť dve pravidlá:

  • Ak sa jedná o centy (haliere), na obrazovku sa hodnota vypíše s presnosťou na dve desatinné miesta. Hodnota 50 centov sa teda vypíše správne ako 0.50 a nie 0.5 alebo 50 alebo 0.50000.
  • Ak sa nejedná o centy (haliere), na obrazovku sa hodnota vypíše v podobe celého kladného čísla. Hodnota 100 Eur sa teda na obrazovku vypíše správne ako 100 a nie ako 100.00.

Následne začne program načítavať bankovky a mince, ktorými bude chcieť zákazník platiť. Samoobslužná pokladňa zvláda pracovať len s bankovkami a mincami v nasledujúcich nominálnych hodnotách: 100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02 a 0.01. Ako je možné vidieť, pomocou uvedených bankoviek a mincí je možné zaplatiť ľubovoľnú sumu s presnosťou na jeden cent. Poradie vkladaných bankoviek a mincí nie je dôležité a tieto sa môžu ľubovoľný počet krát opakovať (nemusia byť pritom nutne v poradí za sebou).

Načítavanie sa ukončí vtedy, ak pri čítaní vstupu program narazí na hodnotu 0 alebo dôjde k ukončeniu štandardného vstupu (načíta sa hodnota EOF napr. stlačením klávesovej skratky Ctrl+d).

Načítavanie bankoviek od zákazníka.
Obr. 2: Načítavanie bankoviek od zákazníka.

Príkladom takejto postupnosti bankoviek a mincí, ktoré do pokladne vložil zákazník v celkovej hodnote 103.23 Eur, môže vyzerať nasledovne:

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

Rovnakú hodnotu však viete zadať rozličnými inými kombináciami - napríklad tento vstup je rovnako platný:

100 2 1 0.20 0.02 0.01

Program samoobslužnej pokladne následne zistí, či zákazník nezaplatil viac, ako je cena jeho nákupu. Ak áno, začne zákazníkovi vydávať potrebné bankovky a mince tak, aby ich súčet tvoril hodnotu výdavku. Vydávať pritom začne od najväčšej hodnoty potrebnej mince alebo bankovky až po najmenšiu (pokladňa sa teda nesnaží pracovať optimálne a vydať čo najmenší počet mincí a bankoviek). Samozrejme - pokiaľ je potrebné použiť viacero mincí alebo bankoviek rovnakej hodnoty, použijú sa.

Ak teda samoobslužná pokladňa zákazníkovi vráti výdavok v hodnote 15.80 Eur, vydá presne tieto bankovky a mince a presne v tomto poradí:

10 5 0.50 0.20 0.10

Príklady použitia

V nasledujúcom texte sa budú nachádzať príklady použitia programu. Text zvýraznený tučne bude predstavovať vstup od používateľa. Riadok začínajúci znakom '$' bude predstavovať príkazový riadok.

V tomto prípade je hodnota nakúpeného tovaru 37.57 Eur. Zákazník postupne vloží potrebnú sumu, ktorá je vyššia ako hodnota nakúpeného tovaru a samoobslužná pokladňa vydá potrebný výdavok.

$ ./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

Poznámka

Všimnite si, že vstup od používateľa nebol ukončený hodnotou 0. V tomto prípade došlo k ukončeniu štandardného vstupu (napr. stlačením klávesovej skratky Ctrl+d).

Ak zákazník nevloží do pokladne dostatočný počet peňazí, tá vypíše na obrazovku správu 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!

Ak sa zákazník pokúsi platiť bankovkou alebo mincou, ktorá nemá potrebnú nominálnu hodnotu (ani tvar), pokladňa takúto "falošnú" bankovku alebo mincu rozpozná, vypíše na obrazovku správu X is invalid!, kde X predstavuje prvú rozpoznanú falošnú bankovku alebo mincu a skončí s návratovým kódom 1.

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

Upozornenie

V prípade, že falošná bankovka alebo minca bude mať desatinnú časť, vypíše sa na obrazovku aj tá s presnosťou na dve desatinné miesta.
$ ./tesco
Enter value of your bill: 37.57
Insert money for payment: 37.57 99.99 0
35.57 is invalid!

Ak zákazník vloží sumu, ktorá je rovnaká ako hodnota nakúpeného tovaru, pokladňa iba oznámi, že je potrebné vrátiť 0 Eur.

$ ./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

Poznámka

Výstup programu končí novým riadkom '\n'.

Hodnotenie

Táto úloha je za max. 4 body. Pre úspech v testovaní je veľmi dôležité, aby sa výstupy z Vašej implementácie zhodovali s požadovanými výstupmi, nakoľko test bude spočívať v porovnaní Vášho výstupu voči očakávanému výstupu.

Upozornenie

Pri hodnotení sa ráta každý jeden znak!

Poznámka

Výstup programu končí novým riadkom '\n'.

Úloha 2: Nepriateľ na obzore!

Hranice krajiny Sedmikráskovo kopírujú na západe brehy končiace v Ružovom mori. Aby krajina odolala prípadným útokom nepriateľa, sú v rozličných vzdialenostiach na pobreží rozmiestnené rozhľadne. Z nich je možné vidieť na šíre more, ako aj na dve najbližie susedné rozhľadne na pobreží. V prípade, že sa na obzore objaví nepriateľská loď, je možné pomocou triangulácie presne zamerať polohu nepriateľskej lode a odoslať zistené súradnice delostrelectvu do vnútrozemia krajiny.

Pozíciu je možné zístiť vtedy, ak sa nepriateľská loď nachádza v zornom poli medzi dvoma susednými rozhľadňami. Pozorovateľ stojaci v rozhľadni A vie zmerať uhol medzi loďou a susednou rozhľadňou B (pobrežím). Pozorovateľ stojaci v rozhľadni B vie podobne zmerať uhol medzi loďou a susednou rozhľadňou A. Využitím týchto dvoch nameraných uhlov a presnou pozíciou rozhľadne A a rozhľadne B je možné získať presnú pozíciu lode na mori, na čo čaká delostrelectvo vo vnútrozemí.

Obrázok ilustrujúci situáciu na pobreží
Obr. 3: Obrázok ilustrujúci situáciu na pobreží

Vytvorte preto program, ktorý krajine Sedmikráskovo umožní pomocou týchto nameraných údajov získať presnú polohu nepriateľskej lode. Vašou úlohou bude najskôr naprogramovať 3 funkcie:

  • float to_radians(const int angle) - Skonvertuje stupne na radiány.
  • float get_watchtowers_distance(const int x1, const int y1, const int x2, const int y2) - Vypočíta vzdialenosť medzi dvoma hliadkovými vežami.
  • float get_boat_distance(const float d, const int alpha, const int beta) - Vypočíta zdialenosť lode od ostrova.

Úloha 2.1: Stupne a radiány

Naprogramujte funkciu float to_radians(const int angle) s parametrom:

  • const int angle - Vyjadruje počet stupňov (uhol), je to hodnota z intervalu (0,360).

Funkcia vráti hodnotu, ktorá zodpovedá danému uhlu v radiánoch. V prípade, že vstupná hodnota je neplatná, funkcia vráti hodnotu -1.

Príklad použitia funkcie:

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

Úloha 2.2: Vzdialenosť medzi vežami

Naprogramujte funkciu float get_watchtowers_distance(const int x1, const int y1, const int x2, const int y2) s parametrami:

  • const int x1 - Vyjadruje súradnicu x rozhľadne A, je to hodnota z intervalu <0,1000>.
  • const int y1 - Vyjadruje súradnicu y rozhľadne A, je to hodnota z intervalu <0,1000>.
  • const int x2 - Vyjadruje súradnicu x rozhľadne B, je to hodnota z intervalu <0,1000>.
  • const int y2 - Vyjadruje súradnicu y rozhľadne B, je to hodnota z intervalu <0,1000>.

Funkcia vráti hodnotu, ktorá zodpovedá vzdialenosti medzi rozhľadňami na základe ich súradníc. V prípade, že niektorá vstupná hodnota je neplatná, funkcia vráti hodnotu -1.

Príklad použitia funkcie:

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

Úloha 2.3: Vzdialenosť lode

Naprogramujte funkciu float get_boat_distance(const float d, const int alpha, const int beta) s parametrami:

  • const float d - Vyjadruje vzdialenosť medzi rozhľadňami, je to hodnota z intervalu <0,1000>.
  • const int alpha - Vyjadruje uhol medzi nepriateľskou loďou a vežou B, je to hodnota z intervalu (0,90).
  • const int beta - Vyjadruje uhol medzi nepriateľskou loďou a vežou A, je to hodnota z intervalu (0,90).

Funkcia vráti hodnotu, ktorá zodpovedá vzdialenosti nepriateľskej lode od ostrova na základe vzdialenosti medzi vežami a uhlov medzi vežami a loďou. V prípade, že niektorá vstupná hodnota je neplatná, funkcia vráti hodnotu -1.

Príklad použitia funkcie:

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

Vstup programu

Program dostane na vstupe súradnice oboch rozhľadní A a B a uhly medzi susednými rozhľadňami a loďou Alpha a Beta. O týchto údajoch platí:

  • Počiatok súradnicového systému (teda bod (0,0)) sa nachádza vľavo dole (juhozápad).
  • Súradnice rozhľadní (x,y) môžu byť definované len hodnotami z intervalu <0,1000>.
  • U oboch rozhľadní sa súradnice y nemôžu rovnať.
  • Uhly medzi susednými rozhľadňami a loďou Alpha a Beta môžu byť definované len hodnotami z intervalu (0,90).

Výstup programu

Výstupom Vášho programu budú nasledujúce údaje:

  • Vzdialenosť lode od pobrežia (kladné číslo s presnosťou na dve desatinné miesta).
  • Súradnice lode (x,y) (môžu byť definované podobne ako súradnice rozhľadní len číslami z intervalu <0,1000>).

V prípade, že niektorá z podmienok platných pre vstupné hodnoty nebola dodržaná (súradnice rozhľadní alebo jednotlivé uhly boli zadané mimo dovolené rozsahy), vypíšte na výstup iba hodnotu -1.

Príklady použitia programu

V nasledujúcom texte sa budú nachádzať príklady použitia programu. Text zvýraznený tučne bude predstavovať vstup od používateľa. Riadok začínajúci znakom '$' bude predstavovať príkazový riadok.

Formát vstupu a výstupu je reprezentovaný na nasledovnom príklade:

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

Ax a Ay predstavujú súradnice prvej rozhľadne A. Bx a By predstavujú súradnice druhej rozhľadne B. Cx a Cy predstavujú súradnice nepriateľskej lode zaokrúhlené na 2 desatinné miesta.

Uhol Alpha predstavuje uhol odmeraný na rozhľadni A medzi susednou rozhľadňou B a nepriateľskou loďou C. Uhol Beta predstavuje uhol odmeraný na rozhľadni B medzi susednou rozhľadňou A a nepriateľskou loďou C.

Hodnota d predstavuje vzdialenosť lode od pobrežia (úsečkou medzi rozhľadňami A a B) zaokrúhlenú na 2 desatinné miesta.

Nasledujú príklady použitia programu:

$ ./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

Poznámka

Výstup programu končí novým riadkom '\n'.

Poznámka

Pre lepšiu vizualizáciu problému Vám odporúčame nainštalovať si program GeoGebra. Pomôže Vám rýchlejšie si overiť správnosť Vášho riešenia.

Hodnotenie

Za správne vyriešenie úlohy môžete získať max. 3 body. Pre úspech v testovaní je veľmi dôležité, aby sa výstupy z Vašej implementácie zhodovali s požadovanými výstupmi, nakoľko test bude spočívať v porovnaní Vášho výstupu voči očakávanému výstupu.

Upozornenie

Pri hodnotení sa ráta každý jeden znak!

Poznámka

Výstup programu končí novým riadkom '\n'.

Úloha 3: Ach, zasa tá matika...

Program nebude mať žiaden konkrétny výstup na obrazovku, ale Vašou úlohou bude naprogramovať 2 funkcie:

  • short int gcd(const short int a, const short int b) - Nájde najväčší spoločný deliteľ čísel a a b.
  • long int lcm(const int a, const int b) - Nájde najmenší spoločný násobok čísel a a b.

Úloha 3.1: Najväčší spoločný deliteľ

Naprogramujte funkciu short int gcd(const short int a, const short int b) s parametrami:

  • const short int a - Nenulové číslo z intervalu <-1000,1000> (okrem nuly)
  • const short int b - Nenulové číslo z intervalu <-1000,1000> (okrem nuly)

Funkcia vráti hodnotu, ktorá zodpovedá najväčšiemu spoločnému deliteľovi čísel a a b. Avšak funkcia vráti hodnotu -1, ak:

  • Vstupné číslo a je 0 alebo vstupné číslo b je 0
  • Vstupné číslo a je menšie ako -1000 alebo väčšie ako 1000
  • Vstupné číslo b je menšie ako -1000 alebo väčšie ako 1000

Príklad použitia funkcie:

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

Úloha 3.2: Najmenší spoločný násobok

Naprogramujte funkciu long int lcm(const int a, const int b) s parametrami:

  • const int a - Kladné číslo z intervalu <1,10000>
  • const int b - Kladné číslo z intervalu <1,10000>

Funkcia vráti hodnotu, ktorá zodpovedá najmenšiemu spoločnému násobku čísel a a b. Avšak funkcia vráti hodnotu -1, ak:

  • Vstupné číslo a je 0 alebo menej alebo vstupné číslo b je 0 alebo menej
  • Vstupné číslo a je väčšie ako 10000 alebo vstupné číslo b je väčšie ako 10000

Príklad použitia funkcie:

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

Hodnotenie

Za správne vyriešenie úlohy môžete získať max. 3 body. Počet získaných bodov sa bude odrážať od výsledku testov, ktorými Vaše zadanie úspešne prejde. Overovať sa bude:

  • Výstup Vášho programu voči očakávanému výstupu.
  • Funkčnosť Vašej implementácie (jednotlivých funkcií).

Upozornenie

Pri hodnotení sa ráta každý jeden znak!

Poznámka

Výstup programu končí novým riadkom '\n'.

Požiadavky pre úspešné odovzdanie zadania

  • Projekt musí byť odovzdaný včas v git repozitári na adrese git.kpi.fei.tuke.sk (viď nižšie).
  • Počas prekladu nemôže dôjsť ku žiadnej chybe! Projekt sa bude prekladať prekladačom gcc pomocou nasledovných prepínačov:
gcc -std=c11 -Werror -Wall -lm 
  • Vo výslednej implementácii sa nemôže nachádzať žiadna globálna premenná.

Odovzdávanie projektu

Zadanie odovzdajte do 25.11.2018. Posledné testovanie prebehne v tento deň o polnoci.

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri git.kpi.fei.tuke.sk.

Názov Vášho projektu musí byť v tvare: zap-2018.

Projekt musí mať nasledujúcu štruktúru priečinkov a súborov:

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

Význam jednotlivých súborov je nasledovný:

  • README resp. README.md - Súbor, v ktorom bude uvedená Vaša skupina, ktorú navštevujete na cvičeniach:
GROUP : C1
  • /ps5/tesco.c - Zdrojový kód riešenia prvej úlohy - Samoobslužná pokladňa.
  • /ps5/triangulation.c - Zdrojový kód riešenia druhej úlohy - Nepriateľ na obzore.
  • /ps5/common.c - Zdrojový kód riešenia tretej úlohy - Ach, zasa tá matika...

Upozornenie

Je dôležité, aby Vaše súbory zachovali uvedenú štruktúru. Ak sa niektorý zo súborov síce v repozitári nachádza, ale v inom priečinku, bude to považované za chybu a takýto projekt nebude považovaný za správny.

Upozornenie

Pri názvoch priečinkov, súborov a obsahu súboru README resp. README.md záleží na veľkosti písmen!

Poznámka

Ak sa vo Vašom projekte budú nachádzať ďalšie súbory okrem požadovaných, ich existencia nebude považovaná za chybu.

Hodnotenie a testovanie

Za zadanie môžete získať max. 10 bodov, z toho max. 4 body za prvú úlohu, max. 3 body za druhú úlohu a max. 3 body za tretiu úlohu. Počet získaných bodov sa bude odrážať od výsledku testov, ktorými Vaše zadanie úspešne prejde. Overovať sa bude:

  • Štruktúra Vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
  • Funkčnosť Vašej implementácie.

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi:

gcc -std=c11 -Werror -Wall -lm

Za chybu sa bude považovať:

  • Ak vo Vašej implementácii použijete globálnu premennú.
  • Ak počas prekladu dôjde ku chybe (upozornenia sú priamo konvertované na chyby).
  • Ak Vaša implementácia neprejde niektorým z testov.

Testovanie Vašich riešení sa bude vykonávať automaticky každé 3 hodiny a to konkrétne o 0300, 0600, 0900, 1200, 1500, 1800, 2100 a 2400.

Vaše riešenia prejdú kontrolou originality. Preto sa pri práci na Vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je Vaše, môžete byť vylúčení z predmetu!

Doplňujúce zdroje

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