Clasa a 7-a Lecția 1: Reguli de programare în limbajul C și complexități algoritmice

Înregistrare video lecție

Reguli de programare în limbajul C

Variabilele simple nu se inițializează la declarare. Ele se inițializează cât mai aproape de secțiunea de program care le folosește. Cu alte cuvinte orice variabilă se inițializează cât mai jos posibil. De ce? Pentru citibilitatea codului. Imaginați-vă că la linia 300 vedem o instrucțiune a = a + y;. Ne punem întrebarea cu ce valoare a fost inițializată a. Imaginați-vă că trebuie să mergem câteva pagini în sus pentru a constata că variabila a fost inițializată la declarare int a = 1;
Vectorii încep de la 0, nu de la 1. Este o regulă importantă, nu o preferință personală. Avantaje: când folosim modulo, vectori caracteristici, etc.
Vectorii au dimensiunile specificate de cerință. Ei nu se declară int v[10010]. Aceasta se cheamă programare aproximativă și nu este o practică acceptată la nivel de înalt. Dacă la matematică vi s-ar cere să rezolvați ecuația 2 · x = 5 și ați răspunde că x este un număr între doi și trei nu cred că ați putea fi considerați cei mai mari matematicieni ai țării. Programarea aproximativă reprezintă lenea minții. Să punem câteva elemente în plus, în caz că depășesc vectorul. Cine depășește vectorul? Zâna memoriei? Nu, voi. Soluția corectă este să vă corectați gândirea și să vă ascuțiți mintea pentru ca algoritmul vostru să nu depășească vectorul. Altfel veți rămâne incapabili de a scrie programe în lumea reală unde aproximarea nu e acceptabilă.
Reguli de indentare, exemple:
- Indentarea se face la două sau la patru spații. Două sunt suficiente pentru citibilitate. Atenție: setați code::blocks să nu folosească caractere TAB.
- Acolada deschisă se pune pe același rând cu instrucțiunea precedentă.
- Acolada închisă se pune pe rândul următor aliniată sub instrucțiunea de care aparține.
- Dacă după else urmează un if atunci instrucțiunea if se pune imediat după else pe aceeași linie, iar corpul de instrucțiuni aparținând lui else se indentează cu două spații, nu cu patru. Astfel, în cazul unor instrucțiuni de genul if ... else if ... else if ... se evită migrarea codului către dreapta prin indentări inutile.
Fără break / continue / return / goto în interiorul buclelor. Ele distrug programarea structurată și, implicit, zeci de ani de experiență a omenirii.
Folosim for pentru bucle cu număr cunoscut de pași, while în celelalte cazuri. Aceasta este o regulă de programare ordonată, care face codul mai citibil.
Nu avem voie să modificăm variabila de buclă for și nici limita ei de final. Dacă este un ciclu cu număr cunoscut de pași nu avem de ce să modificăm aceste variabile.
Când eliminăm un element din vector micșorăm numărul lui de elemente cu 1 (n--). În felul acesta n continuă să arate numărul de elemente din vector.
Nu aveți voie să aveți warnings, vă pot fi fatale: declarați int main() și folosiți return 0 la final. Eliminați orice alte warnings deoarece majoritatea sunt o problemă reală. Unele concursuri compilează sursa cu opriri la warnings (adică tratează warning-urile ca erori). Unele warnings se referă la variabile neinițializate sau la număr diferit de "%d" versus variabile citite, în fscanf, deci sunt importante. Este obligatoriu să setați Code::Blocks să vă afișeze toate warnings. Pentru aceasta, după crearea proiectului, navigați în meniul Project, submeniul Options. În acea fereastră setați opțiunile -Wall și -O2.
Comentați codul când e ceva complicat, de exemplu o formulă. Scrieți ideea algoritmului, dacă nu e ceva trivial. Nu trebuie să umpleți de comentarii, dar minimal. Mă ajutați mult în corectarea temei.
Denumiți variabilele mai clar. Nu lungi, dar să aibă semnificație: prod, sum, nrcf, etc.
Nu abuzați stegulețele. Exemplu unde nu sunt necesare break sau stegulețe: căutarea unui element e în vectorul v:

