View source for Clasa a V-a lecția 12 - 26 oct 2017

= Tema – rezolvări =

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_11_-_19_oct_2017]

= Lecție =
<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2017-10-26-lectie-info-12-720p.mp4</html5media>
== Exerciții ==
Scrieți schema logică și programul C pentru următoarele probleme, folosind fișiere pentru citirea și scrierea datelor.

=== Număr conținut în alt număr ===
Să se spună de cîte ori un număr conține pe altul. Exemplu: 439453967 conține 39 de două ori, iar 2323232 conține 232 de 3 ori. Iată o variantă de algoritm. Acest algoritm nu funcționează într-un caz particular. Puteți spune cînd? Cum putem repara problema?
{|
| [[Image:sl-numar-in-numar.gif|frame|none|Apariții număr în număr]]
| valign="top"|<syntaxhighlight> #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, p, pc, p10, ap;

   fin = fopen( "aparitii.in", "r" );
   fscanf( fin, "%d%d", &n, &p );
   fclose( fin );

   // calculam numarul de cifre al lui p
   pc = p;
   p10 = 1;
   while ( pc > 0 ) {
     p10 = p10 * 10;
     pc = pc /10;
   }
   // comparam cu ultimele cifre ale lui n
   ap = 0;
   while ( n > 0 ) {
     if ( n % p10 == p )
       ap = ap + 1;
     n = n / 10;
   }

   fout = fopen( "aparitii.out", "w" );
   fprintf( fout, "%d\n", ap );
   fclose( fout );
   return 0;
 }</syntaxhighlight>
|}

=== Număr cu cifre distincte ===
Să se spună dacă un număr are toate cifrele distincte. Exemplu: 439453967 nu are cifre distincte, cifrele 3 și 9 apar de două ori în număr; Numărul 4539 are cifre distincte, nici o cifră a sa nu se repetă.

==== Rezolvarea 1 ====
O soluție posibilă este să luăm ultima cifră a numărului <code>n</code>, să o eliminăm din număr, iar apoi să verificăm că numărul rămas nu conține cifra. Dacă totul este în regulă reluăm procedeul cu numărul rămas. Repetăm pînă ce <code>n</code> rămîne de o singură cifră (care nu se poate repeta).

Iată o variantă posibilă pentru această soluție: 
{|
| [[Image:sl-numar-cifre-distincte.gif|frame|none|Număr cu cifre distincte]]
| valign="top"|<syntaxhighlight> #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, nc, cf;

   fin = fopen( "distincte.in", "r" );
   fscanf( fin, "%d", &n );
   fclose( fin );

   nc = 0;
   while ( n > 9 && nc == 0 ) {
     cf = n % 10;
     nc = n / 10;
     while ( nc > 0 && nc % 10 != cf )
       nc = nc / 10;
     n = n / 10;
   }

   fout = fopen( "distincte.out", "w" );
   if ( nc == 0 )
     fprintf( fout, "Cifre distincte\n" );
   else
     fprintf( fout, "Cifre nedistincte\n" );
   fclose( fout );

   return 0;
 }</syntaxhighlight>
|}

==== Rezolvarea 2 ====
O altă soluție ar putea fi să luăm toate cifrele de la 0 la 9 și să numărăm de cîte ori apar în numărul <code>n</code>. Ne oprim dacă găsim că o cifră apare de două sau mai multe ori (este OK să apară de zero ori sau o singură dată).

Iată o variantă posibilă pentru această soluție: 
{|
| [[Image:sl-numar-cifre-distincte-2.gif|frame|none|Număr cu cifre distincte varianta 2]]
| valign="top"|<syntaxhighlight> #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, cf, nc, ncf;

   fin = fopen( "distincte.in", "r" );
   fscanf( fin, "%d", &n );
   fclose( fin );

   cf = 0;
   ncf = 0;
   while ( cf < 10 && ncf < 2 ) {
     ncf = 0;
     nc = n;
     while ( nc > 0 ) {
       if ( nc % 10 == cf )
         ncf = ncf + 1;
       nc = nc / 10;
     }
     n = n / 10;
     cf = cf + 1;
   }

   fout = fopen( "distincte.out", "w" );
   if ( ncf < 2 )
     fprintf( fout, "Cifre distincte\n" );
   else
     fprintf( fout, "Cifre nedistincte\n" );
   fclose( fout );

   return 0;
 }</syntaxhighlight>
|}

