Aby sprawdzić, czy liczba dziesiętna jest podzielna przez 7:
Usuń ostatnią cyfrę. Pomnóż to przez 2 i odejmij od tego, co zostało. Jeśli wynik jest podzielny przez 7, pierwotna liczba jest podzielna przez 7.
(opisane również np. tutaj )
Ta zasada jest przydatna przy ręcznym sprawdzaniu podzielności. Na przykład:
Czy 2016 można podzielić przez 7?
Odejmij
6*2
od 201; otrzymujemy 189. Czy można to podzielić przez 7? Aby to sprawdzić, zastosujmy ponownie regułę.Odejmij
9*2
od 18; otrzymujemy 0. Dlatego 2016 można podzielić przez 7.
W tym wyzwaniu powinieneś stosować tę regułę, dopóki status podzielności nie będzie oczywisty , to znaczy liczba nie będzie większa niż 70 (patrz szczegóły poniżej). Utwórz funkcję lub pełny program.
Dane wejściowe : dodatnia liczba całkowita; twój kod powinien obsługiwać dane wejściowe do 32767 (obsługa liczb całkowitych o dowolnej dokładności jest zaletą; patrz poniżej).
Wyjście : liczba całkowita (prawdopodobnie ujemna), nie większa niż 70, która jest wynikiem zastosowania reguły podzielności przez 7 zero lub więcej razy.
Przypadki testowe:
Input Output Alternative output
1 1
10 10 1
100 10 1
13 13 -5
42 42 0
2016 0
9 9
99 -9
9999 -3
12345 3
32767 28 -14
---------- Values below are only relevant for the bonus
700168844221 70 7
36893488147419103232 32 -1
231584178474632390847141970017375815706539969331281128078915168015826259279872 8
W przypadku określenia dwóch możliwych wyników, każdy wynik jest poprawny: drugi odpowiada zastosowaniu reguły jeszcze raz. Zabronione jest stosowanie reguły do liczby jednocyfrowej: jeśli usuniesz cyfrę, nie pozostanie nic (nie 0).
Bonus : Jeśli twój algorytm
- Obsługuje liczby całkowite o dowolnej dokładności
- Wykonuje tylko jeden przebieg na wejściu
- Ma złożoność przestrzeni
o(n)
(tj. Mniej niżO(n)
); i - Ma złożoność czasu
O(n)
,
gdzie n
jest liczba cyfr dziesiętnych:
Odejmij 50% liczby bajtów kodu.
Prawdziwy bonus :
Ponadto, jeśli twój algorytm odczytuje dane wejściowe w normalnym kierunku, zaczynając od najbardziej znaczącej cyfry, odejmij 50% jeszcze raz - twój wynik to 25% liczby bajtów (wydaje się to możliwe, ale nie jestem absolutnie pewien).
źródło
1000000000000000000001
.long long
wbudowany s lub inny równoważny typ?Odpowiedzi:
Golfscript,
2722 bajtówMożesz użyć tego w następujący sposób:
Wyjaśnienie
5 bajtów zapisanych dzięki Dennisowi!
źródło
@wizzwizz4
(@
następnie moją nazwę użytkownika) na początku komentarza (lub w dowolnym innym miejscu).{...}{}if
część jako{...}*
, która po prostu zastosuje blok kodu zero jeden raz, w zależności od wartości wypchniętej przez>
. Ponadto, mamy prawo wykonywać jedna iteracja (tak zastępując70
ze9
zapisuje bajt) i nie sądzę, trzeba pop z bloku;
.Haskell, 35 bajtów
Przykład użycia:
until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232
->32
.Nic wielkiego do wyjaśnienia, to bezpośrednia implementacja algorytmu.
źródło
Galaretka, 11 bajtów
Wypróbuj online!
Jak to działa
źródło
Python 2, 38 bajtów
Wypróbuj tutaj !
Proste podejście rekurencyjne. Drukuje x, jeśli jego <70 w przeciwnym razie stosuje zasadę podzielności i wywołuje się z wynikiem.
źródło
)
f=lambda x:x*(x<70)or f(x/10-x%10*2)
x*(x<70) != 0
za warunek końcowy. Jeśli x osiągnie wartość 0 - podobnie jak w 2016 r. - warunek końcowy nigdy nie nastąpi.Pyth, 13 bajtów
Wypróbuj online: pakiet demonstracyjny lub testowy
Spowoduje to wydrukowanie wszystkich alternatywnych odpowiedzi.
Wyjaśnienie:
źródło
Julia,
2726 bajtówJest to funkcja rekurencyjna, która przyjmuje liczbę całkowitą i zwraca a
BigInt
. Jeśli dane wejściowe są duże, jak w poprzednim przykładzie, Julia analizuje je jako aBigInt
, więc konwersja ręczna nie jest konieczna.Podejście to jest po prostu implementacją algorytmu. Będzie produkować alternatywne wyjścia. Biorąc moduł przy dzieleniu przez 10, otrzymujemy ostatnią cyfrę, a iloraz z dzielenia liczb całkowitych przez 10 daje wszystko oprócz ostatniej cyfry.
Oszczędność bajtu dzięki Dennisowi!
źródło
70
ze9
zapisuje bajt.Pyth, 17 bajtów
Wypróbuj tutaj!
To samo rekurencyjne podejście jak w mojej odpowiedzi w python . Definiuje lambda
y
, które nazywa się tak:y12345
.Licznik bajtów w tłumaczeniu online pokazuje 19 bajtów, ponieważ dodałem do niego wywołanie lambda, więc możesz po prostu spróbować, naciskając przycisk Run.
Wyjaśnienie
źródło
CJam - 19 bajtów
Wersja do wykonania:
Wypróbuj online lub W wersji nr 1:
Wypróbuj online lub Podczas wersji 2:
Wypróbuj online .
źródło
Oracle SQL 11.2, 116 bajtów
Nie grał w golfa
źródło
Haskell,
157192184167159147138 138 + 5 bajtów - 50% = 71,5 bajtówO (1) space, O (n) time, single-pass!
Użyj,
0![6,1,0,2]
aby zastosować regułę do 2016 r., Tzn. Przekaż jej liczbę w formie strumienia, zaczynając od najmniej znaczącej liczby. W ten sposób przejdzie przez cyfrę po cyfrze, stosując regułę o złożoności przestrzeni O (1).Niegolfowany kod jest tutaj:
Istotą tego, jak to działa, jest to, że implementuje on algorytm odejmowania cyfra po cyfrze , ale wykorzystuje fakt, że każda liczba, która ma być odejmowana, to co najwyżej 2 cyfry, dzięki czemu możemy odjąć dowolną ich liczbę 1- lub dwucyfrowe liczby od głównej (a także do jedzenia najmniej znaczących cyfr).
Algorytm odejmowania to O (1) i zapisuje tylko bieżącą wartość „pożycz”. Zmieniłem to, aby dodać dodatkową cyfrę (0 lub 1), i zauważamy, że ta wartość pożyczki jest ograniczona (w zakresie [-2,2], więc do przechowywania tego potrzebujemy tylko 3 bity).
Pozostałe wartości przechowywane w pamięci to zmienne tymczasowe reprezentujące bieżącą 2-cyfrową liczbę do dodania, jedno spojrzenie w przyszłość w strumieniu i zastosowanie jednego kroku algorytmu odejmowania (tj. Wymaga dwóch cyfr i wartości pożyczonej i zwraca wartość jedna cyfra i nowa wartość pożyczki).
Na koniec na koniec przetwarza jednocześnie dwie ostatnie cyfry w strumieniu, aby zwrócić liczbę jednocyfrową zamiast listy cyfr.
Uwaga:
sev
funkcja w wersji bez golfa będzie działać naInteger
konwertowaniu do postaci strumienia odwróconego.źródło
Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]
działa empirycznie dla n od 10 do 99, ale staje się bardziej skomplikowane, im więcej cyfr ma ...0
podczas wywoływania!
, np. Jako sekcja(0!)
(+ nowa linia), tj. +5 bajtów. Z drugiej strony możesz skrócić pierwszy do wzorca dopasowania!
dop![d]=
ip![d,e]=
. Ponadto, stosowanie wzorca strzeże zamiastlet
:p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
.(0!)
na myśli własną linię.(0!)
to funkcja, którą podajesz jako odpowiedź. Jest0
to wymagane, ale nie ma nic wspólnego z danymi wejściowymi, więc nie możesz zlecić go dzwoniącemu. Oczywiście możesz również użyćf x=0!x
, ale jest to dłuższe.GNU dc,
2015 bajtówTo określa moje pierwsze (w ogóle) funkcję DC
F
. Pobiera dane wejściowe na szczycie stosu i pozostawia jego wynik na szczycie stosu. Przykładowe użycie:źródło
Mathematica,
4744 bajtówProste podejście rekurencyjne. Prawdopodobnie mógłby być dalej golfem.
źródło
#0[{1,-2}.QuotientRemainder[#,10]]
zapisuje bajt.R, 43 bajty
Wyjaśnienie:
Przykładowe przebiegi:
źródło
JavaScript ES6, 38 bajtówZawieszenia
36893488147419103232
i używanie~~(1/10)
również się nie powiedzie700168844221
Test:
źródło
Fail
s ... 70 i 32f=n=>n>70?f((n-n%10*21)/10):n
jest krótszą wersją, ale nadal działa tylko dla maksymalnie2**56
.Mathematica, 33 bajty
Przypadek testowy
źródło
Perl 5,
4746 bajtówMusiałem użyć
bigint
do ostatniego przypadku testowego. (Zwraca 20 bez)Nie jestem pewien, czy jest to kandydat na premię, więc nie wziąłem tego pod uwagę. (Myślę, że tak, ale tak naprawdę nie jestem przyzwyczajony do koncepcji)
Wypróbuj tutaj!
źródło
ES6, 108 bajtów
Działa dla 2²⁵⁷ i 1000000000000000000001, ale przydałby się dalszy golf.
źródło
JavaScript ES6,
140142 bajtówJest to prawdziwa matematyka o dowolnej precyzji, działa nawet na największym przypadku testowym.
Ta funkcja rekurencyjnie usuwa ostatnią cyfrę z łańcucha, a następnie odejmuje 2 * ostatnią cyfrę od pozostałego łańcucha numerycznego, iteracyjnie zwiększając liczbę cyfr, które mają zostać zastosowane do minuend, aż różnica będzie dodatnia. Następnie dołącza tę różnicę do końca łańcucha za pomocą odpowiednio wypełnionych znaków
0
s i wywołuje się rekurencyjnie, dopóki jej wartość liczbowa nie będzie mniejsza lub równa9
.źródło
1000000000000000000001
.s.replace(/.$/,'-$&*2')
. Niestety nie mam żadnych oczywistych pomysłów na resztę.C #,
111104 bajtówźródło
Brain-Flak ,
368360 bajtówWypróbuj online!
Wyjaśnienie
Aby rozpocząć, cały kod znajduje się w pętli, która działa, dopóki górna część stosu nie będzie mniejsza niż zero:
Wewnątrz pętli uruchamiamy podzielny przez siedem algorytm:
Zduplikuj górę stosu
Weź mod 10 na górze stosu (ostatnia cyfra)
To trochę bałagan, ale robi resztę algorytmu, który mógłbym wyjaśnić później, ale nie pamiętam, jak to działa:
źródło
C, 56 bajtów - 75% = 14
Chociaż nie podaje to dokładnie takich samych liczb jak przypadki testowe, spełnia on ducha pytania (i prawdopodobnie więcej). Poprawnie identyfikuje dokładne wielokrotności 7 i podaje dokładną resztę dla innych liczb (ponieważ nigdy nie używa liczb ujemnych).
W algorytmie nie ma mnożenia ani dzielenia, tylko dodawanie i odejmowanie, a cyfry są przetwarzane w jednym przejściu od lewej do prawej. Działa w następujący sposób, zaczynając od 0 w akumulatorze:
Krok „pomnóż przez trzy” jest zapisywany jako
n-=-n-n
zapisanie bajtu i uniknięcie operatora mnożenia.Kiedy osiągniemy koniec, nie odejmujemy siódemek, więc wynik będzie w zakresie 0-24; jeśli chcesz ścisłej moduł (0-7), zastępczego
*c
ze*c||n>6
wfor
warunku pętli.Kwalifikuje się do ulepszonego bonusu, ponieważ to
Program testowy i wyniki
Alternatywna wersja
Oto jedna z nich, która powtarza się (będziesz chciał włączyć optymalizacje kompilatora, aby wykonać transformację wywołania ogona lub możesz przepełnić swój stos; użyłem
gcc -std=c89 -O3
):Nazwij to z „0” jako drugim argumentem.
Obie wersje obliczają pozostałą liczbę siedmiu modułów z liczby 60 000 cyfr w czasie poniżej 50 milisekund na moim komputerze.
źródło
PHP, 50 bajtów
wykorzystuje alternatywne wyjście; działa do
PHP_INT_MAX
wersja łańcuchowa, działa na dowolną (dodatnią) liczbę (64 bajty):
źródło
Java, 133 bajty
Nienawidzę, jak gadatliwy
Integer.parseInt
jest. Nie golfowany:źródło