Tentukan fungsi f sedemikian rupa sehingga f (f (n)) = -n untuk semua bilangan bulat bukan nol n

43

Tantangan ini diinspirasi oleh blog pemrograman yang sering saya kunjungi. Silakan lihat posting asli di sini: Puzzle Pemrograman


Tantangan

Tetapkan fungsi f:Q->Qsedemikian rupa f(f(n)) = -nuntuk semua bilangan bulat bukan nol n, dan di mana Qhimpunan bilangan rasional.

Detail

Dalam bahasa apa pun yang Anda inginkan, sebutkan satu fungsi atau program fyang menerima sebagai parameter satu nomor ndan mengembalikan atau menampilkan satu nomor f(n).

Input dapat diberikan melalui mekanisme apa pun yang paling alami untuk bahasa Anda: argumen fungsi, baca dari STDIN, argumen baris perintah, posisi tumpukan, input suara, tanda-tanda geng, dll.

Output harus berupa nilai balik dari fungsi / program atau dicetak ke STDOUT.

Saya ingin membatasi jawaban untuk fungsi yang tidak memanfaatkan status program atau memori / data global yang terlihat dari luar fungsi f. Misalnya, menjaga penghitung di luar fitu dihitung berapa kali fdipanggil dan hanya melakukan negasi berdasarkan perhitungan ini tidak terlalu menantang atau menarik bagi siapa pun. Keputusan yang diambil fharus hanya bergantung pada data dalam flingkup leksikal.

Namun, batasan ini mungkin tidak sesuai untuk beberapa bahasa berorientasi tumpukan atau jenis bahasa lain yang tidak membedakan tipe data atau cakupan ini. Silakan gunakan penilaian terbaik Anda untuk tetap dengan semangat tantangan ini.


Mencetak gol

Aturan golf kode umum berlaku - skor Anda adalah jumlah byte dalam kode sumber Anda.

Jawaban minimal membutuhkan domain dan kode funtuk menjadi subset dari rasional Q. Jika Anda membatasi domain dan kode domain Anda fke bilangan bulat Z, maka skor Anda adalah batas tertinggi 90% dari jumlah byte dalam kode sumber Anda.

Tiebreak

Dalam hal seri, berikut ini akan digunakan secara berurutan:

  1. Jumlah simbol non-spasi putih yang dapat dicetak dalam kode sumber Anda
  2. Tanggal dan waktu paling awal pengiriman jawaban

Edit

Anda tidak diharuskan untuk mendukung angka-angka berukuran sewenang-wenang. Silakan mengartikan set Zdan Qsebagai tipe data dalam bahasa yang Anda pilih (biasanya integer dan floating point, masing-masing).

Jika solusi Anda sepenuhnya bergantung pada struktur atau pola bit dari tipe data, mohon jelaskan keterbatasannya dan bagaimana itu digunakan.

ardnew
sumber
20
f (n) = i * n - matematika murni: P
Johannes Kuhn
8
@JohannesKuhn inilah sebabnya domain dan codomain dibatasi untuk rasional
ardnew
Bisakah Anda menjelaskan apa f:Q->Qartinya?
beary605
@ beary605 artinya fadalah fungsi pemetaan anggota Q(angka rasional) ke anggota lain (mungkin sama) dari Q. lihat en.wikipedia.org/wiki/Function_(mathematics)#Notation
ardnew
7
Saya tahu saya melihat ini baru-baru ini, tetapi perlu beberapa saat untuk mengingat di mana. Versi yang kurang ditentukan pada StackOverflow baru-baru ini ditutup. Lebih dari 100 jawaban.
Peter Taylor

Jawaban:

12

J, 9 poin (10 karakter)

Berdasarkan jawaban stackoverflow :

   (*-[*_1&^)

Ide pertama (13 karakter):

   ((-*)-2&|*+:)

   ((-*)-2&|*+:) _10 _9 _8 _7 _6 _5 _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10
_9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9

   ((-*)-2&|*+:) _9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9
10 9 8 7 6 5 4 3 2 1 0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _10
randomra
sumber
Ini berfungsi untuk input bilangan bulat, tetapi ini menghasilkan output imajiner untuk nilai floating point (fungsi harus menghasilkan output rasional untuk input rasional sesuai dengan spesifikasi)
Volatilitas
5
@Vatilitas, spek ini membingungkan worded, tetapi ketika saya membacanya, ini memungkinkan membatasi domain dan codomain menjadi bilangan bulat.
Peter Taylor
Apakah Anda membutuhkan tanda kurung?
Cyoce
14

Python: 61 34 30 29 27 poin

f: Q -> Q

dalam matematika:

       | 0.5-x   if x is in Q \ Z
f(x) = |
       | x+0.5   if x is in Z

dalam Python:

f=lambda x:.5+[x,-x][x%1>0]

diuji dengan

filter(lambda n: n[0] != -n[1], map(lambda n:(n,f(f(n))),range(0,50)))

logika di balik ini:

Saat Anda mengambil bilangan bulat ndan memasukkannya ke dalam, fAnda akan mendapatkannya x+0.5. Ini bukan bilangan bulat lagi, jadi aplikasi selanjutnya 0.5-(x+0.5)adalah -x.

Kredit

Terimakasih untuk

  • Bakuriu untuk menghapusnya dari 61 karakter menjadi 34 karakter.
  • Volatilitas untuk mengurangi ukuran kode hingga 30 karakter.
  • salin untuk mengurangi ukuran kode hingga 29 karakter (dan memperbaiki masalah floating point potensial).
  • aditsu untuk menyebutkan ketidakkonsistenan yang datang dengan perubahan di atas.

Catatan

Pertama saya pikir ini akan baik-baik saja

f = lambda n: 1j*n

tapi itu f: N-> C dan itu tidak diperbolehkan: - /

Martin Thoma
sumber
1
Dapat dilucuti ke: f=lambda x:x%1>0and(-x+x%1)or x+.1yang hanya 34 karakter.
Bakuriu
f=lambda x:[x+.1,x%1-x](x%1>0)hanya 30
Volatilitas
1
Salah satu char di pendek: f=lambda x:[x+.5,.5-x][x%1>0]. Perhatikan penggunaan 0,5 bukannya 0,1 untuk mengatasi masalah presisi
salin
1
@AJMansfield 1.48 bukan bilangan bulat.
Martin Thoma
1
Tidak, itu tidak berarti. Jika dia ment itu, dia seharusnya menulis "semua angka rasional". f:Q->Qtidak hanya berarti bahwa f memetakan bilangan rasional ke bilangan rasional. Yang definisi saya tentang f tidak.
Martin Thoma
11

C, 41 poin (41 atau 45 karakter)

Bekerja menggunakan 32- dan 64-bit.

f : Z -> Z(kecuali INT_MAX):

f(n){return (abs(n)%2*2-1)*n+n?(-n<n)*2-1:0;}

Jika kita tidak harus memasukkan, 0kita dapat mencukur beberapa karakter (41 karakter):

f : Z -> Z(kecuali 0& INT_MAX):

f(n){return (abs(n)%2*2-1)*n+(-n<n)*2-1;}

Fungsi ini berfungsi dengan membagi semua bilangan bulat menjadi 4 kelompok berdasarkan tanda dan paritasnya.

Jadi kami memiliki 4 kombinasi berbeda:

+ even, + odd, - even, - odd

Karena kita perlu mengganti tanda nomor, tetapi bukan paritas setelah dua lintasan, kita mendapatkan dua kemungkinan urutan yang berbeda:

  + even -> - odd -> - even -> + odd -\
^-------------------------------------/

  + even -> + odd -> - even -> - odd -\
^-------------------------------------/

Dalam contoh ini saya telah memilih yang pertama.

Pertama kita perlu memetakan semua bahkan bilangan bulat positif ke bilangan bulat negatif ganjil. Kami melakukan ini dengan mengubah tanda dan menambah nomor (Anda juga dapat memilih untuk mengurangi angka):

f1(n) = -n + 1

Kita kemudian perlu memetakan semua bilangan bulat negatif ganjil ke bahkan bilangan bulat negatif. Kita perlu memastikan bahwa f2(f1(n)) = -n:

f2(f1(n)) = -n
f2(-n + 1) = -n
f2(-n) = -n - 1
f2(n) = n - 1

Menggunakan metode yang sama kami temukan f3dan f4:

f3(n) = -n - 1
f4(n) =  n + 1

Untuk menggabungkan fungsi-fungsi ini menjadi satu fungsi tunggal, kami mengamati bahwa setiap kali nbahkan kami mengganti tanda ndan setiap kali npositif kami bertambah satu dan jika tidak, kami mengurangi satu:

f1(n) = -n + 1 (+ even)
f2(n) =  n - 1 (- odd)
f2(n) = -n - 1 (- even)
f4(n) =  n + 1 (+ odd)

Dengan demikian ini dapat ditulis ulang sebagai:

f(n) = odd(n) * n + sign(n)

tempat odd(n)pengembalian 1untuk angka ganjil dan -1untuk angka genap.

Ada 4 solusi total:

f(n) = odd(n) * n + sign(n)  (edge cases: f(f(0))  -> -2, f(f(INT_MAX))   -> -8)
f(n) = even(n) * n - sign(n) (edge cases: f(f(0))  -> -2, f(f(INT_MIN+1)) -> -6)
f(n) = odd(n) * n - sign(n)  (edge cases: f(f(1))  -> -3, f(f(INT_MIN))   -> -5)
f(n) = even(n) * n + sign(n) (edge cases: f(f(-1)) -> -1, f(f(INT_MIN))   -> -5)

INT_MINmungkin selalu dianggap sebagai tepi kasus dalam semua 4 fungsi sebagai -INT_MIN == INT_MIN=> f(f(INT_MIN)) = INT_MIN.

Tyilo
sumber
Ini pada dasarnya sama dengan jawaban GolfScript saya (kecuali dijelaskan lebih baik). Apakah ini berfungsi untuk 0?
Ben Reich
@ Ben Reich Seperti yang dinyatakan dalam jawaban itu tidak berfungsi 0dan 3 nomor lainnya.
Tyilo
1
@ Tylio saya mengerti sekarang. Masuk akal. Sepertinya Anda hanya harus mengambil Zbonus jika Anda mencakup 0, setidaknya.
Ben Reich
@BenReich Menghapus bonus sampai saya memperbaikinya.
Tyilo
9

Ini dia.

long f(int i){return i;}
int f(long i){return -i;}

Contoh langsung :

int main()
{
  for(int i=-10; i<10; i=i+3)
    std::cout << f(f(i)) << "\n";
}

Jenis input cn dapat secara sewenang-wenang disesuaikan dengan kebutuhan Anda. Versi ini berfungsi untuk bilangan bulat integer yang lebih kecil besarnya dari 2 ^ 32-1.

rubenvb
sumber
2
Masalahnya f:Q->Q, tidak f:Z->Z.
AJMansfield
@AJMansfield bagian penilaian dari spec dimaksudkan untuk menawarkan poin bonus untuk fungsi yang ditentukan f:Z->Z, maaf untuk kata
ardnew
6
masalah dengan jawaban ini adalah tampaknya mendefinisikan dua fungsi yang terpisah, sementara spesifikasi mengharuskan Anda hanya mendefinisikan satu. tetapi saya tidak bermaksud memulai debat semantik, ini masih merupakan solusi yang sangat bijaksana
ardnew
@ardnew, oh kamu benar. Saya diarahkan ke keberatan yang valid ini hanya beberapa detik sebelum membaginya dengan Lounge <C ++> di SO chat. Saya bertanya-tanya apa yang membuat kompiler ini (jika tidak sebaris panggilan), tapi perakitan saya payah.
rubenvb
1
Saya pikir Anda dapat menghapus ruang direturn -i
Cyoce
6

JavaScript, 18

f=n=>n%1?.5-n:n+.5

Menggunakan notasi panah lemak baru (Firefox 22).

Versi lain (18):

f=n=>n%1?-.5/n:.5/n

Versi sebelumnya (20):

f=n=>n-~~n?.5-n:n+.5

Contoh:

> [-3,-2,-1,1,2,3].map(f).map(f)
[3, 2, 1, -1, -2, -3]
salinan
sumber
10
Sepertinya JavaScript berkembang menjadi CoffeeScript.
Peter Taylor
4

Mathematica 18

f=#+1/2-4#(#-⌊#⌋)&

Inilah ⌊...⌋fungsi lantai. Hanya menggunakan bilangan rasional (bukan daftar, bilangan kompleks, dll)

f[10]
f[f[10]]

21/2

-10

f[-5]
f[f[-5]]

-9/2

5

ybeltukov
sumber
3

x86 bahasa rakitan (FASM). Argumen dan hasilnya ada di eax register.

Ini berfungsi dengan baik untuk -2 ^ 30 <N <+ 2 ^ 30-1

16 byte kode yang dapat dieksekusi.

        use32

f_n:
        lea     edx, [2*eax]
        xor     edx, eax
        btc     eax, 30
        shl     edx, 1
        jnc     .end
        neg     eax
.end:
        retn
Johnfound
sumber
Nitpicking nomor Anda; 2E30 akan menjadi 2 * 10 ^ 30, bukan 2 ^ 30 seperti yang saya inginkan.
Nick T
@NickT Kesalahan saya. Tetap.
johnfound
Saya cukup yakin Anda seharusnya menghitung byte dalam kode sumber.
nyuszika7h
3

Gangguan Umum: 35 byte

(defun f(x)(/(if(> 1 x)-1/2 1/2)x))

Skema (dan Racket): 36 byte

(define(f x)(/(if(> 1 x)-1/2 1/2)x))

Tidak digabungkan dengan komentar dan penjelasan:

(define (f x)
  (/             ;; divide
     (if (> 1 x) ;; if x is below 1 
         -1/2    ;; then -1/2 (the fraction)
         1/2)    ;; else 1/2 (the fraction)
      x))        ;; gets divided with x

Untuk angka apa pun xdi [1,->]dalam ifakan berubah menjadi fraksi 1/2yang merupakan angka persis nyata dalam kedua bahasa

Bagian bagi kemudian akan menjadi (/ 1/2 x)sehingga pecahan akan menjadi 1/(x*2)yang selalu di bawah ini 1. Untuk 1itu akan 1/2, untuk 2itu 1/4, dll.

Untuk angka apa pun di bawah 1, ifakan berubah menjadi fraksi -1/2, yang membuat fungsi melakukan (/ -1/2 x)yang mana -1/(2*x)tetapi karena kita dapat mengharapkan nilai sebagai hasil dari menjalankan sebelumnya kita dapat mengganti x untuk 1 / (x * 2) membuat aplikasi ganda-1/((1/(x*2))*2) = -x

Misal sejak 1berubah menjadi 1/2aplikasi kedua ini(/ -1/2 1/2) ==> -1

Sylwester
sumber
Bagaimana cara kerjanya?
AJMansfield
@AJMansfield menambahkan beberapa info. Tanyakan saja apakah ada sesuatu yang tidak jelas. Membaca sintaks LISP seperti Yunani jika Anda belum mempelajarinya dan perlu beberapa minggu untuk membiasakan diri.
Sylwester
3

C, 60 (⌈66 * .9⌉)

int f(int x){if(!x&1||!~x)return ~x;if(x<0)return x-1;return x+1;}

Ini adalah versi yang tidak dikondensasi:

int f(int x){
    if(!x&1 || !~x) return ~x;
    if(x<0) return x-1;
    return x+1;
}

Metode ini hanya bekerja menggunakan bilangan bulat, sehingga mendapat bonus skor 90%. Saya awalnya menulis dalam java, tetapi menyadari bahwa program ini khususnya bisa mendapatkan keuntungan dari operator logis C-style.

Karena tidak ada bilangan bulat yang sesuai dengan -INT_MIN, sebaliknya f(f(INT_MIN))mengembalikan INT_MIN.

Pemetaan yang mendasari secara aljabar agak sederhana. Mengeksekusi pernyataan tersebut x=f(x)menggantikan x dengan:

  • x+1, jika xpositif dan aneh
  • -x+1, jika xpositif dan genap
  • x-1, jika xnegatif dan ganjil
  • -x-1, jika xnegatif dan genap

Hasil dari setiap kasus akan jatuh di bawah kasus berikutnya saat fungsi berikutnya diterapkan ke x.

Seperti yang Anda lihat, membuat kasing dengan kasing yang menghasilkannya -x.

Kode ini adalah hasil dari beberapa penyederhanaan fungsi untuk memanfaatkan struktur bit dari integer pujian dua.

AJMansfield
sumber
3

> <> , 21 + 3 = 24 byte, 22 poin

:0)$:0($:1$2%2*-*+-n;

Gunakan juru bahasa Python resmi , dan gunakan -vopsi baris perintah untuk memasukkan input, dengan biaya 3 byte.

Saya punya perasaan bahwa ini bisa lebih baik - saya akan terus melihatnya dan mencoba untuk menurunkannya.

Input yang diberikan n, output program

(n>0) - ((n<0) + n * (1 - 2*(n%2)))

di mana (n>0)dan (n<0)adalah booleans. Ini sama dengan jawaban Python Gelatin

(n>0) - (n<0) - n * (-1)**n

tetapi ><>tidak memiliki operator eksponensial bawaan sehingga kami gunakan (1 - 2*(n%2))sebagai pengganti (-1)**n.

Berikut ini adalah teori matematika - baca jika (dan hanya jika) Anda tertarik:

Dengan fungsi apa pun f: Z -> Zsehingga f(f(n)) = -nuntuk semua yang ada ndi Zdalamnya, kita segera melihat bahwa f(f(f(f(n)))) = n, atau dengan kata lain, f^4adalah fungsi identitas. Secara khusus, fdapat dibalik, dan fungsi kebalikannya adalah f^3. Dengan demikian fadalah permutasi dari Z, dan karena f^4 = Iditu berikut bahwa setiap orbit (atau siklus) dari fmemiliki ukuran baik 1, 2atau 4.

Selanjutnya, kita melihatnya f(0) = 0. Bukti:, f(0) = f(-0) = f(f(f(0))) = -f(0)jadi f(0) = 0, seperti yang diinginkan. Sebaliknya, anggaplah xdalam siklus panjang 1atau 2, jadi f(f(x)) = x. Lalu -x = xbegitu x = 0.

Dengan demikian fseluruhnya terdiri dari 4 siklus, kecuali untuk titik tetap (1 siklus) di 0.

Selanjutnya, setiap 4 siklus harus memiliki bentuk (x, y, -x, -y), dan dengan memutar siklus di sekitar kita dapat mengasumsikan itu xdan ykeduanya positif. Sebaliknya, setiap produk seperti partisi 4-siklus bilangan bulat nol menentukan pilihan f.

Dengan demikian setiap pilihan fkoresponden secara unik dengan grafik berarah yang simpulnya adalah bilangan bulat positif, sehingga setiap simpul adalah kejadian tepat satu panah, baik yang masuk atau keluar. Lebih tepatnya, dalam grafik tak berarah yang mendasarinya, setiap simpul memiliki derajat tepat 1. (Setiap 4 siklus (x y -x -y)dengan xdan ypositif sesuai dengan panah x --> y.)

Fungsi dalam jawaban ini (dan beberapa jawaban lain di sini) sesuai dengan grafik di mana 1 --> 2, 3 --> 4dan pada umumnya 2k-1 --> 2k.

Grafik tersebut di bijection dengan urutan yang tak terbatas dari pasangan memerintahkan (a_n, p_n), di mana masing-masing a_nadalah bilangan bulat positif dan masing-masing p_nadalah baik 0atau 1: diberikan berurutan (a_1, p_1), (a_2, p_2), (a_3, p_3), ..., pertama kita pasangan 1dengan 1 + a_1, dan kemudian kita membentuk baik panah 1 --> 1 + a_1atau panah 1 + a_1 --> 1tergantung pada apakah p_1ini 0atau 1. Pada dasarnya, panah adalah <tanda atau >tanda, tergantung pada paritas p_1.

Selanjutnya, ambil bilangan bulat positif terkecil yang tidak berpasangan k, dan hitung dari k, persis a_2langkah-langkah, MEMASANG angka yang sudah dipasangkan dengan sesuatu. Pasangkan kdengan hasilnya, dan atur arah panah tergantung p_2seperti di atas. Kemudian ulangi dengan (a_3, p_3), dll.

Setiap panah pada akhirnya akan ditentukan dengan cara ini, sehingga prosesnya didefinisikan dengan baik. Fungsi dalam jawaban ini sesuai dengan urutan (1,0), (1,0), (1,0), ..., karena pada langkah nbilangan bulat tidak berpasangan terkecil adalah 2n-1dan tidak ada bilangan bulat yang lebih besar daripada yang 2n-1telah dipasangkan dengan apa pun, jadi kita dapatkan 2n-1 --> 2nuntuk masing-masing n(panah diorientasikan dengan cara ini karena masing-masing p_nsama dengan 0).

Kardinalitas himpunan ini adalah (N*2)^N = N^N, yang pada paragraf terakhir jawaban ini sama dengan 2^N, kardinalitas bilangan real.

mathmandan
sumber
Opsi baris perintah biasanya masing-masing satu byte.
kucing
@cat Lihat bagian "Doa Khusus" di pos meta ini .
mathmandan
2

Untuk memperbaiki jawaban J sebelumnya (saya tidak memiliki reputasi yang cukup untuk mengomentari yang asli):

(*+[*1-~2*2|])

Itu hanya menggantikan _1&^dengan 1-~2*2|], yang memberi tanda sebaliknya. Jadi saya mengubah -ke +(yang hanya penting pada input 1dan _1).

