Triunghiuri & Triunghiuri1(Pbinfo #660 & #661)

#Triunghiuri

Cerință: Se dau n numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.

Pentru rezolvarea acestei probleme sunt necesare cunoștințe de sortare a vectorilor.

Această problemă are la bază elementul definitoriu al fiecărui triunghi, și anume proprietatea care spune că suma lungimilor oricăror două laturi ale unui triunghi trebuie să fie strict mai mare decât lungimea celei de-a treia latură.

Soluția ce oferă 100 de puncte necesită un algoritm de sortare de vector (la alegere) și trei structuri repetitive (una pentru fiecare posibilă latură) care vor căuta în cadrul vectorului elementele care îndeplinesc condiția precizată mai sus:

if( ( triunghi[latura1] + triunghi[latura2] > triunghi[latura3] ) && ( triunghi[latura1] + triunghi[latura3] > triunghi[latura2] ) && ( triunghi[latura2] + triunghi[latura3] > triunghi[latura1] ) )

Desigur, această interpretare îi dă un aer complicat. Datorită faptului că sortăm vetorul înainte de a intra în structurile repetitive, condiția se simplifică considerabil, ajungând la:

if( ( triunghi[latura1] + triunghi[latura2] > triunghi[latura3] )

Mult mai lizibil acum, nu-i așa? Concluzionăm: citire -> sortare elemente -> căutare elemente -> afișare număr de triunghiuri.

Soluție în C++:

#Triunghiuri1

Cerință: Se dau n numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.

Pentru această problemă sunt necesare cunoștințe de sortare de vectori(mai precis Quick Sort sau Binery Insertion Sort) sau funcția sort din librăria <algorithm>.

În cazul acestei probleme, tactica anterioară nu mai funcționează eficient, deoarece numărul de elemente din vector de mărește considerabil, de la maxim 100 la maxim 1000. Dacă veți folosi sursa anterioară la această problemă, veți primi doar 20 de puncte, din cauza limitei de timp depășită.

Soluția eficientă implică un algoritm eficient de sortare de vectori și o altă perspectivă asupra căutării lungimilor laturilor. Pentru a sorta vectorul, putem folosi, fie Binary Insertion Sort, fie Quick Sort(vezi Sortări de vectori) sau am putea folosi, mai simplu, funcția sort din librăria <algorithm.h>. Această funcție predefinită combină doi algoritmi eficienți din două puncte de vedere diferite.

Funcția sort arată așa: sort(adresa primului element, adresa ultimului element); . Astfel, pentru un vector v de n elemente, vom avea: sort(v, v+n); . Acest mod de a scrie adresele primului și ultimului element are la bază lucrul cu pointeri

După ce realizăm sortarea vectorului ce conține lungimile de laturi, trebuie să abordăm într-o altă modalitate problema căutării eficiente a 3 elemente care satisfac condiția despre care am vorbit la problema de mai sus. Vom folosi, de asemenea, 3 structuri repetitive for și vom schimba atât condiția de oprire a ultimului for, cât și modul în care vom număra triunghiurile realizabile.

Vom căuta toate perechile de laturi din vector și pentru fiecare pereche identificăm toate posibilitățile de alegere a celei de-a treia laturi. În cadrul condiției celui de-al treilea for vom introduce condiția folosită anterior în structura decizională if, și astfel vom ști exact până când există triplete care satisfac condiția. Pentru a reține numărul de triunghiuri, vom folosi o variabilă în care vom adăuga, după finalizarea căutării unui al treilea element, numărul de laturi proaspăt parcurse. Acest lucru va garanta viteză.

Concluzionăm: citire->sortare eficientă->căutare eficientă->afișare număr de triunghiuri.

Soluție în C++:

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest sit folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.

octombrie 2018
L Ma Mi J V S D
« sept.   feb. »
1234567
891011121314
15161718192021
22232425262728
293031