關於一座100層高的建築物和兩個玻璃球,有一種流行的puzzle。我看到了解決方案,現在我想知道我是否可以通過編程的方式解決難題。如何以編程方式解決2玻璃球難題?
微不足道的編程解決方案是一個完整的搜索(我相信我可以使用回溯代碼)。有沒有更好的編程解決方案?我可以使用動態編程來解決這個難題嗎?
關於一座100層高的建築物和兩個玻璃球,有一種流行的puzzle。我看到了解決方案,現在我想知道我是否可以通過編程的方式解決難題。如何以編程方式解決2玻璃球難題?
微不足道的編程解決方案是一個完整的搜索(我相信我可以使用回溯代碼)。有沒有更好的編程解決方案?我可以使用動態編程來解決這個難題嗎?
這與卵滴拼圖類似。我會給你在動態編程的基本策略。將此與您的問題緊密聯繫起來。
# include <stdio.h>
# include <limits.h>
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
/* A 2D table where entery eggFloor[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
int eggFloor[n+1][k+1];
int res;
int i, j, x;
// We need one trial for one floor and0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i][1] = 1;
eggFloor[i][0] = 0;
}
// We always need j trials for one egg and j floors.
for (j = 1; j <= k; j++)
eggFloor[1][j] = j;
// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
eggFloor[i][j] = INT_MAX;
for (x = 1; x <= j; x++)
{
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
// eggFloor[n][k] holds the result
return eggFloor[n][k];
}
/* Driver program to test to pront printDups*/
int main()
{
int n = 2, k = 36;
printf ("\nMinimum number of trials in worst case with %d eggs and %d floors is %d \n", n, k, eggDrop(n, k));
return 0;
}
輸出: 在最壞的情況下試驗的最小數量與2個雞蛋和36層爲8
沒有冒犯,但這不是最好的解決方案。最簡單的情況是直到雞蛋休息時跳過N的sqrt。一旦雞蛋破碎,用N的sqrt備份併線性搜索。 N的時間複雜度sqrt並且沒有表格。這很簡單。 – Michael
我很抱歉,但以前的答案只是不能妥善處理這個問題。最好的時間是N的sqrt。有人會試圖用logn來反駁這一點,但我很抱歉,其實並非如此。
// my prentend breaking function
function itBreaks(level) {
return level > 36;
}
function search(maxLevel) {
var sqrtN = Math.floor(Math.sqrt(maxLevel));
var i = 0;
for (;i < maxLevel; i += sqrtN) {
if (itBreaks(i)) {
break;
}
}
for (i -= sqrtN; i < maxLevel; i++) {
if (itBreaks(i)) {
return i - 1;
}
}
}
你有沒有試過,或者你只是想讓我們做到這一點? ;) – annonymously
您可以將您的問題標記爲**作業** – Arung
http://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle – jgroenen