约瑟夫环(josephproblem)-尊龙官方平台

约瑟夫环(josephproblem)

el/2024/3/25 17:05:14

约瑟夫环(josephproblem)

题目:

有41个人围坐成一圈玩游戏,编号分别是0,1,2,…,39,40.

从1开始,每次数到3的人就退出游戏,下个人再次从1开始。

请问最后剩下的人的编号?

约瑟夫环有很多解题思路:

1.用一个标识数组来模拟;
2.用数据结构来实现;
3.用递归实现;
4.用递推实现。


用一个标识数组来模拟:

#include 
#include /******************************************************* 函数名称:josephproblem* 参数列表:*           1.n:从0到n-1共有n个人*           2.m:每次数到m就退出游戏* 返回值  :最后的人的编号* author  :test1280* history :2017/05/02* 备注    :* ***************************************************/
int josephproblem(int n, int m)
{int i = 0;int *flagarr = malloc(sizeof(int)*n);// 初始化标识数组for (i = 0; i1;}// 计数变量int cnt = 0;// 剩余人数,为1时退出int last = n;int index = 0;while (last != 1){if (flagarr[index] == 1){cnt  ;if (cnt == m){flagarr[index] = 0;last--;cnt = 0;}}index  ;index %= n;}int result = -1;for (i = 0; i0; i  );result = i;free(flagarr);flagarr = null;return result;
}int main()
{int n = 41;int m = 3;int result = josephproblem(n, m);printf("the result is %d.\n", result);return 0;
}

基本上就是模拟人工来进行,使用一个数组来标识当前的位置的人是否已经退出游戏。

这个仔细看看应该比较好理解。


用数据结构来实现:

