Jun 2017
1 / 4
Jun 2017
Jun 2017
cyberstormppc
Jun '17

Nie widzę nigdzie dyskusji o tym zadaniu więc otwieram temat.
Mój kod : http://ideone.com/E9hRBb51
Prawdopodobnie zwraca dobry wynik ale jest za wolny, po początkowym pomyśle który dla maksymalnego promienia z zadania 36963 wyznaczał wynik ( 4292242973 - czy jest prawidłowy nie wiem bo przekraczam limit czasu ) w około 160 sekund teraz wyznacza wynik w około 60 sekund co jest wraz o wiele za wolno.
..................
Program oblicza ilość punktów dla 1/4 koła i bez punktu 0,0, a potem mnożę wynik *4 i dodaje 1 czyli punkt 0,0.
Dodatkowo gdy współrzędne odległości są w sumie mniejsze niż promień dodaje punkt automatycznie bez obliczeń żeby przyśpieszyć działanie programu. Automatycznie tez nie liczę dystansu od środka koła jeśli punkt liczony poprzednio w tej samej płaszczyźnie tylko mniejszy o 1 już był poza kołem.
............
Mimo zastosowania tych wszystkich pomysłów mój program jest nadal tysiące razy za wolny w stosunku do wymagań autora zadania i sądzę że zapewne trzeba użyć jakiegoś wzoru z użyciem Pi lub obliczania stopni kątów itp.
Jako że szkołę kończyłem wieki temu i mało już z niej pamiętam chciałbym poprosić Was o podpowiedź jak należy wykonać to zadanie. Może być link to potrzebnego wzoru / opisu algorytmu bez dokładnych wyjaśnień gdyż zależy mi żeby się uczyć a nie iść na łatwiznę.

  • created

    Jun '17

  • last reply

    Jun '17
  • 3

    replies

  • 860

    views

  • 3

    users

  • 1

    like

  • 6

    links

loginus
Jun '17

Masz dobry pomysł żeby liczyć tylko 1 ćwiartkę koła - też tak zrobiłem .
Niestety nie mogę zrozumieć swojego algorytmu gdyż nie dałem do niego żadnego komentarza .
Jeżeli masz poprawny algorytm który daje prawidłowe wyniki dla małych promieni - to wygeneruj pierwsze kilkanaście wyników dla kolejnych rosnących wartości promienia - i wrzuć na encyklopedię liczb23 . - Ja tak zawsze robię jak nie moge wyprowadzić wzoru na kolejne wartości ( a mój algorytm ma kosmiczną złożoność ) - podejrzewam że autorzy zadań specialnie nie dają kilku przykładowych wartości pod rząd żeby nie dało się tak wrzucając na encyklopedie szybko znaleść wzoru .

https://www.youtube.com/watch?v=NaL_Cb42WyY13 -- luknij tez na ten film .

Najwięcej w twoim rozwiązaniu zajmuje obliczanie pierwiastka - jak byś z tego zrezygnował to ......

cyberstormppc
Jun '17

Dziękuję za podpowiedzi.
"
PS
Dla r = 36963 mój program podaje: 4292242373
"
Błąd był z winy użycia złej zmiennej, float zamiast double, ale ostatecznie i tak zrezygnowałem z używania zmiennoprzecinkowych. To zadanie nauczyło mnie że operacje stałoprzecinkowe są dużo szybsze.

"
https://www.youtube.com/watch?v=NaL_Cb42WyY28 -- luknij tez na ten film .
"
Świetny film dzięki, szkoda po angielsku, ale przynajmniej autor mówi powoli i wyraźnie więc za drugim podejściem zrozumiałem :slight_smile:

Mam wynik 0,98 sek, ale jeszcze myślę nad zrobieniem tablicy z wynikami bez kilkukrotnego liczenia, może jeszcze dzięki temu przyśpieszy. Kolega Narbej zaszalał z tymi 0,17 sekundy więc coś chyba jeszcze można pokombinować.....