1. 首页
  2. 面试题库

华为机试题 之 joseph环

发布于 2014-10-15 09:29:58 | 232 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的精品教程，程序狗速度看过来！

华为

华为技术有限公司是一家生产销售通信设备的民营通信科技公司，总部位于中国广东省深圳市龙岗区坂田华为基地。华为的产品主要涉及通信网络中的交换网络、传输网络、无线及有线固定接入网络和数据通信网络及无线终端产品，为世界各地通信运营商及专业网络拥有者提供硬件设备、软件、服务和解决方案。华为于1987年在中国深圳正式注册成立。

一：首先科普一下约瑟夫问题的数学方法 

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

 (2) 为了讨论方便，先把问题稍微改变一下，并不影响原意：  问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:  k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2  并且从k开始报0。     现在我们把他们的编号做一下转换：  k --> 0  k+1 --> 1  k+2 --> 2  ...  ...  k-2 --> n-2  k-1 --> n-1  变换后就完完全全成为了(n-1)个人报数的子问题。

（3）假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！变 回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n  如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式： 

 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]  ；递推公式 ； f[1]=0;  f[i]=(f[i-1]+m)%i; (i>1)  

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1  由于是逐级递推，不需要保存每个f[i]，程序也是异常简单。

二：原题再现：

（1）The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. 

       Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. 

（2） 分析：本题是约瑟夫环变形 先引入Joseph递推公式，设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n- i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人（当前序列编号为0~(n-i));
拿个例子说：K=4,M=30;
f(0)=0;
f(1)=(f(0)+30-1)%8=5; 序列（0,1,2,3,4,5,6,7）中的5
f(2)=(f(1)+30-1)%7=6; 序列（0,1,2,3,4,6,7）中的7
f(3)=(f(2)+30-1)%6=5; 序列（0,1,2,3,4,6）中的6
f(4)=(f(3)+30-1)%5=4; 序列（0,1,2,3,4）中的4
........


依据题意，前K个退出的人必定是后K个人，所以只要前k轮中只要有一次f(i)<k则此m不符合题意。
接下来说说m的取值范围：我们考察一下只剩下k+1个人时候情况，即坏人还有一个未被处决，那么在这一轮中结束位置必定在最后一个坏人，那么开始位置在哪 呢？这就需要找K+2个人的结束位置，然而K+2个人的结束位置必定是第K+2个人或者第K+1个人，这样就出现两种顺序情 况：GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2个人的那一轮退出的人）所以有K+1个人的那一轮的开始位置有两种可能即第一个位置或K+1的那个位置，限定m有两种可能：t(k+1) 或 t(k+1)+1; t>=1; 若遍历每一个m必定超时，避免超时则需要打表和限制m的范围。

（3） 代码如下：

  1. using namespace std;  
  2. const int MAX_SIZE = 14;  
  3.   
  4. int main(void)  
  5. {  
  6.     int joseph[MAX_SIZE]={0};  //打表，保存各个k值对应的m值  
  7.   
  8.     int k;  
  9.     int i;  
  10.     while(cin>>k)  
  11.     {  
  12.         if(0 == k)  
  13.             break;  
  14.         if(joseph[k])// 此k值已经求过直接打印，并下一次循环  
  15.         {  
  16.             cout<<joseph[k]<<endl;  
  17.             continue;  
  18.         }  
  19.   
  20.         int n=2*k;  //总人数  
  21.         int ans[30]={0};  //第i轮杀掉 对应当前轮的编号为ans[i]的人  
  22.                           //PS:每一轮都以报数为“1”的人开始重新编号  
  23.                         // 例如ans[1] = 3 表示第一次把下标为3的人杀掉（其实是第四个人）  
  24.         int m=k+1;    //所求的最少的报数,从k+1开始，因为  
  25.         for(i=1;i<=k;i++)  
  26.         {  
  27.             ans[i] = (ans[i-1]+m-1)%(n-i+1);  
  28.             //cout << ans[i] << ",";// 杀人的原始数组的下标，也相当于erase过程，因为要迁移  
  29.             //如果应用vector的vec[i],vec.erase(iter)就可以实现杀人顺序  
  30.             if(ans[i] < k)// 不符合杀人条件  
  31.             {  
  32.                 i = 0;  
  33.                 m++;// m加一，从i=1再次杀人  
  34.             }  
  35.         }  
  36.         joseph[k] = m;  
  37.         cout << joseph[k] << endl;  
  38.     }  
  39.     return 0;  
  40. }//poj 1012  


三：问题延伸：（更简单的问题）

 

