BitCell

Salut..Imi spune si mie cineva va rog ce face programul asta ?Sunt indicatiile de rezolvare pentru problema
'Tort' de pe Campion.

Avem tortul dreptunghiular, de lungime M si latime N.
Vrem sa-l impartim intr-un numar minim de portii patrate. Notam latura patratului portiei cu L.
Notam numarul de portii cu k.

Aria tortului este M x N. Aria unei portii este L x L. Avem k portii, deci:
M x N = k x L x L => k = (M x N)/(L x L)

Vrem sa obtinem un numar minim de portii. De asemenea stim ca M, N, L si k sunt numere naturale nenule.
Se observa, din aceasta restrictie, ca L trebuie sa divida atat M cat si N. Deoarece k trebuie sa fie minim, reiese ca L trebuie sa fie cel mai mare divizor al numerelor M si N.

In codul de mai sus, cmmdc e o functie care calculeaza cel mai mare divizor comun prin algoritmul lui Euclid.

Problema spune că se dă un tort de dimensiuni M x N. Bucățile în care se împarte tortul trebuie să fie numere întregi (deci nu merge cu jumătăți de măsură). Apoi ne cere să găsim numărul minim de bucăți pătrate în care putem să împărțim tortul. Asta înseamnă că bucățile pătrate trebuie să fie cât mai mari posibile deci cât mai puține (dacă cerea să se afle numărul maxim de pătrate acesta era chiar M*N și de lungime minimă egală 1 ).

Astfel, trebuie să împărțim și lungimea și lățimea la același număr d iar rezultatul împărțirii să fie întreg. Acest număr d trebuie să fie și cel mai mare divizor al celor două mărimi(lungimea și lățimea). De aia apare în programul tău o funcție pentru determinarea cmmdc (cel mai mare divizor comun). Acest d va fi latura pătratului.

Având latura, putem afla de câte ori se împarte lungimea și lățimea în pătrate.

LE: poate înțelege mai bine de la 2 oameni

Multumesc mult !