Problem z zadaniem ze SOPJ'a - "funkcja kwadratowa".

0

Mimo prawidłowych wyników, program nie jest akceptowany przez sędziego.
Tutaj link do zadania: http://pl.spoj.com/problems/ROWNANIE/

#include <iostream>

using namespace std;

int main()
{
	int l_test, wynik[100];
	cin >> l_test;
	for(int i=0; i<l_test; i++)
	{

		float a, b, c;
		cin >> a >> b >> c;
		
		if((b*b)-4*a*c == 0) { wynik[i] = 1; }
		else if ((b*b)-4*a*c < 0) { wynik[i] = 0; }
		else if ((b*b)-4*a*c > 0) { wynik[i] = 2; }

	}
	
	for(int i=0; i<l_test; i++)
	{
		cout << wynik[i] << endl;
	}

}

Zakładam, że problem tyczy się: "Na wejście programu podana zostanie pewna nieokreślona, ale niewielka ilość zestawów danych...". Ale czym jest ta pewna, nieokreślona ilość zestawów (założyłem, że będzie ich do 100), i czy dobrze podaję ją na wejściu?

1

Nie wiem czy to przyczyna problemu, ale nie musisz pamiętać wszystkich wyników, możesz je wypluwać na bieżąco i wczytywać kolejny zestaw danych.

0

hmm, przerobiłem na wersję bez zapamiętywania, i też nie przechodzi - "przekroczono limit czasu". Czy ze względu na nieskończoną pętlę?

#include <iostream>
 
using namespace std;
 
int main()
{
    int wynik;
    
    while(1)
    {
	        float a, b, c;
	        cin >> a >> b >> c;
	 
	        if((b*b)-4*a*c == 0) { wynik = 1; }
	        else if ((b*b)-4*a*c < 0) { wynik = 0; }
	        else if ((b*b)-4*a*c > 0) { wynik = 2; }
	        
	        cout << wynik << endl;	
	}
 
	return 0;
}
1

Tak, musisz przerobić wczytywanie danych tak, aby gdy napotka pustą linię skończył działanie, a nie wisiał na cin.

0
nie100sowny napisał(a):

Tak, musisz przerobić wczytywanie danych tak, aby gdy napotka pustą linię skończył działanie, a nie wisiał na cin.

Okej, udało się. Powinni doprecyzować polecenie. Przechodzi kiedy while(licznik<10) , ale while(licznik<100) już nie chciało przyjąć.

0

Zrozum, że masz zmienną ilość linii. Więc musisz wykryć pustą linię. Zamień cin na scanf, który zwraca -1 gdy osiągnął koniec.

0

Jeśli będę inkrementować ustawiony licznik, to w końcu natrafi na pustą linię.

1

Zadanie w których nie wiadomo ile będzie zestawów, robisz tak

#include <iostream>

using namespace std;

int main()
{

    float a, b, c;
    while(cin >> a >> b >> c)
    {
            int wynik;
            if((b*b)-4*a*c == 0) { wynik = 1; }
            else if ((b*b)-4*a*c < 0) { wynik = 0; }
            else if ((b*b)-4*a*c > 0) { wynik = 2; }

            cout << wynik << endl;
    }

    return 0;
}
2

po co ten copy paste, lepiej by bylo dodac sobie zmienna d = b*b - 4 * a * c

3

klasyczny przykład złego porównywania liczb zmiennoprzecinkowych, przykład gdzie wynikiem mają być same jedynki:
https://wandbox.org/permlink/yT6yDvJqVVRYLNwv
Pamiętaj, że liczby zmiennoprzecinkowe mają ograniczoną precyzję więc możesz porównywać liczby, które powinny być równe, ale różnią się z powodu ograniczeń precyzji.

0

Akruat w tym przypadku porównanie do zera za pomocą "==" jest jak najbardziej rozsądne - wynika ze wzoru na x1 i x2, gdzie z delty bierze się pierwiastek i gdy delta == 0, to dla wprowadzonych danych nie ma dwóch rozwiązań, a jedno. Dodajmy też, że dla |a| < 1 pierwiastek aktualnie zwiększa wartość liczby (przykład: a = 0.81, sqrt(a) = 0.9), co dodatkowo odsuwa nas od epsilona maszynowego. Problemem, który nakreślił przedmówca jest użycie błędnych danych wejściowych - tzn. takich, które nie zmieszczą się w reprezentacji (0.1 to ułamek okresowy w systemie binarnym).

