Difference between revisions of "Clasa a V-a lecția 26 - 14 feb 2020"

From Algopedia
Jump to navigationJump to search
 
Line 104: Line 104:
  
 
     return 0;
 
     return 0;
 +
}</syntaxhighlight>
 +
 +
= Tema - rezolvări =
 +
== Problema culori ==
 +
Problema [http://varena.ro/problema/culori culori] cere să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordine crescătoare.
 +
 +
Atenție la următoarele greșeli uzuale:
 +
 +
* Vectorul de culori declarat ca <tt><nowiki>int v[99]</nowiki></tt>. Greșit, vectorul are <tt>100</tt> de elemente, iar ultimul element este <tt><nowiki>v[99]</nowiki></tt>. Vectorul trebuie declarat ca <tt><nowiki>int v[100]</nowiki></tt>, altfel vom depăși vectorul atunci cînd apelăm <tt><nowiki>v[99]</nowiki></tt>, deoarece acest element ar fi în afara vectorului.
 +
* Parcurgerea vectorului de la <tt>1</tt> la <tt>100</tt>, inclusiv <tt>100</tt> la afișarea culorilor. Greșit, ultima culoare posibilă este <tt>99</tt>.
 +
 +
Problema culori ne învață să ordonăm numere naturale, atunci cînd numerele naturale nu sînt foarte mari. În cazul nostru avem de ordonat culori, care sînt numere între <tt>1</tt> și <tt>99</tt>. Pentru aceasta vom folosi un vector de frecvență de <tt>100</tt> de elemente. Să nu uităm că elementele vor fi numerotate de la <tt>1</tt> la <tt>99</tt>. Pe măsură ce citim culorile adunăm unu la poziția acelei culori în vectorul de frecvență. '''Observație''': nu avem nevoie să păstrăm culorile în alt vector! Odată calculat vectorul de frecvență îl vom parcurge de la <tt>1</tt> la <tt>99</tt> afișînd indicele <tt>i</tt> de cîte ori ne arată elementul <tt><nowiki>v[i]</nowiki></tt>.
 +
 +
Această ordonare (sau sortare) se mai numește și ''sortare prin numărare'' ([http://en.wikipedia.org/wiki/Counting_sort counting sort]). Iată o soluție bazată pe această idee:
 +
 +
<syntaxhighlight>#include <stdio.h>
 +
 +
int v[100];
 +
 +
int main() {
 +
  FILE *fin, *fout;
 +
  int n, i, culoare;
 +
 +
  fin = fopen( "culori.in", "r" );
 +
  fscanf( fin, "%d", &n );
 +
  for ( i = 0; i < n; i++ ) {
 +
    fscanf( fin, "%d", &culoare );
 +
    v[culoare]++;
 +
  }
 +
  fclose( fin );
 +
 +
  fout = fopen( "culori.out", "w" );
 +
  for ( cul = 1; cul < 100; culoare++ )
 +
    while ( v[culoare] > 0 ) {
 +
      fprintf( fout, "%d ", culoare );
 +
      v[culoare]--;
 +
    }
 +
  fclose( fout );
 +
 +
  return 0;
 +
}</syntaxhighlight>
 +
 +
== Problema tastatura 1 ==
 +
Problema [http://varena.ro/problema/tastatura1 tastatura 1] este un exerciţiu de lucru cu caractere şi compunerea valorilor unor numere întregi pornind de la caracterele cifre ce le constituie. Am mai întîlnit aceste două elemente în problema [http://varena.ro/problema/fgetc fgetc].
 +
 +
Pentru rezolvare vom citi caracterele de la intrare pînă la final de linie, <code>'\n'</code>, ignorînd caracterele <code>'#'</code>. Vom adăuga caracterele cifră la coada unui număr <code>n</code>, întocmai ca la problema [http://varena.ro/problema/fgetc fgetc]. Cînd întîlnim un caracter <code>'+'</code> vom adăuga numărul <code>n</code> la sumă. Mare atenție la un caz particular: ultimul număr nu va avea un caracter <code>'+'</code> după el, deci va trebui adăugat special la sumă.
 +
 +
Iată o soluție posibilă:
 +
 +
<syntaxhighlight>#include <stdio.h>
 +
 +
int main() {
 +
  FILE *fin, *fout;
 +
  char c;
 +
  int numar, suma;
 +
 
 +
  fin = fopen( "tastatura1.in", "r" );
 +
  c = fgetc( fin );
 +
  suma = 0;
 +
  numar = 0;
 +
  while ( c != '\n' ) { // citim pina la final de linie
 +
    if ( c != '#' ) {  // caracterele # se ignora
 +
      if ( c == '+' ) { // s-a incheiat numarul, il adunam la suma
 +
        suma = suma + numar;
 +
        numar = 0;
 +
      } else            // altfel este o cifra deghizata in litera mare
 +
        numar = numar * 10 + c - 'A';
 +
    }
 +
    c = fgetc( fin );
 +
  }
 +
  suma = suma + numar; // ultimul numar nu are plus dupa el, deci il adunam separat
 +
  fclose( fin );
 +
 +
  fout = fopen( "tastatura1.out", "w" );
 +
  fprintf( fout, "%d\n", suma );
 +
  fclose( fout );
 +
 +
  return 0;
 
}</syntaxhighlight>
 
}</syntaxhighlight>

Latest revision as of 09:22, 14 February 2020

Tema - rezolvări

Problema cfdist

Problema cfdist cere de fapt să se calculeze numărul de cifre distincte ale unui număr. El se poate calcula ușor astfel: extragem în mod repetat ultima cifră c a numărului, avînd grijă să setăm vectorul de frecvență pe 1 la poziția c. În final parcurgem elementele vectorului de frecvență și numărăm cîte elemente 1 avem. Iată o soluție posibilă:

#include <stdio.h>

int v[10];

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

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

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

  nrcf = 0;
  for ( cf = 0; cf < 10; cf++ )
    nrcf += v[cf];

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

  return 0;
}

De remarcat că nu avem nevoie de numărul de apariții al cifrelor, de aceea stocăm unu, ori de cîte ori apare o cifră. Aceasta ne permite ca la final să calculăm suma elementelor vectorului de frecvență, fără a mai testa dacă valorile sînt zero.

Problema maxnr

Problema maxnr cere să se afişeze cel mai mare număr care se poate forma cu cifrele unui număr. Prima parte a rezolvării problemei este foarte similară cu problema anterioară (cfdist): vom construi vectorul de frecvență al cifrelor numărului, de data asta adunînd 1 pentru fiecate cifră. Apoi vom parcurge vectorul în sens invers, afișînd poziția curentă i de cîte ori ne spune elementul v[i]. Iată o rezolvare posibilă:

#include <stdio.h>

int v[10];

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

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

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

  fout = fopen( "maxnr.out", "w" );
  for ( cf = 9; cf >= 0; cf-- )
    while ( v[cf] > 0 ) {
      fprintf( fout, "%d", cf );
      v[cf]--;
    }
  fclose( fout );

  return 0;
}

Problema plus

Problema plus poate părea la prima vedere o problema care se rezolvă cu vectori: fiecare cifră o așezăm în vectori și apoi facem operațiile aferente. Nu este o rezolvare rea, dar se poate rezolva foarte simplu prin manipularea cifrelor numărului. Scopul problemei era să vă determin să faceți diferența când trebuie să folosim sau nu vectori.

Iată o posibilă rezolvare:

#include <stdio.h>
int main()
{
    FILE *fin = fopen ( "plus.in", "r" );
    FILE *fout = fopen ( "plus.out", "w" );
    int  numar, masca, invers;
    fscanf( fin , "%d" , &numar );
    masca = 0; 
    inv = 0;

    // primul pas reprezintă răsturnarea numărului; 
    // în acest proces, avem grijă să adăugăm deja +1 
    while( numar ) { //adica cat timp există
        masca = masca * 10 + 1;
        invers = invers * 10 + numar % 10 ;
        numar = numar / 10;
    }

    fprintf( fout, "%d\n" , invers % 10 ); //afișăm prima cifră a numărului
    numar = masca + invers;
    invers = 0;

    // al doilea pas este să răsturnăm iarăși numărul;
    // astfel, îl aducem în forma corectă pentru afișare
    while( numar ) {
        invers = invers * 10 + numar % 10;
        numar = numar / 10;
    }

    fprintf( fout, "%d\n" , invers );
    fclose( fin );
    fclose ( fout );

    return 0;
}

Tema - rezolvări

Problema culori

Problema culori cere să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordine crescătoare.

Atenție la următoarele greșeli uzuale:

  • Vectorul de culori declarat ca int v[99]. Greșit, vectorul are 100 de elemente, iar ultimul element este v[99]. Vectorul trebuie declarat ca int v[100], altfel vom depăși vectorul atunci cînd apelăm v[99], deoarece acest element ar fi în afara vectorului.
  • Parcurgerea vectorului de la 1 la 100, inclusiv 100 la afișarea culorilor. Greșit, ultima culoare posibilă este 99.

Problema culori ne învață să ordonăm numere naturale, atunci cînd numerele naturale nu sînt foarte mari. În cazul nostru avem de ordonat culori, care sînt numere între 1 și 99. Pentru aceasta vom folosi un vector de frecvență de 100 de elemente. Să nu uităm că elementele vor fi numerotate de la 1 la 99. Pe măsură ce citim culorile adunăm unu la poziția acelei culori în vectorul de frecvență. Observație: nu avem nevoie să păstrăm culorile în alt vector! Odată calculat vectorul de frecvență îl vom parcurge de la 1 la 99 afișînd indicele i de cîte ori ne arată elementul v[i].

Această ordonare (sau sortare) se mai numește și sortare prin numărare (counting sort). Iată o soluție bazată pe această idee:

#include <stdio.h>

int v[100];

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

  fin = fopen( "culori.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &culoare );
    v[culoare]++;
  }
  fclose( fin );

  fout = fopen( "culori.out", "w" );
  for ( cul = 1; cul < 100; culoare++ )
    while ( v[culoare] > 0 ) {
      fprintf( fout, "%d ", culoare );
      v[culoare]--;
    }
  fclose( fout );

  return 0;
}

Problema tastatura 1

Problema tastatura 1 este un exerciţiu de lucru cu caractere şi compunerea valorilor unor numere întregi pornind de la caracterele cifre ce le constituie. Am mai întîlnit aceste două elemente în problema fgetc.

Pentru rezolvare vom citi caracterele de la intrare pînă la final de linie, '\n', ignorînd caracterele '#'. Vom adăuga caracterele cifră la coada unui număr n, întocmai ca la problema fgetc. Cînd întîlnim un caracter '+' vom adăuga numărul n la sumă. Mare atenție la un caz particular: ultimul număr nu va avea un caracter '+' după el, deci va trebui adăugat special la sumă.

Iată o soluție posibilă:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  char c;
  int numar, suma;
  
  fin = fopen( "tastatura1.in", "r" );
  c = fgetc( fin );
  suma = 0;
  numar = 0;
  while ( c != '\n' ) { // citim pina la final de linie
    if ( c != '#' ) {   // caracterele # se ignora
      if ( c == '+' ) { // s-a incheiat numarul, il adunam la suma
        suma = suma + numar;
        numar = 0;
      } else            // altfel este o cifra deghizata in litera mare
        numar = numar * 10 + c - 'A';
    }
    c = fgetc( fin );
  }
  suma = suma + numar; // ultimul numar nu are plus dupa el, deci il adunam separat
  fclose( fin );

  fout = fopen( "tastatura1.out", "w" );
  fprintf( fout, "%d\n", suma );
  fclose( fout );

  return 0;
}