Terapkan aturan pembagian-per-7

25

Untuk memeriksa apakah angka desimal dapat habis dibagi 7:

Hapus digit terakhir. Lipat gandakan dengan 2 dan kurangi dari yang tersisa. Jika hasilnya habis dibagi 7, angka aslinya bisa habis dibagi 7.

(juga dijelaskan misalnya di sini )

Aturan ini baik untuk pemeriksaan keterbagian manual. Sebagai contoh:

Apakah 2016 dapat dibagi 7?

Kurangi 6*2dari 201; kita dapatkan 189. Apakah ini dapat dibagi oleh 7? Untuk memeriksanya, mari kita terapkan aturan itu lagi.

Kurangi 9*2dari 18; kami mendapatkan 0. Oleh karena itu, 2016 dapat dibagi dengan 7.

Dalam tantangan ini, Anda harus menerapkan aturan ini hingga status pembagiannya jelas , yaitu jumlahnya tidak lebih dari 70 (namun, lihat di bawah untuk detailnya). Buat fungsi atau program lengkap.

Input : bilangan bulat positif; kode Anda harus mendukung input hingga 32767 (mendukung bilangan bulat presisi-sewenang-wenang adalah bonus; lihat di bawah).

Keluaran : bilangan bulat (mungkin negatif), tidak lebih besar dari 70, yang merupakan hasil penerapan aturan pembagian-per-7 nol atau lebih banyak kali.

Kasus uji:

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

Di mana dua output yang mungkin ditentukan, salah satu hasilnya benar: yang kedua sesuai untuk menerapkan aturan sekali lagi. Dilarang menerapkan aturan pada angka satu digit: jika Anda menghapus digit, tidak ada (bukan 0) yang tersisa.


Bonus : Jika algoritma Anda

di mana njumlah angka desimal:

Kurangi 50% dari jumlah byte kode Anda.

Bonus nyata :

Selain itu, jika algoritma Anda membaca input ke arah normal, mulai dari digit paling signifikan, kurangi 50% sekali lagi - skor Anda adalah 25% dari jumlah byte Anda (sepertinya mungkin, tapi saya tidak terlalu yakin).

anatolyg
sumber
1
@DenkerAffe Mengembalikan input apa adanya dapat diterima. Saya memperbarui test case input = 10 untuk mencerminkan ini; itulah ide dari awal.
anatolyg
4
Saya tidak ingin menggunakan aturan itu 1000000000000000000001.
Neil
1
Tetapi bagaimana jika bahasa Anda memiliki long longs atau beberapa jenis yang setara bawaan?
SuperJedi224
1
Apa yang saya katakan adalah bahwa, dalam beberapa implementasi, itu adalah integer 128-bit, yang lebih dari cukup besar untuk kasus uji terakhir.
SuperJedi224
7
-1. Tidak semua bahasa mendukung ketepatan sewenang-wenang.
Maret

Jawaban:

23

Golfscript, 27 22 byte

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

Anda bisa menggunakannya dengan cara ini:

1000f

Penjelasan

{.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 byte disimpan berkat Dennis!

Dica
sumber
1
Selamat datang di Programming Puzzles and Code Golf. Ini adalah jawaban yang bagus, namun Anda dapat memperbaikinya dengan menambahkan uraian kode dan penjelasan, seperti pertanyaan di atas. Untuk membalas komentar ini, ketikkan @wizzwizz4( @lalu nama pengguna saya) di awal (atau di mana saja di) komentar.
wizzwizz4
1
@ wizzwizz4 Lebih baik? Saya tidak yakin bahwa saya mengerti apa yang Anda maksud dengan 'code breakdown' (bukan penutur asli maaf)
Dica
8
Saya percaya dengan "kerusakan kode" maksudnya adalah penjelasan, yang telah Anda tambahkan. Ini memang jawaban pertama yang sangat bagus. Selamat datang di situs ini!
Alex A.
1
Anda dapat menulis ulang {...}{}ifbagian sebagai {...}*, yang hanya akan menerapkan nol blok kode satu kali, tergantung pada nilai yang didorong oleh >. Selain itu, kami diizinkan untuk melakukan satu iterasi lagi (jadi ganti 70dengan 9menghemat satu byte), dan saya rasa Anda tidak perlu menghapus blokirnya ;.
Dennis
3
@Dica, ini adalah jawaban pertama yang cukup baik untuk mendapatkan 12+ upvotes pada pertanyaan dengan hanya 624 tampilan, dan untuk mendapatkan pujian dari dua moderator. Jika Anda terus begini, Anda akan segera menyusul Dennis!
wizzwizz4
13

Haskell, 35 byte

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

Contoh penggunaan: until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232-> 32.

Tidak banyak yang bisa dijelaskan, ini adalah implementasi langsung dari algoritma.

nimi
sumber
9

Jelly, 11 byte

d⁵Uḅ-2µ>9$¿

Cobalah online!

Bagaimana itu bekerja

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.
Dennis
sumber
Dan seperti biasa, Jelly menang. Dennis, berapa banyak byte yang diperlukan untuk mengimplementasikan juru bahasa jelly di Jelly?
Bálint
6

Python 2, 38 byte

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

Coba di sini !

Pendekatan rekursif sederhana. Mencetak x jika <70 jika tidak menerapkan aturan pembagian dan menyebut dirinya dengan hasilnya.

Denker
sumber
Anda tidak perlu ruang setelah)
Maltysen
@Maltysen Benar. Salin menempel yang salah, terima kasih atas petunjuknya!
Denker
2
Jika terlalu bertele-tele. f=lambda x:x*(x<70)or f(x/10-x%10*2)
seequ
1
@Seeq Trik yang bagus, terima kasih! Ini seharusnya bekerja secara teori, tetapi mencapai kedalaman rekursi maksimum dengan 2016 sebagai input sedangkan versi saya tidak. Ada yang tahu kenapa?
Denker
Ah, benar, tidak mempertimbangkan itu. Trik ini dianggap x*(x<70) != 0sebagai kondisi akhir. Jika x mencapai 0 - seperti halnya pada 2016 - kondisi akhir tidak pernah terjadi.
seequ
6

