Keluarkan pernyataan formal lengkap dari pernyataan seperti itu 1+2=3
, 2+2=2*(1+1)
dll.
Introuction
Jika Anda tahu Peano Arithmetic Anda mungkin dapat melewati bagian ini.
Inilah cara kami mendefinisikan Bilangan Alami:
(Axiom 1) 0 is a number
(Axiom 2) If `x` is a number, the `S(x)`, the successor of `x`, is a number.
Karenanya, misalnya S(S(S(0)))
adalah angka.
Anda dapat menggunakan representasi yang setara dalam kode Anda. Misalnya, semua ini valid:
0 "" 0 () !
1 "#" S(0) (()) !'
2 "##" S(S(0)) ((())) !''
3 "###" S(S(S(0))) (((()))) !'''
...
etc
Kita dapat memperluas aturan untuk mendefinisikan tambahan sebagai berikut.
(Rule 1) X+0 = X
(Rule 2) X+S(Y)=S(X)+Y
Dengan ini kita dapat membuktikan 2 + 2 = 4 sebagai berikut
S(S(0)) + S(S(0)) = 2 + 2
[Rule 2 with X=S(S(0)), Y=S(0)]
S(S(S(0))) + S(0) = 3 + 1
[Rule 2 with X=S(S(S(0))), Y=0]
S(S(S(S(0)))) + 0 = 4 + 0
[Rule 1 with X=S(S(S(S(0))))
S(S(S(S(0)))) = 4
Kita dapat memperluas aturan ini untuk mendefinisikan perkalian sebagai berikut
(Rule 3) X*0 = 0
(Rule 4) X*S(Y) = (X*Y) + X
Meskipun untuk memungkinkan ini kita perlu mendefinisikan peran struktural tanda kurung.
(Axiom 3) If X is a number, (X) is the same number.
Operator tambahan dan perkalian adalah biner ketat dan tanda kurung harus selalu eksplisit. A+B+C
tidak didefinisikan dengan baik, tetapi (A+B)+C
dan A+(B+C)
sedang.
Contoh
Sekarang kita memiliki cukup untuk membuktikan teorema tentang perkalian: 2 + 2 = 2 * 2
2 + 2
(2) + 2
(0 + 2) + 2
((0*2) + 2) + 2
(1*2) + 2
2*2
Persyaratan
Sebuah bukti yangA=B
merupakan ekspresi daftar sehingga:
- yang pertama adalah
A
, - yang terakhir adalah
B
, dan - setiap ungkapan dalam daftar selain yang pertama dapat diperoleh dari yang sebelumnya dengan mentransformasikannya di bawah salah satu aturan.
Program Anda akan mengambil dua ekspresi yang valid sebagai input , setiap ekspresi berisi angka, penambahan, perkalian, dan tanda kurung seperti yang didefinisikan di atas.
Program Anda akan menghasilkan bukti, daftar sebagaimana didefinisikan di atas, bahwa kedua ekspresi itu sama, jika bukti tersebut ada.
Jika kedua ekspresi tidak sama, program Anda tidak akan menghasilkan apa-apa.
Membuktikan atau menyangkal selalu mungkin dalam sejumlah langkah terbatas, karena setiap ekspresi dapat dikurangi menjadi satu nomor dan angka-angka ini dapat diuji secara sepele untuk kesetaraan.
Jika ekspresi input tidak valid (mis. Tanda kurung tidak seimbang, berisi operator non-angka, atau non-biner) maka program Anda harus keluar dengan kesalahan, melemparkan pengecualian, mencetak kesalahan, atau menghasilkan beberapa perilaku yang dapat diamati yang berbeda dari kasus di mana input valid tetapi tidak sama .
Singkatnya, output normal untuk input yang dapat diterima adalah daftar angka yang sama, termasuk input, yang dihasilkan oleh aturan berikut.
(Axiom 1) 0 is a number
(Axiom 2) If `x` is a number, the `S(x)`, the successor of `x`, is a number.
(Axiom 3) If X is a number, (X) is the same number
(Rule 1) X+0 = X
(Rule 2) X+S(Y)=S(X)+Y
(Rule 3) X*0 = 0
(Rule 4) X*S(Y) = (X*Y) + X
(Rule 5) X = (X) (Axiom 3 expressed as a transformation rule.)
Setiap representasi yang sesuai dari angka-angka pada input dan output diperbolehkan, misalnya 0=""=()
, 3="###"=(((())))
, dll Whitespace tidak relevan.
Aturan bisa, tentu saja, diterapkan di kedua arah. Program Anda tidak harus menampilkan aturan mana yang digunakan, hanya ekspresi yang dihasilkan oleh aksinya pada ekspresi sebelumnya.
Kode terpendek menang.
Jawaban:
Perl, 166 +1 byte
Jalankan dengan
-p
(penalti 1 byte).Lebih mudah dibaca:
Format input mengekspresikan angka secara unary sebagai string
S
, dan membutuhkan dua input pada baris yang berbeda (masing-masing diikuti oleh baris baru, dan EOF setelah keduanya terlihat). Saya menafsirkan pertanyaan sebagai mensyaratkan bahwa tanda kurung harus secara harfiah(
)
dan penambahan / perkalian harus secara harfiah+
*
; Saya dapat menyimpan beberapa byte melalui sedikit pelarian jika saya diizinkan membuat pilihan yang berbeda.Algoritma sebenarnya membandingkan baris input pertama dengan baris kosong, baris kedua dengan baris pertama, baris ketiga dengan baris kedua, dan seterusnya. Ini memenuhi persyaratan pertanyaan. Berikut ini contoh yang dijalankan:
Masukan saya:
Output program:
Digandakan
SSSS
di tengah menjengkelkan tapi saya memutuskan tidak melanggar spesifikasi, dan lebih sedikit byte untuk meninggalkannyaPada input yang tidak valid, saya menambahkan
1
karakter baris baru, sehingga Anda tersesat1
di akhir output.sumber
echo -e "((SS+)+(S+S))\nSS*SS" | perl -p /tmp/x.pl
output1
.(SS*SS)
). "Operator tambahan dan multiplikasi adalah biner dan tanda kurung harus selalu eksplisit."