约瑟夫环
约瑟夫环问题是一道常见的数学应用问题.假如,有total个人(total>2)围坐一圈,从第first(first默认为1)个人开始报数,报到num的人出圈,直到全部人出圈. 要求模拟出圈过程,并输出出圈人的编号顺序. 这道题的解决方案有很多种,这里,我给大家列出c语言链表,java集合以及c语言数组的解题方式.
------------------------------------------------ 华 丽 的 分 割 线 -----------------------------------------
首先,给大家先讲一下解题思路.
假设,一共有12个人围坐一圈玩游戏,从第一个人开始报数,数到5的人出列. 1 2 3 4 5 6 7 8 9 10 11 12
第一轮游戏结束后5号玩家出列,场上玩家为: 1 2 3 4 6 7 8 9 10 11 12 ,6号玩家从1开始继续报数
第二轮游戏结束后,10号玩家出列,场上玩家为: 1 2 3 4 6 7 8 9 11 12 ,11号玩家从1开始继续报数
第三轮游戏结束后,3号玩家出列,场上玩家为: 1 2 4 6 7 8 9 11 12 ,4号玩家从1开始继续报数
第四轮游戏结束后,9号玩家出列,场上玩家为: 1 2 4 6 7 8 11 12 ,11号玩家从1开始继续报数
第五轮游戏结束后,4号玩家出列,场上玩家为: 1 2 6 7 8 11 12 ,6号玩家从1开始继续报数
第六轮游戏结束后,12号玩家出列,场上玩家为: 1 2 6 7 8 11 ,1号玩家从1开始继续报数
第七轮游戏结束后,8号玩家出列,场上玩家为: 1 2 6 7 11 ,11号玩家从1开始继续报数
第八轮游戏结束后,7号玩家出列,场上玩家为: 1 2 6 11 ,11号玩家从1开始继续报数
第九轮游戏结束后,11号玩家出列,场上玩家为: 1 2 6 ,1号玩家从1开始继续报数
第十轮游戏结束后,2号玩家出列,场上玩家为: 1 6 ,6号玩家从1开始继续报数
第十一轮游戏结束后,6号玩家出列,场上玩家只剩1号一人.由此可得出圈顺序为: 5 10 3 9 4 12 8 7 11 2 6 1
接下来,就轮到代码出场了~~
1.c语言链表解题代码:
#include <stdio.h>
#include <malloc.h>
#define total 12 //总人数
#define num 5
typedef struct Lnode
{
struct Lnode *next;
int data; //玩家的报号
}Lnode;
Lnode* init() //初始化
{
//先创建第一个结点
Lnode *p, *q, *head;
int i;
p = (Lnode *)malloc(sizeof(Lnode));
head = p;
p->data = 1;
//创建剩余结点
for (i = 2; i <= total; i++)
{
q = (Lnode *)malloc(sizeof(Lnode));
q->data = i;
p->next = q;
p = q;
//p = p->next;
}
p->next = head;
return head;
}
void gameStart(Lnode *head) //游戏开始
{
int i;
Lnode *q = head, *h;
while(q->next != q)
{
for (i = 1; i < num; i++) //第num个人出局
{
h = q;
q = q->next; //h指向出局玩家的前一个人
}
printf("%d ", q->data);
h->next = q->next;
free(q);
q = h->next;
}
printf("\n");
}
int main(void)
{
Lnode *p = init();
gameStart(p);
return 0;
}
2.java集合解题代码:
package josephRing;
import java.util.ArrayList;
public class JosephRing { //约瑟夫环
public static void main(String[] args) {
badlyNumber(12, 5);
}
private static void badlyNumber(int total, int num) {
ArrayList<Integer> list = new ArrayList<>(); //用集合来存储1到num的人
for (int i = 1; i <= total; i++) { //将1到total的数添加到集合list中
list.add(i);
}
int count = 1; //count用来记录人的数号
for (int i = 0; list.size() >= 1; i++) {
if (i == list.size()) { //当i增长到最大的索引+1时 i重新归0
i = 0;
}
if (count % num == 0) { //该人数号为num的倍数时出圈
System.out.print(list.get(i) + " ");
list.remove(i--);
}
//i = (i + 1)%list.size(); --> 方法2 同时去掉for循环中的i++
count++;
}
}
}
3.c语言数组(伪链表)解题方法. 由于c数组代码我是用linux最小界面编程的,自己才疏学浅不知道该怎样才能把linux最小界面中的文档导入到windows系统中来,这里我就附上代码的截图吧,大家勿怪~~
以及...调试结果~
博客就到这里了,本文为原创作品,转载请注明出处~
这是自己的第一篇博客,若有什么欠缺之处还请大家多多包涵.