Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WIPING46 - Bisekcja

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

Algorytm startuje z zadanego przedziału , a w kolejnych krokach obliczamy środek aktualnego przedziału:

I zmniejszamy go zgodnie z regułami:

  1. Jeśli , to

  2. Jeśli to


Dodane przez:Sławomir Wernikowski
Data dodania:2015-11-27
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 MAWK BC COFFEE DART FORTH GOSU JS-MONKEY KTLN OCT PROLOG R RACKET SQLITE SWIFT UNLAMBDA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.