Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Numere triunghiulare. Verificarea unui număr triunghiular

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

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:

https://i.ibb.co/FDvytqm/IA-Graphic.png

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;
}

Bibliografie și alte resurse

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorTransformarea unei litere mari în literă mică în C++Suma 1 + 2 + 3 + ... + N în C++Inversarea unui vector în C++Numărul de divizori al unui număr în C++Verifică dacă un număr dat este o putere de 2 în C++Instrucțiunea continue (structuri repetitive)Numărul de cifre ale factorialului unui numărCum să afișezi partea întreagă a unui număr real în C++Verificare număr prim în C++ (Clasa a IX-a)Radicalul unui număr în C++ (rădăcina pătrată)Numere triunghiulare. Verificarea unui număr triunghiularInstrucțiunea while (structuri repetitive)Funcții predefinite în C++ (matematice, șiruri de caractere)Cifra de control a unui numărTransformarea unui număr din baza 2 în baza 10 în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiValoarea absolută (modulul) unui număr în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleCalculul combinărilor de n luate câte k (nCk) în C++Instrucțiunea break (structuri repetitive)Numărul combinărilor în C++ (formula combinărilor)Inversarea unui șir de caractere în C++Numărul de apariții al unui număr într-un vector în C++Codul ASCII (tabel complet)CMMDC recursiv a două numere naturale în C++Află secolul unui an citit de la tastatură în C++Verifică dacă un număr este par sau impar fără modulo în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cel mai mare divizor comun (CMMDC) a două numere în C++Copiuțe: Cifrele unui numărVectorii în C++: declarare și parcurgereAria unui triunghi folosind coordonatele acestora în C++Ce înseamnă endl în C++?Instrucțiunea for (structuri repetitive)Câte numere naturale sunt într-un interval dat? (C++)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortSuma elementelor unui vector recursiv în C++Cum să calculezi instant 2 la puterea N în C++Șiruri de caractere în C++. Tot ce trebuie să știiDivide et Impera (metodă de programare C++)Ce este o variabilă unsigned în C++?Cifra maximă a unui număr recursiv în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Cum să citești și să afișezi în fișiere în C++Verifică dacă trei puncte sunt coliniare C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Rădăcina cubică a unui număr în C++ (cube root)Al N-lea termen dintr-o progresie aritmeticăGenerarea șirului Fibonacci generalizat în C++Operații cu numere mari în C++ - Toate funcțiile explicateMaximul și minimul a două valori în C++Numărul de divizori primi ai unui număr în C++Bordarea unei matrice în C++Citirea și afișarea matricelor în C++Do while vs while în C++ - Care e diferența?Transformarea unei litere mici în literă mare în C++Numărul permutărilor în C++ (formula permutărilor)Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Tipuri de date în C++: numere întregi, reale, caractere și alteleVectori de frecvență (de apariții) în C++Maximul și minimul unui vector în C++Verifică dacă o literă este vocală în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicAl N-lea termen dintr-o progresie geometricăAlgoritm recursiv pentru căutare binară (clasa a X-a)Citește un șir de caractere cu spații în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Verificare dacă șir de caractere este palindrom în C++Complexitatea unui algoritm (timp și spațiu) în C++Ciurul lui Eratostene în C++Pointer în C++. Variabile de tipul char * (char steluță)Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Maximul și minimul a n valori în C++Cel mai semnificativ bit în C++Cel mai mic număr cu suma cifrelor N în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăTipul struct în C++. Ce sunt structurile de date neomogeneTransformarea unui număr din baza 10 în baza 2 în C++Oglinditul unui număr în C++Prima cifră a unui număr în C++Al N-lea termen Fibonacci în C++Ce înseamnă variabilă globală și locală în C++?Verifică dacă un caracter este literă în C++Numărul minim de peroane pentru o gară în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Șirul lui Fibonacci în C++Interschimbarea a două variabile în C++ (3 metode)Afișarea divizorilor primi ai unui număr în C++Comentarii în C++Cel mai frecvent element dintr-un șir în C++Căutare binară în C++Recursivitate în C++Instrucțiunea do while (structuri repetitive)Instrucțiunea de decizie în C++: if, else, switch, caseCombinatorică în C++: permutări, aranjamente, combinări și alteleCel mai puțin semnificativ bit în C++Verifică dacă un caracter este cifră în C++Cifra maximă și minimă a unui număr în C++Distanța dintre două puncte în C++Verificarea unui an bisect în C++Factorialul unui număr în C++Suma divizorilor unui număr în C++Matrice pătratice în C++. Diagonala principală și secundarăAflarea sumei primelor N sume GaussCea mai lungă secvență de elemente crescătoare în C++Suma numerelor naturale dintr-un interval dat în C++Mediana unui șir de valori în C++Funcții în C++. Ce sunt subprogrameleVerificare dacă un număr este palindrom în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Vectorii în C++: citire și afișareIndicatorul lui Euler în C++Maximul și minimul a trei valori în C++Structuri repetitive (while, do while, for, etc)Ce este o funcție void în C++?Interclasarea a doi vectori în C++Aria și circumferința unui cerc în C++Oglinditul recursiv al unui număr în C++Verifică dacă o literă este mică sau mare în C++Afișarea elementelor unui vector recursiv în C++Verifică dacă un număr aparține șirului Fibonacci în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont