Membuang kucing keluar dari jendela

150

Bayangkan Anda berada di gedung tinggi dengan kucing. Kucing bisa bertahan jatuh dari jendela lantai rendah, tetapi akan mati jika dilempar dari lantai atas. Bagaimana Anda bisa mengetahui penurunan terpanjang yang bisa ditanggung kucing, menggunakan upaya paling sedikit?

Tentunya, jika Anda hanya memiliki satu kucing, maka Anda hanya dapat mencari secara linear. Pertama, buang kucing dari lantai pertama. Jika bertahan, lemparkan dari yang kedua. Akhirnya, setelah terlempar dari lantai f, kucing akan mati. Anda kemudian tahu bahwa lantai f-1 adalah lantai aman maksimal.

Tetapi bagaimana jika Anda memiliki lebih dari satu kucing? Anda sekarang dapat mencoba semacam pencarian logaritmik. Katakanlah bangunannya memiliki 100 lantai dan Anda memiliki dua kucing yang identik. Jika Anda membuang kucing pertama keluar dari lantai 50 dan mati, maka Anda hanya perlu mencari 50 lantai secara linear. Anda dapat melakukan lebih baik jika Anda memilih lantai bawah untuk upaya pertama Anda. Katakanlah Anda memilih untuk mengatasi masalah 20 lantai sekaligus dan bahwa lantai fatal pertama adalah # 50. Jika demikian, kucing pertama Anda akan selamat dari lantai 20 dan 40 sebelum mati dari lantai 60. Anda hanya perlu memeriksa lantai 41 hingga 49 secara terpisah. Itu total 12 upaya, yang jauh lebih baik daripada 50 yang Anda perlukan seandainya Anda mencoba menggunakan eliminasi biner.

Secara umum, apa strategi terbaik dan kompleksitas kasus terburuk untuk bangunan bertingkat n dengan 2 kucing? Bagaimana dengan untuk lantai dan kucing?

Asumsikan bahwa semua kucing setara: mereka semua akan bertahan hidup atau mati karena jatuh dari jendela yang diberikan. Selain itu, setiap upaya independen: jika kucing selamat dari kejatuhan, ia sama sekali tidak terluka.

Ini bukan pekerjaan rumah, meskipun saya mungkin telah menyelesaikannya untuk tugas sekolah satu kali. Itu hanya masalah aneh yang muncul di kepala saya hari ini dan saya tidak ingat solusinya. Poin bonus jika ada yang tahu nama masalah ini atau algoritma solusi.

AndrewF
sumber
123
Saya keberatan dengan penggunaan kucing dengan cara yang dijelaskan. Bisakah kita mengubahnya menjadi anjing?
Thilo
53
Tidak sesederhana itu. Penelitian telah dilakukan (kucing tidak sengaja jatuh dari gedung pencakar langit, tidak dilempar). Ada kisaran tertentu di mana mereka mati, dan kisaran *** lebih tinggi dari *** ini di mana mereka selamat. Sesuatu tentang bagaimana mereka menegangkan tubuh mereka.
Andrew Shepherd
5
Saya pernah membaca bahwa 15 kaki atau lebih, kucing memiliki peluang lebih besar untuk bertahan hidup. Pertanyaan ini akan lebih cocok jika kita menjatuhkan mantan pacar dan / atau istri yang mengomel.
Anthony Forloney
34
Anda tahu, jika Anda mulai dengan dua kucing, Anda DAPAT hanya menunggu beberapa bulan dan kemudian menjalankan pencarian biner. Atau tunggu beberapa bulan setelah itu dan lakukan "pencarian simultan," di mana Anda mendapatkan pembantu untuk membuang kucing dari setiap lantai secara bersamaan - jumlah kucing yang bertahan dalam kasus itu adalah jumlah lantai tertinggi yang bisa Anda lemparkan, tentu saja .
mjfgates
10
Dengan kelinci, ubah "bulan" menjadi "minggu."
mjfgates

Jawaban:

70

Anda dapat dengan mudah menulis DP kecil (pemrograman dinamis) untuk kasus umum n lantai dan kucing.

Rumus utama a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n,, harus jelas:

  • Jika kucing pertama dilempar dari lantai k-th dan mati, sekarang kita memiliki k - 1lantai untuk memeriksa (semua di bawah k) dan m - 1kucing ( a[k - 1][m - 1]).
  • Jika kucing bertahan, ada n - klantai yang tersisa (semua lantai di atas k) dan masih mkucing.
  • Kasus terburuk dari dua harus dipilih, karenanya max.
  • + 1 berasal dari fakta bahwa kami baru saja menggunakan satu upaya (terlepas dari apakah kucing telah selamat atau tidak).
  • Kami mencoba setiap lantai yang memungkinkan untuk menemukan hasil terbaik min(f(k)) : for k in 1..n.

Ini setuju dengan hasil Google dari tautan Gaurav Saxena untuk (100, 2).

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

Anda dapat dengan mudah menemukan strategi (cara melempar kucing pertama), jika Anda menyimpan yang terbaik kdi array lain.

Ada juga solusi yang lebih cepat, tidak melibatkan perhitungan O (n ^ 3), tapi saya sudah agak mengantuk.

sunting
Oh yeah, saya ingat di mana saya melihat masalah ini sebelumnya .

Nikita Rybak
sumber
Hmm, bukankah + 1harus di luar min()? Seperti yang Anda katakan sendiri, apakah upaya itu berhasil atau tidak, itu masih merupakan upaya.
j_random_hacker
@j_random_hacker Apakah ini mengubah apa pun? Pindah ke +1luar min. Atau memindahkannya ke dalam max:)
Nikita Rybak
@Nikita: Maaf saya entah bagaimana salah membaca apa yang Anda tulis - apa yang Anda miliki benar menurut saya! +1.
j_random_hacker
Perhatikan bahwa ini identik dengan "Masalah Tetesan Telur" Google Code Jam. Solusi O (n ^ 3) di bawah ini tidak cukup baik, karena set masalah besar menggunakan N = 2000000000. code.google.com/codejam/contest/dashboard?c=32003#s=p2
ripper234
1
Lihat pertanyaan baru ini untuk algoritma O (n). Jawaban teratas untuk Google Code Jam adalah O (n), tetapi saya belum memahaminya. stackoverflow.com/questions/4699067/…
ripper234
92

Menurut episode baru-baru ini dari Radiolab (tentang "Jatuh") , seekor kucing mencapai kecepatan terminal pada lantai 9. Setelah itu, ia rileks dan kecil kemungkinannya untuk terluka. Ada kucing yang sama sekali tidak terluka setelah jatuh dari atas tanggal 30. Lantai paling berisiko adalah lantai 5 hingga 9.

Thilo
sumber
16
Sebagai kucing, saya ingin menunjukkan bahwa penelitian ini didasarkan pada laporan rumah sakit hewan setelah insiden defenestrasi. Tidak ada kucing tambahan yang terluka atau tidak nyaman dalam pertanyaan ini.
Thilo
16
Bukan jawaban, hanya beberapa konteks tambahan dari domain bisnis.
Thilo
19
Ini adalah jawaban yang layak untuk dijawab.
Mark Ransom
2
Ini hanya menunjukkan bagaimana ini bukan kasus live = 1, die = 0 sebagai hasilnya, tetapi lebih banyak dari live = 1.0, die = 0,0 dan semua yang ada di dalamnya adalah probabilitas. Itu juga kurva, bukan garis, yang perlu ditemukan.
tadman
73
Masalah dengan laporan itu adalah bias seleksi - tidak ada yang membawa kucing mati ke dokter hewan.
Niki Yoshiuchi
10

Bayangkan Anda berada di gedung tinggi dengan kucing. Kucing bisa bertahan jatuh dari jendela lantai rendah, tetapi akan mati jika dilempar dari lantai atas. Bagaimana Anda bisa mengetahui penurunan terpanjang yang bisa ditanggung kucing, menggunakan upaya paling sedikit?

Strategi terbaik untuk memecahkan masalah ini adalah menginvestigasi, menggunakan hukum fisika, probabilitas asumsi Anda menjadi benar.

Jika Anda melakukannya, Anda akan menyadari bahwa peluang kucing untuk bertahan hidup sebenarnya semakin tinggi jaraknya dengan tanah. Tentu saja, dengan asumsi Anda membuangnya dari gedung yang lebih tinggi, seperti menara petronas, dan bukan gunung yang lebih tinggi, seperti gunung everest.

Sunting:
Sebenarnya, Anda akan melihat distribusi unta yang belum selesai.
Pertama, kemungkinan kucing mati adalah rendah (ketinggian sangat rendah), kemudian semakin tinggi (ketinggian rendah), kemudian lebih rendah (ketinggian lebih tinggi), dan kemudian lebih tinggi (ketinggian sangat tinggi).

Grafik untuk probabilitas kucing mati sebagai fungsi dari ketinggian di atas tanah terlihat seperti ini:
(selesai pada 3, karena distribusi unta yang belum selesai)

teks alternatif

Pembaruan:
Kecepatan terminal kucing adalah 100 km / jam (60 mph) [= 27,7m / s = 25,4 yard / s].
Kecepatan terminal manusia adalah 210 km / jam (130 mph). [= 75m / s = 68,58 yard / s]

Sumber kecepatan terminal:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Kredit:
Goooooogle

Saya perlu memverifikasi nanti:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html


Stefan Steiger
sumber
2
Apakah ini benar? Tentunya begitu kecepatan terminal tercapai, kemungkinan tidak bisa berubah - dan saya mendapat kesan seekor kucing bisa bertahan dari penurunan kecepatan terminal.
ZoFreX
4
@ZoFreX: Tentu saja bisa, itu adalah kecepatan terminal tepat di bawah yang paling fatal. Di sisi lain, jatuhkan kucing dari, katakan seratus ribu mil ke atas, dan kucing lebih cenderung terbakar di atmosfer setelah meninggal karena kekosongan daripada jatuh dan hidup.
David Thornley
1
Apakah itu telinga kelinci di grafik itu?
ninjalj
1
@ZoFreX: Momentum sudut. Seekor kucing selalu mendarat di kakinya, karena momentum sudut karena desain tubuh kucing dan keterampilan belok kucing. Tapi itu masih berarti perlu waktu untuk berbelok. Semakin banyak waktu yang ada (==> semakin tinggi ketinggian), semakin besar kemungkinan kucing akan mendarat dengan kakinya (==> peluang untuk bertahan hidup meningkat secara dramatis, berlawanan dengan misalnya mendarat di kepala). Tapi Anda benar, probabilitasnya tetap sama setelah mencapai kecepatan terminal. Menurut saya, kemungkinan besar kucing bisa selamat dari kejatuhan kecepatan terminal, setidaknya milik saya melompat keluar jendela kamar mandi (sekitar 20 m), tanpa goresan.
Stefan Steiger
8

Saya pertama kali membaca masalah ini dalam Manual Desain Algoritma Steven Skiena (latihan 8.15). Ini mengikuti bab tentang pemrograman dinamis, tetapi Anda tidak perlu tahu pemrograman dinamis untuk membuktikan batasan yang tepat pada strategi . Pertama pernyataan masalah, lalu solusi di bawah ini.

Telur pecah ketika jatuh dari ketinggian yang cukup besar. Diberi bangunan berlantai n, harus ada lantai f sehingga telur jatuh dari lantai f, tetapi telur yang jatuh dari lantai f-1 bertahan hidup. (Jika telur pecah dari lantai mana pun, kita akan mengatakan f = 1. Jika telur bertahan dari lantai mana pun, kita akan mengatakan f = n +1).

Anda berusaha menemukan lantai kritis f. Satu-satunya operasi yang dapat Anda lakukan adalah menjatuhkan telur dari lantai dan melihat apa yang terjadi. Anda mulai dengan telur k, dan berusaha menjatuhkan telur sesering mungkin. Telur yang rusak tidak dapat digunakan kembali (telur utuh dapat). Biarkan E (k, n) menjadi jumlah minimum dari kotoran telur yang akan selalu mencukupi.

  1. Tunjukkan bahwa E (1, n) = n.
  2. Tunjukkan itu E(k,n) = Θ(n**(1/k)).
  3. Temukan pengulangan untuk E (k, n). Berapa waktu berjalan dari program dinamis untuk menemukan E (k, n)?

Hanya 1 butir telur

Menjatuhkan telur dari setiap lantai mulai dari lantai pertama akan menemukan lantai kritis dalam operasi (paling buruk).

Tidak ada algoritma yang lebih cepat. Kapan saja dalam algoritma apa pun, mari g lantai tertinggi dari mana telur terlihat tidak pecah. Algoritma harus menguji lantai g + 1 sebelum lantai yang lebih tinggi h> g + 1, jika telurnya pecah dari lantai h, ia tidak dapat membedakan antara f = g + 1 dan f = h.

2 telur

