.NET 面试题汇总(二) net面试100题及答案

bigegpt 2024-10-13 01:17 6 浏览

今天小编分享一个猴子争大王的机试题，这题考察了对链表的理解和设计算法的能力。

猴子选大王问题是一个十分经典的算法问题，这个问题是这样的：一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

这个问题要解决起来并不难，但求解的方法很多；题目的变化形式也很多，而我们统称这类问题为约瑟夫问题。这类题目基本的描述为：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。下面我们先来分析一下解决这类问题的几个步骤。

（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。

（2）开始时每个人都是活的，所以数组初值全部赋为false。

（3）模拟杀人过程，直到所有人都被杀死为止。

题目中N个人围成一圈，因而启发我们用一个循环的链来表示，可以使用数组结构来构成一个循环链表。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被杀死的标记，为1表示还存活。从第一个人开始对还存活的人进行计数，每数到M时，将结构中的标记改为0，表示该人已被杀死。这样循环计数直到有15个人被杀死为止。

但是，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。

核心代码：

public int King(int M, int N)

{

//总人数 M ，数到第 N 个排除。

int k=0;

for (int i = 2; i <= M; i++)

k = (k + N) % i;

return ++k;

}

分析：

在n（0、1、2、3、……、n-1）只猴子中,假定报数m的猴子被删除，

则第一只被删除的猴子编号为（m-1）%n,记为k，那么删除k之后剩下的n-1只猴子为0、1、……、k-1、k+1、……、n-1,并且下一次是从k+1开始计数。

相当于在剩下的序列种，k+1排在最前面，从而形成k+1、……、n-1、0、1、……、k-1。

接下来将剩下的这n-1个数字的序列k+1、……、n-1、0、1、……、k-1映射形成一个从0到n-2的序列0、1、2、……、n-2。

把映射定义为p，则p(x)=(x-k-1)%n。

逆过来0、1、2、……、n-2映射为k+1、……、n-1、0、1、……、k-1，时则p’(x)=(x+k+1)%n，而k=(m-1)%n,故p’(x)=(x+m)%n。

最后一只猴子的编号为0，故x=0,n=1。例如当m=3时，p’(0)=(0+3)%1=3,表示最后一只猴大王在倒数第二轮（编号也是从0开始）中编号为3。

看完本文有收获？请转发分享给更多人!!!如果你有更好的答案，欢迎大家点赞，留言讨论，喜欢这篇文章可以分享给更多人，关注我每天更新分享有关程序员、科技、编程之类的文章！！！爱你们，，么么哒，，让我们一起愉快的玩耍把！！！

.net面试题

上一篇：面试 | .NET基础知识快速通关(9) net开发面试基础知识
下一篇：面试 | .NET基础知识快速通关(1) 面试零基础怎么学

.NET 面试题汇总(二) net面试100题及答案

相关推荐

idea本地配置连接远程hadoop集群的一些网络问题解决汇总

无缓存不行?例行升级的入门级阿斯加特AN2 SSD装机点评

Ceph运维手册(基于P版本)

Docker 命令大全（docker命令大全记录表）

替代Docker build的Buildah简单介绍

Docker Desktop安装使用指南:零基础教程

大数据开发前要做什么准备?8台Hadoop服务器进行集群规划前配置

Tensorflow分类loss函数总结 tensorflow绘制loss曲线

R语言学习笔记(七) -离散型数据的模型预测2

iOS Runtime详解