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*2od 201; otrzymujemy 189. Czy można to podzielić przez 7? Aby to sprawdzić, zastosujmy ponownie regułę.

Odejmij 9*2od 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 njest 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).

Golfscript, 27 22 bajtów

{.9>{.10/\10%2*-f}*}:f

Możesz użyć tego w następujący sposób:

1000f

Wyjaśnienie

{.9>{.10/\10%2*-f}*}:f
{                  }:f    # Define block 'f' (similar to a function)
 .                        # Duplicate the first value of the stack
  9>{            }*       # If the value on top of the stack is greater than 9 then the block is executed
     .10/\10%2*-          # Same as nb/10 - (nb%10 * 2) with some stack manipulations '.' to duplicate the top of the stack and '\' to swap the the first and second element of the stack
                f         # Execute block 'f'

5 bajtów zapisanych dzięki Dennisowi!

Haskell, 35 bajtów

until(<71)(\n->div n 10-2*mod n 10)

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.

Galaretka, 11 bajtów

d⁵Uḅ-2µ>9$¿

Wypróbuj online!

Jak to działa

d⁵Uḅ-2µ>9$¿  Main link. Input: n

d⁵           Divmod; return [n : 10, n % 10].
  U          Upend; yield [n % 10, n : 10].
   ḅ-2       Convert from base -2 to integer, i.e., yield -2 × (n % 10) + (n : 10).

      µ      Push the previous chain as a link and begin a new, monadic chain.
          ¿  Apply the previous chain while...
       >9$     its return value is greater than 9.

Python 2, 38 bajtów

f=lambda x:f(x/10-x%10*2)if x>70else x

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.

Pyth, 13 bajtów

.W>H9-/ZTyeZQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Spowoduje to wydrukowanie wszystkich alternatywnych odpowiedzi.

Wyjaśnienie:

.W>H9-/ZTyeZQ   
            Q   read a number from input
.W              while
  >H9              the number is greater than 9
                do the following with the number:
      /ZT          divide it by 10
     -             and subtract
         yeZ       2*(number%10)

Julia, 27 26 bajtów

f(x)=x>9?f(x÷10-x%10*2):x

Jest 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 a BigInt, 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!

Pyth, 17 bajtów

L?<b70by-/bT*%bT2

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

L?<b70by-/bT*%bT2

L                  # Defines the lambda y with the parameter b
 ?<b70             # if b < 70:
      b            # return b, else:
       -/bT*%bT2   # calculate b/10 - b%10*2 and return it

CJam - 19 bajtów

Wersja do wykonania:

r~A*{`)]:~~Y*-_9>}g

Wypróbuj online lub W wersji nr 1:

r~{_9>}{`)]:~~Y*-}w

Wypróbuj online lub Podczas wersji 2:

r~{_9>}{_A/\A%Y*-}w

Wypróbuj online .

