Clasa a VII-a lecția 1 - 19 sep 2019

From Algopedia
Jump to navigationJump to search

Anunțuri

Bun venit la IQ Academy,în noul an școlar.

  • Avem elevi noi. Sîntem mulți. Sînteți mai mari. Hai să fim și mai cuminți și mai maturi în acest an.
  • Listă de prezență, pentru verificare componență grupe (reminder to self).
  • Toată lumea trebuie să fie înscrisă pe clubul curioșilor. Aveți instrucțiuni de înscriere aici: Instrucțiuni înscriere Clubul curioșilor. Recomand ca și măcar unul din părinți sau alt adult să fie inscris pe această listă.
  • Toată lumea, dar mai ales noii veniți, trebuie să citească și să își insușească capitolul reguli ale cercului de informatică. Citiți cu atenție mai ales ultima parte, reguli de programare în limbajul C
  • Alte părți importante din reguli: prezența este foarte importantă, nu chiuliți și anunțați-mă cînd apare o problemă și nu puteți veni. De asemenea temele sunt obligatorii, nu neapărat să luați 100p, dar să vă gîndiți la ele și să incercați să le rezolvați. Atenție, absențele și temele neîncercate sunt motive pentru retragerea selecției la IQ Academy.
  • Temele trebuie făcute de voi și numai de voi. Precum unii din voi știu deja am un al șaselea simț care îmi spune cînd veniți cu teme la care ați fost ajutați. Nu mi-l puneți la încercare ☺

Pentru cei noi:

  • Lecțiile sînt disponibile pe site-ul algopedia.ro.
  • Înscrieți-vă la Clubul Curioșilor dacă nu sînteți deja înscriși. Este locul unde discutăm despre probleme, orar și alte lucruri legate de IQ Academy.
  • Trimiteți la varena doar în cadrul concursului temă, nu la arhivă. A trimite la arhivă înseamnă a pescui, un mod de a trișa pentru a cîștiga mai multe puncte. Vreau să văd rapid numărul de trimiteri la o problemă, nu pescuiți vă rog.

Lecție

Notă: dintr-o greșeală tehnică (subsemnatul uituc a uitat să pornească microfonul) filmul lecției nu are sonor. Îl las totuși aici pentru cîteva desene la tablă care ar putea fi utile.

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-09-18-clasa-7-lectie-info-01-720p.mp4</html5media>

Reguli de programare în limbajul C

Să recapitulăm regulile de programare. Cei nou veniți, atenție maximă vă rog, sînt cerințe ce nu apar întotdeauna la alte cercuri.

  • 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ă sînt 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 if-ul 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() si folosiţi return 0 la final. Eliminați orice alte warnings deoarece majoritatea sînt 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, in fscanf, deci sînt 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 sînt 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, posibil 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ă ☺

Generalități

Să ne aducem aminte următoarele lucruri:

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 sînt 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ă milarde (2 cu nouă zerouri)
%d
unsigned int 4 0 ... 4294967295
aproximativ patru milarde (4 cu nouă zerouri)
%u
long long 8 -9223372036854775808 ... 9223372036854775807
aproximativ 9·1018 (9 cu 18 zerouri)
%lld în GNU/Linux și varena.ro
%I64d în Windows
unsigned long long 8 0 ... 18446744073709551615
aproximativ 18·1018 (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

Recapitulare complexități algoritmice

Algoritm Complexitate timp Complexitate memorie Explicații
Descompunerea lui n în factori primi Putem testa divizorii pînă la . Dacă la final n este diferit de 1 el este un factor prim al lui n la puterea 1.
Ridicare la putere ab Vezi exponențiere logaritmică
Calcul număr de zile între două date calendaristice corecte z1.l1.a1 și z2.l2.a2 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) 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 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 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 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 Elementele de după poziția de inserție trebuie deplasate către dreapta.
Ștergere element din vector de n elemente Elementele de după poziția de ștergere trebuie deplasate către stînga.
Interclasare a doi vectori ordonați de n1, respectiv n2 elemente
Sortare prin selecție a n numere - select sort
Sortare prin numărare (cu vectori de frecvență) a n numere - counting sort 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 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
Descompunerea în factori primi a tuturor numerelor de la 2 la 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
Calculul multiplicității numărului a în n! Termenul provine din descompunerea în factori primi a lui a. Apoi, pentru fiecare divizor prim al lui a () vom calcula de cîte ori se împarte n la acel divizor ().

Temă

Tema 1 clasa a 7a

  • magic dată la infotehnium 2013
  • schi dată la OJI 2014 clasa a 7a

Rezolvări aici [1]