4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Bisekcja

Znajdowanie pierwiastków równań nieliniowych jest jednym z podstawowych zagadnień metod numerycznych. Twoim zadaniem będzie znalezienie miejsca zerowego wielomianu w podanym przedziale z zadaną dokładnością.

Metoda bisekcji jest prostą metodą iteracyjną, bazującą na założeniu mówiącym o istnieniu pierwiastka w zadanym przedziale o krańcach w a i b:

f(a) ∙ f(b) < 0

co oznacza, że funkcja f zmienia znak wewnątrz przedziału <a..b>, a więc musi tam przechodzić przez zero.

Algorytm startuje z zadanego przedziału , a w kolejnych krokach oblicza się środek bieżącego przedziału jako:

x = (a + b) / 2

a następnie zwęża się go zgodnie z regułą:

• jeśli f(a) * f(x) < 0 to b = x
• jeśli f(b) * f(x) < 0 to a = x

Algorytm zatrzymuje się, gdy spełniony jest warunek o dokładności:

|f(x)| < ε

gdzie ε to zadana dokładność tj. odchyłka wartości funkcji od zera w środku przedziału.

Uwagi:

• za pierwszą iterację przyjmij obliczenie środka podanego przedziału
• zwiększaj iteracje na końcu pętli tj. po wyznaczeniu nowego środka przedziału i jego zawężeniu

Wejś›cie

4 wiersze tekstu zawierające kolejno:

• stopień wielomianu n (liczba całkowita, 1 < n < 20)
• współczynniki wielomianu od najniższej do najwyższej potęgi (liczby całkowite z przedziału <-100..100>)
  
• krańce przedziału, w którym może znajdować się szukane rozwiązanie (liczby całkowite z przedziału <-100..100>)
• dopuszczalny błąd ε (liczba rzeczywista z przedziału <10^-10..1>
  

Wyjś›cie

2 wiersze tekstu zawierające kolejno:

• znalezione rozwiązanie zaokrąglone do 8 miejsc po przecinku
• liczbę iteracji, w której znalezione to rozwiązanie

W przypadku braku miejsca zerowego w podanym przedziale należy wyprowadzić dwa wiersze zawierające kolejno:

0.0
0

Przykł‚ad

Wejś›cie: 

2
-4 0 1
0 3
0.01

Wyjście:

1.99804688
9

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 4,0