Clasa a IX-a lecția 2 - 19 oct 2019

From Algopedia
Jump to navigationJump to search

Rezolvare problemă lecția anterioară

Rezolvare aici [1]

Lecție

În urma întrebărilor pe care vi le-am adresat, a rezultat că în acest moment la cerc vin elevi cu un nivel variat de pregătire. Pentru a avea o perspectivă mai bună despre nivelul fiecăruia dintre voi, am continuat cu o lecție introductivă a cărei nivel de dificultate a crescut variat și opțional, am pus la bătaie problema Expresie.

Limbajul C

Am continuat cu o mini introducere în limbajul C, limbaj pe care îl vom aprofunda în lecțiile ce urmează la acest curs.

Limbaje de programare

Spre deosebire de schema logică care exprimă logica de bază a unui algoritm, limbajele de programare adaugă toate detaliile necesare pentru ca algoritmul sa fie înțeles și executat de calculator.

Structura unui program în C

Orice program C conține anumite elemente fixe:

  • Includerea bibliotecilor / librăriilor care vor fi folosite pentru rezolvarea algoritmului (exemplu: biblioteca stdio, care ne permite să folosim funcții de citire și scriere).
  • Începutul funcției principale (main). Programul va executa instrucțiunile în ordine, începând cu această funcție.
  • Finalul funcției principale, în care se returnează valoarea zero (succes).

Hello World

Un program simplu: Hello World (programul clasic pe care programatorii îl scriu atunci când învață un nou limbaj de programare):

#include <stdio.h>

int main() {
  printf( "Hello world!" );
  return 0;
}

Instrucțiuni de intrare/ieșire

Instrucțiunile scanf și printf sunt echivalentul blocului paralelogram în schemă logică. Exemplu: citirea a două numere și afișarea sumei lor:

#include <stdio.h>

int main() {
  int a, b;

  printf( "Introduceti doua numere: " );
  scanf( "%d%d", &a, &b );
  printf( "Suma numerelor este %d\n", a + b );
  return 0;
}

Am discutat pe scurt despre cum sunt aranjate variabilele declarate în memorie pentru a înțelege mai bine semnificația operatorului & și a denumirii de "memorie pe stivă".

Probleme

Suma a două numere

Suma a două numere folosind o variabilă intermediară, de calcul: 

#include <stdio.h>

int main() {
  int a, b, c;

  scanf( "%d%d", &a, &b );
  c = a + b;
  printf( "Suma numerelor este %d\n", c );
  return 0;
}

Calcul expresie

Scrieți la calculator programul care să calculeze expresia 24 / a + 100 / (c3 + b / (d2 + e2))

#include <stdio.h>

int main() {
  int a, b, c, d, e, expr;

  scanf( "%d%d%d%d%d", &a, &b, &c, &d, &e );
  expr = 24/a + 100 / (c * c * c + b / (d * d + e * e));
  printf( "expresia este %d\n", expr );
  return 0;
}

Limbajul C

Intrucțiunea if

Am vorbit despre instrucțiunea if. Ea implementează structura alternativă. Apoi am vorbit despre operatorii de comparație ==, !=, <, <=, >, >=. Exercițiu: Să se spună dacă n divizibil cu k

Schemă logică
 
#include <stdio.h>

int main() {
  int n, k;

  scanf( "%d%d", &n, &k );
  if ( n % k == 0 )
    printf( "Da" );
  else
    printf( "Nu" );
  return 0;
}

Instrucțiunea compusă

Instrucțiunea if permite cîte o singură instrucțiune pe fiecare ramură. Ce facem dacă avem mai multe instrucțiuni pe o ramură? Folosim instrucțiunea compusă, folosind acolade. Exercițiu: ecuația de gradul 1. Fie ecuația

a · x = b

Să se calculeze x. Atenție! Ecuația poate avea multiple soluții, sau nici o soluție!

Schemă logică
 
#include <stdio.h>

int main() {
  int a, b, x;

  scanf( "%d%d", &a, &b );
  if ( a == 0 )
    if ( b == 0 )
      printf( "x oricare\n" );
    else
      printf( "x nu exista\n" );
  else {
    x = b / a;
    printf( "x este %d\n", x );
  }
  return 0;
}

Instrucțiunea while

Am vorbit despre instrucțiunea while. Ea implementează structura repetitivă de tip WHILE-DO.

Problemă: Se dă un număr natural n. Să se afișeze prima cifră a acestuia. 

#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);

  while (n > 9)
    n = n / 10;

  printf("Prima cifra a lui n este %d\n", n);
  return 0;
}

Complexitate

Am vorbit despre complexitatea unui algoritm (numărul de pași pe care acesta va trebui să îi execute pe cazul cel mai "rău").

Divizori & Descompunere în factori primi

Exercițiul 1 - Divizor propriu

Se citește un număr n. Să se afișeze cel mai mare divizor propriu al lui n (strict mai mic decât n). Exemplu: dacă n=24 cel mai mare divizor propriu este 12. Dacă n=7 cel mai mare divizor propriu este 1. Dacă n=125 cel mai mare divizor propriu este 25. Dacă n = 175 cel mai mare divizor propriu este 35. 

