Clasa a V-a lecția 21 - 18 ian 2018

From Algopedia
Jump to: navigation, search

Anunț

Uitați-vă vă rog pe rezolvările la teme postate pe acest site și comparați-le cu rezolvările voastre, încercînd să vă dați seama de diferențe și de ce sau dacă rezolvarea postată pe algopedia este mai bună. De multe ori rezolvarea voastră este ineficientă şi lungă, uneori dublă sau triplă ca număr de linii. Nu postez aceste rezolvări pentru mine, ci pentru voi, pentru a putea învăța ceva. Chiar dacă ați rezolvat problemele trebuie să vă uitați și la rezolvările postate aici.

Tema - rezolvări

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 n, s;
  
  fin = fopen( "tastatura1.in", "r" );
  c = fgetc( fin );
  s = 0;
  n = 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
        s = s + n;
        n = 0;
      } else            // altfel este o cifra deghizata in litera mare
        n = n * 10 + c - 'A';
    }
    c = fgetc( fin );
  }
  s = s + n; // ultimul numar nu are plus dupa el, deci il adunam separat
  fclose( fin );

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

  return 0;
}

Problema tastatura 2

Problema tastatura 2 este similară cu tastatura 1, ea fiind, la fel, un exerciţiu de lucru cu caractere şi compunerea valorilor unor numere întregi pornind de la caracterele cifre ce le constituie.

Pentru rezolvare, în mod similar, vom citi caracterele de la intrare pînă la final de linie, '\n', ignorînd caracterele duplicat (ce sînt egale cu caracterul din-naintea lor). Vom adăuga caracterele cifră la coada unui număr n. Cînd întîlnim un caracter '+' vom adăuga numărul n la sumă. Mare atenție și aici la cazul particular al ultimului număr care 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, uc;
  int n, k, s;
  
  fin = fopen( "tastatura2.in", "r" );
  fscanf( fin, "%d", &k );
  fgetc( fin );
  s = 0;
  n = 0;
  c = fgetc( fin );
  uc = 'a'; // ceva care nu exista in sirul de la intrare
  while ( c != '\n' ) { // citim pina la final de linie
    if ( c != uc )      // caracterele duplicat se ignora
      if ( c == '+' ) { // s-a incheiat numarul, il adunam la suma
        s = s + n;
        n = 0;
      } else            // altfel este o cifra deplasata cu k
        n = n * 10 + (c - '0' + 10 - k) % 10;
    uc = c;
    c = fgetc( fin );
  }
  s = s + n; // ultimul numar nu are plus dupa el, deci il adunam separat
  fclose( fin );

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

  return 0;
}

Problema bomboane 1

Problema bomboane 1 este un exerciţiu de lucru cu caractere şi cu divizorii unui număr. Ea cere să efectuăm adunări şi scăderi asupra sumei de bomboane, iar, în final, să calculăm cel mai mic divizor diferit de unu al numărului de bomboane.

La primul punct vom citi caracter cu caracter. Dacă este semnul dolar îl vom ignora. Dacă este cifră o vom adăuga la numărul pe care îl construim. Cînd dăm peste caracterele C sau P scădem sau adunăm numărul curent avînd grijă să nu facem scăderile decît dacă avem destule bomboane.

La punctul doi vom căuta primul divizor, începînd cu 2. Ştim sigur că vom avea un divizor, deoarece în cel mai rău caz vom da toate bomboanele unui copil.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  char c;
  int suma, nr, d;

  // citire si calcul numar bomboane in 'suma'
  fin = fopen( "bomboane1.in", "r" );
  suma = nr = 0;
  c = fgetc( fin );
  while ( c != '\n' ) {
    if ( c != '$' ) {
      if ( c == 'P' ) { // primeste nr bomboane
        suma = suma + nr;
        nr = 0;
      } else if ( c == 'C' ) { // i se cer nr bomboane
        if ( nr <= suma )      // Diana da numai daca are 'nr' bomboane
          suma = suma - nr;
        nr = 0;
      } else { // inseamna ca este cifra, o adaugam la nr
        nr = nr * 10 + c - '0';
      }
    }
    c = fgetc( fin );
  }
  fclose( fin );

  // calcul numar bomboane per copil
  // numarul este cel mai mic divizor strict mai mare ca 1
  // el exista intotdeauna, putem da toate bomboanele unui singur copil
  d = 2;
  while ( suma % d > 0 )
    d++;

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

  return 0;
}

Problema numere1

Rezolvare problema numere1 la vianuarena (problemă dată la concursul Urmaşii lui Moisil - V-VIII 2012).

