Sebuah pertanyaan yang saya dapatkan pada wawancara terakhir saya:
Desain suatu fungsi
f
, sedemikian rupa sehingga:f(f(n)) == -n
Di mana integer bertanda
n
32 bit ; Anda tidak dapat menggunakan aritmatika bilangan kompleks.Jika Anda tidak dapat mendesain fungsi seperti itu untuk seluruh jajaran angka, rancanglah untuk rentang semaksimal mungkin.
Ada ide?
Jawaban:
Bagaimana tentang:
Dengan Python:
Python secara otomatis mempromosikan bilangan bulat ke panjang sewenang-wenang. Dalam bahasa lain, bilangan bulat positif terbesar akan meluap, sehingga bilangan bulat akan berfungsi untuk semua bilangan bulat kecuali yang itu.
Untuk membuatnya berfungsi untuk bilangan real, Anda harus mengganti n in (-1) n dengan
{ ceiling(n) if n>0; floor(n) if n<0 }
.Di C # (berfungsi untuk sembarang ganda, kecuali dalam situasi luapan):
sumber
Anda tidak mengatakan bahasa apa yang mereka harapkan ... Ini solusi statis (Haskell). Ini pada dasarnya mengacaukan 2 bit paling signifikan:
Jauh lebih mudah dalam bahasa dinamis (Python). Periksa apakah argumennya adalah angka X dan kembalikan lambda yang mengembalikan -X:
sumber
class C a b | a->b where { f :: a->b }
;instance C Int (()->Int) where { f=const.negate }
;instance C (()->Int) Int where { f=($()) }
.Berikut adalah bukti mengapa fungsi semacam itu tidak ada, untuk semua angka, jika tidak menggunakan informasi tambahan (kecuali 32 bit int):
Kita harus memiliki f (0) = 0. (Bukti: Misalkan f (0) = x. Kemudian f (x) = f (f (0)) = -0 = 0. Sekarang, -x = f (f (x (x) )) = f (0) = x, yang berarti bahwa x = 0.)
Selanjutnya, untuk apa pun
x
dany
, misalkanf(x) = y
. Kami menginginkannyaf(y) = -x
. Danf(f(y)) = -y => f(-x) = -y
. Untuk meringkas: jikaf(x) = y
, makaf(-x) = -y
, danf(y) = -x
, danf(-y) = x
.Jadi, kita perlu membagi semua bilangan bulat kecuali 0 ke dalam set 4, tetapi kami memiliki jumlah ganjil dari bilangan bulat tersebut; tidak hanya itu, jika kita menghapus bilangan bulat yang tidak memiliki pasangan positif, kita masih memiliki 2 (mod4) angka.
Jika kita menghapus 2 angka maksimal yang tersisa (berdasarkan nilai abs), kita bisa mendapatkan fungsinya:
Tentu saja pilihan lain, adalah tidak mematuhi 0, dan mendapatkan 2 angka yang kami hapus sebagai bonus. (Tapi itu konyol jika.)
sumber
n = -2147483648
(nilai minimum); Anda tidak dapatabs(n)
dalam hal itu, dan hasilnya akan tidak ditentukan (atau pengecualian).Berkat kelebihan muatan di C ++:
sumber
Atau, Anda dapat menyalahgunakan preprosesor:
sumber
Ini berlaku untuk semua angka negatif.
Karena ada satu angka lebih negatif daripada angka positif untuk dua integer komplemen,
f(n) = abs(n)
valid untuk satu kasus lebih darif(n) = n > 0 ? -n : n
solusi yang sama denganf(n) = -abs(n)
. Punya satu per satu ...: DMEMPERBARUI
Tidak, itu tidak berlaku untuk satu kasus lagi karena saya baru saja dikenali oleh komentar litb ...
abs(Int.Min)
hanya akan meluap ...Saya berpikir tentang menggunakan informasi mod 2 juga, tetapi menyimpulkan, itu tidak berfungsi ... untuk awal. Jika dilakukan dengan benar, ini akan berfungsi untuk semua angka kecuali
Int.Min
karena ini akan meluap.MEMPERBARUI
Saya bermain dengannya sebentar, mencari trik manipulasi bit yang bagus, tetapi saya tidak dapat menemukan satu-liner yang bagus, sedangkan solusi mod 2 cocok untuk satu.
Di C #, ini menjadi yang berikut:
Untuk membuatnya berfungsi untuk semua nilai, Anda harus mengganti
Math.Abs()
dengan(n > 0) ? +n : -n
dan memasukkan perhitungan dalam satuunchecked
blok. Kemudian Anda bahkanInt.Min
dipetakan ke dirinya sendiri seperti halnya negasi yang tidak terkendali.MEMPERBARUI
Terinspirasi oleh jawaban lain saya akan menjelaskan bagaimana fungsi bekerja dan bagaimana membangun fungsi seperti itu.
Mari kita mulai dari awal. Fungsi
f
ini berulang kali diterapkan pada nilai yang diberikann
menghasilkan urutan nilai.Pertanyaannya menuntut
f(f(n)) = -n
, yaitu dua aplikasi berturut-turutf
meniadakan argumen. Dua aplikasi lebih lanjut darif
- total empat - meniadakan argumen lagi menghasilkann
lagi.Sekarang ada siklus panjang empat yang jelas. Mengganti
x = f(n)
dan mencatat bahwa persamaan yang diperolehf(f(f(n))) = f(f(x)) = -x
berlaku, menghasilkan yang berikut.Jadi kita mendapatkan siklus panjang empat dengan dua angka dan dua angka dinegasikan. Jika Anda membayangkan siklus sebagai persegi panjang, nilai yang dinegasikan terletak di sudut yang berlawanan.
Salah satu solusi untuk membangun siklus seperti itu adalah yang berikut dimulai dari n.
Contoh konkret dari siklus semacam itu adalah
+1 => -2 => -1 => +2 => +1
. Kami hampir selesai. Memperhatikan bahwa siklus yang dikonstruksi mengandung bilangan positif ganjil, bahkan penggantinya, dan kedua bilangan tersebut meniadakan, kita dapat dengan mudah mempartisi bilangan bulat menjadi banyak siklus semacam itu (2^32
merupakan kelipatan empat) dan telah menemukan fungsi yang memenuhi kondisi.Tetapi kami memiliki masalah dengan nol. Siklus harus mengandung
0 => x => 0
karena nol dinegasikan ke dirinya sendiri. Dan karena siklus menyatakan sudah0 => x
mengikuti0 => x => 0 => x
. Ini hanya siklus panjang dua danx
diubah menjadi dirinya sendiri setelah dua aplikasi, bukan menjadi-x
. Untungnya ada satu kasus yang menyelesaikan masalah. JikaX
sama dengan nol kita memperoleh siklus panjang yang hanya mengandung nol dan kita memecahkan masalah itu dengan menyimpulkan bahwa nol adalah titik tetapf
.Selesai? Hampir. Kami memiliki
2^32
angka, nol adalah angka tetap yang meninggalkan titik2^32 - 1
, dan kami harus mempartisi angka itu menjadi siklus empat angka. Buruk itu2^32 - 1
bukan kelipatan empat - akan tetap ada tiga angka tidak dalam siklus dengan panjang empat.Saya akan menjelaskan bagian yang tersisa dari solusi menggunakan set yang lebih kecil dari 3 bit yang ditandatangani mulai dari
-4
ke+3
. Kita selesai dengan nol. Kami memiliki satu siklus lengkap+1 => -2 => -1 => +2 => +1
. Sekarang mari kita buat siklus mulai dari+3
.Masalah yang muncul adalah yang
+4
tidak direpresentasikan sebagai integer 3 bit. Kami akan memperoleh+4
dengan meniadakan-3
ke+3
- apa yang masih merupakan integer 3 bit yang valid - tetapi kemudian menambahkan satu ke+3
(biner011
) menghasilkan100
biner. Ditafsirkan sebagai bilangan bulat yang tidak ditandatangani,+4
tetapi kita harus menafsirkannya sebagai bilangan bulat yang ditandatangani-4
. Jadi sebenarnya-4
untuk contoh ini atauInt.MinValue
dalam kasus umum adalah titik tetap kedua negasi aritmatika bilangan bulat -0
danInt.MinValue
dipetakan ke mereka sendiri. Jadi siklusnya sebenarnya sebagai berikut.Ini adalah siklus dengan panjang dua dan juga
+3
memasuki siklus melalui-4
. Karena-4
itu dipetakan dengan benar ke dirinya sendiri setelah dua aplikasi fungsi,+3
dipetakan dengan benar ke-3
setelah dua aplikasi fungsi, tetapi-3
dipetakan secara keliru ke dirinya sendiri setelah dua aplikasi fungsi.Jadi kami membangun fungsi yang bekerja untuk semua bilangan bulat kecuali satu. Bisakah kita berbuat lebih baik? Tidak, kita tidak bisa. Mengapa? Kita harus membuat siklus dengan panjang empat dan mampu mencakup seluruh rentang integer hingga empat nilai. Nilai yang tersisa adalah dua titik tetap
0
danInt.MinValue
yang harus dipetakan untuk diri mereka sendiri dan dua bilangan bulat sewenang-wenangx
dan-x
yang harus dipetakan satu sama lain oleh dua aplikasi fungsi.Untuk memetakan
x
ke-x
dan sebaliknya mereka harus membentuk empat siklus dan mereka harus berada di sudut yang berlawanan dari siklus itu. Karena itu0
danInt.MinValue
harus berada di sudut yang berlawanan juga. Ini akan memetakan dengan benarx
dan-x
tetapi menukar dua titik tetap0
danInt.MinValue
setelah dua aplikasi fungsi dan meninggalkan kita dengan dua input yang gagal. Jadi tidak mungkin untuk membangun fungsi yang bekerja untuk semua nilai, tetapi kami memiliki satu yang berfungsi untuk semua nilai kecuali satu dan ini adalah yang terbaik yang bisa kami capai.sumber
Menggunakan bilangan kompleks, Anda dapat secara efektif membagi tugas meniadakan angka menjadi dua langkah:
Yang hebat adalah Anda tidak memerlukan kode penanganan khusus. Hanya mengalikan dengan saya melakukan pekerjaan.
Tapi Anda tidak diizinkan menggunakan angka kompleks. Jadi Anda harus entah bagaimana membuat sumbu imajiner Anda sendiri, menggunakan bagian dari rentang data Anda. Karena Anda membutuhkan nilai imajiner (menengah) persis seperti nilai awal, Anda hanya memiliki separuh rentang data.
Saya mencoba memvisualisasikan ini pada gambar berikut, dengan asumsi data 8-bit yang ditandatangani. Anda harus skala ini untuk bilangan bulat 32-bit. Kisaran yang diizinkan untuk awal n adalah -64 hingga +63. Inilah yang fungsinya untuk n positif:
Untuk n negatif, fungsi ini menggunakan rentang menengah -65 ..- 128.
sumber
float
vsint
). 'Cincin elemen 4' yang dijelaskan oleh banyak jawaban mengharuskan 4 status, yang dapat direpresentasikan sebagai 2 dimensi masing-masing dengan 2 status. The masalah dengan jawaban ini adalah bahwa hal itu membutuhkan ruang pengolahan tambahan (hanya 'karya' untuk -64..63, namun kebutuhan -128..127 ruang) dan tidak secara eksplisit menyatakan rumus ditulis!Berfungsi kecuali int.MaxValue dan int.MinValue
sumber
0
ke0
dan-2147483648
ke-2147483648
karena kedua angka ini adalah titik tetap untuk operator negasix => -x
,. Untuk sisa angka, ikuti panah pada gambar di atas. Seperti yang jelas dari jawaban SurDin dan komentarnya, akan ada dua angka, dalam hal ini2147483647
dan-2147483647
tanpa pasangan yang tersisa untuk bertukar.Pertanyaannya tidak mengatakan apa-apa tentang apa jenis input dan nilai balik fungsi
f
harus (setidaknya bukan cara Anda mempresentasikannya) ...... Hanya saja ketika n adalah bilangan bulat 32-bit lalu
f(f(n)) = -n
Jadi, bagaimana dengan sesuatu seperti
Jika n adalah bilangan bulat 32-bit maka pernyataan itu
f(f(n)) == -n
akan benar.Jelas, pendekatan ini dapat diperluas untuk bekerja untuk rentang nomor yang lebih luas ...
sumber
untuk javascript (atau bahasa yang diketik secara dinamis lainnya) Anda dapat memiliki fungsi menerima int atau objek dan mengembalikan yang lain. yaitu
memberi
atau Anda dapat menggunakan overloading dalam bahasa yang sangat diketik meskipun itu bisa melanggar aturan yaitu
sumber
Bergantung pada platform Anda, beberapa bahasa memungkinkan Anda menjaga status dalam fungsi. VB.Net, misalnya:
IIRC, C ++ mengizinkan ini juga. Saya curiga mereka mencari solusi yang berbeda.
Gagasan lain adalah karena mereka tidak menentukan hasil dari panggilan pertama ke fungsi, Anda bisa menggunakan keanehan untuk mengontrol apakah akan membalikkan tanda:
Tambahkan satu ke besarnya semua angka genap, kurangi satu dari besarnya semua angka ganjil. Hasil dari dua panggilan memiliki besaran yang sama, tetapi satu panggilan di mana itu bahkan kita menukar tandanya. Ada beberapa kasus di mana ini tidak akan berhasil (-1, maks atau int min), tetapi ini bekerja jauh lebih baik daripada apa pun yang disarankan sejauh ini.
sumber
Memanfaatkan pengecualian JavaScript.
sumber
Untuk semua nilai 32-bit (dengan peringatan bahwa -0 adalah -2147483648)
Anda pada dasarnya perlu memasangkan setiap -x => x => -x loop dengan ay => -y => y loop. Jadi saya memasangkan sisi yang berlawanan
split
.mis. Untuk bilangan bulat 4 bit:
sumber
Versi C ++, mungkin sedikit menekuk aturan tetapi berfungsi untuk semua tipe numerik (float, ints, doubles) dan bahkan tipe kelas yang membebani minus unary:
sumber
x86 asm (gaya AT&T):
Kode diperiksa, semua bilangan bulat 32bit yang mungkin terlewati, kesalahan dengan -2147483647 (underflow).
sumber
Menggunakan global ... tapi begitu?
sumber
Solusi Perl ini berfungsi untuk bilangan bulat, pelampung, dan string .
Coba beberapa data uji.
Keluaran:
sumber
n
adalah string saya bisa membuat 548 menjadi "First_Time_548" dan kemudian waktu berikutnya menjalankan fungsi ... if (awalan == First_Time_ ") ganti" First_Time_ "dengan" - "Tidak ada yang pernah mengatakan f (x) harus bertipe sama.
sumber
Saya tidak benar-benar mencoba memberikan solusi untuk masalah itu sendiri, tetapi memiliki beberapa komentar, karena pertanyaan menyatakan masalah ini diajukan adalah bagian dari wawancara (pekerjaan?):
int.MinValue
keint.MaxValue
, dan untuk masing-masingn
dalam rentang panggilanf(f(n))
dan memeriksa hasilnya-n
), mengatakan saya kemudian akan menggunakan Test Driven Development untuk mendapatkan fungsi seperti itu.Oh, jawaban ini menganggap wawancara itu untuk posisi terkait pemrograman C #. Tentu saja akan menjadi jawaban yang konyol jika wawancara itu untuk posisi terkait matematika. ;-)
sumber
Saya akan Anda mengubah 2 bit paling signifikan.
Seperti yang Anda lihat, itu hanya tambahan, meninggalkan bit yang dibawa.
Bagaimana saya mendapat jawaban? Pikiran pertama saya hanyalah kebutuhan akan simetri. 4 putaran untuk kembali ke tempat saya mulai. Pada awalnya saya pikir, itu kode 2bits Gray. Lalu saya pikir sebenarnya biner standar sudah cukup.
sumber
Berikut adalah solusi yang terinspirasi oleh persyaratan atau klaim bahwa bilangan kompleks tidak dapat digunakan untuk menyelesaikan masalah ini.
Mengalikan dengan akar kuadrat dari -1 adalah sebuah ide, yang sepertinya gagal karena -1 tidak memiliki akar kuadrat di atas bilangan bulat. Tetapi bermain-main dengan program seperti Mathematica memberi misalnya persamaan
dan ini hampir sama baiknya dengan memiliki akar kuadrat dari -1. Hasil dari fungsi harus berupa bilangan bulat yang ditandatangani. Oleh karena itu saya akan menggunakan mod operasi modulo yang dimodifikasi (x, n) yang mengembalikan integer y kongruen ke x modulo n yang paling dekat dengan 0. Hanya sedikit bahasa pemrograman yang memiliki operasi modulo, tetapi dapat dengan mudah didefinisikan . Misalnya dalam python adalah:
Menggunakan persamaan di atas, masalah sekarang dapat diselesaikan sebagai
Ini memuaskan
f(f(x)) = -x
untuk semua bilangan bulat dalam jangkauan . Hasil dari juga dalam kisaran ini, tetapi tentu saja perhitungan akan membutuhkan bilangan bulat 64-bit.[-2
31
-2, 2
31
-2]
f(x)
sumber
C # untuk rentang 2 ^ 32 - 1 angka, semua nomor int32 kecuali (Int32.MinValue)
cetakan:
sumber
Pada dasarnya fungsi harus membagi rentang yang tersedia menjadi siklus ukuran 4, dengan -n di ujung siklus n. Namun, 0 harus menjadi bagian dari siklus ukuran 1, karena jika tidak
0->x->0->x != -x
. Karena 0 sendirian, harus ada 3 nilai lain dalam rentang kami (yang ukurannya merupakan kelipatan 4) tidak dalam siklus yang tepat dengan 4 elemen.Saya memilih nilai-nilai ekstra aneh ini menjadi
MIN_INT
,MAX_INT
, danMIN_INT+1
. Selanjutnya,MIN_INT+1
akan memetakan denganMAX_INT
benar, tetapi terjebak di sana dan tidak memetakan kembali. Saya pikir ini adalah kompromi terbaik, karena ia hanya memiliki properti bagus dari nilai-nilai ekstrem yang tidak berfungsi dengan benar. Juga, itu berarti itu akan bekerja untuk semua BigInts.sumber
Tidak ada yang mengatakan itu harus tanpa kewarganegaraan.
Curang, tapi tidak sebanyak contoh. Yang lebih jahat adalah dengan mengintip tumpukan untuk melihat apakah alamat pemanggil Anda adalah & f, tetapi ini akan menjadi lebih portabel (meskipun bukan utas aman ... versi utas aman akan menggunakan TLS). Yang lebih jahat:
Tentu saja, tak satu pun dari ini bekerja dengan baik untuk kasus MIN_INT32, tetapi ada sedikit yang berharga yang dapat Anda lakukan tentang hal itu kecuali Anda diizinkan untuk mengembalikan tipe yang lebih luas.
sumber
Saya bisa membayangkan menggunakan bit ke-31 sebagai bit imajiner ( i ) akan menjadi pendekatan yang akan mendukung setengah rentang total.
sumber
bekerja untuk n = [0 .. 2 ^ 31-1]
sumber
Masalahnya menyatakan "integer bertanda 32-bit" tetapi tidak menentukan apakah keduanya komplemen dua atau satu .
Jika Anda menggunakan komplemen satu maka semua nilai 2 ^ 32 terjadi dalam siklus dengan panjang empat - Anda tidak memerlukan kasing khusus untuk nol, dan Anda juga tidak memerlukan persyaratan.
Dalam C:
Ini bekerja dengan
Setelah dua lintasan kami memiliki bitwise kebalikan dari nilai aslinya. Yang dalam representasi satu komplemen sama dengan negasi.
Contoh:
sumber
: D
sumber
sumber
Saya ingin berbagi pandangan saya tentang masalah menarik ini sebagai ahli matematika. Saya pikir saya punya solusi paling efisien.
Jika saya ingat dengan benar, Anda meniadakan integer 32-bit yang ditandatangani dengan hanya membalik bit pertama. Misalnya, jika n = 1001 1101 1110 1011 1110 0000 1110 1010, maka -n = 0001 1101 1110 1011 1110 0000 1110 1010.
Jadi bagaimana kita mendefinisikan fungsi f yang mengambil bilangan bulat 32-bit yang ditandatangani dan mengembalikan bilangan bulat 32-bit lainnya dengan properti yang mengambil f dua kali sama dengan membalik bit pertama?
Biarkan saya ulangi pertanyaannya tanpa menyebutkan konsep aritmatika seperti bilangan bulat.
Bagaimana kita mendefinisikan fungsi f yang mengambil urutan nol dan yang panjang 32 dan mengembalikan urutan nol dan yang sama panjang, dengan properti yang mengambil f dua kali sama dengan membalik bit pertama?
Pengamatan: Jika Anda dapat menjawab pertanyaan di atas untuk kasing 32 bit, maka Anda juga dapat menjawab kasing 64 bit, kasing 100 bit, dll. Anda tinggal menerapkan f ke bit 32 pertama.
Sekarang jika Anda dapat menjawab pertanyaan untuk case 2 bit, Voila!
Dan ya ternyata mengubah 2 bit pertama sudah cukup.
Ini kode semu
Catatan: Langkah 2 dan langkah 3 bersama-sama dapat disingkat sebagai (a, b) -> (-b, a). Terlihat tidak asing? Itu akan mengingatkan Anda tentang rotasi 90 derajat pesawat dan perkalian dengan akar kuadrat dari -1.
Jika saya hanya menyajikan pseudo-code saja tanpa pembuka yang lama, itu akan terlihat seperti kelinci, saya ingin menjelaskan bagaimana saya mendapatkan solusinya.
sumber