Care variantă este mai bună? Să analizăm. Prima variantă testează strict cifrele distincte ale numărului, oprindu-se cînd găsește o cifră care se repetă. Astfel, ea va testa maxim toate cele zece cifre. A doua variantă va testa din start toate cele zece cifre, cu excepția cazului cînd găsește o cifră care apare de două sau mai multe ori. Drept care a doua variantă va testa întotdeauna mai multe cifre decît prima variantă. Prima variantă este deci mai bună.

== Secvențe ==
''Definiție'': denumim ''secvență'' un șir de numere. Exemplu: <tt>34 20 4 0 12 5 8 7</tt>. 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ță, <tt>n</tt> și apoi cele <tt>n</tt> numerele din secvență, într-o buclă WHILE-DO. Exemplu:
{|
| [[Image:sl-secventa-citire.gif|frame|none|Citire secvență]]
| valign="top"|<syntaxhighlight> fscanf( fin, "%d", &n );
 i = 0;
 while ( i < n ) {
   fscanf( fin, "%d", &a );
   i = i + 1;
 }</syntaxhighlight>
|}
=== Suma unei secvențe ===
Ca prim exemplu de lucru cu secvențe să calculăm suma a <tt>n</tt> numere citite la intrare:

{|
| [[Image:sl-secventa-suma.gif|frame|none|Suma unei secvențe]]
| valign="top"|<syntaxhighlight> #include <stdio.h>

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

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

   fout = fopen( "suma.out", "w" );
   fprintf( fout, "%d", suma );
   fclose( fout );
   return 0;
 }</syntaxhighlight>
|}
Exemple:
{| class="wikitable"
!Fișierul <tt>suma.in</tt>
!Fișierul <tt>suma.out</tt>
|-
| valign="top" | <tt>3<br/>4 2 6</tt>
| valign="top" | <tt>12</tt>
|-
| valign="top" | <tt>5<br/>25 10 8 0 4</tt>
| valign="top" | <tt>47</tt>
|}
Observații:

* variabila <tt>i</tt> se numește ''contor'', deoarece ea contorizează numărul de execuții al buclei WHILE-DO. Pentru a executa o buclă de <tt>n</tt> ori inițializăm contorul cu <tt>0</tt> și ne oprim cînd devine egal cu <tt>n</tt>. Preferăm această variantă, față de a porni cu <tt>i</tt> de la <tt>1</tt>, deoarece ne obișnuiește pentru viitor să lucrăm corect cu vectori.
* Variabila <tt>suma</tt> 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 <tt>0</tt>, deoarece <tt>0</tt> este elementul neutru la adunare. Dacă am fi calculat produsul secvenței am fi inițializat acumulatorul cu <tt>1</tt>, deoarece <tt>1</tt> 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ță
{|
| [[Image:sl-secventa-nr-pare.gif|frame|none|Numărul de numere pare dintr-o secvență]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}

=== 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.
{|
| [[Image:sl-secventa-nr-zero.gif|frame|none|Numărul de elemente nule și nenule dintr-o secvență]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}
=== Căutare număr în secvență ===
Să se spună dacă un număr <tt>e</tt> apare într-o secvență și pe ce poziție. Dacă <tt>e</tt> apare în secvență se va afișa poziția primei apariții a lui, între <tt>0</tt> și <tt>n - 1</tt>. În caz contrar se va afișa <tt>n</tt>.
{|
| [[Image:sl-secventa-cautare-element.gif|frame|none|Prima apariție a unui număr într-o secvență]]
| valign="top"|<syntaxhighlight> #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;
 }</syntaxhighlight>
|}
Observații:

* Variabila <tt>poz</tt> are dublu rol. Pe de o parte ea memorează poziția primei apariții a numărului <tt>e</tt> î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 <tt>e</tt>. Variabilele care semnalează îndeplinirea unei condiții de oprire se numesc ''stegulețe'', deci putem spune că variabila <tt>poz</tt> este un ''steguleț''.

= Tema =
* [http://varena.ro/runda/2017-10-26-clasa-5-tema-12 Tema 12]: să se rezolve următoarele probleme (schemă logică + program C în CodeBlocks, trimis la vianuarena):
** [http://varena.ro/problema/pinochio pinochio] dată la OJI 2003 clasa a 5<sup>a</sup>
** [http://varena.ro/problema/pozitii poziții]
* Problemă de logică: dispunem de 3000 de banane pe care vrem să le transportăm din orașul A în orașul B aflate la 1000km distanță. Dispunem de o cămilă care poate să care maxim 1000 de banane. În timp ce mergea ea mănîncă o banană la fiecare kilometru. Care este numărul maxim de banane pe care le puteți duce din A în B și cum procedați? Puteți desigur să depozitați banane în orice loc de pe drum.

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_12_-_26_oct_2017]