Pyth, 13 byte

.W>H9-/ZTyeZQ

Cobalah online: Demonstrasi atau Test Suite

Ini akan mencetak semua jawaban alternatif.

Penjelasan:

.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)
Jakube
sumber
5

Julia, 27 26 byte

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

Ini adalah fungsi rekursif yang menerima bilangan bulat dan mengembalikan a BigInt. Jika inputnya besar seperti pada contoh terakhir, Julia mem-parsingnya sebagai BigInt, jadi tidak perlu konversi manual.

Pendekatan ini hanyalah implementasi langsung dari algoritma. Ini akan menghasilkan output alternatif. Mengambil modulus ketika membaginya dengan 10 menghasilkan digit terakhir dan hasil bagi dari pembagian bilangan bulat dengan 10 menghasilkan segalanya kecuali digit terakhir.

Menyimpan satu byte berkat Dennis!

Alex A.
sumber
Kami diizinkan untuk melakukan satu iterasi lagi, jadi ganti 70dengan 9menyimpan satu byte.
Dennis
@Dennis Panggilan bagus, terima kasih!
Alex A.
4

Pyth, 17 byte

L?<b70by-/bT*%bT2

Coba di sini!

Pendekatan rekursif yang sama seperti pada jawaban python saya . Mendefinisikan sebuah lambda yyang disebut seperti ini: y12345.
Penghitung byte dalam juru bahasa online menunjukkan 19 byte karena saya menambahkan panggilan lambda ke sana, jadi Anda bisa mencobanya dengan menekan tombol run.

Penjelasan

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
Denker
sumber
Anda memiliki kesalahan ketik dalam penjelasan Anda, 17 harus 70: P
FryAmTheEggman
4

CJam - 19 byte

Versi do-while:

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

Cobalah online atau Sementara versi # 1:

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

Cobalah online atau Sementara versi # 2:

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

Cobalah 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
CJ Dennis
sumber
3

Oracle SQL 11.2, 116 byte

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;

Tidak bermain golf

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;
Jeto
sumber
3

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

O (1) ruang, O (n) waktu, sekali jalan!

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

Gunakan sebagai 0![6,1,0,2]untuk menerapkan aturan ke 2016, yaitu memberikan nomor dalam bentuk aliran dengan angka paling signifikan terlebih dahulu. Dengan cara ini, ia akan melewati angka digit demi digit, menerapkan aturan dengan kompleksitas ruang O (1).

Kode ungolfed ada di sini:

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

Inti dari cara kerjanya adalah menerapkan algoritme pengurangan digit-per-digit , tetapi memanfaatkan fakta bahwa setiap angka yang akan dikurangkan paling banyak adalah 2-digit, sehingga kita dapat mengurangi jumlah arbitrer dari 1- atau -2 angka angka dari yang utama (serta memakan angka paling signifikan).

Algoritma pengurangan adalah O (1) dan hanya menyimpan nilai 'pinjaman' saat ini. Saya mengubah ini untuk menambahkan digit tambahan (0 atau 1), dan kami perhatikan bahwa nilai pinjaman ini dibatasi (dalam kisaran [-2,2] sehingga kami hanya perlu 3 bit untuk menyimpan ini).

