一,问题:
星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:“我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢?”
你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢?(参考flyingherts的专栏)
二,分析:
n个烙饼经过翻转后的所有状态可组成一棵树。寻找翻转最少次数,相当于在树中搜索层次最低的某个节点。
由于每层的节点数呈几何数量级增长,在n较大时,使用广度优先遍历树,可能没有足够的内存来保存中间结果(考虑到每层的两个节点,可以通过旋转,移位等操作互相转换,也许每层的状态可以用一个函数来生成,这时可以采用广度优先方法),因而采用深度优先。但这棵树是无限深的,必须限定搜索的深度(即最少翻转次数的上限值),当深度达到该值时不再继续往下搜索。最少翻转次数,必然小等于任何一种翻转方案所需的翻转次数,因而只要构造出一种方案,取其翻转次数即可做为其初始值。最简单的翻转方案就是:对最大的未就位的烙饼,将其翻转,再找到最终结果中其所在的位置,翻转一次使其就位。因此,对编号在n-1和2之间的烙饼,最多翻转了2*(n-2)次,剩下0和1号烙饼最多翻转1次,因而最少翻转次数的上限值是:2*(n-2)+1=2*n-3(从网上可搜索到对该上限值最新研究结果:上限值为18/11*n),当然,最好还是直接计算出采用这种方案的翻转次数做为初始值。
三,减少遍历次数:
1 )减小“最少翻转次数上限值”的初始值,采用前面提到的翻转方案,取其翻转次数为初始值。对书中的例子{3,2,1,6,5,4,9,8,7,0},初始值可以取10。
2 ) 避免出现已处理过的状态一定会减少遍历吗?答案是否定的,深度优先遍历,必须遍历完一个子树,才能遍历下一个子树,如果一个解在某层比较靠后位置,若不允许处理已出现过的状态时,可能要经过很多次搜索,才能找到这个解,但允许处理已出现过的状态时,可能会很快找到这个解,并减小“最少翻转次数的上限值”,使更多的分支能被剪掉,反而能减少遍历的节点数。比如说,两个子树A、B,搜索子树A,100次后可得到一个对应翻转次数为20的解,搜索子树B,20次后可得到翻转次数为10的解,不允许处理已出现过的状态,就会花100次遍历完子树A后,才开始遍历B,但允许翻转回上一次状态,搜索会在A、B间交叉进行,就可能只要70次找到子树B的那个解(翻转次数为10+2=12),此时,翻转次数上限值比较小,可忽略更多不必要的搜索。以书中的{3,2,1,6,5,4,9,8,7,0}为例,按程序(1.3_pancake_1.cpp),不允许翻转回上次状态时需搜索195次,而允许翻转回上次状态时只要搜索116次。
3) 如果最后的几个烙饼已经就位,只须考虑前面的几个烙饼。对状态(0,1,3,4,2,5,6),编号为5和6的烙饼已经就位,只须考虑前5个烙饼,即状态(0,1,3,4,2)。如果一个最优解,从某次翻转开始移动了一个已经就位的烙饼,且该烙饼后的所有烙饼都已经就位,那么对这个解法,从这次翻转开始得到的一系列状态,从中移除这个烙饼,可得到一系列新的状态。必然可以设计出一个新的解法对应这系列新的状态,而该解法所用的翻转次数不会比原来的多。
4 )估计每个状态还需要翻转的最少次数(即下限值),加上当前的深度,如果大等于上限值,就无需继续遍历。这个下限值可以这样确定:从最后一个位置开始,往前找到第一个与最终结果位置不同的烙饼编号(也就是说排除最后几个已经就位的烙饼),从该位置到第一个位置,计算相邻的烙饼的编号不连续的次数,再加上1。每次翻转最多只能使不连续的次数减少1,但很多人会忽略掉这个情况:最大的烙饼没有就位时,必然需要一次翻转使其就位,而这次翻转却不改变不连续次数。(可以在最后面增加一个更大的烙饼,使这次翻转可以改变不连续数。)如:对状态(0,1,3,4,2,5,6)等同于状态(0,1,3,4,2),由于1、3和4、2不连续,因而下限值为2+1=3。下限值也可以这样确定:在最后面增加一个比所有烙饼都大的已经就位的烙饼,然后再计算不连续数。如:(0,1,3,4,2),可以看作(0,1,3,4,2,5),1和3
、4和2 、2和5这三个不连续,下限值为3。
5)多数情况下,翻转次数的上限值越大,搜索次数就越多。可以采用贪心算法,通过调整每次所有可能翻转的优先顺序,尽快找到一个解,从而减少搜索次数。比如,优先搜索使“下限值”减少的翻转,其次是使“下限值”不变的翻转,最后才搜索使“下限值”增加的翻转。对“下限值”不变的翻转,还可以根据其下次的翻转对“下限值”的影响,再重新排序。由于进行了优先排序,翻转回上一次状态能减少搜索次数的可能性得到进一步降低。
6 )其它剪枝方法:
假设进行第m次翻转时,“上限值”为min_swap。
如果翻转某个位置的烙饼能使所有烙饼就位(即翻转次数刚好为m),则翻转其它位置的烙饼,能得到的最少翻转次数必然大等m,因而这些位置都可以不搜索。
如果在某个位置的翻转后,“下限值”为k,并且 k+m>=min_swap,则对所有的使新“下限值”kk大等于k的翻转,都有 kk+m>=min_swap,因而都可以不搜索。该剪枝方法是对上面的“调整翻转优先顺序”的进一步补充。
另外,翻转某个烙饼时,只有两个烙饼位置的改变才对“下限值”有影响,因而可以记录每个状态的“下限值”,进行下一次翻转时,只须通过几次比较,就可以确定新状态的“下限值”。(判断不连续次数时,最好写成 -1<=x && x<=1, 而不是x==1 || x==-1。对于 int x; a<=x && x<=b,编译器可以将其优化为 unsigned (x-a) <= b-a。)
结果:
对书上的例子{3,2,1,6,5,4,9,8,7,0}:
|
翻转回上次状态
|
搜索函数被调用次数
|
翻转函数被调用次数
|
1.3_pancake_2
|
不允许
|
29
|
66
|
1.3_pancake_2
|
允许
|
33
|
74
|
1.3_pancake_1
|
不允许
|
195
|
398
|
1.3_pancake_1
|
允许
|
116
|
240
|
(这个例子比较特殊,代码1.3_pancake_2.cpp(与1.3_pancake_1.cpp的最主要区别在于,增加了对翻转优先顺序的判断,代码下载),在不允许翻转回上次状态且取min_swap的初始值为2*10-2=18时,调用搜索函数29次,翻转函数56次)。
搜索顺序对结果影响很大,如果将1.3_pancake_2.cpp第152行:
for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){
这一行改为:
for (int pos=size-1, last_swap=cake_swap[step++]; pos>=1; --pos){
仅仅调整了搜索顺序,调用搜索函数次数由29次降到11次(对应的翻转方法:9,6,9,6,9,6),求第1个烙饼数到第10个烙饼数,所用的总时间也由原来的38秒降到21秒。)
四,源码及分析
#include <iostream>
#include <cassert>
#include <cstdio>
class laobing
{
private:
int *m_CakeArray; // 烙饼信息数组
int m_nCakeCnt; // 烙饼个数
int m_nMaxSwap; // 最多交换次数。根据前面的推断,这里最多为
// m_nCakeCnt * 2
int *m_SwapArray; // 交换结果数组
int *m_ReverseCakeArray; // 当前翻转烙饼信息数组
int *m_ReverseCakeArraySwap; // 当前翻转烙饼交换结果数组
int m_nSearch; // 当前搜索次数信息
public:
laobing()
{
m_nCakeCnt = 0;
m_nMaxSwap = 0;
}
~laobing()
{
if(m_CakeArray != NULL)
delete m_CakeArray;
if( m_SwapArray != NULL )
delete m_SwapArray;
if( m_ReverseCakeArray != NULL )
delete m_ReverseCakeArray;
if( m_ReverseCakeArraySwap != NULL )
delete m_ReverseCakeArraySwap;
}
//
// 计算烙饼翻转信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray, nCakeCnt);
m_nSearch = 0;
Search(0);
}
void mOutput(int* CakeArray, int nCakeCnt,int *m_SwapArray,int m_nMaxSwap)
{
int t;
for(int i = 0; i < m_nMaxSwap; i++)//swap times
{
for(int j1 = 0,j2=m_SwapArray[i]; j1<j2; j1++,j2--) //reverse array
{
t = CakeArray[j1];
CakeArray[j1] = CakeArray[j2];
CakeArray[j2] = t;
}
for(int k=0;k<nCakeCnt;++k)
printf("%d ", CakeArray[k]);
printf("\n");
}
}
void Output()// 输出烙饼具体翻转的次数
{
for(int i = 0; i < m_nMaxSwap; i++)
{
printf("%d ", m_SwapArray[i]);
}
printf("\n|Search Times| : %d\n", m_nSearch);
printf("Total Swap times = %d\n", m_nMaxSwap);
mOutput(m_CakeArray, m_nCakeCnt,m_SwapArray,m_nMaxSwap);//输出交换过程
}
private:
//
// 初始化数组信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Init(int* pCakeArray, int nCakeCnt)
{
assert(pCakeArray != NULL);
assert(nCakeCnt > 0);
m_nCakeCnt = nCakeCnt;
// 初始化烙饼数组
m_CakeArray = new int[m_nCakeCnt];
assert(m_CakeArray != NULL);
for(int i = 0; i < m_nCakeCnt; i++)
{
m_CakeArray[i] = pCakeArray[i];
}
// 设置最多交换次数信息
m_nMaxSwap = UpBound(m_nCakeCnt);
// 初始化交换结果数组
m_SwapArray = new int[m_nMaxSwap + 1];
assert(m_SwapArray != NULL);
// 初始化中间交换结果信息
m_ReverseCakeArray = new int[m_nCakeCnt];
for(int i = 0; i < m_nCakeCnt; i++)
{
m_ReverseCakeArray[i] = m_CakeArray[i];
}
m_ReverseCakeArraySwap = new int[m_nMaxSwap];
}
int UpBound(int nCakeCnt)// 寻找当前翻转的上界
{
return nCakeCnt*2;
}
int LowerBound(int* pCakeArray, int nCakeCnt) // 寻找当前翻转的下界
{
int t, ret = 0;
// 根据当前数组的排序信息情况来判断最少需要交换多少次
for(int i = 1; i < nCakeCnt; i++)
{
// 判断位置相邻的两个烙饼,是否为尺寸排序上相邻的
t = pCakeArray[i] - pCakeArray[i-1];
if((t == 1) || (t == -1))
{
}
else
{
ret++;
}
}
return ret;
}
// 排序的主函数
void Search(int step)
{
int i, nEstimate;
m_nSearch++;
// 估算这次搜索所需要的最小交换次数
nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
if(step + nEstimate > m_nMaxSwap)
return;
// 如果已经排好序,即翻转完成,输出结果
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
if(step < m_nMaxSwap)
{
m_nMaxSwap = step;
for(i = 0; i < m_nMaxSwap; i++)
m_SwapArray[i] = m_ReverseCakeArraySwap[i];
}
return;
}
// 递归进行翻转
for(i = 1; i < m_nCakeCnt; i++)
{
Revert(0, i);//反转
m_ReverseCakeArraySwap[step] = i; //第一步 反转的哪一个
Search(step + 1);
Revert(0, i);
}
}
//
// true : 已经排好序
// false : 未排序
//
bool IsSorted(int* pCakeArray, int nCakeCnt)
{
for(int i = 1; i < nCakeCnt; i++)
{
if(pCakeArray[i-1] > pCakeArray[i])
{
return false;
}
}
return true;
}
//
// 翻转烙饼信息
//
void Revert(int nBegin, int nEnd)
{
assert(nEnd > nBegin);
int i, j, t;
// 翻转烙饼信息
for(i = nBegin, j = nEnd; i < j; i++, j--)
{
t = m_ReverseCakeArray[i];
m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
m_ReverseCakeArray[j] = t;
}
}
};
int main()
{
laobing ll;//这里ll 不可以加括号
laobing *l=new laobing();
int aa[10]={ 3,2,1,6,5,4,9,8,7,0};
l->Run(aa,10);
l->Output();
ll.Run(aa,10);
return 0;
}
输出结果:
4 8 6 8 4 9
|Search Times| : 172126
Total Swap times = 6
5 6 1 2 3 4 9 8 7 0
7 8 9 4 3 2 1 6 5 0
1 2 3 4 9 8 7 6 5 0
5 6 7 8 9 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
五,优化:
在网上下了《编程之美》“第6刷”的源代码,结果在编译时存在以下问题:
1) Assert 应该是 assert
2) m_arrSwap 未被定义,应该改为m_SwapArray
3 )Init函数两个for循环,后一个没定义变量i,应该将i 改为 int i
另外,每运行一次Run函数,就会调用Init函数,就会申请新的内存,但却没有释放原来的内存,会造成内存泄漏。if(step + nEstimate > m_nMaxSwap) 这句还会造成后面对m_ReverseCakeArraySwap数组的越界访问,使程序不能正常运行。
书上程序的低效主要是由于进行剪枝判断时,没有考虑好边界条件,可进行如下修改:
1 ) if(step + nEstimate > m_nMaxSwap) >改为 >=。
2 ) 判断下界时,如果最大的烙饼不在最后一个位置,则要多翻转一次,因而在LowerBound函数return ret; 前插入行:
if (pCakeArray[nCakeCnt-1] != nCakeCnt-1)
ret++;
3 ) n个烙饼,翻转最大的n-2烙饼最多需要2*(n-2)次,剩下的2个最多1次,因而上限值为2*n-3,因此,m_nMaxSwap初始值可以取2*n-3+1=2*n-2,这样每步与m_nMaxSwap的判断就可以取大等于号。
4 )采用书上提到的确定“上限值”的方法,直接构建一个初始解,取其翻转次数为m_nMaxSwap的初始值。
1和2任改一处,都能使搜索次数从172126降到两万多,两处都改,搜索次数降到3475。若再改动第3处,搜索次数降到2989;若采用4的方法(此时初始值为10),搜索次数可降到1045。
六,思考
书中P22页提到动态规划,但最后却给出了解决最优化问题普遍适用但效率可能是最差的递归方法。这不禁让人疑惑:这也不美啊!?如果我们能证明该问题满足动态规划或贪心算法的使用条件,解决问题的时间复杂度将会降到多项式时间甚至N^2。但书中提到动态规划却最终没有使用,又没有讲明原因,我觉得是一种疏失(应该不算错误)。那我们就来想一下为什么没有动态规划或贪心算法的原因。
我们知道动态规划方法是一种自底向上的获取问题最优解的方法,它采用子问题的最优解来构造全局最优解。利用动态规划求解的问题需要满足两个条件:即(1)最优子结构 (2)子结构具有重叠性。条件(1)使我们可以利用子问题的最优解来构造全局最优解,而条件(2)是我们在计算过程中可以利用子结构的重叠性来减少运算次数。此外,《算法导论》上还以有向图的无权最短路径和无权最长路径为例提出条件(3)子问题必须独立。
首先我们假定烙饼问题存在优化子结构。假如我们有N个烙饼,把他们以其半径由小到大进行编号。优化子结构告诉我们对于i个烙饼,我们只需要先排列前(i-1)个,然后再将第i个归位;或先排列第2到i个,最后将第一个归位;又或是找到一个位置k[i<=k<j]像矩阵乘法加括号那样,使得我们先排列前k个,再排列后j-k个,最后再将二者合并,以找到一个最佳翻转策略等等...
根据动态规划算法的计算过程,我们需要一个N*N矩阵M,其中M[i][j]表示将编号i至编号j的烙饼排序所需要的翻转次数。但我们真的能从M[0][0..j-1]和M[1][j+1],或与M[i][j]同行同列的值来计算M[i][j]吗?如果能,我们就能获得多项式时间的算法。
我们来看书中给出的例子:(顶端)3,2,1,6,5,4,9,8,7,0(底端),我们最终的目标是计算M[0][9]。
这里我们以计算M[0][4]为例,计算的矩阵我已经在下面给出:
0 1 2 3 4 5 6 7 8 9
------------------------
0|0 1 (1){1}[?]
1| 0 1 (1){1}
2| 0 1 (1)
3| 0 0
4| 0
------------------
实际上如果我们要向将0-4号烙饼(注意:烙饼编号也等同于其半径)排为正序(中间有其他烙饼也没关系),按照程序给出的结果, 我们需要进行3次翻转,分别为[2,5,9](即分别翻转队列中第二(从零开始)、五、九个烙饼,这里的数字不是烙饼的编号):
[1] [2] [3] 6 5 [4] 9 8 7 [0]
[4] 5 6 [3] [2] [1] 9 8 7 [0]
[0] 7 8 9 [1] [2] [3] 6 5 [4]
我们知道,该矩阵中每一个数的背后都隐含着一个烙饼的排列,例如M[0][4]就应该对应0,7,8,9,1,2,3,6,5,4
所以,每一个M[i][j]的选取都蕴含着其子排列的顺序的变化。
计算M[i][j]的时候,我们需要计算i-j号饼的全部划分(不包括全部为1的划分)所能构成的翻转结构,并取其翻转 次数最少的哪一个最为M[i][j]的最终值。例如,我们在计算M[0][4]的时候,需要查看:
/**先将0和1-4号分别排序,最后将二者合并为有序所需要的翻转次数*/
M[0][0],M[1][4]
/** 同上 */
M[0][1],M[2][4]
/** 同上 */
M[0][2],M[3][4]
/** 同上 */
M[0][3],M[4][4]
/* 先将0、1、2、3-4号分别排序,最后将4者合并为有序所需要的翻转次数.
* 注意这里又包含将4个分组再次进行划分的问题!
*/
M[0][0],M[1][1],M[2][2],M[3][4]
.....//中间略
M[0][3],M[4][4]
如果再加上运算过程中我们可以淘汰超过最大反转次数的方案(剪枝?),我们完成全部的运算所经历的运算过程的时间复杂度已经不是多项式时间的,而是和先前所说的递归方法已没什么两样。
造成这种现象的原因是:某个子问题的最优解不一定是整体的最优解,所以我们在处理整个问题的时候,需要遍历所有可能的子问题,并计算它到整体问题所消耗的代价,才能最终作出有利于整体问题的选择。
所以我们一开始的假设,即烙饼问题有优化子结构的假设是错误的。因此我们不能用动态规划,同理也不能用贪心算法。
但说到每一步的“选择”问题,我记得算法导论上有一个叫做“A*”的算法,它的思想是在进行每一步选择的时候都“推算”最终可能需要的代价,并选择当前代价最小的分支进行遍历。这个“推算”的结果可能不会是最终的代价,而只是作为分支选择的依据。如果谁有兴趣就做一下吧 :-)
分享到:
相关推荐
【华为OJ烙饼排序】是华为在线测评平台(OpenJudge)上的一道高级编程题目,主要考察的是排序算法的应用和实现。烙饼排序(Flipping Sorting),也称为煎饼排序,是一种基于比较的排序算法,它的灵感来源于煎饼翻转...
然而,翻转烙饼排序因其独特的解决思路和算法设计,仍然是学习算法设计原则和优化技巧的重要案例之一。 ### 结论 翻转烙饼排序问题不仅考验了算法设计的能力,也体现了对数据结构和排序算法原理的深刻理解。通过...
《程序之美-C语言:烙饼排序算法与买书问题源码》 在计算机科学的世界里,算法是解决问题的关键。本文将深入探讨两个编程问题:烙饼排序算法和买书问题,这两个问题都涉及到C语言的高效实现。我们将通过源代码分析...
《烙饼问题》课件.ppt是一个关于数学应用的教学资源,旨在让学生通过探索和分析烙饼问题,学习数学知识,发展逻辑思维和解决问题的能力。下面是该资源的知识点总结: 一、数学概念: 1. 最优化问题:烙饼问题是一...
《数学广角优化烙饼问题》是一份针对中小学生设计的专业课件,主要讲解如何通过优化策略来解决实际生活中的烙饼问题,旨在培养学生的逻辑思维和优化意识。在这个问题中,核心是找到烙饼最节省时间的方法。 首先,...
文章《烙饼里的爱与温柔》通过细腻的笔触,描绘了作者肖遥童年时姥姥对烹饪的热情和对家庭成员的深厚情感。姥姥的烹饪技艺不仅仅是一种家庭生活的日常,更是她表达爱与温柔的方式。姥姥烙出的各种饼,成为了家族故事...
在这个文件中,我们可以看到一个经典的烙饼问题,它是计算机科学中一个著名的例子,用于说明时间复杂度的概念。下面我们将详细解释这个问题的解决方案和相关的知识点。 首先,让我们了解什么是烙饼问题。烙饼问题是...
标签中的“烙饼问题”是一种经典的排序问题,也被称为煎饼排序。在这个问题中,想象一个平底锅可以同时煎两张饼,而我们要对多张饼进行排序,每次只能翻转一张或两张饼。烙饼问题展示了如何在有限的操作下达到目标...
该文档描述的是一种自动化烙饼装置的制作方法,旨在提高烙饼加工的效率,减轻工人的劳动强度,并确保卫生安全。这种装置主要由以下几个部分组成: 1. 底板:作为装置的基础结构,底板1固定了整个装置的其他组件。 ...
优化烙饼问题 通过这节课,我们可以学习到数学广角——优化烙饼问题的思想。优化烙饼问题是指在烙饼时,如何通过合理的安排来节约时间和能源。我们可以通过简单的实例,初步体会运筹思想在解决实际问题中的应用。 ...
"烙饼问题",也被称为"煎饼问题"或"三明治问题",是计算机科学中的一个经典问题,属于算法优化的范畴。这个问题源于生活中的实际情况:在平底锅中,每次只能同时烙两张饼,饼需要烙两面,每面需要相同的时间。其目标...
标题中的“行业文档-设计装置-一种节能燃气烙饼锅.zip”表明这是一份关于工业设计和设备创新的文档,具体聚焦在节能燃气烙饼锅的设计上。这种锅的目的是提高烹饪效率,同时减少能源消耗,是现代厨房设备技术与环保...
烙饼问题是一种经典的数学问题,主要涉及如何在有限的时间和资源下,通过优化策略实现效率最大化。在这个教学设计中,教师江海峰针对四年级学生,依据九年义务教育新课标(人教版)数学教材第七册的相应内容,旨在让...
总结起来,烙饼问题提供了一个实际生活中的优化问题实例,它展示了如何通过合理规划和策略调整来提高工作效率。在实际操作中,这样的原则可以应用于各种批量处理的任务,比如烹饪、生产流程优化等。理解并应用这些...
5. **规律的发现与应用**:学生在探究烙饼方法的过程中,会发现一个规律,即当烙饼数量为偶数时,可以两张两张地烙,而当数量为奇数时,前半部分两张两张烙,最后一张按最佳方法烙。同时,他们也会发现烙饼的张数...
9分钟的烙饼方案尤其具有挑战性,它要求学生在第一次烙饼时就考虑到饼的组合,以便在第二次烙饼时能实现所有饼的翻面,这既考验了学生的逻辑思维,也强调了合理规划的重要性。 整个教学设计通过情境引入、问题探究...
"烙饼排序"可能是对一种特定排序算法的形象化描述,它可能涉及到比较和交换元素,优化排序效率。 3. **连连看死锁判断**:连连看游戏中的死锁问题可能涉及到图论和状态空间搜索。死锁是并发系统中的一种现象,当两...
《烙饼问题11-2.ppt》是一个探讨优化算法的经典问题,主要涉及数学和计算机科学中的调度理论。这个问题的核心是找到在有限资源下完成任务的最有效策略,特别是当资源(在这里是平底锅)只能处理有限数量的任务时。在...
它的创新之处在于能够通过一个微型滚动轮自动测量,测量数据能够通过手机App进行存储和分享。此外,该设备被用来测量孕妇的肚子变化和啤酒的泡沫高度,显示出智能设备在跨界应用方面的灵活性和多样性。 3. 摄像头...
此外,还总结了一个公式:烙饼的最少时间等于烙一面饼的时间乘以饼数(一张饼除外)。 此外,课件还扩展到了类似问题,如如果有两个厨师,如何安排炒菜顺序以达到效率最大化,这同样涉及到优化问题的解决。 练习题...