Clasa a V-a lecția 13 - 4 nov 2014

From Algopedia
Jump to: navigation, search

Tema – verificare

Rezolvări aici [1]

Lecție

Instrucțiunea de incrementare/decrementare

Atunci cînd adunăm unu la o variabilă se cheamă că o incrementăm. De asemenea, cînd scădem unu, se cheamă că o decrementăm. Deoarece aceste două operații apar foarte frecvent limbajul C ne permite să le scriem mai scurt.

Instrucțiune Instrucțiune echivalentă
i = i + 1; i++;
i = i - 1; i--;

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
Sl-bucla-for.gif
 i = 0;
 while ( i < n ) {
   ... execută corpul
       buclei...
   i = i + 1;
 }
 for ( i = 0; i < n; i++ ) {
   ... execută corpul
       buclei...
 }

Atenție! Observații importante:

  • Instrucțiunea de incrementare a contorului (i++) se execută întotdeauna la finalul buclei for, imediat înainte de revenirea la condiție.
  • Cele două implementări sînt absolut echivalente, nu este una mai bună ca cealaltă. În fapt, atunci cînd scrieți o instrucțiune for compilatorul o traduce automat în instrucțiunea echivalentă while. Nu este absolut nici o problemă dacă nu vreți să folosiți instrucțiunea for, este doar o opțiune mai succintă pentru cei ce vor să scrie mai puțin, dar nu este obligatorie.
  • La cercul nostru vom respecta următoarele convenții:
    • Vom folosi instrucțiunea for strict pentru buclele cu număr cunoscut de pași. Atunci cînd bucla WHILE-DO se poate executa de un număr necunoscut de ori vom folosi instrucțiunea mai generală while.
    • În interiorul unei instrucțiuni for nu avem voie să modificăm variabila contor a ciclului, adică i ! Dacă dorim să facem acest lucru vom folosi în loc o instrucțiune while.

Exerciții cu secvențe

Elementul maxim într-o secvență

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

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 );
   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:

  • Elementul maxim se inițializează cu primul element al șirului nu cu valoarea zero. Întotdeauna vom inițializa maximul cu un element al secvenței. De ce?
    • Este bine să fim ordonați și consecvenți: max este doar un candidat la maxim, dintre elementele secvenței, pînă la final, cînd devine chiar maximul. Ce fel de candidat este el dacă este un străin, nici măcar nu face parte din secvență?
    • În viitor putem avea și elemente negative.
    • Dacă avem o greșeală în program detecția ei și corectura sînt mai grele atunci cînd max poate lua valori în afara elementelor din secvență.
  • 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 >.

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.

Temă

  • Problema monotonă (schemă logică + program C)
  • Problema mulțimi dată la OJI 2005 clasa a 5a (schemă logică + program C).
  • Problemă 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?

Rezolvări aici [2]