Clasa a IX-a lecția 11

From Algopedia
Jump to navigationJump to search

Secvențe - continuare

Secvență în ordine crescătoare

Dată o secvență cu n numere să se spună dacă cele n numere din secvență sînt in ordine crescătoare (fiecare număr este mai mic sau egal cu cel de după el).

Secvență crescătoare
 
 #include <stdio.h>

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

   fin = fopen( "crescatoare.in", "r" );
   fscanf( fin, "%d", &n );
   fscanf( fin, "%d", &a );
   cresc = 1;
   i = 1;
   while ( i < n && cresc == 1) {
     fscanf( fin, "%d", &b );
     if ( b < a )
       cresc = 0;
     a = b;
     i++;
   }
   fclose( fin );

   fout = fopen( "crescatoare.out", "w" );
   if ( cresc == 1 )
     fprintf( fout, "da\n" );
   else
     fprintf( fout, "nu\n" );
   fclose( fout );
   return 0;
 }

Observații:

  • Nu folosim instrucțiunea for deoarece nu se știe de cîte ori se va executa bucla while (nu avem un ciclu cu număr cunoscut de pași).
  • Trebuie să ținem minte elementul anterior în secvență, pentru a-l putea compara cu elementul curent. Vom vedea că în alte probleme vom avea nevoie să ținem minte două sau chiar și trei elemente anterioare.
  • Încercaţi să scrieţi algoritmul fără a folosi steguleţe.

Laborator

Exerciții cu secvențe

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;
 }

Tema

  • De pe pbinfo.ro

pbinfo : deedee , MinimDoua , MaximPar , rafaelo , platou1 , platou2 , platou3 , platou4 , triviador , Robot5 , Concurs2 , Smartphone , Fibonacci

Probleme Codeforces

Mai grele :

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_IX-a_lecția_11&oldid=17213"