Ostatnio stwierdziłem, że zabiorę się za zadania ze SPOJ. Już na pierwszym zadaniu spotkałem się z przeszkodą. Mianowicie program nie chce mi przejść testów. Co ciekawe w konsoli, na moim komputerze, wszystko działa.
Treść zadania to:
Sprawdź, które spośród danych liczb są liczbami pierwszymi
Link do zadania:
Proszę o wytłumaczenie mi, jak ten kod ma wyglądać, żeby zadziałał.
Poniżej mój kod:
def is_prime?(n)
return "NIE" if n < 2
if (2..Math.sqrt(n).floor).none?{ |i| (n % i).zero? }
return "TAK"
else
return "NIE"
end
end
is_prime? n
Każde zadanie na SPOJu musi wczytywać dane ze standardowego wejścia i wypisywać na standardowe wyjście.
Proponuję Ci zacząć od zadania testowego http://pl.spoj.com/problems/PTEST/. Trzeba tu wczytać 2 liczby i wypisać ich sumę na ekran.
Rozwiązanie:
a = gets.to_i
b = gets.to_i
puts a + b
Testowanie tego programu wpisując ręcznie z klawiatury dane byłoby męczące. Zatem polecam zapisać sobie dane wejściowe do pliku test.in i uruchamiać program przekierowując na wejście z niego dane:
$ cat test0.in
2
3
$ ruby solver.rb < test0.in
5
Inne metody które możesz używać do wczytywania danych to:
wszystkie metody wczytujące z obiektu $stdin
metody gets, readline, readlines
Do wypisywania możesz użyć:
metod obiektu $stdout
puts, print, putc, printf itp.
W zadanich typu PRIME_T musisz obsłużyć dynamiczną ilość danych. Tutaj w pierwszej linii masz podaną liczbę, która mówi ile kolejnych linii musisz wczytać i przetworzyć. Program wykorzystujący Twoją metodę is_prime? wyglądałby tak:
n = gets.to_i
n.times do
number = gets.to_i
puts is_prime?(number)
end
Lepiej (czyściej) byłoby jednak żeby metoda is_prime? zwracała wartość true/false aniżeli napis tak jak to robi obecnie.
@radarek, @korowiov87, @Lypa
Ok, już wiem na czym rozwiązywanie na spoj polega. Nie zrozumiałem, że należy zastosować metody zczytujące dane.
Dzięki wielkie chłopaki za pomoc.
Kod który tam zastosowałem:
n = gets.to_i
def is_prime?(n)
return false if n < 2
(2..Math.sqrt(n).floor).none?{ |i| (n % i).zero? }
end
n.times do
num = gets.to_i
if is_prime?(num)
puts "TAK"
else
puts "NIE"
end
end
Pytanie, czy można go jeszcze jakoś uprościć lub zoptymalizować?
Dodatkowe pytanie. Czy jest możliwość sprawdzenia najlepszych odpowiedzi, po wysłaniu własnej?
Twój kod jest w porządku. Czy można go zoptymalizować? Zachowując algorytm to niewiele można tu poprawić. Istnieją pewne sztuczki, które trochę przyspieszą Twój program, ale kod przestanie być “the ruby way”. Na przykład zobacz czy zamieniając wywołanie Range#none? na pętlę while kod przyspieszy. Takich sztuczek jest więcej, ale nie będę psuł Ci zabawy w poszukiwaniu ich :).
W tym konkretnym zadaniu możesz jeszcze spróbować użyć standardowej biblioteki Rubiego prime.
Warto też przyjrzeć się zakresom i rozmiarom danych jakie w zadaniu występują.
@radarek, @RORMaster
A czy istnieją jakieś metody lub zestawienia odnośnie wyznaczania, ile dany proces będzie trwał. Jako, że nigdy nie zagłębiałem się w testowanie szybkości działania skryptu, to takie sprawdzanie trochę na ślepo jest czasochłonne.
No ile będzie trwał to zależy od zbioru danych i złożoności O.
Użycie benchmarka jest proste, pobaw sie i porównaj sobie iteratory, pętle itp. ruby-benchmark
Do tego zadania, można użyć sita eratostenesa: https://pl.wikipedia.org/wiki/Sito_Eratostenesa. Tak jak kolega wcześniej napisał, można użyć biblioteki prime, gdzie jest zaimplementowane sito. Lecz w przypadku zadań na spoju czy codeforces, warto zapoznać się z danym algorytmem i go zaimplementować
@radarek, @highassfak, @korowiov87
No cóż po wielu próbach poniżej 0.1 nie zszedłem. Co do biblioteki prime wynik był gorszy niż zazwyczaj.
Poniżej jest kod który zaimplementowałem.
def is_prime?(n)
return false if n < 2
i, range = 2, Math.sqrt(n).floor
while i <= range
return false if (n % i) == 0
i += 1
end
true
end
gets.to_i.times { puts is_prime?(gets.to_i) ? "TAK" : "NIE" }
Na pewno też da się ten kod zrobić jeszcze bardziej wydajnym. Pytanie tylko, czy lepiej implementować taki kod, czy bardziej w stylu “the ruby way”?
Sam musisz sobie stawiać cele. Dla mnie spoj nie jest miejscem gdzie piszę ładny, dopieszczony kod. To staram się robić na co dzień w pracy. Na spoju wcielam się w rolę ‘hackera’ i próbuję często robić rzeczy, które normalnie się nie robi. One mimo wszystko też uczą myślenia i kombinowania. To potem w jakiś sposób przekłada się na praktyczne umiejętności.
Myślę, że nie ma sensu katować jednego zadania za długo. Jest duża szansa, że rozwiązując kolejne odkryjesz nowe sztuczki i wtedy wrócisz do poprzednich zadań. Ja tak robiłem wielokrotnie (choćby po odkryciu, że pętla while jest ciut szybsza od pętli działających na blokach).
Pamiętaj też, że wiele zadań na spoju nie da się rozwiązać w ruby z uwagi na wygórowane limity czasowe. Zawsze warto sprawdzić czy już ktoś rozwiązał dane zadanie w tym języku.
Podsumowując: idź dalej, rozwiązuj kolejne zadania, miej z tego radochę. Z pewnością dużo się przy tym nauczysz :).
