Clasa a IX-a lecția 10

From Algopedia
Jump to navigationJump to search

Instrucțiunea for

Precum am văzut în exemplele anterioare de multe ori avem nevoie să executăm o buclă WHILE-DO de n ori, folosind un contor. Aceasta este un tip particular de buclă WHILE-DO, și anume o buclă cu număr cunoscut de pași. Pentru acest tip de bucle limbajul C ne permite o prescurtare, folosind instrucțiunea for.

Schemă logică Implementare cu while Implementare cu for
 i = 0;
 while ( i < n ) {
   ... execută corpul
       buclei...
   i = i + 1;
 }
 for ( i = 0; i < n; i++ ) {
   ... execută corpul
       buclei...
 }

Mecanism:

  • Pasul 1: Se executa initializarea
  • Pasul 2: Se testeaza conditia. Daca conditia este adevarata atunci trecem la pasul 3. Daca conditia este falsa se trece la pasul 5
  • Pasul 3: Se executa pachetul de instructiuni “Prel”
  • Pasul 4: Se executa incrementarea si se revine la pasul 2
  • Pasul 5: Stop

Aplicatie - Suma primelor n numere naturale

#include <stdio.h>

int main(){
    ///declaram 2 variabile de tip FILE*
    FILE *fin, *fout;
    ///vom asocia var. de tip file, 2 fisiere externe
    fin = fopen("date.in", "r");
    fout = fopen("date.out", "w");
    int n, i;
    long long s;
    ///citim din fisier datele de intrare
    fscanf(fin, "%d", &n);
    ///calculam suma primelor n numere
    s = 0;
    for(i = 1; i <= n; i++ )
      s = s + i;
    ///afisam rezultatul in fisierul de iesire
    fprintf(fout, "%lld", s);
    fclose(fin);
    fclose(fout);
    return 0;
}

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

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

Secvențe

Definiție: denumim secvență un șir de numere. Exemplu: 34 20 4 0 12 5 8 7. Simplu?

Citirea unei secvențe

Deoarece nu avem unde păstra numerele unei secvențe, le vom citi, pe rînd, în aceeași variabilă. Pentru a ști cîte numere citim (cîte numere are secvența) de obicei vom citi mai întîi numărul de numere din secvență, n și apoi cele n numerele din secvență, într-o buclă WHILE-DO. Exemplu:

Citire secvență
 fscanf( fin, "%d", &n );
 i = 0;
 while ( i < n ) {
   fscanf( fin, "%d", &a );
   i = i + 1;
 }
 fscanf( fin, "%d", &n );
 
 for (i = 0; i < n; i = i + 1) {
   fscanf( fin, "%d", &a );
   
 }

Suma unei secvențe

#include <stdio.h>

int main(){
    ///declaram 2 variabile de tip FILE*
    FILE *fin, *fout;
    ///vom asocia var. de tip file, 2 fisiere externe
    fin = fopen("date.in", "r");
    fout = fopen("date.out", "w");
    int n, i, nr;
    long long s;
    ///citim din fisier datele de intrare
    fscanf(fin, "%d", &n);
    ///calculam suma primelor n numere
    s = 0;
    for(i = 1; i <= n; i++ ){
      fscanf(fin, "%d", &nr);
      s = s + nr;
    }
    ///afisam rezultatul in fisierul de iesire
    fprintf(fout, "%lld", s);
    fclose(fin);
    fclose(fout);
    return 0;
}

Exemple:

Fișierul suma.in Fișierul suma.out
3
4 2 6
12
5
25 10 8 0 4
47

Observații:

  • variabila i se numește contor, deoarece ea contorizează numărul de execuții al buclei WHILE-DO. Pentru a executa o buclă de n ori inițializăm contorul cu 0 și ne oprim cînd devine egal cu n. Preferăm această variantă, față de a porni cu i de la 1, deoarece ne obișnuiește pentru viitor să lucrăm corect cu vectori.
  • Variabila suma se numește acumulator, deoarece în ea se acumulează rezultatul, pe măsură ce citim secvența. Orice variabilă de tip acumulator trebuie inițializată înainte de a începe calculele! În acest caz, deoarece este o sumă, ea se va inițializa cu 0, deoarece 0 este elementul neutru la adunare. Dacă am fi calculat produsul secvenței am fi inițializat acumulatorul cu 1, deoarece 1 este elementul neutru la înmulțire.

