„Główna żaba” to dziwne zwierzę, które przeskakuje między liczbami całkowitymi, aż dotrze 3 lub 19 ...
Twój program powinien przyjmować liczbę całkowitą n
jako dane wejściowe i wyjściowe wyniku poniższego algorytmu ( 3
lub 19
).
Dla danej liczby całkowitej n >= 2
:
- Niech
f
będzie pozycja żaby. Początkowo jest ustawiony nan
- if
f = 3
lubf = 19
: żaba przestaje skakać - zatrzymać program i wyjścief
. - if
f
jest liczbą pierwszą: żaba skacze na pozycję2×f-1
. Wróć do kroku 2. - jeśli
f
jest mieszany: niechd
będzief
„s największym prime dzielnik. Żaba skacze na pozycjęf-d
. Wróć do kroku 2.
Przykłady:
Przykład z n = 5
:
5 > 9 > 6 > 3 stop
Program powinien wyjść 3
.
Kolejny przykład z n = 23
:
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
Ponownie program powinien wypisać dane 3
.
Przypadki testowe:
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
Możesz założyć 1 < n < 1000000
(sprawdziłem końce programu pod kątem tych wartości).
3
lub19
, możemy zmienić pozycję 2. w algorytmie, aby powiedzieć, że jeśli żaba weszła w jakąkolwiek pętlę (napotkała pozycję, którą widział wcześniej), wówczas zatrzymuje skok i zwraca najmniejszą członek tej pętli.Odpowiedzi:
Python 2 ,
101939290888785 bajtówWypróbuj online!
źródło
while~16&n!=3
zapisuje bajt.~16&n-3
nawet działa!C (gcc),
8765 bajtówWypróbuj online!
Wyjaśnienie:
Wersja przenośna (72 bajty):
Wypróbuj online!
Z bardziej odpowiednimi nazwami zmiennych:
Wypróbuj online!
źródło
Siatkówka ,
6362 bajtyPodziękowania dla Neila za zaoszczędzenie 1 bajtu.
Wypróbuj online!
Wejścia i wyjścia w jednostkowej (zestaw testów używa dziesiętnego dla wygody). To rozwiązanie staje się niezwykle wolne w przypadku większych nakładów. W
9983
przypadku testowego razy na na TIO.Wyjaśnienie
Z tego powodu
{
oba etapy programu są po prostu uruchamiane w pętli, aż nie będą już miały wpływu na ciąg. Przeplatamy kompozyty przetwarzania etapowego i liczby pierwsze przetwarzania etapowego. To pozwala nam uniknąć rzeczywistego warunku (który tak naprawdę nie istnieje w Retina). Jeśli bieżąca wartość jest nieodpowiednia dla sceny, scena po prostu nic nie robi.Przetwarza to kompozyty. Dopasowujemy potencjalny dzielnik
(11+)
, ale sprawdzamy, czy nie jest on złożony(?<!^\2+(11+))
, więc bierzemy pod uwagę tylko czynniki pierwsze. Ze względu na chciwość+
priorytetem jest największy czynnik. Następnie sprawdzamy, czy potencjał ten dzielnik jest rzeczywisty dzielnik próbując dopasować resztę napisu z powtórzeniami nim(?=\1+$)
. Dzielnik ten jest po prostu usuwany z łańcucha, w ten sposób odejmujesz coś unarowo.Przetwarza liczby pierwsze, z wyjątkiem 3 i 19 . Negatywne spojrzenie wstecz zapewnia, że dane wejściowe nie są złożone, a nie 3, a nie 19 . Następnie dopasowujemy pojedynczy
1
i zastępujemy go całym ciągiem. Jest to jedna forma obliczania n - 1 + n , która oczywiście wynosi 2n-1 .Gdy trafimy 3 lub 19 , żaden etap nie może dopasować struny i nie będzie już zmieniany.
źródło
1$'
to samo co$_
?Łuska , 15 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka , 12 bajtów
Wypróbuj online!
Jak to działa
źródło
Wolfram Language (Mathematica) , 65
6668bajtyWypróbuj online!
Inspirowany wskazówką . Zasadniczo po prostu odtwarza algorytm.
//.
jestRepeatedReplace
i/;
jestCondition
. Tak więc kod zastąpii_
(pojedynczą ilość) znakiemIf[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]
, aż doi!=3&&!=19
ocenyTrue
.Reper:
źródło
10000000010
bomaximum number of iterations is 2^16 (= 65536)
#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
05AB1E ,
191817 bajtówWypróbuj online!
Wyjaśnienie
źródło
<ë
JavaScript (ES6),
737169 bajtówPrzypadki testowe
Pokaż fragment kodu
Sformatowane i skomentowane
źródło
57%n
in%38
zamiastn==3|n==19
. Zapisałem również 1 bajt w mojej odpowiedzi Java , więc dzięki!Galaretka ,
2319 bajtów-4 bajty z mil . Nadal jednak dłużej niż 05AB1E.
Wypróbuj online!
źródło
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿
używając zamiast tego pętli while i ponownie zamawiającPython 2 ,
110105103101 bajtów-2 bajty dzięki @Lynn
Wypróbuj online!
Python 2 ,
116112105 bajtówWypróbuj online!
źródło
…n*(n&~16==3)or…
oszczędza 2 bajty.MATL ,
2221 bajtówDzięki @Giuseppe za usunięcie 1 bajtu!
Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
źródło
Haskell - 154 bajty
Prawdopodobnie brakuje tutaj kilku sztuczek golfowych, to moja pierwsza próba golfa haskell.
źródło
1>0
przezTrue
większość czasu, ale często lepiej jest na przykład użyć przypisaniac<-z n
.[x|x<-[b-1,b-2..1],rem b x==0]
jest także krótki niżreverse[x|x<-[1..(b-1)],b
remx==0]
.Neim ,
1716 bajtówWyjaśnienie:
Wypróbuj online!
źródło
Liczby R + ,
10299 bajtówWypróbuj online!
R nie jest znany z krótkich wbudowań, a nawet pakiety podążają za nimi!
źródło
Java 8,
14013513494 bajtów-5 bajtów konwertujących rekurencyjną metodę Java 7 na Java 8 lambda z pętlą.
-1 bajt niejawny dzięki odpowiedzi JavaScript @Arnauld poprzez zmianę
n!=3&n!=19
orazreturn n;
na57%n>0
ireturn n%38;
.Myślę, że powinno być możliwe połączenie w jakiś sposób dwóch pętli i sprawdzenie, czyn
jest liczbą pierwszą, i uzyskanie jej największej liczby w tym samym czasie, ale nie mogę tego rozgryźć (jeszcze). Na razie będzie to początkowa wersja.-40 dużych bajtów dzięki @Nevay, robiąc to, czego nie mogłem zrobić: łącząc pętle, aby sprawdzić liczby pierwsze i największy czynnik pierwszy na raz.
Wyjaśnienie:
Wypróbuj tutaj (działa nawet
999999
w mniej niż 1 sekundę).źródło
n=>
zamiastn->
. A czasem połączenia małe / wielkie litery. ;)n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Bash, 73 bajty
Wypróbuj online! Zmodyfikowano nieznacznie, aby działał na TIO.
Rekurencyjnie wywołuje własny plik skryptu
$0
,który nie działa w TIO, ponieważ musi być uruchomiony jako. Akceptuje dane wejściowe jako argument wiersza polecenia../filename.sh
Używa tej samej sztuczki modułowej, co odpowiedź JS @ Arnauld .
Przypadki testowe
źródło
Python 3 , 97 bajtów
Wypróbuj online!
źródło
Pyth , 19 bajtów
Sprawdź wszystkie przypadki testowe!
Odpowiedź Łuski zainspirowała mnie do zapisania 2 bajtów (
,3 19
doP57
).Jak to działa
źródło
PowerShell ,
150126 bajtówWypróbuj online! (ostrzeżenie: wolne dla większych liczb)
Metoda iteracyjna. Program PowerShell nie ma żadnych wbudowanych głównych faktoryzacji, więc pożycza kod z mojej odpowiedzi na temat znajomych Prime Factors .
Pierwsza jest nasza
for
pętla. Setup ustawia$n
się na wartość wejściową, a warunkowe utrzymuje pętlę tak długo, jak długo57%$n
jest niezerowa (dzięki Arnauldowi za tę sztuczkę). Wewnątrz pętli najpierw otrzymujemy listę głównych czynników$a
(ustawionych na$n
). To jest kod pożyczony od kumpli Prime Factors. Jeśli dane wejściowe$a
są już pierwotne, funkcja zwróci tylko$a
(ważne później). To (potencjalnie po prostu$a
) zostaje zapisane$d
.Dalej jest
if
/else
warunkowy. W przypadkuif
części sprawdzamy, czy$n
jest-in
$d
. Jeśli tak, to znaczy, że$n
jest liczbą pierwszą, więc bierzemy$n=2*$n-1
lub$n+=$n-1
. W przeciwnym razie jest złożony, więc musimy znaleźć największy czynnik pierwszy. Oznacza to, że musimy podjąć ostatnią[-1]
z$d
i odejmować, że od$n
z$n-=
. Działa to, ponieważ zapętlamy się od2
i dlatego ostatni element$d
będzie już największy.Po zakończeniu zapętlania po prostu umieszczamy
$n%38
(ponownie, dzięki Arnauld) w potoku, a dane wyjściowe są niejawne.źródło
APL (Dyalog Unicode) ,
1139059 bajtówWypróbuj online!
TIO działa z wartościami do ~ 3200. Przetestowano na moim komputerze dla ostatniego przypadku testowego. Aby przetestować na TIO, po prostu dodajNie ma już zastosowania, dzięki @ Adám za zwrócenie uwagi, że mój algorytm sprawdzania pierwotności był naprawdę zły i dostarczenie mi zamiennika; także dla 23-bajtowego zapisu.f value
na dole kodu.Edytowane, aby naprawić liczbę bajtów.
Jak to działa
źródło
Aksjomat, 93 bajty
test:
Byłaby funkcja 68 bajtów
ale dla n = 57991 (o ile dobrze pamiętam), to przestaje być zarezerwowane miejsce na stosie.
źródło
Python 2 , 93 bajty
Port z odpowiedzią TFeld jest bez bibliotekami zewnętrznymi.
Wypróbuj online!
źródło