2021微软技术面试心得.docx

微软技术面试心得1 .第1章游戏之乐一游戏中碰到的题目2 .第2章数字之魅数字中的技巧3 .第3章结构之法字符串及链表的探索4 .第4章数学之趣一数学游戏的乐趣5 .第1章游戏之乐游戏中碰到的题目研究院举办过几届桌上足球(football)公开赛，第一届的冠军是一位文静的女实习生。这一章的题目原计划叫做“ProblemSolving"运用所学的知识解决问题，直译为“问题解决“，甚为不美。事实上这里面大部分题目都是和游戏相关的，因此本章改名为“游戏之乐”。这些题FI从游戏和作者平时遇到的有趣问题出发，向程序员提出挑战。个人电脑(PC)在蹒跚起步的时候，就被当时的主流观点视为玩具。PC上的确有各种各样的游戏，电脑上的游戏是给人玩的，如果你愿意，CPU也可以让人“玩”。笔者曾经用“CPU使用率”这个问题问了十几个应聘者，一个典型的模式如下。我：笔试考得怎么样？发挥了多少水平？答：我不习惯在纸上写程序，平时都在电脑上写我：那你对WindOWs、操作系统这些东西熟悉吗？答：那是相当熟悉我：好，那你可否在这笔记本电脑上帮我解决一个问题一让CPU的使用率划出一条直线，比如就在50%的地方。这个时候可以观察应聘者的好几个方面。1.应聘者面对这个陌生问题的时候如何开始分析。有人知道观察任务管理器如何运行，有人在纸上写写画画，有人明显没有什么想法。2 .当提示可以在网上搜索资料时，应聘者如何寻找资料，如何学习。比如，有一位学生很快地用快捷键在IE中打开了几个Tab窗口，然后每个窗口输入不同的搜索关键字。当我提示在MSDN上查找一些函数的时候，有些人根本不知道MSDN网站应该怎么用。有些人反复读了函数的说明，仍不得其解。3 .在电脑上是怎么写程序，怎么调试程序的。有人能很娴熟地使用C/C#的各种语言特性，很快地写出程序，有人写的程序编译了好几次都不能通过，对编译错误束手无策。程序第一次运行的时候，任务管理器的CPU使用率不按预想的轨道运行，这时候有人就十分慌乱，在程序中瞎改一通，希望能“蒙''对。有人则有条理地分析，最后找到并解决问题。我想，45分钟下来，应聘者的思考能力、学习能力、技术能力如何，应该很清楚了。行还是不行，双方都明白了。这一章的其他题目大多和游戏有关，同学们在玩，空当接龙，“俄罗斯方块，甚至“魔兽”的时候，有没有动过好奇心这个程序为什么这么酷，如果是我来写，应该怎么做？有没有把好奇心转化为行动？喜欢玩电脑、会玩电脑的人，也会运用电脑解决实际问题，这也是我们要找的人才。1.I让CPU占用率曲线听你指挥写一个程序，让用户来决定WindOWS任务管理器(TaSkManager)的CPU占用率。程序越精简越好，计算机语言不限。例如，可以实现下面三种情况1：1.CPU的占用率固定在50%,为一条直线；2 .CPU的占用率为一条直线，具体占用率由命令行参数决定(参数范围l100)；3 .CPU的占用率状态是一个正弦曲线。分析与解法有一名学生写了如下的代码：while(true)if(busy)i+;else然后她就陷入了苦苦思索：else干什么呢？怎么才能让电脑不做事情呢？CPU使用率为。的时候，到底是什么东西在用CPU?另一名学生花了很多时间构想如何“深入内核，以控制CPU占用率”可是事情真的有这么复杂吗？MSRAIEG(MicrosoftResearchAsiaJnnovationEngineeringGroup)的一些实习生写了各种解法，他们写的简单程序可以达到如图1-1所示的效果。图1-1编程控制CPU占用率呈现正弦曲线形态看来这并不是不可能完成的任务。让我们仔细地回想一下写程序时曾经碰到的问题，如果不小心写了一个死循环，CPU占用率就会跳到最高，并且一直保持在100%。我们也可以打开任务管理器2,实际观测一下它是怎样变动的。凭肉眼观察，它大约是1秒钟更新一次。一般情况下，CPU使用率会很低。但是，当用户运行一个程序，执行一些复杂操作的时候，CPU的使用率会急剧升高。当用户晃动鼠标时，CPU的使用率也有小幅度的变化。那当任务管理器报告CPU使用率为0的时候，是谁在使用CPU呢？通过任务管理器的“进程(Process)”一栏可以看到，SystemIdleProCeSS占用了CPU空闲的时间这时候大家该回忆起在“操作系统原理”这门课上学到的一些知识了吧。系统中有那么多进程，它们什么时候能“闲下来”呢？答案很简单，这些程序或在等待用户的输入，或者在等待某些事件的发生3,或者主动进入休眠状态4。在任务管理器的一个刷新周期内，CPU忙(执行应用程序)的时间和刷新周期总时间的比率，就是CPU的占用率，也就是说，任务管理器中显示的是每个刷新周期内CPU占用率的统计平均值。因此，我们可以写一个程序，让它在任务管理器的刷新期间内一会儿忙，一会儿闲，然后调节忙/闲的比例，就可以控制任务管理器中显示的CPU占用率。解法一：简单的解法要操纵CPU的使用率曲线，就需要使CPU在一段时间内(根据TaSkManager的采样率)跑busy和idle两个不同的循环(IOoP),从而通过不同的时间比例，来调节CPU使用率。BUSy100P可以通过执行空循环来实现，idle可以通过SIeeP()来实现。问题的关键在于如何控制两个1。P的时间，我们先试验一下SIe叩一段时间，然后循环n次,估算n的值。那么对于一个空循环for(i=0;i<n;i+)；又该如何来估算这个最合适的n值呢？我们都知道CPU执行的是机器指令，而最接近于机器指令的语言是汇编语言，所以我们可以先把这个空循环简单地写成如下汇编代码(此代码为示意性的伪代码)后再进行分析：next:mov eax ,dword ptril add eax,lmov dword ptri,eax cmp eax,dword ptrn jl next;将i放入寄存器；寄存器加1；寄存器赋回i;比较i和n;i小于n时重复循环假设这段代码要运行的CPU是P42.4Ghz(2.4x10的9次方个时钟周期每秒)。现代CPU每个时钟周期可以执行两条以上的代码，我们取平均值两条，于是有(2400000000×2)/5=960000000(循环/秒)，也就是说CPUI秒钟可以运行这个空循环960000000次。不过我们还是不能简单地将n=960000000,然后SIeeP(IOoO)了事。如果我们让CPU工作1秒钟，然后休息1秒钟，波形很有可能就是锯齿状的一先达到一个峰值(>50%),然后跌到一个很低的占用率。我们尝试着降低两个数量级，令n=9600000,而睡眠时间则相应地改为1毫秒(Sleep(10)。用10毫秒是因为比较接近WindoWS的调度时间片。如果选得太小(比如1毫秒)，会造成线程频繁地被唤醒和挂起，无形中又增加了内核时间的不确定性。最后我们可以得到代码清单1-1。代码清单1-1intmain()(for(;)(for(inti=0;i<9600000;i+)9Sleep(10);return0;在不断调整9600OOo的参数后，我们就可以在一台指定的机器上获得一条大致稳定的50%CPU占用率直线。使用这种方法要注意两点影响：1.尽量减少sleep/awake的频率，减少操作系统内核调度程序的干扰；2.尽量不要调用SyStemCalI(比如I/O这些PriVilegeinStrUCtiOn),因为它也会导致很多不可控的内核运行时间。该方法的缺点也很明显：不能适应机器差异性。一旦换了一个CPU,我们又得重新估算n值。有没有办法动态地了解CPU的运算能力，然后自动调节忙/闲的时间比呢？请看下一个解法。解法二：使用GetTiCkCoUnt()和SIeeP()我们知道GetTickCountO可以得到“系统启动到现在”所经历时间的毫秒值，最多能够统计到4上7天。我们可以利用GetTiCkCOUlH()来判断busyloop要循环多久，伪代码如清单12所示。代码清单12constDWORDbusyTime=10;/10msconstDWORDintidleTime=busyTime;/sameratiowillleadto50%cpuusageInt4StartTime=0;while(true)(DWORDStartTime=GetTickCount();/busyloopwhile(GetTickCountO-StartTime)<=busyTime)/idleloopSleep(idleTime);这两种解法都是假设目前系统上只有当前程序在运行，但实际上，操作系统中有很多程序会同时执行各种各样的任务，如果此刻其他进程使用了10%的CPU,那我们的程序就只能使用40%的CPU,这样才能达到50%的效果。怎么做呢？这就要用到另一个工具来帮忙Perfmon.exe<）PerfmOrl是从WindoWSNT开始就包含在WindOWS管理工具组中的专业检测工具之一（如图12所示）。PerfmOn可获取有关操作系统、应用程序和硬件的各种效能计数器（Perfcounter）<>PerfmOn的用法相当直接，只要选择你所要检测的对象（比如：处理器、RAM或硬盘），然后选择效能计数器（比如监视物理磁盘的平均队列长度）即可。图1-2系统监视器（Perfmon）我们可以写程序来查询Perfmon的值，MiCrOSOfLNetFrameWOrk提供了PerfOrmanCeeoUnter这一对象，可以方便地得到当前各种性能数据，包括CPU的使用率。例如下面这个程序（见代码清单13）。解法三：能动态适应的解法代码清单1-3/C#codestaticvoidMakeUsage(floatlevel)PerformanceCounterP=newPerformanceCounter(,Processor","%ProcessorTimenr-Total);while(true)(if(.NextValue()>level)System-Threading.Thread.Sleep(10);)可以看到，上面的解法能方便地处理各种CPU使用率参数。这个程序可以解答前面提到的问题2。有了前面的积累，我们应该可以让任务管理器画出优美的正弦曲线了，见代码清单14。解法四：正弦曲线代码清单1-4/C+codetomaketaskmanagergeneratesinegraph#includenWindows.h#includestdlib.h,#include,math.h/把一条正弦曲线O2p之间的弧度等分成200份进行抽样，计算每个抽样点的振幅然后每隔30OmS的时间取下一个抽样点，并让CPU工作对应振幅的时间constintSAMPLING_COUNT=200;抽样点数量constdoublePI=3.14159265;/pi值constintTOTAL_AMPLITUDE=300;/每个抽样点对应的时间片int_tmain(intargc,_TCHAR*argv)(-DWORDbusySpanSAMPLING_COUNT;intamplitude=TOTAL_AMPLITUDE/2;doubleradian=0.0;doubleradianlncrement=2.0/(double)SAMPLlNG_COUNT;/抽样弧度的增量for(inti=0;i<SAMPLING_COUNT;i+)(busySpani=(DWORD)(amplitude+(sin(PI*radian)*amplitude);radian+=radianincrement;/printf(w%dtdn,busySpani,TOTAL_AMPLITUDE-busySpani);DWORDStartTime=0;for(intj=0;j=(j+l)%SAMPLING_COUNT(StartTime=GetTickCount();while(GetTickCountO-StartTime)<=busySpanj)fSleep(TOTAL_AMPLITUDE-busySpanj);)return0;讨论如果机器是多核或多CPU,上面的程序会出现什么结果？如何在多核或多CPU时显示同样的状态？例如，在双核的机器上，如果让一个单线程的程序死循环，能让两个CPU的使用率达到50%的水平吗？为什么？多CPU的问题首先需要获得系统的CPU信息。可以使用GetPrOCeSSOrInfOO获得多处理器的信息，然后指定进程在明L个处理器上运行。其中指定运行使用的是SetThreadAffinityMask()函数。另外，还可以使用RDTSC指令获取当前CPU核心运行周期数。在x86平台上定义函数：inlineunsignedjnt64GetCPUTickCount()_asm(rdtsc;)在x64平台上定义：#defineGetCPUTickCount()_rdtsc()使用CaHNtPoWerlnformaIionAPI得到CPU频率，从而将周期数转化为毫秒数，例如代码清单15所示。代码清单15_PR0CESS0R_P0WERJNF0RMATI0Ninfo;Cal1NTPowerlnformation(11,/queryprocessorpowerinformationNULL,/noinputbufferO,/inputbuffersizeiszero&info,/outputbuffersizeof(info);/outbufsizeunsigned_int64l_begin=GelCPUTickCount();/dosomethingunsignedjnt64Cend=GetcPUTickCount();doublemillisec=(double)(t_end-t_begin)/(double)info.CurrentMhz;RDTSC指令读取当前CPU的周期数，在多CPU系统中，这个周期数在不同的CPU之间基数不同，频率也可能不同。用从两个不同的CPU得到的周期数来计算会得出没有意义的值。如果线程在运行中被调度到了不同的CPU,就会出现上述情况。可用SetThreadAffinityMaSk避免线程迁移。另外，CPU的频率会随系统供电及负荷情况有所调总结能帮助你了解当前线程/进程/系统效能的APl大致有以下这些。1.SleepO这个方法能让当前线程“停”下来。2 .WaitForSingleObject()由己停下来，等待某个事件发生。3 .GetTickCountO有人把TiCk翻译成“嘀嗒”，很形象。4 .QueryPerformanceFrequency()、QueryPerformanceCounter()让你访问到精度更高的CPU数据。5 .timeGetSystemTime()另一个得到高精度时间的方法。6 .PerformanceCounter效能计数器。7 .GetProcessorInfo()/SetThreadAffinityMask()。遇到多核的问题怎么办呢？这两个方法能够帮你更好地控制CPU。8 .GetCPUTickCount()。想拿到CPU核心运行周期数吗？用用这个方法吧。了解并应用了上面的API,就可以考虑在简历中写上“精通WindoWS”了。1.2中国象棋将帅问题下过中国象棋的朋友都知道，双方的“将''和"帅”相隔遥远，并且不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将''和"帅''二子(如图1-3所示)(为了下面叙述方便，我们约定用A表示“将”,B表示“帅”)。图13棋盘上的将和帅A、B二子被限制在己方3x3的格子里运动。例如，在如上的表格里，A被正方形dl,fl,d8,f8包围,而B被正方形d3,f3,dl,fl包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B,也就是说，A和B不能处于同一纵向直线上（比如A在diO的位置，那么B就不能在dl、d2以及d3的位置上）。请写出一个程序，输出A、B所有合法位置。要求在代码中只能使用一个字节存储变量。分析与解法问题本身并不复杂，只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量，所以首先必须想清楚在写代码的时候，有哪些信息需要存储，并且尽量高效率地存储信息。稍微思考一下，可以知道这个程序的大体框架是：遍历A的位置遍历B的位置判断A、B的位置组合是否满足要求如果满足，则输出因此，需要存储的是A、B的位置信息，并且每次循环都要更新。首先创建一个逻辑坐标系统，一个可行的方法是用19的数字，按照行优先的顺序来表示每个格点的位置（如图1-4所示）。这样，只需要用模余运算就可以得到当前的列号，从而判断A、B是否互斥。图1-4用19的数字表示A、B的坐标第二，题目要求只用一个变量，我们却要存储A和B两个子的位置信息，该怎么办呢？可以先把已知变量类型列举一下，然后分析。对于bool类型，估计没有办法做任何扩展了，因为它只能表示true和false两个值；而byte或int类型，它们能够表达的信息则更多。事实上，对本题来说，每个子都只需要9个数字就可以表示它的全部位置。一个8位的byte类型能够表达28=256个值，所以用它来表示A、B的位置信息绰绰有余，因此可以把这个字节的变量(设为b)分成两部分。用前面的4bit表示A的位置，用后面的4bit表示B的位置，而4个bit可以表示16个数，这已经足够了。问题在于：如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。下面是做法。将byleb(10100101)的右边4bit(0101)设为n(0011)：首先清除b右边的bits,同时保持左边的bits:11110000(LMASK)&10100101(b)10100000然后将上一步得到的结果与n做或运算:10100000(LMASK&h)I00000011(n10100011Wbyteb(10100101)左边的4bit(1010)设为n(0011)：首先，清除b左边的bits,同时保持右边的bits：00001111(RMASK)&10100101(b)00000101现在，把n移动到byte数据的左边：n<<4=00110000然后对以上两步得到的结果做或运算，从而得到最终结果。00000101(RMASK&b)I00110000(/7«4)00110101得到byte数据的右边4bits或左边4bits(e.g.10100101中的IolO以及OlOI):清除b左边的bits,同时保持右边的bits：00001111(RMASK)&10100101(b)00000101清除b右边的bits,同时保持左边的bits：11110000(LMASK)&10100101(h)10100000将结果右移4bits：10100000»4=00001010最后的挑战是如何在不声明其他变量约束的前提下创建一个for循环。可以重复利用IbyIe的存储单元，把它作为循环计数器并用前面提到的存取和读入技术进行操作。还可以用宏来抽象化代码，例如：for(LSET(b,l);LGET(b)<=GRIDW*GRIDW;LSET(b,(LGET(b)+1)解法一(如代码清单16所示)代码清单1-6#include<stdio.h>#defineHALF_BITS_LENGTH4/这个值是记值存储或元长度的一半，在这道题里是4bit#defineFULLMASK255/这个数字表示一个全部bit的mask,在二进制表示中，它是IlllIm#defineLMASK(FULLMASK«HALFTSjLENGTH)/这个宏表示左bits的mask,在二进新表示轧它是11110000#defineRMASK(FULLMASK»HALF_BITS_LENGTH)/这个数字表示右bits的mask,在二逑制表示中，它表示OOooml#defineRSET(bzn)(b=(LMASK&b)In)/这个宏，将b的右边设置成n#defineLSET(bzn)(b=(RMASK&b)I(n«HALF_BITS_LENGTH)/这个宏，将b的左边设置成n#defineRGET(b)(RMASK&b)/这个宏得到b的右边的值#defineLGET(b)(LMASK&b)»HALF_BITS_LENGTH)/这个宏得到b的左边的值#defineGRIDW3/这个数字表示将帅移动范围的行宽度intmain()(unsignedcharb;for(LSET(br1);LGET(b)<-GRIDW*GRIDW;LSET(b,(LGET(b)+1)for(RSET(b,1);RGET(b)<=GRIDW*GRIDW;RSET(b,(RGET(b)+1)if(LGET(b)%GRIDW!=RGET(b)%GRIDW)printf("A=%dzB=%dn,LGET(b)rRGET(b);return0;输出格子的位置用N来表示，N=l,2.,8,9,依照行优先的顺序，如图15所示。图1-5格子的位置/=1.8=2/=4,8=2A=LB=2A=1,8=34=4,8=3A=LB=3A=1,6=54=4,8=5A=LB=5/=1,8=64=4,8=6A=7,B=64=1,8=8N=4.8=8A=I7、B=8A=1,8=9A=4.B=9A=LB=9A=2,B=A=5,B=l4=8,8=1A=2,B=34=5,8=34=8,8=34=2,8=44=5.8=44=8,8=44=2,3=6A=5.B=64=8,8=6A=2,B=74=5,B=7A=8,B=7A=2,B=9A=5,B=94=8,8=94=3,8=1A=6,=14=9,8=1/I=3,8=2A=6,B=2A=%B=24=3,8=4A=6.B=44=9,8=4A=3,B=5A=6.B=5A=9,8=5A=3,B=1A=6,B=74=9,8=7/=3,8=84=6,8=84=9,8=8考虑了这么多因素，总算得到了本题的一个解法，但是MSRA里却有人说，下面的一小段代码也能达到同样的目的。BYTEi=81;while(i)(if(i9%3=i%9%3)continue;printf(tA=%d,B=%dn,i9+l,i%9+1);)很快又有另一个人说他的解法才是效率最高的(如代码清单1-7所示)。代码清单1-7structunsignedchara:4;unsignedcharb:4;)i；for(i.a=l;i.a<=9;i.a+)for(i.b=l;i.b<=9;i.b+)if(i.a%3!=i.b%3)printf("A=%d,B=%d,i.a,i.b);读者能自己证明一下吗？51.3一摞烙饼的排序星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好一小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。”我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到大小有序的结果呢？”如图1-6所示。你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？图1-6翻烙饼的顺序分析与解法这个排序问题非常有意思，首先我们要弄清楚解决问题的关键操作一"单手每次抓几块饼，全部颠倒具体参看图1-7。图1-7烙饼的翻转过程每次我们只能选择最上方的一堆饼，一起翻转。而不能一张张地直接抽出来，然后进行插入，也不能交换任意两块饼。这说明基本的排序办法都不太好用。那么怎么把这n个烙饼排好序呢？由于每次操作都是针对最上面的饼，如果最底层的饼己经排序，那我们只用处理上面的1个烙饼。这样，我们可以再简化为n2、n-3,直到最上面的两个饼排好序。解法一我们用图1-8演示一下，为了把最大的烙饼摆在最下面，我们先把最上面的和最大的烙饼之间的翻转（14之间），这样，最大的烙饼就在最上面了。接着，我们把所有烙饼翻转（45之间），最大的烙饼就摆在最下面了。图18两次翻转烙饼，调整最大的烙饼到最底端之后，我们对上面n-1、n-2个饼重复这个过程。那么，我们一共需要多少次翻转才能实现结果呢？经过两次翻转可以把最大的烙饼翻转到最下面。因此，最多需要把上面的nl个烙饼依次翻转两次。那么，我们至多需要2（n-l）次翻转就可以把所有烙饼排好序（因为第二小的烙饼排好的时候，最小的烙饼已经在最上面了）。这样看来，单手翻转的想法是肯定可以实现的。我们进一步想想怎么减少翻转烙饼的次数吧。怎样才能通过程序来搜索到一个最优的方案呢？通过每次找出最大的烙饼进行翻转是一个可行的解决方案。这个方案是最好的一个吗？考虑这样一种情况，假如这堆烙饼中有好几个不同的部分相对有序，凭直觉来猜想，我们可以先把小一些的烙饼进行翻转，让其有序。这样会比每次翻转最大的烙饼要更快。既然如此，有类似的方案可以达到目的吗？比如说，考虑每次翻转的时候，把两个本来应该相邻的烙饼尽可能地换到一起。这样，等所有的烙饼都换到一起之后，实际上就是完成排序了。（从这个意义上来说，每次翻最大烙饼的方案实质上就是每次把最大的和次大的交换到一起。)在这个基础之上，本能的想法就是穷举。只要穷举出所有可能的交换方案，那么，我们一定能够找到最优的一个。沿着这个思路去考虑，我们自然就会使用动态规划或递归的方法来实现了。可以从不同的翻转策略开始，比如说第一次先翻最小的，然后递归把所有的可能全部翻转一遍。这样，最终肯定是可以找到一个解的。但是，既然是递归就一定有退出的条件。在这个过程中，第一个退出的条件肯定是所有的烙饼已经排好序。那么，有其他的吗？大家仔细想想就会发现到，既然2(n-l)是一个最多的翻转次数。如果在算法中，需要翻转的次数多于2(n-l),我们就应该放弃这个翻转算法，直接退出。另外，既然这是一个排序问题。我们也应该利用排序的信息来处理。同样，在翻转的过程中，我们可以看看当前的烙饼数组排序情况如何，然后利用这些信息来减少翻转次数。代码清单1-8是在前面讨论的基础之上形成的一个粗略的搜索最优方案的程序。代码清单18/烙饼排序实现/classCPrefixSortingpublic:CPrefixSorting()(m_nCakeCnt=0;m_nMaxSwap=O;)-CPrefixSorting()(if(m_CakeArray!=NULL)(deletem_CakeArray;)if(m_SwapArray!=NULL)(deletem_SwapArray;)if(m_ReverseCakeArray!=NULL).deletem_ReverSeCakeArray;if(m_ReverSeCakeArraySwap!=NULL)(deletem_ReverSeCakeArraySwap;/计算烙饼翻转信息/aram/CakeArray存储烙饼索引数组/nCakeCnt烙饼个数/voidRun(int*PCakeArray,intnCakeCnt)(Init(pCakeArray,nCakeCnt);m_nSearch三O;Search(O);/榆出烙饼具体翻转的次数/voidOutput()(for(inti=O;i<m_nMaxSwap;i+÷)(printf(,%d",m_arrSwapi);printf("nISearchTimesI:%dn,m_nSearch);printf("TotalSwaptimes=%dn,zm_nMaxSwap);private:/初始化数组信息/QParam/CakeArray存储珞饼索引数组/nCakeCnt烙饼个数/voidInit(int*PCakeArray,intnCakeCnt)(assert(pCakeArray!-NULL);assert(nCakeCnt>0);m_nCakeCnt=nCakeCnt;/初始化烙饼数组m_CakeArray=newintm_nCakeCnt;assert(m_CakeArray!=NULL);for(inti=0;i<m_nCakeCnt;i+)m_CakeArrayi=pCakeArrayi;/设建最多交换次数信息m_nMaxSwap=UpperBound(m_nCakeCnt);/初始化交换结果数组m_SwapArray=newintm_nMaxSwap+l;assert(m_SwapArray!=NULL);/初始化中间交换结果信息m_ReverseCakeArray=newintm_nCakeCnt;for(i=O;i<m_nCakeCnt;i+)(m_ReverseCakeArrayi=m_CakeArrayi);)m_ReverseCaReArraySwap»newintm_nMaxSwap;/寻找当前翻转的上界/intUpperBound(intnCakeCnt)returnnCakeCnt*2;/寻找当前翻转的下界/intLowerBound(int*pCakeArrayzintnCakeCnt)(inttfret=0;/根据当前数组的排序信息情况来判斯最少需要交换多少次for(inti=1;i<nCakeCnt;i+)(/判断位置相邻的两个烙饼，是否为尺寸排序上相邻的t=pCakeArrayi-pCakeArrayi-1;if(t=1)II(t=-1)()elseret+;)returnret;)/排序的主函数voidSearch(intstep)(inti,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=O;i<m_nMaxSwap;i+)m_arrSwapi=m_ReverseCakeArraySwapi;return;/递归进行翻转for(i=1;i<m_nCakeCnt;i+)(Reverse(0ri);m_ReverseCakeArraySwapstep=i;Search(step+1);Reverse(0ri);/true:已经排好序/false:未排序/boolIsSorted(int*CakeArray,intnCakeCnt)(for(inti=1;i<nCakeCnt;i+)(if(pCakeArrayi-l>pCakeArrayi)(returnfalse;)returntrue;/翻转烙饼信息/voidRevert(intnBegin,intnEnd)(assert(nEnd>nBegin);inti,j,t;/翻转烙饼信息for(i=nBegin,j=nEnd;i<j;i+,j-)(t=m_ReverseCakeArrayi;m_ReverseCakeArrayi三m_ReverseCakeArrayj;m_ReverseCakeArrayj=t;一)private:int* m_CakeArray; int m_nCakeCnt; int m_nMaxSwap;int* m_SwapArray;/烙饼信息数组/烙饼个数/最多交换次数根据前面的推断.这里最多为/m_nCakeCnt*2/端结果数组int*m_ReverSeCakeArray;/当前翻转烙饼信息数组int*m_ReverSeCakeArraySwap;/当前翻转烙饼交换结果数组intm_nSearch;/当前搜索次数信息）；当烙饼不多的时候，我们已经可以很快地找出最优的翻转方案。还有优化方案吗？我们已经知道怎么构造一个可行的翻转方案，所以最优方案肯定不会比这个差。这个就是我们程序中的上界(UPPerBOImd),就是说，我们感兴趣的最优方案最差也就是上面的方案了。如果我们能够找到一个更好的构造方案，搜索空间就会继续缩小，所以我们一开始就设m_nMaxSwap为UPPerBoUnd,而程序中有一个剪枝：nEstimate=LowerBound(m_ReverseCakeArray,m_n);if(step+nEstimate>m_nMaxSwap)return;m_nMaXSWaP越小，这个剪枝条件就越容易满足，更多的情况就不需要再去搜索。当然，程序也就能更快地找出最优方案。仔细分析上面的剪枝条件，在到达m_R