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.

Rezolvare

Rezolvați problema monotonă: numim o secvență monotonă dacă ea este fie crescătoare fie descrescătoare. O secvență este crescătoare dacă fiecare element este mai mare sau egal cu cel din-naintea lui. O secvență este descrescătoare dacă fiecare element este mai mic sau egal cu cel din-naintea lui. Cerință: dată o secvență de n numere să se spună dacă este monotonă. Exemple:

Fișierul monotona.in Fișierul monotona.out Explicație
5
4 7 7 8 8
da Secvența este crescătoare.
8
7 7 7 7 4 4 3 2
da Secvența este descrescătoare.
6
3 3 3 3 3 3
da Secvența poate fi și crescătoare si descrescătoare.
8
1 1 1 2 2 2 1 2
nu Secvența nu este nici crescătoare nici descrescătoare.

Răspuns: La începutul secvenței nu știm în ce stare se află ea: este crescătoare sau descrescătoare, sau nici una, nici alta. O idee ar putea fi să ne uităm la primele două numere din secvență și să stabilim. Din păcate acest lucru nu este posibil deoarece primele două numere pot fi egale. Sau primele 10 numere!

O altă idee ar putea fi să citim numere pînă ce găsim un număr diferit de primul. Dar trebuie să avem grijă să nu se termine secvența înainte! Puteți să încercați voi soluția aceasta, probabil că unii dintre voi așa vor încerca.

Aici vom descrie o altă soluție: vom folosi o variabilă d care ne va indica direcția de creștere a secvenței: d va fi:

  • 1 dacă secvența este crescătoare
  • -1 dacă secvența este descrescătoare
  • 0 dacă secvența este egală, compusă din același număr
  • 2 dacă secvența nu este în nici unul din cazurile de mai sus (adică nu este nici crescătoare, nici egală nici descrescătoare)

La început, înainte să citim numere, secvența este egală, deci vom inițializa d cu 0. Pe măsură ce citim numere vom vedea cum se compară cu cele din-naintea lor și vom modifica d ca atare. Dacă găsim un număr mai mic înseamnă că secvența a devenit descrescătoare, deci vom pune d pe -1. Dacă găsim un număr mai mare, înseamnă că punem d pe 1. Dacă însă d este deja -1, adică secvența este descrescătoare, și găsim un număr mai mare, înseamnă că secvența întîi a scăzut și apoi crește, deci nu este monotonă și vom pune d 2. Similar, dacă d este deja 1 și apoi găsim un număr mai mic, vom pune d pe 2. La final secvența va fi monotonă dacă d < 2.

Iată algoritmul care implementează această idee.

Secvență monotonă
#include <stdio.h>
int main() {
  FILE *fin, *fout;
  int n, i, a, b, dir;

  fin = fopen( "monotona.in", "r" );
  fscanf( fin, "%d", &n );
  fscanf( fin, "%d", &a );
  /*
    directia poate fi:
    -1 - descrescatoare
     0 - indecisa (egala)
     1 - crescatoare
     2 - nici unul din cazurle de mai sus
  */
  dir = 0; // initial directia este indecisa (egala)
  i = 1;
  while ( i < n && dir < 2 ) {
    fscanf( fin, "%d", &b );
    if ( b > a ) // secventa devine crescatoare, daca se mai poate
      if ( dir < 0 )
        dir = 2;
      else
        dir = 1;
    else if ( b < a ) // secventa devine descrescatoare, daca se mai poate
      if ( dir > 0 )
        dir = 2;
      else
        dir = -1;
    a = b;
    i++;
  }
  fclose( fin );

  fout = fopen( "monotona.out", "w" );
  if ( dir < 2 )
    fprintf( fout, "da\n" );
  else
    fprintf( fout, "nu\n" );
  fclose( fout );
  return 0;
}

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ă...

Rezolvare

Rezolvați problema mulţimi dată la OJI 2005 clasa a 5a.

Răspuns: vom proceda similar cu găsirea maximului unei secvențe. Vom ține minte intersecția curentă a mulțimilor folosind două variabile inta și intb. La fiecare pas vom citi încă o mulțime, a, b și vom calcula intersecția dintre ea și inta, intb.

Cum calculăm intersecția a două mulțimi? Să observăm că dacă ea este nevidă atunci capătul din stînga este maximul dintre inta și a. Similar, capătul din dreapta este minimul dintre intb și b. Cum ne dăm seama că intersecția mulțimilor este vidă? Ea este vidă dacă capătul din stînga a depășit capătul din dreapta; cu alte cuvinte dacă inta > intb.

Iată soluția:

Mulțimi
#include <stdio.h>

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

  fin = fopen( "multimi.in", "r" );
  fscanf( fin, "%d", &n );
  fscanf( fin, "%d%d", &inta, &intb );
  i = 1;
  while ( i < n && inta <= intb ) { // intersectia nu e vida?
    fscanf( fin, "%d%d", &a, &b );  // citim o noua multime
    if ( inta < a )  // calculam noul capat din stinga
      inta = a;
    if ( intb > b )  // calculam noul capat din dreapta
      intb = b;
    i++;
  }
  fclose( fin );

  fout = fopen( "multimi.out", "w" );
  if ( inta > intb )                    // multimea este vida?
    fprintf( fout, "multimea vida\n" );
  else {
    for ( i = inta; i <= intb; i++ )
      fprintf( fout, "%d ", i );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Problema de logică

Ne aflăm în întuneric total (nu putem vedea nimic). Avem în față un pachet de 52 de cărți de joc. Ele sînt amestecate, dar se știe că 42 de cărți sînt cu fața în jos, iar 10 sînt cu fața în sus. Cum facem să împarțim cele 52 de cărți în două gramezi, astfel încît ambele grămezi să conțină un număr egal de cărți cu fața în sus?

Răspuns: Luăm primele 10 cărți din pachet, le întoarcem pe dos și le punem într-un teanc. Ce rămîne este al doilea teanc. Ambele teancuri vor avea număr egal de cărți cu fața în sus. De ce?

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 [1]