约瑟夫问题——C语言实现
约瑟夫问题约瑟夫问题简述约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后 [1]结果+1即为原问题的解。代码实现#include <stdi...
·
约瑟夫问题
约瑟夫问题简述
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后 [1] 结果+1即为原问题的解。
代码实现
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int local;
struct node * next;
}LNode,*LinkList;
void CreateLinkList_L(LinkList L,int n);
void Josephus(LinkList L,int n,int m,int k);
void main()
{
//创建循环单链表 结点个数是 n
//报数 报到m的出去 也就是 删除该结点
LinkList L = (LinkList)malloc(sizeof(LNode));
L->local = 1;
CreateLinkList_L(L,10);
Josephus(L,10,4,3);
}
void CreateLinkList_L(LinkList L,int n)
{
int i;
LinkList s,r;
r = L;
for(i = 2;i <= n;i++)
{
s = (LinkList)malloc(sizeof(LNode));
s->local = i;
r->next = s;
r = r->next;
}
r->next = L;
}
void Josephus(LinkList L,int n,int m,int k) //m = 3 , k = 2
{
int i = 1,j = 1;
LinkList p,q,s;
p = L;
//确定第一个喊话的同学
while(i < k)
{
q = p;
p = p->next;
i++;
}
while(p->next != p)
{
//一个循环用来喊话,一直喊m次
while(j < m)
{
q = p;
p = p->next;
j++;
}
s = p;
p = p->next;
q->next = p;
printf("%d号淘汰!\n",s->local);
free(s);
j = 1;
}
printf("%d胜出!",p->local);
}
更多推荐
所有评论(0)