Clasa a IX-a lecția 12

Aplicatii cu secvente

#516SumSec1

Se dă un vector format din n elemente, numere naturale. Calculați suma elementelor din secvența determinată de primul și ultimul element impar.

#include <stdio.h>

int main(){
  int n, i, s, s1, x, start;

  scanf ( "%d", &n );
  s = s1 = 0;
  start = 0;
  for ( i = 0; i < n; i ++ ){
    scanf ( "%d", &x );
    if ( x % 2 ){
      start = 1;        // dam startul la adunarea numerelor
      s += x + s1;      // adunam nr impar si suma acumulata pana atunci
      s1 = 0;           // resetam suma acumulata pana atunci
    }
    else
      if ( start )      // daca am gasit anterior un nr impar, pun x intr-o suma 
        s1 += x;
  }
  printf ( "%d", s );
  return 0;
}

SecvZero - cea mai lunga subsecventa de elemente egale cu zero

Se dă un vector cu n elemente numere naturale. Determinați cea mai lungă secvență de elemente nule din vector. Dacă în vector există mai multe secvențe de elemente nule de lungime maximă se va determina cea mai din stânga ( adica prima gasita).

// Cea mai lunga secventa de zerouri din sir
#include <stdio.h>

int main(){
  int n, i, nr, st, stmax, l, lmax;
  scanf( "%d", &n );

  lmax = 0;           // lungimea celei mai lungi secvente de zerouri
  l = 0;              // lungimea secventei de zerouri curente
  for(i = 1; i <= n; i++ ){
    scanf( "%d", &nr );   // citim numarul de pe pozitia i din sir
    if( nr == 0 ){        // daca numarul este 0
      if ( l == 0 )       // daca e inceput de secventa
        st = i;           // pastram pozitia de inceput a secventei curente
      l++;                // lungimea secventei curente creste cu 1
      if( lmax < l ){     // verific daca am obtinut o secventa mai lunga decat cea maxima
        lmax = l;         // daca da, actualizez valoarea secventei maxime
        stmax = st;       // si memorez pozitia sa de inceput
      }
    }
    else                  // daca nr nu este 0
      l = 0;              // resetam lungimea secventei curente la 0
  }

  printf("%d %d", stmax, stmax + lmax - 1 );
  return 0;
}

SecvEgaleCea mai lunga subsecventa de elemente egale

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente egale din vector. Dacă în vector există mai multe secvențe de elemente egale de lungime maximă se va determina cea mai din dreapta.

// Cea mai lunga secventa de elemente egale din sir, cea mai din dreapta
#include <stdio.h>

int main(){
  int n, i, a, b, st, stmax, l, lmax;

  scanf( "%d%d", &n, &a );

  l = lmax = 1;            // lungimea secventei curente de elem egale, aceasta e si lungimea maxima de pana acum
  st = stmax = 1;          // pozitia secventei curent, aceasta este si poz secv. maxime de pana acum
  for(i = 2; i <= n; i++ ){
    scanf( "%d", &b );    // citim numarul de pe pozitia i din sir
    if( b == a ){         // daca numarul este 0
      l++;                // lungimea secventei curente creste cu 1
      if( lmax <= l ){    // verific daca am obtinut o secventa mai lunga decat cea maxima
        lmax = l;         // daca da, actualizez valoarea secventei maxime
        stmax = st;       // si memorez pozitia sa de inceput
      }
    }
    else{                  // daca nr nu este egal cu precedentul
      l = 1;               // elementul citit e singurul in secventa
      st = i;              // si pozitia lui e pozitia secventei curente
    }
    a = b;                 // salvam valoarea citita in a, pentru a o compara cu cea citita la pasul urmator
  }

  printf("%d %d", stmax, stmax + lmax - 1 );   
  return 0;
}

Laborator

secventa11

Într-un şir trebuie determinată lungimea maximă a unei secvenţe de numere care în scrierea binară au numai cifra 1.

SecvEgale2

Se dă un vector cu n elemente, numere naturale. Determinați câte secvențe ale vectorului au toate elementele egale.

Secvente1

Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare.

SumSec

Se dă un şir format din n elemente, numere naturale. Calculaţi suma elementelor din secvenţa determinată de primul şi ultimul element prim.

SecvMax

Să se determine cea mai lungă secvență de elemente pare dintr-un vector.

SecvCresc

Să se determine cea mai lungă secvență de elemente ordonate strict crescător dintr-un vector.

Secvente

Se dă un şir format din n elemente, numere naturale. Determinaţi câte secvenţe maximale cu elementele ordonate crescător conţine şirul.

Tema

Terminati de rezolvat problemele de la laborator A - Tokitsukaze and Discard Items -Div1