Design patterns în probleme - clasa IX
Teorema împărțirii cu rest
Fie două numere \(a, b \in \mathbb{Z}, b \neq 0\).
Există și sunt unice numerele întregi câtul q și restul r astfel încât să fie
satisfăcute simultan condițiile: \(a = b \cdot q + r, r < b\)
În C/C++ se exprimă altfel cu operatori:
int a, b, q, r;
q = a / b; /* în pseudocod era a div b. q e garantat întreg dacă a și b sunt int */
r = a % b; /* în pseudocod era a mod b. valoarea maximă a lui r e b-1 */
Criterii de divizibiliate
Fie două numere \(a, b \in \mathbb{Z}\). Spunem că a este divizibil cu b dacă
și numai dacă a % b == 0. Condiția este universal valabilă și nu este nevoie de criteriile de divizibilitate de la matematică. Restul 0 la împărțire ne spune că numerele se împart exact.
Exemplu de problemă: Se citesc n numere de la tastatură. Afișați numerele divizibile cu 5
#include <iostream>
using namespace std;
int main()
{
int n, i, nr;
for (i = 0; i < n; i++) {
cin >> nr;
if (nr % 5 == 0)
cout << nr;
}
return 0;
}
Observație: este evident că a NU este divizibil cu b dacă a % b != 0, adică
restul împărțirii lui a la b este nenul.
Ce înseamnă că numărul natural n este par? Răspuns: n % 2 == 0. Dar impar? n % 2 != 0
Divizorii unui număr
O problemă frecvent întâlnită este determinarea divizorilor unui număr dat. În practică se pot cere diverse operații cu aceștia: afișarea, însumarea, numărarea și diverse altele.
Implementare naivă
Toți divizorii lui n sunt între 1 și n, inclusiv.
Putem parcurge numerele din acest interval și verifica dacă restul împărțirii este 0.
for(d = 1; d <= n; d++)
if(n % d == 0)
cout << d << " ";
Optimizare n/2
O primă optimizare pe care o putem observa este că pentru orice n, de la n/2 la n
nu mai sunt divizori. În plus excludedm pe și pe 1. Putem astfel să înjumătățim interval în care căutăm divizorii:
for(d = 2; d <= n/2; d++ )
if(n % d == 0)
cout << d << " ";
Optimizare sqrt(n)
Optimizare eficientă din punct de vedere a timpului: Observăm că divizorii oricărui număr n sunt în pereche: dacă d este divizor al lui n, atunci și n/d este divizor al lui n.
Atenție dacă n este pătrat perfect. Asta deoarece vom parcurge numerele doar de la 1 la
sqrt(n) și aici trebuie să nu afișăm de două ori sqrt(n) care este divizor în acest caz.
Programul nostru final devine (și acesta trebuie să îl folosiți mereu în probleme!)
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n, d;
cin >> n;
for(d = 1; d <= sqrt(n); d++)
if(n % d == 0) {
cout << d << " ";
if (d < sqrt(n))
cout << n / d << " ";
}
return 0;
}
Detalii și exemple pe https://www.pbinfo.ro/articole/72/divizorii-unui-numar. De asemenea revedeți și lecțiile de matematică: Divizibiliatea numerelor naturale
Verificarea că un număr este prim
Un număr n este prim dacă are exact 2 divizori: pe 1 și pe el însuși.
Pentru a stabili dacă un număr p este prim avem 3 posibilități:
- numărăm divizorii săi. Dacă sunt 2 divizori, p este prim.
- determinăm suma divizorilor. Dacă suma este
p + 1, numărul este prim. - căutăm divizori ai săi diferiți de 1 și de el însuși. Dacă nu găsim, numărul este prim.
Atenție! Ne folosim de optimizarea discutată mai sus ca să putem face un algoritm eficient.
Ca să ne creem algoritmul pentru verificarea dacă un număr n este prim îl vom presupune de la început prim, eliminăm cazurile particulare n = 0, n = 1 și apoi parcurgem intervalul
[2, sqrt(n)] și aplicăm unul din cele 3 bullet-uri de mai sus. Pentru a nu cicla mereu până la
finalul buclei facem o optimizare folosind instrucțiunea break
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int prim = 1; // presupunem ca n este prim, prim=1 adevarat, prim=0 fals
int d;
if(n < 2)
prim = 0; // 0 si 1 nu sunt prime
for(d = 2 ; d <= sqrt(n); d++)
if(n % d == 0) {
prim = 0;
break; //iesim din bucla, am gasit deja un divizor clar nu e prim
}
if (prim)
cout << n << " este prim";
else
cout << n << " nu este prim";
return 0;
}
CMMDC, CMMMC și Algoritmul lui Euclid
Material foarte bun pe https://www.pbinfo.ro/articole/73/cmmdc-si-cmmmc-algoritmul-lui-euclid
Descompunerea în factori primi
- Material introductiv pbinfo
- Aplicații ale descompunerii în factori primi
- Lecție matematică descompunere în factori
- TELEȘCOALA: Matematică, a VIII–a - Descompunerea în factori
- TELEȘCOALA: Matematică, a VIII-a - Metode de descompunere în factori
Citirea șirurilor de numere de la tastatură
Se citesc numere pana la 0
Într-o problemă va apărea exprimarea: “Se citesc numere de la tastatură până la apariția lui zero.”
Soluția este pe pași:
- Citesc primul număr într-o variabilă
n - Cât timp
neste diferit de0continui citirea. Pentru că am făcut citirea la pasul anterior variabilaneste inițializată
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
/* procesez n conform cerinței */
while (n != 0) {
cin >> n;
/* procesez n conform cerinței */
}
return 0;
}
Alternativ: inițializez n cu orice valoare (să zicem 1) și fac citirea în buclă:
#include <iostream>
using namespace std;
int main()
{
int n = 1;
while (n != 0) {
cin >> n;
/* procesez n conform cerinței */
}
return 0;
}
Se citesc n numere
În alte probleme pur și simplu se specifică clar: “Se citesc n numere de la tastatură”.
Aici soluția elegantă este să se folosească un for
#include <iostream>
using namespace std;
int main()
{
int n, i, nr;
cin >> n;
for (i = 0; i < n; i++) {
cin >> nr;
/* procesez nr conform cerinței */
}
return 0;
}
Dar se poate și cu while:
#include <iostream>
using namespace std;
int main()
{
int n, i = 0;
cin >> n;
while (i < n) {
cin >> nr;
/* procesez nr conform cerinței */
i++;
}
return 0;
}
Se citesc numere pana cand doua consecutive
Se citesc numere de la tastatură până când se introduc două numere consecutive egale. Programul citește de la tastatură numere întregi. Citirea se încheie când se introduc două numere egale.
Vom folosi două variabile prev și crt. Le citim întâi pe amândouă.
Apoi vom citi în mod repetat pe crt (până când e egal cu prev).
Procesăm datele prev și crt conform cerinței din problemă,
apoi copiem pe crt în prev și citim altă valoare pentru crt
Copierea lui crt în prev este necesară pentru a avea tot timpul
acces la două valori citite consecutiv: valoarea curenta crt și valoarea anterioară prev.
#include <iostream>
using namespace std;
int main()
{
int prev, crt, s = 0;
/* Fac o citire inițială a primelor două numere */
cin >> prev;
cin >> crt;
while (prev != crt) {
prev = crt; /* in prev stochez valoarea anterioara */
cin >> crt; /* citesc valoare noua */
/* procesez prev si crt conform cerintei ulterioare */
}
return 0;
}
Atenție: programul este scris cu presupunerea că datele introduse chiar sunt în perechi și că vi se vor citi minim 2 numere. Lucrurile se pot complica dacă nu vi se precizează ce date de intrare veți avea, dar nu sunt obiectul acestui exemplu.
Alt exemplu: Se citesc numere de la tastatură până la apariția lui zero. Să se afișeze câte perechi de elemente citite consecutiv sunt egale:
#include <iostream>
using namespace std;
int main()
{
int prev, crt = -1, counter = 0;
/* Citesc primul numar */
cin >> prev;
while (crt != 0) {
/* citesc repetetiv */
cin >> crt;
/* determin dacă sunt o pereche de egale */
if (crt == prev)
counter++;
/* imi fac o copie ca sa am acces mereu la doua valori citite consecutiv:
* valoarea curenta e mereu crt valoarea anterioara e prev
*/
prev = crt;
}
cout << counter;
return 0;
}
Determinare maxim și minim
În multe probleme de informatică suntem în situația ca pentru un șir de numere să determinăm
valoarea maximă respectiv cea minimă. Pentru exemplificare datele de intrare sunt un șir de n numere citit de la tastatură cu una din metodele menționate mai sus.
Vă recomand să urmăriți următorul videoclip scurt:
Există și solutii mai elegante/eficiente, dar pentru clasa a IX-a este general acceptată această metodă:
- Se declară două variabile
max, min. În general este binemaxsă fie inițializat la cea mai mică valoare posibilă în funcție de contextul problemei iarminsă fie inițializat la cea mai mare valoare posibilă. Exemplu: dacă dorim să determinăm cifra minimă și maximă atunci inițializările suntmax = 0, min = 9. - Se parcurge șirul de numere cu metoda de citire descrisă mai sus. Fiecare număr citit de la tastatură se compară cu
max, min - Dacă
x < minînseamnă că am găsit o valoarexmai mică decât minimul curent, deci minimul curent devinex:min = x. Similar pentru maxim, doar că invers facem comparția.
#include <iostream>
using namespace std;
int main()
{
int n, max = -65535, min = 65535;
cin >> n;
for (i = 0; i < n; i++) {
cin >> nr;
if (nr < min)
min = nr;
if (nr > max)
max = nr;
}
cout << "Maximul este: " << max << " si minimul " << min;
return 0;
}
Vă recomand și articolul similar https://www.pbinfo.ro/articole/79/maximul-minimul-pentru-un-numar-oarecare-de-valori
Calcul de sume și produs
Ne dorim să calculăm: \(\displaystyle S = \sum_{i=1}^{n} i, \ P = \prod_{i=1}^{n} i\). P se mai
scrie și P = n! (factorial)
Ce este important la sume/produse: trebuie să ne inițializăm variabila în care stocăm rezultatul final (cu 0 la sume, cu 1 la produse).
#include <iostream>
using namespace std;
int main()
{
int n, i, s = 0, p = 1;
cin >> n;
for (i = 1; i <= n; i++) {
s = s + i;
p = p * i;
}
cout << "Suma este: " << s << " si produsul " << p;
return 0;
}
Întotdeauna este important când vi se dă o sumă de calculat (sau un produs) să scrieți forma prescurtată. Pe baza ei veți putea scrie algoritmul. De exemplu: dacă vi se cere să calculați suma:
\[S = \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 4} + \ldots + \frac{1}{n(n+2)}\]Îi scriem forma prescurtată: \(\displaystyle S = \sum_{i=1}^{n} \frac{1}{k(k+2)}\) și atunci algoritmul nostru devine:
#include <iostream>
using namespace std;
int main()
{
int n, k;
double s;
cin >> n;
for (k = 1; k <= n; k++) {
s = s + 1.0 / (k * (k + 2));
}
cout << "Suma este: " << s << " si produsul " << p;
return 0;
}
Descompunerea unui număr în cifre
Teorie
Un număr natural de trei cifre se scrie sub forma \(\overline{abc}\).
Descompus, acest număr se poate scrie \(\overline{abc} = 100 \cdot a + 10 \cdot b + c\). Observăm că
c < 10, b < 10, a < 10 deci ne putem folosi de operatorul modulo pentru a obține cifrele.
Întotdeauna ultima cifră a unui număr natural n este n % 10. Cum ajung la următoarea cifră?
Mă folosesc de descompunerea menționată mai sus și cer câtul împărțirii lui n la 10 pentru a elimina ultima cifră. Practic pe relația \(n = \overline{abc} = 100 \cdot a + 10 \cdot b + c\) avem:
c = n % 10b = (n / 10) % 10a = ((n / 10) / 10) % 10 = (n / 100) % 10
Când ne oprim? Atunci când câtul împărțirii la 10 este 0. Practic am ajuns la ultima cifră (cunoscută și sub numele de cea mai semnificativă cifră).
Exemplu
Exemplu de problemă: Se citește numărul n. Afișați toate cifrele lui
#include <iostream>
using namespace std;
int main()
{
int n, c;
cin >> n;
while (n != 0) {
c = n % 10;
cout << c << ", ";
n = n / 10;
}
return 0;
}
Palindrom
Observație importantă: folosind algoritmul de mai sus pentru un număr \(n = \overline{abc}\) noi vom afișa cifrele lui în ordine inversă \(b, c, a\). De ce este importantă? Există multe probleme care cer să verificați dacă un număr natural n este palindrom. Palindromul este un număr care e același indiferent că citim de la stânga la dreapta sau dreapta la stânga. Exemplu: 123 nu este palindrom, dar 12321 este palindrom.
Cum scriem algoritmul să verificăm dacă un număr e palindrom? Ne folosim din nou de \(n = \overline{abc}\) și încercăm să compunem \(s = \overline{cba}\) și la final comparăm cele două numere: dacă sunt egale e palindrom.
Încă o observație importantă: pe programul de mai sus valoarea lui n la ieșirea din buclă este 0
deci noi pierdem valoarea citită. Trebuie să facem o copie pentru aceasta.
#include <iostream>
using namespace std;
int main()
{
int n, c, s = 0, cn;
cin >> n;
/* Fac o copie pentru n */
cn = n;
while (n != 0) {
c = n % 10;
s = (s * 10) + c;
n = n / 10;
}
/* Aici n e 0. Dar am copia numărului citit în cn. Compar cn cu s */
if (cn == s)
cout << "este palindrom";
else
cout << "nu este palindrom";
return 0;
}
Vă recomand și articolul https://www.pbinfo.ro/articole/65/cifrele-unui-numar
Șirul lui Fibonacci
Fie șirul \((f_n)_{n \ge 3}\) pentru care se definește relația de recurență \(f_n = f_{n-1} + f_{n-2}\)
având valorile inițiale \(f_1 = 1, f_2 = 1\). Numerele Fibonacci sunt numere naturale care fac parte din următorul șir, în care fiecare număr este egal cu suma celor două de dinainte:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Algoritmul pentru a determina primii n termeni din șirul lui Fibonacci este: folosim
trei variabile a,b,c. Două dintre ele reprezintă termenii anteriori \(f_{n-1}, f_{n-2}\) și a
treia reprezintă termenul curent \(f_n\):
#include <iostream>
int main()
{
int a = 1, b = 1, c, i;
cout << a << ", " << b;
for (i = 3; i <= n; i++) {
c = a + b;
cout << c << ", ";
a = b;
b = c;
}
}