Ideea de rezolvare este simplă, dar trebuie să avem grijă la detalii și cazuri limită. O idee posibilă este să căutăm primul divizor al lui n, sa-i spunem d. El va fi obligatoriu număr prim. Îl împărțim pe n la d. Apoi testăm încă o dată dacă n se împarte la d. Dacă se mai împarte o dată, numărul nu poate fi aproape prim. Dacă nu, reluăm, căutăm primul divizor al noului n, pornind de la d în sus. Dacă nu găsim nici un divizor înseamnă că noul n este prim și numărul original este aproape prim.

Atenție! Pentru a lua 100p la aceasta problemă este important să nu verificăm divizorii mai mari decît sqrt(n). Cei care verifică divizorii pînă la n, sau n/2, vor depăși timpul la cîteva teste.

Iată soluția bazată pe această idee, cu comentarii:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, nr, nap, d;

  nap = 0;
  fin = fopen( "numere1.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &nr );
    d = 2;
    while ( d * d < nr && nr % d > 0 ) // pentru a fi aproape prim trebuie ca
      d++;                // nr sa aiba un divizor strict mai mic ca sqrt(nr)
    if ( d * d < nr ) {   // am gasit un divizor propriu
      nr = nr / d;        // il "curatam" din nr
      if ( nr % d > 0 ) { // n-are voie sa-l mai imparta o data
        while ( d * d <= nr && nr % d > 0 ) // cautam in continuare
          d++;            // de data asta pina la sqrt(nr) inclusiv
        if ( d * d > nr ) // inseamna ca ce a ramas din nr este prim
          nap++;          // numarul original era aproape prim
      }
    }
  }
  fclose( fin );

  fout = fopen( "numere1.out", "w" );
  fprintf( fout, "%d", nap );
  fclose( fout );

  return 0;
}

Rezolvări aici [1]

Lecție

Vectori

Uneori avem nevoie să lucrăm cu multe variabile de același tip. De exemplu, la problema cifre comune am putea folosi zece variabile, a_0, a_1, ..., a_9, ce numără aparițiile respectivelor cifre în numărul a. Similar pentru b. Apoi am putea calcula numărul minim de apariții ale fiecărei cifre din a și b pe baza acestor variabile. Suma numărului minim de apariții este răspunsul la problemă. Unii din voi au şi rezolvat problema aşa, folosind 20 de variabile!

Cele zece variabile au ceva în comun: toate reprezintă valori de același tip, enumerate la rînd conform cifrelor. Această situație apare foarte des în algoritmi. De aceea a apărut conceptul de vector.

Definiție: vectorul este o colecție de valori de același tip (întreg, caracter, sau alte tipuri), valori ce pot fi accesate după un indice, sau poziție, care se mai cheamă și indicele în vector al acelei valori.

Exemplu:

Exemplu de vector cu n elemente

În acest exemplu avem un vector v care conține n valori de tip întreg. Cele n valori pot fi accesate folosind indicele lor, sau poziția lor, de la 0 la n-1, înscrisă în desen sub fiecare din căsuțe. Elementul de pe poziția 2 este accesat ca v[2]. Așa cum la matematică scriem

v = v0, v1, v2, ..., vn-2, vn-1

în limbajul C scriem

v[0], v[1], v[2], ..., v[n-2], v[n-1]

În cazul nostru v[0] are valoarea 9, v[1] are valoarea 5, v[2] are valoarea 12, și așa mai departe.

Observație importantă: pozițiile, sau indicii elementelor încep de la zero, nu de la unu. Astfel, dacă avem un vector de 10 elemente, ele vor fi numerotate de la 0 la 9. Elementul v[10] nu există, deorece ar fi al 11-lea element.

De ce se întîmplă acest lucru? Nu ar fi mai natural ca primul element să fie elementul unu, și nu elementul zero? Răspunsul este nu. Gîndiți-vă că deși parterul este primul etaj nu îi spunem etajul unu, ci parter. El este totuna cu etajul zero. Etajul unu este următorul. De ce facem așa? Pentru că așa ne-am obișnuit. Americanii consideră parterul ca etajul unu, spre deosebire de noi. Deci nu există o regulă clară. Cînd avem o secvență de elemente le putem numerota fie ca "al cîtelea element este", caz în care primul element va fi unu, fie ca "distanța lui față de începutul secvenței", caz în care primul element este zero. În cazul vectorilor există avantaje în a numerota elementele de la zero. Ele vor deveni evidente în următoarele lecții, este vorba despre parcurgerea circulara a vectorilor și alte relații matematice.

O variabilă de tip vector stochează mai multe valori. De aceea tipul vector se mai numește și tip compus de date, prin opoziție cu tipurile simple de date pe care le-am învățat pînă acum, respectiv întreg și caracter, care stochează o singură valoare.

