加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 编程之美

编程之美.pdf

编程之美

天过雨不晴
2011-05-19 0人阅读 举报 0 0 暂无简介

简介:本文档为《编程之美pdf》,可适用于人文社科领域

第章游戏之乐游戏中碰到的题目让CPU占用率曲线听你指挥中国象棋将帅问题一摞烙饼的排序买书问题快速找出故障机器饮料供货光影切割问题小飞的电梯调度算法高效率地安排见面会双线程高效下载NIM()一排石头的游戏NIM()“拈”游戏分析NIM()两堆石头的游戏连连看游戏设计构造数独点游戏俄罗斯方块游戏挖雷游戏第章数字之魅数字中的技巧求二进制数中的个数不要被阶乘吓倒寻找发帖“水王”的数目寻找最大的K个数精确表达浮点数最大公约数问题找符合条件的整数斐波那契(Fibonacci)数列寻找数组中的最大值和最小值寻找最近点对快速寻找满足条件的两个数子数组的最大乘积求数组的子数组之和的最大值子数组之和的最大值(二维)求数组中最长递增子序列数组循环移位数组分割区间重合判断程序理解和时间分析只考加法的面试题第章结构之法字符串及链表的探索字符串移位包含的问题电话号码对应英语单词计算字符串的相似度从无头单链表中删除节点最短摘要的生成编程判断两个链表是否相交队列中取最大值操作问题求二叉树中节点的最大距离重建二叉树分层遍历二叉树程序改错第章数学之趣数学游戏的乐趣金刚坐飞机问题瓷砖覆盖地板买票找零点是否在三角形内磁带文件存放优化桶中取黑白球蚂蚁爬杆三角形测试用例数独知多少数字哑谜和回文挖雷游戏的概率让CPU占用率曲线听你指挥编程之美微软技术面试心得《编程之美微软技术面试心得》《编程之美微软技术面试心得》(http:wwwchinapubcom)是微软亚洲研究院技术创新组研发主管邹欣继《移山之道VSTS软件开发指南》后的最新力作。它传达给读者:微软重视什么样的能力需要什么样的人才。但它更深层的意义在于引导读者思考提倡一种发现问题、解决问题的思维方式充分挖掘编程的乐趣展示编程之美。本书月份上市。网上讨论和解答在:wwwmsracnbop   题目《让CPU占用率曲线听你指挥》问题写一个程序让用户来决定Windows任务管理器(TaskManager)的CPU占用率。程序越精简越好计算机语言不限。例如可以实现下面三种情况:CPU的占用率固定在为一条直线CPU的占用率为一条直线但是具体占用率由命令行参数决定(参数范围~)让CPU占用率曲线听你指挥编程之美微软技术面试心得CPU的占用率状态是一个正弦曲线。分析与解法有一名学生写了如下的代码:while(true){if(busy)ielse}然后她就陷入了苦苦思索:else干什么呢?怎么才能让电脑不做事情呢?CPU使用率为的时候到底是什么东西在用CPU?另一名学生花了很多时间构想如何“深入内核以控制CPU占用率”可是事情真的有这么复杂么?MSRATTG(MicrosoftResearchAsia,TechnologyTransferGroup)的一些实习生写了各种解法他们写的简单程序可以达到如图所示的效果。图编码控制CPU占用率呈现正弦曲线形态看来这并不是不可能完成的任务。让我们仔细地回想一下写程序时曾经碰到的问题如作者注:当面试的同学听到这个问题的时候很多人都有点意外。我把我的笔记本电脑交给他们说这是开卷考试你可以上网查资料干什么都可以。大部分面试者在电脑上的第一个动作就是上网搜索“CPU控制”这样的关键字当然没有找到什么直接的结果。不过这本书出版以后情况可能就不一样了。让CPU占用率曲线听你指挥编程之美微软技术面试心得果我们不小心写了一个死循环CPU占用率就会跳到最高并且一直保持。我们也可以打开任务管理器实际观测一下它是怎样变动的。凭肉眼观察它大约是秒钟更新一次。一般情况下CPU使用率会很低。但是当用户运行一个程序执行一些复杂操作的时候CPU的使用率会急剧升高。当用户晃动鼠标时CPU的使用率也有小幅度的变化。那当任务管理器报告CPU使用率为的时候谁在使用CPU呢?通过任务管理器的“进程(Process)”一栏可以看到SystemIdleProcess占用了CPU空闲的时间这时候大家该回忆起在“操作系统原理”这门课上学到的一些知识了吧。系统中有那么多进程它们什么时候能“闲下来”呢?答案很简单这些程序或者在等待用户的输入或者在等待某些事件的发生(WaitForSingleObject())或者进入休眠状态(通过Sleep()来实现)。在任务管理器的一个刷新周期内CPU忙(执行应用程序)的时间和刷新周期总时间的比率就是CPU的占用率也就是说任务管理器中显示的是每个刷新周期内CPU占用率的统计平均值。因此我们写一个程序让它在任务管理器的刷新期间内一会儿忙一会儿闲然后通过调节忙闲的比例就可以控制任务管理器中显示的CPU占用率。【解法一】简单的解法步骤要操纵CPU的usage曲线就需要使CPU在一段时间内(根据TaskManager的采样率)跑busy和idle两个不同的loop从而通过不同的时间比例来获得调节CPUUsage的效果。步骤Busyloop可以通过执行空循环来实现idle可以通过Sleep()来实现。问题的关键在于如何控制两个loop的时间方法有二:Sleep一段时间然后以for循环n次估算n的值。那么对于一个空循环for(i=i<ni)又该如何来估算这个最合适的n值呢?我们都知道CPU执行的是机器指令而最接近于机器指令的语言是汇编语言所以我们可以先把这个空循环简单地写成如下汇编代码后再进行分析:loop:movdxi将i置入dx寄存器incdx将dx寄存器加movidx将dx中的值赋回icmpin比较i和njlloopi小于n时则重复循环假设这段代码要运行的CPU是PGhz(*的次方个时钟周期每秒)。现代CPU每个时钟周期可以执行两条以上的代码那么我们就取平均值两条于是让(*)=(循环秒)也就是说CPU秒钟可以运行这个空循环次。不过我们还是不能简单地将n=然后Sleep()了事。如果我们让CPU工如果应聘者从来没有琢磨过任务管理器那还是不要在简历上说“精通Windows”为好。让CPU占用率曲线听你指挥编程之美微软技术面试心得作秒钟然后休息秒钟波形很有可能就是锯齿状的先达到一个峰值(大于>)然后跌到一个很低的占用率。我们尝试着降低两个数量级令n=而睡眠时间相应改为毫秒(Sleep())。用毫秒是因为它不大也不小比较接近Windows的调度时间片。如果选得太小(比如毫秒)则会造成线程频繁地被唤醒和挂起无形中又增加了内核时间的不确定性影响。最后我们可以得到如下代码:代码清单intmain(){for(){for(inti=i<i)Sleep()}return}在不断调整的参数后我们就可以在一台指定的机器上获得一条大致稳定的CPU占用率直线。使用这种方法要注意两点影响:尽量减少sleepawake的频率如果频繁发生影响则会很大因为此时优先级更高的操作系统内核调度程序会占用很多CPU运算时间。尽量不要调用systemcall(比如IO这些privilegeinstruction)因为它也会导致很多不可控的内核运行时间。该方法的缺点也很明显:不能适应机器差异性。一旦换了一个CPU我们又得重新估算n值。有没有办法动态地了解CPU的运算能力然后自动调节忙闲的时间比呢?请看下一个解法。【解法二】使用GetTickCount()和Sleep()我们知道GetTickCount()可以得到“系统启动到现在”的毫秒值最多能够统计到天。另外利用Sleep()函数最多也只能精确到毫秒。因此可以在“毫秒”这个量级做操作和比较。具体如下:利用GetTickCount()来实现busyloop的循环用Sleep()实现idleloop。伪代码如下:代码清单intbusyTime=msintidleTime=busyTimesameratiowillleadtocpuusage让CPU占用率曲线听你指挥编程之美微软技术面试心得IntstartTime=while(true){startTime=GetTickCount()busyloop的循环while((GetTickCount()startTime)<=busyTime)idleloopSleep(idleTime)}这两种解法都是假设目前系统上只有当前程序在运行但实际上操作系统中有很多程序都会在不同时间执行各种各样的任务如果此刻其他进程使用了的CPU那我们的程序应该只能使用的CPU(而不是机械地占用)这样可达到的效果。怎么做呢?我们得知道“当前CPU占用率是多少”这就要用到另一个工具来帮忙Perfmonexe。Perfmon是从WindowsNT开始就包含在Windows服务器和台式机操作系统的管理工具组中的专业监视工具之一(如图所示)。Perfmon可监视各类系统计数器获取有关操作系统、应用程序和硬件的统计数字。Perfmon的用法相当直接只要选择您所要监视的对象(比如:处理器、RAM或硬盘)然后选择所要监视的计数器(比如监视物理磁盘对象时的平均队列长度)即可。还可以选择所要监视的实例比如面对一台多CPU服务器时可以选择监视特定的处理器。图系统监视器(Perfmon)我们可以写程序来查询Perfmon的值MicrosoftNetFramework提供了PerformanceCounter()这一类型从而可以方便地拿到当前各种计算机性能数据包括CPU的使用率。例如下面这个程序【解法三】能动态适应的解法让CPU占用率曲线听你指挥编程之美微软技术面试心得代码清单C#codestaticvoidMakeUsage(floatlevel){PerformanceCounterp=newPerformanceCounter("Processor","ProcessorTime","Total")while(true){if(pNextValue()>level)SystemThreadingThreadSleep()}}可以看到上面的解法能方便地处理各种CPU使用率参数。这个程序可以解答前面提到的问题。有了前面的积累我们应该可以让任务管理器画出优美的正弦曲线了见下面的代码。【解法四】正弦曲线代码清单Ccodetomaketaskmanagergeneratesinegraph#include"Windowsh"#include"stdlibh"#include"mathh"constdoubleSPLIT=constintCOUNT=constdoublePI=constintINTERVAL=inttmain(intargc,TCHAR*argv){DWORDbusySpanCOUNTarrayofbusytimesDWORDidleSpanCOUNTarrayofidletimesinthalf=INTERVALdoubleradian=for(inti=i<COUNTi){busySpani=(DWORD)(half(sin(PI*radian)*half))idleSpani=INTERVALbusySpaniradian=SPLIT}DWORDstartTime=intj=while(true){j=jCOUNTstartTime=GetTickCount()while((GetTickCount()startTime)<=busySpanj)Sleep(idleSpanj)j}return}让CPU占用率曲线听你指挥编程之美微软技术面试心得讨论如果机器是多CPU上面的程序会出现什么结果?如何在多个CPU时显示同样的状态?例如在双核的机器上如果让一个单线程的程序死循环能让两个CPU的使用率达到的水平么?为什么?多CPU的问题首先需要获得系统的CPU信息。可以使用GetProcessorInfo()获得多处理器的信息,然后指定进程在哪一个处理器上运行。其中指定运行使用的是SetThreadAffinityMask()函数。另外还可以使用RDTSC指令获取当前CPU核心运行周期数。在x平台上定义函数:inlineintGetCPUTickCount(){asm{rdtsc}}在x平台上定义:#defineGetCPUTickCount()rdtsc()使用CallNtPowerInformationAPI得到CPU频率从而将周期数转化为毫秒数例如:代码清单PROCESSORPOWERINFORMATIONinfoCallNTPowerInformation(,queryprocessorpowerinformation,noinputbuffer,inputbuffersizeiszeroinfo,outputbufferSizeof(info))outbufsizeinttbegin=GetCPUTickCount()dosomethinginttend=GetCPUTickCount()doublemillisec=((double)tend–(double)tbegin)(double)infoCurrentMhzRDTSC指令读取当前CPU的周期数在多CPU系统中这个周期数在不同的CPU之间基数不同频率也有可能不同。用从两个不同的CPU得到的周期数作计算会得出没有意义的值。如果线程在运行中被调度到了不同的CPU就会出现上述情况。可用SetThreadAffinityMask避免线程迁移。另外CPU的频率会随系统供电及负荷情况有所调整。总结能帮助你了解当前线程进程系统效能的API大致有以下这些:让CPU占用率曲线听你指挥编程之美微软技术面试心得Sleep()这个方法能让当前线程“停”下来。WaitForSingleObject()自己停下来等待某个事件发生GetTickCount()有人把Tick翻译成“嘀嗒”很形象。QueryPerformanceFrequency()、QueryPerformanceCounter()让你访问到精度更高的CPU数据。timeGetSystemTime()是另一个得到高精度时间的方法。PerformanceCounter效能计数器。GetProcessorInfo()SetThreadAffinityMask()。遇到多核的问题怎么办呢?这两个方法能够帮你更好地控制CPU。GetCPUTickCount()。想拿到CPU核心运行周期数吗?用用这个方法吧。了解并应用了上面的API就可以考虑在简历中写上“精通Windows”了。写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp中国象棋将帅问题★★★下过中国象棋的朋友都知道双方的“将”和“帅”相隔遥远并且它们不能照面。在象棋残局中许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图所示)(为了下面叙述方便我们约定用A表示“将”B表示“帅”):图A、B二子被限制在己方×的格子里运动。例如,在如上的表格里A被正方形{d,f,d,f}包围而B被正方形{d,f,d,f}包围。每一步A、B分别可以横向或纵向移动一格但不能沿对角线移动。另外A不能面对B也就是说A和B不能处于同一纵向直线上(比如A在d的位置那么B就不能在d、d以及d)。请写出一个程序输出A、B所有合法位置。要求在代码中只能使用一个变量。写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp分析与解法问题的本身并不复杂只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量所以必须首先想清楚在写代码的时候有哪些信息需要存储并且尽量高效率地存储信息。稍微思考一下可以知道这个程序的大体框架是:遍历A的位置遍历B的位置判断A、B的位置组合是否满足要求。如果满足则输出。因此需要存储的是A、B的位置信息并且每次循环都要更新。为了能够进行判断首先需要创建一个逻辑的坐标系统以便检测A何时会面对B。这里我们想到的方法是用~的数字按照行优先的顺序来表示每个格点的位置(如图所示)。这样只需要用模余运算就可以得到当前的列号从而判断A、B是否互斥。图用~的数字表示A、B的坐标第二题目要求只用一个变量但是我们却要存储A和B两个子的位置信息该怎么办呢?可以先把已知变量类型列举一下然后做些分析。对于bool类型估计没有办法做任何扩展了因为它只能表示true和false两个值而byte或者int类型它们能够表达的信息则更多。事实上对本题来说每个子都只需要个数字就可以表达它的全部位置。一个位的byte类型能够表达=个值所以用它来表示A、B的位置信息绰绰有余因此可以把这个字节的变量(设为b)分成两部分。用前面的bit表示A的位置用后面的bit表示B的位置那么个bit可以表示个数这已经足够了。问题在于:如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。下面是做法:„将byteb()的右边bit()设为n():首先清除b右边的bits同时保持左边的bits:写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp(LMASK)(b)然后将上一步得到的结果与n做或运算(LMASKb)^(n)„将byteb()左边的bit()设为n():首先清除b左边的bits同时保持右边的bits:(RMASK)(b)现在把n移动到byte数据的左边n<<=然后对以上两步得到的结果做或运算从而得到最终结果。(RMASKb)^(n<<)写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp„得到byte数据的右边bits或左边bits(eg中的以及):清除b左边的bits同时保持右边的bits(RMASK)(b)清除b的右边的bits同时保持左边的bits(LMASK)(b)将结果右移bits>>=最后的挑战是如何在不声明其他变量约束的前提下创建一个for循环。可以重复利用byte的存储单元把它作为循环计数器并用前面提到的存取和读入技术进行操作。还可以用宏来抽象化代码例如:for(LSET(b,)LGET(b)<=GRIDW*GRIDWLSET(b,(LGET(b))))【解法一】代码清单#defineHALFBITSLENGTH这个值是记忆存储单元长度的一半在这道题里是bit#defineFULLMASK这个数字表示一个全部bit的mask在二进制表示中它是。#defineLMASK(FULLMASK<<HALFBITSLENGTH)这个宏表示左bits的mask在二进制表示中它是。#defineRMASK(FULLMASK>>HALFBITSLENGTH)这个数字表示右bits的mask在二进制表示中它表示。#defineRSET(b,n)(b=((LMASKb)^n))这个宏将b的右边设置成n#defineLSET(b,n)(b=((RMASKb)^(n<<HALFBITSLENGTH)))这个宏将b的左边设置成n#defineRGET(b)(RMASKb)这个宏得到b的右边的值#defineLGET(b)((LMASKb)>>HALFBITSLENGTH)这个宏得到b的左边的值#defineGRIDW这个数字表示将帅移动范围的行宽度。#include<stdioh>#defineHALFBITSLENGTH#defineFULLMASK#defineLMASK(FULLMASK<<HALFBITSLENGTH)#defineRMASK(FULLMASK>>HALFBITSLENGTH)#defineRSET(b,n)(b=((LMASKb)^n))#defineLSET(b,n)(b=((RMASKb)^(n<<HALFBITSLENGTH)))#defineRGET(b)(RMASKb)#defineLGET(b)((LMASKb)>>HALFBITSLENGTH)#defineGRIDW写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMaspintmain(){unsignedcharbfor(LSET(b,)LGET(b)<=GRIDW*GRIDWLSET(b,(LGET(b))))for(RSET(b,)RGET(b)<=GRIDW*GRIDWRSET(b,(RGET(b))))if(LGET(b)GRIDW!=RGET(b)GRIDW)printf("A=d,B=dn",LGET(b),RGET(b))return}【输出】格子的位置用N来表示N=,,…,,依照行优先的顺序如图所示:“将”(A)的格子“帅”(B)的格子图写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMaspA=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=A=,B=考虑了这么多因素总算得到了本题的一个解法但是MSRA里却有人说下面的一小段代码也能达到同样的目的:BYTEi=while(i){if(i==i)continueprintf(“A=d,B=dn”,i,i)}但是很快又有另一个人说他的解法才是效率最高的:写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp代码清单struct{unsignedchara:unsignedcharb:}ifor(ia=ia<=ia)for(ib=ib<=ib)if(ia==ib)printf(“A=d,B=dn”,ia,ib)读者能自己证明一下么?这一题目由微软亚洲研究院工程师MattScott提供他在学习中国象棋的时候想出了这个题目后来一位应聘者给出了比他的“正解”简明很多的答案他们现在成了同事。写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp饮料供货★★★在微软亚洲研究院上班大家早上来的第一件事是干啥呢?查看邮件?No是去水房拿饮料:酸奶豆浆绿茶、王老吉、咖啡、可口可乐……(当然还是有很多同事把拿饮料当做第二件事)。管理水房的阿姨们每天都会准备很多的饮料给大家为了提高服务质量她们会统计大家对每种饮料的满意度。一段时间后阿姨们已经有了大批的数据。某天早上当实习生小飞第一个冲进水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鲜橙多时阿姨们逮住了他要他帮忙。从阿姨们统计的数据中小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞STC(SmartTeaCorp)负责给研究院供应饮料每天总量为V。STC很神奇他们提供的每种饮料之单个容量都是的方幂比如王老吉都是=升的可乐都是=升的。当然STC的存货也是有限的这会是每种饮料购买量的上限。统计数据中用饮料名字、容量、数量、满意度描述每一种饮料。那么小飞如何完成这个任务求出保证最大满意度的购买量呢?写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp分析与解法【解法一】我们先把这个问题“数学化”一下吧。假设STC共提供n种饮料用(Si、Vi、Ci、Hi、Bi)(对应的是饮料名字、容量、可能的最大数量、满意度、实际购买量)来表示第i种饮料(i=,,…,n)其中可能的最大数量指如果仅买某种饮料的最大可能数量比如对于第i中饮料Ci=VVi。基于如上公式:饮料总容量为总满意度为那么题目的要求就是在满足条件=V的基础上求解max{}。对于求最优化的问题我们来看看动态规划能否解决。用Opt(V',i)表示从第i,i,i,…,n,n种饮料中算出总量为V'的方案中满意度之和的最大值。因此Opt(V,n)就是我们要求的值。那么我们可以列出如下的推导公式:Opt(V',i)=max{k*HiOpt(V'Vi*k,i)}(k=,,…,Ci,i=,,…,n)。即:最优化的结果=选择第k种饮料×满意度减去第k种饮料×容量的最优化结果根据这样的推导公式我们列出如下的初始边界条件:Opt(,n)=即容量为的情况下最优化结果为。Opt(x,n)=INF(x!=)(–INF为负无穷大)即在容量不为的情况下把最优化结果设为负无穷大并把它作为初值。那么根据以上的推导公式就不难列出动态规划求解代码如下所示:代码清单intCal(intV,inttype){optT=边界条件for(inti=i<=Vi)边界条件{optiT=INF}for(intj=Tj>=j){for(inti=i<=Vi){写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMaspoptij=INFfor(intk=k<=Cjk)遍历第j种饮料选取数量k{if(i<=k*Vj){break}intx=optik*Vjjif(x!=INF){x=Hj*kif(x>optij){optij=x}}}}}returnoptV}在上面的算法中空间复杂度为O(V*N)时间复杂度约为O(V*N*Max(Ci))。因为我们只需要得到最大的满意度则计算optij的时候不需要optij只需要optij和optij所以空间复杂度可以降为O(v)。写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp【解法二】应用上面的动态规划法可以得到结果那么是否有可能进一步地提高效率呢?我们知道动态规划算法的一个变形是备忘录法备忘录法也是用一个表格来保存已解决的子问题的答案并通过记忆化搜索来避免计算一些不可能到达的状态。具体的实现方法是为每个子问题建立一个记录项。初始化时该纪录项存入一个特殊的值表示该子问题尚未求解。在求解的过程中对每个待求解的子问题首先查看其相应的纪录项。若记录项中存储的是初始化时存入的特殊值则表示该子问题是第一次遇到此时计算出该子问题的解并保存在其相应的记录项中。若记录项中存储的已不是初始化时存入的初始值则表示该子问题已经被计算过其相应的记录项中存储的是该子问题的解答。此时只需要从记录项中取出该子问题的解答即可。因此我们可以应用备忘录法来进一步提高算法的效率。代码清单intVTopt子问题的记录项表假设从i到T种饮料中找出容量总和为V’的一个方案快乐指数最多能够达到opt(V'iT)存储于optV’i初始化时opt中存储值为表示该子问题尚未求解。intCal(intV,inttype){if(type==T){if(V==)returnelsereturnINF}if(V<)returnINFelseif(V==)returnelseif(optVtype!=)returnoptVtype该子问题已求解则直接返回子问题的解子问题尚未求解则求解该子问题intret=INFfor(inti=i<=Ctypei){inttemp=Cal(V–i*Ctype,type)if(temp!=INF){temp=Htype*iif(temp>ret)ret=temp}}returnoptVtype=ret}【解法三】写书评赢取《编程之美微软技术面试心得》wwwieeeorgcnBCZMasp请注意这个题目的限制条件看看它能否给我们一些特殊的提示。我们把信息重新整理一下按饮料的容量(单位为L)排序:VolumeTotalCountHappinessLTCHLTCHLTCHLTCMHM假设最大容量为L。一开始如果V()非零那么我们肯定需要购买L容量的饮料至少一瓶。在这里可以使用贪心规则购买快乐指数最高的一瓶。除去这个我们只要再购买总量(V)L的饮料就可以了。这时如果我们要购买L容量的饮料怎么办呢?除了L容量里面快乐指数最高的我们还应该考虑两个容量为L的饮料组合的情况。其实我们可以把剩下的容量为L的饮料之快乐指数从大到小排列并用最大的两个快乐指数组合出一个新的“容量为L”的饮料。不断地这样使用贪心原则即得解。这是不是就简单了很多呢?如果各种饮料数量都无限的话这种方法是很简单。但是如果饮料有个数限制复杂度可能达到指数级您有更好的办法么?题目NIM“拈”游戏分析NIM“拈”游戏分析问题有N块石头和两个玩家A和B玩家A先将石头分成若干堆然后按照BABA……的顺序不断轮流取石头能将剩下的石头一次取光的玩家获胜。每次取石头时每个玩家只能从若干堆石头中任选一堆取这一堆石头中任意数目(大于)个石头。请问:玩家A有必胜策略吗?要怎么分配和取石头才能保证自己有把握取胜?解法与分析据说该游戏起源于中国英文名字叫做“NIM”是由广东话“拈”(取物之意)音译而来经由当年到美洲打工的华人流传出去这个游戏一个常见的变种是将十二枚硬币分三列排成再开始玩。我们这里讨论的是一般意义上的“拈”游戏。言归正传在面试者咄咄逼人的目光下你要如何着手解决这个问题?在面试中面试者考察的重点不是“what”能否记住某道题目的解法某件历史事件发生的确切年代C语言中关于类的继承的某个规则的分支等。面试者很想知道的是“how”应聘者是如何思考和学习的。所以应聘者得展现自己的思路。解答这类问题应从最基本的特例开始分析。我们用N表示石头的堆数M表示总的石头数目。当N=时即只有一堆石头显然无论你放多少石头你的对手都能一次全拿光你不能这样摆。当N=时即有两堆石头最简单的情况是每堆石头中各有一个石子()先让对手拿无论怎样你都可以获胜。我们把这种在双方理性走法下你一定能够赢的编程之美微软技术面试心得第章游戏之美局面叫作安全局面。当N=M>时既然(,)是安全局面那么(,X)都不是安全局面因为对手只要经过一次转换就能把(,X)变成(,)然后该你走你就输了。既然(,X)不安全那么(,)如何?经过分析()是安全的因为它不能一步变成()这样的安全局面。这样我们似乎可以推理(,)、(,)一直到(X,X)都是安全局面。于是我们初步总结如果石头的数目是偶数就把它们分为两堆每堆有同样多的数目。这样无论对手如何取你只要保证你取之后是安全局面(X,X)你就能赢。好如果石头数目是奇数个呢?当M=的时候有两种情况(,)、(,,)这两种情况都会是先拿者赢。当M=的时候和M=类似。无论你怎么摆都会是先拿者赢。若M=呢?情况多起来了头有些晕了好像也是先拿者赢。我们在这里得到一个很重要的阶段性结论:当摆放方法为(,,…,)的时候如果的个数是奇数个则先拿者赢如果的个数是偶数个则先拿者必输。当摆放方法为(,,…,,X)(多个加上一个大于的X)的时候先拿者必赢。因为:如果有奇数个先拿者可以从(X)这一堆中一次拿走X个剩下偶数个接下来动手的人必输。如果有偶数个加上一个X先拿者可以一次把X都拿光剩下偶数个接下来动手的人也必输。当然游戏是两个人玩的还有其他的各种摆法例如当M=的时候我们可以摆为(,,)、(,,)、(,,)等等这么多堆石头它们既互相独立又互相牵制那如何分析得出致胜策略呢?关键是找到在这一系列变化过程中有没有一个特性始终决定着输赢。这个时候就得考验一下真功夫了我们要想想大学一年级数理逻辑课上学的异或(XOR)运算。异或运算规则如下:编程之美微软技术面试心得题目NIM“拈”游戏分析XOR(,)=XOR(,)=XOR(,)=首先我们看整个游戏过程我们从N堆石头(M,M,…,Mn)开始双方斗智斗勇石头一直递减到全部为零(,,…,)。当M为偶数的时候我们的取胜策略是把M分成相同的两份这样就能取胜。开始:(M,M)它们异或的结果是XOR(M,M)=中途:(M,M)对手无论怎样从这堆石头中取XOR(M,M)!=我方:(M,M)我方还是把两堆变相等。XOR(M,M)=…最后:(M,M)我方取胜类似的若M为奇数我们把石头分成(,,…,)奇数堆的时候XOR(,,…,)奇数个!=。而这时候对方可以取走一整堆XOR(,,…,)偶数个=如此下去我方必输。我们推广到M为奇数但是每堆石头的数目不限于的情况看看XOR值的规律:开始:(M,M,…,Mn)XOR(M,M,…Mn)=?中途:(M’,M’,…Mn’)XOR(M’,M’,…Mn’)=?最后:(,,…,)XOR(…)=

用户评价(11)

点击加载更多内容
关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/18

编程之美

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利