一摞烙饼
博客分类：编程 1.有一些服务员会把上面的一摞饼子放在自己头顶上（放心，他们都戴着洁白的帽子），然后再处理其他饼子，在这个条件下，我们的算法能有什么改进？Java代码 int[]cakeArray; CPrefixSortingsorting; for(inti=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;
如果觉得《烙饼啊烙饼{转自ITEO》对你有帮助，请点赞、收藏，并留下你的观点哦！
