Clasa a V-a lecția 14 - 23 noi 2019

From Algopedia
Jump to navigationJump to search

Tema – rezolvări

Comentarii generale

  • Felicitări celor care au făcut toate problemele corect: Andrei Grama. Apreciez toate încercările celorlalți care și-au dat silința, dar nu au obținut punctaj maxim.
  • Avertisment celor care nu au abordat tema deloc: Alex Stanciu și David Poterașu (avertisment final).
  • Printre voi în continuare sunt aceia care trimit surse în C++. Cum spuneam data trecută, nu accept astfel de surse la curs. Dacă nu ați înțeles motivul, vă invit să revedeți filmarea cursului trecut sî să citiți regulile cercului. Avertisment: Luca Zamfir și Matei Balaur.
  • Chiar dacă nu aveți disponibile testele în timpul temelor, vineri aveți acces la ele. Puteți să vă corectați soluțiile.
  • În timpul temelor mi-aș dori să începeți să vă dați singuri testele. Adică, să citiți cu atenție cerința problemei și să testați programul cu valorile limită pe care le poate avea problema. Exemplu: dacă șirul poate conține o singură valoare, atunci testați cazul acesta. S-ar putea să aveți surpriza să nu meargă algoritmul scris de voi.

Monotonă

Comentarii

  • În principiu, au fost soluții bune, cu mici excepții. Unii dintre voi v-ați complicat foarte tare să ajungeți la rezultat, cu soluții care avea foarte multe cazuri de tratat. Încercați să rafinați soluția după ce ați gasit-o. Fiți din ce în ce mai eficienți.
  • Cei care nu ați punctat maxim, ați ratat doar câteva teste, acelea care erau limită. Aici mă refer la Andrei Coman, Briana Vasile, Vladimir Gavriș. Exemplu:
    • nu ați testat cazul când șirul era format dintr-un singur element;
    • nu ați verificat cazul când șirul avea oricare două valori;
    • nu ați testat situația în care șirul este alcătuit din n numere și acelea avea doar două calități. Exemplu: șir de 6 numere, 1 1 1 2 2 2.
  • Nu accept coduri care conțin comenzile [code]continue[/code] sau [code]break[/code]. În primul rând, aceste noțiuni nu le-am predat. Nu vă cer lucruri pe care eu nu le-am predat. Și dovada este că nici măcar nu sunt folosite corect. În al doilea rând, noi învățăm programare structurată, iar aceste 2 comenzi au rămas din timpul în care programarea nu era structurată și o puteam scrie oricum. Avertisment: Luca Zamfir.


Mulțimi

Comentarii

  • Cristina Boabeș: nu ai verificat cazul în care mulțimea este vidă. Citește cerința cu atenție, pentru că îți spunea clar ce trebuie să faci. Altfel, soluția ta este bună.
  • Luca Zamfir: ai avut tentative și cu vectori și în C++... nu am predat așa ceva. Rezumă-te la ceea ce v-am predat întrucât nu vă cer altceva.
  • Briana Vasile: ultima sursă cu eroare de compilare nu are mult sens. Ai incercat să închizi fișierul de scriere, pe care nu l-ai deschis niciodată...

Rezolvări aici [1]

Lecție

Exerciții cu secvențe

Șirul lui Fibonacci

Definiție: șirul lui Fibonacci este secvența de numere 0, 1, 1, 2, 3, 5, 8, 13... Regula acestei secvențe este că primele două numere sînt 0 și 1, iar următoarele numere sînt suma celor două numere din-naintea lor. Exercițiu: dat n, să se calculeze al n-lea termen din șirul lui Fibonacci. Exemple:

fibonacci.in fibonacci.out
1 0
2 1
5 3
8 13

Rezolvare:

Șirul lui Fibonacci
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, b, f;

   fin = fopen( "fibonacci.in", "r" );
   fscanf( fin, "%d", &n );
   fclose( fin );

   a = 0;
   if ( n == 1 )
     b = a;
   else {
     b = 1;
     for ( i = 2; i < n; i++ ) {
       f = a + b;
       a = b;
       b = f;
     }
   }

   fout = fopen( "fibonacci.out", "w" );
   fprintf( fout, "%d", b );
   fclose( fout );
   return 0;
 }

Observații:

  • Secvența de numere nu este citită ci generată.
  • Este necesar să memorăm ultimele două numere din secvență pentru a genera următorul număr.

Numere identice

Se dă o secvența de n numere. Să se spună care este numărul maxim de numere identice consecutive în secvență. Exemple:

identice.in identice.out Explicație
10
6 2 2 5 8 8 8 2 2 5
3 Numărul 8 apare de trei ori la rînd. Nici un alt număr nu apare de mai multe ori la rînd.
14
8 8 3 3 3 3 1 1 1 5 5 5 5 2
4 Numărul 3 apare de patru ori la rînd. De asemenea și numărul 5 apare de patru ori la rînd. Nici un alt număr nu apare de mai multe ori la rînd.

Rezolvare:

Numere identice
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, b, l, lmax;

   fin = fopen( "identice.in", "r" );
   fscanf( fin, "%d", &n );
   fscanf( fin, "%d", &a );
   lmax = 1;
   l = 1;
   for ( i = 1; i < n; i++ ) {
     fscanf( fin, "%d", &b );
     if ( b == a ) {
       l++;
       if ( l > lmax )
         lmax = l;
     } else {
       a = b;
       l = 1;
     }
   }
   fclose( fin );

   fout = fopen( "identice.out", "w" );
   fprintf( fout, "%d", lmax );
   fclose( fout );
   return 0;
 }

Observații:

  • Și aici ținem minte elemetul anterior în secvență, pentru a-l putea compara cu cel actual.
  • O alternativă mai eficientă ar fi să comparăm l > lmax numai atunci cînd b ≠ a. Se poate și așa, dar trebuie să avem grijă în cazul în care cea mai lungă secvență este chiar la final. Pentru acest caz particular va trebui ca imediat după bucla WHILE-DO să mai testăm o dată dacă l > lmax.

Numărare de cuvinte

Considerăm o secvență de numere. Să considerăm zerourile ca spații, iar numerele diferite de zero ca litere. Dorim să numărăm cîte cuvinte avem în secvență. Exemple:

cuvinte.in cuvinte.out Explicație
10
3 5 0 0 2 9 7 0 1 3
3 Sînt trei cuvinte (subsecvenţe de numere diferite de zero), 3 5, 2 9 7 şi 1 3.
10
0 0 0 2 6 1 0 0 1 0
2 Sînt două cuvinte (subsecvenţe de numere diferite de zero), 2 6 1 şi 1.

O variantă de rezolvare ar fi să ne uităm la două numere consecutive în secvență și să vedem dacă începe un cuvînt (sau dacă se termină). O a doua variantă este să ținem o variabila incuv care să ne spună dacă ne aflăm în interiorul unui cuvînt sau nu. Vom prefera această variantă deoarece este mai simplă și se poate generaliza pentru situații mai complicate.

Numărare de cuvinte
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, incuv, nrcuv;

   fin = fopen( "cuvinte.in", "r" );
   fscanf( fin, "%d", &n );
   nrcuv = 0;
   incuv = 0;
   for ( i = 0; i < n; i++ ) {
     fscanf( fin, "%d", &a );
     if ( a == 0 )
       incuv = 0;
     else
       if ( incuv == 0 ) {
         nrcuv++;
         incuv = 1;
       }
   }
   fclose( fin );

   fout = fopen( "cuvinte.out", "w" );
   fprintf( fout, "%d", nrcuv );
   fclose( fout );
   return 0;
 }

Temă

  • Tema 14: să se rezolve următoarele probleme (schemă logică + program C în Code::Blocks, trimis la vianuarena):
  • Problemă de logică: zece oameni sînt așezați în șir, unul în spatele altuia. Li se așează pe cap cîte o tichie neagră sau albă. Fiecare om poate să vadă tichiile oamenilor din fața lui. Începînd cu ultimul, cel mai din spate, oamenii strigă pe rînd "alb" sau "negru". După ce strigă, ei sînt scoși din rînd și duși într-o cameră unde sînt eliberați, dacă și-au ghicit culoarea tichiei, sau omorîți în caz contrar. Un om poate să audă ce au strigat, pe rînd oamenii din spatele său. Oamenii nu au voie să comunice în nici un alt fel, cum ar fi să tușească, să se atingă, etc, sau vor fi omorîți toți! Ei au voie să se sfătuiască înainte să fie așezați, pentru a stabili strategia prin care să salveze cîți mai mulți dintre ei. Voi trebuie să stabiliți ce strategie aleg oamenii și care este numărul maxim de oameni pe care îi puteți salva. Exemplu: să presupunem că oamenii aleg următoarea strategie: ei vor striga, pe rînd, "alb", cu toții. În acest caz vor supraviețui 5 oameni, pe medie.

Rezolvări aici [2]