#include 
#include using namespace std;/****************************************************** 函数名称:josephproblem* 参数列表:*           1.n:从0到n-1共有n个人*           2.m:数到m的人退出游戏* 返回值  :最后的人的编号* author :test1280* history:2017/05/02* 备注    :* **************************************************/
int josephproblem(int n, int m)
{queue<int> q;int i = 0, j;for (; iwhile (q.size() > 1){j = m-1;while (j--){q.push(q.front());q.pop();}q.pop();}return q.front();
}int main()
{int result = josephproblem(41, 3);cout<<"the result is "<return 0;
}

这个算是很简洁的了。

现将所有的编号(从0到n-1)存储到一个queue中,然后也还是模拟。

虽然简单易懂,但是效率低。


用递归实现:

使用递归来实现就很有意思。

首先,m%n得到的值一定是0到n-1范围内的某一值(不论m和n的大小关系如何)。

其次,如果我想要求n个人第一次数到m的那个人的编号,可以使用:

pos = m%nif pos == 0 thenpos = n - 1
elsepos = pos - 1
end

其实上面的这个逻辑等价于:

数到m的那个人的编号=(m%n-1 n)%n。

-1 n是防止变负数,再%n可以防止本身就是正值超出n范围。

再其次,我现在有个位置是pos,我想将其右移x个位置,求得右移后的位置?

右移后的位置=(pos x) % n

例如:

我有序列:0 1 2 3 4 此时n=5

我想要:

将2右移1位:2 1=3
将2右移2位:2 2=4
将2右移3为:2 3=5=0
将2右移4位:2 4=6=1
将2右移5位:2 5=7=2
将2右移6位:2 6=8=3
……

将pos右移x位就是(pos x)%n啦。

最后想想左移,我现在的位置是pos,想要将其左移x位,求左移后的位置?

还是那个序列:0 1 2 3 4 此时n=5

我想要:

将2左移1位:2-1=1
将2左移2位:2-2=0
将2左移3位:2-3=-1=4
将2左移4位:2-4=-2=3
将2左移5位:2-5=-3=2
将2左移5位:2-6=-4=1
……

将pos左移x位就是(pos-x n)%n啦。

想明白这几点后,我们可以思考:

我想要求n个人,实际是先求第一个退出的人的位置(记为delpos,意为delete-position),此时知道谁退出游戏了;

从退出游戏的那个人(delpos)的下一个人(记为k)开始,让他(k)成为0编号,相当于将所有的元素右移了n-1-k 1个(n-1是最后的编号,k是当前的编号,n-1-k是将k移动到n-1处的右移量,而0编号是n-1的下一个位置,故移动量为n-1-k 1);

然后将n-1个人(相对一开始的n个人少了一个,那个人已经数到m退出游戏了)按照谁数到m就退出游戏的规则再进行,得到n-1个人数m的最后的编号;

将此编号再左移n-1-k 1个位置回到原位置,即我们求得的n个人数m退出的解。

代码如下:

#include 
#include /******************************************** 函数名称:josephproblem* 参数列表:*          1.n:从0到n-1共有n个人*          2.m:数到m的人退出游戏* 返回值  :最后的人的编号* 备注    :* autohr  :test1280* history :2017/05/08
*******************************************/
int josephproblem(int n, int m)
{// 递归终止条件// 如果只有一个人,那么必然是返回0位置;if (n == 1)return 0;// 本次剔除的位置// 假设m==x*n:delpos = n-1(x为[0,...]);// 假设m=6, n=3, delpos=2=(6%3-1 3)%3;// 假设m=5, n=3, delpos=1=(5%3-1 3)%3;// 假设m=4, n=3, delpos=0=(4%3-1 3)%3;// 假设m=3, n=3, delpos=2=(3%3-1 3)%3;// 假设m=2, n=3, delpos=1=(2%3-1 3)%3;// 假设m=1, n=3, delpos=0=(1%3-1 3)%3;int delpos = (m % n -1   n) % n;// k是delpos的下一位// 假设m=6, n=3, k=0=(2 1)%3=0;// 假设m=5, n=3, k=2=(1 1)%3=2;// 假设m=4, n=3, k=1=(0 1)%3=1;// 假设m=3, n=3, k=0=(2 1)%3=0;// 假设m=2, n=3, k=2=(1 1)%3=2;// 假设m=1, n=3, k=1=(0 1)%3=1;int k = (delpos   1) % n;// 0 1 .. delpos k .. n-1;// 使上一行全部的数字向右移动,使得k移动到左首第0个;// 移动的位数为:((n-1) 1-k)%n;// 假设有序列:0 1 2 3 4 此时n=5;// 当delpos=1时(k=2),将k右移至0处,共移动3=((5-1) 1-2)%5;// 当delpos=4时(k=0),将k右移至0处,共移动0=((5-1) 1-0)%5;int move = ((n-1) 1-k)%n;// 由subresult回推到原位置int subresult = josephproblem(n-1, m);return (subresult - move   n) % n;
}int main()
{int result = josephproblem(10, 3);printf("result is %d\n", result);return 0;
}

其实核心步骤就是:先剔除一个,然后将剩余的人右移,求n-1个人的解,再左移回来即可。

就像一开始的拨号电话,先旋转数字键盘,然后放开手回退…

代码本来没有几行,注释比较多。。。

另,递归有个缺点,数字不能很大,否则栈溢出。

(如果有好的尾调用倒是可以避免,但是也有很多限制)


用递推实现:

有了上面递归的铺垫,我们能不能写的更简单一点?

我的递归是从大到小(解决n规模是要解决n-1规模,解决n-1规模是解决n-2规模…)进行的,我能否从小到大进行?

我们的0-(n-1)的序列,删除第一次数到m的人之后的序列为:

0 1 2 … k … n-2 n-1 共计n-2个。

将k右移n-1 1-k个位置后,得到的序列为:

k
k 1
k 2
...
n-2
n-1
0
1
...
k-2

其中k对应0编号(右移):

k       0
k 1     1
k 2     2
...
n-2     ?(p)
n-1     ?
0       ?
1       ?
...
k-2     n-2

其中有很多?不知道值是多少。

假定第一个?为p,很容易有等式:p-2=(n-2)-(k 2),得出p=n-k-2,于是:

k       0
k 1     1
k 2     2
...
n-2     n-k-2
n-1     n-k-1
0       n-k
1       n-k 1
...
k-2     n-2
结束......x1<-----x2

我们的目的是从右侧向左侧进行推导:

假定右侧的最后编号是x2,x2对应的左侧编号是x1,即从左侧右移思考改变为:右侧左移。

左侧的右移量是k,那么右侧的左移量也是k,此时还记得我们之前的左移右移吗?

x1=(x2-k n)%n

而k的值是多少?看看上面的递归:

k = (delpos 1) % n = ((m % n -1 n) % n 1)%n

x5=(x4-k4 4)%4;
x4=(x3-k3 3)%3;
x3=(x2-k2 2)%2;
x2=(x1-k1 1)%1;
x1仔细一想,当然就是0啦。

f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果是f[n]。

f[1]=0
f[i]=(f[i-1] -k*   i) % i

代码如下:

#include 
#include /******************************************** 函数名称:josephproblem* 参数列表:*          1.n:从0到n-1共有n个人*          2.m:数到m的人退出游戏* 返回值  :最后的人的编号* 备注    :* autohr  :test1280* history :2017/05/08
*******************************************/
int josephproblem(int n, int m)
{int s = 0;for (int i=2; i<=n; i  ){int k = ((m % i - 1   i) % i   1) % i;s = (s -k   i) % i;}return s;
}int main()
{int result = josephproblem(41, 3);printf("the result is %d\n", result);return 0;
}

那么一长串其实可以化简:

int josephproblem(int n, int m)
{int s = 0;for (int i=2; i<=n; i  ){s = (s   m) % i;}return s;
}

至于是怎么化简的,大家可以多找找规律。

其实我更提倡用数学方法化简。。回头我再看看再补上来,嘿嘿。

额,至此,几种解题方法都实现过啦,恩,大家可以多看看,多想想,其实还有很多可以优化来处理。

参考资料:

1.http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/
2.http://blog.csdn.net/kangroger/article/details/39254619
3.https://www.zhihu.com/question/20065611
……

如果有错误请大伙指出来,哈!


http://www.ngui.cc/el/5127165.html

相关文章

c/c :使用数组模拟链表

c/c:使用数组模拟链表 链表中每一个node都由两部分组成: 1.真实的数据; 2.下一个数据的位置; 通常的实现可以使用指针作为指示下一个数据的位置的方式,当没有一个合法的数据存在,就将指针部分置为null&…

c/c :全排列问题

c/c:全排列问题 啥叫全排列? 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。 当mn时所有的排列情况叫全排列。 假设现在有三个数字:…

杭电-pid1181-变形课

杭电-pid1181-变形课 problem description 呃......变形课上harry碰到了一点小麻烦,因为他并不像hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使a物体变成b物…

杭电-pid1008-elevator

杭电-pid1008-elevator 好吧,其实这道题是水过去的。。 problem description the highest building in our city has only one elevator. a request list is made up with n positive numbers. the numbers denote at which floors the elevator will stop, in s…

杭电-pid1012-u calculate e

杭电-pid1012-u calculate e #include #include int main() {printf("n e\n- -----------\n0 1\n1 2\n2 2.5\n");double num 2.5;double base 2;int i 3;while (i < 10){base base * i;num num 1 / base;printf("%d %…

杭电-pid1013-digital roots

杭电-pid1013-digital roots 九余数定理 #include using namespace std;int main() {string s;while (cin>>s){if (s[0] 0){break;}int sum 0, i;for (i 0; i < s.length(); i){sum sum s[i] - 0;}if (sum % 9 0){cout<<"9"<…

linux:curl的使用

linux:curl的使用 curl is a tool to transfer data from or to a server, using one of the supported protocols (http, https, ftp, ftps, tftp, dict, telnet, ldap or file). the command is designed to work without user interaction. curl支持多种协…

c/c :类型转换

c:dynamic_cast、static_cast 实验环境: [test1280localhost ~]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux …… gcc 版本 4.1.2 20080704 (red hat 4.1.2-54) c/c中…

lua:ipairs/pairs

lua:ipairs/pairs lua中有两个很类似的函数:ipairs以及pairs。 实验环境: [test1280localhost 20170531]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux [te…

常用linux命令:ssh

常用linux命令:ssh 以后随时记录一些工作中用到的命令,这些命令是常用的,但是参数可能比较多,容易混淆,不是很容易记住;也有可能某天忽然间需要用了,还要man一下就… 总之吧,这里讲…
网站地图