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 + 1) / 2, variabila să nu iasă din int (sau long long)!
#include <iostream>
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;
}