Numere triunghiulare. Verificarea unui număr triunghiular
Ce este un număr triunghiular?
Un număr triunghiular reprezintă numărul de puncte dintr-un triunghi echilateral umplut într-un mod uniform cu puncte.
Al n
-lea număr triunghiular este egal cu numărul de puncte dintr-un triunghi
echilateral de latură n
; spre exemplu, al treilea număr triunghiular este
egal cu 6
:
Ca formulă generală a numerelor triunghiulare, al n
-lea număr triunghiular
este n * (n + 1) / 2
— aceeași formulă ca și la suma Gauss.
Program care determină al n
-lea număr triunghiular
#include <iostream>
using namespace std;
int numarTriunghiular(int x) {
return x * (x + 1) / 2;
}
int main()
{
int n;
cin >> n;
cout << numarTriunghiular(n);
return 0;
}
Program care verifică dacă un număr este triunghiular
Să zicem că avem un număr n
, pe care vrem să îl verificăm dacă este sau nu
triunghiular. Pentru asta, putem să calculăm în mod repetat primele câteva
numere triunghiulare, până când depășim valoarea n
. Dacă am atins valoarea
n
cu vreunul dintre numere, atunci n
este triunghiular, altfel, nu este.
#include <iostream>
using namespace std;
int numarTriunghiular(int x) {
return x * (x + 1) / 2;
}
int esteNumarTriunghiular(int x) {
//Calculăm primele numere triunghiulare până când depășim valoarea lui x.
//Dacă întâlnim vreo valoare egală cu x, atunci este triunghiular.
//Ne vom folosi de funcția creată mai sus pentru a determina al *n*-lea număr triunghiular.
int i = 1;
while(numarTriunghiular(i) < x) {
i++;
}
if(numarTriunghiular(i) == x) {
return 1;
}
return 0;
}
int main()
{
int n;
cin >> n;
if(esteNumarTriunghiular(n) == 1) {
cout << n << " este număr triunghiular" << endl;
} else {
cout << n << " nu este număr triunghiular" << endl;
}
return 0;
}
Algoritmul de mai sus are complexitate liniară (O(n)
), dar putem să îl
optimizăm folosind căutarea binară.
Mai exact, luăm un număr triunghiular și verificăm dacă este mai mare sau mai
mic decât n
, iar în funcție de acest rezultat, căutăm numere triunghiulare
mai mici sau mai mari.
Vom asuma, pentru simplitate, că numărul nu depășește al 100
-lea număr
triunghiular (1 ≤ n ≤ 5050
). Putem, desigur, să mărim limita, actualizând
valmax
la valoarea dorită — atenție doar ca în timpul calculării `n * (n +
-
/ 2
, variabila să nu iasă din
int(sau
long long`)!#include
using namespace std;
int numarTriunghiular(int x) { return x * (x + 1) / 2; }
int esteNumarTriunghiular(int x) { //Căutăm binar dacă există vreun număr triunghiular egal cu x. //Ne vom folosi de funcția creată mai sus pentru a determina al n-lea număr triunghiular. //Asumăm pentru simplitate că x < numarTriunghiular(100) (adică x < 5050). int st = 1, dr = 100, mij; //Pentru căutarea binară: luăm al 50-lea număr triunghiular. Dacă este mai mare //decât x, atunci căutăm numere triunghiulare mai mici, iar în caz contrar //căutăm numere triunghiulare mai mari. while(st <= dr) { mij = (st + dr) / 2; if(numarTriunghiular(mij) == x) { //x este număr triunghiular, returnăm 1 return 1; } else if(numarTriunghiular(mij) < x) { //Numărul curent este mai mic decât x, așadar căutăm numere mai mari st = mij + 1; } else { //Invers: numărul curent este mai mare decât x, așadar căutăm numere mai mici dr = mij - 1; } } //Dacă am ajuns în punctul acesta fără să returnăm 1, atunci x nu este număr triunghiular. return 0; }
int main() { int n; cin >> n; if(esteNumarTriunghiular(n) == 1) { cout << n << " este număr triunghiular" << endl; } else { cout << n << " nu este număr triunghiular" << endl; } return 0; }
Bibliografie și alte resurse
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0