Clasa a V-a lecția 10 - 14 oct 2014

From Algopedia
Jump to: navigation, search

Anunțuri

  • Semnați temele! Altfel nu primiți buline :) În final voi ține cont de aceste teme.
  • Tema constă nu numai din programe C ci și din schemele logice! Cine dă numai scheme logice sau numai programe C primește numai jumate de bulină :)
  • Atunci cînd rezolvați o problemă nu vă repeziți să scrieți programul C. Urmăriți următoarele etape:
    • Mai întîi gîndiți-vă la modul cum ați rezolva-o voi, "de mînă". Pentru fiecare din ideile de rezolvare treceți prin etapele de mai jos.
    • Elaborați regula observată într-o metodă. Asigurați-vă că știți să traduceți acea metodă în pași pe calculator. Dacă aveți nevoie să inversați ordinea cifrelor unui număr, știți pașii elementari pentru asta?
    • Verificați că metoda funcționează pe cîteva exemple, nu doar pe exemplul furnizat de problemă. Pentru aceasta creați-vă propriile exemple de test.
    • Scrieți schema logică.
    • Verificați schema logică pe exemple. Faceți corecturile necesare, dacă observați greșeli în metoda pe care ați gîndit-o original. Verificați, de asemenea, că schema logică funcționează pe exemple la limită: cînd n este zero, sau unu, sau număr prim, etc. Rularea schemei logice se face ținînd efectiv degetul pe săgeți până ajungeți la blocul de STOP. Păstrați un tabel cu valorile tuturor variabilelor la orice moment.
    • Abia la final scrieți programul C, urmărind îndeaproape schema logică.

Tema - rezolvări

Rezolvări aici [1]

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, k ≤ n. 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 [2]