[c++] rozwiązanie równania

rochaj · Post autor: **rochaj** » 22 gru 2014, o 07:38

Mamy równanie \(\displaystyle{ x^3+ax=b}\), chcemy je rozwiązać w liczbach całkowitych. Użytkownik podaje liczby całkowite a i b, a program ma wyliczyć x. Mam taki problem gdy przechodzę pętlą wszystkie x to następują przekroczenie czasu (1 s). Dzieje się to w przypadku gdy x=565773. Jak się da jakoś inaczej to rozwiązać?

luka52 · Post autor: **luka52** » 22 gru 2014, o 07:54

Zamiast sprawdzać każdy \(\displaystyle{ x}\) można sprytniej: ... nonicznych

rochaj · Post autor: **rochaj** » 22 gru 2014, o 07:58

luka52 pisze:Zamiast sprawdzać każdy \(\displaystyle{ x}\) można sprytniej: ... nonicznych

Aha zapomniałem dodać że nie można używać tych wzorów.

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 08:01

rochaj pisze:Aha zapomniałem dodać że nie można używać tych wzorów.

To może powiedz od razu, co można używać, a czego nie. Bo będziemy sobie tak dyskutować, dyskutować, a w końcu i tak nie na temat.

Wolfram mówi, że rozwiązanie jest w liczbach całkowitych, gdy \(\displaystyle{ b=a+1}\). To jest kod do sprawdzaczki?

rochaj · Post autor: **rochaj** » 22 gru 2014, o 08:12

Vardamir pisze:
rochaj pisze:Aha zapomniałem dodać że nie można używać tych wzorów.
To może powiedz od razu, co można używać, a czego nie. Bo będziemy sobie tak dyskutować, dyskutować, a w końcu i tak nie na temat.

Wolfram mówi, że rozwiązanie jest w liczbach całkowitych, gdy \(\displaystyle{ b=a+1}\). To jest kod do sprawdzaczki?

Tak to do sprawdzarki. Liczby a i b to podaje użytkownik i jeśli istnieje rozwiązanie to program wylicza x. Użytkownik nie wie kiedy jest rozwiązanie.

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 08:27

Wczytaj \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Sprawdź czy spełniają warunek \(\displaystyle{ b=a+1}\). Jeśli tak, to rozwiązanie \(\displaystyle{ x=1}\), jeśli nie to nie ma rozwiązania w liczbach całkowitych.

rochaj · Post autor: **rochaj** » 22 gru 2014, o 08:35

Vardamir pisze:Wczytaj \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Sprawdź czy spełniają warunek \(\displaystyle{ b=a+1}\). Jeśli tak, to rozwiązanie \(\displaystyle{ x=1}\), jeśli nie to nie ma rozwiązania w liczbach całkowitych.

ale czemu mam się ograniczać tylko do \(\displaystyle{ b=a+1}\)? bo np. dla a=3,b=14,x=2?

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 08:40

Źle popatrzyłem na to co zwraca mi wolfram, to było tylko przykładowe rozwiązanie. Są jakieś ograniczenia na \(\displaystyle{ a,b,x}\) ?

rochaj · Post autor: **rochaj** » 22 gru 2014, o 08:46

Vardamir pisze:Źle popatrzyłem na to co zwraca mi wolfram, to było tylko przykładowe rozwiązanie. Są jakieś ograniczenia na \(\displaystyle{ a,b,x}\) ?

Tylko ze całkowite dodatnie.

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 09:05

rochaj pisze: Tylko ze całkowite dodatnie.

Aż tyle, wklejaj następnym razem treści zadań bo nie podajesz najważniejszych informacji.

Masz funkcję \(\displaystyle{ f(x)=x^3+ax-b}\), która jest rosnąca. Możesz skorzystać np. z metody bisekcji.

rochaj · Post autor: **rochaj** » 22 gru 2014, o 09:09

Vardamir pisze:
rochaj pisze: Tylko ze całkowite dodatnie.
Aż tyle, wklejaj następnym razem treści zadań bo nie podajesz najważniejszych informacji.

Masz funkcję \(\displaystyle{ f(x)=x^3+ax-b}\), która jest rosnąca. Możesz skorzystać np. z metody bisekcji.

Też myślałem o tej metodzie, ale to zadanie jest w temacie Wyszukiwanie binarne.

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 09:15

Bisekcja jest wyszukiwaniem binarnym...

rochaj · Post autor: **rochaj** » 22 gru 2014, o 09:22

Vardamir pisze:Bisekcja jest wyszukiwaniem binarnym...

A da się jakoś bez tej metody, bo już próbowałem jakimś naciąganiem żeby się zmieścić w czasie:

Kod: Zaznacz cały

long long row( long a, long b)
{
float f   = ((float)1.0)/(float(3.0));	
long long i=1,k=0;
   do
   {
   	if (i*i*i+a*i==b) 
   	k=i; 
   	i++;
   } while(i<=pow(b,f));
    cout<<k<<endl;	
}

Vardamir · Post autor: **Vardamir** » 22 gru 2014, o 09:38

Przed chwilą mówiłeś, że dział to wyszukiwanie binarne. Teraz nie chcesz z niego korzystać?

Przecież metoda bisekcji dla każdego przypadku wykona co najwyżej 32 sprawdzeń (w zakresie unsigned int), zatem na pewno zmieści się w czasie. Obstawiałbym nawet czas <0.02

To co zamieściłeś będzie strasznie niewydajne, m.in przez korzystanie z potęgi do 1/3.

rochaj · Post autor: **rochaj** » 22 gru 2014, o 09:56

a w jakim przedziale badac?