# 约瑟夫环的C语言实现

2018-01-29 12:40:10来源:网络收集作者:程序诗人人点击

约瑟夫环问题 ：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _JOSEPH_H__
#define _JOSEPH_H__

#include
#include
#include

typedef struct Joseph_ring
{
int num;
struct Joseph_ring* next;
}Joseph,*pJoseph;

pJoseph CreateJoseph(int n);
void joseph_r(pJoseph head, int m);

#endif
#include"Joseph ring.h"

pJoseph CreateJoseph(int n)
{
int i = 0;
pJoseph head = NULL;
pJoseph tail = NULL;
head = (pJoseph)malloc(sizeof(Joseph));
head->next = head;    //先让第一个结点head指向自己形成一个环
head->num = 1;
tail = head;
for (i = 2; i <= n; i++)     //循环向环中插入结点
{
pJoseph New = (pJoseph)malloc(sizeof(Joseph));
New->num = i;
New->next = tail->next;
tail->next = New;
tail = New;
}
return head;
}
void joseph_r(pJoseph head, int m)
{
assert(head);
pJoseph cur = NULL;
pJoseph prev = NULL;
pJoseph del = NULL;
cur = head;
int i = 0;
while (head->next != head)
{
for (i = 1; i < m - 1; i++)  //找到要出列的人的前一个
{
cur = cur->next;
}                          //cur当前表示要出列的人的前一个
del = cur->next;
cur->next = del->next;
printf("%d ", del->num);
if (del == head)
{
head = del->next;
}
free(del);
cur = cur->next;
}
printf("%d/n", head->num);
}
}

#include

#include

int n;

int length(int *p)

{

int i, k = 0;

for(i = 0; i < n; i++)

{

if(*(p+i) == 0)

{

k++;

}

}

return k;

}

int main()

{

int i, k, j = 0;

int *a;

printf("Please input the number:");

scanf("%d", &n);

printf("Which number go out:");

scanf("%d", &k);

a = malloc(sizeof(int) * n);

for(i = 0; i < n; i++)

{

a[i] = 0;

}

while(length(a) > 1)

{

for(i = 0; i < n; i++)

{

if(a[i]
== 0)

{

j++;

if(j
== 3)

{

a[i]
= 1;

j
= 0;

}

}

}

}

for(i = 0; i < n; i++)

{

if(a[i] == 0)

{

printf("%d/n",
i + 1);

break;

}

}

free(a);

return 0;

}