Numărul de elemente pare din secvență

Să se afișeze cîte elemente pare se află într-o secvență

Numărul de numere pare dintr-o secvență
 #include <stdio.h>

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

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

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

Numărul de elemente zero și diferite de zero din secvență

Să se calculeze cîte numere zero apar într-o secvență, precum și cîte numere diferite de zero.

Numărul de elemente nule și nenule dintr-o secvență
 #include <stdio.h>

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

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

   fout = fopen( "zero.out", "w" );
   fprintf( fout, "%d %d", zero, n - zero );
   fclose( fout );
   return 0;
 }

Căutare număr în secvență

Să se spună dacă un număr e apare într-o secvență și pe ce poziție. Dacă e apare în secvență se va afișa poziția primei apariții a lui, între 0 și n - 1. În caz contrar se va afișa n.

Prima apariție a unui număr într-o secvență
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, e, poz;

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

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

Observații:

  • Variabila poz are dublu rol. Pe de o parte ea memorează poziția primei apariții a numărului e în secvență. Pe de altă parte ea ne spune dacă am găsit numărul, astfel încît să ieșim din bucla WHILE-DO imediat ce am găsit numărul e. Variabilele care semnalează îndeplinirea unei condiții de oprire se numesc stegulețe, deci putem spune că variabila poz este un steguleț.

Elementul maxim într-o secvență

Dată o secvență de n numere să se afișeze elementul cel mai mare (maxim) din secvență.

#include <stdio.h>

int main(){
  int  n, i, nr, max;
  scanf( "%d", &n);           // citim numarul de valori din sir
  scanf( "%d", &nr );         // citim primul numar din sir
  max = nr;                    // initializam maximul cu prima valoare di sir
  for(i = 1; i < n; i++ ){          // mai avem de citit n-1 valori
    scanf( "%d", &nr );             // fiecare valoare citita
    if( nr > max )                  // daca noua valoare citita este mai mare decat maxim
      max = nr;                     // maximul va deveni acea valoare
  }
  printf( "%d", max );
  return 0;
}


Numărul maxim în secvență
 #include <stdio.h>

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

   fin = fopen( "maxim.in", "r" );
   fscanf( fin, "%d", &n );
   //citim prima val din sir si o punem direct in variabila maxim
   fscanf( fin, "%d", &max );
   for ( i = 1; i < n; i++ ) {
     fscanf( fin, "%d", &a );
     if ( max < a )
       max = a;
   }
   fclose( fin );

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

Observații:

  • De cate ori este posibil, vom initializa maximul cu prima valoare din sir ci nu cu o valoarea arbitrara.
  • Pentru a calcula elementul minim într-o secvență singurul lucru care se modifică în schema de mai sus este semnul comparației max < a, din mai mic < în mai mare >.

Elementul maxim într-o secvență si frecventa acestuia

Dată o secvență de n numere să se afișeze elementul cel mai mare (maxim) din secvență si numarul de aparitii ale acestuia ( frecventa maximului in sir ).

#include <stdio.h>

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

   fin = fopen( "maxim.in", "r" );
   fscanf( fin, "%d", &n );
   //citim prima val din sir si o punem direct in variabila maxim
   fscanf( fin, "%d", &max );
   for ( i = 1; i < n; i++ ) {
     fscanf( fin, "%d", &a );
     if ( max < a ){
       max = a;
       f = 1;
     }
     else if ( max == a )
       f ++;
   }
   fclose( fin );
   fout = fopen( "maxim.out", "w" );
   fprintf( fout, "%d", max );
   fclose( fout );
   return 0;
 }

Se citesc numere de la tastatură până la apariția lui zero. Să se determine câte dintre ele erau pare.

Laborator

Probleme de pe PBINFO

Probleme de pe VARENA

Tema

Codeforces