Declararea vectorilor

Ca orice variabilă C, vectorii trebuie declarați. Vectorul din exemplul de mai sus se declară astfel:

int v[100];

Numărul dintre parantezele pătrate reprezintă numărul de elemente (valori) al vectorului, iar int reprezintă tipul fiecărei valori. Să nu uităm că toate valorile unui vector trebuie să aibă același tip. Nu se poate ca v[1] să fie de tip int, iar v[2] de tip char. Nu uitați că ultimul element din acest vector este v[99], deoarece v[100] ar fi in afara vectorului.

În ce secțiune a programului C declarăm vectorii? În mod normal vectorii se declară împreună cu celelalte variabile la începutul programului C, imediat după main(). Dar noi vom face o excepție de la regulă și-i vom declara imediat înainte de main(), astfel:

#include <stdio.h>

int v[100];

int main() {
  ...
  return 0;
}

Există două motive pentru aceasta:

  1. Vectorii ocupă mai multă memorie decît variabilele simple, ceea ce duce la probleme cu compilatoarele comisiei de corectură la olimpiada de informatică și alte concursuri. Veți înțelege mai multe pe măsură ce învățăm despre limbajul C.
  2. Variabilele declarate în afara lui main() sînt automat inițializate cu zero. De cele mai multe ori vrem ca toate elementele unui vector să fie la început zero. Această declarare ne scutește să mai scriem instrucțiuni speciale pentru aceasta.

Atribuirea vectorilor

Cum dăm valori unui vector? Fiecare element al vectorului este o variabilă separată, care poate fi atribuită, citită sau scrisă întocmai ca o variabilă de tipul vectorului. Exemple:

v[3] = 23;
v[i] = v[i] + 1;

Citirea vectorilor

Citirea mai multor valori dintr-un fișier și introducerea lor într-un vector se face similar cu citirea unei secvențe: vom citi mai întîi numărul de elemente, n și apoi cele n elemente, de la 0 la n-1:

fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ )
  fscanf( fin, "%d", &v[i] );

Acum înțelegeți de ce v-am cerut ca la citirea unei secvențe de numere să variați contorul de la 0 la n-1 și nu de la 1 la n: deoarece la citirea unui vector este important acest lucru și am vrut să vă obișnuiesc corect :-) Remarcați faptul că nu putem folosi o singură instrucțiune de citire pentru întregul vector. Valorile vectorului trebuie citite separat.

Afișarea vectorilor

Afișarea valorilor vectorului este similară cu citirea. Vom scrie în fișierul de ieșire fiecare valoare, pe rînd:

for ( i = 0; i < n; i++ )
  fprintf( fout, "%d ", v[i] );

Inițializarea vectorilor

Precum am văzut dacă declarăm vectorii deasupra lui main() ei vor fi automat inițializați cu zero. Cum procedăm dacă avem nevoie ca valorile vectorului să fie inițializate cu o altă valoare? Iată un exemplu care inițializează toate valorile vectorului v cu 1:

for ( i = 0; i < n; i++ )
  v[i] = 1;

Maximul dintr-un vector

Exercițiu: să se citească un vector de n elemente și să se afișeze valoarea maximă din acest vector. Precum știm, nu avem nevoie să folosim un vector pentru această problemă. O vom face pentru a ne obișnui cu vectorii. Iată soluția:

#include <stdio.h>

int v[100];

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

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

  max = v[0];
  for ( i = 1; i < n; i++ )
    if ( max < v[i] )
      max = v[i];

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

  return 0;
}

Suma elementelor unui vector

Exercițiu: să se citească un vector de n elemente și să se afișeze suma elementelor lui. La fel, nu avem nevoie de vector, dar îl vom folosi pentru a ne obișnui. Iată soluția:

#include <stdio.h>

int v[100];

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

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

  sum = 0;
  for ( i = 0; i < n; i++ )
    sum = sum + v[i];

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

  return 0;
}

Căutarea unui element în vector

Exercițiu: se citesc n şi e numere naturale, iar apoi se citesc n numere. Să se spună prima poziție pe care apare elementul e. Dacă elementul e nu se află în vector vom afișa poziția n (în afara vectorului).

Soluție: vom citi cele n valori într-un vector, iar apoi vom porni de la poziția 0 și vom înainta fie pînă ce găsim elementul e, fie pînă cînd ajungem la poziția n, în afara vectorului. Iată soluția:

#include <stdio.h>

int v[100];

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

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

  i = 0;
  while ( i < n && v[i] != e ) // cita vreme sintem inca in vector
      i++;                     // si nu l-am gasit pe e, avansam i

  fout = fopen( "cautare.out", "w" );
  fprintf( fout, "%d", i );
  fclose( fout );

  return 0;
}

Căutarea unui element în vector după poziţia k

Exercițiu: se citesc n, e și k numere naturale, iar apoi se citesc n numere. Să se spună prima poziție după poziția k pe care apare elementul e. Dacă ajungem la ultima poziție, n-1, avem voie să începem din nou cu zero, deoarece se consideră că cele n numere sînt așezate în cerc. Dacă elementul e nu se află în vector vom afișa poziția n (în afara vectorului).

Soluție: vom citi cele n valori într-un vector, iar apoi vom porni de la poziția k și vom înainta fie pînă ce găsim elementul e, fie pînă cînd ajungem la poziția k din nou. Avansul indicelui i se va face modulo n. Iată soluția:

#include <stdio.h>

int v[100];

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

  fin = fopen( "cautarek.in", "r" );
  fscanf( fin, "%d%d%d", &n, &e, &k );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  i = k;
  if ( v[i] != e ) {               // daca pe pozitia k nu avem e
    i = (i + 1) % n;               // avansam indicele i
    while ( i != k && v[i] != e )  // cita vreme nu ne-am intors la k
      i = (i + 1) % n;             // si v[i] diferit de e, avansam i
  }

  if ( v[i] != e )                 // daca nu am gasit e, setam i pe n
    i = n;
  fout = fopen( "cautarek.out", "w" );
  fprintf( fout, "%d", i );
  fclose( fout );

  return 0;
}

Observăm că pentru a începe din nou de la zero atunci cînd i devine n este deajuns să aplicăm funcția %n lui i. Acest lucru este posibil tocmai pentru că indicii vectorului v încep de la 0.

Vectori de frecvență (vectori caracteristici)

Vectorii de frecvență sînt vectori ale căror elemente au o semnificație specială: valoarea de pe poziția i arată numărul de apariții (sau frecvența) lui i într-o altă entitate, de obicei o secvență de numere, sau un număr. De exemplu, dacă avem o secvență de 10 numere cuprinse între 0 și 4 putem construi un vector de 5 elemente în care v[i] reprezintă numărul de apariții ale numărului i în secvența originală. Exemplu:

Fie secvența

3 2 0 3 4 1 2 0 2 2

Atunci vectorul ei de frecvență, sau vectorul caracteristic este

Vectorul de frecvență al secvenței

v[0] este 2 deoarece 0 apare de două ori în secvența originală, v[1] este 1 deoarece 1 apare o dată, 2 apare de 4 ori, 3 apare de 2 ori și 4 apare o dată. Observați că suma elementelor vectorului a este egală cu numărul de numere din secvența originală.

Exemplu: numărul maxim de apariții al unei culori într-o secvență

Se citește la intrare un număr n și apoi n culori. Cele n culori sînt codificate cu numere între 0 și 14. Să se afișeze în ordine crescătoare toate culorile care apar de cele mai multe ori în secvență.

Exemplu: pentru secvența

22
4 2 9 8 2 5 8 10 14 12 14 6 12 14 8 3 7 2 0 13 14 8

Vom afișa:

8 14

deoarece culorile 8 și 14 apar de 4 ori în secvență, iar toate celelalte culori apar de mai puține ori.

Rezolvare: vom crea un vector caracteristic a de 15 elemente, inițializat cu zero. Apoi vom citi rînd pe rînd culorile, în variabila c, adunînd 1 la a[c]. În final a[c] va conține numărul de apariții ale culorii c. Pentru a afla culorile care apar de cele mai multe ori vom căuta maximul în acest vector, apoi, la o a doua parcurgere vom afișa toate pozițiile pe care a[i] este maxim. Iată soluția:

#include <stdio.h>

int a[15];

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

  // citim secventa de culori si construim vectorul de frecventa
  fin = fopen( "culori.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &c );
    a[c]++;
  }
  fclose( fin );

  // cautam maximul in vectorul de frecventa
  max = a[0];
  for ( c = 1; c < 15; c++ )
    if ( a[c] > max )
      max = a[c];

  // afisam toate pozitiile c pentru care a[c] == max
  fout = fopen( "culori.out", "w" );
  for ( c = 0; c < 15; c++ )
    if ( a[c] == max )
      fprintf( fout, "%d ", c );
  fclose( fout );

  return 0;
}

Tema

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

  • cfdist (numărul de elemente al mulțimii cifrelor unui număr)
  • maxnr (cel mai mare număr care se poate forma cu cifrele unui număr)
  • culori (să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordinea lor crescătoare)

Rezolvări aici [2]