Pertama, mari kita perhatikan k = 2 kasus telur, ketika n = r ** 2 adalah kuadrat sempurna. Inilah strategi yang membutuhkan waktu O (sqrt (n)). Mulailah dengan menjatuhkan telur pertama secara bertahap di lantai. Ketika telur pertama pecah, katakanlah di lantai ar, kita tahu lantai kritis f harus (a-1)r < f <= ar. Kami kemudian menjatuhkan telur kedua dari setiap lantai mulai dari (a-1)r. Ketika telur kedua pecah, kami telah menemukan lantai kritis. Kami paling banyak menjatuhkan setiap telur, jadi algoritma ini mengambil operasi 2r yang paling buruk, yaitu Θ (sqrt (n)).

Ketika n bukan kuadrat sempurna, ambil r = ceil(sqrt(n)) ∈ Θ(sqrt(n)). Algoritma tetap Θ (sqrt (n)).

Bukti bahwa algoritma apa pun membutuhkan setidaknya waktu sqrt (n). Misalkan ada algoritma yang lebih cepat. Pertimbangkan urutan lantai dari mana ia menjatuhkan telur pertama (asalkan tidak pecah). Karena turun kurang dari sqrt (n), harus ada interval setidaknya n / sqrt (n) yang merupakan sqrt (n). Ketika f berada dalam interval ini, algoritma harus menyelidikinya dengan telur kedua, dan itu harus dilakukan lantai-demi-lantai mengingat case 1-egg. KONTRADIKSI.

k telur

Algoritma yang disajikan untuk 2 telur dapat dengan mudah diperluas ke k telur. Jatuhkan setiap telur dengan interval konstan, yang harus diambil sebagai kekuatan akar ke-k dari n. Misalnya, untuk n = 1000 dan k = 3, cari interval 100 lantai dengan telur pertama, 10 dengan telur kedua, dan 1 dengan telur terakhir.

Demikian pula, kita dapat membuktikan bahwa tidak ada algoritma yang lebih cepat Θ(n**(1/k))dengan menginduksi dari bukti k = 2.

Solusi tepat

Kami menyimpulkan pengulangan dengan mengoptimalkan tempat menjatuhkan telur pertama (lantai g), dengan asumsi kami tahu solusi optimal untuk parameter yang lebih kecil. Jika telur pecah, kita memiliki lantai g-1 di bawah ini untuk dijelajahi dengan telur k-1. Jika telurnya bertahan, kita punya lantai di atas untuk dijelajahi dengan telur k. Iblis memilih yang terburuk untuk kita. Jadi untuk k> 1 perulangan

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n
Kolonel Panic
sumber
Jika saya punya k telur, mengapa bukan runtime O(k*n**(1/k))untuk kasus terburuk? Karena dalam kasus terburuk saya harus melalui waktu yang n**(1/k) tepat k.
Rakete1111
2

Bukankah ini menganggap Anda menggunakan "The Same Cat"?

Anda dapat mendekatinya secara matematis, tetapi itulah hal yang menyenangkan tentang matematika ... dengan asumsi yang tepat, 0 dapat sama dengan 1 (untuk nilai besar 0).

Dari sudut pandang praktis, Anda bisa mendapatkan 'Kucing Serupa ", tetapi Anda tidak bisa mendapatkan" Kucing yang Sama ".

Anda dapat mencoba menentukan jawabannya secara empiris, tetapi saya akan berpikir bahwa akan ada perbedaan statistik yang cukup sehingga jawabannya tidak akan bermakna secara statistik.

Anda bisa mencoba MENGGUNAKAN "Kucing yang Sama", tetapi itu tidak akan berhasil, karena, setelah tetes pertama, itu tidak lagi kucing yang sama. (Demikian pula untuk, onecan tidak pernah melangkah ke sungai yang sama dua kali)

Atau, Anda bisa mengumpulkan kesehatan kucing, mengambil sampel dengan interval sangat dekat, dan menemukan ketinggian tempat kucing "sebagian besar hidup" (berlawanan dengan "sebagian besar mati" dari "The Princess Bride"). Kucing akan bertahan hidup, rata-rata (hingga interval terakhir).

Saya pikir saya telah menyimpang dari niat awal, tetapi jika Anda memilih rute empiris, saya memilih untuk memulai setinggi mungkin dan terus menurunkan kucing karena ketinggian menurun hingga mereka bertahan secara statistik. Dan kemudian tes ulang pada kucing yang masih hidup untuk memastikan.

Marc
sumber
0

Saya mengambil metode yang sedikit berbeda untuk menghasilkan solusi.

Saya mulai dengan bekerja keluar lantai maksimal yang bisa ditutupi menggunakan x kucing dan y tebakan menggunakan metode berikut.

Mulailah dengan 1 lantai dan terus meningkatkan jumlah tebakan sambil melacak lantai, yang tebak mereka diperiksa dan berapa banyak kucing yang tersisa untuk setiap lantai.
Ulangi ini hingga y kali.

Kode ini sangat tidak efisien untuk menghitung jawaban yang diberikan tetapi tetap berguna untuk sejumlah kecil kucing / lantai.

Kode python:

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

Untuk 2 kucing, lantai maksimum yang dapat diidentifikasi dalam x tebakan adalah:
1, 3, 6, 10, 15, 21, 28 ...

Untuk 3 kucing:
1, 3, 7, 14, 25, 41, 63 ...

Untuk 4 kucing:
1, 3, 7, 15, 30, 56, 98 ...

Setelah penelitian yang luas (sebagian besar melibatkan urutan nomor pengetikan ke dalam OEIS ) saya perhatikan bahwa lantai maksimum untuk x mengikuti pola kombinasi satu sama lain .

Untuk 2 kucing:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Untuk 3 kucing:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

Untuk 4 kucing:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)

Dari sini saya mengambil pendekatan mudah penambahan sederhana sampai saya melewati jumlah lantai yang diperlukan.

Kode python:

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

Ini memberikan solusi yang benar untuk (100, 2) = 14.
Bagi siapa pun yang ingin memeriksa sesuatu yang kurang sepele, itu memberi (1 000 000, 5) = 43.

Ini berjalan di O (n) di mana n adalah jawaban untuk masalah (semakin banyak kucing semakin baik).
Namun saya yakin seseorang dengan tingkat matematika yang lebih tinggi dapat menyederhanakan rumus piecewise untuk menghitung dalam O (1).

threenplusone
sumber
0
O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 
tldr
sumber
-1

Saya tidak dapat membaca google blogspot tentang ini (terima kasih untuk karya blogwall) tapi saya tidak berpikir pencarian gaya biner lurus akan lebih baik. Alasannya adalah bahwa pencarian biner didasarkan pada gagasan bahwa jawaban yang Anda cari memiliki peluang yang sama untuk berada pada indeks indeks mana pun dalam daftar. Namun dalam hal ini itu tidak benar. Dalam hal ini jawabannya akan memiliki kemungkinan lebih tinggi untuk lebih dekat ke salah satu ujung rentang daripada yang lain. Saya tidak tahu bagaimana memasukkannya ke dalam pencarian, tetapi ini pemikiran yang menarik.

drekka
sumber
1
Saya pikir pertanyaannya adalah meminta kasus terburuk terbaik, sehingga distribusinya tidak relevan selama setiap lantai mungkin.
Steve Jessop
-1

semua ini pembicaraan gila tentang kucing..dan itu hanya menebak jumlah masalah dengan tebakan minimum (jumlah kucing). seharusnya tidak ada kebutuhan untuk secara artifisial (dan salah) mendefinisikan infinity sebagai bagian dari solusi. variabel seharusnya dinamai batas atas atau maks-coba atau semacamnya. definisi masalah (masalah kucing) memiliki beberapa masalah serius, dengan orang-orang menanggapi potensi kekejaman terhadap hewan dan juga banyak segi dari masalah yang ditimbulkan dalam kehidupan nyata, misalnya hambatan udara, gravitasi adalah akselerasi, dan parameter kehidupan nyata lainnya seperti itu masalah. jadi mungkin itu seharusnya ditanyakan dengan cara yang sama sekali berbeda.

chris
sumber
FWIW itu mungkin masalah kehidupan nyata yang disamarkan. Misalkan Anda memiliki tes otomatis yang gagal pada versi 1234 tetapi bekerja pada versi 42. Kucing mati pada 1234 tetapi hidup pada versi 42. Revisi apa yang membunuhnya? Jika memperbarui mis. Dari 42 menjadi 43 cepat dan mudah tetapi memeriksa dan membangun kembali versi baru itu sulit, ini mulai terlihat seperti masalah kucing.
mcdowella