数据结构 解答报数问题
数字职场
报数题，是经典的数据结构概念题，也是标准的算法测试题。一般编程类的教材中，都会提及此类题，如果在应聘考试看到这类题，感觉很简单立即就答题，可能会出错。下面，我们以一道经典的多家公司都用过的报数题为例，讲解如何解答报数问题。
题目：n个人围成一圈，从1开始报数，报到3的出列，最后剩谁？用数据结构完成设计。
剖析：本题是课本中的题目，学过的人应该有很多，用算法就可以完成设计，不过本题的精髓是“用数据结构完成设计”，忽视这点就会出错。本题的解题思路是，定义一个过程make，过程的功能是每隔两个人就踢一个人（判断间隔两个数组元素的值为1则把下一个元素的值写0），然后此过程反复调用自己，重新判断每个人的状态，每隔两个状态为1的人就将下一个人的状态标志为0，直到所有人全部被踢出去，将最后一个被踢出去的人挑选出来（见图）。
解题步骤
第一步：初始化所有人的状态
先对每个人在圆圈中的状态（是否出列）赋初值，设定每个人的初始状态为未出列，因此对数组每个元素的值写1，关键代码如下所示（完整代码下载地址：http://www.shudoo.com/bzsoft）：
#include
#include
using namespace std;
int main（）
{
int n，m，c=0，pos;//参与人数为n，间隔人数为m，踢人次数为c，前进为pos.
cout<<"请输入总人数"< cin>>n; cout<<"请输入要隔几个人:"< cin>>m; int *base=new int[n]; for（int i=0;i pos=m-1; make（base，n，pos，c，m）; 当踢人操作（把数组元素的值写0）完成后，判断下一个人是否已经出列就采用判断base[pos]的值是否为1，如果为1，则pos加1指向下一个人并再判断下一个人是否出列，如果执行了两次base[pos]的值为1，表示间隔了两个没有出列的人，此时就可以让下一个人出列了，对下一个数组元素进行赋值为0的操作，反复执行这个过程，直到最后一个人出列，最后一个元素在数组中的位置（下标）就是本题答案。关键代码如下所示（完整代码下载地址：http://www.shudoo.com/bzsoft）： void make（int *base，int n，int pos，int c，int m）// base数组名，n数组长度。pos控制base的下标。c计算踢人次数。m间隔人数 { int j=0; cout<<"No. "<<++c<<" 第"< base[pos]=0;//踢掉 if（c==n）return; //出口 while（j-m） { pos=（pos+1）%n; //pos累加，如果累加到n，则为0 if（base[pos]） j++;//如果base[pos]状态值为1，则j加1，当j++执行两次后表示间隔两人了，此时需要踢下一个人，采用递归进行踢人操作 } make（base，n，pos，c，m）;//递归 } 很多数据结构的书，都采用C++或Java语言编写，所以有很多学生朋友在答题的时候会回忆书中的语句。其实，在书中找语句是大忌！考官想看到的是你的真实能力，而不是标准化答案。比如本题的解题方法有很多，可以使用顺序存储（数组）、链表存储、队列等多种方式。 此外，在应聘中要突出思维——“新、细、宽”，即对题目的解答方向要“新颖”，对题目的处理环节分析要“细致”，对答题的领域分析要“宽广”，这是获得一个好印象的基础。如果你的答题是大众化的，那出现高分是不可能的。 还有一点要说明，语言处理能力要突出语句清晰，而不是算法的清晰；很多人往往会认为算法掌握得越多，应聘时越有利，其实，这是一个误区；在实际工作中，往往要求的是清晰、可更新、可交互的语句表述，而不是算法的表现。对于考官而言，他要求的是你的代码段可以清晰地告诉他：思路是可行的，也是很高效的。第二步：每隔两个人踢一个人
我的建议>>