Probni ispit: od zahteva do odbrane rešenja

MAPA ČASA

Od ideje do prvog C programa

Na kraju je dovoljno da:

• Iz zahteva izdvoji ulaz, stanje, uslov prekida, obradu i izlaz.
• Napiši ceo program bez oslanjanja na gotov kostur.
• Odredi granice kvadranata matrice za parne i neparne dimenzije.
• Bezbedno pročitaj redove iz fajla i zameni nepoklapajuće pojave podstringa.
• Prepoznaj nedefinisano ponašanje i pogrešan format u starim pitanjima.
• Objasni zašto je svaka važna provera u programu potrebna.

01 · KORAK

Pre koda napravi mapu zadatka

Dugačak tekst zadatka postaje lakši kada ga podelimo na pet stvari: šta ulazi, šta mora da se pamti, šta se računa, kada se obrada završava i šta se prikazuje ili upisuje u fajl. Tek tada biramo petlju, niz, matricu ili pomoćnu funkciju.

Posebno podvuci ograničenja kao što su bez korišćenja niza, neparna dimenzija, nepoklapajuće zamene i obavezno zatvaranje fajla. Ona najčešće određuju samu strukturu rešenja.

ULAZ: podaci i njihove granice
STANJE: vrednosti koje moraju da prežive sledeći korak
PREKID: tačan uslov završetka
OBRADA: funkcije i petlje
IZLAZ: šta se ispisuje i kojim redom

02 · KORAK

Prekid zavisi od dva uzastopna unosa

Za svaki broj računamo i odmah prikazujemo sumu cifara. Unos prestaje kada dva uzastopna broja imaju jednaku sumu cifara, pa između dva čitanja moramo sačuvati prethodnu sumu i podatak da li prethodni broj uopšte postoji.

Niz nije potreban: za sledeći korak dovoljni su prethodna_suma, ima_prethodni, max_suma i broj_max. Trenutni broj se uračunava i prikazuje pre provere prekida, jer je i on deo ulaza.

int s = suma_cifara(x);
printf("%d\n", s);
if (s > max_suma) {
    max_suma = s;
    broj_max = x;
}
if (ima_prethodni && s == prethodna_suma) break;

03 · KORAK

Jedna formula pokriva parne i neparne dimenzije

Gornji deo koristi vrste manje od N/2, a donji počinje od (N+1)/2. Za paran N granice se dodiruju; za neparan N između njih ostaje srednja vrsta koja se preskače. Isto važi za kolone i M.

Rezultat je matrica 2 x 2: svaki element čuva zbir jednog kvadranta. Srednja vrsta ili kolona ne pripada nijednom kvadrantu kada je odgovarajuća dimenzija neparna.

int donja = (n + 1) / 2;
int desna = (m + 1) / 2;

if (i < n / 2 && j < m / 2) q[0][0] += a[i][j];
else if (i < n / 2 && j >= desna) q[0][1] += a[i][j];
else if (i >= donja && j < m / 2) q[1][0] += a[i][j];
else if (i >= donja && j >= desna) q[1][1] += a[i][j];

04 · KORAK

Zamena podstringa traži granice i uredne resurse

Tri reda A, B i C čitamo sa fgets, pa sa svakog uklanjamo završni novi red. Prazan B nije dozvoljen, jer bi se prazan podstring poklapao na svakom mestu i indeks ne bi napredovao smisleno.

Kada B počinje na poziciji i, u rezultat kopiramo C i u ulazu preskačemo ceo B. Kada poklapanja nema, kopiramo jedan znak. Pre svakog kopiranja proveravamo da li ostaje mesto i za završni znak '\0'.

if (strncmp(a + i, b, lb) == 0) {
    if (k + lc >= kap) return 0;
    memcpy(rezultat + k, c, lc);
    k += lc;
    i += lb;
} else {
    if (k + 1 >= kap) return 0;
    rezultat[k++] = a[i++];
}

05 · KORAK

Dobar usmeni odgovor ima pravilo, deklaraciju i mali primer

Prvo odgovori jednom preciznom rečenicom. Zatim napiši deklaraciju ili prototip koji to pravilo pokazuje. Na kraju dodaj najmanji primer kojim se vidi rezultat ili način upotrebe.

Kod pitanja o funkciji navedi šta prima i šta vraća. Kod memorije reci ko zauzima blok, kako se proverava neuspeh i ko ga oslobađa. Kod strukture ili niza pokaži ispravnu deklaraciju i pristup jednom članu.

Pravilo: strstr vraća pokazivač na prvo pojavljivanje ili NULL.
Deklaracija: char *strstr(const char *s, const char *trazeni);
Primer: strstr("algoritam", "rit") pokazuje na "ritam".

06 · KORAK

Odvoji definisan deo od greške u starom pitanju

U staroj zbirci postoje primeri sa pogrešnim formatom, dereferenciranjem pokazivača iza objekta i drugim problemima. Izračunaj samo deo do prve greške, jasno je označi i napiši kako bi ispravan kod izgledao.

Na odbrani svog programa očekuj pitanja o stanju između dva unosa, granicama petlji, kapacitetu stringa, proveri malloc-a ili fopen-a i mestu na kom se poziva free ili fclose. To nisu dodaci rešenju; to su delovi njegove ispravnosti.

printf("%u %u", c, d);       /* unsigned vrednosti */
printf("%p", (void *)p);      /* adresa */
printf("%-8.3f", x);          /* širina 8, tri decimale */

/* *q nije dozvoljeno ako q pokazuje iza poslednjeg objekta. */

ZATVARANJE

Brza provera pre domaćeg

1. Koja je razlika između algoritma i programa?
2. Šta je ime, a šta vrednost promenljive?
3. Kako svojim rečima čitaš x = x + 1?
4. Koji red prvog programa računa, a koji prikazuje rezultat?