Na poparcie moich słów, fragment faktoryzacji LU w LAPACKu: http://www.netlib.org/lapack/explore-html/d1/dfc/dgetrf2_8f_source.html
Linijka 178, porównywanie elementu na diagonali z 0. Robione dokładnie za pomocą ".EQ.". Stabilność numeryczną gwarantuje się w takim przypadku pivotowaniem.

0

To zadanie jest po prostu źle przygotowane. Dla danych wejściowych 1 -2.00000000000000000000000000000000001 1 każdy "poprawny" program padnie. I te dane z fajnego linku Marka też. A przecież to banalne zadanie, a nie ciężki problem zmiennoprzecinkowy. Powinno być ograniczenie do liczby znaków po przecinku, albo integer.

0
jarekczek napisał(a):

To zadanie jest po prostu źle przygotowane.

przesadzasz, jakos ponad 7k osob dalo rade rozwiazac co dosc dobitnie sugeruje ze nie ma tu rocket science i najprostsze rozwiazanie przejdzie.

1

Pisałem to już z 10 razy tutaj, ale powtórzę.
Liczby zmiennoprzecinkowe mają skończoną precyzję. Na dodatek cześć prostych liczb zapisanych systemie dziesiętnym nie ma dokładnej reprezentacji binarnej.
Przykładowo 0.2 komputer nie potrafi zapisać w double dokładnie. To jest dokładnie tak samo jak nie da się zapisać 1/3 w systemie dziesiętnym: 0.33333(3).
Czyli każdą liczbę należy traktować jako zapisaną z pewną skończoną dokładnością.
Do tego służy stała DBL_EPSILON, albo lepiej w stylu C++ wartość epsilon z szablonu numeric_limits.
Mnożąc wartość bezwzględną dowolnej wartości przez epsilon uzyskujemy minimalny (najlepszą) niepewność danej wartości wynikającą z architektury danego typu zmiennoprzecinkowego.
Do tego dochodzi kumulowanie się tych błędów po obliczeniach. W przypadku obliczania delty należy wziąć to pod uwagę.
Jak dane obarczone są błędami to poleganie na ścisłej równości skazane jest na porażkę jak to pokazałem tutaj: https://wandbox.org/permlink/yT6yDvJqVVRYLNwv
Większość linijek w zapisie dziesiętnym jest ściśle pasuje do delta==0, ale dodałem też parę linijek gdzie nawet w zapisie dziesiętnym nie ma ścisłej reprezentacji danych wejściowych.

Gotowca pokazującego jak powinno się obchodzić ten problem mam od dawna, ale go nie pokażę dopóki zainteresowani troszkę się nie pomęczą i nie zainteresują problemem.

0

Z tego, co mnie uczono, to:

  1. Porównywania do 0 (ani do jakiejkolwiek liczby) nie należy używać do przerywania pętli, np. poniższy kod jest zły"
double a = 1.0;
while (a != 0.0)
	a -= 0.1;
  1. We wzorach matematycznych można używać porównania do zera, jak to zostało zrobione powyżej i jak to robi się w przypadku faktoryzacji LU. Tylko trzeba wiedzieć kiedy. Danych 0.1, 0.6, 0.9 nikt znający się na numeryce w życiu by nie użył w kontekście tego problemu, bo wiadome jest, że sama ich reprezentacja jest niemożliwa do zapisu w komputerze. Ciekawe, że z porównywaniem do zera SPOJ akceptuje rozwiązania, nie?
0

Marku, Twój przykład jest błędny. Rozwiązaniem wcale nie są same jedynki. Tu masz dowód: https://wandbox.org/permlink/wPZYtJ7FamcOuwvz To jest rozwiązanie w Groovy (taka inna Java).

Do prawdziwego rozwiązania tych zadań potrzebne jest arbitrary precision arithmetic. 2 znane języki, które to potrafią, to Java i Python. Wtedy można, a nawet należy, porównywać z zerem.

Ale to oczywiście akademicka dyskusja, bo na spoju dali przykłady z 1 miejscem po przecinku i eps = 0.01 wystarcza do przejścia.

1 użytkowników online, w tym zalogowanych: 0, gości: 1