Nilai-nilai lain yang disimpan dalam memori adalah variabel sementara yang mewakili jumlah 2 digit saat ini untuk ditambahkan, satu pandangan ke depan dalam aliran, dan untuk menerapkan satu langkah dari algoritma pengurangan (yaitu dibutuhkan dua digit dan nilai pinjaman, dan pengembalian satu digit dan nilai pinjaman baru).

Akhirnya pada akhirnya memproses dua digit terakhir dalam aliran sekaligus untuk mengembalikan angka satu digit daripada daftar digit.

NB sevFungsi dalam versi yang tidak diklik akan bekerja pada Integer, mengubahnya menjadi bentuk aliran terbalik.

nitrogen
sumber
Saya bermaksud bonus untuk urutan angka normal. Tapi saya tidak pernah mengatakannya, jadi adil untuk mendapatkan bonus untuk pesanan terbalik, meskipun itu kurang menyenangkan. Ngomong-ngomong, bahkan urutan yang terbalik lebih sulit daripada yang saya duga, jadi cukup menyenangkan!
anatolyg
@anatolyg: Terima kasih! Saya tidak yakin apakah mungkin untuk melakukan satu operan tunggal O (1) penerapan tatanan normal ... aturannya tergantung pada angka paling tidak signifikan, jadi dalam teori penerapan langsung dari aturan tersebut tidak mungkin kecuali dalam urutan terbalik. Satu-satunya hal lain yang dapat saya pikirkan adalah dengan menemukan bentuk yang setara secara matematis - misalnya Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]bekerja secara empiris untuk n antara 10 dan 99, tetapi semakin rumit semakin banyak digit yang dimiliki ...
nitrous
Hmm saya memikirkannya dan sepertinya mungkin ada cara dengan menjaga 2 digit depan dan menerapkan setiap digit berikutnya, tetapi mengalikannya dengan (-2) ^ n untuk memperhitungkannya 'menyaring melalui' ... sejauh yang saya bisa tahu meskipun tidak ada cara untuk membuat ini bekerja tanpa menyimpan semua digit dalam memori dan mengorbankan O (1) 'ness atau bahkan o (n)' ness ... Saya pikir urutan normal jelas tidak mungkin :(
nitrous
1
Saya khawatir Anda harus menghitung byte awal 0ketika memanggil !, juga, misalnya sebagai bagian (0!)(+ baris baru), yaitu +5 byte. Di sisi lain, Anda dapat mempersingkat yang pertama untuk mencocokkan pola !ke p![d]=dan p![d,e]=. Juga, penggunaan pola penjaga bukan let: p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f).
nimi
1
@nitrous: Oh saya ment (0!)pada baris itu sendiri. (0!)adalah fungsi yang Anda berikan sebagai jawaban Anda. The 0diperlukan, tetapi tidak ada hubungannya dengan input, sehingga Anda tidak bisa outsource ke pemanggil. Tentu saja Anda juga bisa menggunakan f x=0!x, tetapi ini lebih lama.
nimi
3

GNU dc, 20 15 byte

[10~2*-d70<F]sF

Ini mendefinisikan fungsi dc pertama saya F,. Dibutuhkan input di atas tumpukan, dan meninggalkan hasilnya di atas tumpukan. Contoh penggunaan:

36893488147419103232
lFxp
32
Toby Speight
sumber
2

Mathematica, 47 44 byte

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

Pendekatan rekursif sederhana. Mungkin bisa bermain golf lebih lanjut.

LegionMammal978
sumber
#0[{1,-2}.QuotientRemainder[#,10]]menghemat satu byte.
njpipeorgan
2

R, 43 byte

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

Penjelasan:

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

Sampel berjalan:

> 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
Laterow
sumber
1

JavaScript ES6, 38 byte

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

Gagal 36893488147419103232menggunakan dan menggunakan ~~(1/10)juga akan gagal untuk700168844221

Uji:

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>

andlrc
sumber
Saya mendapat dua Fail... 70 dan 32
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ya saya, saya masih bertanya-tanya mengapa ...
andlrc
Karena tipe angka JavaScript tidak menangani kasus terakhir, setidaknya.
Conor O'Brien
1
f=n=>n>70?f((n-n%10*21)/10):nadalah versi yang lebih pendek tetapi masih hanya berfungsi hingga 2**56.
Neil
@Neil lihat jawaban saya untuk presisi yang sewenang-wenang, dan jangan ragu untuk bermain golf, sangat dihargai.
Patrick Roberts
1

Mathematica, 33 byte

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

Kasus cobaan

%[9999]
(* -3 *)
njpipeorgan
sumber
1

Perl 5, 47 46 byte

Harus digunakan bigintuntuk test case terakhir. (Mengembalikan 20 tanpa)

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

Tidak begitu yakin itu adalah kandidat untuk bonus, jadi saya tidak memperhitungkannya. (Saya pikir itu benar, tapi saya tidak terlalu terbiasa dengan konsep-konsep itu)

