约瑟夫问题方法总结

n个人围成一个圈,每个人分别标注为1、2、...、n,要求从1号从1开始报数,报到k的人出圈,接着下一个人又从1开始报数,如此循环,直到只剩最后一个人时,该人即为胜利者。例如当n=10,k=4时,依次出列的人分别为4、8、2、7、3、10,9、1、6、5,则5号位置的人为胜利者。给定n个人,请你编程计算出最后胜利者标号数。(要求用单循环链表完成。)

第一行为人数n;  第二行为报数k

10

4

对于约瑟夫问题当前实现方法大概有两种:

一:模拟:

链表模拟:

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 typedef struct List
 4 {
 5     int  data;
 6     struct List *next;
 7 }LinkList;
 8 int main()
 9 {
10     LinkList *L,*r,*s;
11     L = (LinkList *)malloc(sizeof(LinkList));
12     r =L;
13     int n,i;
14     int k;
15     scanf("%d%d",&n,&k);
16     for(i = 1;i<=n;i++)               ///尾插法建立循环链表
17     {
18         s = (LinkList *)malloc(sizeof(LinkList));
19         s->data = i;
20         r->next = s;
21         r= s;
22     }
23      
24     r->next =L->next;                  //让最后一个链表的下一个节点指向开头
25     LinkList *p;
26     p = L->next;                    
27      
28     while(p->next != p)                            //开始模拟(判断条件要注意:因为最后肯定剩下一个人, 所以最后一个数据的next还是他本身)
29     {
30         for(i = 1;i<k-1;i++)
31         {
32             p = p->next;                         //每k个数死一个人
33         }
34         p->next = p->next->next;                   //将该节点从链表上删除。
35         p = p->next;
36     }
37     printf("%d",p->data);
38     return 0;
39 }

数组模拟:

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n, k;
 5     scanf("%d%d", &n, &k);
 6     int i;
 7     int a[1001];
 8     int dead = 0;                              //表示已经死了多少人
 9     int num = 0;                             //num模拟没有被杀的人的喊数
10     for (i = 1; i<=n; i++)               //开始时每个人都可以报数,为了能得到最后一个人的编号,我们让初始值为i下标
11     {
12         a[i] = i;
13     }
14     for (i = 1;; i++)
15     {
16         if (i > n)
17         {
18             i = i%n;                     //如果大于总人数,我们就从头开始
19         }
20 
21         if (a[i] > 0)                        //如果当前这个人没有死,就报数
22           num++;
23         
24         if (k == num && dead != n-1)          //如果当前这个人报的数等于k 并且没有已经死亡n-1个人
25         {
26             num = 0;
27             a[i] = 0;
28             dead++;
29         }
30         else if(k == num && dead == n-1)  //如果这个人报数等于k,并且已经死了n-1个人,说明当前这个人就是最后的一个活着的了。。
31         {
32             printf("%d", a[i]);
33             break;
34         }
35             
36     }
37     return 0;
38 }

二、公式法(即递推):

递推过程:

 (1)第一个被删除的数为(m-1)%n;  

(2)设第二次的开始数字为k,

  做下映射:(即将数字的排列计算还是从0开始)

  k--->0

  k+1--->1 

 k+2--->2

  ---  ---

  k-2--->n-2 

此时剩下n-1个人 ,假如我们已经知道了n-1个人时,最后胜利者的编号为x,利用映射关系逆推,就可以得出n个人时,胜利者的编号为(x+k)%n(要注意的是这里是按照映射后的序号进行的)

其中k=m%n。

代入 

(x+k)%n<=>(x+(m%n))%n<=>(x%n + (m%n)%n)%n<=> (x%n+m%n)%n  <=> (x+m)%n 

 (3)第二个被删除的数为(m-1)%n-1

 (4)假设第三轮的开始数字为o,那这n-2个数构成的约瑟夫环为o,o+1,o+2,...,o-3,o-2。

映射 

o--->0 

 o+1--->1  

o+2--->2

  ---  ---  

o-2--->n-3  

这是一个n-2个人的问题。假设最后胜利者为y,那么n-1个人时,胜利者为(y+o)%(n-1),其中o等于m%(n-1)。代入可得(y+m)%(n-1)  

要得到n-1个人问题的解,只需要得到n-2个人问题的解,倒退下去。只有一个人时,胜利者就是编号0.小面给出递推式:

  f(1)=0;

  f(i)=(f[i-1]+m)%i;(i>1) 

这个公式的思想:

现在假设n=10

0 1 2 3  4 5 6 7 8 9 

k=3 

第一个人出列后的序列为:

 0 1 3 4 5 6 7 8 9 

即:  3 4 5 6 7 8 9 0 1(1式) 

我们把该式转化为: 0 1 2 3 4 5 6 7 8 (2式) 

则你会发现: ((2式)+3)%10则转化为(1式)了 

 也就是说,我们求出9个人中第9次出环的编号,最后进行上面的转换就能得到10个人第10次出环的编号了

 设f(n,k,i)为n个人的环,报数为k,第i个人出环的编号,则f(10,3,10)是我们要的结果

 当i=1时,  f(n,k,i) = (n+k-1)%n

 当i!=1时,  f(n,k,i)= ( f(n-1,k,i-1)+k )%n

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n, m,i,s=0;
 5     scanf("%d%d",&n,&m);
 6     for(i=2;i<=n;i++)
 7         s=(s+m)%i;
 8     printf("%d", s+1);
 9     return 0;
10 }

说一下:

 for(i=2;i<=n;i++)         s=(s+m)%i;

这个式子:

首先从2开始,因为1个人的时候报的数字的人为0号,结果已经确定了。不需要从i=0开始,要注意的是序列从0开始编号的,所以最后的输出结果也要加1.

s表示的是上一轮的结果,m代表是每多少个人出列一次,i代表当前已经出列了多少个人。

整个式子就是根据上一个的出列数和已经出列的人数来算的。

如果还不懂就仔细琢磨哦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

43830
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17830
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

20140
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

27540
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13350
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

28330
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

15420
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

50920
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

11510
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励