Clasa a V-a lecția 22 - 25 ian 2018

From Algopedia
Jump to navigationJump to search

Anunț

Duminică 28 ianuarie 2018 la ora 15:30 vom avea un concurs de pregătire pentru olimpiada pe sector. Concursul se va desfășura la varena.ro, va cere rezolvarea a două probleme și va dura trei ore, întocmai ca olimpiada pe sector. La terminarea concursului problemele vor fi adăugate la tema lecției 22.

Tema - comentarii

  • Vectorii de frecvență ai cifrelor au zece elemente și se declară int v[10]. Avem zece cifre, nu?
  • La „culori” culorile încep de la 1, nu de la zero.
  • Vectorul de frecvență al culorilor are 100 de elemente, nu 99, deoarece ultima culoare (ultimul element al vectorului) este 99. Se declară int v[100]
  • Pentru a scrie o buclă while de la 9 la 0 puteți scrie for ( i = 9; i >= 0; i-- ). Unii dintre voi ați tratat special cazul zero, nu era cazul.
  • La problema cfdist puteați stoca doar zero și unu în elementele vectorului de frecventa, nu era necesar sa calculati numărul de aparitii ale fiecarei cifre. Puteați apoi să însumați elementele vectorului.
  • Unii din voi uitați să închideți fișiere: Cadîr, Fares, Nicu. Este greu să scăpați de năravul freopen, nu-i așa?
  • Folosiți cu încredere for pentru cicluri cu număr cunoscut de pași.

Tema - rezolvări

Rezolvări aici [1]

Lecţie

Probleme cu vectori de frecvență.

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-01-25-lectie-info-22-720p.mp4</html5media>

Problema cifre comune

Problema cifre comune este relativ ușor de rezolvat folosind doi vectori de frecvență, cîte unul pentru fiecare număr, pe care îi vom construi în mod corespunzător, apoi îi vom compara element cu element, adunînd unu la contorul de cifre atunci cînd ambele elemente sînt diferite de zero. Vom încerca să rezolvăm problema cu extra credit :). Pentru aceasta vom construi vectorul de frecvență al primului număr, m. El va avea numai elemente zero și unu. Apoi vom extrage pe rînd cifrele lui n. Dacă ele apar în vectorul de frecvență vom face două lucruri: vom aduna unu la contorul de cifre comune și vom șterge acea cifră din vectorul de frecvență, setînd acel element pe zero, pentru ca în viitor să nu o mai luăm din nou în considerare dacă cifra apare de mai multe ori în n. Iată o rezolvare bazată pe aceste idei:

#include <stdio.h>

int v[10];

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

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

  // setam 1 pentru cifrele lui m
  while ( m > 0 ) {
    cf = m % 10;
    v[cf] = 1;
    m = m / 10;
  }

  nrcf = 0;
  // testam cifrele lui n, resetind cifrele deja gasite, pentru a nu le
  // gasi de mai multe ori
  while ( n > 0 ) {
    cf = n % 10;
    if ( v[cf] == 1 ) {
      nrcf++;
      v[cf] = 0;
    }
    n = n / 10;
  }

  fout = fopen( "cfcomune.out", "w" );
  fprintf( fout, "%d", nrcf );
  fclose( fout );

  return 0;
}

Problema minnr

Problema minnr este foarte similară cu problema maxnr, doar că de data aceasta vom afișa cifrele în ordinea lor crescătoare. Trebuie să avem însă grijă deoarece nu putem să începem cu cifra 0! De aceea vom afișa mai întîi cea mai mică cifră diferită de zero din vectorul de frecvență. Apoi vom scădea unu de la acea poziție, ca să știm că am afișat-o. Abia apoi putem trece la afișarea întregului vector de la mic la mare fără să ne mai pese de cifrele 0. Iată o soluție posibilă:

#include <stdio.h>

int v[10];

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

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

  while ( n > 0 ) {
    cf = n % 10;
    v[cf]++;
    n = n / 10;
  }

  fout = fopen( "minnr.out", "w" );
  // cauta cea mai mica cifra diferita de zero
  cf = 1;
  while ( v[cf] == 0 )
    cf++;
  fprintf( fin, "%d", cf ); // afiseaza prima cifra
  v[cf]--;                  // scoate-o din numar

  // afiseaza restul cifrelor, in ordine crescatoare
  for ( cf = 0; cf < 10; cf++ )
    while ( v[cf] > 0 ) {
      fprintf( fout, "%d", cf );
      v[cf]--;
    }
  fclose( fout );

  return 0;
}

Temă

Atenţie: rezolvaţi problemele următoare folosind vectori de frecvenţă! Acesta este scopul temei.

Tema 22: să se rezolve următoarele probleme (program C trimis la vianuarena):

Rezolvări aici [2]