Clasa a IX-a lecția 8 - 7 dec 2019

From Algopedia
Jump to navigationJump to search

Clasament teme lecțiile 1 - 7

Am observat că aceste clasamente vă stârnesc puțin mai tare interesul de a lucra deci vi le-am făcut publice. Ca regulă, voi actualiza clasamentul la finalul fiecărei săptămâni (vineri seară, cel mai probabil).

Felicitări celor care ocupă primele locuri și mult spor tuturor la teme!!!

Clasamente avansați

Avansați Infoarena
Avansați Varena

Clasamente începători

Începători Varena

Lecție

Caractere

Pe lângă citire, scriere și prelucrare de numere, calculatorul poate manipula și caractere sau șiruri de caractere. Fiecare caracter este reținut de calculator cu ajutorul unui cod, iar această codificare poartă și numele de ASCII. Puteți găsi aici toate codurile ASCII.

Citirea și afișarea unui caracter

Există mai multe modalități de a citi și de a afișa caractere. În exemple, vom folosi funcțiile fgetc și fputc:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  fin = fopen("fisier.in", "r");
  fout = fopen("fisier.out", "w");

  char c;
  c = fgetc(fin); // Citire caracter
  
  fputc(c, fout); // Afisare caracter
  
  fclose(fin);
  fclose(fout);
  return 0;
}

Similar cum parcurgem numere consecutive cu instrucțiunea for, putem parcurge și caractere consecutive, cum ar fi ABCDEF...XYZ:

#include <stdio.h>

int main() {
  FILE *fout;
  fout = fopen("fisier.out", "w");

  char c;
  for (c = 'A'; c <= 'Z'; ++c)
    fputc(c, fout);

  fclose(fout);
  return 0;
}

Citirea unui șir de caractere

Vrem să citim caractere din fișier până când dăm de rând nou și să le afișăm. Vom proceda astfel:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  fin = fopen("fisier.in", "r");
  fout = fopen("fisier.out", "w");

  char c = fgetc(fin); // Citim caracter din fisier
  while (c != '\n') { // Cat timp nu am ajuns la rand nou
    fputc(c, fout); // Scriem caracterul
    c = fgetc(fin); // Citim urmatorul caracter
  }

  fclose(fin);
  fclose(fout);
  return 0;
}

Vrem să citim din fișier un număr N de pe primul rând, urmat de N caractere pe cel de-al doilea rând:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  fin = fopen("fisier.in", "r");
  fout = fopen("fisier.out", "w");

  int n, i;
  char c;
  fscanf(fin, "%d", &n); // Citim n
  fgetc(fin); // ATENTIE! Citim urmatorul caracter dupa n, caracterul \n
  for (i = 0; i < n; ++i) {
    c = fgetc(fin); // Citim al i-lea caracter
    fputc(c, fout); // Il afisam
  }

  fclose(fin);
  fclose(fout);
  return 0;
}

Vrem să citim toate caracterele din fișier, până la finalul acestuia. Pentru aceasta, există un caracter special codificat EOF (End of File):

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  fin = fopen("fisier.in", "r");
  fout = fopen("fisier.out", "w");

  char c;
  c = fgetc(fin);
  // ATENTIE! Este posibil ca unele fisiere sa se termine cu: \nEOF
  // Depinde de caz, este posibil sa nu vrem sa luam in considerare caracterul \n
  while (c != '\n' && c != EOF) {
    fputc(c, fout);
    c = fgetc(fin);
  }

  fclose(fin);
  fclose(fout);
}

Linkuri utile

Mai multe despre caractere găsiți aici.

Baze de numerație

Din baza 10 în baza 2

Pentru a transforma un număr din baza 10 în baza 2, vom folosi un algoritm similar cu cel prin care extragem cifrele unui număr în baza 10:

#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  
  while (n > 0) {
    printf("%d", n % 2);
    n /= 2;
  }

  return 0;
}

Atenție! Acest algoritm ne oferă cifrele în ordine inversă! Pentru a afișa cifrele în ordinea corectă, le putem reține într-un vector pe care îl vom răsturna.

Din baza 2 în baza 10

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  fin = fopen("fisier.in", "r");
  fout = fopen("fisier.out", "w");

  int n = 0;
  char c = fgetc(fin);
  while (c != '\n' && c != EOF) {
    // c este un caracter și are un cod ASCII asociat (număr întreg)
    // c - '0' este conversia de la codul ASCII la valoarea pe care o reprezintă caracterul
    n = n * 2 + (c - '0');
    c = fgetc(fin);
  }

  fprintf(fout, "%d\n", n);

  fclose(fin);
  fclose(fout);
}