#include <stdio.h>

int main() {
  int n, d;
  scanf("%d", &n);
  
  d = 2;
  while (d * d <= n && n % d > 0)
    d = d + 1;

  if (n % d == 0)
    printf("%d\n", n / d);
  else
    printf("1\n");

  return 0;
}

Am discutat despre cum este aranjată mulțimea divizorilor unui număr și cum putem parcurge divizorii acestuia în complexitate O(sqrt(N)).

Exercițiul 2 - Divizorii unui număr

Se citește un număr n, Să se afișeze toți divizorii lui n.

Folosindu-ne de observația anterioară, am parcurs divizorii lui n în perechi de câte doi divizori, ținând cont și de cazul special în care n este pătrat perfect. 

#include <stdio.h>

int main() {
  int n, d;

  scanf("%d", &n);
  printf("Divizorii lui %d sunt:", n);
  d = 1;
  while (d * d < n) {
    if (n % d == 0)
      printf("%d %d ", d, n / d);
    d = d + 1;
  }
  if (n % d == 0)
    printf("%d", d);
  printf("\n");

  return 0;
}

Exerciţiul 3 - Descompunere în factori primi

Se citește un număr n. Să se scrie descompunerea acestuia în factori primi.

Ne-am folosit de o observație similară cu cea folosită pentru afișarea divizorilor. În momentul în care întâlnim un divizor, împărțim numărul la acel divizor de câte ori este posibil și numărăm. Astfel avem garanția că de fiecare dată când dăm de un divizor, acesta este prim.

Atenție și la cazul în care numărul are un factor prim mai mare decât radicalul acestuia. Am demonstrat că dacă există, este unul singur și se află la puterea 1. 

#include <stdio.h>

int main() {
  int n, p, e;

  scanf("%d", &n);
  p = 2;
  while (p * p <= n) {
    e = 0;
    while (n % p == 0) {
      n = n / p;
      ++e;
    }

    if (e > 0)
      printf("%d la puterea %d\n", p, e);

    ++p;
  }

  if (n > 1)
    printf("%d la puterea 1\n", n);

  return 0;
}

Exerciţiul 4 - Numărul de pătrate perfecte între a și b

Se citesc două numere a și b. Să se afișeze câte pătrate perfecte între a și b există.

Soluție: Am dezbătut mai multe soluții la această problemă și am căzut de acord pe cea mai simplă sau intuitivă dintre ele:

  • Calculăm câte pătrate perfecte sunt în intervalul [1, b] și notăm valoarea obținută cu N0.
  • Calculăm câte pătrate perfecte sunt în intervalul [1, a - 1] și notăm valoarea obținută cu N1.
  • Rezultatul este N0 - N1.

Am demonstrat că numărul pătratelor perfecte din intervalul [1, x] este sqrt(x).

Mențiune: De reținut această metodă de a număra într-un interval, poate ușura munca în multe situații! 

#include <stdio.h>
#include <math.h>

int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  printf("%d\n", sqrt(b) - sqrt(a - 1));
  return 0;
}

Observăm că pentru a putea calcula radicalul unui număr (funcția sqrt în C), trebuie să includem biblioteca math.h.

Algoritmul lui Euclid

Cel mai mare divizor comun

Algoritmul lui Euclid este o metodă eficientă de a calcula cel mai mare divizor comun al două numere. El pornește de la următoarea idee:

  • cmmdc(a, b) = cmmdc(a - b, b), unde a > b.

Aplicând repetat metoda scăderilor repetate de mai sus, concluzionăm că:

  • cmmdc(a, b) = cmmdc(a % b, b). Am arătat că în acest caz, nu contează dacă inițial se respectă condiția a > b.
#include <stdio.h>

int main() {
  int a, b, r;
  scanf("%d%d", &a, &b);
  
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }

  printf("Cel mai mare divizor comun este %d\n", a);

  return 0;
}

Cel mai mic multiplu comun

Ne folosim de calculul celui mai are divizor comun și obținem: cmmmc(a, b) = a * b / cmmdc(a, b).

Extindere pentru mai multe numere

Dacă vrem să extindem algoritmul pentru mai mult de două numere, avem:

  • cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c).
  • cmmmc(a, b, c) = cmmmc(cmmmc(a, b), c).

Atenție! Următoarea variantă este INCORECTĂ: cmmmc(a, b, c) = a * b * c / cmmdc(a, b, c).

Temă

Slack

Acceptați invitațiile de pe Slack, ca să putem comunica și să vă pot da feedback mai ușor pe problemele implementate.

Temă începători

Cei începători aveți ca temă să vă familiarizați cu limbajul ca să putem ajunge la un numitor comun în dificultatea cercului cât mai rapid. Treceți prin Prima lecție și trimiteți problemele în format .cpp pe Slack.

Lucrați și cereți-mi ajutorul și cu suficient efort și dorință veți putea ajunge la nivelul cercului. Recomandare de citit / exersat / învățat: Cercul de informatică gimnaziu.

Temă

Rezolvați problemele rămase ca gândire în timpul cercului. Ma voi uita pe sursele voastre și vă voi oferi feedback.

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_IX-a_lecția_2_-_19_oct_2019&oldid=17956"