Sprawdź Wielokąt

Zadanie

Sprawdź czy z podanych n boków można ułożyć figurę o n kątach. Do rozwiązania tego zadania trzeba uogólnić nierówność trójkąta, która pozwala sprawdzić czy istnieje trójkąt o podanych długościach boków. Program powinien wczytać tablicę n wartości, które mogą być w dowolnej kolejności.

Definicja

Wielokąt o n bokach można skonstruować jeśli najdłuższy bok jest krótszy niż suma wszystkich pozostałych boków.

Przykład

Poniżej zostały przedstawione dwa trójkąty oraz boki ułożone w rzędzie dla porównania najdłuższego z pozostałymi. W obu przypadkach najdłuższy jest zielony odcinek.

Poprawne dane

Niepoprawne dane

Jak można zauważyć na pierwszym obrazku jeśli najdłuższy jest krótszy niż suma pozostałych to jest możliwe, aby pozostałe "odstawały" i tworzyły trójkąt. W drugim przypadku nie jest możliwe wyciagnięcie boków tak bardzo, aby utworzyć trójkąt. Należy też pamiętać, że jeśli najdłuższy bok równa się długości pozostałych to też nie powstaje figura, ponieważ wszystko składa się wtedy w jeden odcinek.

Implementacja

Poniższa funkcja SprawdzWielokat() sprawdza czy z podanych boków w dane można utworzyć figurę:

1. bool SprawdzWielokat(vector<int> dane) {
2.   int suma = 0;
3.   int maksimum = 0;
4.   for (int i = 0; i < dane.size(); i++) {
5.     suma += dane[i];
6.     if (dane[i] > maksimum) {
7.       maksimum = dane[i];
8.     }
9.   }
10.   return suma > 2 * maksimum;
11. }

Algorytm początkowo inicjalizuje sumę oraz długość maksymalnego boku na 0. Następnie dla każdej wartości na liście dolicza ją do sumy i aktualizuje na bieżąco maksymalną wartość. Na koniec w sumie też jest zawarty najdłuższy bok, więc wystarczy sprawdzić warunek czy suma jest większa od podwojnej długości najdłuższego, znalezionego boku.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystać z poniższego fragmentu programu:

1. int main () {
2.   int n, tmp;
3.   cout << "Ile wartosci?\n n = ";
4.   cin >> n;
5.   vector<int> dane;
6.   cout << "Podaj wartosci:" << endl;
7.   for (int i = 0; i < n; i++) {
8.     cin >> tmp;
9.     dane.push_back(tmp);
10.   }
11.   bool wynik = SprawdzWielokat(dane);
12.   cout << "Wielokat" << (wynik ? "" : " nie") << " istnieje";
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja