专业版装修用什么网站做导航条,企业网站建设综合实训心得体会,市桥网站建设哪家好,北京网站建设首页题目描述
求解约瑟夫#xff08;Joseph#xff09;问题。有n个小孩围成一圈#xff0c;给他们从1开始依次编号#xff0c;从编号为1的小孩开始报数#xff0c;数到第m个小孩出列#xff0c;然后从出列的下一个小孩重新开始报数#xff0c;数到第m个小孩又出列#xff…题目描述
求解约瑟夫Joseph问题。有n个小孩围成一圈给他们从1开始依次编号从编号为1的小孩开始报数数到第m个小孩出列然后从出列的下一个小孩重新开始报数数到第m个小孩又出列…如此反复直到所有的小孩全部出列为止求整个出列序列。
如当n6m5时的出列序列是546231。n,m不大于20
输入
n m的值
输出
出列序列
样例输入
6 5
样例输出
5 4 6 2 3 1 问题解析
我们可以看到这个约瑟夫问题即小孩报数的问题其实就是链表问题。我们通过这道题需要掌握的是循环单链表的写法以c语言为例
一、循环链表的写法
1.先定义链表的结构体
struct child{int data;struct child* next;
};
然后再全局变量定 “头节点”和“约瑟夫环的两个参数”
struct child* headnode;
int n,m;
下面我们来定义两个函数分别是“创建空节点”与“创建有数据的节点”
struct child* emptynode(){struct child* p (struct child*)malloc(sizeof(struct child));p-data NULL;p-next NULL;return p;
}struct child* createnode(int num){struct child* p (struct child*)malloc(sizeof(struct child));p-data num;p-next NULL;return p;
}
我们可以看出这两段代码的主要差别其实就是p-dataNULL和p-datanum
接下来定义一个函数“createlistBytail”以尾接法创建循环单链表
void createlistBytail(struct child* headnode,int num){struct child* rheadnode;for (int i2; inum; i ){struct child* s createnode(i);s-next r-next;r-next s;rs;} r-next headnode;
}
那么其中需要注意的是这段代码看似为单纯的创建单链表其实我们在结尾处添加了一段代码
r-next headnode;
这段代码保证了单链表的循环也正因为这段代码使得我们的单链表成功升级为循环单链表
当然为了检验我们的链表是否创建成功我们可以写入这列代码来遍历出链表的数据
void printlist(struct child* headnode){struct child* pMove headnode;while(pMove) {printf(%d,pMove-data );pMove pMove-next ;}
} 接下来我们开始创建solve函数实现小孩的报数功能
void solve(struct child* headnode,int n,int m){int i,j;struct child* p;struct child* q;for(i1;in;i){p headnode;j 1;for(j1;jm-1;j){p p-next ;}q p-next ;printf(%d ,q-data );p-next q-next ;headnode p-next ;}
}
其中我们需要注意的是 我们在进行第二个for循环时jm-1这个数值不要搞错。我们为什么要jm-1呢因为我们要保证p是在第m个人的前一个人这样我们就可以使q指向p-next,也就是我们想要的那个第m个人实现精准查找然后精准“删除”。但是问题来了我们为什么不直接将p指向第m个人呢这样我们直接输出p不就好了么:(。非也非也你只是想到了输出数值的事但是后面的事你却没能想到。
我们在这段函数的主要任务是什么呢1.输出第m个人2.删除m,让m前一个人接上m后一个人3.将领头人headnode变成m的下一个人也就是说从m的下一个人开始报数。这样我们不难发现我们将p设为m的前一个人是要将p-next指向q-next实现删除m的目的,因为我们节点的指针能指向某节点的后面,却指向不了节点的前面,所以哦我们需要这样的一个p指向m前一个点。
最后我们编写主函数将上面的函数包装进去
其中我们要注意的是创建空节点与数据节点不在主函数里。
int main(){struct child* headnode createnode(1);scanf(%d %d,n,m);createlistBytail(headnode,n);//printlist(headnode);solve(headnode,n,m);return 0;
}这样我们的代码就算结束了。最后给大家奉上“小孩报数”即约瑟夫问题的完整版代码
#includestdio.h
#includestdlib.h
struct child{int data;struct child* next;
};struct child* headnode;
int n,m;struct child* emptynode(){struct child* p (struct child*)malloc(sizeof(struct child));p-data NULL;p-next NULL;return p;
}struct child* createnode(int num){struct child* p (struct child*)malloc(sizeof(struct child));p-data num;p-next NULL;return p;
}void createlistBytail(struct child* headnode,int num){struct child* rheadnode;for (int i2; inum; i ){struct child* s createnode(i);s-next r-next;r-next s;rs;} r-next headnode;
}void printlist(struct child* headnode){struct child* pMove headnode;while(pMove) {printf(%d,pMove-data );pMove pMove-next ;}
}void solve(struct child* headnode,int n,int m){int i,j;struct child* p;struct child* q;for(i1;in;i){p headnode;j 1;for(j1;jm-1;j){p p-next ;}q p-next ;printf(%d ,q-data );p-next q-next ;headnode p-next ;}
}int main(){struct child* headnode createnode(1);scanf(%d %d,n,m);createlistBytail(headnode,n);//printlist(headnode);solve(headnode,n,m);return 0;
}
