Clasa a V-a lecția 9 - 19 oct 2019

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Comentarii generale

  • În continuare sunt printre voi care nu verificați programele înainte să le trimiteți. Dacă veți continua în acest stil, veți avea probleme serioase. Respectați indicațiile de rezolvare a problemelor..

Exercițiul 1: divizorii impari ai lui n

Să se afișeze toți divizorii impari ai lui n. Aceasta este aceiași problemă ca cea de la curs, divizorii unui număr, doar că mai trebuie să adăugăm o condiție asupra divizorilor, și anume ca aceștia să fie impari.

Iată o posibilă rezolvare:


Divizorii impari ai lui n
#include <stdio.h>

int main() {
  int n, d;

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

  return 0;
}

Exercițiul 2: numere prime până la n

Se citește un număr n. Să se afișeze toate numerele prime mai mici sau egale cu n.

Vom folosi exerciţiul anterior. Vom varia un contor p de la 2 pînă la n. Aceste numere pot sau nu să fie numere prime, drept pentru care vom testa fiecare din ele dacă este prim.

Numere prime pînă la n
#include <stdio.h>

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

  scanf( "%d", &n );
  printf( "Nr. prime pina la %d:", n );
  p = 2;
  while ( p <= n ) {
    d = 2;
    while ( d < p && p % d > 0 )
      d = d + 1;
    if ( d == p )
      printf( " %d", p );
    p = p + 1;
  }
  printf( "\n" );

  return 0;
}

Observație: acesta este primul nostru algoritm în care am folosit două bucle while imbricate (una într-alta). Interesant, nu?

Exercițiul 3: numere divizibile cu k

Se citesc două numere, n și k. Să se afișeze toate numerele mai mici sau egale cu n care se divid cu k. Exemple: pentru n = 7 k = 2 se va afișa 2 4 6; pentru n = 25 k = 5 se va afișa 5 10 15 20 25.

Răspuns: am putea să variem un contor d de la 1 la n şi, pentru fiecare valoare a lui d să testăm dacă se împarte la k. Dar există o rezolvare mai eficientă: ştim că numerele divizibile cu k sînt k, 2k, 3k, etc. Drept care putem să generăm direct aceste numere, pornind cu d de la k şi adunînd k la fiecare iteraţie.

Numere divizibile cu k
#include <stdio.h>

int main() {
  int n, d, k;

  scanf( "%d%d", &n, &k );
  d = k;
  while ( d <= n ) {
    printf( "%d ", d );
    d = d + k;
  }

  return 0;
}

Exercițiul 4: numere perfecte

Se citește un număr n. Să se afișeze toate numerele perfecte mai mici sau egale cu n. Un număr este perfect dacă este egal cu suma divizorilor lui strict mai mici ca el. Primul număr perfect este 6, deoarece 6 = 1 + 2 + 3. Următorul număr este 28 deoarece 28 = 1 + 2 + 4 + 7 + 14. Exemple: dacă n = 8 se va afișa 6. Dacă n = 30 se va afișa 6 28. Dacă n = 500 se va afișa 6 28 496.

Răspuns: vom varia contorul p de la 6 (primul număr perfect) pînă la n. Acestea sînt potenţialele numere perfecte, ce trebuie testate. Pentru aceasta vom calcula suma divizorilor lui p, pentru fiecare p. Pentru a calcula suma divizorilor lui p vom varia divizorul d de la 1 la n (exclusiv n) şi îl vom adăuga la sumă dacă el îl divide pe p.

Acesta este un alt exemplu cu două bucle WHILE-DO imbricate (una în cealaltă).

Numere perfecte
#include <stdio.h>

int main() {
  int n, p, d, s;

  scanf( "%d", &n );
  p = 6;
  while ( p <= n ) {
    d = 1;
    s = 0;
    while ( d < p ) {
      if ( p % d == 0 )
        s = s + d;
      d = d + 1;
    }
    if ( s == p )
      printf( "%d ", p );
    p = p + 1;
  }

  return 0;
}

Exercițiul 5: problemă logică

