约翰夫环问题
题目简述:n个人围成一圈报数,每报到第m个人出列(持续报数,不重新开始),分析求解最后一个(第n个)出列的人
用数组的思想理解:
N代表第几个出列的人(N<=n),每一次出列相当于把数组向前移动m位。第N-1出列的人的位置为f(N−1,M),则N个出列的人,就是往前移动M位。
用链表的思想理解:
N个人看作是N个链表节点,节点1指向节点2,节点2指向节点3,……,节点N-1指向节点N,节点N指向节点1,这样就形成了一个环。然后从节点1开始1、2、3……往下报数,每报到M,就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点
递归法(近似数组)
该解法实际上是一种编号的变形,环在编号意义上的重构
分析可知,如果关注最后一个出列的是谁,不妨将所有人的编号减去m,递归化处理
程序分析:以m递减的方式是我们认为环没有改变的前提下,事实上环有重构(有人出列)的过程
现在假设n=10 m=3
0 1 2 3 4 5 6 7 8 9
第一个人出列后的序列为:
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式
容易发现: ((2式)+3)%10转化为(1式)
从0开始编号是为了方便取模运算,也便于数组化思想的体现
得到答案后需要加1,符合题意的编号
#include <cstdio>
int n,k;
int main()
{
scanf("%d %d",&n,&m);
int person=0;
for(int i=1;i<=n;i++)//代表次数(即总人数),依次出列
person=(person+m)%i;//由最后的编号倒推至最初的编号
printf("%d",person+1);
}//本算法可以形象的理解为撤销环的重构的过程,回归原始的编号过程
程序继续优化的思路
i与m增势不同,某一区间取余的效果没有体现,改进解法可以省略重复无效的步骤,加快撤销重构的过程
相当于分析 person每次加m,i 每次加1,问多少次之后person≥i 追击问题
#include <cstdio>
#include <cstdlib>
#include <cstring>
int main()
{
scanf("%d %d",&n,&m);
int i=1,person=0,p;
while(i<n){
p=(i-person)/(m-1)+((i-person)%(m-1)!=0);//距离除以相对速度得到时间 不整除的情况需要+1
if(i+p>n) p=n-i;//要判断是否大于n
person+=p*m;
i+=p;
person%=i;
}
printf("%d",person+1);
}
//该算法在理解上稍复杂 但数据足够大时 执行更快
链表法
删除结点的思想
#include<stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}Node , *LinkList;
void CreateLinkList_Head(LinkList &L,int n){
L=(LinkList)malloc(sizeof(Node));
L->data=1;
L->next=L;
LinkList s;
for(int i=0;i<n-1;i++){
s=(LinkList)malloc(sizeof(Node));
s->data=n-i;
s->next=L->next;
L->next=s;
}
}//创建链表 n为参加游戏总人数
void Print_L(LinkList L)
{
LinkList p;
p=L;
do
{
printf("%d",p->data);
p=p->next;
}
while(p!=L);
printf("\n");
} //单链表遍历输出函数
void ListDelete(LinkList &L,int i,int a){
int e;
LinkList p=L,s;
printf("出列编号依次为:\n");
for(int i=0;i<a;i++){
int j=1;
while((j+1)!=i)
{
j++;
p=p->next;
}
s=p->next;
e=s->data;
p->next=s->next;
free(s);
p=p->next;
printf("%d",e);
}
} //i为第几个报数的人被淘汰 a为淘汰多少人
#include <iostream>
#include "Node.h"
using namespace std;
int main()
{
LinkList pn;
int n,m,c;
scanf("%d %d",&n,&m); //c为最后保留多少人 本题应输入的是1
scanf("%d",&c);
CreateLinkList_Head(pn,n);
Print_L(pn);
ListDelete(pn,m,n-c);
Print_L(pn);
return 0;
}