Pertanyaan Merancang fungsi f (f (n)) == -n [tertutup]


Sebuah pertanyaan yang saya dapatkan pada wawancara terakhir saya:

Rancang suatu fungsi f, seperti yang:

f(f(n)) == -n

Dimana n adalah 32 bit menandatangani bilangan bulat; Anda tidak dapat menggunakan aritmatika angka yang rumit.

Jika Anda tidak dapat mendesain fungsi semacam itu untuk seluruh rentang angka, rancanglah untuk rentang terbesar yang mungkin.

Ada ide?


836


asal


Jawaban:


Bagaimana tentang:

f (n) = tanda (n) - (-1)n * n

Dengan Python:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python secara otomatis mempromosikan bilangan bulat ke panjang semau yang sewenang-wenang. Dalam bahasa lain, bilangan bulat positif terbesar akan melimpah, sehingga akan berfungsi untuk semua bilangan bulat kecuali yang satu itu.


Untuk membuatnya bekerja untuk bilangan real Anda harus mengganti n di (-1)n dengan { ceiling(n) if n>0; floor(n) if n<0 }.

Dalam C # (bekerja untuk setiap ganda, kecuali dalam situasi meluap):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

374



Anda tidak mengatakan jenis bahasa apa yang mereka harapkan ... Berikut adalah solusi statis (Haskell). Ini pada dasarnya mengutak-atik 2 bit paling signifikan:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

Ini jauh lebih mudah dalam bahasa dinamis (Python). Cukup periksa apakah argumennya adalah angka X dan kembalikan lambda yang mengembalikan -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

439



Berikut adalah bukti mengapa fungsi seperti itu tidak dapat ada, untuk semua nomor, 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) )) = f (0) = x, yang berarti x = 0.)

Selanjutnya, untuk apa saja x dan y, seharusnya f(x) = y. Kami mau f(y) = -x kemudian. Dan f(f(y)) = -y => f(-x) = -y. Untuk meringkas: jika f(x) = y, kemudian f(-x) = -y, dan f(y) = -x, dan f(-y) = x.

Jadi, kita perlu membagi semua bilangan bulat kecuali 0 ke dalam set 4, tetapi kita memiliki bilangan ganjil seperti bilangan bulat; tidak hanya itu, jika kita menghapus integer yang tidak memiliki mitra positif, kita masih memiliki 2 (mod4) angka.

Jika kita menghapus 2 angka maksimal yang tersisa (berdasarkan nilai abs), kita bisa mendapatkan fungsi:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

Tentu saja pilihan lain, adalah tidak mematuhi 0, dan mendapatkan 2 nomor yang kami hapus sebagai bonus. (Tapi itu hanya konyol jika.)


280



Berkat kelebihan muatan di C ++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

146



Atau, Anda dapat menyalahgunakan preprocessor:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

135



Ini berlaku untuk semua angka negatif.

    f (n) = abs (n)

Karena ada satu lagi bilangan negatif daripada bilangan bulat positif untuk bilangan bulat kompos, f(n) = abs(n) berlaku untuk satu kasus lebih dari f(n) = n > 0 ? -n : n solusi yang sama seperti f(n) = -abs(n). Sampai jumpa oleh ...: D

MEMPERBARUI

Tidak, itu tidak berlaku untuk satu kasus lebih karena saya hanya diakui oleh komentar litb ... abs(Int.Min) hanya akan meluap ...

Saya juga berpikir untuk menggunakan informasi mod 2, tetapi menyimpulkan, itu tidak berhasil ... sampai awal. Jika dilakukan dengan benar, itu akan bekerja untuk semua angka kecuali Int.Min karena ini akan meluap.

MEMPERBARUI

Saya bermain dengan itu untuk sementara waktu, mencari trik manipulasi sedikit yang bagus, tetapi saya tidak dapat menemukan satu baris yang bagus, sementara solusi mod 2 cocok dalam satu.

    f (n) = 2n (abs (n)% 2) - n + sgn (n)

Dalam C #, ini menjadi sebagai berikut:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Agar berhasil untuk semua nilai, Anda harus mengganti Math.Abs() dengan (n > 0) ? +n : -ndan termasuk perhitungan dalam unchecked blok. Maka Anda membalas dendam Int.Min dipetakan pada dirinya sendiri sebagai negasi yang tidak terkendali.

MEMPERBARUI

Terinspirasi oleh jawaban lain saya akan menjelaskan bagaimana fungsi berfungsi dan bagaimana membangun fungsi seperti itu.

Mari kita mulai dari awal sekali. Fungsi itu f berulang kali diterapkan ke nilai yang diberikan n menghasilkan urutan nilai.

    n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (f (n)))) => ...

Pertanyaan itu menuntut f(f(n)) = -n, yaitu dua aplikasi berurutan f meniadakan argumen. Dua aplikasi lebih lanjut dari f - empat total - meniadakan argumen lagi menghasilkan n lagi.

    n => f (n) => -n => f (f (f (n))) => n => f (n) => ...

Sekarang ada siklus panjang yang jelas. Mengganti x = f(n) dan mencatat bahwa persamaan yang diperoleh f(f(f(n))) = f(f(x)) = -x memegang, menghasilkan yang berikut ini.

    n => x => -n => -x => n => ...

Jadi kita mendapatkan siklus panjang empat dengan dua angka dan dua angka yang dinegasikan. Jika Anda membayangkan siklus sebagai persegi panjang, nilai yang dilewatkan terletak di sudut yang berlawanan.

Salah satu dari banyak solusi untuk membangun siklus tersebut adalah sebagai berikut mulai dari n.

 n => meniadakan dan mengurangi satu