i = 0
while ( (i < n) && (v[i] != e) )
    i++;

Folosiți corect fișiere, le deschideți cu fopen, iar la final obligatoriu le închideți cu fclose. În nici un caz nu folosiți freopen.
Folosiți doar funcțiile de intrare/ieșire C, fscanf / fprintf / fgetc / fputc / fgets. Aveți aici un sumar al acestor funcții: instrucțiuni de intrare/ieșire în limbajul C
Nu folosiți funcții gen sort și qsort. Aveți nevoie de dispensă specială ☺

Declararea vectorilor cu inițializare

Precum știm, un vector poate primi valori la declarare. De exemplu:

int dl[4] = { 0, -1, 0, 1 };
int dc[4] = { 1, 0, -1, 0 };

Tabel de descriptori citire/scriere

Dimensiunile diverselor tipuri: în C char are 1 octet, short are 2 octeți, int are 4 octeți, long long are 8 octeți.

Să recapitulăm care sunt descriptorii de citire/scriere folosiți de scanf() și printf() pentru fiecare din tipurile învățate:

Tip variabilă	Bytes	Valori limită	Format folosit (litere)
`char`	1	`-128` ... `127`	`%d` dacă vrem să afișăm numărul întreg `%c` dacă vrem să afișăm caracterul
`unsigned char`	1	`0` ... `255`	`%u` dacă vrem să afișăm numărul întreg `%c` dacă vrem să afișăm caracterul
`short`	2	`-32768` ... `32767`	`%hd`
`unsigned short`	2	`0` ... `65535`	`%hu`
`int`	4	`-2147483648` ... `2147483647` aproximativ două miliarde (2 cu nouă zerouri)	`%d`
`unsigned int`	4	`0` ... `4294967295` aproximativ patru miliarde (4 cu nouă zerouri)	`%u`
`long long`	8	`-9223372036854775808` ... `9223372036854775807` aproximativ 9·10¹⁸ (9 cu 18 zerouri)	`%lld` în GNU/Linux și varena.ro `%I64d` în Windows
`unsigned long long`	8	`0` ... `18446744073709551615` aproximativ 18·10¹⁸ (18 cu 18 zerouri)	`%llu` în GNU/Linux și varena.ro `%I64u` în Windows
`double`	8	valorile minime și maxime nu au aceeași relevanță, dar erorile de reprezentare cresc cu mărimea numărului	`%lf`

Complexități algoritmice