Generalizare

Procesul de transformare a unui număr din baza 10 în baza B sau din baza B în baza 10 este similar.

Linkuri utile

Mai multe despre baze de numerație găsiți aici și aici.

Submulțimile unei mulțimi

Vrem să afișăm toate submulțimile nevide ale mulțimii {1, 2, 3, ..., n}.

Cum abordăm această problemă? La prima vedere pare foarte grea. Va trebui, probabil, să afișăm toate submulțimile de un element. Aceasta e simplu. Apoi cele de două elemente. Tot simplu, vom selecta perechile cu două bucle for. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle for. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de n. Dar stai! Nu putem scrie un număr variabil de bucle for una într-alta!

Ne trebuie o altă abordare. Vom codifica mulțimile. Cum? Foarte simplu: folosind vectorul lor caracteristic. Pentru fiecare element al mulțimii, de la 1 la n, vom avea un element în vectorul v. Pentru o submulțime dată v[i] este 1 dacă elementul i apare în submulțime.

Acest mod de codificare demonstrează un lucru interesant: numărul de submulțimi al unei mulțimi, incluzînd mulțimea vidă, este 2n. Interesant!

Cum vom folosi acest vector? Destul de neclar. Ne-ar trebui un mod în care să variem toate elementele sale de la zero la unu. Și iar ne întoarcem la buclele for una într-alta. Dar există un mod natural în care elementele pot trece prin toate combinațiile posibile de 0 și 1: dacă în loc să folosim un vector cu n elemente folosim un număr binar cu n cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele n cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

În concluzie, care este algoritmul? Iată-l descris mai jos:

   1. Pentru i de la 1 la 2^n - 1
       1.1 Descompune i în baza 2
       1.2 Pentru fiecare cifră binară 1 care se află pe poziția j
           1.2.1 Afișează j
       1.3 Sfîrșit de submulțime, treci la linia următoare

Sursă: IQ Academy

Operații pe biți

Pe lângă operatorii despre care am vorbit până acum, există și operatori care ne permit să jonglăm mai ușor cu biții unui număr (cifrele din baza 2).

Operator Semnificație Exemplu
<< Shiftare biți către stânga (înmulțire cu 2) x ← 1 << n (shiftăm de n ori către stânga biții lui 1, obținând în x valorea 2n)
>> Shiftare biți către dreapta (împărțire la 2) x ← 20 >> n (shiftăm de n ori către dreapta biții lui 20, obținând în x valorea 20 / 2n)
& Operația "și" pe fiecare bit în parte x ← a & b (și între fiecare pereche de biți ale numerelor a și b)

Exemple

  • 1 << 10 = 1024;
  • 1 << n = 2n;
  • 1024 >> 10 = 1;
  • 1000 >> 2 = 250;
  • 5 << 2 = 20;
  • 5 & 1 = 1;
  • x & 1 = x % 2;
  • x & 7 = x % 8;
  • x & (2n - 1) = x % 2n;
  • x & 2n = 0 sau 1, al n-lea bit al lui x (din descompunerea în baza 2);

Submulțimile unei mulțimi (folosind operații pe biți)

Cum arată un algoritm care se folosește de regulile operațiilor pe biți prezentate mai sus pentru a genera submulțimile unei mulțimi:

   1. Pentru i de la 1 la 2^n - 1
      1.2. Pentru j de la 1 la n
           1.2.3. Dacă al (j - 1)-lea bit al lui i este 1, afișează j
      1.3. Sfârșit de submulțime, treci la linia următoare

Același lucru, dar în limbaj:

#include <stdio.h>

int main() {
  int n, max2, i, j;
  scanf("%d", &n);
  
  max2 = 1 << n;
  for (i = 1; i < max2; ++i) {
    for (j = 1; j <= n; ++j)
      if ((i & (1 << (j - 1)) == 1)
        printf("%d ", j);
    printf("\n");
  }

  return 0;
}

Atenție! Operațiile pe biți au prioritate mică în ordinea efectuării operațiilor. De aceea este indicat să "forțați" executarea acestora în ordinea dorită folosind paranteze (ca în exemplul anterior).

Performanță Operațiile pe biți sunt mai rapide decât operațiile simple de înmulțire sau împărțire cu puteri ale lui 2. Recomand să le folosiți unde aveți ocazia.

Probleme

Avansați

Puteri
Gigel si Resturile
Leo
Numere8
Reteta

Începători

Lucrați probleme de inițiere în caractere:

Numchar
Sumacifre
Alfanumeric
Fgetc
Plusminus

Probleme cu baze de numerație:

Dubla Conversie
Monsters
Suprapuneri
Submultimi