Coba di sini!

Paul Picard
sumber
1

ES6, 108 byte

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

Dapat digunakan untuk 2²⁵⁷ dan 100000000000000000000001, tetapi dapat menggunakan golf lebih lanjut.

Neil
sumber
@ PatrickRoberts Ups, awasi saat memformat ulang untuk pengiriman.
Neil
1

JavaScript ES6, 140 142 byte

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

Ini benar-benar matematika presisi arbitrer, bahkan bekerja pada kasus uji terbesar.

Fungsi ini secara rekursif menghilangkan digit terakhir dari string, kemudian mengurangi 2 * digit terakhir dari string numerik yang tersisa dengan secara iteratif menambah jumlah digit untuk diterapkan pada minuend hingga perbedaannya positif. Kemudian menambahkan perbedaan itu ke ujung string dengan 0s yang tepat dan menyebut dirinya secara rekursif sampai nilai numeriknya kurang dari atau sama dengan 9.

  • Golfed 7 byte berkat @Neil (ya saya tahu saya memperoleh 2 byte tapi saya memperbaiki beberapa bug yang menyebabkan fungsi membeku atau mengembalikan output yang salah untuk beberapa kasus).

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

Patrick Roberts
sumber
Bagus, tapi mungkin tidak berhasil 1000000000000000000001.
Neil
1
Coba s.replace(/.$/,'-$&*2'). Saya tidak punya ide yang jelas untuk sisanya meskipun maaf.
Neil
1

C #, 111 104 byte

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);}
TheLethalCoder
sumber
1

Brain-Flak , 368 360 byte

Cobalah secara Online!

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

Penjelasan

Untuk memulai, semua kode berada dalam satu lingkaran yang berjalan hingga bagian atas tumpukan kurang dari nol:

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

Di dalam loop kami menjalankan yang dibagi dengan tujuh algoritma:

Gandakan bagian atas tumpukan

(({}))

Ambil mod 10 dari atas tumpukan (digit terakhir)

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

Ini agak berantakan tapi itu sisa dari algoritma saya mungkin akan menjelaskannya nanti, tetapi saya tidak sepenuhnya ingat cara kerjanya:

([(({})<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})
Wisaya Gandum
sumber
1

C, 56 byte - 75% = 14

Meskipun ini tidak memberikan angka yang sama persis dengan kasus uji, itu memuaskan semangat pertanyaan (dan bisa dibilang lebih). Ini dengan benar mengidentifikasi kelipatan tepat 7, dan memberikan sisa yang tepat untuk nomor lain (karena tidak pernah menggunakan angka negatif).

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

Tidak ada perkalian atau pembagian dalam algoritme, hanya penjumlahan dan pengurangan, dan digit diproses dalam satu pass tunggal dari kiri ke kanan. Ini berfungsi sebagai berikut, dimulai dengan 0 di akumulator:

  1. Kurangi 7 jika perlu, dan lagi jika masih perlu
  2. Lipat gandakan total berjalan dengan tiga, dan tambahkan digit berikutnya

Langkah "gandakan dengan tiga" ditulis n-=-n-nuntuk menghemat byte dan untuk menghindari operator gandakan.

Ketika kita mencapai akhir, kita tidak mengurangi tujuh, sehingga hasilnya akan berada dalam kisaran 0-24; jika Anda menginginkan modulus ketat (0-7), gantikan *cdengan *c||n>6dalam forkondisi loop.

Itu memenuhi syarat untuk bonus yang ditingkatkan, karena itu

  • mendukung integer presisi sewenang-wenang
  • hanya melakukan satu operan pada input, dalam urutan kiri-ke-kanan
  • memiliki kompleksitas ruang O (1)
  • memiliki kompleksitas waktu O (n).

Program uji dan hasil

#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

Versi alternatif

Inilah salah satu yang berulang (Anda ingin mengaktifkan optimisasi kompiler untuk melakukan transformasi tail-call atau Anda dapat meluap stack Anda; Saya menggunakan 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;}

Sebut saja dengan '0' sebagai argumen kedua.

Kedua versi menghitung sisa-modulo-tujuh dari angka 60.000 digit dalam waktu kurang dari 50 milidetik pada mesin saya.

Toby Speight
sumber
Terima kasih atas bonusnya - itu membuat perubahan nyata bagi C untuk menjadi sangat kompetitif! Saat ini hanya dikalahkan oleh Jelly (11) dan Pyth (13). :-)
Toby Speight
1

PHP, 50 byte

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

menggunakan output alternatif; bekerja hinggaPHP_INT_MAX


versi string, berfungsi untuk semua angka (positif) (64 byte):

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

Java, 133 byte

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

Aku benci bagaimana verbose Integer.parseIntitu. Tidak Disatukan:

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);
    }
}
Justin
sumber