Algoritm	Complexitate timp	Complexitate memorie	Explicații
Descompunerea lui `n` în factori primi	$O (\sqrt{n})$	$O (1)$	Putem testa divizorii până la $O (\sqrt{n})$ . Dacă la final n este diferit de 1, el este un factor prim al lui n la puterea 1.
Ridicare la putere a^b	$O (\log b)$	$O (1)$	Vezi exponențiere logaritmică
Calcul număr de zile între două date calendaristice corecte z1.l1.a1 și z2.l2.a2	$O (1)$	$O (1)$	Partea importantă este calculul numărului de ani bisecți între a1 și a2 în O(1). Ea se reduce la problema calculului numărului de numere divizibile cu k între a și b.
Determinare dacă o secvență de `n` numere de la intrare este bitonă (sau munte)	$O (n)$	$O (1)$	Pe măsură ce citim numerele decidem proprietatea cerută, nu este nevoie să le memorăm.
Determinare corectitudine șir de `n` paranteze închise și deschise	$O (n)$	$O (1)$	Folosim un contor de paranteze deschise și încă neînchise. Nu avem nevoie să memorăm parantezele.
Determinare corectitudine șir de `n` paranteze rotunde, drepte și acolade	$O (n)$	$O (n)$	Similar anterior, dar menținem o stivă de paranteze deschise și încă neînchise, de aceea memoria este liniară.
Determinare corectitudine șir de `n` paranteze de `k` tipuri	$O (n)$	$O (n)$	Similar anterior, trebuie să avem grijă ca atunci când la intrare avem o paranteză închisă să testăm dacă pe stivă se află paranteza deschisă corectă în timp constant. Folosim un vector care pentru fiecare tip de paranteză închisă memorează codul parantezei deschise corespunzătoare.
Inserare element în vector de `n` elemente	$O (n)$	$O (n)$	Elementele de după poziția de inserție trebuie deplasate către dreapta.
Ștergere element din vector de `n` elemente	$O (n)$	$O (n)$	Elementele de după poziția de ștergere trebuie deplasate către stânga.
Interclasare a doi vectori ordonați de `n1`, respectiv `n2` elemente	$O (n 1 + n 2)$	$O (n 1 + n 2)$
Sortare prin selecție a `n` numere - select sort	$O (n^{2})$	$O (n)$
Sortare prin numărare (cu vectori de frecvență) a `n` numere - counting sort	$O (n + X_{m a x})$	$O (X_{m a x})$	$X_{m a x}$ este valoarea maximă dintre numerele de la intrare. Va trebui să parcurgem vectorul de frecvență. La memorie se adaugă n dacă dorim să creăm un vector cu elementele sortate.
Elementul majoritar într-un vector de `n` elemente	$O (n)$	$O (n)$	Algoritmul face două parcurgeri ale elementelor, deci trebuie să le memorăm.
Calculul tuturor numerelor prime de la 1 la `n` folosind ciurul lui Eratostene	$O (n \log \log n)$	$O (n)$
Descompunerea în factori primi a tuturor numerelor de la 2 la `n`	$O (n \log n)$	$O (n)$	Vom calcula un ciur special în care pentru fiecare poziție i calculăm cel mai mare divizor prim al lui i. Pentru a obține descompunerea în factori primi a lui i vom afla divizorii în ordine descrescătoare, împărțind repetat pe i la ciur[i].
Căutare binară în vector ordonat de `n` elemente	$O (\log n)$	$O (n)$
Calculul multiplicității numărului `a` în `n!`	$O (\sqrt{a} + \log a \log n)$	$O (1)$	Termenul $O (\sqrt{a})$ provine din descompunerea în factori primi a lui a. Apoi, pentru fiecare divizor prim al lui a ( $O (\log a)$ ) vom calcula de câte ori se împarte n la acel divizor ( $O (\log n)$ ).

Funcții în limbajul C

Funcțiile permit programelor complicate să fie parcelate în blocuri mici, fiecare din ele fiind mai ușor de scris, citit și modificat (întreținut). Am întâlnit deja funcția main() și am folosit funcții de intrare ieșire precum fscanf() și fprintf(), precum și funcții matematice din bibliotecile standard precum sqrt() sau abs(). Vom vedea în continuare cum putem să scriem propriile noastre funcții.

De ce funcții

Pentru a nu repeta cod.
Pentru organizare, citibilitate, ușurinta înțelegerii codului și întreținerea codului.
Recursivitate.

Sintaxa: cum scriem o funcție

Sintaxa (simplificare)

