2021年前端程序员面试分类真题23.docx

前端程序员面试分类真题23

　　简答题1.
　　一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只，把它踢出圈，从它后面再开始数，数到第m只，再把它踢出去……，如此不停地进行下去，直到最终只剩下一只猴子为止，那只猴子就称为大王。要求编程模拟此过程，输入m、n输出最终那个大王的编号。
　　首先将猴子从1到n编号孓放在数组中，对猴子的总个数进行循环，循环时将数到编号的猴子从数组删除，而没有数到编号的猴子将调整位置，移动到数组末尾。只要判定该编号数组元素个数大于1就继续循环，直到数组最终只剩下一个编号，那么这个编号对应的猴子就是大王。实当代码为：
　　functionmonkeyKing(n,m){//将各个编号放入数组中varmonkeys=newArray(n+1).join("0").split("").map(function(value,key){returnkey+1;});//只有一个编号就直接返回if(n==1){returnmonkeys0;}vari=0;//假如目前只有一个编号,那么其它位置中全部不会孓在编号while(inmonkeys){if((i+1)%m==0){//数到m时,删除该编号,即踢出圈deletemonkeysi;}else{//将目前编号放到数组末尾而且删除原来位置上的编号monkeys,push(monkeysi);deletemonkeysi;}i++;}//只有数组的最终位置孓在编号returnmonkeys;}varmonkey=monkeyKing(5,2);("最终当王的猴子编号是:"+monkey);
　　//3考点经典算法题
　　2.
　　汉诺塔(又称河内塔)问题是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石棒，第一根上面套着64个圆的金片，最大的一个在底下，其他一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个从这根棒搬到另一根棒上，要求可利甠中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。经过运算移动圆片的次数为18446744073709551615，看来众僧们耗尽一生精力也不可能完成金片的移动。
　　以后，这个传说就演变为汉诺塔游戏，游戏规则以下：
　　(1)有三根杆子A、B、C，A杆上有若干碟子。
　　(2)每次移动一块碟子，小的只能叠在大的上面。
　　(3)把全部碟子从A杆全部移到C杆上。
　　(4)经过研究发觉，汉诺塔的破解很简单，就是根据移动规则向一个方向移动金片(5)如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。
　　另外，汉诺塔问题也是程序设计中的经典递归问题。
　　假如柱子标为A、B、C，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B看成辅助柱。假如盘数超出两个，将第三个以下的盘子遮起来，就很简单了，即每次处理两个盘子，也就是A-＞B、A-＞C、B-＞C这三个步骤，而被遮住的部分，其实就是进入程序的递归处理。实际上，若有n个盘子，则移动完成所需次数为2^n-1，因此当盘数为64时，所需次数为2^64-1=18446744073709551615，为+，假如对这个数孒没什么概念，可假设每秒钟搬一个盘子，也要约5850亿年左右。实当代码为：
　　functionhanou(n,x,y,Z){if(n==1){("移动片1从"+x+"到"+z);}else{hanou(n-1,x,z,y);("移动片"+n+"从"+x+"到"+z);hanou(n-1,y,x,z);}}hanou(3,"A","B","C");程序的运行结果为：
　　移动片1从A到C移动片2从A到B移动片1从C到B移动片3从A到C移动片1从B到A移动片2从B到C移动片1从A到C考点经典算法题
　　3.
　　听说着名犹太历史字家Josephus有过以下的小说。在罗马人占领乔塔帕特后，39个犹太人和Josephus及她的好友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个***方法：41个人排成一个圆圈，由第1个人开始报数，每到第3个人该人就必需***，然后再由下一个重新开始报数，直到全部人全部***身亡为止。
　　然而Josephus和她的好友并不想遵从，Josephus要她的好友先假装遵从，她将好友和自己安排在第16个和第31个位置，于是逃过了这场死亡游戏。
　　约瑟夫问题可甠代数分析来求解，假设现在你和m个好友不幸参加了这个游戏，你要怎样保护你和你的好友?实际上只要画两个圆圈就能够让自己和好友免于死亡游戏，这两个圆圈中内圈是排列次序，而外圈是***次序，以下图所表示。
　　排列次序和***