f (g (x)) berkurang sementara g (f (x)) meningkat

42

Untuk tantangan ini, Anda perlu mengimplementasikan dua fungsi, f dan g , pada bilangan bulat, sehingga f ∘ g adalah fungsi yang sangat menurun sementara g g f adalah fungsi yang benar-benar meningkat. Dengan kata lain, jika Anda mengambil dua bilangan bulat a <b , maka f (g (a))> f (g (b)) dan g (f (a)) <g (f (b)) . Tidak ada batasan pada f dan g secara terpisah, kecuali bahwa mereka masing-masing harus memetakan satu bilangan bulat ke bilangan bulat lainnya.

Harap sertakan deskripsi singkat tentang f dan g dan argumen mengapa mereka memiliki properti yang diperlukan.

Kredit: Tantangan ini terinspirasi oleh masalah dalam kompetisi Master of Mathematics Romania 2011 (yang menanyakan hal yang sama tetapi pada bilangan real, bukan bilangan bulat). Jika Anda benar-benar ingin spoiler, Anda sekarang tahu apa yang harus dicari.

Aturan

  • Kata "fungsi" dalam tantangan ini harus diambil dalam arti matematis memetakan satu bilangan bulat ke yang lain: Anda dapat menulis dua program atau dua fungsi dan menggunakan salah satu metode standar untuk menerima input dan memberikan output, seperti biasa. Anda dapat menggunakan representasi string dari integer alih-alih variabel integer yang sebenarnya, tetapi jenis input dan output harus identik, sehingga fungsi dapat dikomposisikan tanpa secara manual mengkonversi tipe di antaranya. Ingatlah bahwa secara konseptual, f dan g masih harus berfungsi pada ℤ, jadi Anda tidak dapat menipu dengan menggunakan dua representasi string yang berbeda dari angka yang sama atau yang seperti itu.

  • Ingatlah bahwa fungsi mungkin tidak disebutkan namanya , selama namanya tidak diperlukan dengan sendirinya atau fungsi lain yang Anda tetapkan. Jika Anda menyebutkan satu atau kedua fungsi, Anda dapat mengasumsikan bahwa mereka ada dalam program yang sama, sehingga mereka dapat merujuk satu sama lain dalam implementasinya (mis. Dengan def f(x): return -g(x)Python).

  • Aturan bilangan bulat bilangan bulat yang biasa berlaku: solusi Anda harus dapat bekerja untuk bilangan bulat besar yang sewenang-wenang dalam versi hipotetis (atau mungkin nyata) bahasa Anda di mana semua bilangan bulat tidak terikat secara default, tetapi jika program Anda gagal dalam praktik karena implementasi tidak mendukung bilangan bulat yang besar, itu tidak membatalkan solusi.

  • Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

  • Ini adalah , jadi skor Anda adalah jumlah dari jumlah byte dari kedua fungsi dan jawaban tersingkat yang menang.

Martin Ender
sumber
Bisakah fungsi mengembalikan string?
Matius Roh
@SIGSEGV Saya akan mengatakan ya, tetapi hanya jika mereka juga mengambil string sebagai input, sehingga mereka dapat dikomposisikan tanpa harus memasukkan konversi tipe apa pun.
Martin Ender
Aduh, saya mencoba konversi ke string untuk membuat fungsi lain tidak dapat mengedit hasil lebih lanjut.
Matius Roh
1
@Fatalize Correct. Masing-masing harus merupakan fungsi tipe ℤ → ℤ.
Martin Ender
1
@Bijan positif dan negatif.
Martin Ender

Jawaban:

18

Python, 68 karakter

f=lambda x:(1-x%2*2)*(2*x*x+(x<0))
g=lambda x:(1-x%2*2)*(2*x*x+(x>0))

f memetakan angka negatif ke angka ganjil dan angka positif ke angka genap, dan bahkan nomor ke angka positif dan angka ganjil ke angka negatif, dengan besarnya output meningkat ketat dengan besarnya input.

g melakukan hal yang sama, kecuali memetakan angka negatif ke angka genap dan angka positif ke angka ganjil.

f ∘g memetakan negatif → datar → positif dan positif → aneh → negatif.
g ∘ f peta negatif → ganjil → negatif dan positif → genap → positif.

