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.
Jawaban:
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:k - 1
lantai untuk memeriksa (semua di bawahk
) danm - 1
kucing (a[k - 1][m - 1]
).n - k
lantai yang tersisa (semua lantai di atask
) dan masihm
kucing.max
.+ 1
berasal dari fakta bahwa kami baru saja menggunakan satu upaya (terlepas dari apakah kucing telah selamat atau tidak).min(f(k)) : for k in 1..n
.Ini setuju dengan hasil Google dari tautan Gaurav Saxena untuk (100, 2).
Anda dapat dengan mudah menemukan strategi (cara melempar kucing pertama), jika Anda menyimpan yang terbaik
k
di 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 .
sumber
+ 1
harus di luarmin()
? Seperti yang Anda katakan sendiri, apakah upaya itu berhasil atau tidak, itu masih merupakan upaya.+1
luarmin
. Atau memindahkannya ke dalammax
:)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.
sumber
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)
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
sumber
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.
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
sumber
O(k*n**(1/k))
untuk kasus terburuk? Karena dalam kasus terburuk saya harus melalui waktu yangn**(1/k)
tepatk
.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.
sumber
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:
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:
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).
sumber
sumber
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.
sumber
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.
sumber