Problem Set 2: Numbers, Arrays

Úloha 1: Lift a Car

Už aj malé deti vedia, že ak sa chcú hojdať na hojdačke, tak ťažšie dieťa si musí sadnúť bližšie ku stredu. Z fyziky vieme, že ak majú byť deti na hojdačke v rovnováhe, musí platiť:

F1 * r1 = F2 * r2

Silu páky si uvedomil aj Archimedes a prehlásil: Dajte mi pevný bod vo vesmíre a pohnem Zemou.

Pozrime sa na realizáciu podobného pokusu v reálnych podmienkach. Predpokladajme, že máme železnú tyč dlhú 2 m. Kde by sme mali umiestniť onen pevný bod, ak by sme chceli len tiažou svojho tela nadvihnúť osobné auto?

r1 + r2 = 2 => r1 = 2 – r2
m1 * r1 = m2 * r2
...
r2 = 2 * m1 / (m1 + m2)

Vytvorte funkciu float lift_a_car(const int stick_length, const int human_weight, const int car_weight) s troma parametrami:

• const int stick_length - Dĺžka tyče
• const int human_weight - Hmotnosť človeka
• const int car_weight - Hmotnosť auta

Funkcia pre zadané parametre vypočíta, na ktorom mieste je potrebné podložiť tyč tak, aby človek len tiažou vlastného tela nadvihol auto. Funkcia vráti hodnotu s výsledkom zaokrúhleným na 2 desatinné miesta.

Príklad použitia funkcie

printf("%.4f\n", lift_a_car(2, 80, 1400));
// prints: 0.1100
printf("%.4f\n", lift_a_car(4, 90, 1650));
// prints: 0.2100

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 2: Unit Price for Toilet Paper

Pri nákupoch sa často rozhodujeme podľa ceny. Obchodníci by mali pri každom výrobku uvádzať jednotkovú cenu, aby sme si vedeli porovnať výhodnosť rôznych balení. Ak si začneme všímať tieto jednotkové ceny, čoskoro zistíme, že niekedy sú ťažko využiteľné. Niekde obchodník prepočítal cenu na litre a inde na kilogramy. Niekde aj prepočítal cenu na rovnaké jednotky, napr. kusy, ale každý kus má inú veľkosť.

Navrhnime vhodnú jednotku a spôsob prepočítavania pri toaletnom papieri. Niektoré balenia obsahujú viac kotúčov papiera, inde sa predáva len jeden kotúč. Pri niektorých kotúčoch je uvedený počet útržkov, inde zase celková dĺžka v metroch.

Ako jednotku môžeme uvažovať 1 útržok. Keďže cena útržku by bola príliš nízka, uvažujme cenu za 100 útržkov. Ostáva nám zistiť, ako prepočítať metre na útržky. Jednoduchým premeraním zistíme, že 10 útržkov má dĺžku asi 1.17 metra.

Vytvorte funkciu float unit_price(const float pack_price, const int rolls_count, const int pieces_count) s troma parametrami:

• const float pack_price - Cena balenia
• const int rolls_count - Počet kotúčov
• const int pieces_count - Množstvo útržkov v kotúči

Funkcia pre zadané parametre vypočíta, aká je jednotková cena pre 100 ks útržkov. Funkcia vráti hodnotu s výsledkom zaokrúhleným na 2 desatinné miesta.

Príklad použitia funkcie

printf("%.4f\n", unit_price(4.79, 16, 150));
// prints: 0.2000
printf("%.4f\n", unit_price(5.63, 20, 200));
// prints: 0.1400

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 3: ATM

Bankomat dokáže vydať bankovky v nominálnej hodnote 10, 20, 50, 100 a 200 €. Pre výber hotovosti z bankomatu, je potrebné vedieť počet bankoviek, ktoré bankomat vydá. Avšak softvér Vášho bankomatu ešte nemá túto funkciu naprogramovanú.

Preto je Vašou úlohou naprogramovať funkciu int bank_notes(const int price) s jednym parametrom:

• const int price - Požadovaná suma výberu

Funkcia pre zadaný parameter vypočíta, počet potrebných bankoviek na výdaj. Funkcia vráti hodnotu počtu bankoviek určných na výber, alebo vráti hodnutu -1 v prípade, že výber požadavanej sumy v hotovosti nie je možný.

Príklad použitia funkcie

printf("%d\n", bank_notes(540));
// prints: 5
printf("%d\n", bank_notes(5));
// prints: -1

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 4: Euler's Totient Function

Eulerova funkcia totientu, označovaná ako φ (fi), je matematická funkcia, ktorá počíta kladné celé čísla menšie alebo rovné zadanému kladnému číslu n, ktoré sú relatívne prvočíselné s číslom n. Dve čísla sú relatívne prvočíselné, ak ich najväčší spoločný deliteľ je 1. Inými slovami, Eulerova funkcia totientu φ(n) počíta počet kladných celých čísel menších alebo rovných n, ktoré nemajú žiadne spoločné delitele (okrem 1) s číslom n.

Vzorec pre Eulerovu funkciu totientu:

φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

Kde:

• φ(n) je hodnota Eulerovej funkcie totientu pre n.
• n je zadané kladné celé číslo.
• p1, p2, ..., pk sú odlišné prvočíselné faktory čísla n.

Naprogramujte funkciu int euler(const int n), ktorá určí hodnotu totientu pre n.

Funkcia má jeden parameter:

• const int n - Celé kladné číslo

Príklad použitia funkcie

printf("%d\n", euler(6));
// prints: 2
printf("%d\n", euler(12));
// prints: 4

Hodnotenie

Táto úloha je za max. 1.5 bodov.

Úloha 5: Missing Number

Pole obsahuje n rôznych čísel z množiny 0, 1, 2, ..., n. Čísla tvoria postupnosť, ktorá nemusí byť v správnom poradí.

Práve jedno číslo v tomto poli chýba. Vašou úlohou je pomocou funkcie int find_missing_number(const int n, const int arr[]) nájsť chyjúce číslo.

Funkcia má na vstupe 2 paramatre:

• const int n - Počet prvkov poľa.
• const int arr[] - Pole obsahujúce hodnoty postupnosti.

Funkcia vráti hodnotu chybajúceho čísla v postupnosti.

Príklad použitia funkcie

int input_array[] = {3,0,1};
printf("%d\n", find_missing_number(3,input_array));
// prints: 2

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 6: Pascal's Triangle

Na obrázku je časť Pascalovho trojuholníka. Pascalov trojuholník sa v matematike preslávil vďaka svojej symetrii a rôznym skrytým vzťahom. Blaise Pascal si v roku 1653 myslel to isté a poznamenal, že by ich pravdepodobne nevedel opísať v jednej práci. Množstvo prepojení Pascalovho trojuholníka s inými vetvami matematiky urobilo z neho posvätný matematický objekt.

Pascalova schéma funguje zhora. Začneme s jednou jednotkou (riadok č. 0) a pod ňu napíšeme dve jednotky zľava a sprava (riadok č. 1). Ďalšie riadky zostrojíme tak, že na oba okraje napíšeme 1 a stredné čísla dostaneme ako súčet dvojice čísel v predošlom riadku priamo nad miestom, na ktorom práve sme.

Vašou úlohou je vypočítať súčet mocnín všetkých koeficientov vo vybranom riadku, ak riadky sú číslované od 0.

Vytvorte funkciu unsigned long sum_squared(const int line) s parametrom:

• const int line - Kladné celé číslo, ktoré vyjadruje riadok v Pascalovom trojuholníku

Funkcia vráti súčet druhých mocnín všetkých koeficientov v zadanom riadku Pascalovho trojuholníka.

Príklad použitia funkcie

printf("%lu\n", sum_squared(1));
// prints: 2
printf("%lu\n", sum_squared(4));
// prints: 70
printf("%lu\n", sum_squared(33));
// prints: 7219428434016265740

Hodnotenie

Táto úloha je za max. 1.5 bodov.

Úloha 7: Min-and-Max Price

Denis si chce zarobiť peniaze a dostal veľmi jednoduchý nápad - bude predávať veci. Keďže chce mať nejaký zisk, potrebuje veci nakupovať za najnižšiu možnú cenu a predávať za najvyššiu.

Vašou úlohou je nájsť najnižšiu a najvyššiu cenu v poli, ktoré je na vstupe.

Úloha 7.1: Min

Vytvorte funkciu int array_min(const int input_array[], const int array_size) s dvoma parametrami:

• const int input_array[] - Vstupné pole obsahujúce celé čísla
• const int array_size - Veľkosť vstupného poľa, vyjadrená počtom prvkov v poli

Funkcia vráti najmenšiu hodnotu, ktorá sa nachádza medzi prvkami vstupného poľa. Avšak ak je vstupné pole NULL, funkcia vráti hodnotu -1.

Úloha 7.2: Max

Vytvorte funkciu int array_max(const int input_array[], const int array_size) s dvoma parametrami:

• const int input_array[] - Vstupné pole obsahujúce celé čísla
• const int array_size - Veľkosť vstupného poľa, vyjadrená počtom prvkov v poli

Funkcia vráti najväčšiu hodnotu, ktorá sa nachádza medzi prvkami vstupného poľa. Avšak ak je vstupné pole NULL, funkcia vráti hodnotu -1.

Príklad použitia funkcií

int input_array[] = {1,2,3,4,5};
printf("%d\n", array_min(input_array, 5));
// prints: 1
printf("%d\n", array_max(input_array, 5));
// prints: 5
printf("%d\n", array_max(NULL, 5));
// prints: -1

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 8: Factor Counter

Počet prvočíselných faktorov (prvočíselných deliteľov) závisí na samotnom čísle a jeho rozklade na prvočísla. Všeobecne platí, že každé kompozitné číslo má jedinečný rozklad na prvočíselné faktory. Počet prvočíselných faktorov daného čísla bude rovný počtu rôznych prvočísel, ktoré ho tvoria.

Pre získanie počtu jedinečných prvočíselných faktorov daného čísla je potrebné nájsť jeho rozklad na prvočíselné faktory. Napríklad, ak máme číslo 12, jeho rozklad na prvočíselné faktory je 2 a 3. Tu vidíme, že 12 má 2 rôzne prvočíselné faktory: 2, 2 a 3. Čiže počet rôznych faktorov je 2.

Naprogramujte funkciu int factorize_count(const int n), ktorá určí počet rôznych faktorov.

Funkcia má jeden paramater:

• const int n - Vstupné číslo určené na rozklad.

Príklad použitia funkcie

printf("%d\n", factorize_count(12));
// prints: 2

Hodnotenie

Táto úloha je za max. 1 bod.

Úloha 9: Marathon

Vo Vašom meste sa koná výnimočná bežecká súťaž, ktorá tu nebola nikdy predtým. Preto mesto nemá k dispozícii pódium pre víťazov súťaže. Mesto si tak najalo výrobcu pódií pre súťaže, aby im také pódium vyrobil na mieru. Požiadavky na pódium sú:

• Prvá priečka musí byť v strede a musí byť najvyššia.
• Druhá priečka musí byť naľavo a musí byť nižšia ako prvá priečka, ale vyššia ako tretia priečka. Jej výška je čo najbližšia k prvej priečke.
• Tretia priečka musí byť napravo a musí byť zo všetkých priečok najnižšia.

Keďže prírodné zdroje a materiály na výrobu sú cenné, tak nemôže vzniknúť žiadny odpad.

Vašou úlohou je naprogramovať funkciu void podium(const int n, int arr[]), ktorá rozdelí kváder materiálu tak, aby spĺňal podmienky na výrobu.

Funkcia má 2 parametre:

• const int n – celková výška kvádra materiálu
• int arr[] – pole o veľkosti 3 určené na zápis jednotlivých veľkostí priečok v správnom poradí

Funkcia zapíše do poľa int arr[] výšky priečok v správnom poradí.

Príklad použitia funkcie

int heights[3];
int material = 6;
podium(material, heights);

for(int i = 0; i < 3; i++){
    printf("%d ", heights[i]);
}
printf("\n");
// prints: 2 3 1

Hodnotenie

Táto úloha je za max. 1 bod.

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 07.11.2024 (štvrtok). 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-2024-id.

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

.
├── ps2
│   └── arrays.c
└── README

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

• README - Súbor, v ktorom bude uvedená Vaša skupina, ktorú navštevujete na cvičeniach:

GROUP : C1

• /ps2/arrays.c - Zdrojový kód pre riešenia úloh 1-9

Hodnotenie a testovanie

Za zadanie môžete získať max. 10 bodov, z toho max. 1 bod za úlohu č. 1,2,3,5,7,8 a 9, max. 1.5 bodov za úlohu č. 4 a 6. Ľubovoľné 2 body sa započítajú do zápočtu, ostatné body sa započítajú do skúšky. 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!