josephus.cpp

各种算法

//约瑟夫环

#include"stdio.h"
#include"iostream.h"
#include"malloc.h"
typedef struct LNode
{
	int data;
	struct LNode *link;
}LNode,*LinkList;

void main()
{
	void JOSEPHUS(int n,int k,int m);
	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	JOSEPHUS(n,k,m);
}

void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
    /* p为当前结点  r为辅助结点，指向p的前驱结点  list为头节点*/
	LinkList p,r,list=NULL; 

    /*建立循环链表*/
    for(int i=0;i<n;i++)
    {
        p=(struct LNode *)malloc(sizeof(LNode));
        p->data=i;printf("%2d ",i);
        if(list==NULL)
            list=p;
        else
            r->link=p;
        r=p;
    }
	printf("\n");
    p->link=list; /*使链表循环起来*/
    p=list; /*使p指向头节点*/

    /*把当前指针移动到第一个报数的人*/
    for(i=0;i<k;i++)
    {
        r=p;
        p=p->link;
    }

    /*循环地删除队列结点*/
    while(p->link!=p)
    {
        for(i=0;i<m;i++)
        {
            r=p;
            p=p->link;
        }
        r->link=p->link;
        printf("%2d,",p->data);
        free(p);
        p=r->link;
    }
    printf("%2d\n",p->data);
}


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