用c语言实现约瑟夫环

正好之前写过基础的约瑟夫环，稍作修改就可以满足你的题目

#include <stdio.h>

#include <stdlib.h>

typedef struct _node {

    int id

    int key

    struct _node *next

} Linklist

int main() {

int n, m

scanf("%d %d", &n, &m)

int i, count = 0

Linklist *head = (Linklist*)malloc(sizeof(Linklist)), *tail = head

head->id = 1

scanf("%d", &head->key)

head->next = head

for(i = 2 i <= n i++) {

Linklist *p = (Linklist*)malloc(sizeof(Linklist))

p->id = i

scanf("%d", &p->key)

p->next = head

tail->next = p

tail = p

}

while(head != tail) {

if(++count % m) {

tail = head

} else {

    m = head->key

    count = 0

printf("%d ", head->id)

tail->next = head->next

free(head)

}

head = tail->next

}

printf("%d\n", head->id)

free(head)

return 0

}

1、约瑟夫问题：Joseph问题的一种描述是：编号为1、2、……、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

2、例程：

#include

#include

typedef int ElemType

typedef struct LNode{

ElemType dataint num

struct LNode *next

}LNode,*LinkList

void CreateList_L(LinkList *L,int n)

{ int i=0

ElemType e

LinkList p,q

*L=(LinkList)malloc(sizeof(LNode))

(*L)->next=NULL(*L)->data=n

q=*L

while(i

data=ep->num=i+1

p->next=NULL

q->next=p

q=p

i++

}

p->next=(*L)->next

}

void PrintList(LinkList L)

{ int i=0

LinkList p

p=L->next

while(i

data)

{

printf("%5d",p->data)

p=p->next

i++

}

printf("\n")

}

void Put(LinkList *L)

{ int i,mLinkList p,q

printf("input a number:\n")

scanf("%d",&m)

q=(*L)->next

while((*L)->data)

{for(i=0i

next

}

printf("%5d",q->num)

m=q->data

p->next=q->next

free(q)

q=p->next

(*L)->data=(*L)->data-1

}

}

void main()

{LinkList L

int a

printf("请输入人数:")

scanf("%d",&a)

printf("请输入密码:")

CreateList_L(&L,a)

printf("您输入的数字为:\n")

PrintList(L)

Put(&L)

}

约瑟夫问题：

#include

struct

Node

{

int

data

Node

*pNext

}

void

main()

{

int

n,k,m,i

Node

*p,*q,*head

cout<<"输入n的值:"

cin>>n

cout<<"输入起始报数人号码k的值:"

cin>>k

cout<<"输入

数到m出列的m的值:"

cin>>m

head=(Node*)new

Node

//确定头结点

p=head

for(i=1i<=n-1i++)

//赋初值

{

p->data=i

p->pNext=(Node*)new

Node

//为下一个新建内存

p=p->pNext

}

p->data=n

//最后一个单独处理

p->pNext=head

//指向头，形成循环链表

p=head

while(p->data!=(p->pNext)->data)

//p->data==(p->pNext)->data表示只剩下一个结点的

{

while(p->data

!=k)

//寻找编号为k的结点

p=p->pNext

if(m==1)

{

for(i=1i<=ni++)

{

cout<

data<<'\t'

p=p->pNext

}

cout<<'\n'

return

}

else

for(i=1i

pNext

//q为报m的结点

cout<

data<<"\t"

//输出报m的结点的值

k=(q->pNext)->data

//k为下一个报数的起点

p->pNext=q->pNext

//删除报m的结点

}

cout<

data<<'\n'

//输出最后一个结点的值

}

---