Inilah tes-tesnya:

   (*+[*1-~2*2|])6 3 _9 _8 1r2 _4.6 0 1 _1
7 _2 8 _9 1 7.28 0 2 _2
   (*+[*1-~2*2|])7 _2 8 _9 1 7.28 0 2 _2
_6 _3 9 8 0 _10.3568 0 _1 1

   NB. f^:2 = f@:f
   (*+[*1-~2*2|])^:(2)6 3 _9 _8 1r2 _4.6 0 1 _1
_6 _3 9 8 2 _5.0832 0 _1 1

Seperti yang Anda lihat, domain dan rentang semua bilangan real, tetapi hanya berfungsi untuk bilangan bulat (termasuk 0).

Penjelasan:

(   *     + [ *  1-~    2*     2|]    )
 signum n + n * pred (twice (n mod 2))
James Wood
sumber
2

GolfScript ceiling(26*.9)=24

Golfscript hanya menangani bilangan bulat, jadi terapkan Zbonus dengan total 24 poin:

.{..0>2*(\)2%!2*(@*+}{ }if

Kasing khusus 0 akun untuk 8 karakter. Mengabaikan 0, kita dapat memiliki 17 poin jawaban:

..0>2*(\)2%!2*(@*+

Kode ini melakukan hal berikut ini ke integer xdi atas tumpukan:

  • Jika x0, tinggalkan 0di tumpukan dan tidak menerapkan aturan lagi.
  • Jika xgenap, negasikan x.
  • Jika xpositif, tambahkan 1.
  • Jika xnegatif, kurangi 1.

Ini secara logis menghubungkan set 4 angka dalam satu siklus, di mana felemen lintas siklus, dan sudut-sudut yang berlawanan dari siklus adalah negatif satu sama lain. Setiap bilangan bulat adalah bagian tepat dari 1 siklus seperti itu, kecuali 0 yang merupakan casing khusus. Misalnya, untuk {-8, -7, 7, 8}:

  • 7 f -> 8
  • 8 f -> -7
  • -7 f -> -8
  • -8 f -> 7

Satu-satunya kasus uji yang relevan yang dapat saya pikirkan adalah negatif aneh, negatif bahkan, positif aneh, bahkan positif 0, dan kemudian saya melemparkan -1dan 1karena kedekatannya dengan 0mungkin telah menyebabkan masalah:

[-10 -5 -1 0 1 5 10]
{.{..0>2*(\)2%!2*(@*+}{ }if}:f;
{f f}%
-> [10,5,1,0,-1,-5,-10]

Saya yakin GolfScript yang sebenarnya dapat sedikit ditingkatkan. Itu tidak terasa seperti itu harus mengambil 26 karakter! Senang mendengar beberapa saran.

Ben Reich
sumber
2

Jawa, hanya untuk bersenang-senang

Berikut ini adalah implementasi yang melakukan penambangan aktual antara ℤ dan ℤ², yang merupakan fungsi aneh pada saat yang sama (g (-x) == -g (x)). Ini memperlakukan elemen ℤ² yang sesuai sebagai bilangan kompleks dan mengalikannya dengan "i", lalu mengubahnya kembali menjadi ℤ.

f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x

Fungsi berjalan di O (1).

public class Ffn {
    public static int f(int n) {
        if (n == 0) {
            return 0;
        }
        // adjust sign
        int s = n > 0 ? 1 : -1;
        int m = n * s;
        // calculate square "radius"
        int r = (int) (Math.sqrt(2 * m - 1) + 1) / 2;
        int q = r * 2;
        // starting point
        int x = r, y = r;
        int k = q * (r - 1) + 1;

        if (m - k < q) {
            // go left
            x -= m - k;
        }
        else {
            // go left
            x -= q;
            // go down
            y -= m - k - q;
        }

        // multiply by i
        int x2 = -y * s, y2 = x * s;
        // adjust sign
        s = y2 < x2 || y2 == x2 && x2 < 0 ? -1 : 1;
        x2 *= s;
        y2 *= s;

        if (y2 == r) {
            // go left
            k += r - x2;
        }
        else {
            // go left and down
            k += q + r - y2;
        }
        return k * s;
    }

    public static void main(final String... args) {
        for (int i = 0; i < 1000000; ++i) {
            if (f(f(i)) != -i || f(f(-i)) != i) {
                System.out.println(i);
            }
        }
    }
}

PS Selamat Tahun Baru!

aditsu
sumber
Saya percaya spasi tidak perlu.
pppery
2

Python 3 - 38

Mirip dengan jawaban @ moose, tetapi f(n) == n,. Berfungsi untuk semua nilai integer.

f=lambda x:x*(isinstance(x,int)*2.0-1)
cjfaure
sumber
2

Perl, 33 (non-spasi putih)

sub f{($=)=@_;$=-$_[0]?-$=:"$=.1"}

Edit:

  • $=.".1"disingkat menjadi "$=.1"(terima kasih ardnew).

Matematika:

Matematika

Tidak Disatukan:

# script.pl
sub f {
  ($=) = @_;   # short for $= = int($_[0]); 
               # "int" is implicit in assignments to $=;
               # ($=) can be prepended by "local" to get
               # the function free of side effects.

  $= - $_[0] ? # short for $= != $_[0], check if input is integer
    -$=        # input is not an integer  
  : $= . ".1"  # input is integer
}  

# Testing
chomp;
$_ = sprintf "f(f($_)) = f(%s) = %s\n", f($_), f(f($_));

Contoh:

perl -p script.pl
7
f(f(7)) = f(7.1) = -7
2
f(f(2)) = f(2.1) = -2
0
f(f(0)) = f(0.1) = 0
-1
f(f(-1)) = f(-1.1) = 1
-10
f(f(-10)) = f(-10.1) = 10
-1.23
f(f(-1.23)) = f(1) = 1.1
3.4
f(f(3.4)) = f(-3) = -3.1
1.0
f(f(1.0)) = f(1.1) = -1
Heiko Oberdiek
sumber
solusi yang kuat - test case floating point yang Anda demo tidak diperlukan per spec (seharusnya menawarkan poin bonus untuk itu!). inilah algoritma Anda yang sama dengan beberapa pembersihan yang datang pada 22 karakter:sub f{yzxzzc?-$_:x.$_}
ardnew
1
@ardnew: Terima kasih. Tapi saya tidak setuju bahwa solusi Anda menggunakan algoritma yang sama. Algoritma sub f{yzxzzc?-$_:x.$_}ini tidak keadaan bebas, ia menggunakan sebuah negara melalui variabel $_. Karena itu, ftidak ada lagi fungsi (dalam arti matematika), karena nilai yang berbeda dimungkinkan untuk nilai input yang sama tergantung pada keadaan (cuaca $_mengandung xatau tidak). Algoritme saya tidak menggunakan status, informasi dikodekan dalam nilai output. Integer dikonversi ke bilangan real dengan menambahkan .1. Dan bilangan real dikonversi kembali ke bilangan bulat dengan tanda diaktifkan.
Heiko Oberdiek
menarik - tidak ada data keadaan digunakan dalam implementasi Anda karena penugasan awal dan bukan karena beberapa properti khusus $=?
ardnew
saya tidak menyadari saya juga gagal dengan kebutuhan saya sendiri (yang fdidefinisikan Q->Q) dengan xchar itu. juga $=.".1"dapat disingkat menjadi"$=.1"
ardnew
@ardnew: Properti khusus $=hanya membutuhkan nomor integer. Hal yang sama dapat dicapai dengan menggunakan variabel biasa: $a=int$_[0]. Tetapi biaya tiga byte tambahan karena fungsi int.
Heiko Oberdiek
2

Julia, 26

julia> f(n::Int)=n//1
f (generic function with 1 method)
julia> f(n)=int(-n)
f (generic function with 2 methods)
julia> f(f(4))
-4

Tidak super kompetitif, tetapi sangat Julian karena bergantung pada pengiriman ganda. Itu hanya membuat na Rasional jika itu sebuah Int, atau sebuah int dengan tanda minus jika itu hal lain. Orang mungkin keberatan bahwa ini adalah 2 fungsi, tetapi Julia menganggap ini sebagai satu fungsi dengan dua metode, dan itu setara dengan mendefinisikan satu fungsi dengan statemen if pada tipe n.

gggg
sumber
Bukan apa yang disebut ahli matematika fungsi: di Julia 3==3//1kembali truetetapi f(3//1)==f(3)kembali false.
Omar
2

Permen , 20 18 byte

Menggunakan 3 -> 4 -> -3 -> -4 -> 3 trik.

~A2%{|m}1A0>{+|-}.

Untuk memintanya gunakan tombol -i pada interpreter

Contoh invokasi ganda:

$ candy -i 7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 8
$ candy -i 8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -7
$ candy -i -7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -8
$ candy -i -8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 7

Bentuk panjang:

peekA
pushA
digit2
mod          # even/odd
if
else
  negate     # negate even numbers
endif
digit1
pushA
digit0
greater      # positive/negative
if
  add        # add two numbers from stack (original stack value, and delta)
else
  sub        # diff two numbers from stack (original stack value, and delta)
endif
retSub
Dale Johnson
sumber
2

Dyalog APL, 9 poin

×-⍨⊢ׯ1*⊢

Sumbernya berukuran 9 byte dan memenuhi syarat untuk bonus (yang tidak membantu sama sekali). Ini juga menggunakan rumus dari jawaban SO atas.

lirtosiast
sumber
1

Python: 32 byte (29 poin)

f: Z -> Z

f=lambda n:(n>0)-(n<0)-n*(-1)**n

Menggunakan metode Ben Reich.

agar-agar
sumber
Dalam Python 2, Anda bisa menggantinya (n>0)-(n<0)dengan cmp(n,0), untuk menyimpan beberapa byte. (Tetapi tidak dalam Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )
mathmandan
1

GTB , 22

@S;N,"--$x?N)→N~N#~-N&
Timtech
sumber
1

Java, 113 byte

Pendekatannya cukup sederhana. Itu berakhir lebih banyak byte daripada yang saya perkirakan, tetapi mungkin bisa diturunkan sedikit.

public class F{public static int f(int x){if(x<0)x+=-2147483647-++x;x+=1073741824;return x<0?-2147483647-++x:x;}

Ini pada dasarnya menciptakan 4 "area" berbeda x, memanfaatkan fakta bahwa Java dengan senang hati membiarkan variabel membungkus. Saya harus melakukan beberapa konversi rumit untuk angka negatif yang merupakan alasan utama ini berakhir lebih besar dari yang diperkirakan.

Berfungsi untuk semua x selain -2147483648.

FIQ
sumber
1

Urutan angka yang sama (3, 4, -3, -4, 3 ...) sebagai jawaban skrip golf, tetapi diimplementasikan dalam perl (42 karakter setelah spasi dilucuti)

sub f{($_[0]%2?1:-1)*$_[0]+($_[0]<0?-1:1)}

Lebih jelas:

sub f { ($_[0] % 2 ? $_[0] : -$_[0] ) + ( $_[0] < 0 ? -1 : 1 ) }

Atau bahkan lebih jelas:

sub f {
  my $n = shift;
  my $sign = $n >= 0 ? 1 : -1;
  # note that in perl $n % 2 is the same as int($n) % 2
  if( $n % 2 ) {
    # odd: add one to magnitude
    return $n + $sign
  } else {
    # even: subtract one from magnitude then invert
    return -($n - $sign)
  }
}

Keluaran:

ski@anito:~/mysrc/.../acme$ echo 3 | perl -e 'sub f{($_[0]%2?1:-1)*$_[0] + ($_[0]<0?-1:1)}; my $x = <>; for(0..10) { print "$_: $x\n"; $x = f($x); }'
0: 3
1: 4
2: -3
3: -4
4: 3
5: 4
6: -3
7: -4
8: 3
9: 4
10: -3
skibrianski
sumber
Di atas juga berfungsi untuk non-integer: ski @ anito: ~ / mysrc /.../ acme $ echo 1.1234 | perl -e 'sub f {($ _ [0]% 2? 1: -1) * $ _ [0] + ($ _ [0] <0? -1: 1)}; $ x = <> saya; untuk (0..4) {print "$ _: $ x \ n"; $ x = f ($ x); } '0: 1.1234 1: 2.1234 2: -1.1234 3: -2.1234 4: 1.1234
skibrianski
1

Sed, 25 byte.

|sed s/0+/0-/|sed s/^/0+/

Pemakaian:

$ echo 1.23 |sed s/0+/0-/|sed s/^/0+/
0+1.23
$ echo 0+1.23 |sed s/0+/0-/|sed s/^/0+/
0+0-1.23
Ken A
sumber
1

Matlab, 26 karakter

f=@(n) (n<0)-(n<0)-n*(-1)^n
bla
sumber
2
Ini bukan jawaban yang valid, karena domain dan kode fungsi tidak boleh rumit.
Wrzlprmft
oh, maaf ... saya baru saja membaca judulnya dan tidak terlalu berhati-hati ... Mari kita lihat apakah saya bisa mengedit ini agak
bla
1

C ++ - 63 55.8

Begini tampilannya kode:

int f(int n){return (n&45056?n^45056:n|45056)*(n&45056?-1:1);}

Itu tidak bekerja pada bilangan bulat yang byte keempatnya sama dengan 0xB karena menggunakan nilai itu untuk melacak lintasan. Jika tidak bekerja pada anggota Z, termasuk nol.

Darkgamma
sumber
dapatkah kamu menjelaskan yang ini pada inspeksi pertama sepertinya Anda menjaga konter panggilan fdengan variabel statis. tapi lalu apa gunanya sqrt?
ardnew
Sepertinya saya salah paham soal itu; berpikir bahwa variabel statis baik-baik saja karena C ++ adalah bahasa berorientasi stack, tapi saya akan memperbaiki kodenya. Kalau tidak, saya tidak tahu mengapa saya perlu sqrtkarena dibulatkan pula dengan tipe casting. Saya akan refactor sehingga berfungsi tanpa variabel statis.
Darkgamma
Saya tidak tahu dari mana Anda mendapatkannya 55.8, tetapi kode Anda saat ini adalah 62 byte. Sunting: Sudahlah, saya tidak membaca pertanyaan dengan benar.
nyuszika7h
Pembatasan bahwa byte keempat tidak dapat sama dengan 0xB sayangnya membuat ini bukan jawaban yang valid untuk tantangan, yang mengharuskannya bekerja pada (setidaknya) semua bilangan bulat.
pppery
1

Diperbarui dengan fungsi yang disediakan oleh Synthetica (jelas orang yang seharusnya mendapatkan kredit untuk ini sekarang)

Bahasa: Python

Jumlah karakter: 41 termasuk spasi

f=lambda x:-float(x) if str(x)==x else`x`
Tupai Suci
sumber
Harap berikan juga nama bahasa yang Anda gunakan dan sediakan juga jumlah karakter.
ProgramFOX
Saya suka bagaimana ini juga bekerja dengan non-integer. Sudah selesai dilakukan dengan baik. :)
cjfaure
f=lambda x:-float(x) if str(x)==x else`x`cukup sedikit lebih pendek: 41 termasuk spasi
ɐɔıʇǝɥʇuʎs
Terima kasih Synthetica, saya bahkan tidak tahu tentang trik backticks! : D
HolySquirrel
Pada integer fmengembalikan sebuah string; spesifikasi mengatakan itu harus mengembalikan bilangan rasional.
Omar
1

Prolog, 36 byte

Kode:

X*Y:-X//1=:=X,Y is 0.5+X;Y is 0.5-X.

Dijelaskan:

Dyadic predicate which converts integers to floats and floats back to negated integers.

Contoh:

10*X.
X = 10.5

10*Y,Y*X.
X = -10,
Y = 10.5
Emigna
sumber
1

Javascript ES6, 27 26 byte

a=>a%1?-Math.floor(a):a+.2
SuperJedi224
sumber
1

Mouse-2002 , 21 19 12 byte

$A1%[1%_|1%]

Mendefinisikan suatu fungsi A; sebut seperti #A,#A,?;;(yang akan menunggu pengguna memasukkan nomor apa pun). Atau, sebut saja seperti di #A,#A,n;;mana nnomor apa pun.

kucing
sumber
1

Julia, 21

f(x)=(1-2(1>x>-1))/2x

Kemudian

julia> f(f(12//1))
-12//1

p // q adalah notasi literal bilangan rasional dari julia.

mschauer
sumber