tip-returnat nume-funcție( tip-1 param-1, tip-2 param-2, ..., tip-n param-n ) { ... declarații variabile ... ... cod funcție ... return valoare-return; // dacă tipul returnat nu este 'void' }

Exemplu

// functie ce returneaza valoarea minima dintre două numere
int min(int a, int b) {
   int rezultat; // declaratie de variabila locala
 
   if (a < b)
      rezultat = a;
   else
      rezultat = b;
 
   return rezultat; 
}

Apelul

O funcție este apelată astfel:

Apelul funcțiilor

Pentru a apela (sau chema) o funcție vom scrie numele funcției urmat, între paranteze, de parametrii ceruți. Ei pot fi expresii, nu doar variabile. Expresiile se vor apela, iar rezultatele lor vor fi depuse, la intrarea în funcție, în variabilele parametru corespunzătoare, conform ordinii din listă. Dacă funcția returnează o valoare ea poate fi folosită sau stocată într-o variabilă:

rez = nume-functie( valoare-1, valoare-2, ..., valoare-n );

Iată un exemplu de folosire a funcției min():

#include <stdio.h>
 
// functie ce returnează valoarea minima dintre două numere
int min(int a, int b) {
   int rezultat; // declaratie de variabila locala
 
   if (a < b)
      rezultat = a;
   else
      rezultat = b;
 
   return rezultat; 
 
int main () {
   int x, y, rez;
 
   x = 200;
   y = 100;
   rez = min( x, y ); // chemam functia pentru a obtine valoarea minima
 
   printf( "Valoarea minima este: %d\n", rez );
 
   return 0;
}

Parametri și valoare returnată

Precum am văzut, o funcție primește o listă de parametri și returnează o valoare. Funcția poate să nu returneze nici o valoare, caz în care tipul returnat va fi declarat ca void, sau "vid" în limba engleză.

Atenție: transmisia parametrilor în funcție se face prin copiere! Aceasta înseamnă că la apelul funcției valorile din apel vor fi atribuite parametrilor ce sunt variabile nou create ce primesc acele valori.

Exemplul 1: ce afișează următorul program:

void inc( int a ) {
  a++;
}

int main() {
  int x;

  x = 0;
  inc( x );
  printf( "%d\n", x );

  return 0;
}

Parametrul a este o variabilă nou creată la intrarea în funcție în care se copiază valoarea variabilei x. Funcția modifică (incrementează) valoarea lui a, dar aceasta nu influențează valoarea lui x, ele fiind variabile diferite. De aceea programul va afișa 0.

Exemplul 2: ce afișează următorul program:

void inc( int a[10] ) {
  a[0]++;
}

int main() {
  int v[10];

  v[0] = 17;
  inc( v );
  printf( "%d\n", v[0] );

  return 0;
}

Surpriză, programul va afișa 18! Elementul zero al vectorului a fost modificat. Și atunci cum rămâne cu transmisia prin copiere? Răspunsul este greu de dat fără cunoștințe despre pointeri. Vectorii sunt ei înșiși adrese de variabile întregi. Parametrul vector se transmite prin copiere, însă ceea ce se copiază este adresa unde se află șirul de întregi ai vectorilor. De aceea modificarea unui vector într-o funcție are ca efect modificarea vectorului.

Pentru moment este îndeajuns să țineți minte că variabilele simple se transmit prin copiere, iar vectorii (matricele, etc) se transmit ca atare, fără a fi copiați.

Cum transmitem corect vectorii unei funcții

Un vector este un tip de date abstract care constă dintr-o pereche (n, v). n este lungimea vectorului (numărul de elememente), iar v este vectorul propriu zis. Ele nu se pot separa. De aceea vom transmite funcției atât vectorul cât și lungimea sa.

Exemplu: suma elementelor unui vector

#include <stdio.h>

int sumaVect( int n, int v[] ) {
  int i, s;

  s = 0;
  for ( i = 0; i < n; i++ )
    s += v[i];

  return s;
}

int main() {
  int x;
  int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  x = sumaVect( 10, a );
  printf( "Suma este %d\n", x );

  return 0;
}

Modificarea numărului de elemente al vectorului într-o funcție

Ce se întâmplă dacă funcția modifică numărul de elemente al vectorului, de exemplu inserează un element în vector? Ar trebui să modificăm numărul de elemente, ceea ce nu putem face în funcție, din cauza transmiterii prin copiere a parametrilor. O soluție poate fi ca funcția să returneze noul număr de elemente al vectorului.

Exemplu: ștergerea unei valori din vector

#include <stdio.h>

// sterge valoarea e din v[] de pe toate pozitiile unde apare
int stergVect( int n, int v[], int e ) {
  int i, j;

  j = 0;
  for ( i = 0; i < n; i++ )
    if ( v[i] != e ) {
      v[j] = v[i];
      j++;
    }

  return j;
}

int main() {
  int n, i;
  int a[10] = { 1, 2, 3, 4, 2, 3, 2, 8, 9, 2 };

  n = 10;
  n = stergVect( n, a, 2 );
  printf( "Vectorul are acum %d elemente:", n );
  for ( i = 0; i < n; i++ )
    printf( " %d", a[i] );
  printf( "\n" );

  return 0;
}

Programul va afișa:

Vectorul are acum 6 elemente: 1 3 4 3 8 9

Pentru matrice cărora funcția le modifică dimensiunile vom vedea mai jos cum putem proceda.

Exemple

Scrieți funcții care să rezolve:

Inversare vector

#include <stdio.h>

// inverseaza (rastoarna) elementele unui vector
void invVect( int n, int v[] ) {
  int i, j, aux;

  i = 0;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
}

int main() {
  int n, i;
  int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  n = 10;
  invVect( n, a );
  printf( "Vectorul inversat este:" );
  for ( i = 0; i < n; i++ )
    printf( " %d", a[i] );
  printf( "\n" );

  return 0;
}

Inserare element în vector la o poziție dată

#include <stdio.h>

// insereaza un element e in vectorul v de n elemente la pozitia poz
// daca poz este mai mare strict decit n nu face nimic
int insVect( int e, int n, int v[], int poz ) {
  int i;

  if ( poz <= n ) { // putem insera?
    for ( i = n; i > poz; i-- )
      v[i] = v[i - 1];
    v[poz] = e;
    n++;
  }

  return n;
}

int main() {
  int n, e, i;
  int a[20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  n = 10;
  e = 15;
  n = insVect( e, n, a, 5 ); // insereaza 15 pe pozitia 5
  printf( "Vectorul cu %d inserat pe pozitia 5 este:", e );
  for ( i = 0; i < n; i++ )
    printf( " %d", a[i] );
  printf( "\n" );

  return 0;
}

Citire întreg fără semn din fișier folosind doar fgetc()

#include <stdio.h>
#include <ctype.h> // pentru isdigit()

FILE *fin;

// Citeste un intreg de la intrare
int getInt() {
  int ch, n;

  n = 0;
  while ( !isdigit( ch = fgetc( fin ) ) ); // ignora non-cifre
  do n = n * 10 + ch - '0';
  while ( isdigit( ch = fgetc( fin ) ) );

  return n;
}

// Citim un vector din fisierul 'fin' si il afisam
int main() {
  int n, i;
  int v[20];

  fin = fopen( "exemplu.in", "r" );
  n = getInt();
  for ( i = 0; i < n; i++ )
    v[i] = getInt();
  fclose( fin );

  printf( "Vectorul citit este:" );
  for ( i = 0; i < n; i++ )
    printf( " %d", v[i] );
  printf( "\n" );
  
  return 0;
}

Observați că am declarat variabila fișier în afara lui main() pentru a putea fi vizibilă în funcție. Vom vorbi despre aceasta mai jos.

Reguli de vizibilitate ale variabilelor în funcții

În C avem două tipuri de variabile: locale și globale.

Variabilele locale se declară în interiorul unei funcții (sau în interiorul lui main()) și sunt vizibile (apelabile, folosibile) doar în acea funcție. Se cheamă că variabilele aparțin acelei funcții.
Variabilele globale se declara în afara oricărei funcții și sunt vizibile din toate funcțiile, inclusiv main(). Precum știm deja ele sunt și inițializate automat cu zero.

Ce se întâmplă dacă denumim o variabilă locală cu același nume ca una globală? Cea locală are prioritate.

Exemplu

Ce afișează următorul program?

#include <stdio.h>

int a = 100; // declarare variabila globala

void afiseaza() {
  printf( "a global este %d\n", a );
}
 
int main () {
  int a; // declarare variabila locala cu acelasi nume

  a = 30; // atribuire variabila locala

  afiseaza();
 
  printf( "a local este %d\n", a );
 
  return 0;
}

Programul va afișa:

a global este 100
a local este 30

Modificarea parametrilor cu efect la ieșirea din funcție

Ce facem dacă totuși ne dorim să modificăm o variabilă transmisă ca parametru? În acest caz vom apela funcția cu adresa de memorie (zisă și pointer) a variabilei. Vom folosi doi operatori noi:

& se aplică unei variabile și extrage adresa de memorie a variabilei
* se aplică unei adrese de memorie și extrage conținutul variabilei de la acea adresă

Ar fi bine să evitați, deocamdată, deoarece mai întâi trebuie să învățați noțiunea de pointeri, care nu face scopul acestei lecții.

Exemplu: functia swap

#include <stdio.h>

void swap( int *pa, int *pb ) {
  int aux;

  aux = *pa;
  *pa = *pb;
  *pb = aux;
}

int main() {
  int a, b;

  a = 100;
  b = 200;
  swap( &a, &b );
  printf( "a=%d b=%d\n", a, b );

  return 0;
}

Declarații de variabile și vizibilitatea acestora. Așezarea lor pe stivă.
Conversia de tip când chemăm funcția cu alte tipuri decât cele declarate.

Funcțiile și programarea structurată

Instrucțiunea return este echivalentul unui salt la finalul funcției. Programare evident nestructurată. De aceea, deși limbajul C ne permite, nu o vom folosi decât la finalul funcției, ca ultima instrucțiune. C este un limbaj vechi. Limbaje gen Pascal au rezolvat problema nestructurării eliminând instrucțiunea return.

Când scriem funcții?

Bun, am învățat funcții. Dar cum iau decizia să scriu o funcție sau nu?

Atunci când nu putem evita repetiția de cod prin alte mijloace (factorizare, bucle, etc)
Atunci când programul devine prea lung pentru a fi citit ușor, de obicei undeva la 80-100 de linii. Ca regulă generală o funcție ar fi bine să aibă până în 100 de linii, dar desigur regula nu este bătută în cuie.
Atunci când simțim că o bucată semnificativă de cod are o coeziune, reprezintă un tot unitar, o putem transforma în funcție.
Atunci când scriem o bucată de cod care execută un calcul general, gen sortare, sau citirea unui întreg, atunci o putem scrie ca funcție pentru a o refolosi în viitor. Vom vedea că aceasta este baza de pornire a bibliotecilor de funcții.
Nu este bine să "rupem" artificial programul de dragul funcțiilor. Dacă tot programul ar avea 40 de linii, introducerea unor funcții i-ar scădea lizibilitatea.
Pe cazul general, la olimpiade și pentru programele mici care rezolvă probleme de concurs încercați să evitați funcțiile inutile, doar de dragul artei. Când tot programul, scris elegant, ar avea 80 de linii este destul de greu să justifici introducerea unor funcții.

Cum denumim funcțiile?

O funcție trebuie denumită cât mai sugestiv. Funcții denumite citire() sau solve() cu am văzut la colegii voștri mai mari fac codul mai necitibil decât dacă ele nu existau. Ele sunt echivalentul variabilelor denumite contor sau stegulet. Așa cum stegulețul ar fi bine să se numească terminat sau fara_zero, la fel și funcțiile trebuie denumite sugestiv. Pentru cele două funcții de mai sus nume bune ar fi citesteVectorInaltimi() sau calculSumePartiale(). Observați că primul cuvânt din denumirea unei funcții începe cu literă mică, celelalte cu literă mare. Aceasta este o convenție de codare. Pentru variabile formate din mai multe cuvinte vom folosi numai litere mici, unind cuvintele cu underscore (sau underline, caracterul '_').

Considerente de viteză

Atunci când funcția poate fi chemată de un număr mare de ori calculatorul pierde un timp semnificativ în apelul de funcție. Un exemplu tipic ar fi când funcția este chemată într-o buclă care se execută de un milion de ori. Ce putem face?

Evitați astfel de funcții, dacă nu dăunează eleganței și citibilității programului: introduceți codul funcției în loc de apel.
Dacă totuși trebuie să folosiți o funcție aveți opțiunea să o declarați inline. Aceasta înseamnă că compilatorul nu va genera cod care să cheme funcția ci va înlocui apelul cu chiar corpul funcției, peste tot unde apare el. Este ca și cum funcția nu ar exista, păstrând însă citibilitatea programului (nu și scurtimea executabilului generat, din păcate).

Tema 1

Să se rezolve următoarele probleme (program C în CodeBlocks, trimis la NerdArena):

Rapper

Snake

Atenție! Implementările trebuie să conțină funcțiile menționate la prezentarea soluțiilor problemelor, mai sus. Mai exact:

La problema Rapper, veți scrie și utiliza următoarele funcții (folosind doar fgetc() pentru citirea caracterelor):

#define LINLEN 100

char linie[LINLEN + 1]; // unu in plus pentru terminatorul de linie '\0'

// citeste o linie si calculeaza numarul de nume si pozitia ultimului spatiu
void citesteLinie( FILE *fin, int *pnnume, int *psp ) {
  // ... corpul functiei
}

// calculeaza nota prezenta in linia curenta
// nota este un numar intre 0 si 1000, pentru a nu avea un numar cu zecimale
// i este pozitia ultimului spatiu din linie
int calcNota( int i ) {
  int nota = 0;

  // ... corpul functiei

  return nota;
}

// exemplu de utilizare
int main() {
  FILE *fin, *fout;
  int i, nnume, sp;

  fin = fopen( "rapper.in", "r" );
  // ...
  citesteLinie( fin, &nnume, &sp ); // citeste prima linie
  while ( nnume > 0 ) {    // linia are macar un spatiu - nu este ultima
    nlin++;                // numaram inca o linie
    // ...
    citesteLinie( fin, &nnume, &sp ); // citeste urmatoarea linie
  }
  fclose( fin );
  // ...
  return 0;
}

La problema snake, veți scrie și utiliza următoarele funcții:

#define MAXN 1000
#define ZID -1
#define MAR -2

int dlin[4] = { 0, 1, 0, -1 };
int dcol[4] = { 1, 0, -1, 0 };

int tabla[MAXN][MAXN];

// citeste perechi de coordonate la intrare si le marcheaza in matrice cu mark
void citestePozitii( FILE *fin, int mark ) {
  // corpul functiei
}

// date:
// n - dimensiunea tablei
// (l c) - pozitia curenta
// *dir - directia curenta
//
// calculeaza (*lurm *curm) pozitia urmatoare si *dir pozitia urmatoare
inline static void genUrm( int n, int l, int c,
                           int *dir, int *lurm, int *curm ) {
  // ... corpul functiei
}

// exemplu de utilizare
int main() {
  FILE *fin, *fout;
  int nivel, n, m, dir, lcap, ccap, lurm, curm, valcoada, aux;

  fin = fopen( "snake.in", "r" );
  fscanf( fin, "%d%d%d", &nivel, &n, &m );
  citestePozitii( fin, ZID ); // citeste zidurile
  citestePozitii( fin, MAR ); // citeste merele
  fclose( fin );

  lcap = ccap = dir = 0;
  // ... alte initializari
  genUrm( n, lcap, ccap, &dir, &lurm, &curm ); // urmatoarea pozitie
  while ( m > 0 && <conditie non-intersectie> ) {
    // ... bucla simulare, mutare sarpe, etc
    genUrm( n, lcap, ccap, &dir, &lurm, &curm ); // urmatoarea pozitie
  }
  // ...  
  return 0;
}

Accesează rezolvarea temei 1

Clasa a 7-a Lecția 1: Reguli de programare în limbajul C și complexități algoritmice

Contents

Înregistrare video lecție

Reguli de programare în limbajul C

Declararea vectorilor cu inițializare

Tabel de descriptori citire/scriere

Complexități algoritmice

Funcții în limbajul C

De ce funcții

Sintaxa: cum scriem o funcție

Sintaxa (simplificare)

Exemplu

Apelul

Apelul funcțiilor

Parametri și valoare returnată

Cum transmitem corect vectorii unei funcții

Exemplu: suma elementelor unui vector

Modificarea numărului de elemente al vectorului într-o funcție

Exemplu: ștergerea unei valori din vector

Exemple

Inversare vector

Inserare element în vector la o poziție dată

Citire întreg fără semn din fișier folosind doar fgetc()

Reguli de vizibilitate ale variabilelor în funcții

Exemplu

Modificarea parametrilor cu efect la ieșirea din funcție

Exemplu: functia swap

Funcțiile și programarea structurată

Când scriem funcții?

Cum denumim funcțiile?

Considerente de viteză

Tema 1

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools