Programarea Calculatoarelor, seria CC

Ultima modificare: 20 Noiembrie 2010, ora 18:30

Ultima versiune de Simulator: 1.1

Tema 2

Data publicării: Joi, 18 Noiembrie 2010, ora 12:00

Deadline: Duminică, 5 Decembrie 2010, ora 23:55

Precizări:


CORECTAREA temei se va face cu ajutorul unui checker grafic pe care il puteți downloada de la această adresă. Pentru a putea rula checkerul, trebuie să aveți instalată o mașină virtuală Java. În cazul improbabil în care nu aveți deja Java instalat, îl puteți instala astfel:

PENTRU TESTAREA soluției voastre, veți avea nevoie de hărți. Câteva exemple de hărți se pot downloada de la această adresă, dar vă recomand să încercați să vă desenați și hărți proprii [ Bonus 10p :) ].

UN SCURT TUTORIAL despre temă cu explicații despre checker și sfaturi despre rezolvare pe care vă sfătuiesc să îl urmăriți se găsește mai jos (sau aici):


Introducere

După ce a fost eliberat de către băștinașii de pe insulă, Marcvs, fiind un spirit întreprinzător, a decis să intre în afaceri cu ei. După ce au proiectat împreună plantația de cafea și au intrat în producție, și-au dat seama repede că au nevoie de un sistem eficient de transport.

Șefii de trib l-au recomandat pe un contractor local, numit Julien, care a proiectat o rețea de străzi prin plantație. Pe aceste străzi vor circula vehicule conduse de angajați băștinași (vezi Figura 1).


Figura 1. Băștinaș care operează vehicule foarte periculoase.

Marcvs, însă, ține foarte mult la viața localnicilor și îl suspectează pe Julien că a proiectat o rețea de transport în care accidentele sunt inevitabile. El vrea să îi convingă pe șefii de trib de intențiile egoiste și non-etice ale lui Julien, dar pentru asta are nevoie de dovezi concrete.

De aceea, el vă cere să scrieți un program care simulează traficul pe plantație, în speranța că va putea demonstra că accidentele sunt inevitabile și viețile șoferilor au fost puse în pericol de munca neglijentă a lui Julien.


Taskul 1: Input & Output [20 puncte]

Se știe că plantația are formă dreptunghiulară și măsoară 20km lățime cu 30km lungime. Mai mult, harta plantației este împărțită în parcele pătrate cu latura de 1km (de unde rezultă că întreaga plantație se poate reprezenta sub forma unei matrici de 20 x 30 parcele).

Fiecare parcelă este complet descrisă printr-un număr natural de maxim 4 cifre.

Cerințe:

Pentru a rezolva acest task, este necesar să folosiți redirectări din linia de comandă. Explicații detaliate despre cum să faceți asta se găsesc în următorul tutorial video:

  1. Implementați o funcție care citește de la tastatură harta plantației (o matrice 20 x 30 de numere întregi pozitive, separate prin spații). Funcția trebuie să respecte următorul antet:

    void citesteHarta(int** harta);

  2. Implementați o funcție care afișează pe ecran harta plantației (o matrice 20 x 30 de numere întregi pozitive, separate prin spații). Funcția trebuie să respecte următorul antet:

    void scrieHarta(int** harta);


    Se va trece la rând nou după fiecare linie din matrice. După afișarea întregii matrice se va lăsa un rând liber.

  3. Scrieți funcția main() care, folosind funcțiile de mai sus, citește de la tastatură harta inițială a matricii și o afișează înapoi pe ecran.

Exemplu:

Intrare (island.map)
03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
03 03 03 03 03 03 02 02 02 02 02 03 02 02 02 02 03 03 03 03 03 03 02 02 02 02 03 03 03 03
03 03 03 03 02 02 02 01 01 01 02 02 02 01 01 02 02 03 03 03 03 02 02 01 02 02 02 02 03 03
03 03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 02 02 03 03 02 02 01 01 01 02 02 02 02 03
03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 02 02 01 01 01 01 01 02 02 02 03
03 03 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 03 03
03 03 02 02 02 02 01 01 30 40 40 40 40 40 40 40 40 40 40 40 40 40 40 01 01 01 01 02 03 03
03 02 02 02 01 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 01 02 02 03
03 02 02 02 02 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 02 02 02 03
03 03 03 02 02 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 01 02 02 03
03 03 03 02 02 02 01 01 30 01 01 01 01 110 01 01 01 01 10 01 01 01 10 01 01 01 02 02 02 03
03 03 03 03 02 02 01 01 30 40 40 40 440 10 40 40 440 40 10 40 40 40 40 01 01 01 02 02 03 03
03 03 03 02 02 02 01 01 30 01 01 01 01 10 01 01 01 01 01 01 01 01 10 01 01 01 02 03 03 03
03 03 03 02 02 02 02 01 30 01 01 01 01 10 01 01 01 01 01 01 01 01 10 01 01 01 02 02 03 03
03 03 03 03 03 02 02 01 20 20 20 20 20 20 220 20 20 20 20 20 20 20 10 02 02 02 02 03 03 03
03 03 03 03 03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 02 02 03 03 03 03
03 03 03 03 02 02 02 02 02 02 02 02 02 02 02 02 01 01 01 01 02 02 02 02 02 03 03 03 03 03
03 03 03 03 03 03 02 02 03 03 03 02 02 02 02 02 02 02 02 02 02 02 02 03 03 03 03 03 03 03
03 03 03 03 03 03 03 03 03 03 03 03 03 03 02 02 03 03 03 02 02 02 03 03 03 03 03 03 03 03
03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
Ieșire (oglindește intrarea - atenție la linia liberă de la sfârșit)
03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
03 03 03 03 03 03 02 02 02 02 02 03 02 02 02 02 03 03 03 03 03 03 02 02 02 02 03 03 03 03
03 03 03 03 02 02 02 01 01 01 02 02 02 01 01 02 02 03 03 03 03 02 02 01 02 02 02 02 03 03
03 03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 02 02 03 03 02 02 01 01 01 02 02 02 02 03
03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 02 02 01 01 01 01 01 02 02 02 03
03 03 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 03 03
03 03 02 02 02 02 01 01 30 40 40 40 40 40 40 40 40 40 40 40 40 40 40 01 01 01 01 02 03 03
03 02 02 02 01 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 01 02 02 03
03 02 02 02 02 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 02 02 02 03
03 03 03 02 02 01 01 01 30 01 01 01 01 10 01 01 01 01 10 01 01 01 10 01 01 01 01 02 02 03
03 03 03 02 02 02 01 01 30 01 01 01 01 110 01 01 01 01 10 01 01 01 10 01 01 01 02 02 02 03
03 03 03 03 02 02 01 01 30 40 40 40 440 10 40 40 440 40 10 40 40 40 40 01 01 01 02 02 03 03
03 03 03 02 02 02 01 01 30 01 01 01 01 10 01 01 01 01 01 01 01 01 10 01 01 01 02 03 03 03
03 03 03 02 02 02 02 01 30 01 01 01 01 10 01 01 01 01 01 01 01 01 10 01 01 01 02 02 03 03
03 03 03 03 03 02 02 01 20 20 20 20 20 20 220 20 20 20 20 20 20 20 10 02 02 02 02 03 03 03
03 03 03 03 03 02 02 02 01 01 01 01 01 01 01 01 01 01 01 01 01 01 02 02 02 02 03 03 03 03
03 03 03 03 02 02 02 02 02 02 02 02 02 02 02 02 01 01 01 01 02 02 02 02 02 03 03 03 03 03
03 03 03 03 03 03 02 02 03 03 03 02 02 02 02 02 02 02 02 02 02 02 02 03 03 03 03 03 03 03
03 03 03 03 03 03 03 03 03 03 03 03 03 03 02 02 03 03 03 02 02 02 03 03 03 03 03 03 03 03
03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03


Taskul 2: Mișcarea vehiculelor - primul pas [+30 puncte]

După ce v-ați asigurat că funcțiile de I/O funcționează corect, este momentul să precizăm cum este codificată harta. Fiecare element din matrice este un număr natural pozitiv de maxim 4 cifre, cu semnificațiile după cum urmează:

ABCD (de exemplu: 0120)

Cifra unităților semnifică tipul de teren de pe hartă și poate fi:

  • 0 - drum prin plantație
  • 1 - arbore de cafea
  • 2 - iarbă
  • 3 - apă

Cifra zecilor semnifică tipul de viraj obligatoriu de pe o porțiune de drum:

  • 0 - parcela nu este drum prin plantație sau nu este precizat un viraj obligatoriu
  • 1 - obligatoriu avansare spre Nord
  • 2 - obligatoriu avansare spre Est
  • 3 - obligatoriu avansare spre Sud
  • 4 - obligatoriu avansare spre Vest

Cifra sutelor semnifică tipul de vehicul aflat pe o porțiune de drum:

  • 0 - parcela nu este drum prin plantație sau momentan nu există nici un vehicul acolo
  • 1 - vehicul orientat spre Nord
  • 2 - vehicul orientat spre Est
  • 3 - vehicul orientat spre Sud
  • 4 - vehicul orientat spre Vest

Cifra miilor semnifică dacă pe respectiva parcelă a avut loc vreun accident:

  • 0 - pe parcelă nu a avut loc nici un accident
  • 1 - pe parcelă a avut loc un accident

De exemplu, matricea din exemplul de la Taskul 1 codifică de fapt următoarea hartă inițială:

La fiecare pas, mașinile se mișcă după următoarele reguli:

Cerință:

Adăugați funcționalitatea de a simula un singur pas al vehiculelor aflate în deplasare, și afișați pe ecran codificarea pentru noua stare a hărții (folosind funcția de afișare de la Task-ul 1).

Pentru acest Task, se garantează că:

  • Fiecare parcelă de drum pe care se află o mașină are viraj obligatoriu.
  • În urma acestui pas, nu se vor ciocni mașini.
  • În urma acestui pas, nici o mașină nu va ieși în decor.

  • Taskul 3: Mișcarea vehiculelor - primul pas, fără direcții [+20 puncte]

    După ce v-ați asigurat că primul pas este simulat corect în condițiile de la Task-ul 2, este timpul să mai înlăturăm o garanție: existența virajelor obligatorii.

    Cerință:

    Modificați funcționalitatea de a simula un singur pas al vehiculelor aflate în deplasare, astfel încât să nu mai contați pe faptul că fiecare parcelă de drum conține viraje obligatorii. Prin parcelele de drum care nu conțin viraje obligatorii, mașinile se deplasează fără a-și schimba direcția de mers.

    Pentru acest Task, se garantează în continuare că:

  • În urma acestui pas, nu se vor ciocni mașini.
  • În urma acestui pas, nici o mașină nu va ieși în decor.

  • Taskul 4: Mișcarea vehiculelor - primul pas, cu explozii :D [+20 puncte]

    După ce v-ați asigurat că primul pas este simulat corect în condițiile de la Task-ul 3, este timpul să luăm în considerare și situațiile în care se produc accidente.

    Cerință:

    Modificați funcționalitatea de a simula un singur pas al vehiculelor aflate în deplasare, astfel încât să luați în considerare și situațiile în care se produc accidente:

    • Mașina iese în decor.
    • Mașina ajunge în aceeași parcelă de drum simultan cu cel puțin o altă mașină.
    • Mașina ajunge intr-o parcelă de drum în care deja exista un accident.

    Pentru acest Task, vi se garantează în continuare că:

  • Nu vor exista parcele cu drum pe granița hărții (adică nici o mașină nu poate ieși în afara matricii fără să facă accident și să se oprească).
  • Exemplu (doar grafic):

    Starea inițială

    Mașina de sus va ieși în decor
    După primul pas

    Mașina de sus a ieșit în decor și a făcut accident

    Taskul 5: Mișcarea vehiculelor - 100 de pași [+10 puncte]

    După ce v-ați asigurat că simularea primului pas funcționează corect conform Task-urilor precendente, este timpul să simulăm și următorii 99 de pași.

    Cerință:

    Modificați funcționalitatea programului astfel încât să simuleze primii 100 de pași (101, dacă numărăm și starea inițială de la Taskul 1).

    Pe ecran se va afișa, succesiv, fiecare stare astfel simulată (în total, 101 matrici, daca luăm în considerare și afișarea de la Task-ul 1).

    Pentru acest Task, vi se garantează în continuare că:

  • Nu vor exista parcele cu drum pe granița hărții (adică nici o mașină nu poate ieși în afara matricii fără să facă accident și să se oprească).

  • Bonus: Proiectare harta nouă [+10 puncte]

    Pentru ca învingerea lui Julien să fie deplină, creați un nou proiect de plantație și proiectați un sistem de trafic prin acesta.

    Cerință:

    Descrieți o hartă nouă pentru a o folosi la simulat (de exemplu, o puteți scrie în vim/gedit).

    Harta va respecta convențiile de codificare de la Task-ul 2, și va fi salvată într-un fișier denumit hartaX.map, unde X este un număr cuprins între 2 și 4 care specifică garanțiile cărui task le respectă harta.

    Harta proiectată poate genera în continuare accidente, dacă harta este proiectată pentru a testa Task-ul 4 (daca X este 4).