一摞烙餅

博客分類：

• 編程

1.有一些服務員會把上面的一摞餅子放在自己頭頂上（放心，他們都戴著潔白的帽子），然后再處理其他餅子，在這個條件下，我們的算法能有什么改進？
Java代碼 ?

int[]?cakeArray; ??

CPrefixSorting?sorting;? ??

for(int?i=0;i<cakeArray.length;i++)?{ ??

????找出cakeArray[0:i]中的最大者cakeArray[i_max]; ??

????找出cakeArray[i+1:cakeArray.length-1]中的最小者cakeArray[i_min]; ??

????if(cakeArray[i_max]<=cakeArray[i_min]){ ??

????????sorting.run(cakeArray,i); ??

????????sorting.run(&cakeArray[i+1],cakeArray.length-i); ??

????} ??

}??

int[] cakeArray; CPrefixSorting sorting; for(int i=0;i<cakeArray.length;i++) {找出cakeArray[0:i]中的最大者cakeArray[i_max];找出cakeArray[i+1:cakeArray.length-1]中的最小者cakeArray[i_min];if(cakeArray[i_max]<=cakeArray[i_min]){sorting.run(cakeArray,i);sorting.run(&cakeArray[i+1],cakeArray.length-i);} }
2.事實上，飯店的師傅經常把烙餅烤得一面非常焦，另一面則是金黃色。這時，服務員還得考慮讓烙餅大小有序，并且金黃色的一面都要向上。這樣要怎么翻呢？
A? 先按照“烙餅排序實現”對烙餅進行大小排序
B? 然后對有金黃色不朝上的烙餅做如下操作，以cakeArray[k]為例
翻轉cakeArray[0:k],將cakeArray[k]翻到頂層，翻轉cakeArray[k],然后將cakeArray[0:k]翻轉，將cake[k]翻回原來位置

3.有一次師傅烙了三個餅，一個兩面都焦了，一個兩面都是金黃色，一個一面是焦的，一面是金黃色，我把它們摞一起，只能看到最上面一個餅的上面，發現是焦的，問最上面這個餅的另一面是焦的概率是多少？
條件概率：雙焦面的烙餅在最上面的概率為1/3,單焦面烙餅在最上面的概率也為1/3，單焦面烙餅在最上面同時焦面朝上的概率為1/3 * 1/2 = 1/6，因此在最上表面為焦面的條件下，其對應的下表面也為焦面的概率為1/3 / (1/6 + 1/3) = 2/3

4.每次翻烙餅的時候，上面的若干個烙餅會被翻轉。如果我們希望在排序過程中，翻轉烙餅的總個數最少，結果會如何呢？
不以翻轉次數作為評價標準，而是以翻轉烙餅總個數作為評價標準。
A? 修改相應的LowerBound和UpBound函數，UpBound也采用同LowerBound一樣的參數列表
B?? 同時在Search(int step)中增加一個參數int tatalReverseCount，增加一個成員變量int m_nMaxReverseCount,
C?? 代碼m_nMaxSwap = UpBound(m_nCakeCnt);修改為m_nMaxReverseCount = UpBount(m_CakeArray,m_nCakeCnt);m_nMaxSwap = 2*m_nCakeCnt;
D?? 代碼if(step + nEstimate > m_nMaxSwap)修改為if(tatalReverseCount + nEstimate > m_nMaxReverseCount)
E?? 代碼m_nMaxSwap = step;下面增加一條語句m_nMaxReverseCount = tatalReverseCount;

轉載于:https://www.cnblogs.com/avenxia/archive/2012/09/13/2683094.html

總結

以上是生活随笔為你收集整理的烙饼啊烙饼{转自ITEO的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。