Problemă de logică: ce linie urmează în secvență:

       1
      1 1
      2 1
    1 2 1 1
  1 1 1 2 2 1
  3 1 2 2 1 1
1 3 1 1 2 2 2 1

Răspuns:

1 1 1 3 2 1 3 2 1 1

Fiecare linie enumeră cîte cifre apar de fiecare tip. De exemplu linia doi se poate citi ca "un 1", linia 3 ca "doi 1", linia 4 ca "un 2 și un 1" și așa mai departe.

Lecție

Exerciții

Să se scrie schema logică și programul C pentru următoarele exerciții:

Descompunere în factori primi

Se citește un număr n. Să se descompună în factori primi. Exemple: dacă n = 12 vom afișa 12 = * 2^2 * 3^1; dacă n = 504 vom afișa 504 = * 2^3 * 3^2 * 7^1. Notă de rezolvare: nu este nevoie să testăm dacă un divizor este prim, putem testa toți divizorii. Numai cei primi vor ajunge să dividă n.

Descompunere în factori primi
#include <stdio.h>

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

  scanf( "%d", &n );
  printf( "%d =", n );
  d = 2;
  while ( n > 1 ) {
    p = 0;
    while ( n % d == 0 ) {
      p = p + 1;
      n = n / d;
    }
    if ( p > 0 )
      printf( " * %d^%d", d, p );
    d = d + 1;
  }
  printf( "\n" );

  return 0;
}

Puterea lui k în n!

Se citesc numerele n și k, k număr prim, kn. Considerăm numărul n! = 1∙2∙3∙...∙n. Să se afișeze puterea lui k din descompunerea în factori primi a lui n!.

Puterea lui k în n!
#include <stdio.h>

int main() {
  int n, k, p, f, fc;

  scanf( "%d%d", &n, &k );
  p = 0;
  f = 2;
  while ( f <= n ) {
    fc = f;
    while ( fc % k == 0 ) {
      p = p + 1;
      fc = fc / k;
    }
    f = f + 1;
  }
  printf( "%d", p );

  return 0;
}

Algoritmul lui Euclid (cmmdc a două numere)

Algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a inventat. Un avantaj important al algoritmului lui Euclid este că el poate găsi CMMDC eficient fără să trebuiască să calculeze factorii primi ai numerelor.

Euclid a observat că CMMDC al două numere a și b rămîne același dacă se scade numărul mai mic din cel mai mare (demonstrați!). Presupunînd că a este numărul mai mare, scăzînd în mod repetat pe b din a, în a va rămîne restul împărțirii lui a la b. Rezultă că CMMDC(a, b) este totuna cu CMMDC(b, a % b). Algoritmul care rezultă este următorul: luăm restul împărțirii lui a la b, apoi restul împărțirii lui b la rest, și așa mai departe, pînă ce obținem un rest zero. CMMDC este numărul rămas, cel diferit de zero.

Exemplu

Să calculăm CMMDC(252, 105). Calculăm 252 % 105 = 42. De aceea va trebui să calculăm CMMDC(105, 42). În continuare calculăm 105 % 42 = 21. Deci, vom calcula CMMDC(42, 21). Calculăm 42 % 21 = 0. Deoarece restul este zero CMMDC va fi ultimul număr nenul, adica 21.

Schema logică și programul

Iată algoritmul scris ca schemă logică și implementarea sa în limbajul C:

CMMDC cu algoritmul lui Euclid
#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( "%d", a );

  return 0;
}

Notă: remarcați că nu este nevoie să interschimbăm variabilele dacă a este inițial mai mic ca b. După prima execuție a buclei while ele se vor interschimba în mod natural.

Exercițiu

Doi prieteni, un iepure și o broscuță joacă un joc: pornesc de la o linie de start și încep să sară. Broasca sare n centimetri, iar iepurele m centimetri. Cine este mai în spate vine la rînd să sară. Jocul se termină atunci cînd iepurele și broasca sînt iarăși la egalitate. Cîți centimetri au parcurs cei doi prieteni?

Săriturile broscuței și iepurelui

Răspuns: după cum se vede și din figură, broscuța și iepurele vor sări o lungime egală cu CMMMC(m, n). Precum știm