r~                     | Read and convert input
  A*                   | Multiply by 10 to get around "if" rule
     `                 | Stringify
      )                | Split last character off
       ]               | Convert stack to array
        :~             | Foreach in array convert to value
          ~            | Dump array
           Y*          | Multiply by 2
             -         | Subtract
              _        | Duplicate
               9>      | Greater than 9?
    {            }g    | do-while

Oracle SQL 11.2, 116 bajtów

WITH v(i)AS(SELECT:1 FROM DUAL UNION ALL SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70)SELECT MIN(i)FROM v;

Nie grał w golfa

WITH v(i) AS
(
  SELECT :1 FROM DUAL
  UNION ALL
  SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70
)
SELECT MIN(i) FROM v;

Haskell, 157 192 184 167 159 147 138 138 + 5 bajtów - 50% = 71,5 bajtów

O (1) space, O (n) time, single-pass!

h d=d%mod d 10
d%r=(quot(r-d)10,r)
p![d]=d-p*10
p![d,e]=d#(e-p)
p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
m#0=m
m#n=n-2*m
(0!)

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:

import Data.Char

{- sub a b = sub2 0 a b
  where
    sub2 borrow (a:as) (b:bs) = res : sub2 borrow2 as bs
      where
        (borrow2, res) = subDig borrow a b
    sub2 borrow (a:as) [] = sub2 borrow (a:as) (0:[])
    sub2 _ [] _ = [] -}

--subDig :: Int -> Int -> Int -> (Int, Int)
subDig borrow a b = subDig2 (a - b - borrow)
  where
    subDig2 d = subDig3 d (d `mod` 10)
    subDig3 d r = ((r-d) `quot` 10, r)

seven ds = seven2 0 ds
seven2 borrow (d:e:f:gs) = seven2 (b + borrow2) (res:f:gs)
  where
    (a, b) = double d
    (borrow2, res) = subDig borrow e a
seven2 borrow (d:e:[]) = finalApp d (e-borrow)
seven2 borrow (d:[]) = d - borrow*10

double d = ((2*d) `mod` 10, (2*d) `quot` 10)

finalApp m 0 = m
finalApp m n = n - 2*m

num2stream :: Int -> [Int]
num2stream = reverse . map digitToInt . show
sev = seven . num2stream

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: sevfunkcja w wersji bez golfa będzie działać na Integerkonwertowaniu do postaci strumienia odwróconego.

GNU dc, 20 15 bajtów

[10~2*-d70<F]sF

To 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:

36893488147419103232
lFxp
32

Mathematica, 47 44 bajtów

If[#>70,#0[{1,-2}.{⌊#/10⌋,#~Mod~10}],#]&

Proste podejście rekurencyjne. Prawdopodobnie mógłby być dalej golfem.

R, 43 bajty

x=scan();while(x>70)x=floor(x/10)-x%%10*2;x

Wyjaśnienie:

x=scan()                                      # Takes input as a double
        ;                                     # Next line
         while(x>70)                          # While-loop that runs as long x > 70
                      floor(x/10)             # Divide x by 10 and round that down
                                 -x%%10*2     # Substract twice the last integer
                    x=                        # Update x
                                         ;    # Next line once x <= 70
                                          x   # Print x

Przykładowe przebiegi:

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 9999
2: 
Read 1 item
[1] -3

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 32767
2: 
Read 1 item
[1] 28

JavaScript ES6, 38 bajtów

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i

Zawieszenia 36893488147419103232i używanie ~~(1/10)również się nie powiedzie700168844221

Test:

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i
O.textContent = O.textContent.replace(/(-?\d+) +(-?\d+)/g, (_,i,o) =>
  _+": "+(a(+i)==o?"OK":"Fail")
);

<pre id=O>1                       1
10                      10
100                     10
13                      13
42                      42
2016                    0
9                       9
99                      -9
9999                    -3
12345                   3
700168844221            70
36893488147419103232    32</pre>

Mathematica, 33 bajty

#//.a_/;a>70:>⌊a/10⌋-2a~Mod~10&

Przypadek testowy

%[9999]
(* -3 *)

Perl 5, 47 46 bajtów

Musiałem użyć bigintdo ostatniego przypadku testowego. (Zwraca 20 bez)

use bigint;$_=<>;while($_>9){$_-=2*chop;}print

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!

ES6, 108 bajtów

f=(s,n=0)=>s>1e9?f(s.slice(0,-1),((1+s.slice(-1)-n%10)%10*21+n-s.slice(-1))/10):s>9?f(((s-=n)-s%10*21)/10):s

Działa dla 2²⁵⁷ i 1000000000000000000001, ale przydałby się dalszy golf.

JavaScript ES6, 140 142 bajtów

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s

Jest 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 0s i wywołuje się rekurencyjnie, dopóki jej wartość liczbowa nie będzie mniejsza lub równa 9.

• Grał w golfa 7 bajtów dzięki @Neil (tak, wiem, że zyskałem 2 bajty, ale naprawiłem kilka błędów, które powodowały zawieszanie się funkcji lub zwracanie błędnych danych wyjściowych w niektórych przypadkach).

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s;[['1',1],['10',1],['100',1],['13',-5],['42',0],['2016',0],['9',9],['99',-9],['9999',-3],['12345',3],['700168844221',7],['36893488147419103232',-1],['231584178474632390847141970017375815706539969331281128078915168015826259279872',8]].map(a=>document.write(`<pre>${f(a[0])==a[1]?'PASS':'FAIL'} ${a[0]}=>${a[1]}</pre>`))

C #, 111 104 bajtów

int d(int n){var s=""+n;return n<71?n:d(int.Parse(s.Remove(s.Length-1))-int.Parse(""+s[s.Length-1])*2);}

Brain-Flak , 368 360 bajtów

Wypró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:

([(({})<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})

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).

n;f(char*c){for(n=0;*c;)n-=n>6?7:'0'-n-n-*c++;return n;}

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:

1. Odejmij 7, jeśli to konieczne, i ponownie, jeśli to konieczne
2. Pomnóż bieżącą sumę przez trzy i dodaj następną cyfrę

Krok „pomnóż przez trzy” jest zapisywany jako n-=-n-nzapisanie 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 *cze *c||n>6w forwarunku pętli.

Kwalifikuje się do ulepszonego bonusu, ponieważ to

• obsługuje liczby całkowite o dowolnej dokładności
• wykonuje tylko jeden przebieg na wejściu, w kolejności od lewej do prawej
• ma złożoność przestrzenną O (1)
• ma złożoność czasową O (n).

Program testowy i wyniki

#include <stdio.h>
int main(int argc, char **argv) {
    while (*++argv)
        printf("%s -> %d\n", *argv, f(*argv));
    return 0;
}

540 -> 15
541 -> 16
542 -> 17
543 -> 18
544 -> 19
545 -> 20
546 -> 21
547 -> 22
548 -> 23
549 -> 24
550 -> 18
99 -> 15
999 -> 12
12345 -> 11
32767 -> 7
700168844221 -> 7
36893488147419103232 -> 11
231584178474632390847141970017375815706539969331281128078915168015826259279872 -> 11

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):

f(c,n)char*c;{return n>6?f(c,n-7):*c?f(c+1,n+n+n+*c-'0'):n;}

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.

PHP, 50 bajtów

for($n=$argv[1];$n>9;)$n=$n/10|0-2*($n%10);echo$n;

wykorzystuje alternatywne wyjście; działa doPHP_INT_MAX

wersja łańcuchowa, działa na dowolną (dodatnią) liczbę (64 bajty):

for($n=$argv[1];$n>9;)$n=substr($n,0,-1)-2*substr($n,-1);echo$n;

Java, 133 bajty

int d(int n){String s=""+n;return n<71?n:d(Integer.parseInt(s.replaceFirst(".$",""))-Integer.parseInt(""+s.charAt(s.length()-1))*2);}

Nienawidzę, jak gadatliwy Integer.parseIntjest. Nie golfowany:

static int div(int n) {
    if (n <= 70) {
        return n;
    } else {
        String num = ("" + n);
        int last = Integer.parseInt("" + num.charAt(num.length() - 1));
        int k = Integer.parseInt(num.replaceFirst(".$", "")) - last * 2;
        return div(k);
    }
}