Wszyscy znacie metodę Newtona do przybliżania pierwiastków funkcji, prawda? Moim celem w tym zadaniu jest wprowadzenie Cię w interesujący aspekt tego algorytmu.
Algorytm Newtona jest zbieżny tylko dla niektórych, ale przede wszystkim złożonych wartości wejściowych. Jeśli zobrazujesz zbieżność metody dla wszystkich wartości wejściowych na płaszczyźnie złożonej, zwykle otrzymasz piękny fraktal taki jak ten:
Dane techniczne
Celem tego zadania jest wygenerowanie takich fraktali. Oznacza to, że otrzymujesz wielomian jako dane wejściowe i musisz wydrukować odpowiedni fraktal jako obraz w wybranym formacie jako wynik.
Wkład
Dane wejściowe to oddzielona spacjami lista liczb zespolonych. Są zapisane w stylu <Real part><iImaginary part>
, jak ten numer:5.32i3.05
. Możesz założyć, że liczba wejściowa ma nie więcej niż 4 miejsca po przecinku i jest mniejsza niż 1000. Pierwszy z nich nie może być zerowy. Może to być na przykład dane wejściowe do Twojego programu:
1 -2i7,5 23 0004i-3,8 i12 0 5.1233i0,1
Liczby są interpretowane jako współczynniki wielomianu, zaczynając od najwyższej mocy. W pozostałej części tej specyfikacji wejściowy wielomian nosi nazwę P . Powyższe dane wejściowe są równe temu wielomianowi:
f (x) = x 5 + (-2 + 7,5 i ) x 4 + (23 0004 - 3,8 i ) x 3 + 12 i x 2 + 5,1233 + 0,1 i
Dane wejściowe mogą pochodzić z wejścia standardowego, z argumentu przekazanego do programu lub z monitu wyświetlanego programowi. Możesz założyć, że dane wejściowe nie zawierają żadnych początkowych ani końcowych znaków spacji.
Wykonanie
Fraktal musisz wyrenderować w następujący sposób:
- Wybierz tyle kolorów, ile korzeni P. i dodatkowy kolor dla rozbieżności
- Dla każdej liczby w widocznej płaszczyźnie określ, czy metoda jest zbieżna, a jeśli tak, z którym pierwiastkiem. Pokoloruj punkt zgodnie z wynikiem.
- Nie drukuj linijek ani innych fantazyjnych rzeczy
- Wydrukuj czarny punkt w punktach, które są pierwiastkami wielomianów dla orientacji. Możesz wydrukować do czterech pikseli wokół każdego katalogu głównego.
- Znajdź sposób, aby wybrać widoczną płaszczyznę w taki sposób, aby wszystkie korzenie były rozróżnialne i, jeśli to możliwe, szeroko rozłożone na niej. Chociaż nie jest wymagane idealne umieszczenie ramki wyjściowej, zastrzegam sobie prawo do odmowy przyjęcia odpowiedzi, która wybiera ramkę w niedopuszczalny sposób, np. zawsze na tych samych współrzędnych, wszystkie pierwiastki są w jednym punkcie itp.
- Obraz wyjściowy powinien mieć rozmiar 1024 * 1024 pikseli.
- Czas renderowania wynosi maksymalnie 10 minut
- Wystarczy zastosować zmiennoprzecinkowe wartości pojedynczej precyzji
Wydajność
Wyjście powinno być obrazem rastrowym w wybranym formacie pliku, odczytywalnym przez standardowe oprogramowanie dla systemu operacyjnego marki X. Jeśli chcesz użyć rzadkiego formatu, rozważ dodanie linku do strony internetowej, z której można pobrać przeglądarkę.
Wyjście pliku na standardowe wyjście. Jeśli twój język nie obsługuje stdout lub jeśli ta opcja jest mniej wygodna, znajdź inny sposób. W jakikolwiek sposób musi być możliwe zapisanie wygenerowanego obrazu.
Ograniczenia
- Brak bibliotek przetwarzania obrazu
- Brak bibliotek generujących fraktale
- Najkrótszy kod wygrywa
Rozszerzenia
Jeśli podoba Ci się to zadanie, możesz spróbować pokolorować punkty zgodnie z prędkością zbieżności lub innymi kryteriami. Chciałbym zobaczyć ciekawe wyniki.
Odpowiedzi:
Python,
827777 znakówZnajduje granice wyświetlania (i pierwiastki), znajdując punkty zbieżności dla grupy losowych próbek. Następnie rysuje wykres, obliczając punkty zbieżności dla każdego punktu początkowego i używając funkcji skrótu, aby uzyskać losowe kolory dla każdego punktu zbieżności. Przyjrzyj się bardzo uważnie i zobaczysz zaznaczone korzenie.
Oto wynik przykładowego wielomianu.
źródło
Java,
1093 1058 10991077 znakówDane wejściowe to argumenty wiersza polecenia - np
java F 1 0 0 -1
. Uruchom . Dane wyjściowe są wysyłane na standardowe wyjście w formacie PPM (piksel ASCII).Skalę wybiera się za pomocą Fujiwary związanej z wartością bezwzględną złożonych pierwiastków wielomianu; Następnie mnożę to ograniczenie przez 1,5. Dostosowuję jasność za pomocą współczynnika konwergencji, więc korzenie będą w najjaśniejszych łatach. Dlatego logiczne jest używanie bieli zamiast czerni do zaznaczania przybliżonych lokalizacji korzeni (co kosztuje mnie 41 znaków za coś, czego nie można nawet zrobić „poprawnie”. Jeśli oznaczę wszystkie punkty, które zbiegają się w granicach 0,5 piksela od siebie następnie niektóre pierwiastki wychodzą nieoznakowane; jeśli oznaczę wszystkie punkty, które zbiegają się w obrębie 0,6 piksela od siebie, wówczas niektóre pierwiastki wyjdą oznakowane na więcej niż jednym pikselu; więc dla każdego pierwiastka oznaczam pierwszy napotkany punkt, który zbiegnie się w granicach 1 piksela od siebie ).
Obraz dla przykładowego wielomianu (przekonwertowanego do png za pomocą GIMP):
źródło
x^6-9x^3+8
, starannie zaprojektowane przez wybranie korzeni, a następnie użycie Wolfram Alpha w celu uproszczenia wielomianu. Ok, oszukiwałem zamieniając odcienie w GIMP.Python, 633 bajty
Po przyspieszeniach i upiększaniu (756 bajtów)
Poniższy wykres dotyczy funkcji Newtona Fraktala log (z).
źródło
;
. Usuń także wszystkie możliwe spacje.matplotlib
tutaj), więc nie ma gwarancji, że nadal działa.