CMMMC(m, n) = m ∙ n / CMMDC(m, n)

.

Interschimbarea a două variabile (swap)

Uneori, în algoritmi, este necesar ca două variabile, să spunem a și b să își schimbe între ele valorile, astfel încît valoarea care era la început în a să se afle în final în b și valoarea care era la început în b să se afle în final în a. Această operație se cheamă interschimbare (în engleză swap).

O metodă naivă și greșită ar fi următoarea:

a = b;
b = a;

Aceasta ar duce la un alt rezultat, și anume ambele variabile ar conține în final vechea valoare a lui b.

Pentru a înțelege mai bine soluția vom face o analogie cu o altă problemă: să presupunem că avem două pahare a și b, paharul a plin cu apă și paharul b plin cu lapte. Să presupunem că vrem să schimbăm conținutul paharelor astfel încît paharul a să conțină în final lapte și paharul b să conțină în final apă. Este clar că nu putem rezolva problema fără a ne folosi de un al treilea pahar, gol, să îi spunem aux, de la auxiliar (ce înseamnă auxiliar? Înseamnă ajutător). Pentru a face interschimbul putem vărsa paharul a în paharul aux, apoi paharul b în paharul a și în final paharul aux în paharul b.

Similar, pentru a interschimba variabilele a și b vom folosi o a treia variabilă aux:

aux = a;
a = b;
b = aux;

Exemplu: sortarea a trei numere

Sortarea a trei numere, revizitată: se citesc trei numere a, b și c, să se afișeze în ordine crescătoare. În lecția 4 am făcut deja o schemă logică care rezolvă problema testînd toate variantele. Iată o soluție mai simplă bazată pe interschimbarea variabilelor. Vom proceda de așa natură încît în final a, b și c să fie în ordine. Pentru aceasta vom interschimba două variabile dacă ordinea este greșită. Iată schema logică și programul C:

Sortare prin interschimbare
#include <stdio.h>

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

  scanf( "%d%d%d", &a, &b, &c );
  if ( a > b ) {
    aux = a;
    a = b;
    b = aux;
  }
  if ( b > c ) {
    aux = b;
    b = c;
    c = aux;
  }
  if ( a > b ) {
    aux = a;
    a = b;
    b = aux;
  }
  printf( "%d %d %d", a, b, c );

  return 0;
}

Se observă că această schemă este mai mică și mai simplă. Pe măsură ce numărul de variabile de ordonat crește, această metodă, cu interschimbări, devine tot mai compactă față de cea originală, în care testăm toate posibilitățile de ordonare.

Temă

  • Să se rezolve următoarele probleme (schemă logică + program C în CodeBlocks):
    • Pavaj: să se paveze un dreptunghi cu pătrate maximale. Se citesc a și b numere naturale, dimensiunile laturilor dreptunghiului, să se afișeze latura pătratelor cele mai mari cu care putem acoperi dreptunghiul, precum și numărul lor. Exemple: dacă a este 3 și b este 4 vom afișa 1 și 12 (cel mai mare pătrat cu care putem acoperi dreptunghiul are latură 1 și avem nevoie de 12 astfel de pătrate); dacă a este 6 și b este 8 vom afișa 2 și 12; dacă a este 12 și b este 20 vom afișa 4 și 15.
    • Cifră: se citește un număr n, să se spună dacă este format dintr-o singură cifră, repetată. Exemple: 3333 este un astfel de număr, 2424 nu este, 5 este, 88 este.
    • Ordonare: se citesc patru numere, a, b, c și d. Să se afișeze în ordine crescătoare. Folosiți interschimbări de variabile, precum ați văzut mai sus, în lecție.
  • Problemă de logică: un rege ar fi trebuit să primească zece fișicuri (ce este acela un fișic?) de monede a cîte zece grame fiecare monedă. Din nefericire unul din fișicuri conține zece monede a cîte 9 grame fiecare monedă, în loc de zece. Dispunem de un cîntar cu eroare mai mică de un gram și avem voie să facem o singură cîntărire. Cum vom proceda pentru a descoperi fișicul cu monede mai ușoare?

Rezolvări aici [1]