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*2
dari 201; kita dapatkan 189. Apakah ini dapat dibagi oleh 7? Untuk memeriksanya, mari kita terapkan aturan itu lagi.Kurangi
9*2
dari 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
- Mendukung bilangan bulat presisi sembarang
- Hanya melakukan satu operan pada input
- Memiliki kompleksitas ruang
o(n)
(yaitu kurang dariO(n)
); dan - Memiliki kompleksitas waktu
O(n)
,
di mana n
jumlah 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).
sumber
1000000000000000000001
.long long
s atau beberapa jenis yang setara bawaan?Jawaban:
Golfscript,
2722 byteAnda bisa menggunakannya dengan cara ini:
Penjelasan
5 byte disimpan berkat Dennis!
sumber
@wizzwizz4
(@
lalu nama pengguna saya) di awal (atau di mana saja di) komentar.{...}{}if
bagian 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 ganti70
dengan9
menghemat satu byte), dan saya rasa Anda tidak perlu menghapus blokirnya;
.Haskell, 35 byte
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.
sumber
Jelly, 11 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python 2, 38 byte
Coba di sini !
Pendekatan rekursif sederhana. Mencetak x jika <70 jika tidak menerapkan aturan pembagian dan menyebut dirinya dengan hasilnya.
sumber
)
f=lambda x:x*(x<70)or f(x/10-x%10*2)
x*(x<70) != 0
sebagai kondisi akhir. Jika x mencapai 0 - seperti halnya pada 2016 - kondisi akhir tidak pernah terjadi.Pyth, 13 byte
Cobalah online: Demonstrasi atau Test Suite
Ini akan mencetak semua jawaban alternatif.
Penjelasan:
sumber
Julia,
2726 byteIni adalah fungsi rekursif yang menerima bilangan bulat dan mengembalikan a
BigInt
. Jika inputnya besar seperti pada contoh terakhir, Julia mem-parsingnya sebagaiBigInt
, 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!
sumber
70
dengan9
menyimpan satu byte.Pyth, 17 byte
Coba di sini!
Pendekatan rekursif yang sama seperti pada jawaban python saya . Mendefinisikan sebuah lambda
y
yang 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
sumber
CJam - 19 byte
Versi do-while:
Cobalah online atau Sementara versi # 1:
Cobalah online atau Sementara versi # 2:
Cobalah online .
sumber
Oracle SQL 11.2, 116 byte
Tidak bermain golf
sumber
Haskell,
157192184167159147138 + 5 byte - 50% = 71,5 byteO (1) ruang, O (n) waktu, sekali jalan!
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:
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
sev
Fungsi dalam versi yang tidak diklik akan bekerja padaInteger
, mengubahnya menjadi bentuk aliran terbalik.sumber
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 ...0
ketika memanggil!
, juga, misalnya sebagai bagian(0!)
(+ baris baru), yaitu +5 byte. Di sisi lain, Anda dapat mempersingkat yang pertama untuk mencocokkan pola!
kep![d]=
danp![d,e]=
. Juga, penggunaan pola penjaga bukanlet
:p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
.(0!)
pada baris itu sendiri.(0!)
adalah fungsi yang Anda berikan sebagai jawaban Anda. The0
diperlukan, tetapi tidak ada hubungannya dengan input, sehingga Anda tidak bisa outsource ke pemanggil. Tentu saja Anda juga bisa menggunakanf x=0!x
, tetapi ini lebih lama.GNU dc,
2015 byteIni mendefinisikan fungsi dc pertama saya
F
,. Dibutuhkan input di atas tumpukan, dan meninggalkan hasilnya di atas tumpukan. Contoh penggunaan:sumber
Mathematica,
4744 bytePendekatan rekursif sederhana. Mungkin bisa bermain golf lebih lanjut.
sumber
#0[{1,-2}.QuotientRemainder[#,10]]
menghemat satu byte.R, 43 byte
Penjelasan:
Sampel berjalan:
sumber
JavaScript ES6, 38 byteGagal
36893488147419103232
menggunakan dan menggunakan~~(1/10)
juga akan gagal untuk700168844221
Uji:
sumber
Fail
... 70 dan 32f=n=>n>70?f((n-n%10*21)/10):n
adalah versi yang lebih pendek tetapi masih hanya berfungsi hingga2**56
.Mathematica, 33 byte
Kasus cobaan
sumber
Perl 5,
4746 byteHarus digunakan
bigint
untuk test case terakhir. (Mengembalikan 20 tanpa)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!
sumber
ES6, 108 byte
Dapat digunakan untuk 2²⁵⁷ dan 100000000000000000000001, tetapi dapat menggunakan golf lebih lanjut.
sumber
JavaScript ES6,
140142 byteIni 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
0
s yang tepat dan menyebut dirinya secara rekursif sampai nilai numeriknya kurang dari atau sama dengan9
.sumber
1000000000000000000001
.s.replace(/.$/,'-$&*2')
. Saya tidak punya ide yang jelas untuk sisanya meskipun maaf.C #,
111104 bytesumber
Brain-Flak ,
368360 byteCobalah 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:
sumber
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).
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:
Langkah "gandakan dengan tiga" ditulis
n-=-n-n
untuk 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
*c
dengan*c||n>6
dalamfor
kondisi loop.Itu memenuhi syarat untuk bonus yang ditingkatkan, karena itu
Program uji dan hasil
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
):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.
sumber
PHP, 50 byte
menggunakan output alternatif; bekerja hingga
PHP_INT_MAX
versi string, berfungsi untuk semua angka (positif) (64 byte):
sumber
Java, 133 byte
Aku benci bagaimana verbose
Integer.parseInt
itu. Tidak Disatukan:sumber