1/21
文档分类:资格/认证考试

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


下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
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个好友不幸参加了这个游戏,你要怎样保护你和你的好友?实际上只要画两个圆圈就能够让自己和好友免于死亡游戏,这两个圆圈中内圈是排列次序,而外圈是***次序,以下图所表示。
  排列次
内容来自淘豆网www.taodocs.com转载请标明出处.
非法内容举报中心
文档信息