Karena itu f dan g memiliki sifat yang diinginkan.

pengguna1502040
sumber
2
fdan gbisa berupa fungsi yang tidak disebutkan namanya, sehingga Anda dapat menjatuhkan empat byte.
Martin Ender
Anda dapat mendefinisikan (1-x%2*2)sebagai variabel untuk menyimpan beberapa byte.
OldBunny2800
Berikut adalah kode lengkap untuk dimainkan dengan import numpy as np; import matplotlib.pyplot as plt; xrange=np.arange(-3,4); f=lambda x:(1-x%2*2)*(2*x*x+(x<0)); g=lambda x:(1-x%2*2)*(2*x*x+(x>0)); plt.plot(xrange, map(f, xrange), 'ro'); plt.plot(xrange, map(g, xrange), 'go'); plt.plot(xrange, map(f, map(g, xrange)), 'b--'); plt.plot(xrange, map(g, map(f, xrange)), 'y--'); plt.show(); Anda dapat mengganti ;dengan linefeeds agar mudah dibaca.
Stéphane Gourichon
16

Python , 40 byte

f=lambda x:x*(-1)**x
g=lambda x:3*f(x)+1

Cobalah online! Beberapa output adalah float yang sama dengan bilangan bulat karena (-1)**(-3)memberikan float misalnya.

Didasarkan atas ide - ide dari Peter Taylor . Fungsi fmeniadakan angka ganjil dan membiarkan yang tidak berubah. Fungsi gmelakukan hal yang sama, kemudian menerapkan peta switching paritas monotonik x -> 3*x + 1.

Sejak itu f(f(x)) = x, kami g(f(x)) = 3*f(f(x))+1 = 3*x+1semakin meningkat.

Sebab f(g(x)) = f(3*f(x)+1), idenya adalah bahwa tepat salah satu ftanda flips dalam dan luar , membuatnya berkurang.

  • Untuk bahkan x,, f(x) = xtetapi f(3*x+1) = -3*x-1karena 3*x+1itu aneh.
  • Untuk yang aneh x,, f(x) = -xdan f(-3*x+1) = -3*x+1karena -3*x+1itu genap.

Kita sekarang hanya membutuhkan input genap dan ganjil yang interleave dengan cara menurun, yang berlaku karena -3*x±1berkurang terlepas dari bagaimana tanda-tanda dipilih. Inilah mengapa 3*dibutuhkan.

Port Haskell adalah 25 byte:

f x=x*(-1)**x
g x=1+3*f x

Cobalah online!

Tidak
sumber
Dalam Haskell, (^)adalah eksponen bilangan bulat.
user1502040
1
@ user1502040 Tidak dapat menangani eksponen negatif.
xnor
1
Karena Anda tidak menyebut gdiri Anda, Anda dapat menyimpan dua byte dengan membuatnya tidak bernama.
Martin Ender
14

CJam (17 byte)

Fungsi f (dinamai Fkarena CJam hanya mengizinkan nama huruf besar):

{W1$2b,#*}:F

Fungsi g (anonim):

{F2*}

Demo online

Ini menghemat satu byte dengan mengandalkan detail implementasi CJam yang bisa dibilang bug: ketika melakukan konversi basis, ia menggunakan nilai absolut. 2b,karena itu memberikan jumlah bit dalam nilai absolut argumennya, jadi f meniadakan angka-angka yang nilai absolutnya memiliki jumlah bit ganjil. g berlaku f dan kemudian gandakan (mengubah paritas jumlah bit).

Jadi menerapkan f dan kemudian meninggalkan tanda tidak berubah dan ganda, pemetaan xke 2x. Menerapkan g dan kemudian f mengubah tanda tepat sekali dan dua kali lipat, memetakan xke -2x.

Peter Taylor
sumber
Bagus, inilah solusi referensi yang disediakan dalam kompetisi ini. (Saya berasumsi Anda datang dengan itu secara independen?)
Martin Ender
@ MartinEnder, saya pernah melihat masalah ini di suatu tempat sebelumnya. Mungkin di math.SE.
Peter Taylor
2

Pyth, 34 Bytes

Ini hanya terjemahan langsung dari jawaban Python saya.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
pengguna1502040
sumber