-n - 1 = - (n + 1) => tambahkan satu
-n => meniadakan dan menambahkan satu
 n + 1 => kurangi satu
 n

Contoh konkret adalah siklus seperti itu +1 => -2 => -1 => +2 => +1. Kami hampir selesai. Memperhatikan bahwa siklus yang dibangun mengandung bilangan positif yang ganjil, penerus genapnya, dan kedua bilangan tersebut meniadakan, kita dapat dengan mudah mempartisi bilangan bulat ke banyak siklus seperti itu (2^32 adalah kelipatan empat) dan telah menemukan fungsi yang memenuhi persyaratan.

Tapi kami punya masalah dengan nol. Siklus harus mengandung 0 => x => 0 karena nol dinegasikan ke dirinya sendiri. Dan karena siklus sudah menyatakan 0 => x itu mengikuti 0 => x => 0 => x. Ini hanya sebuah siklus dengan panjang dua dan x berubah menjadi dirinya sendiri setelah dua aplikasi, tidak menjadi -x. Untungnya ada satu kasus yang memecahkan masalah. Jika X sama dengan nol kita mendapatkan satu siklus panjang yang hanya mengandung nol dan kita memecahkan masalah yang menyimpulkan bahwa nol adalah titik tetap f.

Selesai? Hampir. Kita punya 2^32 angka, nol adalah titik tetap meninggalkan 2^32 - 1 angka, dan kita harus mempartisi angka itu ke dalam siklus empat angka. Buruk itu 2^32 - 1 bukan kelipatan empat - akan tetap ada tiga angka tidak dalam satu 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 untuk +3. Kami selesai dengan nol. Kami memiliki satu siklus lengkap +1 => -2 => -1 => +2 => +1. Sekarang mari kita membangun siklus mulai dari +3.

    +3 => -4 => -3 => +4 => +3

Masalah yang muncul adalah itu +4 tidak dapat direpresentasikan sebagai 3 bit integer. Kami akan mendapatkan +4 dengan meniadakan -3 untuk +3 - apa yang masih valid 3 bit integer - tetapi kemudian menambahkan satu ke +3 (biner 011) hasil 100biner. Diartikan sebagai integer unsigned itu +4 tetapi kita harus menafsirkannya sebagai bilangan bulat yang ditandatangani -4. Jadi sebenarnya -4 untuk contoh ini atau Int.MinValue dalam kasus umum adalah titik tetap kedua dari negasi aritmatika integer - 0  dan Int.MinValue dipetakan ke themselve. Jadi siklusnya sebenarnya sebagai berikut.

    +3 => -4 => -3 => -4 => -3

Ini adalah siklus panjang dua dan tambahan +3 memasuki siklus melalui -4. Karena itu -4 dipetakan dengan benar ke sendiri setelah dua aplikasi fungsi, +3 dipetakan dengan benar -3 setelah dua aplikasi fungsi, tetapi -3 salah dipetakan dengan sendirinya setelah dua aplikasi fungsi.

Jadi kami membangun fungsi yang berfungsi untuk semua bilangan bulat tetapi satu. Bisakah kita melakukan lebih baik? Tidak, kita tidak bisa. Mengapa? Kita harus membangun siklus dengan panjang empat dan mampu menutupi seluruh rentang integer hingga empat nilai. Nilai yang tersisa adalah dua titik tetap 0 dan Int.MinValue yang harus dipetakan sendiri dan dua bilangan bulat acak x dan -x yang harus dipetakan satu sama lain oleh dua aplikasi fungsi.

Untuk memetakan x untuk -x dan sebaliknya mereka harus membentuk empat siklus dan mereka harus berada di sudut-sudut berlawanan dari siklus itu. Karena itu 0 dan Int.MinValue harus berada di sudut yang berlawanan juga. Ini akan memetakan dengan benar x dan -x tetapi menukar dua titik tetap 0 dan Int.MinValue setelah dua aplikasi fungsi dan meninggalkan kami dengan dua input yang gagal. Jadi tidak mungkin untuk membangun fungsi yang berfungsi untuk semua nilai, tetapi kita memiliki satu yang berfungsi untuk semua nilai kecuali satu dan ini adalah yang terbaik yang bisa kita capai.


103



Menggunakan bilangan kompleks, Anda dapat secara efektif membagi tugas meniadakan angka menjadi dua langkah:

  • kalikan n oleh saya, dan Anda mendapatkan n * i, yang n diputar 90 ° berlawanan arah jarum jam
  • kalikan lagi dengan saya, dan Anda mendapatkan -n

Yang hebat adalah Anda tidak memerlukan kode penanganan khusus. Hanya mengalikan dengan saya melakukan pekerjaan itu.

Tetapi Anda tidak diizinkan untuk menggunakan bilangan kompleks. Jadi Anda harus membuat aksis imajiner Anda sendiri, menggunakan bagian dari jangkauan data Anda. Karena Anda membutuhkan nilai imajiner (menengah) sebagai nilai awal, Anda hanya memiliki setengah rentang data.

Saya mencoba memvisualisasikan ini pada gambar berikut, dengan asumsi data 8-bit yang ditandatangani. Anda harus menskalakan ini untuk bilangan bulat 32-bit. Rentang yang diizinkan untuk awal n adalah -64 hingga +63. Inilah yang fungsi lakukan untuk positif n:

  • Jika n dalam 0..63 (rentang awal), panggilan fungsi menambahkan 64, memetakan n ke kisaran 64..127 (jarak menengah)
  • Jika n berada di 64..127 (jarak menengah), fungsi mengurangi n dari 64, memetakan n ke kisaran 0 ..- 63

Untuk n negatif, fungsi menggunakan rentang menengah -65 ..- 128.

alt text


96