（1）有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。
第一行输入小孩的人数N（N<=64） 
接下来每行输入一个小孩的名字(人名不超过15个字符) 
最后一行输入W,S (W < N)，用逗号","间隔
（2）poj 3750的代码，用list和vector分别实现：
 
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <vector>  
  5. using namespace std;  
  6. const int MAX_SIZE = 20;  
  7.   
  8. int main()  
  9. {  
  10.     int n,w,s;  
  11.     int i,cp;  
  12.     char str[MAX_SIZE];  
  13.     vector<string> vec;  
  14.     scanf("%d",&n);  
  15.     for(i=0;i<n;i++)  
  16.     {  
  17.         cin >> str;  
  18.         vec.push_back(str);  
  19.     }  
  20.     scanf("%d,%d",&w,&s);  
  21.     vector<string>::iterator iter;  
  22.     cp = 1;  
  23.     for(iter=vec.begin()+w-1; vec.begin()!=vec.end();)  
  24.     {  
  25.         cp++;  
  26.         if(iter == vec.end())  
  27.             iter = vec.begin();  
  28.         if(cp<=s)  
  29.         {  
  30.             iter++;  
  31.         }  
  32.         else  
  33.         {  
  34.             cout << *iter << endl;  
  35.             iter = vec.erase(iter);  
  36.             //iter++;// 因为删除iter,自动指向下一个元素的;  
  37.             cp = 1;  
  38.         }  
  39.     }  
  40.   
  41.     return 0;  
  42. }//poj 3750  
  43. */  
  44.   
  45. #include <iostream>  
  46. #include <cstdio>  
  47. #include <cstring>  
  48. #include <list>  
  49. using namespace std;  
  50. const int MAX_SIZE = 20;  
  51.   
  52. int main()  
  53. {  
  54.     int n,w,s;  
  55.     int i,cp;  
  56.     char str[MAX_SIZE];  
  57.     list<string> lists;  
  58.     scanf("%d",&n);  
  59.     for(i=0;i<n;i++)  
  60.     {  
  61.         cin >> str;  
  62.         lists.push_back(str);  
  63.     }  
  64.     scanf("%d,%d",&w,&s);  
  65.     list<string>::iterator iter;  
  66.     iter = lists.begin();  
  67.     while(w>1)  
  68.     {  
  69.         iter++;  
  70.         w--;  
  71.     }  
  72.     cp = 1;  
  73.     for(; lists.size()!=0;)  
  74.     {  
  75.         cp++;  
  76.         if(iter == lists.end())  
  77.             iter = lists.begin();  
  78.         if(cp<=s)  
  79.         {  
  80.             iter++;  
  81.         }  
  82.         else  
  83.         {  
  84.             cout << *iter << endl;  
  85.             iter = lists.erase(iter);// 因为删除iter,自动返回下一个元素的,vector也是一样;否则ter成为野指针  
  86.             cp = 1;  
  87.         }  
  88.     }  
  89.     return 0;  
  90. }//poj 3750 


最新网友评论  共有(0)条评论 发布评论 返回顶部
推荐阅读
  • 终极炫富——2016 年 iOS 开发者收入调查报告
  • 年度大片：Stack Overflow 2017 开发者调查报告发布！
  • 开发者需要大学学位吗？
  • 程序员多大年纪算高龄，届时该何去何从？
  • 2017 年高薪编程语言排行榜，你的语言上榜没？
  • 各编程语言开发者最常使用的按键，中了没?
  • 伤不起的三十岁，干不动的程序员要何去何从？
  • 2016年中国加班最狠IT公司排行
  • 一句话"面试"漫画：黑了苹果、谷歌、三星
  • 拿代码量算 KPI ……跟程序员们来这套？
  • 程序员遇到 Bug 时的 30 个反应，你是哪一种？
  • 2016年收入最高的5个编程语言 Java和C没在前五?
  • 为什么很少见人傻钱多的程序员炫富？
  • 阿里月薪两万是什么体验？
  • 代码缩进时 程序员更喜欢空格键还是Tab键？
    • 最新资讯
  • Python获取系统所有进程PID及进程名称的方法示例
  • Python简单获取网卡名称及其IP地址的方法【基于psutil模块】
  • Python实现的根据IP地址计算子网掩码位数功能示例
  • 好的Python培训机构应该具备哪些条件
  • 详解Pytorch 使用Pytorch拟合多项式(多项式回归)
  • Python加载带有注释的Json文件实例
  • 对python的文件内注释 help注释方法
  • Python实现判断一行代码是否为注释的方法
  • Oracle数据库表中字段顺序的修改方法
  • ASP.NET MVC 4使用PagedList.Mvc分页的实现代码
  • Oracle实例启动时报错：ORA-32004的解决方法
  • 解读ASP.NET 5 & MVC6系列教程（7）：依赖注入
  • 详解IDEA用maven创建springMVC项目和配置
  • ASP.NET MVC5网站开发之展示层架构（五）
  • SpringBoot创建maven多模块项目实战代码
    • 后端技术
    前端技术
    数据库
    热门框架
    常用IDE
    其他
    Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务