View source for Clasa a IX-a lecția 11

== 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).
{|
| [[Image:sl-secventa-crescatoare.gif|frame|none|Secvență crescătoare]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}
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:
{| class="wikitable"
!<tt>identice.in</tt>
!<tt>identice.out</tt>
!Explicație
|-
| valign="top" |<tt>10<br/>6 2 2 5 8 8 8 2 2 5</tt>
| valign="top" |<tt>3</tt>
| valign="top" | Numărul 8 apare de trei ori la rînd. Nici un alt număr nu apare de mai multe ori la rînd.
|-
| valign="top" |<tt>14<br/>8 8 3 3 3 3 1 1 1 5 5 5 5 2</tt>
| valign="top" |<tt>4</tt>
| valign="top" |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:
{|
| [[Image:sl-secventa-identice.gif|frame|none|Numere identice]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}

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 <tt>l > lmax</tt> numai atunci cînd <tt>b ≠ a</tt>. 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ă <tt>l > lmax</tt>.

=== 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: 
{| class="wikitable"
!<tt>cuvinte.in</tt>
!<tt>cuvinte.out</tt>
!Explicație
|-
| valign="top" |<tt>10<br/>3 5 0 0 2 9 7 0 1 3</tt>
| valign="top" |<tt>3</tt>
| valign="top" | Sînt trei cuvinte (subsecvenţe de numere diferite de zero), <tt>3 5</tt>, <tt>2 9 7</tt> şi <tt>1 3</tt>.
|-
| valign="top" |<tt>10<br/>0 0 0 2 6 1 0 0 1 0</tt>
| valign="top" |<tt>2</tt>
| valign="top" |Sînt două cuvinte (subsecvenţe de numere diferite de zero), <tt>2 6 1</tt> şi <tt>1</tt>.
|}

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 <tt>incuv</tt> 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.
{|
| [[Image:sl-secventa-cuvinte.gif|frame|none|Numărare de cuvinte]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}
= Tema =
* De pe pbinfo.ro
pbinfo : deedee , MinimDoua , MaximPar , rafaelo , platou1 , platou2 , platou3 , platou4 , triviador , Robot5 , Concurs2 , Smartphone , Fibonacci

* De pe Varena.ro
* Problema [http://varena.ro/problema/padure padure]
* Problema [http://varena.ro/problema/subcresc subcresc]
* Problema [http://varena.ro/problema/monotona monotona]
* Problema [http://varena.ro/problema/plaja1 plaja1]
* Problema [http://varena.ro/problema/plaja2 plaja2]
* Problema [http://varena.ro/problema/cabina cabina]

==== Probleme Codeforces ====
* [https://codeforces.com/contest/427/problem/A A. Police Recruits]
* [http://codeforces.com/problemset/problem/1138/A A. Sushi for Two] Cea mai lunga secv de 111222 sau 222111 ( secv de 1 si secv de 2 cu lungimi egale )
*[https://codeforces.com/contest/721/problem/A A. One-dimensional Japanese Crossword]

Mai grele :
* Problema [http://varena.ro/problema/bitona bitona]